arXiv:2508.18768stat.MLcs.LG2025-08被引 3

首个兼顾对抗与鲁棒性的上下文组合半强化学习算法,兼顾性能与效率。

Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits

  • 基于熵正则化FTRL框架,实现自适应策略更新
  • 在对抗和污染随机场景下分别达到√T和ln T的最优后悔界
  • 通过单变量求根加速投影,每轮计算速度显著提升

我们提出了首个针对上下文组合半强化学习问题的最佳-双世界算法,能在对抗性环境下实现$ ilde{ ext{O}}( oot{T}{})$的后悔率,在被污染的随机环境中实现$ ilde{ ext{O}}( ext{ln } T)$的后悔率。该方法基于带香农熵正则项的Follow-the-Regularized-Leader(FTRL)框架,具有良好的灵活性与高效实现潜力。为克服传统FTRL中高维投影步骤带来的计算瓶颈,我们利用Karush-Kuhn-Tucker(KKT)条件,将原本的K维凸投影问题转化为单变量求根问题,极大提升了每轮迭代的计算效率。实验表明,该方法不仅实现了最佳-双世界算法的理想后悔界,还带来了显著的每轮加速,适用于大规模实时应用场景。

原文摘要 · Abstract (English)

We introduce the first best-of-both-worlds algorithm for contextual combinatorial semi-bandits that simultaneously guarantees $\widetilde{\mathcal{O}}(\sqrt{T})$ regret in the adversarial regime and $\widetilde{\mathcal{O}}(\ln T)$ regret in the corrupted stochastic regime. Our approach builds on the Follow-the-Regularized-Leader (FTRL) framework equipped with a Shannon entropy regularizer, yielding a flexible method that admits efficient implementations. Beyond regret bounds, we tackle the practical bottleneck in FTRL (or, equivalently, Online Stochastic Mirror Descent) arising from the high-dimensional projection step encountered in each round of interaction. By leveraging the Karush-Kuhn-Tucker conditions, we transform the $K$-dimensional convex projection problem into a single-variable root-finding problem, dramatically accelerating each round. Empirical evaluations demonstrate that this combined strategy not only attains the attractive regret bounds of best-of-both-worlds algorithms but also delivers substantial per-round speed-ups, making it well-suited for large-scale, real-time applications.

强化学习上下文学习优化算法在线学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。