提出高效无换悔算法，解决高维组合强化学习难题。
Efficient Swap Regret Minimization in Combinatorial Bandits
- 设计新算法实现对数级依赖于动作数的换悔值
- 后悔值随时间呈次线性增长，且在理论上紧致
- 适用于多种经典场景，每轮计算开销也对数级
本文研究组合多臂老虎机中的高效无换悔算法设计问题，其中动作数量 $N$ 随问题维度呈指数级增长。在此背景下，高效无换悔意味着后悔值在时间 $T$ 上为次线性、且在 $N$ 上为多项式对数级依赖。相较于外部后悔最小化（已有较好理解），组合多臂老虎机中实现该项目标长期未解。本文首次构造出一种无换悔学习算法，其后悔值在 $N$ 上为多项式对数级，且对组合多臂老虎机类问题具有理论紧致性。同时，我们展示了该算法在多种经典应用中的高效实现方式，每轮迭代复杂度亦为 $N$ 的多项式对数级。
原文摘要 · Abstract (English)
This paper addresses the problem of designing efficient no-swap regret algorithms for combinatorial bandits, where the number of actions $N$ is exponentially large in the dimensionality of the problem. In this setting, designing efficient no-swap regret translates to sublinear -- in horizon $T$ -- swap regret with polylogarithmic dependence on $N$. In contrast to the weaker notion of external regret minimization - a problem which is fairly well understood in the literature - achieving no-swap regret with a polylogarithmic dependence on $N$ has remained elusive in combinatorial bandits. Our paper resolves this challenge, by introducing a no-swap-regret learning algorithm with regret that scales polylogarithmically in $N$ and is tight for the class of combinatorial bandits. To ground our results, we also demonstrate how to implement the proposed algorithm efficiently -- that is, with a per-iteration complexity that also scales polylogarithmically in $N$ -- across a wide range of well-studied applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。