提出首个线性椭球动作集下的最优算法，兼具理论最优与高效计算。
Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
- 通过新序列估计法结合探索-提交策略，设计非乐观、非采样型算法。
- 理论证明算法达到Ω(√T)量级最小最大后悔下界，且可实现多项式时间运行。
- 适用于高维在线学习场景，尤其适合对计算效率有要求的研究者。
我们研究动作集为椭球体的线性随机老虎机问题。首次给出了该问题的最小最大最优算法。首先推导出一个新颖的信息论下界，任何算法的后悔至少为 Ω( min(d σ√T + d ‖θ‖_A, ‖θ‖_A T))，其中 d 为维度，T 为时间范围，σ² 为噪声方差，A 为定义动作集的矩阵，θ 为未知参数向量。随后提出一个后悔上界与此下界相差至多一个通用常数的算法。该算法非经典：既不基于乐观原则，也不是采样型。核心思想是先通过新序列过程估计 ‖θ‖，再据此执行探索-提交策略。算法计算高效，单次运行时间仅需 O(dT + d² log(T/d) + d³)，内存占用为 O(d²)，远优于已知的乐观型算法（后者无法在多项式时间内实现）。我们还证明该算法在局部渐近最小最大意义下最优，这是比最小最大最优更强的概念。最后通过数值实验验证了理论结果。
原文摘要 · Abstract (English)
We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least $Ω(\min(d σ\sqrt{T} + d \|θ\|_{A}, \|θ\|_{A} T))$ where $d$ is the dimension, $T$ the time horizon, $σ^2$ the noise variance, $A$ a matrix defining the set of actions and $θ$ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate $\|θ\|$, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$, in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。