Analyzing feature generation for value-function approximation

ABSTRACT

We analyze a simple, Bellman-error-based approach to generating basis functions for value-function approximation. We show that it generates orthogonal basis functions that provably tighten approximation error bounds. We also illustrate the use of this approach in the presence of noise on some sample problems.

REFERENCES

• 1: Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997 [doi>10.1023/A:1006559212014]
• 2: Boyan, J. A., & Moore, A. W. (1995). Generalization in reinforcement learning: Safely approximating the value function. Advances in Neural Information Processing Systems 7 (pp. 369--376). Cambridge, MA: The MIT Press.
• 3: 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]
• 4: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
• 5: 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]
• 6: 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
• 7: Michail G. Lagoudakis , Ronald Parr, Least-squares policy iteration, The Journal of Machine Learning Research, 4, p.1107-1149, 12/1/2003
• 8: Mahadevan, S., & Maggioni, M. (2006). Proto-value functions: A Laplacian framework for learning representation and control in Markov decision processes (Technical Report 2006--35). University of Massachusetts, Amherst.
• 9: Mallat, S. G., & Zhang, Z. (1993). Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing, 41.
• 10: Menache, I., Mannor, S., & Shimkin, N. (2005). Basis function adaptation in temporal difference reinforcement learning. Annals of Operations Research, 134.
• 11: Munos, R. (2003). Error bounds for approximate policy iteration. Proceedings of the Twentieth International Conference on Machine Learning.
• 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: Benjamin Van Roy , John N. Tsitsiklis, Learning and value function approximation in complex decision processes, Massachusetts Institute of Technology, 1998
• 14: Vapnik, V., Golowich, S., & Smola, A. (1997). Support vector method for function approximation, regression estimation, and signal processing. Advances in Neural Information Processing Systems 9 (pp. 281--287). Cambridge, MA: MIT Press.
• 15: Yu, H., & Bertsekas, D. (2006). Convergence results for some temporal difference methods based on least squares (Technical Report LIDS-2697). Laboratory for Information and Decision Systems, Massachusetts Institute of Technology.