Identifying useful subgoals in reinforcement learning by local graph partitioning

By Özgür Simsek, Alicia P. Wolfe, Andrew Barto. 2005

305 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning, Graph Learning

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Reinforcement Learning

In Graph Learning

Citations in the corpus

Learning Parameterized Skills (2012, background): “mination conditions, for instance, might be determined by identifying possibly useful subgoal states [47, 14, 16, 38] that an agent may want to reach.”
Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation (2016, background): “[24] provide a graph partitioning approach to subgoal identification.”
Search on the Replay Buffer: Bridging Planning and Reinforcement Learning (2019, background): “Another class of algorithms (Drummond, 2002; Fox et al., 2017; Şimşek et al., 2005) focus solely on automatically discovering these skills or subgoals.”
Flexible Option Learning (2021, background): “This can be done in various ways such as identifying bottleneck states [McGovern and Barto, 2001, Şimşek et al., 2005, Menache et al., 2002, Machado et al., 2017] or through feudal RL [Dayan and Hinton, 1993, Vezhnevets et al., 2017, Nachum et al., 2018].”
Automatic Construction of Temporally Extended Actions for MDPs Using Bisimulation Metrics (2011, methodology): “Subgoals can be identified based on a learned model of the environment, using graph theoretic techniques [Mannor et al., 2004; Šimšek et al., 2005], or based on trajectories through the system, without learning a model [McGovern and Barto, 2001; Stolle and Precup, 2002].”
Probabilistic policy reuse in a reinforcement learning agent (2006, background): “Some related algorithms are SKILL [17], which discovers partially defined policies that arise in the context of multiple tasks in the same domain, and L-Cut, which discovers subgoals and corresponding sub-policies [12].”
Efficient skill learning using abstraction selection (2009, methodology): “Previous research has selected goal states by a variety of methods, for example variable change frequency [Hengst, 2002] and local graph partitioning [Şimşek et al., 2005].”
Skill Discovery in Continuous Reinforcement Learning Domains using Skill Chaining (2009, methodology): “Graph-based methods [9, 10, 11] build a state graph and use its properties (e.”
Building Portable Options: Skill Transfer in Reinforcement Learning (2007, background): “, variable change frequency [Hengst, 2002], local graph partitioning [Şimşek et al., 2005] and salience [Singh et al.”
Learning Multi-Level Hierarchies with Hindsight (2017, background): “Building agents that can learn hierarchical policies is a longstanding problem in Reinforcement Learning (Sutton et al., 1999; Dietterich, 2000; McGovern & Barto, 2001; Kulkarni et al., 2016; Menache et al., 2002; Şimşek et al., 2005; Bakker & Schmidhuber, 2004; Wiering & Schmidhuber, 1997).”
Discovering Options for Exploration by Minimizing Cover Time (2019, methodology): “Menache et al. (2002) used a learned model of the environment to run a Max-Flow/Min-Cut algorithm to the state-space graph to identify bottleneck states whereas Simsek et al. (2005) proposed to apply spectral cut to identify bottlenecks.”
Hierarchically organized behavior and its neural foundations: A reinforcement-learning perspective (2008, methodology): “Graph partitioning methods are then used to identify states that constitute bottlenecks or access points within the graph, which are then designated as option subgoals (Mannor, Menache, Hoze, & Klein, 2004; Menache, Mannor, & Shimkin, 2002; Simsek, Wolfe, & Barto, 2005; see also Hengst, 2002; Jons”
A Multitask Representation Using Reusable Local Policy Templates (2012, background): “The question of learning options remains in general an open question, but has been approached from many different angles (S¸ims¸ek, Wolfe, and Barto 2005; Pickett and Barto 2002).”
Transfer in Reinforcement Learning: A Framework and a Survey (2012, background): “…traversed by the optimal policy of the source task and that can be considered as critical to solve tasks in the same MDP. Metrics defined for graph partitioning techniques are used in (Menache et al, 2002) and (Simsek et al, 2005) to identify states connecting different regions of the state space.”