Sigma point policy iteration

ABSTRACT

In reinforcement learning, least-squares temporal difference methods (e.g., LSTD and LSPI) are effective, data-efficient techniques for policy evaluation and control with linear value function approximation. These algorithms rely on policy-dependent expectations of the transition and reward functions, which require all experience to be remembered and iterated over for each new policy evaluated. We propose to summarize experience with a compact policy-independent Gaussian model. We show how this policy-independent model can be transformed into a policy-dependent form and used to perform policy evaluation. Because closed-form transformations are rarely available, we introduce an efficient sigma point approximation. We show that the resulting Sigma-Point Policy Iteration algorithm (SPPI) is mathematically equivalent to LSPI for tabular representations and empirically demonstrate comparable performance for approximate representations. However, the experience does not need to be saved or replayed, meaning that for even moderate amounts of experience, SPPI is an order of magnitude faster than LSPI.

REFERENCES

• 1: Justin A. Boyan, Least-Squares Temporal Difference Learning, Proceedings of the Sixteenth International Conference on Machine Learning, p.49-56, June 27-30, 1999
• 2: 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]
• 3: N. J. Higham. Computing a nearest symmetric positive semidefinite matrix. Linear Algebra and its Applications, 103:103--118, 1988.
• 4: S. Julier and J. K. Uhlmann. A general method for approximating nonlinear transformations of probability distributions. Technical report, University of Oxford, 1996.
• 5: Daphne Koller , Ronald Parr, Policy Iteration for Factored MDPs, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.326-334, June 30-July 03, 2000
• 6: Michail G. Lagoudakis , Ronald Parr, Least-squares policy iteration, The Journal of Machine Learning Research, 4, p.1107-1149, 12/1/2003
• 7: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 8: Richard S. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning, v.3 n.1, p.9-44, August 1988 [doi>10.1023/A:1022633531479]
• 9: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 10: R. van der Merwe and E. A. Wan. The square-root unscented Kalman filter for state and parameter-estimation. In International Conference on Acoustics, Speech, and Signal Processing, 2001.
• 11: H. O. Wang, K. Tanaka, and M. F. Griffin. An approach to fuzzy control of non-linear systems: Stability and design issues. IEEE Transactions on Fuzzy Systems, 4(1):14--23, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
least-squares, policy iteration, reinforcement learning