研究随机多臂赌博机中批处理纯探索的最少批次数，揭示算法效率极限。
The Batch Complexity of Bandit Pure Exploration
- 提出批处理算法，仅在有限批次间切换采样策略。
- 给出任意纯探索任务的样本与批次下界，验证方法最优性。
- 适用于最优臂识别和阈值探测场景，适合资源受限环境。
在随机多臂赌博机的固定置信度纯探索问题中，算法需迭代采样各臂，并尽早停止并返回关于臂分布的正确答案。本文关注批处理方法，即仅在有限批次间改变采样行为。我们给出了任意纯探索任务下，任何高效采样算法所需的最小批次数的实例依赖下界。随后，提出一种通用批处理算法，并证明其期望样本复杂度与批复杂度的上界。通过最优臂识别与阈值探测两个任务验证上下界。
原文摘要 · Abstract (English)
In a fixed-confidence pure exploration problem in stochastic multi-armed bandits, an algorithm iteratively samples arms and should stop as early as possible and return the correct answer to a query about the arms distributions. We are interested in batched methods, which change their sampling behaviour only a few times, between batches of observations. We give an instance-dependent lower bound on the number of batches used by any sample efficient algorithm for any pure exploration task. We then give a general batched algorithm and prove upper bounds on its expected sample complexity and batch complexity. We illustrate both lower and upper bounds on best-arm identification and thresholding bandits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。