Research map / Bandits and online learning / Online convex optimization and games
Best-of-both-worlds bandit algorithms
Obtain optimal regret in both stochastic and adversarial regimes for linear and semi-bandits.
125 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Online convex optimization and games, keyword cluster “price · pricing · auctions”
State History Tried Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
27 papers in 2023–24 and 40 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 11.8% to 14.5%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Regret of Queueing Bandits (NeurIPS 2016 · 15 citations)
- 2017 · The Price of Differential Privacy for Online Learning (ICML 2017 · 46 citations)
- 2018 · Information Directed Sampling for Stochastic Bandits With Graph Feedback (AAAI 2018 · 19 citations)
- 2019 · Weighted Linear Bandits for Non-Stationary Environments (NeurIPS 2019 · 52 citations)
- 2020 · Learning Strategy-Aware Linear Classifiers (NeurIPS 2020 · 29 citations)
- 2021 · Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously (ICML 2021 · 8 citations)
- 2022 · A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback (AAAI 2022 · 9 citations)
- 2023 · Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits (ICML 2023 · 1 citation)
- 2024 · Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · 1 citation)
- 2025 · Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · 0 citations)
- 2026 · Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere (ICML 2026 · 0 citations)
Earliest papers here
- Regret of Queueing Bandits (NeurIPS 2016 · 15 citations)
- Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions (NeurIPS 2016 · 10 citations)
- Tracking the Best Expert in Non-stationary Stochastic Environments (NeurIPS 2016)
What has been tried
94 papers here report 481 measured changes (a component added, removed or swapped, compared with a baseline): helped 72%, no clear effect 9%, hurt 14%, mixed 5%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| use a constant learning rate η_t^{(i)}(a_t)=\nicefrac{1}{\sqrt{T}} with an exponentially weighted estimator | Stochastic constraints · violation | \tilde O(T^{3/4}) | Hurt | Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · 1 citation) |
| Remove the negative-correlation requirement and guarantee only the mean condition | Combinatorial semi-bandits with strongly observable graph feedback · regret | \widetilde{O}(S\sqrt{T} + \sqrt{\alpha ST}) versus \Omega(S\sqrt{\alpha T}) | Hurt | Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · 0 citations) |
| Add early stopping when the running-mean action is certified feasible | Unit ball, m = 2, feasible instances · stopping time | < τ/10 | Helped | Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · 0 citations) |
| Vary the greedy stop level | Unique greedy path function, n=20 and k=5 · regret | Mixed | Nearly Minimax Optimal Submodular Maximization with Bandit Feedback (NeurIPS 2024 · 0 citations) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 67 papers; from OpenAlex and the papers' affiliations).
- Politecnico di Milano · 7 papers
- Google · 5 papers
- Polytechnic Institute of Milan · 5 papers
- The University of Tokyo · 4 papers
- Bocconi University · 3 papers
- University of Milan · 3 papers
- Kyoto University · 3 papers
- New York University · 3 papers
- Tel Aviv University · 3 papers
- Nanjing University · 2 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Online learning with feedback graphs (155 papers)
- Learning for pricing and auctions (101 papers)
- Online allocation with constraints (77 papers)
- Online decision-making with feedback structure (81 papers)
- Online linear-quadratic control regret (36 papers)
- Learning-augmented online algorithms (73 papers)
Elsewhere in the topic
- Constrained and unconstrained OCO algorithms (85 papers)
- Last-iterate convergence in games (65 papers)
- Dynamic and adaptive regret (57 papers)
- Parameter-free non-stationary online learning (45 papers)
- Fast no-regret dynamics in games (37 papers)
- Counterfactual regret minimization (15 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).