Relating reinforcement learning performance to classification performance

ABSTRACT

We prove a quantitative connection between the expected sum of rewards of a policy and binary classification performance on created subproblems. This connection holds without any unobservable assumptions (no assumption of independence, small mixing time, fully observable states, or even hidden states) and the resulting statement is independent of the number of states or actions. The statement is critically dependent on the size of the rewards and prediction performance of the created classifiers.We also provide some general guidelines for obtaining good classification performance on the created subproblems. In particular, we discuss possible methods for generating training examples for a classifier learning algorithm.

REFERENCES

• 1: Bagnell, D. (2004). Personal communication.
• 2: Bagnell, D., Kakade, S., Ng, A., & Schneider, J. (2004). Policy search by dynamic programming. Advances in Neural Information Processing Systems 16 (NIPS*2003).
• 3: Baird, L. C. (1993). Advantage updating (Technical Report). Wright Laboratory.
• 4: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 5: Beygelzimer, A., Dani, V., Hayes, T., Langford, J., & Zadrozny, B. (2004). Reductions between classification tasks. Preprint at http://hunch.net/~jl/projects/reductions/mc_to_c/mc_submission.ps.
• 6: Evan-Dar, E., Kakade, S., & Mansour, Y. (2005). Reinforcement learning in POMDPs without resets. Preprint at http://www.cis.upenn.edu/~skakade/papers/rl/learn_pomdp.ps.
• 7: Fern, A., Yoon, S., & Givan, R. (2004). Approximate policy iteration with a policy language bias. Advances in Neural Information Processing Systems 16 (NIPS*2003).
• 8: Sham Kakade , John Langford, Approximately Optimal Approximate Reinforcement Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.267-274, July 08-12, 2002
• 9: Michael J. Kearns , Yishay Mansour , Andrew Y. Ng, A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1324-1231, July 31-August 06, 1999
• 10: Kearns, M., Ng, A., & Mansour, Y. (2000). Approximate planning in large pomdps via reusable trajectories. Advances in Neural Information Processing Systems 12 (NIPS*1999).
• 11: Michael J. Kearns , Satinder P. Singh, Near-Optimal Reinforcement Learning in Polynominal Time, Proceedings of the Fifteenth International Conference on Machine Learning, p.260-268, July 24-27, 1998
• 12: Roni Khardon, Learning to Take Actions, Machine Learning, v.35 n.1, p.57-90, April 1999 [doi>10.1023/A:1007571119753 ]
• 13: Lagoudakis, M., & Parr, R. (2003). Reinforcement learning as classification: Leveraging modern classifiers. Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003) (pp. 424--431).
• 14: Langford, J., & Beygelzimer, A. (2005). Sensitive error correcting output codes. Proceedings of the Eighteenth Annual Conference on Learning Theory (COLT-2005). To appear.
• 15: Langford, J., & Zadrozny, B. (2003). Reducing T-step reinforcement learning to classification. Preprint at http://hunch.net/~jl/projects/reductions/RL_to_class/colt_submission.ps%.
• 16: Langford, J., & Zadrozny, B. (2005). Estimating class membership probabilities using classifier learners. Proceedings of the Tenth International Workshop on AI and Statistics (AISTATS-2005) (pp. 198--205).
• 17: Satinder Singh , Michael R. James , Matthew R. Rudary, Predictive state representations: a new theory for modeling dynamical systems, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.512-519, July 07-11, 2004, Banff, Canada
• 18: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 19: Watkins, C. (1989). Learning from delayed rewards. Doctoral dissertation, Cambridge University.
• 20: Bianca Zadrozny , John Langford , Naoki Abe, Cost-Sensitive Learning by Cost-Proportionate Example Weighting, Proceedings of the Third IEEE International Conference on Data Mining, p.435, November 19-22, 2003