Automatic basis function construction for approximate dynamic programming and reinforcement learning

ABSTRACT

We address the problem of automatically constructing basis functions for linear approximation of the value function of a Markov Decision Process (MDP). Our work builds on results by Bertsekas and Castañon (1989) who proposed a method for automatically aggregating states to speed up value iteration. We propose to use neighborhood component analysis (Goldberger et al., 2005), a dimensionality reduction technique created for supervised learning, in order to map a high-dimensional state space to a low-dimensional space, based on the Bellman error, or on the temporal difference (TD) error. We then place basis function in the lower-dimensional space. These are added as new features for the linear function approximator. This approach is applied to a high-dimensional inventory control problem.

REFERENCES

• 1: Bertsekas, D. (2005). Dynamic programming and optimal control vol. 1 third edition. Athena Scientific.
• 2: Bertsekas, D., & Castaññon, D. (1989). Adaptive aggregation methods for infinite horizon dynamic programming. IEEE Transactions on Automatic Control, 34, 589--598.
• 3: Justin A. Boyan, Technical Update: Least-Squares Temporal Difference Learning, Machine Learning, v.49 n.2-3, p.233-246, November-December 2002
• 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: Dmitriy Fradkin , David Madigan, Experiments with random projections for machine learning, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956812]
• 6: Goldberger, J., Roweis, S., Hinton, G., & Salakhutdinov, R. (2005). Neighbourhood components analysis. In NIPS 17, 513--520.
• 7: Jacobs, R. A. (1988). Increased rates of convergence through learning rate adaptation. Neural Networks, 1, 295--307.
• 8: Mahadevan, S. (2005). Samuel meets Amarel: Automating value function approximation using global state space analysis. In Proceedings of AAAI.
• 9: Mannor, S., Menache, I., & Shimkin, N. (2005). Basis function adaptation in temporal difference reinforcement learning. Annals of Operations Research, 134, 215--238.
• 10: Rémi Munos , Andrew Moore, Variable Resolution Discretization in Optimal Control, Machine Learning, v.49 n.2-3, p.291-323, November-December 2002
• 11: Ratitch, B., & Precup, D. (2004). Sparse distributed memories for on-line value-based reinforcement learning. In Proceedings of ECML.
• 12: Smart, W. (2004). Explicit manifold representations for value-functions in reinforcement learning. In Proceedings of the 8th int. symp. on ai and mathematics.
• 13: 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]
• 14: Richard S. Sutton, Reinforcement Learning, Kluwer Academic Publishers, Norwell, MA, 1992
• 15: Vladislav Tadić, On the Convergence of Temporal-Difference Learning with Linear Function Approximation, Machine Learning, v.42 n.3, p.241-267, March 2001 [doi>10.1023/A:1007609817671 ]
• 16: Tsitsiklis, J., & Van Roy, B. (1997). An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42, 674--690.
• 17: Ziv, O., & Shimkin, N. (2005). Multigrid algorithms for temporal difference reinforcement learning. In Proc. icml workshop on rich representations for rl.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Theory