提出首个兼具多种理论保证的半参数博弈实验设计方法。
Experimental Design for Semiparametric Bandits
- 基于正交化回归的实验设计，实现最优学习效率。
- 达到最小化误差界$ ilde{O}( ext{sqrt}{dT})$，匹配已知下界。
- 适合需要高可靠性与快速识别最优策略的研究者。
我们研究有限臂半参数博弈问题，其中每条臂的收益由线性部分与未知且可能对抗性的偏移共同构成。该模型严格推广了经典线性博弈，更贴近实际场景。本文提出首个同时具备尖锐遗憾界、PAC界和最优臂识别保证的实验设计方法。所提方法在一般条件下实现最小化遗憾界$ ilde{O}( ext{sqrt}{dT})$，与有限臂线性博弈的已知下界一致；在存在正子最优间隙条件下，进一步实现对数级遗憾。这些结果源于对正交化回归的精细非渐近分析，达到了最优$ ext{sqrt}{d}$收敛速率，为一大类半参数博弈问题提供了稳健高效的求解路径。
原文摘要 · Abstract (English)
We study finite-armed semiparametric bandits, where each arm's reward combines a linear component with an unknown, potentially adversarial shift. This model strictly generalizes classical linear bandits and reflects complexities common in practice. We propose the first experimental-design approach that simultaneously offers a sharp regret bound, a PAC bound, and a best-arm identification guarantee. Our method attains the minimax regret $\tilde{O}(\sqrt{dT})$, matching the known lower bound for finite-armed linear bandits, and further achieves logarithmic regret under a positive suboptimality gap condition. These guarantees follow from our refined non-asymptotic analysis of orthogonalized regression that attains the optimal $\sqrt{d}$ rate, paving the way for robust and efficient learning across a broad class of semiparametric bandit problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。