未知边缘参数导致批量非参数强化学习有不可规避的性能损失。
The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin
- 通过优化批量分配与探索策略实现自适应
- 性能损失随时间呈多项式增长，由维度和光滑度决定
- 当批次数超过双对数级别时，损失几乎消失
研究在边缘条件未知的情况下，批量非参数上下文老虎机问题的统计代价。我们引入后悔膨胀率，即自适应算法与已知边缘参数的最优算法的后悔比。结果表明，最优后悔膨胀率随时间 $T$ 呈多项式增长，其指数由依赖于维度、光滑性和批次数 $M$ 的凸优化问题决定。该优化问题的解直接给出最优算法的批量分配与探索策略。基于此，我们提出 RoBIN（RObust batched algorithm with adaptive BINning），在多对数因子内达到最优后悔膨胀。研究揭示了一种新的自适应障碍：在批量设置下，无法避免对未知边缘参数的适应性惩罚，其程度由变分问题精确刻画。值得注意的是，当批次数超过 $\log \log T$ 阶时，该障碍基本消失，仅需双重对数级更新即可恢复近似最优后悔率。
原文摘要 · Abstract (English)
We study batched nonparametric contextual bandits under a margin condition when the margin parameter $α$ is unknown. To capture the statistical cost of this ignorance, we introduce the regret inflation criterion, defined as the ratio between the regret of an adaptive algorithm and that of an oracle knowing $α$. We show that the optimal regret inflation grows polynomially with the horizon $T$, with exponent given by the value of a convex optimization problem that depends on the dimension, smoothness, and number of batches $M$. Moreover, the minimizer of this optimization problem directly prescribes the batch allocation and exploration strategy of a rate-optimal algorithm. Building on this principle, we develop RoBIN (RObust batched algorithm with adaptive BINning), which achieves the optimal regret inflation up to polylogarithmic factors. These results reveal a new adaptivity barrier: under batching, adaptation to an unknown margin parameter inevitably incurs a polynomial penalty, sharply characterized by a variational problem. Remarkably, this barrier vanishes once the number of batches exceeds order $\log \log T$; with only a doubly logarithmic number of updates, one can recover the oracle regret rate up to polylogarithmic factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。