Research map / Bandits and online learning / Online convex optimization and games
Online Learning under Budget and ROI Constraints via Weak Adaptivity
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-balancing primal-dual framework using weakly adaptive regret minimizers to handle budget and ROI constraints without knowing the Slater parameter or requiring a safe policy at every round, with best-of-both-worlds guarantees and applications to repeated first- and second-price auctions.
Problem
Online learning with hard budget and soft ROI constraints under stochastic or adversarial bandit feedback, where the Slater parameter is unknown and strictly feasible policies may not exist in every round (e.g., repeated ad auctions bidding).
Approach
Endow standard primal-dual templates with weakly adaptive (interval-regret) primal and dual regret minimizers; boundedness of Lagrange multipliers then emerges from their interaction, and a safe policy is only needed frequently enough rather than every round.
Key results
- Proves O~(sqrt(T)) regret and ROI violation in the stochastic setting without knowledge of the Slater parameter alpha.
- Proves an alpha/(alpha+1) constant-factor competitive ratio in the adversarial setting under budget B=Omega(T).
- Shows a safe policy needed only every k steps yields O~(T^{3/4}) regret when k=T^{1/4}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use weakly adaptive primal and dual regret minimizers instead of only standard sublinear-regret minimizers | Primal-dual online learning under budget and ROI constraints · Adversarial setting | cumulative ROI constraint violation: \Omega(T) under the standard regret requirements; sublinear under weak adaptivity | Helped |
| Use weakly adaptive primal and dual regret minimizers | Primal-dual online learning under budget and ROI constraints · Stochastic setting | cumulative regret: \tilde O(T^{1/2}) | Helped |
| Use weakly adaptive primal and dual regret minimizers | Primal-dual online learning under budget and ROI constraints · Adversarial setting | competitive ratio: \alpha/(\alpha+1) | Helped |
| Relax the safe-policy requirement from every round to intervals of length k=T^{1/4} | Dual-balancing primal-dual algorithm · Adversarial setting | regret: \tilde O(T^{3/4}) | Mixed |
Surprising findings
- Standard primal-dual algorithms with sublinear regret can still incur linear ROI constraint violation in a non-packing example (GFP auctions).
Limitations
- Requires budget Omega(T) for competitive-ratio guarantees in the adversarial setting.
- Analysis for bidding restricted to finite valuation and bid sets in first-price auctions.
- Requires a safe policy to exist at least every k steps for relaxed assumption, with worse T^{3/4} rate for large k.
Experimental setup
Metrics: cumulative regret cumulative ROI constraint violation budget satisfaction
Baselines: Standard primal-dual templates requiring known Slater parameter Concurrent work with O(T^{3/4}) guarantees under unknown alpha
Builds on: Bandits with Knapsacks EXP3-SIX Fixed Share primal-dual template for adversarial constrained online learning
Closest papers by meaning
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.90)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 2025 · similarity 0.89)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.88)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.88)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · 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.