Research map / Bandits and online learning / Online convex optimization and games
Piecewise-Stationary Bandits with Knapsacks
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 inventory-reserving algorithms (IRES, IRES-CM) for bandits with knapsacks in piecewise-stationary environments, achieving an O(log(ηmax/ηmin)) competitive ratio against a dynamic best-distribution fluid benchmark without bounded global variation.
Problem
Bandits with knapsacks under piecewise-stationary (non-stationary) outcomes with bandit feedback, where global variation may be linear in T, so existing non-stationary Bwk results do not apply.
Approach
Reserve budget across intervals of reward-consumption ratio and use round-robin guessing of each stationary piece's ratio interval; for bandit feedback, add exploration with change monitoring that resets estimates of reward and consumption, so the performance guarantee holds against a dynamic best-distribution benchmark.
Key results
- IRES-CM achieves an O(log(ηmax/ηmin)) competitive ratio against the fluid benchmark FA, with a matching lower bound Ω(log(ηmax/ηmin)) (Theorem 4.5).
- In simulations, IRES-CM outperforms Immorlica et al. (2019) in both instance settings.
- Zhou et al. (2008) beats IRES-CM only when the optimal benchmark uses a single arm per piece; it underperforms when mixed arms are optimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IRES-CM instead of Immorlica et al. (2019)'s algorithm | Piecewise-stationary BwK · Numerical experiments, both single-arm and mixed-arm FA optima | cumulative reward | Helped |
| Use IRES-CM instead of Zhou et al. (2008)'s algorithm | Piecewise-stationary BwK · Numerical experiments, mixed-arm FA optimum | cumulative reward | Helped |
| Use IRES-CM instead of Zhou et al. (2008)'s algorithm | Piecewise-stationary BwK · Numerical experiments, single-arm FA optimum | cumulative reward | Hurt |
Surprising findings
- Assuming bounded global variation is not needed, but without it sublinear-in-T regret is impossible, so the guarantee is a competitive ratio rather than regret.
Limitations
- Requires known bounds ηmin, ηmax and the number of change points L must be small (o(sqrt(T)ηmin) if unknown).
- Requires budget B and optimum to be large enough (Assumption 4.1) for the bandit-feedback guarantee.
- Competitive ratio only, with regret bounds dependent on exploration and change-point losses; experiments are limited to a small single-resource instance.
Experimental setup
Benchmarks: simulated two-piece single-resource Bwk instances
Metrics: cumulative reward relative to LP benchmark FA
Baselines: Immorlica et al. (2019) algorithm Zhou et al. (2008) algorithm
Builds on: Immorlica et al. (2019) Zhou et al. (2008) Liu et al. (2022) Kesselheim and Singla (2020)
Closest papers by meaning
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.89)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.88)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.87)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
- High-dimensional Linear Bandits with Knapsacks (ICML 2024 · similarity 0.86)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.86)
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.