A semiparametric statistical approach to model-free policy evaluation

ABSTRACT

Reinforcement learning (RL) methods based on least-squares temporal difference (LSTD) have been developed recently and have shown good practical performance. However, the quality of their estimation has not been well elucidated. In this article, we discuss LSTD-based policy evaluation from the new view-point of semiparametric statistical inference. In fact, the estimator can be obtained from a particular estimating function which guarantees its convergence to the true value asymptotically, without specifying a model of the environment. Based on these observations, we 1) analyze the asymptotic variance of an LSTD-based estimator, 2) derive the optimal estimating function with the minimum asymptotic estimation variance, and 3) derive a suboptimal estimator to reduce the computational burden in obtaining the optimal estimating function.

REFERENCES

• 1: Amari, S., & Kawanabe, M. (1997). Information geometry of estimating functions in semi-parametric statistical models. Bernoulli, 3, 29--54.
• 2: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 3: Bickel, D., Ritov, D., Klaassen, C., & Wellner, J. (1998). Efficient and Adaptive Estimation for Semi-parametric Models. Springer.
• 4: Steven J. Bradtke , Andrew G. Barto, Linear least-squares algorithms for temporal difference learning, Machine Learning, v.22 n.1-3, p.33-57, Jan./Feb./March 1996 [doi>10.1007/BF00114723]
• 5: Godambe, V. (1985). The foundations of finite sample estimation in stochastic processes. Biometrika, 72, 419--428.
• 6: Godambe, V. (Ed.). (1991). Estimating Functions. Oxford Science.
• 7: Evan Greensmith , Peter L. Bartlett , Jonathan Baxter, Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning, The Journal of Machine Learning Research, 5, p.1471-1530, 12/1/2004
• 8: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 9: Michail G. Lagoudakis , Ronald Parr, Least-squares policy iteration, The Journal of Machine Learning Research, 4, p.1107-1149, 12/1/2003
• 10: Shie Mannor , Duncan Simester , Peng Sun , John N. Tsitsiklis, Bias and Variance Approximation in Value Function Estimates, Management Science, v.53 n.2, p.308-322, February 2007 [doi>10.1287/mnsc.1060.0614]
• 11: Peters, J., Vijayakumar, S., & Schaal, S. (2005). Natural actor-critic. Proceedings of the 16th European Conference on Machine Learning (pp. 280--291).
• 12: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 13: Peter Young, Recursive estimation and time-series analysis: an introduction, Springer-Verlag New York, Inc., New York, NY, 1984

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Least squares methods

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory