A Tale of Sampling and Estimation in Discounted Reinforcement Learning

Alberto Maria Metelli, Mirco Mutti, Marcello Restelli

Introduction

In discounted Reinforcement Learning (RL), the fundamental goal is often the estimation of a "mean" value—be it the expected return of a specific policy or the gradient required for policy optimization. While theoretical models often treat these as infinite-horizon sums, practical implementation relies on "episodic sampling." In this paradigm, an agent interacts with an environment for a fixed number of steps ($T$) before being reset.

Despite the ubiquity of this approach, a significant gap has persisted between engineering practice and theoretical justification. This paper provides the first formal theoretical framework to bridge this gap, analyzing how the interaction between the discount factor, environment mixing speed, and estimator choice determines the statistical efficiency of RL algorithms.

The Estimation Problem: Resets and Formulas

The authors formalize the estimation process as a combination of two components: a reset policy and an estimator. The reset policy determines when the simulation restarts, while the estimator is the mathematical formula used to process the resulting data.

Historically, practitioners have struggled with three core issues:

  1. The Mixing Problem: Most theories ignore the "spectral gap"—a measure of how quickly a Markov process reaches a steady state. In "sticky" or slow-mixing environments, standard estimates become highly unreliable.
  2. The Horizon Dilemma: Choosing the episode length $T$ involves a trade-off. Short episodes introduce significant bias, while excessively long episodes waste computational samples.
  3. Estimator Selection: While various methods exist to average data, it was previously unclear which method is mathematically optimal in terms of Probably Approximately Correct (PAC) requirements.

Methodology

The research evaluates four primary estimator types:

  • Fixed-Horizon (FHN/FHC): The industry standard, which resets every $T$ steps.
  • One-Sample (OS): An unbiased approach that resets with probability $1-\gamma$ at every step, utilizing only the final sample before the reset.
  • All-Samples (AS): A method that also resets with probability $1-\gamma$ but utilizes every transition collected during the trajectory.

To evaluate these, the authors employed minimax analysis to identify the most challenging scenarios for any algorithm and concentration inequalities to prove convergence rates. These were tested using a synthetic "Illustrative Markov Chain" (MC), a 3-state environment where mixing speed ($\alpha$) and the discount factor ($\gamma$) could be precisely manipulated.

Key Insights: The Fundamental Limits of Estimation

The Minimax Lower Bound

A major contribution of this work is the establishment of a minimax lower bound of order $\Omega(1/\sqrt{N(1 - \beta\gamma)})$, where $1-\beta$ represents the spectral gap. This bound explicitly demonstrates that estimation difficulty is not solely a function of the discount factor $\gamma$; it is equally dependent on the environment's mixing speed. As $\gamma$ approaches 1 or the environment becomes slower to explore (high $\beta$), the number of samples required for accuracy increases dramatically.

The Bias-Variance Trade-off

The study offers a counter-intuitive insight regarding the All-Samples (AS) estimator. While the AS estimator is technically biased—because samples within a single trajectory are dependent—the authors prove that the massive reduction in variance gained by using all available data far outweighs the bias.

The Failure of Correction Factors

In finite-horizon settings, practitioners often apply "correction factors" to compensate for the missing tail of the infinite sum. However, the authors found that in slow-mixing environments, these corrections can backfire, causing the bias to "skyrocket" and leading the estimate to diverge significantly from the true value.

Results and Empirical Findings

The theoretical and numerical analyses converge on several key points:

  • Optimality of All-Samples: The AS estimator is the only method that nearly matches the minimax lower bound without requiring the practitioner to tune the episode horizon $T$ based on the (usually unknown) spectral gap.
  • Inefficiency of Unbiased Estimators: The One-Sample (OS) estimator, despite being unbiased, is practically unusable in complex environments due to its extreme variance, requiring an impractical number of samples to converge.
  • Horizon Sensitivity: Fixed-Horizon estimators are highly sensitive to the choice of $T$. If $T$ is not perfectly calibrated to the environment's mixing speed, the error remains high regardless of the total data volume collected.

Conclusion and Future Directions

This research establishes that the All-Samples estimator is the most statistically efficient method for value estimation in discounted RL. By linking estimation error to both discounting and mixing speed, the paper provides a rigorous foundation for future algorithmic development.

While this study focuses on stationary functions, it opens the door for extending these minimax bounds to more complex settings, such as Deep RL (where the function being estimated changes over time) and scenarios involving inhomogeneous reward structures. These insights are poised to help develop more sample-efficient reset strategies for complex simulators.

Summary updated

BibTeX
@inproceedings{metelli2023tale,
  author = {Alberto Maria Metelli and Mirco Mutti and Marcello Restelli},
  title = {{A Tale of Sampling and Estimation in Discounted Reinforcement Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=wq3P0lWaRH},
}
Figure