  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.
