# Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 16 Jun 2022.

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

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [Online Learning with Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Stochastic Online Learning with Probabilistic Graph Feedback](https://mlsanity.com/paper/1903.01083/) (2019)
- [Thompson Sampling For Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1701.04238/) (2017)

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

- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)

## Abstract (arXiv)

The problem of online learning with graph feedback has been extensively studied in the literature due to its generality and potential to model various learning tasks. Existing works mainly study the adversarial and stochastic feedback separately. If the prior knowledge of the feedback mechanism is unavailable or wrong, such specially designed algorithms could suffer great loss. To avoid this problem, citeterez2021towards try to optimize for both environments. However, they assume the feedback graphs are undirected and each vertex has a self-loop, which compromises the generality of the framework and may not be satisfied in applications. With a general feedback graph, the observation of an arm may not be available when this arm is pulled, which makes the exploration more expensive and the algorithms more challenging to perform optimally in both environments. In this work, we overcome this difficulty by a new trade-off mechanism with a carefully-designed proportion for exploration and exploitation. We prove the proposed algorithm simultaneously achieves poly log T regret in the stochastic setting and minimax-optimal regret of tildeO(T2/3) in the adversarial setting where T is the horizon and tildeO hides parameters independent of T as well as logarithmic terms. To our knowledge, this is the first best-of-both-worlds result for general feedback graphs.