arXiv:2506.02980stat.MLcs.LG2025-06NeurIPS被引 3

在非平稳环境中优化凸损失,提出新算法实现最优后悔界。

Non-stationary Bandit Convex Optimization: A Comprehensive Study

  • 设计新算法TEWA-SE,基于睡眠专家框架适应非平稳环境。
  • 对强凸损失,实现关于切换次数与总变差的最优后悔上界。
  • 适用于已知或未知非平稳性的场景,理论性能领先现有方法。

Bandit Convex Optimization 是一类基础的序列决策问题:学习者从连续动作空间中选择动作,每轮仅观测一个点的损失值(不包含梯度)。本文研究非平稳环境下的该问题,旨在最小化三种标准非平稳性度量下的后悔:比较序列的切换次数 $S$、损失函数的总变差 $Δ$,以及比较序列的路径长度 $P$。提出一种多项式时间算法 Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE),将在线凸优化中的睡眠专家框架扩展至带器设置。对于强凸损失,证明了 TEWA-SE 在已知 $S$ 与 $Δ$ 时达到极小极大最优后悔率,通过建立匹配的上下界实现。通过引入 Bandit-over-Bandit 框架,进一步拓展至非平稳性度量未知的情形。对于一般凸损失,提出第二算法 clipped Exploration by Optimization (cExO),基于离散动作空间上的指数权重。虽非多项式时间可计算,但实现了关于已知 $S$ 与 $Δ$ 的极小极大最优后悔率,并在 $P$ 度量下优于现有最佳界限。

原文摘要 · Abstract (English)

Bandit Convex Optimization is a fundamental class of sequential decision-making problems, where the learner selects actions from a continuous domain and observes a loss (but not its gradient) at only one point per round. We study this problem in non-stationary environments, and aim to minimize the regret under three standard measures of non-stationarity: the number of switches $S$ in the comparator sequence, the total variation $Δ$ of the loss functions, and the path-length $P$ of the comparator sequence. We propose a polynomial-time algorithm, Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE), which adapts the sleeping experts framework from online convex optimization to the bandit setting. For strongly convex losses, we prove that TEWA-SE is minimax-optimal with respect to known $S$ and $Δ$ by establishing matching upper and lower bounds. By equipping TEWA-SE with the Bandit-over-Bandit framework, we extend our analysis to environments with unknown non-stationarity measures. For general convex losses, we introduce a second algorithm, clipped Exploration by Optimization (cExO), based on exponential weights over a discretized action space. While not polynomial-time computable, this method achieves minimax-optimal regret with respect to known $S$ and $Δ$, and improves on the best existing bounds with respect to $P$.

在线优化带器学习凸优化后悔界

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