Research map / Bandits and online learning / Online convex optimization and games
Online learning with feedback graphs
Design best-of-both-worlds experts and bandit algorithms with structured feedback and limited information.
155 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 Checklist 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.
35 papers in 2023–24 and 39 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic held steady, from 15.3% to 14.1%.
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 · Efficient Second Order Online Learning by Sketching (NeurIPS 2016 · 50 citations)
- 2017 · Emulating the Expert: Inverse Optimization through Online Learning (ICML 2017 · 28 citations)
- 2018 · Online Learning with Abstention (ICML 2018 · 22 citations)
- 2019 · Online-Within-Online Meta-Learning (NeurIPS 2019 · 22 citations)
- 2020 · Online Learning with Imperfect Hints (ICML 2020 · 15 citations)
- 2021 · Regret Bounds for Online Kernel Selection in Continuous Kernel Space (AAAI 2021 · 2 citations)
- 2022 · DeepLIIF: An Online Platform for Quantification of Clinical Pathology Slides (CVPR 2022 · 31 citations)
- 2023 · Improved Online Conformal Prediction via Strongly Adaptive Online Learning (ICML 2023 · 11 citations)
- 2024 · Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound (AAAI 2024 · 4 citations)
- 2025 · High-Dimensional Prediction for Sequential Decision Making (ICML 2025 · 1 citation)
- 2026 · Online Conformal Prediction via Universal Portfolio Algorithms (ICML 2026 · 0 citations)
Earliest papers here
- Efficient Second Order Online Learning by Sketching (NeurIPS 2016 · 50 citations)
- Adaptive Smoothed Online Multi-Task Learning (NeurIPS 2016 · 34 citations)
- Selecting Near-Optimal Learners via Incremental Data Allocation (AAAI 2016 · 34 citations)
What has been tried
108 papers here report 684 measured changes (a component added, removed or swapped, compared with a baseline): helped 67%, no clear effect 9%, hurt 17%, mixed 7%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use ψ(w)=\|w\|^{1+q} instead of ψ(w)=\|w\|^2 | Fully unconstrained OLO · regret bound | \frac{G^{1+1/q}}{\gamma^{1/q}}\log\left(1+\log\left(\frac{G}{h_1}\right)\right)^{1/q} | Mixed | Fully Unconstrained Online Learning (NeurIPS 2024 · 1 citation) |
| Replace the Euclidean initial safe set with an ℓ1 ball | Linear constraints · eluder dimension | increases by a factor of \log(d) | Hurt | Online Learning with Unknown Constraints (ICML 2025 · 0 citations) |
| Use higher-degree Chebyshev preconditioning (degree 10 rather than degree 5) | Linear LDS, τ_thresh=0.01 · absolute error | 0.15 -> 0.77 | Hurt | Universal Sequence Preconditioning (NeurIPS 2025 · 0 citations) |
| use context factor size greater than 1 instead of factor size 1 | AnimalAI, Categorical VAE · steps to reach goal | Helped | Learning Successor Features with Distributed Hebbian Temporal Memory (ICLR 2025 · 0 citations) | |
| Increase the quantile learning rate η₂ | Experiments varying η₂ · coverage control speed | Helped | Efficient Online Set-valued Classification with Bandit Feedback (ICML 2024 · 0 citations) | |
| Update the internal confusion matrix using estimated probabilities instead of observed labels | Benchmarks with many labels · Macro-averaged metrics | Helped | A General Online Algorithm for Optimizing Complex Performance Metrics (ICML 2024 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 32 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Baselines
- Standard Optimal Algorithm · 2 of 32 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 74 papers; from OpenAlex and the papers' affiliations).
- Purdue University · 10 papers
- Google · 7 papers
- University of Pennsylvania · 5 papers
- Massachusetts Institute of Technology · 4 papers
- Tianjin University · 3 papers
- Columbia University · 3 papers
- Amazon · 3 papers
- University of Washington · 3 papers
- University of California, Berkeley · 3 papers
- Leiden University · 3 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
- Best-of-both-worlds bandit algorithms (125 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).