Research map / Bandits and online learning / Online convex optimization and games

Data-Dependent Regret Bounds for Constrained MABs

NeurIPS 2025 · Bandits and online learning › Online convex optimization and games · approach: Best-of-both-worlds bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives data-dependent (small-loss style) regret bounds for constrained multi-armed bandits with adversarial losses and stochastic constraints, including soft- and hard-constraint algorithms and a matching lower bound.

Problem

Regret bounds in constrained MABs with adversarial losses and stochastic constraint costs have been only worst-case O(sqrt(T)); data-dependent (small-loss) bounds are unexplored in the constrained setting, especially under hard constraints that must hold at every round w.h.p.

Approach

Combines OMD with log-barrier (increasing learning rates for small-loss bounds) with a confidence-based safe decision space, and for hard constraints mixes the OMD strategy with a known strictly feasible strategy via an adaptive combination factor, yielding a regret bound split into a safety complexity term and a bandit complexity term.

Key results

• Safe OMD with Log-Barrier (SafeOMD-LB) achieves, w.h.p., regret O~((K ln(1/δ)/ρ) sqrt(sum_t (ℓ_t^T(x^⋄−x*))^2) + (1/ρ) sqrt(K sum_t ℓ_t^T x* ln(1/δ))) while satisfying hard constraints at every round w.p. 1−δ.
• Constrained OMD with Log-Barrier (soft constraints) achieves small-loss regret O~(sqrt(K sum_t ℓ_t^T x*)) and cumulative violations V_T = O(sqrt(KT ln(TKm/δ))).
• A matching lower bound Ω((Δ/ρ)sqrt(T) + sqrt(ωT)) over constrained small-loss balls shows the two data-dependent terms are unavoidable up to logarithmic factors (and the 1/ρ dependence in the bandit term is left open).

Surprising findings

• The paper conjectures the 1/ρ dependence on the bandit-complexity term may be removable, placing it instead on the safety term.

Limitations

• Requires knowledge of a strictly feasible strategy and its margin rho, and the bound depends on 1/rho.
• Requires knowledge of the optimal cumulative loss sum_t ℓ_t^T x* to set the learning rate (doubling trick only sketched).
• Restricted to adversarial losses with stochastic constraints; the impossibility result rules out adversarial constraints.

Experimental setup

Metrics: expected regret bound cumulative positive constraint violation

Baselines: state-of-the-art O(sqrt(T)/rho) hard-constraint bandit algorithms

Builds on: OMD with log-barrier small-loss bounds for adversarial MABs constrained online learning with hard constraints

Closest papers by meaning

• Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.87)
• Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.87)
• Replicable Constrained Bandits (NeurIPS 2026 · similarity 0.87)
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.87)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs (NeurIPS 2025 · similarity 0.86)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.86)