# Online learning with graph-structured feedback against adaptive adversaries

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2018.

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

- [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)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Understanding the Role of Feedback in Online Learning with Switching Costs](https://mlsanity.com/paper/2306.09588/) (2023)

## Abstract (arXiv)

We derive upper and lower bounds for the policy regret of T-round online learning problems with graph-structured feedback, where the adversary is nonoblivious but assumed to have a bounded memory. We obtain upper bounds of widetilde O(T2/3) and widetilde O(T3/4) for strongly-observable and weakly-observable graphs, respectively, based on analyzing a variant of the Exp3 algorithm. When the adversary is allowed a bounded memory of size 1, we show that a matching lower bound of widetildeOmega(T2/3) is achieved in the case of full-information feedback. We also study the particular loss structure of an oblivious adversary with switching costs, and show that in such a setting, non-revealing strongly-observable feedback graphs achieve a lower bound of widetildeOmega(T2/3), as well.