Optimism and Delays in Episodic Reinforcement Learning

Benjamin Howson, Ciara Pike-Burke, Sarah Filippi

Abstract

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.

Introduction

Most theoretical Reinforcement Learning (RL) models operate under the assumption of immediate feedback. In a standard episodic Markov Decision Process (MDP), an agent completes an episode and immediately utilizes the resulting data to update its policy for the subsequent round. However, real-world applications—ranging from healthcare outcomes and e-commerce conversions to hardware communication lags—rarely provide such instantaneous feedback.

When feedback is delayed, agents must make decisions based on stale information. Previous theoretical work often produced loose bounds or required prior knowledge of the maximum possible delay. This paper addresses these gaps by providing a robust framework for learning under stochastic delays without requiring knowledge of the maximum delay duration.

Meta-Algorithms for Delayed Feedback

The authors propose two general-purpose meta-algorithms that can wrap around existing optimistic, model-based RL algorithms (such as UCRL2 or UCBVI):

  1. Active Updating: The agent updates its policy the moment any new feedback arrives. While intuitive, this approach is mathematically complex to analyze because policy updates occur at irregular, stochastic intervals.
  2. Lazy Updating: This approach employs a "batching" strategy. The agent waits to update until its observed visitation counter for a state-action pair increases by a specific factor $(1 + 1/\alpha)$. This effectively creates a more stable, simulated "non-delayed" environment for the underlying algorithm.

Theoretical Contributions

The core theoretical contribution is the proof that for a wide class of optimistic algorithms, delays result in an additive rather than multiplicative penalty to regret. This means that agents can still learn efficiently even with significant lag, provided the expected delay is finite.

Table 1: Regret bounds for various optimistic algorithms under Active and Lazy updating strategies.

As shown in Table 1, the regret penalty depends on a constant $C$ that characterizes the tightness of an algorithm's exploration bonuses. Algorithms with aggressive bonuses (like UCBVI) may suffer a slightly higher penalty from delays compared to more conservative counterparts. Crucially, these bounds remove previous dependencies on episode length ($H$) and state space size ($S$) within the delay term, offering significantly tighter guarantees than prior state-of-the-art methods.

Experimental Evaluation

The researchers evaluated these methods using the Chain Environment, a classic benchmark designed to test exploration efficiency. To simulate real-world conditions, they tested four stochastic delay distributions: Constant, Geometric, Poisson, and Uniform, with expected delays ($\mathbb{E}[\tau]$) ranging up to 500 episodes.

Key Results

  • Empirical Performance: Active Updating consistently achieved the lowest regret across all tested delay distributions.
  • Robustness of Lazy Updating: While Active Updating was faster, Lazy Updating (particularly with $\alpha=1$) proved highly robust. By forcing the agent to wait for more information, it maintained stable performance across varying types of delay.
  • Baseline Comparison: Both meta-algorithms significantly outperformed standard "Explicit Exploration" baselines, which often failed to converge to optimal policies within the experimental timeframe.

Conclusion and Future Work

This work demonstrates that optimism remains a powerful principle even in the presence of significant feedback lag. By showing that the regret penalty is additive and independent of the maximum delay, the authors provide a more practical theoretical foundation for real-world RL.

Future research may extend these meta-algorithms to model-free methods (such as Q-learning) or Posterior Sampling. Additionally, while Active Updating is theoretically superior, its computational overhead for frequent policy recalculation suggests that Lazy Updating may remain the preferred choice for high-throughput practical systems.

Summary updated

Abstract

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.
BibTeX
@inproceedings{howson2023optimism,
  author = {Benjamin Howson and Ciara Pike-Burke and Sarah Filippi},
  title = {{Optimism and Delays in Episodic Reinforcement Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=J5ndk8HOdC},
}
Figure