Research map / Bandits and online learning / Online convex optimization and games
Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback
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 non-stochastic budgeted online procurement pricing with semi-bandit feedback, proposing the GAP policy (and Doubling-GAP for unknown budgets) with matching-up-to-log regret bounds and a lower bound.
Problem
A budget-limited buyer must offer prices to multiple sellers over time when sellers' costs and values change arbitrarily (non-stochastic), observing only accept/reject decisions and values on acceptance; the goal is to maximize procured value under the budget with low alpha-regret.
Approach
Discretize the continuous price space, exploit the monotonicity of seller acceptance to form a feedback graph with side observations, and run an Exp3-style exponential-weights learner over prices (GAP); the budget-unknown variant restarts GAP in doubling phases.
Key results
- GAP's total reward is 55.59%, 59.89% and 26.32% larger than BP-UCB, TSampling and KUBE on average, and 14.16% larger than Exp3 across budgets.
- GAP achieves alpha-regret upper bound O(n (vmax/cmin) sqrt(B/cmin) ln B); Doubling-GAP achieves O(... ln^2 B) for unknown budget.
- A lower bound Omega(vmax sqrt(Bn/cmin)) holds for any online policy, tight up to sub-linear/log terms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GAP instead of BP-UCB | Online pricing · Simulation, varying budget | total reward: 55.59% larger on average | Helped |
| Use GAP instead of TSampling | Online pricing · Simulation, varying budget | total reward: 59.89% larger on average | Helped |
| Use GAP instead of KUBE | Online pricing · Simulation, varying budget | total reward: 26.32% larger on average | Helped |
| Use GAP instead of Exp3 | Online pricing · Simulation, varying budget | total reward: 14.16% larger on average | Helped |
| Use GAP instead of BP-UCB | Online pricing · Simulation, varying number of sellers | total reward: 48.69% larger on average | Helped |
| Use GAP instead of TSampling | Online pricing · Simulation, varying number of sellers | total reward: 62.22% larger on average | Helped |
| Use GAP instead of KUBE | Online pricing · Simulation, varying number of sellers | total reward: 47.45% larger on average | Helped |
| Use GAP instead of Exp3 | Online pricing · Simulation, varying number of sellers | total reward: 12.31% larger on average | Helped |
| Use feedback-graph side information for price learning | GAP versus Exp3 · Simulation, varying budget | total reward: 14.16% larger on average | Helped |
Limitations
- Regret bounds hold only up to log factors and are approximate relative to the alpha-optimal benchmark (alpha = vmin/((2-cmin)vmax)).
- Experiments are simulation-only with a single adversary model; no real-world data.
- Assumes known cmin, vmin, vmax and discretization of the price space.
Experimental setup
Benchmarks: simulated non-stochastic pricing environment
Metrics: total reward alpha-regret
Baselines: Exp3 BP-UCB KUBE Thompson Sampling
Builds on: Exp3 feedback graph bandits (Alon et al.) KUBE BP-UCB
Closest papers by meaning
- Online Second Price Auction with Semi-Bandit Feedback under the Non-Stationary Setting (AAAI 2020 · similarity 0.89)
- No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.88)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.88)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.87)
- Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits (NeurIPS 2024 · similarity 0.87)
- Dynamic Budget Throttling in Repeated Second-Price Auctions (AAAI 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.