No-Regret Linear Bandits beyond Realizability
No-Regret Linear Bandits beyond Realizability
复制标题
DOI：
10.48550/arxiv.2302.13252
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Chong Liu;Ming Yin;Yu-Xiang Wang
中科院分区：
文献类型：
--
作者：
Chong Liu;Ming Yin;Yu-Xiang Wang
我们研究线性土匪时，潜在的奖励函数不是线性的。现有的工作依赖于统一的误指定参数$\epsilon$，该参数衡量最佳线性逼近的超范误差。当$\n>0$时，这将导致不可避免的线性遗憾。我们描述了一个更自然的模型，只需要近似误差在每个输入$x$是成比例的次优差距在$x$。它抓住了直觉，对于优化问题，接近最优的区域应该更重要，我们可以容忍次优区域中更大的近似误差。令人惊讶的是，我们表明，经典的LinUCB算法-设计的可实现的情况下-是自动鲁棒性对这种间隙调整的误指定。它实现了一个接近最优的$\sqrt{T}$遗憾的问题，最有名的遗憾是几乎线性的时间范围$T$。从技术上讲，我们的证明依赖于一个新颖的自约束的论点，限制了部分的遗憾，由于错误指定的遗憾本身。
We study linear bandits when the underlying reward function is not linear. Existing work relies on a uniform misspecification parameter $\epsilon$ that measures the sup-norm error of the best linear approximation. This results in an unavoidable linear regret whenever $\epsilon>0$. We describe a more natural model of misspecification which only requires the approximation error at each input $x$ to be proportional to the suboptimality gap at $x$. It captures the intuition that, for optimization problems, near-optimal regions should matter more and we can tolerate larger approximation errors in suboptimal regions. Quite surprisingly, we show that the classical LinUCB algorithm -- designed for the realizable case -- is automatically robust against such gap-adjusted misspecification. It achieves a near-optimal $\sqrt{T}$ regret for problems that the best-known regret is almost linear in time horizon $T$. Technically, our proof relies on a novel self-bounding argument that bounds the part of the regret due to misspecification by the regret itself.