提出新算法打破批量识别最优臂的效率瓶颈，更省样本和批次。
Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids
- 设计自适应网格采样分配策略，动态平衡探索与利用。
- 样本复杂度近似最优，批次复杂度突破对数级下限。
- 适用于多臂及线性强化学习场景，实测更高效。
我们研究多臂老虎机中的批量最优臂识别问题，目标是在最小化样本量和批次数量的同时识别最优臂。提出一种新算法，实现近似最优的样本复杂度，并具有实例相关的批次复杂度，突破了传统的 $\\(log(1/Δ_2)\\)$ 瓶颈。核心贡献在于一种新颖的采样分配机制，能有效协调批量规模下的探索与利用。实验表明，该方法在多种设置下均表现出更高的批量效率。同时，该框架可扩展至线性老虎机场景，同样获得显著改进。
原文摘要 · Abstract (English)
We investigate the problem of batched best arm identification in multi-armed bandits, where we aim to identify the best arm from a set of $n$ arms while minimizing both the number of samples and batches. We introduce an algorithm that achieves near-optimal sample complexity and features an instance-sensitive batch complexity, which breaks the $\log(1/Δ_2)$ barrier. The main contribution of our algorithm is a novel sample allocation scheme that effectively balances exploration and exploitation for batch sizes. Experimental results indicate that our approach is more batch-efficient across various setups. We also extend this framework to the problem of batched best arm identification in linear bandits and achieve similar improvements.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。