An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning

ABSTRACT

We show that linear value-function approximation is equivalent to a form of linear model approximation. We then derive a relationship between the model-approximation error and the Bellman error, and show how this relationship can guide feature selection for model improvement and/or value-function improvement. We also show how these results give insight into the behavior of existing feature-selection algorithms.

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: Dean, T., & Givan, R. (1997). Model minimization in Markov decision processes. AAAI-97.
• 4: Philipp W. Keller , Shie Mannor , Doina Precup, Automatic basis function construction for approximate dynamic programming and reinforcement learning, Proceedings of the 23rd international conference on Machine learning, p.449-456, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143901]
• 5: Daphne Koller , Ronald Parr, Computing Factored Value Functions for Policies in Structured MDPs, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1332-1339, July 31-August 06, 1999
• 6: Michail G. Lagoudakis , Ronald Parr, Least-squares policy iteration, The Journal of Machine Learning Research, 4, p.1107-1149, 12/1/2003
• 7: Sridhar Mahadevan , Mauro Maggioni, Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes, The Journal of Machine Learning Research, 8, p.2169-2231, 12/1/2007
• 8: Mallat, S. G., & Zhang, Z. (1993). Matching pursuits with time-frequency dictionaries. IEEE Trans. on Signal Processing, 41.
• 9: Ronald Parr , Christopher Painter-Wakefield , Lihong Li , Michael Littman, Analyzing feature generation for value-function approximation, Proceedings of the 24th international conference on Machine learning, p.737-744, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273589]
• 10: Petrik, M. (2007). An analysis of Laplacian methods for value function approximation in MDPs. IJCAI-07.
• 11: Sanner, S., & Boutilier, C. (2005). Approximate linear programming for first-order MDPs. UAI-05.
• 12: 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]
• 13: Richard S. Sutton, Reinforcement Learning, Kluwer Academic Publishers, Norwell, MA, 1992
• 14: Wu, J.-H., & Givan, R. (2004). Feature-discovering approximate value iteration methods (Technical Report TR-ECE-04-06). Purdue University.
• 15: Yu, H., & Bertsekas, D. (2006). Convergence results for some temporal difference methods based on least squares (Technical Report LIDS-2697). MIT.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory