PaperlayerView exact revision on arXiv

Source-linked AI summary

MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning

Elise van der Pol, Daniel E. Worrall, Herke van Hoof, Frans A. Oliehoek, Max Welling

arXiv:2006.16908v2cs.LGstat.ML

TL;DR

Deep reinforcement learning often does not exploit known symmetries in large state-action spaces. The paper introduces MDP homomorphic networks and numerically constructed equivariant layers to encode those symmetries, reporting faster convergence across CartPole, Pong, and grid-world experiments.

  • Problem

    Deep reinforcement learning often uses large state-action spaces without exploiting designer-recognizable symmetries, requiring many samples before convergence.

  • Method

    The paper builds MDP homomorphic policy networks with weight-tying and group equivariance, and introduces a numerical method for constructing equivariant layers from specified transformations.

  • Results

    Across CartPole, Pong, and grid-world experiments, MDP homomorphic networks outperform non-equivariant basis networks and standard architectures in convergence speed.

  • Takeaways & Limitations

    Weight-tying over symmetric state-action pairs reduces degrees of freedom and, in these experiments, translates into faster convergence.

  • Takeaways & Limitations

    Control strategies learned with reinforcement learning are hard to verify and validate, creating accident risks when deployed on physical systems without proper precautions.

Abstract

from arXiv · show

This paper introduces MDP homomorphic networks for deep reinforcement learning. MDP homomorphic networks are neural networks that are equivariant under symmetries in the joint state-action space of an MDP. Current approaches to deep reinforcement learning do not usually exploit knowledge about such structure. By building this prior knowledge into policy and value networks using an equivariance constraint, we can reduce the size of the solution space. We specifically focus on group-structured symmetries (invertible transformations). Additionally, we introduce an easy method for constructing equivariant network layers numerically, so the system designer need not solve the constraints by hand, as is typically done. We construct MDP homomorphic MLPs and CNNs that are equivariant under either a group of reflections or rotations. We show that such networks converge faster than unstructured baselines on CartPole, a grid world and Pong.

1 Introduction

The paper uses known symmetries in reinforcement-learning state-action spaces to constrain neural policies and reduce redundant solutions. It connects these constraints to equivariant networks and introduces numerical layer construction for faster learning.

  • Motivation: Deep reinforcement learning often faces large state-action spaces and therefore requires many samples before convergence, while many tasks contain designer-recognizable symmetries.CartPole illustrates this through mirrored strategies for poles falling left or right.
  • MDP Homomorphic Networks: MDP homomorphisms formalize symmetry by removing equivalent state-action pairs and producing a smaller space on which policies can be built.The paper constructs networks satisfying the homomorphism rather than discovering one for a given MDP.
  • MDP Homomorphic Networks: MDP homomorphic networks tie weights across equivalent state-action pairs, allowing experience from one pair to improve policies for all equivalent pairs.For invertible transformations, these policy networks belong to the class of group-equivariant neural networks.
  • Contributions: The paper introduces a numerical method that constructs equivariant layers from specified input and output transformation groups instead of requiring hand-derived linear constraints.Implementations are provided in Pytorch for the layers and transformations used in the paper.
  • Contributions: The proposed contributions are a connection between MDP homomorphisms and group-equivariant networks, plus an automated algorithm for constructing equivariant layers.The approach targets symmetry-preserving decision-making networks.

2 Background

The background defines equivalence, invariance, equivariance, MDPs, and homomorphisms as tools for representing symmetry and reducing reinforcement-learning state-action spaces. Group transformations map equivalent pairs into shared abstract state-actions while equivariant functions transform outputs consistently.

  • Equivalence, Invariance, and Equivariance: Two inputs are f-equivalent when f maps them to the same value; the set of all such inputs forms an equivalence class.Optimal-value equivalence applies this idea to states sharing the same optimal value.
  • Equivalence, Invariance, and Equivariance: A function is invariant under L_g when f(x) = f(L_g[x]) for every group element and input, so transformations remain within equivalence classes.The transformation group includes an identity operation.
  • Equivalence, Invariance, and Equivariance: A function is equivariant when an output transformation K_g satisfies K_g[f(x)] = f(L_g[x]), with invariance as the special case where K_g is the identity.The paper constructs intertwiners computationally for pairs of transformation operators.
  • Markov Decision Processes: An MDP consists of state and action spaces, reward and transition functions, and a discount factor; its goal is a policy maximizing expected return.Value and Q-value functions describe expected returns and are governed by Bellman equations.
  • Markov Decision Processes: MDP symmetries are state and state-dependent action transformations that leave reward and transition operators invariant along transformation orbits.CartPole is presented as an example with reflection symmetry about the vertical axis.
  • MDP Homomorphisms: An MDP homomorphism maps an MDP surjectively to an abstract state-action space, with h-equivalent pairs sharing state and action-map images.Symmetries naturally induce such homomorphisms because transformed pairs satisfy the same reward and transition invariances.
  • MDP Homomorphisms: Group-structured homomorphisms map every state-action pair in a transformation orbit to one representative equivalence class in the reduced MDP.Optimal policies can be optimized in the abstract MDP and pulled back to the original MDP.

3 Method

The method derives MDP homomorphic policies as equivariant networks and numerically constructs equivariant layers from designer-specified transformations. It represents valid layers through a basis of weights satisfying linear equivariance constraints.

  • 3.1 Lifted Policies Are Invariant: MDP homomorphic policies for group-structured symmetries must satisfy an equivariance constraint under state and policy transformations.For finite action spaces, action transformations become permutation matrices acting on vectorized policies.
  • 3.2 Building MDP Homomorphic Networks: The network is built from equivariant layers and nonlinearities, which preserves equivariance through the complete network.The construction targets policy networks satisfying the lifted-policy property.
  • 3.2 Building MDP Homomorphic Networks: Equivariant layers are constructed numerically instead of requiring hand-derived constraints for each transformation group.The designer specifies input and output transformations, while the method automatically finds the equivariant layer space.
  • 3.2 Building MDP Homomorphic Networks: The valid weight space is defined by linear constraints KgW = WLg and parameterized as linear combinations of basis weights.A symmetrizer projects arbitrary weights into the equivariant subspace, after which sampled projections and SVD provide basis vectors.
  • 3.2 Building MDP Homomorphic Networks: The numerical procedure requires only the ability to apply input and output transformations to weights, not explicit transformation matrices.For example, a matrix action can be implemented through a built-in image rotation function.

4 Experiments

The experiments evaluate MDP homomorphic MLPs, CNNs, and equivariant feature extractors on three symmetric reinforcement-learning tasks. Across the tasks, equivariant networks converge faster than non-equivariant bases and standard architectures, with additional comparisons isolating basis and feature-extractor effects.

  • 4 Experiments: MDP homomorphic MLPs, CNNs, and equivariant feature extractors were evaluated on CartPole, a grid world, and Pong.The environments exhibit reflection, rotational, or flip symmetries represented over their state and action spaces.
  • 4.2 Models: Networks were compared using equivariant, nullspace, and random bases, while basis networks generally used fewer channels to keep trainable parameters comparable.Channels were reduced by the square root of the group size unless stated otherwise.
  • 4.3 Results and Discussion: Across CartPole, the grid world, and Pong, MDP homomorphic networks outperformed non-equivariant basis networks and standard architectures in convergence speed.Training curves are reported for CartPole, Pong, and the grid world.
  • 4.3 Results and Discussion: Equivariant networks were more beneficial than data augmentation on Pong, consistent with direct parameter sharing through equivariance.Pong curves were limited to the first 15 million frames to highlight early-training differences.
  • 4.3 Results and Discussion: The equivariant basis converged fastest in the basis ablation, while the nullspace basis beat the random basis on CartPole and Pong but not clearly in the grid world.The authors identify the grid-world result as requiring deeper follow-up investigation.
  • 4.3 Results and Discussion: Equivariant feature extractors converged faster than standard CNN feature extractors, although the advantage was much less pronounced on Breakout.The authors hypothesize that equivariant features make learning an equivariant policy easier.

5 Related Work

Prior work has explored discovering MDP homomorphisms, learning them from experience, and exploiting symmetries through data or filter transformations. This paper differs by encoding symmetries directly into neural-network weights and introducing automatic equivariant-layer construction.

  • MDP homomorphisms: Earlier MDP-homomorphism methods often discovered maps from transition and reward functions, enumerable state spaces, or sampled experience.Exact symmetry computation remains graph-isomorphism complete even with full MDP dynamics.
  • Symmetry exploitation: Deep reinforcement learning has exploited symmetries through symmetric filter weights, data augmentation, and transformations such as translations, cutout, and color jitter.These approaches include work on Go and benchmark data augmentation.
  • Symmetry exploitation: In contrast, MDP homomorphic networks encode symmetries directly into neural-network weights rather than augmenting existing data.
  • Equivariant layers: Existing equivariant-network work has relied on hand-constructed layers for grid-based roto-translation groups.The cited theory and implementations cover two-dimensional and three-dimensional grid transformations.
  • Equivariant layers: The paper contributes an automatic numerical procedure for constructing equivariant layers from specified transformation groups.This addresses prior work that described equations but did not provide an algorithm.

6 Conclusion

The paper introduces MDP homomorphic networks for reinforcement-learning problems with identified symmetries and connects weight tying to faster convergence. It also provides automatic equivariant-layer construction and identifies directions for extending the approach.

  • Contributions: MDP homomorphic networks tie weights over symmetric state-action pairs, reducing degrees of freedom and yielding faster convergence in the experiments.
  • Contributions: The paper formalizes the connection between MDP homomorphisms and equivariant networks for reinforcement learning.
  • Contributions: The paper introduces a method to automatically construct equivariant network layers from specified symmetries, removing an implementational obstacle.
  • Future work: Future work will study the symmetrizer’s effect on learning dynamics and generalize to problems that are not fully symmetric.

8 Broader Impact

The paper’s efficiency goals could affect broad application domains because MDPs model systems such as autonomous driving, smart grids, and scheduling. Potential impacts include both resource gains and societal risks.

  • Potential impact: More efficient solutions for MDPs could affect autonomous driving, smart grids, and scheduling over the long term.
  • Scope: The paper does not expect its particular algorithm to create immediate societal risks, but acknowledges possible long-term positive or negative impacts.
  • Potential benefits: Improving transportation or power-grid efficiency could make better use of scarce resources.
  • Potential risks: Applications such as autonomous weapons could pose societal risks, while automation may increase productivity but reduce labor demand.

A The Symmetrizer

The symmetrizer maps arbitrary weight matrices into the equivariant subspace and fixes matrices already in that subspace. Its proof establishes symmetry, fixing, and idempotence properties.

  • Summary: Together, the three properties characterize symmetrization as a projection onto the equivariant subspace.
  • Symmetric property: The symmetric property shows that symmetrization maps arbitrary matrices into equivariant matrices.The proof verifies that the symmetrized matrix satisfies the equivariance constraint.
  • Fixing property: The equivariant subspace is fixed by the symmetrizer: every matrix already in it remains unchanged.This establishes that the symmetrizer’s range covers the full equivariant subspace rather than only a subset.
  • Idempotence property: The symmetrizer is idempotent, so applying it again does not change its previous output.

B Experimental Settings

The experiments construct equivariant networks by selecting transformation groups and stacking layers whose intermediate representations are shared. MLPs and CNNs use group-specific representation dimensions and transformations.

  • Designing representations: The method constructs a space of equivariant intertwiners using chosen transformation operators for inputs, outputs, and intermediate layers.The input and output transformations are relatively easy to define, while intermediate-layer operators require design rules.
  • Transformation groups: Each experiment begins by identifying a finite transformation group G and its size |G|.For example, the Pong flip group has |G| = 2; group size need not equal the dimensionality of its transformation operators.
  • Layer composition: Stacking equivariant layers produces a network that is equivariant as a whole when adjacent layers share the intermediate representation.The output transformation of one layer must match the input transformation of the next.
  • MLP implementation: MLP activations use an additional representation dimension of |G|+1, with permutations for group elements and a fixed bias coordinate.This representation is applied to activations shaped as [batch_size, num_channels, representation_size].
  • CNN implementation: CNN activations likewise add a |G|+1 representation dimension, combining spatial transformations with permutations of that dimension.The resulting activation shape is [batch_size, num_channels, representation_size, height, width].

B.2 Cartpole-v1

The experiments instantiate group representations and architectures for CartPole, GridWorld, Pong, and Breakout, using MLP or CNN networks with task-specific transformations and training settings.

  • Output representations: Value outputs are invariant rather than equivariant, implemented with |G| identity representations for the desired output dimensionality.State-value prediction uses a one-dimensional output replicated across the group representation.
  • Training settings: PPO CartPole training used ADAM with 16 parallel environments, seven candidate learning rates, and 25 random seeds per setting.The reported final learning rates are listed in Table 2.
  • Architectures: CartPole uses MLP architectures with basis networks and two comparison MLPs, while GridWorld, Pong, and Breakout use CNN architectures.The supplied passages identify separate architecture listings for each task family.
  • Group representations: CartPole MLP intermediate representations use permutations over the group dimension, while GridWorld and Pong use spatial transformations with cyclic representation permutations.GridWorld and Pong specify task-specific spatial flips or rotations for their state representations.
  • Training settings: A2C GridWorld training used ADAM with four parallel environments, three candidate learning rates, and 15 random seeds per setting.The candidate rates were selected near values where the baseline performed well in preliminary experiments.

C Breakout Experiments

Breakout compares an equivariant feature extractor with a convolutional baseline after modifying the input to ensure symmetry. The improvement is smaller than in the other reported tasks.

  • Experimental setup: Breakout removes two decorative bottom-corner blocks to ensure that the input states are symmetric.The experiment otherwise largely follows the Pong hyperparameter and architecture settings.
  • Results: The equivariant feature extractor improves over the standard convolutional approach, but the difference is much less pronounced than in CartPole, Pong, or GridWorld.The authors state that the reason for this weaker improvement is not straightforward.
  • Interpretation: The Breakout extractor is not end-to-end MDP homomorphic because it produces homomorphic state representations followed by an unconstrained regular policy.The authors suggest that the unconstrained final layers may negate some advantages of the equivariant feature extractor, especially in the more complex Breakout setting.

D Cartpole-v1 Deeper Network Results

The deeper CartPole networks use four layers instead of two. Their performance is comparable to regular-depth networks, but deeper regular MLPs show substantially higher variance.

  • Depth comparison: The experiment compares four-layer CartPole-v1 networks with the two-layer networks used in the regular-depth setting.The comparison is reported in Figure 8.
  • Results: Performance of regular-depth and deeper networks is comparable, while the regular MLP has much higher variance at greater depth.The passage compares the regular-depth results from Figure 4b with the deeper-network results from Figure 8.
  • Evaluation: Figure 8 reports 25%, 50%, and 75% quantiles over 25 random seeds for equivariant, random, nullspace, and different-degree-of-freedom MLP networks.All networks were trained with PPO and fine-tuned over seven learning rates.
Loading 2006.16908v2…