PaperlayerView exact revision on arXiv

Source-linked AI summary

The Laplacian in RL: Learning Representations with Efficient Approximations

Yifan Wu, George Tucker, Ofir Nachum

arXiv:1810.04586v1cs.LGstat.ML

TL;DR

Existing Laplacian-eigenvector approximation methods are computationally costly and inadequately justified beyond tabular RL settings. This paper introduces a general, scalable model-free approach and reports stronger approximation results than previous proposals, alongside reward-shaping benefits in goal-achieving tasks.

  • Problem

    Existing methods for approximating Laplacian eigenvectors can be computationally expensive and lack adequate justification beyond finite, tabular RL settings.

    Source: §4 · p. 7

  • Method

    The paper uses a spectral graph-drawing objective with function approximation and sampled experience to learn Laplacian eigenvector representations in model-free RL.

    Source: §1 · p. 2, §3.2 · p. 6

  • Results

    The method outperforms previous proposals at approximating Laplacian eigenvectors, including with tabular representations, and its learned representations outperform sparse and raw-feature L2 rewards in goal-achieving tasks.

    Source: §1 · p. 3, §5.1 · p. 8, §5.2.1 · p. 10

  • Takeaways & Limitations

    The approach applies to state spaces of any cardinality and requires only sampled mini-batches of states and state pairs.

    Source: §6 · p. 11

    In continuous control, shaped rewards can encourage a policy to reach only one of multiple goal-achieving states, such as states with different velocities.

    Source: §5.2.2 · p. 11

Abstract

from arXiv · show

The smallest eigenvectors of the graph Laplacian are well-known to provide a succinct representation of the geometry of a weighted graph. In reinforcement learning (RL), where the weighted graph may be interpreted as the state transition process induced by a behavior policy acting on the environment, approximating the eigenvectors of the Laplacian provides a promising approach to state representation learning. However, existing methods for performing this approximation are ill-suited in general RL settings for two main reasons: First, they are computationally expensive, often requiring operations on large matrices. Second, these methods lack adequate justification beyond simple, tabular, finite-state settings. In this paper, we present a fully general and scalable method for approximating the eigenvectors of the Laplacian in a model-free RL context. We systematically evaluate our approach and empirically show that it generalizes beyond the tabular, finite-state setting. Even in tabular, finite-state settings, its ability to approximate the eigenvectors outperforms previous proposals. Finally, we show the potential benefits of using a Laplacian representation learned using our method in goal-achieving RL tasks, providing evidence that our technique can be used to significantly improve the performance of an RL agent.

1 Introduction

Laplacian representations offer a way to reflect environment geometry in RL state representations, but existing approximation methods are costly and poorly justified beyond tabular settings. The paper proposes a scalable, model-free approach and reports better eigenvector approximations and reward-shaping performance than previous proposals and raw-feature or sparse rewards.

1 Introduction

  • In a two-room gridworld, raw (x, y) distances ignore walls, whereas Laplacian representations reflect the environment geometry and avoid spurious local optima.The paper motivates representations whose distances roughly correspond to an agent’s ability to reach one state from another.Source: §1 · p. 2
  • For a weighted graph, its d smallest Laplacian eigenvectors embed vertices in Rd; in RL, states are vertices and transition probabilities define edge weights.Prior work used these eigenvectors as policy-iteration basis functions and to construct exploratory options.Source: §1 · p. 2
  • Existing Laplacian-approximation methods can require expensive eigendecompositions and have unclear applicability beyond finite, tabular state spaces.Reduced-matrix methods can also preclude stochastic or online settings.Source: §1 · p. 2
  • The approach uses a computationally efficient function-approximation objective that can be stochastically optimized over sampled experience in a general RL setting.The objective is based on spectral graph drawing, whose optimum yields the desired eigenvector representations.Source: §1 · pp. 2–3

5.1 Evaluating the Learned Representations

  • The method outperforms previous eigenvector-approximation methods across all three raw representations, including the tabular setting, and performs well with few training samples.The paper also evaluates learned-representation reward shaping in gridworld mazes and continuous-control navigation environments.Source: §1 · p. 3

2 Background

The background generalizes Laplacian eigenvector representations from finite graphs to function spaces, then frames their computation as a graph-drawing optimization problem. Under the stated operator assumptions, minimizing that objective recovers the subspace spanned by the eigenfunctions with the smallest Laplacian eigenvalues.

2.1 A Space and a Measure

  • The framework uses Hilbert spaces to treat discrete and continuous state spaces uniformly, with square-integrable real-valued functions forming the function space.The inner product induces orthogonality and a norm; the finite-state simplification uses a probability distribution over states and a weighted dot product.Source: §2 · p. 3, §2.1 · p. 3

2 Background

  • The background presents a unified Hilbert-space treatment of the Laplacian and its eigenfunctions, regardless of whether the underlying space is discrete or continuous.For finite-state intuition, the paper gives simplified definitions of the state space, probability measure, and function space.Source: §2 · p. 3

2.2 The Laplacian

  • A symmetric, normalized kernel defines a compact self-adjoint operator; its Laplacian is I − D, and its d smallest-eigenvalue eigenfunctions define an embedding into Rd.The assumptions include symmetry and a kernel that integrates to one for each state.Source: §2.2 · p. 4

2.3 Spectral Graph Drawing

  • Spectral graph drawing seeks orthonormal functions whose pairwise embedding distances are small for highly connected vertices.The objective’s minimum is the sum of the d smallest Laplacian eigenvalues and is achieved by functions spanning the corresponding eigenfunction subspace.Source: §2.3 · pp. 4–5

3 Representation Learning with the Laplacian

This section defines an RL Laplacian from a fixed behavior policy and develops a sampled graph-drawing objective for learning its eigenfunctions. It uses stochastic optimization and a soft penalty to address state-space and orthonormality challenges.

3.1 The Laplacian in a Reinforcement Learning Setting

  • For a fixed behavior policy π, the RL Laplacian uses its chain’s stationary distribution ρ and a symmetric affinity D formed from the two-way transition probabilities.For finite state spaces, the affinity averages the transition probabilities in each direction, normalized by the corresponding stationary probabilities.Source: §3.1 · p. 5

3.2 Approximating the Laplacian Eigenfunctions

  • The graph-drawing objective can be expressed as an expectation, enabling minibatch optimization despite state-enumeration, pairwise-affinity-access, and exact-orthonormality challenges.The method samples states and state pairs rather than requiring enumeration of the state space or explicit access to arbitrary D(u, v).Source: §3.2 · p. 6
  • Because exact orthonormality is difficult to enforce, the method relaxes it to a soft constraint and penalizes deviations in an unconstrained graph-drawing objective.Source: §3.2 · p. 6
  • The objective attracts embeddings of policy-transition pairs and repels independently sampled states; the repulsive term is interpreted as orthogonalizing embeddings while keeping their norms away from zero.Source: §3.2 · pp. 6–7

4 Related Work

Prior Laplacian representation methods either target tabular settings or face computational and optimization limitations. The paper presents a general stochastic graph-drawing approach and positions its continuous-control reward-shaping application as extending beyond earlier narrow applications.

  • The paper presents a Laplacian representation-learning framework for state spaces accessed only through sampling, unlike earlier RL work focused on simple tabular settings.Source: §4 · p. 7
  • The graph-drawing objective stochastically optimizes a representation module that approximates Laplacian eigenfunctions without storing the entire eigendecomposition.The authors note that many stochastic eigendecomposition approaches require storing the full decomposition, which scales poorly and does not provide arbitrary rows through a function approximator.Source: §4 · p. 7
  • Machado et al. (2017b) propose stochastic approximation for large state spaces, but their method is justified only tabularly and uses a reduced-matrix eigendecomposition unsuitable for online settings.Source: §4 · p. 7
  • Shaham et al. (2018) require large mini-batches and risk numerical instability, whereas Pfau et al. (2018) lack unbiased stochastic gradients and scale quadratically with embedding dimensions.Source: §4 · p. 7
  • The paper’s reward-shaping application in continuous-control environments contrasts with prior applications limited to small discrete spaces or qualitative assessments of learned options.Source: §4 · pp. 7–8

5 Experiments

The experiments compare learned representations with Laplacian-based targets and test their use for reward shaping in goal-achieving tasks. The method outperforms prior representation methods and, in gridworld and continuous-control settings, learned-representation rewards outperform alternatives in the reported comparisons.

5.1 Evaluating the Learned Representations

  • Our method more accurately approximates Laplacian representations than previous methods across all three raw representations, including tabular inputs and settings with few training samples.Figure 3 plots the gap between learned and optimal Laplacian-based representations against training transitions; lower is better.Source: §5.1 · p. 8, Figure 3 · p. 8

5.2 Laplacian Representation Learning for Reward Shaping

  • For reward shaping, the paper uses distance in a learned latent space and proposes goal-space or state-space embeddings when goal and state spaces differ.The experiments use both options when the spaces differ.Source: §5.2 · p. 9

5.2.1 GridWorld

  • In TwoRoom and HardMaze, the learned-representation reward mix significantly outperforms the other reward settings when raw-feature distances are inaccurate.The mix combines learned-space distance with sparse reward; in OneRoom, all shaped rewards significantly outperform sparse reward.Source: §5.2.1 · pp. 9–10, Figure 4 · p. 10

5.2.2 Continuous Control

  • In continuous-control navigation, both mix and fullmix outperform all other methods, although neither goal-space nor state-space embedding is a perfect solution.The tasks use PointMass and Ant agents; the paper notes that the two embedding choices have different drawbacks when aligning goal and state spaces.Source: §5.2.2 · pp. 10–11, Figure 5 · p. 11

6 Conclusion

The paper presents a general, scalable Laplacian-based state representation and applies it to reward shaping in discrete and continuous-control settings. The appendices discuss when the needed eigenvalues exist and how transition distributions are extended and sampled.

6 Conclusion

  • The approach applies regardless of state-space cardinality and relies on sampling mini-batches of states and state pairs; it is also applied to reward shaping in discrete and continuous-control settings.The authors encourage further investigation of Laplacian-based representations.Source: §6 · p. 11

A Existence of smallest eigenvalues of the Laplacian.

  • In infinite-dimensional Hilbert spaces, the largest d eigenvalues are guaranteed to exist when d is below the number of positive eigenvalues of D; the authors conjecture this restriction is an artifact.They conjecture that any d may work in practice in infinite-dimensional H.Source: A Existence of smallest eigenvalues of… · p. 14

B Defining D for Multi-step Transitions

  • The generalized discounted transition samples a random number of steps, with λ = 0 corresponding to one-step transitions.Sampling draws τ from qλ and rolls out the Markov chain for τ steps.Source: B Defining D for Multi-step Transitions · p. 15
  • With finite trajectories, samples are discarded when the sampled multi-step transition would extend beyond the trajectory.The transition distribution may require arbitrarily long rollouts, which cannot be sampled exactly from a finite replay buffer.Source: B Defining D for Multi-step Transitions · p. 15
  • The definition assumes transition distributions are absolutely continuous with respect to ρ, requiring the behavior policy to be able to explore every reachable state.The paper notes that this exploration need not be efficient.Source: B Defining D for Multi-step Transitions · p. 15
  • When concentrated starts, slow mixing, and short horizons make replay samples differ from stationarity, randomized resets can approximate stationary sampling.The adjusted definition uses a small reset probability; pairs spanning reset transitions are ignored in practice.Source: B Defining D for Multi-step Transitions · pp. 15–16

C Derivation of (5)

Switching u and v in the second term leaves the quantity unchanged.

C Derivation of (5)

  • Switching u and v in the second term gives the same quantity as the first term.This is the stated symmetry used in the derivation.Source: C Derivation of (5) · p. 16

D.1 Evaluating the Learned Representations

The learned representations are evaluated in FourRoom, and Figure 6 covers dimensions d = 50 and 100. The β ablation describes a trade-off between approximation quality and optimization difficulty.

D.1 Evaluating the Learned Representations

  • FourRoom has 152 discrete states and four actions, with deterministic transitions and episodes of length 50.The position representation uses scaled (x, y) coordinates, while image states are 15-by-15 RGB pixels.Source: §D.1 · p. 16
  • Figure 6 evaluates learned representations for d = 50 and d = 100.The supplied caption does not state a result comparison.Source: Figure 6 · p. 17
  • Larger β improves the exact graph-drawing approximation as the soft constraint approaches a hard constraint, but makes SGD harder; the optimal β increases with d.Figure 7 studies β with n = 2000 and position representations.Source: §D.1 · p. 17, Figure 7 · p. 17

D.2.1 GridWorld

The GridWorld experiments use maze positions as raw states and train representations with discounted multi-step transitions. The stated setup uses DQN for policy training.

D.2.1 GridWorld

  • The mazes are 15-by-15 grids with four actions, position-based raw states, and episodes of length 50.Success requires reaching the exact grid state.Source: §D.2.1 · p. 18
  • Representations use d = 20 and discounted multi-step transitions with λ = 0.9, pretrained for 30,000 steps.The authors report that training converges much earlier, and state that 30,000 steps was not optimized.Source: §D.2.1 · p. 18
  • Policy training uses vanilla DQN with online and target networks, ε-greedy exploration at ϵ = 0.2, and reward discount 0.98.The target network is updated every 50 steps with mixing rate 0.05.Source: §D.2.1 · p. 18

D.2.2 Continuous Control

In continuous-control experiments, online-learned representations achieved equivalent performance to pretrained-then-fixed representations. The experiments used PointMass and Ant maze tasks with DDPG policies.

D.2.2 Continuous Control

  • PointMass used 6-dimensional states and 2-dimensional actions, while Ant used 29-dimensional states and 8-dimensional actions.Success meant reaching an L2 ball centered on a specified maze position, with radius 10% of the maze size; episodes lasted 300 steps.Source: §D.2.2 · p. 18
  • The experiments pretrained 20-dimensional representations for 50,000 steps and trained policies with vanilla DDPG.Representation learning used discounted multi-step transitions with λ = 0.99 for PointMass and 0.999 for Ant; the graph-drawing objective used β = 2.0 and δ_jk = 0.1 when j = k, otherwise 0.Source: §D.2.2 · p. 18
  • Online-learned and pretrained-then-fixed representations achieved equivalent performance in the continuous-control experiments.For online training, λ in D was linearly annealed toward 0.95; the authors note that randomized starting positions enabled efficient exploration even with random walks.Source: Figure 8 · p. 19, §D.2.2 · p. 19

Related papers

Loading 1810.04586v1…