Research map / Bandits and online learning / Multi-armed bandits
Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits
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.
Frames ex-ante selection of how many coalition bidders to send to repeated second-price auctions as a structured N-armed bandit and proposes Local-Greedy and Greedy-Grid algorithms with constant problem-dependent regret via a power-of-CDF reward estimator.
Problem
Ex-ante choice of how many agents from a coalition to enter repeated second-price auctions against p competitors, under privacy constraints that reveal only winning-bid feedback, so the reward must be learned from limited observations.
Approach
Expresses the expected reward as n times an integral of F^{p+n-1} minus F^{p+n}, estimates r(n) from samples collected by any nearby arm k via empirical CDF powers, and exploits unimodality with a greedy play inside estimation neighborhoods (LG) or successive elimination on a logarithmic grid (GG).
Key results
- Local-Greedy and Greedy-Grid achieve regret independent of T, with GG giving a problem-independent bound of order sqrt((K+|B*|)T) where K=floor(log_{3/2}N).
- Local-Greedy has the lowest expected regret among LG, GG, UCB, EXP3 and OSUB in synthetic experiments (Appendix D).
- The reward estimator's concentration avoids a linear-in-n first-order term, giving gap-dependent terms of order N-bar(1/Delta_n) instead of N^2/Delta_n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Local-Greedy instead of the tested competing algorithms | Synthetic auction benchmark · Synthetic data | expected regret | Helped |
| use Local-Greedy instead of Greedy-Grid | Online auction bandit algorithms · Synthetic data | expected regret | Helped |
| use Local-Greedy instead of OSUB and multi-armed bandit algorithms | Online auction bandit algorithms · Synthetic data | expected regret | Helped |
| use Greedy-Grid rather than a standard UCB approach | Online auction bandit problem · Regret guarantee | regret upper bound | Helped |
| use Local-Greedy rather than a standard UCB approach | Online auction bandit problem · Regret guarantee | regret upper bound | Helped |
Surprising findings
- Local-Greedy, which uses no confidence intervals, empirically outperforms the theoretically stronger Greedy-Grid and standard unimodal bandit baselines.
- The reward function is not always unimodal; a discrete counterexample is given, so the unimodality assumption can fail.
Limitations
- Unimodality of the reward is assumed (Assumption 2) and not guaranteed for all distributions; LG relies heavily on it.
- Regret bounds for LG are conservative and depend on the worst local gap; GG may be conservative in practice.
- Analysis assumes a single auction per round and symmetric i.i.d. bidders with a known number of competitors p.
Experimental setup
Benchmarks: synthetic auction bandit simulations
Metrics: expected cumulative regret
Baselines: UCB1 EXP3 OSUB Local-Greedy Greedy-Grid
Builds on: OSUB UCB1 EXP3 Successive Elimination
Closest papers by meaning
- No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.88)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.87)
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.87)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.87)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.87)
- Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback (AAAI 2025 · 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.