研究无限答案的纯探索问题，提出新算法实现渐近最优。
Pure Exploration with Infinite Answers
- 提出广义框架Sticky-Sequence Track-and-Stop，适用于无限答案场景。
- 证明了该问题的实例相关下界，揭示旧方法失效原因。
- 适用于函数回归、纳什均衡等连续决策任务，适合理论研究者。
我们研究正确答案集合可能为无穷的纯探索问题，例如在贝叶斯带宽中对均值函数进行回归，或通过查询噪声支付矩阵值学习纳什均衡。本文推导出此类问题的实例相关下界，并分析表明，现有针对有限答案问题的Sticky Track-and-Stop方法在此更一般设置下无法实现渐近最优。最后，我们提出一个通用框架——Sticky-Sequence Track-and-Stop，它同时推广了Track-and-Stop和Sticky Track-and-Stop，且具备渐近最优性。由于其普适性，我们的分析还揭示了原有方法在特定情况下仍可达到最优的情形。
原文摘要 · Abstract (English)
We study pure exploration problems in which the set of correct answers is possibly infinite. For example, such problems arise when regressing a continuous function on the means of the bandit or when learning Nash equilibria by querying noisy values of the payoff matrix. We derive an instance-dependent lower bound for these problems. By analyzing it, we discuss why existing methods (i.e., Sticky Track-and-Stop) for finite answer problems fail at being asymptotically optimal in this more general setting. Finally, we present a framework, Sticky-Sequence Track-and-Stop, which generalizes both Track-and-Stop and Sticky Track-and-Stop, and that enjoys asymptotic optimality. Due to its generality, our analysis also highlights special cases where existing methods enjoy optimality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。