Research map / Bandits and online learning / Online convex optimization and games
Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints
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.
Proposes a best-of-both-worlds bandit-with-constraints algorithm that combines a no-regret learner on moving feasible sets with UCB-style optimistic constraint estimates built from adaptively weighted means, avoiding primal-dual methods and Slater's condition in the stochastic case.
Problem
Bandits with arbitrary long-term constraints (generalizing bandits with knapsacks) where constraints and rewards may be stochastic or adversarial; prior best-of-both-worlds methods rely on primal-dual approaches needing Slater's condition and scale polynomially in the number of constraints.
Approach
Estimate the feasible set optimistically via adaptively weighted means of past constraint costs (learning rate interpolating between empirical mean and exponential averaging, driven by current violation), and run an EXP-IX-style mirror descent over the moving estimated feasible sets, avoiding primal-dual updates.
Key results
- In the stochastic setting, the algorithm achieves regret R_T <= 4sqrt(KT log(2K/eps)) and violations V_t <= 53sqrt(Kt log(28mKT^2/eps)) with high probability, without Slater's condition.
- In the adversarial setting, it achieves alpha-regret with alpha = rho/(1+rho) and violations of order sqrt(KT log m), logarithmic in the number of constraints m.
- Positive violations in the stochastic setting are bounded by 16sqrt(Kt log(28mKT^2/eps)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a constant learning rate η_t^{(i)}(a_t)=\nicefrac{1}{\sqrt{T}} with an exponentially weighted estimator (ablation) | Proposed algorithm · Stochastic constraints | violation: \tilde O(T^{3/4}) | Hurt |
| use η_t^{(i)}(a_t)=\nicefrac{1}{n_t(a_t)} and the empirical mean estimator (ablation) | Proposed algorithm · Stochastic constraints | estimation concentration: |\hat g_t^{(i)}(a)-\bar g^{(i)}(a)|=\widetilde O\left({n_t(a)^{-1/2}}\right) | Helped |
| use η_t^{(i)}(a_t)=\nicefrac{1}{n_t(a_t)} and the empirical mean estimator (ablation) | Proposed algorithm · Adversarial constraints | violation: linear in T | Hurt |
| use adaptive learning rates that increase with the current constraint violation | Proposed algorithm · Stochastic constraints | maximum violation: V_t\le 53\sqrt{Kt\log(2/\delta_2)} | Helped |
| use adaptive learning rates that increase with the current constraint violation | Proposed algorithm · Adversarial constraints | maximum violation: V_t\le 53\sqrt{Kt\log(2/\delta_2)} | Helped |
Surprising findings
- UCB-style optimistic constraint estimation achieves optimal performance in both stochastic and adversarial constraint settings, contrary to the primal-dual intuition.
Limitations
- Adversarial guarantees are only for a constant competitive ratio alpha = rho/(1+rho) depending on the Slater parameter rho, not full regret.
- Results rely on high-probability events and union bounds yielding log(T) and K-dependent terms; no empirical experiments are reported.
Experimental setup
Metrics: regret cumulative constraint violation alpha-regret (competitive ratio)
Baselines: primal-dual best-of-both-worlds methods for bandits with constraints Lagrangian BwK framework
Builds on: EXP-IX bandits with knapsacks (UCB-based) Lagrangian BwK framework online gradient descent on quadratic losses
Closest papers by meaning
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.94)
- Smoothed Adversarial Linear Contextual Bandits with Knapsacks (ICML 2022 · similarity 0.92)
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.91)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.90)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.