# Learning on the Edge: Online Learning with Stochastic Feedback Graphs

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 45 references that are in the map.
- First posted on arXiv 9 Oct 2022.

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

- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [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)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Information Directed Sampling for Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1711.03198/) (2017)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Stochastic Online Learning with Probabilistic Graph Feedback](https://mlsanity.com/paper/1903.01083/) (2019)
- [Online learning with feedback graphs and switching costs](https://mlsanity.com/paper/1810.09666/) (2018)
- [Adversarial Online Learning with noise](https://mlsanity.com/paper/1810.09346/) (2018)
- [Online learning with graph-structured feedback against adaptive adversaries](https://mlsanity.com/paper/1804.00335/) (2018)

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

- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Efficient Contextual Bandits with Uninformed Feedback Graphs](https://mlsanity.com/paper/2402.08127/) (2024)
- [Online Learning with Feedback Graphs: The True Shape of Regret](https://mlsanity.com/paper/2306.02971/) (2023)
- [Can Probabilistic Feedback Drive User Impacts in Online Platforms?](https://mlsanity.com/paper/2401.05304/) (2024)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Graph Feedback Bandits on Similar Arms: With and Without Graph Structures](https://mlsanity.com/paper/2501.14314/) (2025)
- [Graph Feedback Bandits with Similar Arms](https://mlsanity.com/paper/2405.11171/) (2024)
- [Online Network Source Optimization with Graph-Kernel MAB](https://mlsanity.com/paper/2307.03641/) (2023)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Pooling and Drift in Delayed Bandits](https://mlsanity.com/paper/2609.01761/) (2026)

## Abstract (arXiv)

The framework of feedback graphs is a generalization of sequential decision-making with bandit or full information feedback. In this work, we study an extension where the directed feedback graph is stochastic, following a distribution similar to the classical ErdHos-R'enyi model. Specifically, in each round every edge in the graph is either realized or not with a distinct probability for each edge. We prove nearly optimal regret bounds of order minbiglminvarepsilon √(α_varepsilon/varepsilon) T,, minvarepsilon (δ_varepsilon/varepsilon)1/3 T2/3bigr (ignoring logarithmic factors), where αvarepsilon and δvarepsilon are graph-theoretic quantities measured on the support of the stochastic feedback graph G with edge probabilities thresholded at varepsilon. Our result, which holds without any preliminary knowledge about G, requires the learner to observe only the realized out-neighborhood of the chosen action. When the learner is allowed to observe the realization of the entire graph (but only the losses in the out-neighborhood of the chosen action), we derive a more efficient algorithm featuring a dependence on weighted versions of the independence and weak domination numbers that exhibits improved bounds for some special cases.