Optimal Online Learning Procedures for Model-Free Policy Evaluation

Tsuyoshi Ueno, Shin-ichi Maeda, Motoaki Kawanabe, Shin Ishii

Introduction

In reinforcement learning (RL), policy evaluation is the critical task of estimating the value function—the expected cumulative reward—associated with a specific strategy. Historically, this has been approached through two distinct lenses: online procedures like Temporal Difference (TD) learning, which are computationally efficient but often slow to converge, and batch procedures like Least Squares Temporal Difference (LSTD), which offer superior statistical accuracy at the cost of higher memory and computational overhead. This paper introduces a unified theoretical framework that bridges these approaches using semiparametric statistics, deriving an optimal online learning algorithm that matches the statistical efficiency of state-of-the-art batch methods.

Theoretical Framework: Semiparametric Inference

The authors frame policy evaluation as a problem of semiparametric statistical inference. In this paradigm, the parameters defining the value function are the "parameters of interest," while the unknown environment dynamics (e.g., transition probabilities) are treated as "nuisance parameters." By utilizing estimating functions, the authors derive consistent M-estimators that do not require explicit modeling of these hidden complexities.

Estimating function convergence: The estimator $\hat{\theta}$ is found where the empirical estimating function crosses zero, approximating the true parameter $\theta^*$.

To handle the temporal dependencies inherent in Markov Reward Processes (MRPs), the framework employs Martingale Estimating Functions. This ensures that the estimators remain valid even when samples are correlated over time. The central insight is that both TD and LSTD can be viewed as different methods for solving the same underlying estimating equation, allowing for a direct comparison of their statistical properties.

Algorithm Design: Optimal Online Learning

The paper proposes two primary advancements for online learning:

  1. Algorithm 1 (The Optimal Online Algorithm): This procedure uses online function approximation to estimate an "optimal weight function." This weight function is mathematically proven to minimize the asymptotic variance of the estimation error, effectively reaching the theoretical lower bound for accuracy.
  2. Accelerated TD: The authors demonstrate that the slow convergence of traditional TD is not a fundamental limitation of online updates but rather a consequence of a poorly tuned scaling matrix ($R$). By setting $R$ to approximate the inverse of the gradient of the estimating function, a standard TD update can be "accelerated" to achieve the same convergence rate as batch LSTD.

Experimental Results: The Chain Walk Problem

The proposed algorithms were evaluated on a synthetic 10-state Chain Walk problem. In this environment, an agent moves along a chain with rewards centered in the middle. The performance was measured by the Mean Squared Error (MSE) of the estimated value function over 200 trajectories.

Algorithm Average MSE
Standard TD 35.98
Accelerated-TD 13.93
Batch LSTD 12.97
Optimal Online Algorithm 8.46
Batch gLSTD 8.44

The results confirm the theoretical predictions: the Optimal Online algorithm significantly outperforms standard TD and matches the performance of the "gold standard" batch algorithm, generalized LSTD (gLSTD).

Discussion and Limitations

A key takeaway is the importance of the scaling matrix $R$; with proper tuning, online methods can be as statistically efficient as batch methods. Furthermore, the semiparametric approach provides robustness against nuisance parameters, meaning the optimal value function can be estimated without perfect knowledge of the transition model.

However, the authors note several limitations. The current theory assumes no model misspecification; in practice, the bias from a poor choice of basis functions might outweigh the variance benefits. Additionally, maintaining the scaling matrix incurs an $O(m^2)$ computational cost per step, which may necessitate approximations in high-dimensional settings. Future work will focus on handling model misspecification and automated basis function selection.

Summary updated

BibTeX
@inproceedings{ueno2009optimal,
  author = {Tsuyoshi Ueno and Shin-ichi Maeda and Motoaki Kawanabe and Shin Ishii},
  title = {{Optimal Online Learning Procedures for Model-Free Policy Evaluation}},
  booktitle = {ECML/PKDD},
  year = {2009},
  doi = {10.1007/978-3-642-04174-7\_31},
}
Figure