Research map / Bandits and online learning / Online convex optimization and games
Improved learning rates in multi-unit uniform price auctions
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 new bid-space representation (pseudo-bids and bid-gaps) for repeated K-unit uniform price auctions that decomposes utility into independent sub-utilities, improving bandit regret to K^{4/3}T^{2/3} and introducing all-winner feedback with K^{5/2}sqrt(T) regret.
Problem
Online bidding in repeated multi-unit uniform price auctions against an adversarial opposing bid, motivated by electricity day-ahead and reserve markets; prior bandit regret bounds were O(K^{7/4}T^{3/4}).
Approach
Replace the exponential bid space with an equivalent pseudo-bid space built from binary bid and bid-gap indicators, so utility decomposes into a sum of sub-utilities each depending on a single component; combine EXP3-style exponential weights with a weight-pushing sampler over a DAG, and add an all-winner feedback model revealing all winning bids.
Key results
- Bandit feedback regret of O~(K^{4/3}T^{2/3}), improving the previous O~(K^{7/4}T^{3/4}) and matching Omega(T^{2/3}) lower bound up to logs.
- All-winner feedback achieves O~(K^{5/2}sqrt(T)) regret.
- Full-information regret of O(sqrt(K^3 T log T)) recovered with the new action space.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the prior DAG action-space representation with bid-gap pseudo-bids and decompose utility into sub-utilities | Online learning in K-unit uniform-price auctions · Repeated K-unit uniform-price auction, bandit feedback | regret upper bound: \mathcal{\tilde{O}}(K^{7/4}T^{3/4}) -> \mathcal{\tilde{O}}(K^{4/3}T^{2/3}) | Helped |
| Use all-winner feedback instead of bandit feedback | Proposed algorithm · Repeated K-unit uniform-price auction | regret upper bound: \mathcal{O} \left ( K^{4/3} T^{2/3} \log \left (T \right ) \right ) -> \mathcal{O} \left ( K^{5/2} \sqrt{T} \log (T) \ri | Helped |
| Use the proposed action-space representation with Hedge in full-information feedback | Online learning in K-unit uniform-price auctions · Repeated K-unit uniform-price auction, full-information feedback | regret upper bound: \mathcal{\tilde{O}}(K^{3/2}\sqrt{T}) -> O \left ( \sqrt{K^3T\log \left (T \right )} \right ) | No clear effect |
Surprising findings
- Uniform pricing under bandit feedback is not strictly harder than discriminatory pricing: the same T^{2/3} rate is achievable.
Limitations
- Results are regret bounds only; no empirical experiments are reported.
- Analysis assumes the adversary's bids avoid the discretization grid (ties avoided via perturbation).
Experimental setup
Metrics: regret
Baselines: DAG-based uniform price bandit algorithm (K^{7/4}T^{3/4}) full-information Hedge on discretized bid space
Builds on: EXP3 DAG-based action space for multi-unit uniform auctions bandits with graph feedback
Closest papers by meaning
- Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization (NeurIPS 2025 · similarity 0.93)
- Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions (NeurIPS 2017 · similarity 0.91)
- Learning and Collusion in Multi-unit Auctions (NeurIPS 2023 · similarity 0.89)
- Learning Optimal Reserve Price against Non-myopic Bidders (NeurIPS 2018 · similarity 0.89)
- Reserve Pricing in Repeated Second-Price Auctions with Strategic Bidders (ICML 2020 · similarity 0.88)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 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.