在非平稳环境中,同时优化损失与约束违规,实现自适应最优性能。
Truly Adapting to Adversarial Constraints in Constrained MABs
- 设计算法动态适应未知约束的非平稳性,兼顾损失与违规控制。
- 在全反馈下,达到近似√T + C的后悔与正违规率,其中C为约束非平稳度。
- 适用于需鲁棒决策的实时系统,如在线广告、资源分配等场景。
我们研究多臂老虎机(MAB)问题的约束变体,在该问题中,学习者不仅需最小化学习过程中的总损失,还需控制多个未知约束的违反。考虑一个涵盖随机与对抗模型的非平稳环境,每轮损失和约束均从可能任意变化的分布中抽取。在此设定下,无法同时保证次线性后悔与次线性违规。先前工作主要聚焦于随机约束或通过竞争比等松弛基准来处理完全对抗性约束。本文提出首个算法,在约束为随机而损失可任意变化时,实现最优后悔与正违规率;同时,当约束具有对抗性时,保证性能随其对抗程度平滑退化。在全反馈下,算法实现$ ilde{ m O}( oot{T}+C)$后悔与$ ilde{ m O}( oot{T}+C)$正违规,其中$C$衡量约束非平稳性。进一步推广至仅损失有带反馈的情况,并在约束也仅具带反馈时,设计出$ ilde{ m O}( oot{T}+C)$正违规与$ ilde{ m O}( oot{T}+C oot{T})$后悔的算法。
原文摘要 · Abstract (English)
We study the constrained variant of the \emph{multi-armed bandit} (MAB) problem, in which the learner aims not only at minimizing the total loss incurred during the learning dynamic, but also at controlling the violation of multiple \emph{unknown} constraints, under both \emph{full} and \emph{bandit feedback}. We consider a non-stationary environment that subsumes both stochastic and adversarial models and where, at each round, both losses and constraints are drawn from distributions that may change arbitrarily over time. In such a setting, it is provably not possible to guarantee both sublinear regret and sublinear violation. Accordingly, prior work has mainly focused either on settings with stochastic constraints or on relaxing the benchmark with fully adversarial constraints (\emph{e.g.}, via competitive ratios with respect to the optimum). We provide the first algorithms that achieve optimal rates of regret and \emph{positive} constraint violation when the constraints are stochastic while the losses may vary arbitrarily, and that simultaneously yield guarantees that degrade smoothly with the degree of adversariality of the constraints. Specifically, under \emph{full feedback} we propose an algorithm attaining $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ regret and $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ {positive} violation, where $C$ quantifies the amount of non-stationarity in the constraints. We then show how to extend these guarantees when only bandit feedback is available for the losses. Finally, when \emph{bandit feedback} is available for the constraints, we design an algorithm achieving $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ {positive} violation and $\widetilde{\mathcal{O}}(\sqrt{T}+C\sqrt{T})$ regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。