Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems

Abstract

This paper presents two new approaches to decomposing and solving large Markov decision problems (MDPs), a partial decoupling method and a complete decoupling method. In these approaches, a large, stochastic decision problem is divided into smaller pieces. The first approach builds a cache of policies for each part of the problem independently, and then combines the pieces in a separate, light-weight step. A second approach also divides the problem into smaller pieces, but information is communicated between the different problem pieces, allowing intelligent decisions to be made about which piece requires the most attention. Both approaches can be used to find optimal policies or approximately optimal policies with provable bounds. These algorithms also provide a framework for the efficient transfer of knowledge across problems that share similar structure.

Appears in Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI1998)

References in corpus (1)

• Hierarchical Solution of Markov Decision Processes using Macro-actions

Cited by in corpus (10)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Graying the black box: Understanding DQNs
• Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks
• Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition
• Probabilistic Hybrid Action Models for Predicting Concurrent Percept-driven Robot Behavior
• Visualizing Dynamics: from t-SNE to SEMI-MDPs
• Restricted Value Iteration: Theory and Algorithms
• Robust Combination of Local Controllers
• Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments
• Deep Reinforcement Learning Discovers Internal Models