A Laplacian Framework for Option Discovery in Reinforcement Learning

By Marlos C. Machado, Marc G. Bellemare, Michael H. Bowling. 2017

292 citations recorded by the source corpus.

Representation learning and option discovery are two of the biggest challenges in reinforcement learning (RL). Proto-value functions (PVFs) are a well-known approach for representation learning in MDPs. In this paper we address the option discovery problem by showing how PVFs implicitly define options. We do it by introducing eigenpurposes, intrinsic reward functions derived from the learned representations. The options discovered from eigenpurposes traverse the principal directions of the state space. They are useful for multiple tasks because they are discovered without taking the environment's rewards into consideration. Moreover, different options act at different time scales, making them helpful for exploration. We demonstrate features of eigenpurposes in traditional tabular domains as well as in Atari 2600 games.

Subfields: Artificial Intelligence, Molecular Biology, Reinforcement 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 Molecular Biology

In Reinforcement Learning

Citations in the corpus

Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents (2017, background): “The community is just beginning to investigate exploration strategies in model-free settings when function approximation is required (e.g., Bellemare et al., 2016b; Osband et al., 2016; Ostrovski et al., 2017; Machado et al., 2017; Martin et al., 2017; Vezhnevets et al., 2017).”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “While much of the work on learning options has focused on single task learning (Bacon, Harb, and Precup, 2017; Machado, Bellemare, and Bowling, 2017a; Machado, Rosenbaum, Guo, Liu, Tesauro, and Campbell, 2017b; Harb, Bacon, Klissarov, and Precup, 2018; Khetarpal, Klissarov, Chevalier-Boisvert,…”
Learning to Play with Intrinsically-Motivated Self-Aware Agents (2018, background): “Intrinsic and extrinsic reward structures have been used to learn generic “skills” for a variety of tasks [6, 28, 41].”
Curiosity Driven Exploration of Learned Disentangled Goal Spaces (2018, background): “More involved methods that value states or actions in terms of novelty, information gain, or prediction errors are limited the presence of “distractors” that cannot be controlled [9, 10, 11, 12, 13].”
Learning Plannable Representations with Causal InfoGAN (2018, methodology): “For continuous observations, SC requires a distance function to build a connectivity graph, and previous studies [26, 40, 25] relied on the Euclidean distance, using either nearest neighbor to connect nodes, or exponentiated-distance weighted edges.”
Options of Interest: Temporal Abstraction with Interest Functions (2020, background): “Constructing such temporal abstractions automatically from data has also been tackled extensively, and with some success [16, 23, 18, 21, 3, 20].”
Spectral Inference Networks: Unifying Deep and Spectral Learning (2018, methodology): “The use of PVFs for discovering subgoals in reinforcement learning has been investigated in (Machado et al., 2017) and combined with function approximation in (Machado et al., 2018), though using a less rigorous approach to eigenfunction approximation than SpIN.”
A Meta-MDP Approach to Exploration for Lifelong Reinforcement Learning (2019, background): “not been frequently visited, [13, 22], or use approximations of a state-transition graph to exploit structural patterns, [11, 12].”
A Geometric Perspective on Optimal Representations for Reinforcement Learning (2019, methodology): “We perform all of our experiments within the four-room domain (Sutton et al., 1999), one of the most commonly used environment for studying representation learning for RL (see e.g. Solway et al., 2014; Machado et al., 2017).”
Discovering Options for Exploration by Minimizing Cover Time (2019, methodology): “Deﬁnition 1 (option): An option o is deﬁned by a triple: ( I , π, β ) where: • I ⊆ S is a set of states where the option can initiate, • π : S → Pr( A ) is a policy, Many previous approaches propose methods to generate options based on heuristics and demonstrate the effectiveness in experimental eva”
Learning Structures: Predictive Representations, Replay, and Generalization (2020, methodology): “When computing the proto-value function, an environment is decomposed into basis functions of successor features and options, the linear combinations of which could compute any given task’s value function and hence serve as intrinsic motivation [79 ,84].”
Reinforcement Learning with Competitive Ensembles of Information-Constrained Primitives (2019, methodology): “Eigen-options [21] use the eigenvalues of the Laplacian (for the transition graph induced by the MDP) to derive an intrinsic reward for discovering options as well as learning an intra-option policy.”
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].”
An Introduction to Deep Reinforcement Learning (2018, unknown): “games or different variants of the same game, they are also a good testbed for evaluating generalization of reinforcement learning algorithms (Machado et al., 2017b), multi-task learning (Parisotto et al., 2015) and for transfer learning (Rusu et al., 2015).”
Eigenoption Discovery through the Deep Successor Representation (2017, methodology): “Our ﬁrst experiment evaluates the impact of estimating the SR from samples instead of assuming the DIF model was given in the form of the normalized Laplacian.”
InfoBot: Transfer and Exploration via the Information Bottleneck (2019, background): “…one that lies on a wide variety of rewarding trajectories (McGovern and Barto, 2001; Stolle and Precup, 2002) or one that otherwise serves to separate regions of state space in a graph-theoretic sense (Menache et al., 2002; ¸Sim¸sek et al., 2005; Kazemitabar and Beigy, 2009; Machado et al., 2017).”
The Laplacian in RL: Learning Representations with Efficient Approximations (2018, methodology): “C Derivation of (5) (Switching the notation u and v in the second term gives the same quantity as the ﬁrst term) D Additional results and experiment details et al., 2017a) or a representation learned by a forward prediction model (Machado et al., 2017b).”
GEP-PG: Decoupling Exploration and Exploitation in Deep Reinforcement Learning Algorithms (2017, unknown): “In deep RL, this is achieved using count-based exploration (Bellemare et al., 2016), as well as various forms of intrinsic rewards and exploration bonuses (Houthooft et al., 2016a;b; Pathak et al., 2017) and methods for option discovery (Machado et al., 2017a).”