Research map / Bandits and online learning / Online convex optimization and games
Online Resource Allocation with Non-Stationary Customers
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 the ULwE algorithm, which switches between an LP-based UCB policy (sublinear regret under near-IID arrivals) and a greedy adversarial policy (constant competitive ratio under non-stationary arrivals) for online resource allocation with unknown click-through rates.
Problem
Online resource allocation where customers arrive non-stationarily with known total arrival rates per type, unknown per-period arrival distributions, and unknown click-through rates that must be learned online.
Approach
Combines a UCB-based LP policy with an adversarial greedy (exponential inventory-discount) policy, switching between them via condition checks on regret and remaining capacity, so one algorithm attains sublinear regret under near-stationary arrivals and a constant competitive ratio under adversarial arrivals.
Key results
- Theory: ULwE gets expected regret O~(sqrt(n|Theta|T)) under near-i.i.d. arrivals and OPT <= (1+ constant) E[ALG] + O~(sqrt(n|Theta|T)) under general non-stationary arrivals, where the constant depends on min capacity.
- Simulation with T=500, 100 runs: ULwE tracks ALG_LP under IID arrivals and switches to ALG_ADV around T/3 under ADV1 arrivals.
- Under IID arrivals, ALG_ADV has the highest cumulative regret at T=500, while ALG_LP and ULwE perform similarly.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ALG_LP instead of ALG_ADV | Resource allocation algorithms · IID arrivals | cumulative regret | Helped |
| Use ULwE instead of ALG_ADV | Resource allocation algorithms · IID arrivals | cumulative regret | Helped |
| Use ALG_ADV instead of ALG_LP | Resource allocation algorithms · Adversarial arrivals (ADV1) | regret | Helped |
| Switch adaptively from ALG_LP to ALG_ADV | ULwE · Adversarial arrivals (ADV1) | regret | Helped |
| Use ULwE under high-nonstationarity ADV2 conditions | ULwE · General arrivals (ADV2) | regret | Mixed |
Surprising findings
- The reported ADV2 results show ULwE's performance dips under high nonstationarity, though the paper claims it still outperforms in stationary settings.
Limitations
- Experiments are small-scale simulations with only two customer types and two resources.
- Manuscript has many unfilled [ref] placeholders and inconsistent notation, making the theory hard to verify.
- The constant competitive ratio depends on the minimum resource capacity and degrades when capacities are small.
Experimental setup
Benchmarks: simulated resource allocation with T=500
Metrics: cumulative regret relative to J^D benchmark
Baselines: ALG_LP ALG_ADV optimal offline benchmark J^D
Builds on: contextual bandit with knapsacks Adwords problem primal-dual UCB Agrawal2016 BwK
Closest papers by meaning
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.88)
- Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback (AAAI 2025 · similarity 0.86)
- Maximizing the Success Probability of Policy Allocations in Online Systems (AAAI 2024 · similarity 0.85)
- Piecewise-Stationary Bandits with Knapsacks (NeurIPS 2024 · similarity 0.85)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 2025 · similarity 0.85)
- Dynamic Budget Throttling in Repeated Second-Price Auctions (AAAI 2024 · similarity 0.84)
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.