# Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [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)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [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)
- [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)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Reward Maximization Under Uncertainty: Leveraging Side-Observations on Networks](https://mlsanity.com/paper/1704.07943/) (2017)
- [Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality](https://mlsanity.com/paper/2206.10022/) (2022)

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

- [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)
- [Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach](https://mlsanity.com/paper/2312.12731/) (2023)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)

## Abstract (arXiv)

We study high-probability regret bounds for adversarial K-armed bandits with time-varying feedback graphs over T rounds. For general strongly observable graphs, we develop an algorithm that achieves the optimal regret widetildeO((sumt=1Tαt)1/2+maxt∈[T]αt) with high probability, where αt is the independence number of the feedback graph at round t. Compared to the best existing result [Neu, 2015] which only considers graphs with self-loops for all nodes, our result not only holds more generally, but importantly also removes any poly(K) dependence that can be prohibitively large for applications such as contextual bandits. Furthermore, we also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs, which even improves the best expected regret bound of [Alon et al., 2015] by removing the O(√KT) term with a refined analysis. Our algorithms are based on the online mirror descent framework, but importantly with an innovative combination of several techniques. Notably, while earlier works use optimistic biased loss estimators for achieving high-probability bounds, we find it important to use a pessimistic one for nodes without self-loop in a strongly observable graph.