Research map / Bandits and online learning / Online convex optimization and games
Bandits with Replenishable Knapsacks: the Best of both Worlds
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 primal-dual template for bandits with replenishable knapsacks (non-monotonic resource consumption), giving constant competitive ratio under adversarial inputs and O~(sqrt T) instance-independent regret under stochastic inputs.
Problem
Online learning with long-term resource constraints where resources can be replenished (negative consumption), which breaks the monotonic assumption of standard bandits with knapsacks; prior work gave only instance-dependent stochastic bounds and no adversarial positive results.
Approach
A primal-dual template that runs a bandit-feedback primal regret minimizer and a weakly-adaptive full-feedback dual regret minimizer (generalized fixed share or OGD), playing a void action when any budget falls below 1; the analysis splits rounds before and after the last budget-depletion time to handle replenishment, yielding a competitive ratio nu/(1+beta) in adversarial settings and sqrt(T) reg
Key results
- Adversarial setting: constant competitive ratio alpha = nu/(1+beta) when B=Omega(T) or replenishment is a positive constant, with regret term m^4/nu^2 (primal + dual terms) sublinear in T.
- Stochastic setting: instance-independent O~(m^4/nu^2 sqrt(KT)) regret for BwRK with probability 1-2delta, the first such bound for i.i.d. inputs.
- With beta=0 the framework recovers the 1/rho competitive ratio of prior monotonic BwK work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the primal-dual template with EXP3-SIX and OGD to adversarial BwRK | BwRK · BwRK adversarial | regret: \tilde \cO\left(\frac{m^4}{\nu^2}\sqrt{KT} \log\mleft(\frac{1}{\delta}\mright)\right) | Helped |
| Apply the primal-dual template with EXP3-SIX and OGD to stochastic BwRK | BwRK · BwRK stochastic | regret: \tilde \cO\left(\frac{m^4}{\nu^2}\sqrt{KT} \log\mleft(\frac{1}{\delta}\mright)\right) | Helped |
| Use the primal-dual template with EXP-SIX | Inventory management · Inventory management, stochastic | regret: \tilde {\cO}(\sqrt{T}) | Helped |
| Use the primal-dual template for bilateral trade | Bilateral trade · Bilateral trade, stochastic | regret: \tilde\cO({\sqrt{T}}) | Helped |
Surprising findings
- Adversarial results are not invariant to translating rewards, so the simple rescaling trick used in the stochastic case does not extend to adversarial inputs with negative rewards.
Limitations
- Adversarial case with negative rewards remains open; translation/rescaling trick fails for the multiplicative competitive ratio.
- Stochastic bound is instance-independent and does not give logarithmic instance-dependent rates.
- Requires a void action with non-negative reward and negative cost (beta-replenishment assumption) for adversarial guarantees.
Experimental setup
Metrics: competitive ratio regret
Baselines: EXP3-SIX bandits with replenishable knapsacks instance-dependent algorithm
Builds on: bandits with knapsacks EXP3-SIX fixed share bandits with replenishable knapsacks
Closest papers by meaning
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.92)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.91)
- Contextual Decision-Making with Knapsacks Beyond the Worst Case (NeurIPS 2024 · similarity 0.89)
- High-dimensional Linear Bandits with Knapsacks (ICML 2024 · similarity 0.89)
- Piecewise-Stationary Bandits with Knapsacks (NeurIPS 2024 · similarity 0.89)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 2025 · similarity 0.88)
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.