Predictive representations for policy gradient in POMDPs

ABSTRACT

We consider the problem of estimating the policy gradient in Partially Observable Markov Decision Processes (POMDPs) with a special class of policies that are based on Predictive State Representations (PSRs). We compare PSR policies to Finite-State Controllers (FSCs), which are considered as a standard model for policy gradient methods in POMDPs. We present a general Actor-Critic algorithm for learning both FSCs and PSR policies. The critic part computes a value function that has as variables the parameters of the policy. These latter parameters are gradually updated to maximize the value function. We show that the value function is polynomial for both FSCs and PSR policies, with a potentially smaller degree in the case of PSR policies. Therefore, the value function of a PSR policy can have less local optima than the equivalent FSC, and consequently, the gradient algorithm is more likely to converge to a global optimal solution.

REFERENCES

• 1: Douglas Aberdeen , Jonathan Baxter, Scalable Internal-State Policy-Gradient Methods for POMDPs, Proceedings of the Nineteenth International Conference on Machine Learning, p.3-10, July 08-12, 2002
• 2: Aberdeen, D., Buffet, O., & Thomas, O. (2007). Policy-Gradients for PSRs and POMDPs. Proc. 11th Int. Conf. Artificial Intelligence and Statistics.
• 3: Jonathan Baxter , Peter L. Bartlett, Reinforcement Learning in POMDP's via Direct Gradient Ascent, Proceedings of the Seventeenth International Conference on Machine Learning, p.41-48, June 29-July 02, 2000
• 4: Casella, G., & Robert, C. P. (1996). Raoblackwellisation of Sampling Schemes. Biometrika, 15, 229--235.
• 5: Littman, M., Sutton, R., & Singh, S. (2002). Predictive Representations of State. Advances in Neural Information Processing Systems 14 (pp. 1555--1561).
• 6: Takaki Makino , Toshihisa Takagi, On-line discovery of temporal-difference networks, Proceedings of the 25th international conference on Machine learning, p.632-639, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390236]
• 7: Meuleau, N., Peshkin, L., Kim, K., & Kaelbling, L. (1999). Learning Finite-State Controllers for Partially Observable Environments. Uncertainty in Artificial Intelligence: Proc. 15th Conf. (pp. 427--436).
• 8: Leonid M. Peshkin , Leslie Kaelbling, Reinforcement learning by policy search, Brown University, Providence, RI, 2002
• 9: Peters, J., & Schaal, S. (2006). Policy Gradient Methods for Robotics. Proc. IEEE Int. Conf. Intelligent Robotics Systems (pp. 2219--2225).
• 10: Christian Robert Shelton , Tomaso Poggio, Importance sampling for reinforcement learning with multiple objectives, Massachusetts Institute of Technology, 2001
• 11: Sutton, R. S., Mcallester, D., Singh, S., & Mansour, Y. (2000). Policy Gradient Methods for Reinforcement Learning with Function Approximation. Advances in Neural Information Processing Systems 12 (pp. 1057--1063).
• 12: Eric Wiewiora, Learning predictive representations from a history, Proceedings of the 22nd international conference on Machine learning, p.964-971, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102473]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory