# Adversarial Online Learning with Temporal Feedback Graphs

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

## Key facts

- Cited by 3 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 30 Jun 2024.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [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)
- [Online Learning with Bounded Recall](https://mlsanity.com/paper/2205.14519/) (2022)

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

- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [Decentralized Online Convex Optimization with Unknown Feedback Delays](https://mlsanity.com/paper/2601.07901/) (2026)
- [Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization](https://mlsanity.com/paper/2608.16216/) (2026)

## Abstract (arXiv)

We study a variant of prediction with expert advice where the learner's action at round t is only allowed to depend on losses on a specific subset of the rounds (where the structure of which rounds' losses are visible at time t is provided by a directed "feedback graph" known to the learner). We present a novel learning algorithm for this setting based on a strategy of partitioning the losses across sub-cliques of this graph. We complement this with a lower bound that is tight in many practical settings, and which we conjecture to be within a constant factor of optimal. For the important class of transitive feedback graphs, we prove that this algorithm is efficiently implementable and obtains the optimal regret bound (up to a universal constant).