Value function estimation in Markov reward processes: Instance-dependent 𝓁∞-bounds for policy evaluation

Ashwin Pananjady, Martin J. WainwrightarXiv 2019 · arXiv

Abstract

Markov reward processes (MRPs) are used to model stochastic phenomena arising in operations research, control engineering, robotics, and artificial intelligence, as well as communication and transportation networks. In many of these cases, such as in the policy evaluation problem encountered in reinforcement learning, the goal is to estimate the long-term value function of such a process without access to the underlying population transition and reward functions. Working with samples generated under the synchronous model, we study the problem of estimating the value function of an infinite-horizon, discounted MRP on finitely many states in the $\ell_\infty$-norm. We analyze both the standard plug-in approach to this problem and a more robust variant, and establish non-asymptotic bounds that depend on the (unknown) problem instance, as well as data-dependent bounds that can be evaluated based on the observations of state-transitions and rewards. We show that these approaches are minimax-optimal up to constant factors over natural sub-classes of MRPs. Our analysis makes use of a leave-one-out decoupling argument tailored to the policy evaluation problem, one which may be of independent interest.

Introduction

Policy evaluation is a fundamental task in reinforcement learning, focused on estimating the expected long-term discounted reward—the "value"—of a specific policy. While theoretical guarantees for this task often rely on "worst-case" or global analysis, such bounds can be overly pessimistic. In practice, the difficulty of learning a value function depends heavily on the specific structure of the environment. This paper bridges the gap by providing instance-dependent, non-asymptotic bounds for policy evaluation in the $\ell_\infty$-norm, revealing how local transition and reward structures dictate statistical efficiency.

Methods and Estimators

The study focuses on two primary estimators under a generative (synchronous) model, where samples can be drawn from any state-action pair.

  1. The Plug-in Estimator: The standard approach where empirical estimates of the transition matrix ($\hat{P}$) and reward vector ($\hat{r}$) are used to solve the Bellman equation: $\hat{\theta} = (I - \gamma \hat{P})^{-1} \hat{r}$.
  2. The Median-of-Means (MoM) Estimator: A robust variant that splits data into blocks, computes block means, and takes their median to mitigate the impact of rare, high-variance events.

The authors introduce a novel leave-one-out decoupling argument to address the statistical dependencies between estimated transitions and the value function, which is critical for deriving tight $\ell_\infty$ bounds.

Key Insights: Beyond Worst-Case Analysis

A central finding is the distinction between the span of the value function and its variance.

  • The "Span" Penalty: The plug-in estimator's performance is sensitive to the difference between the maximum and minimum values (the span). In environments with high-reward but rarely visited states, the plug-in method can be inefficient.
  • Minimax Optimality: The fundamental limit of policy evaluation depends on the variance of the value function. The MoM estimator is shown to be minimax-optimal because it removes the dependence on the span, succeeding where the plug-in estimator may struggle.
  • Tightness of Local Bounds: For a discount factor $\gamma = 0.99$, these local results can improve upon previous global bounds by a factor of 100 in error, implying a 10,000-fold reduction in required sample complexity.

Key Results

  • Theorem 1: Provides the first instance-dependent upper bounds for the plug-in estimator, showing error scales with $\frac{1}{1-\gamma}$ and depends on both variance and span.
  • Theorem 2: Establishes minimax lower bounds, proving that no algorithm can surpass a threshold defined by the instance's variance.
  • Theorem 3: Proves the MoM estimator achieves this lower bound, closing the gap for high-span environments.

Empirical Validation

The theoretical results are validated using synthetic MRP constructions designed to highlight the gap between global and local bounds.

In the 3-state MRP shown above, local bounds provide significantly tighter error estimates than global ones. Experiments on a "hard" 2-state chain further confirm that empirical error scales exactly as predicted by the theory relative to the discount complexity $1/(1-\gamma)$ and reward variance.

Conclusion and Future Work

This work establishes that instance-dependent analysis is essential for a precise understanding of policy evaluation. While the MoM estimator offers superior robustness and minimax optimality, it comes with higher computational costs. Future research directions include extending these local bounds to the trajectory-based setting and exploring the complexities of "local" geometry in the context of function approximation.

Summary updated

Abstract

Markov reward processes (MRPs) are used to model stochastic phenomena arising in operations research, control engineering, robotics, and artificial intelligence, as well as communication and transportation networks. In many of these cases, such as in the policy evaluation problem encountered in reinforcement learning, the goal is to estimate the long-term value function of such a process without access to the underlying population transition and reward functions. Working with samples generated under the synchronous model, we study the problem of estimating the value function of an infinite-horizon, discounted MRP on finitely many states in the $\ell_\infty$-norm. We analyze both the standard plug-in approach to this problem and a more robust variant, and establish non-asymptotic bounds that depend on the (unknown) problem instance, as well as data-dependent bounds that can be evaluated based on the observations of state-transitions and rewards. We show that these approaches are minimax-optimal up to constant factors over natural sub-classes of MRPs. Our analysis makes use of a leave-one-out decoupling argument tailored to the policy evaluation problem, one which may be of independent interest.
BibTeX
@misc{pananjady2019value,
  author = {Ashwin Pananjady and Martin J. Wainwright},
  title = {{Value function estimation in Markov reward processes: Instance-dependent 𝓁∞-bounds for policy evaluation}},
  year = {2019},
  eprint = {1909.08749},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.08749},
}
Figure