mlsanityData to 14 Oct 2026

Data-Dependent Regret Bounds for Constrained MABs

arXiv 2505.20010 ↗First posted 26 May 2025cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

This paper initiates the study of data-dependent regret bounds in constrained MAB settings. These bounds depend on the sequence of losses that characterize the problem instance. Thus, they can be much smaller than classical widetildeO(√T) regret bounds, while being equivalent to them in the worst case. Despite this, data-dependent regret bounds have been completely overlooked in constrained MAB settings. The goal of this paper is to answer the following question: Can data-dependent regret bounds be derived in the presence of constraints? We answer this question affirmatively in constrained MABs with adversarial losses and stochastic constraints. Specifically, our main focus is on the most challenging and natural settings with hard constraints, where the learner must ensure that the constraints are always satisfied with high probability. We design an algorithm with a regret bound consisting of two data-dependent terms. The first term captures the difficulty of satisfying the constraints, while the second one encodes the complexity of learning independently of the presence of constraints. We also prove a lower bound showing that these two terms are not artifacts of our specific approach and analysis, but rather the fundamental components that inherently characterize the complexities of the problem. Finally, in designing our algorithm, we also derive some novel results in the related (and easier) soft constraints settings, which may be of independent interest.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 27 of its 39 references that are in the map. First posted on arXiv 26 May 2025.

Builds on

27 of 39 references.

References · 27

  1. 2020Exploration-Exploitation in Constrained MDPscited by 149
  2. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  3. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  4. 2016Corralling a Band of Bandit Algorithmscited by 100
  5. 2017Online Convex Optimization with Stochastic Constraintscited by 95
  6. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  7. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  8. 2020Stochastic Bandits with Linear Constraintscited by 68
  9. 2015Adaptive Algorithms for Online Convex Optimization with Long-term Constraintscited by 65
  10. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  11. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  12. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
15 more
  1. 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
  2. 2015First-order regret bounds for combinatorial semi-banditscited by 26
  3. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  4. 2020A Closer Look at Small-loss Bounds for Bandits with Graph Feedbackcited by 21
  5. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  6. 2016Refined Lower Bounds for Adversarial Banditscited by 20
  7. 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
  8. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 16
  9. 2022Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Riskcited by 15
  10. 2017Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Studycited by 14
  11. 2022Safe Linear Bandits over Unknown Polytopescited by 14
  12. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 12
  13. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  14. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
  15. 2024Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedbackcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Replicable Constrained Banditscited by 2
  2. 2026Truly Adapting to Adversarial Constraints in Constrained MABscited by 0