Research map / Bandits and online learning / Online convex optimization and games
No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
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.
Shows that weakly adaptive primal and dual regret minimizers in a LagrangeBwK-style primal-dual framework keep dual multipliers bounded without knowing the Slater parameter, yielding best-of-both-worlds guarantees for bandits with general constraints and contextual bandits with linear constraints.
Problem
Bandits with general long-term constraints (generalizing bandits with knapsacks) where the Slater parameter is unknown and inputs may be stochastic or adversarial; standard no-regret primal-dual methods can fail to keep constraint violations sublinear.
Approach
A self-bounding lemma: when the primal algorithm is weakly adaptive and 2-scale-free and the dual algorithm is online gradient descent on R^m_{>=0} with a suitably small learning rate, the dual multipliers' l1 norm stays bounded by about 13m/rho without any projection or knowledge of rho, giving best-of-both-worlds guarantees.
Key results
- Self-bounding lemma: with OGD dual and 2-scale-free weakly adaptive primal, max dual l1-norm is at most 13m/rho with high probability, without knowing rho.
- Adversarial setting: reward at least rho/(1+rho) times the best unconstrained reward minus a sublinear term, with a matching lower bound showing 1+1/rho competitive ratio is optimal when violations are o(T).
- Stochastic setting: sublinear regret against the best randomized feasible-in-expectation strategy, with violations of order m^2 sqrt(T)/rho up to logs; the paper also gives CBwLC guarantees for adversarial contexts.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require weakly adaptive regret minimization for both primal and dual algorithms | Primal-dual framework for general constraints · General constraints, adversarial and stochastic | constraint violation: \(V_T=\widetilde O\left(\frac{m^2}{\rho}\overline{\RP}_{T,\delta}(\cX)\right)\) | Helped |
| Use standard no-regret algorithms rather than weakly adaptive algorithms | Primal-dual framework for general constraints · General constraints, adversarial example | constraint violation: \(\Omega(T)\) | Hurt |
| Use weakly adaptive primal and dual algorithms with OGD on the nonnegative orthant | Primal-dual framework for general constraints · General constraints, adversarial | reward guarantee: \(\Rew\ge \frac{\rhoadv}{1+\rhoadv}\optadv- \widetilde O\left(\left(\frac m\rhoadv\right)^2\overline{\RP}_{T,\delta}(\cX | Helped |
| Use weakly adaptive primal and dual algorithms with OGD on the nonnegative orthant | Primal-dual framework for general constraints · General constraints, stochastic | reward guarantee: \(\Rew\ge \optstoc-\widetilde O\left(\left(\frac{m}{\rhostoc}\right)^2\overline{\RP}_{T,\delta}(\cX)\right)\) | Helped |
| Use a weakly adaptive EXPSIX primal algorithm | Multi-armed bandits with constraints · Multi-armed bandits with constraints, adversarial | reward guarantee: \(\Rew\ge \frac\rhoadv{1+\rhoadv}\optadv -\tilde O\left(\frac{m^{2}}{\rhoadv^2} \sqrt {KT} \right)\) | Helped |
| Apply the weakly adaptive framework to regression-oracle contextual bandits | Contextual bandits with linear constraints · Adversarial contexts | reward guarantee: \(\Rew\ge \frac\rhoadv{1+\rhoadv}\optadv -\tilde O\left(\overline{\term{Err}}\frac{m^3}{\rhoadv^2}\sqrt{KT} \right)\) | Helped |
Surprising findings
- Standard no-regret primal and dual algorithms can have zero regret yet still incur linear constraint violations on a simple three-action instance.
- Weakly adaptive regret, not merely no-regret, is what is needed; the self-bounding property arises without any explicit projection of dual variables.
Limitations
- Guarantees hold only up to logarithmic factors and with high probability; violation bounds depend on the regret of the primal algorithm.
- Requires the primal algorithm to be 2-scale-free and weakly adaptive, which limits applicability.
- Contextual results rely on online regression oracles with bounded error and the adversarial competitive ratio is 1+1/rho rather than the optimal BwK ratio.
Experimental setup
Metrics: regret cumulative constraint violation competitive ratio
Baselines: LagrangeBwK primal-dual with projection onto [0,1/rho]
Builds on: LagrangeBwK EXP-SIX online gradient descent recovery technique for BwK
Closest papers by meaning
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.94)
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.92)
- High-dimensional Linear Bandits with Knapsacks (ICML 2024 · similarity 0.91)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.91)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · 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.