A Tale of Sampling and Estimation in Discounted Reinforcement Learning
This work addresses a foundational gap in reinforcement learning theory by formally studying the pitfalls of episodic sampling, which is crucial for improving estimation accuracy in policy evaluation and optimization tasks.
The paper tackles the problem of estimating the mean of a function in discounted reinforcement learning, such as expected return or policy gradient, by analyzing the mismatch between practical finite-horizon episodic sampling and the ideal setting that considers mixing properties. It presents a minimax lower bound connecting estimation error to mixing and discount factors, and shows that sampling from the discounted kernel matches this bound without needing to tune the episode horizon.
The most relevant problems in discounted reinforcement learning involve estimating the mean of a function under the stationary distribution of a Markov reward process, such as the expected return in policy evaluation, or the policy gradient in policy optimization. In practice, these estimates are produced through a finite-horizon episodic sampling, which neglects the mixing properties of the Markov process. It is mostly unclear how this mismatch between the practical and the ideal setting affects the estimation, and the literature lacks a formal study on the pitfalls of episodic sampling, and how to do it optimally. In this paper, we present a minimax lower bound on the discounted mean estimation problem that explicitly connects the estimation error with the mixing properties of the Markov process and the discount factor. Then, we provide a statistical analysis on a set of notable estimators and the corresponding sampling procedures, which includes the finite-horizon estimators often used in practice. Crucially, we show that estimating the mean by directly sampling from the discounted kernel of the Markov process brings compelling statistical properties w.r.t. the alternative estimators, as it matches the lower bound without requiring a careful tuning of the episode horizon.