Research map / Bandits and online learning / Online convex optimization and games
Online Resource Allocation With General Constraints
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 dual gradient descent algorithm for online resource allocation with both budget and general long-term constraints, achieving best-of-both-worlds regret/alpha-regret bounds and bounded Lagrangian multipliers via weak adaptivity of OGD.
Problem
Online resource allocation where requests arrive sequentially and decisions must satisfy strict budget constraints plus general long-term constraints (e.g., ROI, fairness) whose feasibility margin (Slater's parameter) is unknown, in both stochastic and adversarial regimes.
Approach
Greedy primal action maximizing the instantaneous Lagrangian with OGD dual updates, with no void-action-based bound on multipliers; the multiplier norm is bounded using weak adaptivity of OGD over sub-intervals, which handles cross-constraint compensation when no point-wise feasible void action exists.</natural_language_placeholder>
Key results
- Stochastic regret of order O~(sqrt(T)) with strict budget satisfaction and O~(sqrt(T)) cumulative violation of general constraints, without knowing the Slater parameter.
- Adversarial alpha-regret of order O~(sqrt(T)) with alpha = rho/(1+rho).
- Lagrangian multiplier l1-norm bounded by 14M/rho with high probability via weak adaptivity.
Surprising findings
- Standard budget-only dual methods rely on the void action to bound multipliers; with general constraints, cross-constraint compensation can keep violations and multipliers growing, so the void-action argument fails.
Limitations
- Results are purely theoretical with no experiments reported in the provided text.
- Adversarial guarantee is alpha-regret rather than standard regret, with alpha depending on the unknown Slater parameter.
- Bounds carry M^2/rho factors and depend on the feasibility margin.
Experimental setup
Metrics: regret alpha-regret cumulative constraint violation
Builds on: bandits with knapsacks primal-dual weakly adaptive online learning online gradient descent
Closest papers by meaning
- Online Learning under Budget and ROI Constraints via Weak Adaptivity (ICML 2024 · similarity 0.90)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 2025 · similarity 0.89)
- Online Resource Allocation with Non-Stationary Customers (ICML 2024 · similarity 0.88)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.88)
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.88)
- Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback (AAAI 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.