提出首个理论最优且实用的分批线性强化学习算法
Optimal and Practical Batched Linear Bandit Algorithm
- 结合臂淘汰与正则化G-最优设计，实现分批优化
- 仅需O(log log T)个批次，达到最小最大后悔率
- 计算开销低，实测性能优于现有最优方法
我们研究受限自适应性的线性带宽问题，即分批线性带宽。尽管现有方法在理论上可实现近似最优后悔率，但通常计算成本过高或实际表现不佳。本文提出BLAE，一种新分批算法，融合臂淘汰与正则化G-最优设计，在大K和小K情形下首次实现最小最大后悔率（对数因子内最优），且仅使用O(log log T)个批次。分析引入新的批处理最优设计技术与更精细的集中界。关键在于，BLAE具有低计算开销和强实证性能，在广泛数值实验中优于当前最先进方法。因此，BLAE是首个在所有场景下兼具理论最优性与实际优越性的分批线性带宽算法。
原文摘要 · Abstract (English)
We study the linear bandit problem under limited adaptivity, known as the batched linear bandit. While existing approaches can achieve near-optimal regret in theory, they are often computationally prohibitive or underperform in practice. We propose BLAE, a novel batched algorithm that integrates arm elimination with regularized G-optimal design, achieving the minimax optimal regret (up to logarithmic factors in $T$) in both large-$K$ and small-$K$ regimes for the first time, while using only $O(\log\log T)$ batches. Our analysis introduces new techniques for batch-wise optimal design and refined concentration bounds. Crucially, BLAE demonstrates low computational overhead and strong empirical performance, outperforming state-of-the-art methods in extensive numerical evaluations. Thus, BLAE is the first algorithm to combine provable minimax-optimality in all regimes and practical superiority in batched linear bandits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。