Non-parametric policy gradients: a unified treatment of propositional and relational domains

ABSTRACT

Policy gradient approaches are a powerful instrument for learning how to interact with the environment. Existing approaches have focused on propositional and continuous domains only. Without extensive feature engineering, it is difficult - if not impossible - to apply them within structured domains, in which e.g. there is a varying number of objects and relations among them. In this paper, we describe a non-parametric policy gradient approach - called NPPG - that overcomes this limitation. The key idea is to apply Friedmann's gradient boosting: policies are represented as a weighted sum of regression models grown in an stage-wise optimization. Employing off-the-shelf regression learners, NPPG can deal with propositional, continuous, and relational domains in a unified way. Our experimental results show that it can even improve on established results.

REFERENCES

• 1: Aberdeen, D. (2006). Policy-gradient methods for planning. Advances in Neural Information Processing Systems 18 (pp. 9--17).
• 2: J. Andrew Bagnell , Jeff Schneider, Learning decisions: robustness, uncertainty, and approximation, Carnegie Mellon University, Pittsburgh, PA, 2004
• 3: Bagnell, J., & Schneider, J. (2003). Policy search in reproducing kernel hilbert space (Technical Report CMU-RI-TR-03-45). Robotics Institute, Carnegie Mellon University, Pittsburg, Pa, USA.
• 4: Baxter, J., Bartlett, P., & Weaver, L. (2001). Experiments with infinite-horizon, policy-gradient estimation. Journal of Arificial Intellifence Research (JAIR), 15, 351--381.
• 5: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 6: Hendrik Blockeel , Luc De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence, v.101 n.1-2, p.285-297, May 1998 [doi>10.1016/S0004-3702(98)00034-4]
• 7: Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and regression trees. Belmont: Wadsworth.
• 8: Chapman, D., & Kaelbling, L. P. (1991). Input generalization in delayed reinforcement learning: An algorithm and performance comparisions. Proceedings of the 12th International Joint Conference on Artificial Intelligence (pp. 726--731) Sydney, Australia.
• 9: Thomas G. Dietterich , Adam Ashenfelter , Yaroslav Bulatov, Training conditional random fields via gradient tree boosting, Proceedings of the twenty-first international conference on Machine learning, p.28, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015428]
• 10: Kurt Driessens , Sašo Džeroski, Combining model-based and instance-based learning for first order regression, Proceedings of the 22nd international conference on Machine learning, p.193-200, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102376]
• 11: Kurt Driessens , Sašo Džeroski, Integrating Guidance into Relational Reinforcement Learning, Machine Learning, v.57 n.3, p.271-304, December 2004 [doi>10.1023/B:MACH.0000039779.47329.3a]
• 12: Driessens, K., & Ramon, J. (2003). Relational instance based regression for relational reinforcement learning. Proceedings of the 20th International Conference on Machine Learning (pp. 123--130) Washington, DC, USA.
• 13: Kurt Driessens , Jan Ramon , Hendrik Blockeel, Speeding Up Relational Reinforcement Learning through the Use of an Incremental First Order Decision Tree Learner, Proceedings of the 12th European Conference on Machine Learning, p.97-108, September 05-07, 2001
• 14: Sošo Džeroski , Luc De Raedt , Kurt Driessens, Relational reinforcement learning, Machine Learning, v.43 n.1/2, p.7-52, April/May 2001 [doi>10.1023/A:1007694015589]
• 15: Damien Ernst , Pierre Geurts , Louis Wehenkel, Tree-Based Batch Mode Reinforcement Learning, The Journal of Machine Learning Research, 6, p.503-556, 12/1/2005
• 16: Friedman, J. (2001). Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29, 1189--1232.
• 17: Gärtner, T., Driessens, K., & Ramon, J. (2003). Graph kernels and gaussian processes for relational reinforcement learning. International Conference on Inductive Logic Programming (pp. 146--163) Szeged, Hungary.
• 18: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 19: Carlos Guestrin , Michail G. Lagoudakis , Ronald Parr, Coordinated Reinforcement Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.227-234, July 08-12, 2002
• 20: Gutmann, B., & Kersting, K. (2006). TildeCRF: Conditional random fields for logical sequences. Proceedings of the 17th European Conference on Machine Learning (pp. 174--185). Berlin, Germany.
• 21: Kristian Kersting , Martijn Van Otterlo , Luc De Raedt, Bellman goes relational, Proceedings of the twenty-first international conference on Machine learning, p.59, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015401]
• 22: Vijay R. Konda , John N. Tsitsiklis, On Actor-Critic Algorithms, SIAM Journal on Control and Optimization, v.42 n.4, p.1143-1166, 2003 [doi>10.1137/S0363012901385691]
• 23: Andrew Kachites Mccallum , Dana Ballard, Reinforcement learning with selective perception and hidden state, The University of Rochester, 1996
• 24: Rémi Munos, Policy Gradient in Continuous Time, The Journal of Machine Learning Research, 7, p.771-791, 12/1/2006
• 25: Riedmiller, M. (2005). Neural fitted Q iteration - First experiences with a data efficient neural reinforcement learning method. Proceedings of the 16th European Conference on Machine Learning (pp. 317--328) Porto, Portugal.
• 26: Sanner, S., & Boutilier, C. (2005). Approximate linear programming for first-order MDPs. Proceedings of the 21st conference on Uncertainty in AI (UAI) (pp. 509--517) Edinburgh, Scotland.
• 27: John Slaney , Sylvie Thiébaux, Blocks World revisited, Artificial Intelligence, v.125 n.1-2, p.119-153, Jan. 2001 [doi>10.1016/S0004-3702(00)00079-5]
• 28: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 29: 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). MIT Press.
• 30: William T. B. Uther , Manuela M. Veloso, Tree based discretization for continuous state space reinforcement learning, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.769-774, July 1998, Madison, Wisconsin, United States
• 31: Wang, C., Joshi, S., & Khardon, R. (2007). First order decision diagrams for relational mdps. Proceedings of the 20th International Joint Conference on Artificial Intelligence (pp. 1095--1100). Hyderabad, India: AAAI press.
• 32: Wang, X., & Dietterich, T. (2003). Model-based policy gradient reinforcement learning. Proceedings of the 20th International Conference on Machine Learning (pp. 776--783) Washington, DC, USA.
• 33: Ronald J. Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning, Machine Learning, v.8 n.3-4, p.229-256, May 1992 [doi>10.1007/BF00992696]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Nonparametric statistics

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

  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