# Optimism and Delays in Episodic Reinforcement Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 15 Nov 2021.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)

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

- [Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2405.07637/) (2024)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward](https://mlsanity.com/paper/2305.02527/) (2023)
- [Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning](https://mlsanity.com/paper/2603.03480/) (2026)
- [Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays](https://mlsanity.com/paper/2605.23351/) (2026)

## Abstract (arXiv)

There are many algorithms for regret minimisation in episodic reinforcement learning. This problem is well-understood from a theoretical perspective, providing that the sequences of states, actions and rewards associated with each episode are available to the algorithm updating the policy immediately after every interaction with the environment. However, feedback is almost always delayed in practice. In this paper, we study the impact of delayed feedback in episodic reinforcement learning from a theoretical perspective and propose two general-purpose approaches to handling the delays. The first involves updating as soon as new information becomes available, whereas the second waits before using newly observed information to update the policy. For the class of optimistic algorithms and either approach, we show that the regret increases by an additive term involving the number of states, actions, episode length, the expected delay and an algorithm-dependent constant. We empirically investigate the impact of various delay distributions on the regret of optimistic algorithms to validate our theoretical results.