An analytic solution to discrete Bayesian reinforcement learning

ABSTRACT

Reinforcement learning (RL) was originally proposed as a framework to allow agents to learn in an online fashion as they interact with their environment. Existing RL algorithms come short of achieving this goal because the amount of exploration required is often too costly and/or too time consuming for online learning. As a result, RL is mostly used for offline learning in simulated environments. We propose a new algorithm, called BEETLE, for effective online learning that is computationally efficient while minimizing the amount of exploration. We take a Bayesian model-based approach, framing RL as a partially observable Markov decision process. Our two main contributions are the analytical derivation that the optimal value function is the upper envelope of a set of multivariate polynomials, and an efficient point-based value iteration algorithm that exploits this simple parameterization.

REFERENCES

• 1: Boger, J., Poupart, P., Hoey, J., Boutilier, C., Fernie, G., & Mihailidis, A. (2005). A decision-theoretic approach to task assistance for persons with dementia. IJCAI (pp. 1293--1299).
• 2: Crites, R. H., & Barto, A. G. (1996). Improving elevator performance using reinforcement learning. NIPS (pp. 1017--1023).
• 3: Dearden, R., Friedman, N., & Andre, D. (1999). Model based Bayesian exploration. UAI (pp. 150--159).
• 4: Richard Dearden , Nir Friedman , Stuart Russell, Bayesian Q-learning, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.761-768, July 1998, Madison, Wisconsin, United States
• 5: DeGroot, M. H. (1970). Optimal statistical decisions. New York: McGraw-Hill.
• 6: Michael O'Gordon Duff , Andrew Barto, Optimal learning: computational procedures for bayes-adaptive markov decision processes, 2002
• 7: Duff, M. (2003). Design for an optimal probe. ICML (pp. 131--138).
• 8: Leslie Pack Kaelbling, Learning in embedded systems, MIT Press, Cambridge, MA, 1993
• 9: Nicolas Meuleau , Paul Bourgine, Exploration of Multi-State Environments: Local Measures and Back-Propagation of Uncertainty, Machine Learning, v.35 n.2, p.117-154, May 1999 [doi>10.1023/A:1007541107674]
• 10: Ng, A., Kim, H. J., Jordan, M., & Sastry, S. (2003). Autonomous helicopter flight via reinforcement learning. NIPS.
• 11: Porta, J. M., Spaan, M. T., & Vlassis, N. (2005). Robot planning in partially observable continuous domains. Proc. Robotics: Science and Systems.
• 12: Smallwood, R. D., & Sondik, E. J. (1973). The optimal control of partially observable Markov processes over a finite horizon. Operations Research, 21, 1071--1088.
• 13: Spaan, M. T. J., & Vlassis, N. (2005). Perseus: Randomized point-based value iteration for POMDPs. Journal of Artificial Intelligence Research, 24, 195--220.
• 14: Malcolm J. A. Strens, A Bayesian Framework for Reinforcement Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.943-950, June 29-July 02, 2000
• 15: Richard S. Sutton, Reinforcement Learning, Kluwer Academic Publishers, Norwell, MA, 1992
• 16: Gerald Tesauro, Temporal difference learning and TD-Gammon, Communications of the ACM, v.38 n.3, p.58-68, March 1995 [doi>10.1145/203330.203343]
• 17: Tao Wang , Daniel Lizotte , Michael Bowling , Dale Schuurmans, Bayesian sparse sampling for on-line reward optimization, Proceedings of the 22nd international conference on Machine learning, p.956-963, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102472]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms, Theory