Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes

Abstract

We study an approach to policy selection for large relational Markov Decision Processes (MDPs). We consider a variant of approximate policy iteration (API) that replaces the usual value-function learning step with a learning step in policy space. This is advantageous in domains where good policies are easier to represent and learn than the corresponding value functions, which is often the case for the relational MDPs we are interested in. In order to apply API to such problems, we introduce a relational policy language and corresponding learner. In addition, we introduce a new bootstrapping routine for goal-based planning domains, based on random walks. Such bootstrapping is necessary for many large relational MDPs, where reward is extremely sparse, as API is ineffective in such domains when initialized with an uninformed policy. Our experiments show that the resulting system is able to find good policies for a number of classical planning domains and their stochastic variants by solving them as extremely large relational MDPs. The experiments also point to some limitations of our approach, suggesting future work.

References in corpus (4)

• The FF Planning System: Fast Plan Generation Through Heuristic Search
• On-line Policy Improvement using Monte-Carlo Search
• Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes
• Inductive Policy Selection for First-Order MDPs

Cited by in corpus (17)

• Planning with Noisy Probabilistic Relational Rules
• Optimal Stochastic Dynamic Scheduling for Managing Community Recovery from Natural Hazards
• Plan-based Policies for Efficient Multiple Battery Load Management
• Rollout Sampling Approximate Policy Iteration
• First Order Decision Diagrams for Relational MDPs
• Structure in Deep Reinforcement Learning: A Survey and Open Problems
• Engineering a Conformant Probabilistic Planner
• Solving Markov decision processes for network-level post-hazard recovery via simulation optimization and rollout
• Output Space Search for Structured Prediction
• Learning General Policies from Small Examples Without Supervision
• Symbolic Network: Generalized Neural Policies for Relational MDPs
• Fitted Q-Learning for Relational Domains
• Automatic Induction of Bellman-Error Features for Probabilistic Planning
• Approximate Policy Iteration for Budgeted Semantic Video Segmentation
• Decision Automation for Electric Power Network Recovery
• Approximate Modified Policy Iteration
• Dynamic probabilistic logic models for effective abstractions in RL