Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems

By Ronald E. Parr. 1998

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Graying the black box: Understanding DQNs (2016, background): “Given a good representation of the states, varying levels of convergence guarantees has been promised (Dean & Lin, 1995; Parr, 1998; Hauskrecht et al., 1998; Dietterich, 2000).”
Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition (1999, background): “Parr (1998b) proves that his HAMQ learning algorithm converges with probability 1 to a hierarchically optimal policy. Similarly, given a xed set of options, Sutton, Precup, and Singh (1998) prove that their SMDP learning algorithm converges to a hierarchically optimal value function.”
Hierarchical Solution of Markov Decision Processes using Macro-actions (1998, background): “Two limitations of this model are then addressed.”
Transfer in variable-reward hierarchical reinforcement learning (2008, background): “The work by Parr (1998) decomposes the problem of solving a big MDP into one of solving smaller weakly-coupled sub-MDPs.”
Generalizing plans to new environments in relational MDPs (2003, background): “Others [12; 8; 4] have focused on reusing solutions from isomorphic regions of state space.”
Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks (2011, unknown): “Parr (1998)develops algorithms to control the caching of policies that can be used in multiple tasks.”
Decision-Theoretic Planning: Structural Assumptions and Computational Leverage (1999, background): “The issue of macro generation|constructing a set of macros guaranteed to provide the exibility to select close to optimalglobal behavior|is addressed in (Hauskrecht et al., 1998; Parr, 1998).”
Visualizing Dynamics: from t-SNE to SEMI-MDPs (2016, methodology): “Good temporal representation of the data can speed up the prerformence of Reinforcement Learning (RL) algorithms (Dietterich, 2000; Dean & Lin, 1995; Parr, 1998; Hauskrecht et al., 1998), and indeed there is a growing interest in developing hierarchical DRL algorithms.”