# Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality

arXiv: https://arxiv.org/abs/2206.10022 · HTML: https://mlsanity.com/paper/2206.10022/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 20 Jun 2022.

## Builds on (most cited first, 13 of 13)

- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Small-loss bounds for online learning with partial information](https://mlsanity.com/paper/1711.03639/) (2017)
- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)
- [Online Learning with Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [Stochastic Online Learning with Probabilistic Graph Feedback](https://mlsanity.com/paper/1903.01083/) (2019)
- [Reward Maximization Under Uncertainty: Leveraging Side-Observations on Networks](https://mlsanity.com/paper/1704.07943/) (2017)
- [Reinforcement Learning with Feedback Graphs](https://mlsanity.com/paper/2005.03789/) (2020)

## Built on by (most cited first, 3 of 3)

- [Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs](https://mlsanity.com/paper/2210.01376/) (2022)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Reinforcement Learning with Intrinsically Motivated Feedback Graph for Lost-sales Inventory Control](https://mlsanity.com/paper/2406.18351/) (2024)

## Abstract (arXiv)

We revisit the problem of stochastic online learning with feedback graphs, with the goal of devising algorithms that are optimal, up to constants, both asymptotically and in finite time. We show that, surprisingly, the notion of optimal finite-time regret is not a uniquely defined property in this context and that, in general, it is decoupled from the asymptotic rate. We discuss alternative choices and propose a notion of finite-time optimality that we argue is meaningful. For that notion, we give an algorithm that admits quasi-optimal regret both in finite-time and asymptotically.