Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Decision-Making with Knapsacks Beyond the Worst Case
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 an unavoidable Omega(sqrt T) gap between the fluid and online optima for degenerate LPs, and that re-solving with distribution estimation achieves O(1) regret (full info) / O(log T) (partial info) under a unique non-degenerate fluid LP, plus near-optimal O(sqrt T log T)-type worst-case bounds for contextual decision-making with knapsacks.
Problem
Contextual decision-making with knapsacks (CDMK): online resource-constrained decisions where the reward and consumption depend on an unobserved external factor; prior work only gives O(sqrt T) worst-case regret and the fluid benchmark's tightness is unclear.
Approach
Applies the re-solving (certainty equivalence) heuristic with empirical distribution estimation to CDMK, showing that under a unique non-degenerate fluid LP the regret is O(1) with full information and O(log T) with partial information, while a degenerate fluid LP forces an Omega(sqrt T) gap to the online optimum.
Key results
- Degenerate fluid LP: an Omega(sqrt T) gap between fluid and online optimum is unavoidable.
- Unique non-degenerate fluid LP: re-solving achieves O(1) regret with full information and O(log T) with partial information.
- Worst case: O(sqrt(T log T)) regret with full information and O(sqrt T log T) with partial information.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use full information feedback instead of partial information feedback | Re-solving with Empirical Estimation on a discrete CDMK with a unique non-degenerate fluid LP · Discrete CDMK, unique non-degenerate fluid LP | regret to fluid benchmark: O((n^2 + k + \log T)/D^2) -> O((n^2 + k)/D^2) | Helped |
| Use partial information feedback instead of full information feedback | Re-solving with Empirical Estimation on a discrete CDMK in the worst case · Discrete CDMK, worst case | regret to fluid benchmark: O(k\sqrt{T \log T} + n) -> O(k\sqrt{T}\log T + n) | Hurt |
| Require the fluid LP to have a unique and non-degenerate optimal solution | Re-solving with Empirical Estimation under full information feedback · Discrete CDMK, regular instances | regret to fluid benchmark: O(k\sqrt{T \log T} + n) -> O((n^2 + k)/D^2) | Helped |
| Require the fluid LP to have a unique and non-degenerate optimal solution | Re-solving with Empirical Estimation under partial information feedback · Discrete CDMK, regular instances | regret to fluid benchmark: O(k\sqrt{T}\log T + n) -> O((n^2 + k + \log T)/D^2) | Helped |
| Have a unique and degenerate optimal solution to the fluid LP | Fluid benchmark versus online optimum · CDMK, unique and degenerate fluid LP | gap between fluid optimum and online optimum: \Omega(\sqrt{T}) | Hurt |
Surprising findings
- Under degenerate fluid LP, the fluid benchmark can be Omega(sqrt T) away from the online optimum, so fluid-benchmark regret can mislead.
Limitations
- Results for finite request/external-factor sets rely on a unique non-degenerate fluid LP assumption.
- Dependence on the unknown external-factor set size is omitted from bounds.
- Continuous case requires an oracle for a possibly non-convex re-solving problem.
Experimental setup
Benchmarks: synthetic CDMK instance (degenerate vs non-degenerate LP)
Metrics: regret regret scaling with T
Baselines: contextual bandits with knapsacks primal/dual algorithms (O(sqrt T) regret)
Builds on: re-solving heuristic bandits with knapsacks network revenue management
Closest papers by meaning
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.90)
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.89)
- Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions (NeurIPS 2026 · similarity 0.88)
- High-dimensional Linear Bandits with Knapsacks (ICML 2024 · similarity 0.88)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.87)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
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.