A Laplacian Framework for Option Discovery in Reinforcement Learning

Marlos C. Machado; Marc G. Bellemare; Michael Bowling

Source-linked AI summary

A Laplacian Framework for Option Discovery in Reinforcement Learning

Marlos C. Machado, Marc G. Bellemare, Michael Bowling

arXiv:1703.00956v2Mar 2, 2017cs.LGcs.AI

TL;DR

Representation learning and option discovery remain major reinforcement-learning challenges, with PVFs established for representation learning but not yet connected to automatic option discovery. The paper derives intrinsic rewards, called eigenpurposes, from PVFs to define task-independent options, finding that they traverse principal state-space directions and support exploration across time scales. The approach is demonstrated in tabular domains and Atari 2600 games.

Problem
Representation learning and automatic skill discovery are two major reinforcement-learning challenges, while PVFs primarily address representation learning.
Method
The paper derives eigenpurposes as intrinsic rewards from PVF representations and uses their optimal policies as options, with tabular and function-approximation versions.
Results
The discovered options do not necessarily target bottleneck states and can improve exploration when enough options are added, while also supporting reward accumulation across multiple tasks.
Takeaways & Limitations
Task-independent options operating at different time scales and available across the state space can support exploration and be sequenced across tasks.
Takeaways & Limitations
The approach involves a trade-off between reconstructing the adjacency matrix and constructing the incidence matrix, with the preferred choice depending on state connectivity.

Abstract

from arXiv · show

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.

1. Introduction

The paper connects representation learning and option discovery by showing that PVFs implicitly define options through eigenpurposes. These task-independent options support exploration because they operate at different time scales and can be sequenced.

Representation learning and automatic skill discovery are identified as two important challenges in reinforcement learning.
The paper shows how proto-value functions implicitly define options, tying representation learning to option discovery.
Eigenpurposes are intrinsic rewards derived from learned representations that incentivize traversal along principal state-space directions.
The discovered options are task-independent because their eigenpurposes use no information about the environment’s reward structure.
Options operating at different time scales and being easily sequenced can improve exploration, whereas planning-oriented options may hinder random exploration.

2. Background

The background introduces RL as sequential decision-making in MDPs and explains function approximation and temporally extended options. It also presents PVFs as Laplacian-based representations of large-scale temporal properties.

2.1. Reinforcement Learning: In reinforcement learning, agents choose actions that affect subsequent states and rewards while seeking to maximize cumulative reward.
2.1. Reinforcement Learning: An MDP is represented by states, actions, rewards, transition probabilities, and a discount factor.
2.1. Reinforcement Learning: When state-action spaces are too large, action values can be approximated with parameterized linear features.
2.2. Options: Options are temporally extended actions defined by an initiation set, policy, and termination set, generalizing MDPs to semi-Markov decision processes.
2.3. Proto-value Functions: PVFs capture large-scale temporal properties by taking eigenvectors from graph-Laplacian decompositions built from transition or adjacency information.

3. Option Discovery through the Laplacian

The paper turns PVFs into eigenoptions by defining intrinsic eigenpurposes whose optimal policies traverse learned state-space structure. These task-independent options have explicit initiation and termination rules, and finite-state options terminate under discounting γ < 1.

Eigenpurposes: PVFs are interpreted as state-space geometry, and each eigenpurpose converts a learned representation into an intrinsic reward for option discovery.The eigenpurpose gives the agent a discounted intrinsic-reward objective over the representation.
Option construction: The option-learning MDP preserves the original states and transitions, adds a cost-free terminate action, and uses the discount rate to control the option’s timescale.The terminate action returns control to the higher-level policy.
Eigenbehaviors: An eigenbehavior is the policy optimal for an eigenpurpose, and its corresponding eigenoption uses that policy to pursue the purpose.The discovered eigenoption in the 4-room example is derived from the second PVF.
Initiation and termination: Eigenoptions initiate wherever some action can achieve positive intrinsic value and terminate when no action can accumulate further positive intrinsic reward.Termination occurs at a value maximum, or a local maximum when γ < 1; the terminate action is selected when all action values are nonpositive.
Theoretical guarantee: For finite-state MDPs with γ < 1, every eigenoption has a nonempty termination set, and the result applies to both tabular and linear function-approximation settings.The paper also provides an algorithm that does not require knowing the underlying graph.
Empirical examples: The empirical study evaluates eigenoptions in an open room, an I-Maze, and a 4-room domain, with figures showing options from low-frequency eigenvectors.The four smallest eigenvectors are used to depict options in the grid and I-Maze domains.

4. Empirical Evaluation

The empirical evaluation examines eigenoptions in three deterministic gridworlds for discovered purposes, exploration, and reward accumulation. Results show that eigenoptions can improve exploration and learning, although too few options may hurt performance.

Evaluation Setup: The evaluation uses deterministic open-room, I-Maze, and 4-room MDPs to study eigenoption purposes, exploration, and reward accumulation.Agents use primitive movement actions in environments with walls and unchanged states when attempting blocked moves.
Discovered Options: Eigenoptions do not necessarily target bottlenecks: in the 4-room domain, the fifth eigenoption is the first to terminate at a doorway.The framework also discovers behaviors such as walking down corridors and moving to open-room corners.
Exploration: Eigenoptions support exploration across the state space because they are available broadly and operate at different time scales.In the 10 × 10 grid, the fourth eigenoption terminates, on expectation, twice as often as the second.
Exploration: The first added options can hurt exploration, but enough options greatly improve diffusion time relative to primitive-action random walks.Long options bias random exploration toward their trajectories, while eigenoptions operating at different time scales mitigate this effect.
Accumulating Rewards: In most scenarios eigenoptions improve reward-accumulation performance, with the best results obtained using 64 options.Exceptions occur when only a few options are added, while performance remains fairly robust across different option counts.

5. Approximate Option Discovery

The paper develops sample-based eigenoption discovery that avoids explicitly reconstructing the adjacency matrix, extends to linear function approximation, and yields purposeful options in Atari games.

5. Approximate Option Discovery: The approach addresses settings where state spaces are too large for repeated state visits by using sample-based methods and function approximation.The paper presents the method as an asymptotic eigenoption-discovery procedure and extends it to linear function approximation.
5. Approximate Option Discovery: The sample-based algorithm stores unique feature-difference transitions, applies SVD to their incidence matrix, and uses right singular vectors to generate eigenpurposes.In the tabular case, each transition is represented as φ(s′) − φ(s).
5. Approximate Option Discovery: When all tabular transitions are sampled once, the incidence-matrix method discovers the same options as the combinatorial Laplacian.The equivalence follows from T⊤T = 2L, so the right singular vectors correspond to Laplacian eigenvectors.
5. Approximate Option Discovery: For function approximation, duplicate transitions are removed by treating feature-difference vectors as identical exactly when their difference is zero.The authors describe this as a naïve approach and expect more involved methods to perform better.
5. Approximate Option Discovery: In Atari 2600 experiments, the method sampled 25,000 RAM-transition rows and analyzed all 1,024 discovered options rather than assuming the smoothest options were best.Options were greedily approximated with γ = 0 using the emulator’s look-ahead.
5. Approximate Option Discovery: In MONTEZUMA’S REVENGE, discovered options showed intent to reach positions such as staircases, ropes, and doors, resembling handcrafted options.The comparison is reported with respect to options handcrafted by Kulkarni et al. (2016).

6. Related Work

The paper contrasts reward-driven, top-down option discovery with its bottom-up construction of task-independent options from learned representations, relating the approach to exploration and other representation-based methods.

6. Related Work: Many option-discovery methods begin with trajectories leading to informative rewards and refine them into options.These approaches include intrinsic-reward, gradient-based, and probabilistic-inference methods.
6. Related Work: Reward-dependent approaches are difficult to apply in large state spaces with sparse rewards when informative rewards require long or specific action sequences.In that setting, options are equally unlikely to be discovered from primitive actions alone.
6. Related Work: This paper’s bottom-up approach constructs options before informative rewards are observed, making them independent of the agent’s intention and potentially useful across tasks.The options can also support exploration by committing the agent to behavior for an extended period.
6. Related Work: Eigenpurposes encode different rates of change in the agent’s representation, while their options aim to maximize those changes.This connects the method to approaches that learn to control parts of the environment.
6. Related Work: CCSA is identified as the closest approach, but it uses Incremental Slow Feature Analysis rather than PVFs to define intrinsic rewards.The methods also differ in initiation and termination sets and in the objective being maximized.

7. Conclusion

The conclusion presents graph-Laplacian options as representation-informed behaviors that can support exploration and reward accumulation across tasks, while identifying incremental, incomplete-graph, and hierarchical extensions as future work.

7. Conclusion: The approach uses the graph Laplacian and links option discovery directly to proto-value functions.The learned representation identifies meaningful options to seek.
7. Conclusion: Discovered options need not target bottlenecks, and bottleneck options can hinder exploration when added naively to the action set.The conclusion contrasts planning-oriented bottleneck options with options that improve exploration.
7. Conclusion: The discovered options can help agents explore and accumulate reward across multiple tasks.The reported reward accumulation leverages the options’ exploratory properties.
7. Conclusion: Future work includes comparing eigenoptions with SFA, discovering options incrementally with incomplete graphs, and building hierarchies of options.These are presented as open avenues rather than established capabilities of the current method.

Appendix: Supplementary Material

The supplementary material contains omitted proofs, diffusion-time computation details, option examples and comparisons, additional task experiments, and further Atari experimental details.

Appendix: Supplementary Material: The supplement includes supporting lemmas, their proofs, and a more detailed proof of Theorem 3.1.These materials provide formal support omitted from the main text.
Appendix: Supplementary Material: It describes how to compute diffusion time in tabular MDPs.This is listed as an implementation detail in the supplementary contents.
Appendix: Supplementary Material: It provides the bottleneck-state options used in the experiments and performance comparisons against options reaching randomly selected states.These materials support comparisons among alternative option sets.
Appendix: Supplementary Material: The supplement demonstrates eigenoption applicability to multiple tasks with a new experiment set.It also contains further details on the Arcade Learning Environment experimental setting.

A. Lemmas and Proofs

The appendix establishes termination and matrix-norm results for eigenoptions, proves the tabular identity T^⊤T = 2(D − W), and explains diffusion-time computation and bottleneck options.

Matrix Bounds: The induced infinity norm satisfies ||(I − γT)^−1T||∞ ≤ 1/(1 − γ).This bound follows from the transition-operator norm assumptions used in the appendix.
Option Termination: Eigenoptions have nonempty termination sets in finite-state MDPs when γ < 1.The theorem states this for an eigenoption o = ⟨I_o, π_o, T_o⟩.
Tabular Identity: For tabular transitions sampled once, T^⊤T = 2(D − W), twice the graph Laplacian.The proof decomposes T^⊤T into diagonal degree contributions Z = 2D and off-diagonal transition contributions K = −2W.
Diffusion Time: Diffusion time is the expected random-walk steps needed to navigate between pairs of states.It is computed by evaluating goal-conditioned value functions under a uniform random policy and averaging across possible goals.
Bottleneck Options: Bottleneck options move an agent within a room toward the closest doorway.These options target doorway states that connect different regions of the 4-room domain.

D. Comparison to Random Options

The comparison shows that eigenoptions use diffusion information to define option purposes and time scales, whereas random options often fail to improve diffusion and learning performance.

Comparison Setup: Eigenoptions use environmental diffusion information to determine subgoal order and operating time scales.The ordering and time scales of discovered eigenoptions can substantially affect agent performance.
Comparison Setup: Random options terminate in randomly selected states and are evaluated incrementally in the tabular 4-room domain.The random-option procedure was repeated 24 times to vary the order in which options were added.
Diffusion Time: Most random-option sequences increase diffusion time by several orders of magnitude before the option set nearly connects the state graph.The diffusion-time plot uses a logarithmic y-axis, and eigenoptions reduce diffusion time more effectively than random options.
Learning Performance: No individual random-option run is competitive with eigenoptions in the reported learning curves.With fewer random options, performance variance is even larger and depends on whether an option terminates near the goal.

D. Empirical Evaluation of the Agent’s Performance in Multiple Tasks

The multi-task evaluation tests different start and goal states in the 4-room domain and finds eigenoptions robust to start-goal reversal, generally outperforming primitive actions and competing with bottleneck options according to goal location.

Experimental Design: The evaluation compares eigenoptions, bottleneck options, and primitive actions across different starting and goal states.Agents learn primitive-action policies with Q-Learning while using the discovered options as augmentations.
Eigenoptions Across Tasks: Switching the starting and goal positions has no effect on the performance of the eigenoption algorithm.The reported final performance averages 100 trials after a predetermined number of episodes.
Eigenoptions Across Tasks: Eigenoption-augmented agents outperform primitive-action agents in almost all tested settings.The evaluation uses 64 eigenoptions, consisting of 32 options and their negations.
Comparison with Bottleneck Options: Eigenoptions outperform doorway-directed bottleneck options when goals are far from doorways, while bottleneck options are more competitive for nearby goals.The authors note that 64 eigenoptions may not encode every option needed to reach a specific state-space region.

E. Experimental Setup in the Arcade Learning Environment

The Arcade Learning Environment experiments evaluate eigenoptions in Atari games using predefined starts, sampled transitions, and linear function approximation, including an additional MS. PAC-MAN evaluation.

Atari Data Collection: Each Atari game uses six predefined starting states, with random-action trajectories collected from each start until termination.Transitions leading to the starts and those generated by random actions are stored for option discovery.
Atari Data Collection: Agents play rounds of six episodes until observing at least 25,000 new transitions.The final SVD incidence matrix contains 25,000 uniformly sampled transition rows, using deterministic ALE settings and frame skip 1.
Game Evaluations: MS. PAC-MAN extends the sample-based linear-function-approximation evaluation beyond FREEWAY and MONTEZUMA’S REVENGE.The game requires maze navigation, pellet collection, and ghost avoidance, with intended screen positions serving as navigation targets.
Game Evaluations: The reported MS. PAC-MAN results are similar to those previously discussed for FREEWAY and MONTEZUMA’S REVENGE.The experimental figures include options in MS. PAC-MAN and performance comparisons across eigenoptions, bottleneck options, and primitive actions.