Research map / Bandits and online learning / Online convex optimization and games
No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!
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.
Studies online resource allocation and online learning with resource constraints under adversarially changing reward/cost distributions, using a spending plan as the benchmark-defining guide, and gives primal-dual no-regret methods with a robust variant for small per-round budgets.
Problem
Online decision making under resource (budget) constraints when reward and cost distributions change adversarially; without a spending plan, sublinear regret is impossible, so regret is measured against baselines that follow a given per-round spending plan.
Approach
Uses a spending plan (per-round expected budget) as the reference for both dynamic and fixed baselines; a black-box primal-dual scheme with dual online mirror descent (and a primal regret minimizer for OLRC) achieves regret scaling with 1/rho_min, plus a meta-procedure that caps rho_min at rho/T^{1/4} and rescales the plan to get T^{3/4} regret.
Key results
- Dual algorithm for online resource allocation attains dynamic regret O~(sqrt(T)/rho_min) against the spending-plan dynamic optimum.
- Primal-dual OLRC method attains static regret O~(sqrt(T)/rho_min) under full feedback, extended to bandit feedback with high probability.
- Meta-procedure with rho_hat = rho/T^{1/4} gives O~(T^{3/4}) dynamic and static regret when rho_min is arbitrarily small.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Provide a spending plan with a well-balanced per-round budget (larger \rho_{\min}) | ORA and OLRC primal-dual methods · Online decision making with resource constraints | regret bound: \widetilde{O}(\frac{1}{\rho_{\min}}\sqrt{T}) | Helped |
| Use the spending plan to guide decisions and constrain the comparator to follow it | ORA and OLRC · Adversarially changing reward and cost distributions | regret: sublinear regret | Helped |
| Cap the minimum per-round budget and rescale the spending plan | Dual Algorithm for ORA · ORA with arbitrarily small \rho_{\min} | dynamic regret: \widetilde{O}(T^{3/4}) | Helped |
| Use a bandit-feedback primal regret minimizer instead of a full-feedback one | Primal-Dual Algorithm for OLRC · OLRC with bandit feedback | static regret: almost identical results | No clear effect |
| Allow the baseline to deviate from the spending plan by per-round errors | Dual Algorithm for ORA · ORA with spending-plan deviation | dynamic regret: \frac{1}{\rho_{\min}}\sum_{t=1}^{T}\sum_{i\in[m]}\epsilon^{(i)}_t | Hurt |
Limitations
- Regret bounds scale linearly with 1/rho_min, which is vacuous when the spending plan has tiny per-round budgets.
- Impossibility of sublinear dynamic regret in OLRC means only static regret is attainable there.
- Bandit-feedback results hold only with high probability and depend on the primal regret minimizer's confidence.
Experimental setup
Metrics: dynamic regret static regret
Baselines: dynamic optimum OPT_D fixed optimum OPT_H adversarial bandits with knapsacks primal-dual methods
Builds on: bandits with knapsacks EXP3.IX online mirror descent
Closest papers by meaning
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.90)
- Online Learning under Budget and ROI Constraints via Weak Adaptivity (ICML 2024 · similarity 0.89)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.89)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.89)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (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.