PaperlayerView exact revision on arXiv

Source-linked AI summary

Eigenoption Discovery through the Deep Successor Representation

Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, Murray Campbell

arXiv:1710.11089v3cs.LGcs.AI

TL;DR

Autonomous discovery of effective options remains difficult, especially with stochastic transitions and without handcrafted features. The paper uses the successor representation and a neural network learned from raw pixels to discover eigenoptions, with tabular and Atari evaluations providing evidence of applicability. The approach also addresses limitations of prior methods, including dependence on symmetric transitions and handcrafted representations.

  • Problem

    Option discovery remains an open problem, while existing eigenoption methods do not naturally support stochastic transitions or representation learning without handcrafted features.

  • Method

    The algorithm estimates diffusive information flow with the successor representation and learns nonlinear state representations from raw pixels to extract eigenoptions.

  • Results

    The method was evaluated in tabular domains and Atari 2600 games, with the Atari experiments providing promising evidence of applicability from raw pixels.

  • Takeaways & Limitations

    Using the successor representation removes several prior restrictions, including the need for symmetric transition matrices and handcrafted feature representations.

  • Takeaways & Limitations

    The paper identifies eigenoption compositionality, transfer between similar environments, and reward accumulation as future investigations rather than established capabilities.

Abstract

from arXiv · show

Options in reinforcement learning allow agents to hierarchically decompose a task into subtasks, having the potential to speed up learning and planning. However, autonomously learning effective sets of options is still a major challenge in the field. In this paper we focus on the recently introduced idea of using representation learning methods to guide the option discovery process. Specifically, we look at eigenoptions, options obtained from representations that encode diffusive information flow in the environment. We extend the existing algorithms for eigenoption discovery to settings with stochastic transitions and in which handcrafted features are not available. We propose an algorithm that discovers eigenoptions while learning non-linear state representations from raw pixels. It exploits recent successes in the deep reinforcement learning literature and the equivalence between proto-value functions and the successor representation. We use traditional tabular domains to provide intuition about our approach and Atari 2600 games to demonstrate its potential.

1 INTRODUCTION

Option discovery asks how agents can autonomously identify useful temporally extended actions. This paper develops eigenoption discovery for stochastic environments and learned representations, then evaluates it in tabular domains and Atari 2600 games.

  • Options represent temporally extended courses of action and can speed learning and planning when appropriately defined.
  • Autonomously identifying good options remains an open problem known as option discovery.
  • Eigenoptions traverse directions of a latent environment representation that encodes diffusive information flow.
  • The proposed algorithm learns representations while discovering eigenoptions, using the equivalence between proto-value functions and the successor representation.
  • The evaluation covers a tabular domain for intuition and comparison, plus Atari 2600 games using representations learned from raw pixels.

2 BACKGROUND

The background introduces options, eigenoptions, proto-value functions, and the successor representation as tools for representing environment structure and discovering temporally extended behavior.

  • Options: Options are temporally extended actions specified by an initiation set, policy, and termination set.
  • Eigenoptions: Eigenoptions maximize intrinsic eigenpurposes derived from eigenvectors of a representation of diffusive information flow.
  • Proto-value functions: In tabular settings, the combinatorial graph Laplacian encodes environment connectivity, and its eigenvectors are proto-value functions.
  • Proto-value functions: The Laplacian approach does not naturally handle stochastic or unidirectional transitions because its weight matrix is generally symmetric.
  • Successor representation: The successor representation defines state similarity through expected future occupancy under a policy, capturing temporal rather than purely Euclidean proximity.
  • Successor representation: Temporal-difference samples estimate the successor representation, which converges to Ψπ = (I−γTπ)^−1 and decomposes value into successor representation times immediate reward.

3 EIGENOPTION DISCOVERY

The paper replaces graph-based eigenoption discovery with successor-representation methods that handle stochastic transitions and learned representations, including from raw pixels. Eigenpurposes are extracted from SR eigenvectors, then used to define eigenoption learning problems.

  • Motivation: Existing eigenoption methods struggle with stochastic environments, non-enumerated states, and representation learning during DIF-model estimation.Previous approaches either rely on enumerated transitions or require a fixed feature representation.
  • Successor-representation approach: The proposed algorithm estimates diffusive information flow through the successor representation, replacing the need to know the combinatorial Laplacian.This relies on the equivalence between proto-value functions and successor representations.
  • Eigenoption construction: Eigenpurposes are obtained from eigenvectors of the learned representation and define intrinsic rewards that eigenoption policies maximize.The general procedure first learns a representation of diffusive information flow, then extracts eigenpurposes and learns options for them.
  • Successor-representation approach: Using the SR naturally accommodates stochastic transitions and policies, has sample-independent memory cost, and does not require symmetric transitions.These properties address limitations of graph constructions based on symmetric adjacency matrices.
  • Function approximation: For raw-pixel inputs, a neural network learns successor features of a lower-dimensional representation and uses reconstruction as an auxiliary task.The reconstruction module helps avoid the zero fixed point of the successor-feature loss and encourages representations sensitive to controllable pixels.
  • Function approximation: The learned network outputs successor features, which are collected under a uniform random policy to form a matrix whose right eigenvectors define eigenpurposes.The resulting eigenpurposes are then used in the unchanged eigenoption-learning step.

4 EXPERIMENTS

The experiments evaluate SR-based eigenoptions in tabular environments and Atari games. They show reduced diffusion time, improved tabular control, and purposeful options learned from raw pixels, while also exposing limits from myopic option execution.

  • 4.1 TABULAR CASE: The rooms-domain experiments compare SR-derived eigenvectors and eigenoptions with those obtained from the normalized Laplacian and PVFs.The SR was learned from 1,000 uniform-random episodes of 100 steps using α=0.1 and γ=0.9.
  • 4.1 TABULAR CASE: SR-derived eigenoptions preserve exploration benefits, reducing diffusion time relative to uniform random navigation despite estimation differences.The comparison uses diffusion time, defined as expected decisions to navigate between two randomly chosen states under a uniform random policy.
  • 4.1 TABULAR CASE: The SR implicitly models self-loops near walls, likely explaining its diffusion-time gap from PVF-based eigenoptions.The agent observes no movement after actions blocked by walls, which the SR incorporates as self-loops.
  • 4.1 TABULAR CASE: Eigenoptions improved control performance over primitive-action Q-learning and remained useful without highly accurate SR estimates.Results averaged 24 independent SR-learning runs, each paired with 100 Q-learning evaluations; options were extracted after 100 episodes.
  • 4.2 ATARI 2600: The Atari options were limited by greedy one-step execution, which likely prevented delayed-reward behavior and contributed to failure in FREEWAY.The method used one-step lookahead because of computational constraints, effectively corresponding to γ=0 for option execution.
  • 4.2 ATARI 2600: In three out of four Atari games, raw-pixel training discovered options that drove the avatar toward corners or other relevant state-space regions.BANK HEIST, MONTEZUMA’S REVENGE, and MS. PAC-MAN showed these behaviors; MONTEZUMA’S REVENGE options reached states considered good subgoals.
  • 4.2 ATARI 2600: The algorithm learned meaningful screen features directly from raw pixels and discovered eigenoptions qualitatively similar to those using RAM-state features.Unlike RAM-based methods, it had to identify relevant parts of the screen implicitly.

5 RELATED WORK

The related-work discussion positions the method between prior latent-representation approaches and bottleneck-based option discovery. Its distinctions include learned nonlinear representations and different initiation and termination sets.

  • 5 RELATED WORK: The proposed network predicts future observations and learns representations sensitive to controllable screen features, rather than using a reward model or autoencoder.This contingency-aware representation is used to estimate the successor representation for option discovery.
  • 5 RELATED WORK: Unlike Vezhnevets et al., the method explicitly constructs options with initiation and termination sets instead of only learning an end-to-end hierarchy.The discussion also contrasts the method with Machado et al.’s linear-function-approximation setting.
  • 5 RELATED WORK: Unlike bottleneck-state approaches, the discovered options are not defined as searches for bottleneck states.The paper distinguishes its option-definition choices from those of prior bottleneck-oriented methods.

6 CONCLUSION

The paper introduces SR-based eigenoption discovery that addresses stochastic transitions, nonsymmetric dynamics, incremental estimation, and the absence of handcrafted features. It identifies transfer, compositionality, and reward accumulation as future directions.

  • 6 CONCLUSION: The algorithm uses the successor representation to estimate diffusive information flow through the equivalence between PVFs and the SR.A neural network estimates the SR when handcrafted feature representations are unavailable.
  • 6 CONCLUSION: The framework supports increasingly accurate constant-cost updates, stochastic MDPs, nonsymmetric transition matrices, and learned rather than handcrafted representations.The first three properties come from replacing PVFs with the SR; the learned-representation property comes from neural-network SR estimation.
  • 6 CONCLUSION: Future work should evaluate eigenoption compositionality, transfer across similar environments, and using eigenoptions for reward accumulation rather than exploration.The paper specifically mentions different modes of Atari 2600 games as a possible transfer setting.

APPENDIX: SUPPLEMENTARY MATERIAL

The supplementary material adds proof details and empirical analyses of SR-learning duration, eigenvector quality, eigenoptions, and the auxiliary reconstruction module.

  • APPENDIX: SUPPLEMENTARY MATERIAL: The appendix contains a more detailed proof of the paper’s theorem.
  • APPENDIX: SUPPLEMENTARY MATERIAL: It evaluates how the number of episodes used to learn the successor representation affects eigenvectors and their corresponding eigenoptions.
  • APPENDIX: SUPPLEMENTARY MATERIAL: It evaluates the reconstruction module, an auxiliary task that learns the latent representation used to estimate the successor representation.

A MORE DETAILED PROOF OF THE THEOREM IN THE MAIN PAPER

The theorem relates eigenvalues and eigenvectors of the successor representation to those of the normalized Laplacian under a uniform random policy. The proof uses the successor representation’s convergence to (I −γT)−1.

  • Theorem: The theorem states a correspondence between successor-representation and normalized-Laplacian eigenvalues.Both matrices are obtained under a uniform random policy.
  • Theorem: The corresponding eigenvectors are paired in reversed order, with i + j = n + 1.Here, n is the total number of rows and columns of T.
  • Proof: The proof starts from an eigenvalue-eigenvector pair of the successor representation.It denotes the pair by λ_i and e_i.
  • Proof: The proof uses convergence of the successor representation to (I −γT)−1 through the Neumann series.This converts the successor-representation eigenvalue equation into an equation involving I −γT.

THE IMPACT THE NUMBER OF EPISODES HAS IN LEARNING THE SR AND THE EIGENOPTIONS

The number of learning episodes affects how accurately the successor representation captures diffusive structure, but useful eigenoptions can emerge before the representation is fully accurate.

  • Episode impact: After 500 episodes, the first successor-representation eigenvectors are almost perfectly estimated, whereas 100 episodes are insufficient in all rooms.The comparison uses 100-step episodes with η = 0.1 and γ = 0.9.
  • Episode impact: After 100 episodes, the learned successor representation can still generate eigenoptions that reduce the agent’s diffusion time.Thus, accurate estimation of the entire diffusive-information-flow model is not required for this outcome.
  • Eigenoption behavior: Except after 100 episodes, estimated-successor-representation eigenoptions move the agent toward the correct rooms, although they do not always reach the corners.Proto-value-function eigenoptions are shifted one tile from the corners because prior work omitted self-loops.
  • Eigenoption behavior: The first eigenoption learned after 100 episodes moves the agent toward previously unvisited parts of the state space.The authors speculate that this helps explain why the option combination reduces diffusion time and identify incremental discovery as future work.

USING EIGENOPTIONS TO ACCUMULATE REWARD IN THE ENVIRONMENT

Eigenoptions improve control performance as well as diffusion through the environment. Rough successor-representation estimates and relatively few eigenoptions can already produce gains, with more accurate estimates helping especially when many options are used.

  • Control performance: Eigenoptions improve the agent’s control performance while reducing diffusion time.The proposed explanation is that they increase the likelihood of covering more of the state space within the same time.
  • Control performance: Few eigenoptions appear sufficient to improve the agent’s performance.The experiments use off-policy Q-learning with primitive actions as the target policy and random actions and eigenoptions as the behavior policy.
  • Successor-representation accuracy: Rough successor-representation estimates obtained after only 100 episodes can already improve performance.More accurate successor-representation predictions provide further gains mainly when dozens of eigenoptions are used.
  • Successor-representation accuracy: The eigenoptions added first are those associated with the larger eigenvalues, which are also the first to be estimated accurately.This links the ordering of option addition to the accuracy pattern of successor-representation estimates.

EVALUATION OF THE RECONSTRUCTION TASK

The reconstruction evaluation compares predicted game screens with target screens over ten time steps in four games. The network captures the environment’s general structure and tracks most movement.

  • Reconstruction evaluation: Figures 20–23 compare target screens with the network’s predictions over ten time steps in each game.The evaluation covers four games from the Arcade Learning Environment.
  • Reconstruction evaluation: The network accurately predicts the general structure of the environment.The passage also reports that it can track most movement in the evaluated games.

EIGENOPTIONS DISCOVERED IN FREEWAY

In FREEWAY, the method discovers two meaningful eigenoptions, visualized through colored trajectories and visitation intensity. The accompanying figures track eigenvector and eigenoption evolution, evaluate performance across environments, and show auxiliary next-screen predictions in Atari games.

  • FREEWAY eigenoptions: FREEWAY yields two meaningful eigenoptions, represented by trajectories whose colors distinguish options and whose intensity indicates visitation frequency.Each option is visualized through the normalized count of the avatar’s screen position over a trajectory.
  • Reward evaluation: Figures 15–19 compare reward accumulation with and without eigenoptions across environments and across successor-representation estimates based on 100, 500, and 1,000 episodes, plus the true representation.The environments vary start and goal locations, and the plots report performance separately for four environments.
  • Pixel-based estimation: Figures 20–23 show final one-step predictions for BANK HEIST, FREEWAY, MONTEZUMA’S REVENGE, and MS. PACMAN using next-screen prediction as an auxiliary task for successor-representation estimation.The auxiliary task predicts the next game screen while estimating the successor representation.
Loading 1710.11089v3…