mlsanityData to 7 Oct 2026

Truly Adapting to Adversarial Constraints in Constrained MABs

arXiv 2602.14543 ↗First posted 16 Feb 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the constrained variant of the 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 unknown constraints, under both full and 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 (e.g., via competitive ratios with respect to the optimum). We provide the first algorithms that achieve optimal rates of regret and 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 full feedback we propose an algorithm attaining widetildeO(√T+C) regret and widetildeO(√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 bandit feedback is available for the constraints, we design an algorithm achieving widetildeO(√T+C) positive violation and widetildeO(√T+C√T) regret.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 32 of its 46 references that are in the map. First posted on arXiv 16 Feb 2026.

Builds on

32 of 46 references.

References · 32

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  2. 2020Exploration-Exploitation in Constrained MDPscited by 146
  3. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  4. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  5. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  6. 2017Online Convex Optimization with Stochastic Constraintscited by 94
  7. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  9. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  10. 2018Adversarial Bandits with Knapsackscited by 73
  11. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  12. 2020Stochastic Bandits with Linear Constraintscited by 68
20 more
  1. 2015Adaptive Algorithms for Online Convex Optimization with Long-term Constraintscited by 65
  2. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  3. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  4. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
  7. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  8. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  9. 2017Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Studycited by 14
  10. 2022Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Riskcited by 14
  11. 2022Safe Linear Bandits over Unknown Polytopescited by 13
  12. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  13. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  14. 2024Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraintscited by 10
  15. 2022Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithmcited by 6
  16. 2024No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimizationcited by 6
  17. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  18. 2023CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruptioncited by 2
  19. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2
  20. 2024Stochastic Bandits Robust to Adversarial Attackscited by 1

Built on by

Not cited yet.