首个无需调参的线性带子问题动态遗憾算法，自动适应最优切换次数。
Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
- 通过组合多个算法实现自适应切换次数
- 达到最优遗憾上界√(d(1+S_T)T)，无需事先知道切换数
- 适合在线学习中比较序列频繁变化的场景
我们研究无约束对抗性线性带子问题中的动态遗憾最小化。在此设定下，学习者需相对于任意比较器序列 $\boldsymbol{u}_1,\ldots,\boldsymbol{u}_T$ 在 $\mathbb{R}^d$ 中最小化累积损失，但每轮仅获得点评估反馈。我们提出一种简单方法，结合多个带子算法的性能保证，可最优适应任意比较器序列的切换次数 $S_T = \sum_t\mathbb{I}\{\boldsymbol{u}_t \neq \boldsymbol{u}_{t-1}\}$。特别地，我们首次提供了在不依赖 $S_T$ 先验知识的情况下，实现最优遗憾上界 $\mathcal{O}\big(\sqrt{d(1+S_T) T}\big)$ 的线性带子算法（忽略对数项），从而解决了长期悬而未决的开放问题。
原文摘要 · Abstract (English)
We study dynamic regret minimization in unconstrained adversarial linear bandit problems. In this setting, a learner must minimize the cumulative loss relative to an arbitrary sequence of comparators $\boldsymbol{u}_1,\ldots,\boldsymbol{u}_T$ in $\mathbb{R}^d$, but receives only point-evaluation feedback on each round. We provide a simple approach to combining the guarantees of several bandit algorithms, allowing us to optimally adapt to the number of switches $S_T = \sum_t\mathbb{I}\{\boldsymbol{u}_t \neq \boldsymbol{u}_{t-1}\}$ of an arbitrary comparator sequence. In particular, we provide the first algorithm for linear bandits achieving the optimal regret guarantee of order $\mathcal{O}\big(\sqrt{d(1+S_T) T}\big)$ up to poly-logarithmic terms without prior knowledge of $S_T$, thus resolving a long-standing open problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。