解决半参数强化学习中最佳动作识别的样本效率问题
Nearly Optimal Best Arm Identification for Semiparametric Bandits
- 采用正交化回归与新型XY设计，提升算法稳定性
- 理论证明样本复杂度近乎最优，仅差对数因子和d²项
- 适合关注高效探索与在线决策的研究者
我们研究半参数强化学习中的固定置信度最佳动作识别（BAI）问题，其中奖励为臂特征的线性组合加上未知的加性基线偏移。与线性带宽不同，该设定需使用正交化回归，且其实例最优样本复杂度长期未解。针对转换设置，我们建立了可实现的实例相关下界，由移位特征上的线性带宽复杂度刻画。随后提出一种基于新XY设计的计算高效的分阶段淘汰算法。分析表明，其高概率样本复杂度上界近乎最优，仅差对数因子和一个d²项。在合成实例及Jester数据集上的实验显示，相比先前基线有显著提升。
原文摘要 · Abstract (English)
We study fixed-confidence Best Arm Identification (BAI) in semiparametric bandits, where rewards are linear in arm features plus an unknown additive baseline shift. Unlike linear-bandit BAI, this setting requires orthogonalized regression, and its instance-optimal sample complexity has remained open. For the transductive setting, we establish an attainable instance-dependent lower bound characterized by the corresponding linear-bandit complexity on shifted features. We then propose a computationally efficient phase-elimination algorithm based on a new $XY$-design for orthogonalized regression. Our analysis yields a nearly optimal high-probability sample-complexity upper bound, up to log factors and an additive $d^2$ term, and experiments on synthetic instances and the Jester dataset show clear gains over prior baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。