MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning

Introduction

This paper considers learning decision-making systems that exploit symmetries in the structure of the world. Deep reinforcement learning (DRL) is concerned with learning neural function approximators for decision making strategies. While DRL algorithms have been shown to solve complex, high-dimensional problems (silver2016mastering; schulman2017proximal; mnih2015human; mnih2016asynchronous), they are often used in problems with large state-action spaces, and thus require many samples before convergence. Many tasks exhibit symmetries, easily recognized by a designer of a reinforcement learning system. Consider the classic control task of balancing a pole on a cart. Balancing a pole that falls to the right requires an equivalent, but mirrored, strategy to one that falls to the left. See Figure 1. In this paper, we exploit knowledge of such symmetries in the state-action space of Markov decision processes (MDPs) to reduce the size of the solution space.

We use the notion of MDP homomorphisms ravindran2004approximate; ravindran2001symmetries to formalize these symmetries. Intuitively, an MDP homomorphism is a map between MDPs, preserving the essential structure of the original MDP, while removing redundancies in the problem description, i.e., equivalent state-action pairs. The removal of these redundancies results in a smaller state-action space, upon which we may more easily build a policy. While earlier work has been concerned with discovering an MDP homomorphism for a given MDP ravindran2004approximate; ravindran2001symmetries; narayanamurthy2008hardness; ravindran2003smdp; biza2019online; van2020plannable, we are instead concerned with how to construct deep policies, satisfying the MDP homomorphism. We call these models MDP homomorphic networks.

MDP homomorphic networks use experience from one state-action pair to improve the policy for all ‘equivalent’ pairs. See Section 2.1 for a definition. They do this by tying the weights for two states if they are equivalent under a transformation chosen by the designer, such as $s$ and $L[s]$ in Figure 1. Such weight-tying follows a similar principle to the use of convolutional networks lecun1998convnet, which are equivariant to translations of the input cohen2016group. In particular, when equivalent state-action pairs can be related by an invertible transformation, which we refer to as group-structured, we show that the policy network belongs to the class of group-equivariant neural networks cohen2016group; worrall2017harmonic.Equivariant neural networks are a class of neural network, which have built-in symmetries cohen2016group; cohen2016steerable; worrall2017harmonic; weiler2018learning; weiler2019general. They are a generalization of convolutional neural networks—which exhibit translation symmetry—to transformation groups (group-structured equivariance) and transformation semigroups worrall2019deep (semigroup-structured equivariance). They have been shown to reduce sample complexity for classification tasks worrall2017harmonic; winkels20183d and also to be universal approximators of symmetric functions Specifically group equivariant networks are universal approximators to functions symmetric under linear representations of compact groups. yarotsky2018universal. We borrow from the literature on group equivariant networks to design policies that tie weights for state-action pairs given their equivalence classes, with the goal of reducing the number of samples needed to find good policies. Furthermore, we can use the MDP homomorphism property to design not just policy networks, but also value networks and even environment models. MDP homomorphic networks are agnostic to the type of model-free DRL algorithm, as long as an appropriate transformation on the output is given. In this paper we focus on equivariant policy and invariant value networks. See Figure 1 for an example policy.

An additional contribution of this paper is a novel numerical way of finding equivariant layers for arbitrary transformation groups. The design of equivariant networks imposes a system of linear constraint equations on the linear/convolutional layers cohen2016steerable; cohen2016group; worrall2017harmonic; weiler2018learning. Solving these equations has typically been done analytically by hand, which is a time-consuming and intricate process, barring rapid prototyping. Rather than requiring analytical derivation, our method only requires that the system designer specify input and output transformation groups of the form {state transformation, policy transformation}. We provide Pytorch NEURIPS2019_9015 implementations of our equivariant network layers, and implementations of the transformations used in this paper. We also experimentally demonstrate that exploiting equivalences in MDPs leads to faster learning of policies for DRL.

We draw a connection between MDP homomorphisms and group equivariant networks, proposing MDP homomorphic networks to exploit symmetries in decision-making problems;

We introduce a numerical algorithm for the automated construction of equivariant layers.

Background

Here we outline the basics of the theory behind MDP homomorphisms and equivariance. We begin with a brief outline of the concepts of equivalence, invariance, and equivariance, followed by a review of the Markov decision process (MDP). We then review the MDP homomorphism, which builds a map between ‘equivalent’ MDPs.

Equivalence If a function $f:\mathcal{X}\to\mathcal{Y}$ maps two inputs $x,x^{\prime}\in\mathcal{X}$ to the same value, that is $f(x)=f(x^{\prime})$, then we say that $x$ and $x^{\prime}$ are $f$-equivalent. For instance, two states $s,s^{\prime}$ leading to the same optimal value $V^{*}(s)=V^{*}(s^{\prime})$ would be $V^{*}$-equivalent or optimal value equivalent ravindran2001symmetries. An example of two optimal value equivalent states would be states $s$ and $L[s]$ in the CartPole example of Figure 1. The set of all points $f$-equivalent to $x$ is called the equivalence class of $x$.

Invariance and Symmetries Typically there exist very intuitive relationships between the points in an equivalence class. In the CartPole example of Figure 1 this relationship is a horizontal flip about the vertical axis. This is formalized with the transformation operator $L_{g}:\mathcal{X}\to\mathcal{X}$, where $g\in G$ and $G$ is a mathematical group. If $L_{g}$ satisfies

then we say that $f$ is invariant or symmetric to $L_{g}$ and that $\{L_{g}\}_{g\in G}$ is a set of symmetries of $f$ . We can see that for the invariance equation to be satisfied, it must be that $L_{g}$ can only map $x$ to points in its equivalence class. Note that in abstract algebra for $L_{g}$ to be a true transformation operator, $G$ must contain an identity operation; that is $L_{g}[x]=x$ for some $g$ and all $x$. An interesting property of transformation operators which leave $f$ invariant, is that they can be composed and still leave $f$ invariant, so $L_{g}\circ L_{h}$ is also a symmetry of $f$ for all $g,h\in G$. In abstract algebra, this property is known as a semigroup property. If $L_{g}$ is always invertible, this is called a group property. In this work, we experiment with group-structured transformation operators. For more information, see dummit2004abstract. One extra helpful concept is that of orbits. If $f$ is invariant to $L_{g}$, then it is invariant along the orbits of $G$. The orbit ${\mathcal{O}}_{x}$ of point $x$ is the set of points reachable from $x$ via transformation operator $L_{g}$:

Equivariance A related notion to invariance is equivariance. Given a transformation operator $L_{g}:\mathcal{X}\to\mathcal{X}$ and a mapping $f:\mathcal{X}\to\mathcal{Y}$, we say that $f$ is equivariant cohen2016group; worrall2017harmonic to the transformation if there exists a second transformation operator $K_{g}:\mathcal{Y}\to\mathcal{Y}$ in the output space of $f$ such that

The operators $L_{g}$ and $K_{g}$ can be seen to describe the same transformation, but in different spaces. In fact, an equivariant map can be seen to map orbits to orbits. We also see that invariance is a special case of equivariance, if we set $K_{g}$ to the identity operator for all $g$. Given $L_{g}$ and $K_{g}$, we can solve for the collection of equivariant functions $f$ satisfying the equivariance constraint. Moreover, for linear transformation operators and linear $f$ a rich theory already exists in which $f$ is referred to as an intertwiner (cohen2016steerable). In the equivariant deep learning literature, neural networks are built from interleaving intertwiners and equivariant nonlinearities. As far as we are aware, most of these methods are hand-designed per pair of transformation operators, with the exception of diaconu2019learning. In this paper, we introduce a computational method to solve for intertwiners given a pair of transformation operators.

2 Markov Decision Processes

Symmetries can appear in MDPs. For instance, in Figure 2 CartPole has a reflection symmetry about the vertical axis. Here we define an MDP with symmetries. In an MDP with symmetries there is a set of transformations on the state-action space, which leaves the reward function and transition operator invariant. We define a state transformation and a state-dependent action transformation as ${L_{g}}:{\mathcal{S}}\to{\mathcal{S}}$ and ${K_{g}^{s}}:{\mathcal{A}}\to{\mathcal{A}}$ respectively. Invariance of the reward function and transition function is then characterized as

Written like this, we see that in an MDP with symmetries the reward function and transition operator are invariant along orbits defined by the transformations $({L_{g}},{K_{g}^{s}})$.

MDP Homomorphisms

MDPs with symmetries are closely related to MDP homomorphisms, as we explain below. First we define the latter. An MDP homomorphism $h$ ravindran2004approximate; ravindran2001symmetries is a mapping from one MDP ${M}=({\mathcal{S}},{\mathcal{A}},{R},{T},\gamma)$ to another ${\bar{M}}=({\mathcal{\bar{S}}},{\mathcal{\bar{A}}},{\bar{R}},{\bar{T}},\gamma)$ defined by a surjective map from the state-action space ${\mathcal{S}}\times{\mathcal{A}}$ to an abstract state-action space ${\mathcal{\bar{S}}}\times{\mathcal{\bar{A}}}$. In particular, $h$ consists of a tuple of surjective maps ${({\sigma},{\{{\alpha_{s}}|s\in{\mathcal{S}}\}})}$, where we have the state map ${\sigma}:{\mathcal{S}}\to{\mathcal{\bar{S}}}$ and the state-dependent action map ${\alpha_{s}}:{\mathcal{A}}\to{\mathcal{\bar{A}}}$. These maps are built to satisfy the following conditions

An exact MDP homomorphism provides a model equivalent abstraction li2006towards. Given an MDP homomorphism $h$, two state-action pairs $(s,a)$ and $(s^{\prime},a^{\prime})$ are called $h$-equivalent if ${\sigma}(s)={\sigma}(s^{\prime})$ and ${\alpha_{s}}(a)=\alpha_{s^{\prime}}(a^{\prime})$. Symmetries and MDP homomorphisms are connected in a natural way: If an MDP has symmetries $L_{g}$ and $K_{g}$, the above equations (4) and (5) hold. This means that we can define a corresponding MDP homomorphism, which we define next.

Group-structured MDP Homomorphisms

Specifically, for an MDP with symmetries, we can define an abstract state-action space, by mapping $(s,a)$ pairs to (a representative point of) their equivalence class $(\sigma(s),\alpha_{s}(a))$. That is, state-action pairs and their transformed version are mapped to the same abstract state in the reduced MDP:

In this case, we call the resulting MDP homomorphism group structured. In other words, all the state-action pairs in an orbit defined by a group transformation are mapped to the same abstract state by a group-structured MDP homomorphism.

Optimal Value Equivalence and Lifted Policies $h$-equivalent state-action pairs share the same optimal $Q$-value and optimal value function ravindran2001symmetries. Furthermore, there exists an abstract optimal $Q$-value $\bar{Q}^{*}$ and abstract optimal value function $\bar{V}^{*}$, such that $Q^{*}({s},{a})=\bar{Q}^{*}({\sigma}({s}),{\alpha_{s}}({a}))$ and $V^{*}({s})=\bar{V}^{*}({\sigma}({s}))$. This is known as optimal value equivalence ravindran2001symmetries. Policies can thus be optimized in the simpler abstract MDP. The optimal abstract policy $\bar{\pi}(\bar{a}|\sigma(s))$ can then be pulled back to the original MDP using a procedure called lifting Note that we use the terminology lifting to stay consistent with ravindran2001symmetries.. The lifted policy is given in Equation 9. A lifted optimal abstract policy is also an optimal policy in the original MDP ravindran2001symmetries. Note that while other lifted policies exist, we follow ravindran2001symmetries; ravindran2004approximate and choose the lifting that divides probability mass uniformly over the preimage:

Method

The focus of the next section is on the design of MDP homomorphic networks—policy networks and value networks obeying the MDP homomorphism. In the first section of the method, we show that any policy network satisfying the MDP homomorphism property must be an equivariant neural network. In the second part of the method, we introduce a novel numerical technique for constructing group-equivariant networks, based on the transformation operators defining the equivalence state-action pairs under the MDP homomorphism.

Lifted policies in symmetric MDPs with group-structured symmetries are invariant under the group of symmetries. Consider the following: Take an MDP with symmetries defined by transformation operators $({L_{g}},{K_{g}^{s}})$ for $g\in G$. Now, if we take $s^{\prime}=L_{g}[s]$ and $a^{\prime}=K_{g}^{s}[a]$ for any $g\in G$, $(s^{\prime},a^{\prime})$ and $(s,a)$ are h-equivalent under the corresponding MDP homomorphism $h={({\sigma},{\{{\alpha_{s}}|s\in{\mathcal{S}}\}})}$. So

for all $s\in{\mathcal{S}},a\in{\mathcal{A}}$ and $g\in G$. In the first equality we have used the definition of the lifted policy. In the second equality, we have used the definition of $h$-equivalent state-action pairs, where ${\sigma}(s)={\sigma}({L_{g}}(s))$ and ${\alpha_{s}}(a)=\alpha_{s^{\prime}}(a^{\prime})$. In the third equality, we have reused the definition of the lifted policy. Thus we see that, written in this way, the lifted policy is invariant under state-action transformations $({L_{g}},{K_{g}^{s}})$. This equation is very general and applies for all group-structured state-action transformations. For a finite action space, this statement of invariance can be re-expressed as a statement of equivariance, by considering the vectorized policy.

Invariant Policies On Finite Action Spaces Are Equivariant Vectorized Policies For convenience we introduce a vector of probabilities for each of the discrete actions under the policy

where $a_{1},...,a_{N}$ are the $N$ possible discrete actions in action space ${\mathcal{A}}$. The action transformation ${K_{g}^{s}}$ maps actions to actions invertibly. Thus applying an action transformation to the vectorized policy permutes the elements. We write the corresponding permutation matrix as ${\textbf{K}}_{g}$. Note that

where writing the inverse ${\textbf{K}}_{g}^{-1}$ instead of ${\textbf{K}}_{g}$ is required to maintain the property ${\textbf{K}}_{g}{\textbf{K}}_{h}={\textbf{K}}_{gh}$. The invariance of the lifted policy can then be written as $\bm{\pi}^{\uparrow}(s)={\textbf{K}}_{g}^{-1}\bm{\pi}^{\uparrow}({L_{g}}[s])$, which can be rearranged to the equivariance equation

This equation shows that the lifted policy must satisfy an equivariance constraint. In deep learning, this has already been well-explored in the context of supervised learning cohen2016group; cohen2016steerable; worrall2017harmonic; worrall2019deep; weiler2018learning. Next, we present a novel way to construct such networks.

2 Building MDP Homomorphic Networks

Our goal is to build neural networks that follow Eq. 13; that is, we wish to find neural networks that are equivariant under a set of state and policy transformations. Equivariant networks are common in supervised learning cohen2016group; cohen2016steerable; worrall2017harmonic; worrall2019deep; weiler2018learning; weiler2019general. For instance, in semantic segmentation shifts and rotations of the input image result in shifts and rotations in the segmentation. A neural network consisting of only equivariant layers and non-linearities is equivariant as a whole, too See Appendix B for more details. cohen2016group. Thus, once we know how to build a single equivariant layer, we can simply stack such layers together. Note that this is true regardless of the representation of the group, i.e. this works for spatial transformations of the input, feature map permutations in intermediate layers, and policy transformations in the output layer. For the experiments presented in this paper, we use the same group representations for the intermediate layers as for the output, i.e. permutations. For finite groups, such as cyclic groups or permutations, pointwise nonlinearities preserve equivariance cohen2016group.

In the past, learnable equivariant layers were designed by hand for each transformation group individually cohen2016group; cohen2016steerable; worrall2017harmonic; worrall2019deep; winkels20183d; weiler2018learning; weiler2019general. This is time-consuming and laborious. Here we present a novel way to build learnable linear layers that satisfy equivariance automatically.

Since this equation is true for all z we can in fact drop z entirely. Our task now is to find all weights W which satisfy Equation 14. We label this space of equivariant weights as ${\mathcal{W}}$, defined as

again noting that we have dropped z. To find the space ${\mathcal{W}}$ notice that for each $g\in G$ the constraint ${\textbf{K}_{g}}{\textbf{W}}={\textbf{W}}{\textbf{L}_{g}}$ is in fact linear in W. Thus, to find ${\mathcal{W}}$ we need to solve a set of linear equations in W. For this we introduce a construction, which we call a symmetrizer $S({\textbf{W}})$. The symmetrizer is

$S$ has three important properties, of which proofs are provided in Appendix A. First, $S({\textbf{W}})$ is symmetric ($S({\textbf{W}})\in{\mathcal{W}}$). Second, $S$ fixes any symmetric W: (${\textbf{W}}\in{\mathcal{W}}\implies S({\textbf{W}})={\textbf{W}}$). These properties show that $S$ projects arbitrary ${\textbf{W}}\in{\mathcal{W}_{\text{total}}}$ to the equivariant subspace ${\mathcal{W}}$.

Since ${\mathcal{W}}$ is the solution set for a set of simultaneous linear equations, ${\mathcal{W}}$ is a linear subspace of the space of all possible weights ${\mathcal{W}_{\text{total}}}$. Thus each ${\textbf{W}}\in{\mathcal{W}}$ can be parametrized as a linear combination of basis weights $\{{\textbf{V}}_{i}\}_{i=1}^{r}$, where $r$ is the rank of the subspace and $\text{span}(\{{\textbf{V}}_{i}\}_{i=1}^{r})={\mathcal{W}}$. To find as basis for W, we take a Gram-Schmidt orthogonalization approach. We first sample weights in the total space ${\mathcal{W}_{\text{total}}}$ and then project them into the equivariant

subspace with the symmetrizer. We do this for multiple weight matrices, which we then stack and feed through a singular value decomposition to find a basis for the equivariant space. This procedure is outlined in Algorithm 1. Any equivariant layer can then be written as a linear combination of bases

where the $c_{i}$’s are learnable scalar coefficients, $r$ is the rank of the equivariant space, and the matrices ${\textbf{V}}_{i}$ are the basis vectors, formed from the reshaped right-singular vectors in the SVD. An example is shown in Figure 3. To run this procedure, all that is needed are the transformation operators ${\textbf{L}_{g}}$ and ${\textbf{K}_{g}}$. Note we do not need to know the explicit transformation matrices, but just to be able to perform the mappings ${\textbf{W}}\mapsto{\textbf{W}}{\textbf{L}_{g}}$ and ${\textbf{W}}\mapsto{\textbf{K}_{g}^{-1}}{\textbf{W}}$. For instance, some matrix ${\textbf{L}_{g}}$ rotates an image patch, but we could equally implement ${\textbf{W}}{\textbf{L}_{g}}$ using a built-in rotation function. Code is available https://github.com/ElisevanderPol/symmetrizer/.

Experiments

We evaluated three flavors of MDP homomorphic network—an MLP, a CNN, and an equivariant feature extractor—on three RL tasks that exhibit group symmetry: CartPole, a grid world, and Pong. We use RLPYT stooke2019rlpyt for the algorithms. Hyperparameters (and the range considered), architectures, and group implementation details are in the Supplementary Material. Code is available https://github.com/ElisevanderPol/mdp-homomorphic-networks.

For each environment we show ${\mathcal{S}}$ and ${\mathcal{A}}$ with respective representations of the group transformations.

CartPole In the classic pole balancing task barto1983neuronlike, we used a two-element group of reflections about the $y$-axis. We used OpenAI’s Cartpole-v1 brockman2016openai implementation, which has a 4-dimensional observation vector: (cart position $x$, pole angle $\theta$, cart velocity $\dot{x}$, pole velocity $\dot{\theta}$). The (discrete) action space consists of applying a force left and right $(\leftarrow,\rightarrow)$. We chose this example for its simple symmetries.

Grid world We evaluated on a toroidal 7-by-7 predator-prey grid world with agent-centered coordinates. The prey and predator are randomly placed at the start of each episode, lasting a maximum of 100 time steps. The agent’s goal is to catch the prey, which takes a step in a random compass direction with probability $0.15$ and stands still otherwise. Upon catching the prey, the agent receives a reward of +1, and -0.1 otherwise. The observation is a $21\times 21$ binary image identifying the position of the agent in the center and the prey in relative coordinates. See Figure 6(a). This environment was chosen due to its four-fold rotational symmetry.

Pong We evaluated on the RLPYT stooke2019rlpyt implementation of Pong. In our experiments, the observation consisted of the 4 last observed frames, with upper and lower margins cut off and downscaled to an $80\times 80$ grayscale image. In this setting, there is a flip symmetry over the horizontal axis: if we flip the observations, the up and down actions also flip. A curious artifact of Pong is that it has duplicate (up, down) actions, which means that to simplify matters, we mask out the policy values for the second pair of (up, down) actions. We chose Pong because of its higher dimensional state space. Finally, for Pong we additionally compare to two data augmentation baselines: stochastic data augmentation, where for each state, action pair we randomly transform them or not before feeding them to the network, and the second an equivariant version of kostrikov2020image and similar to silver2016mastering, where both state and transformed state are input to the network. The output of the transformed state is appropriately transformed, and both policies are averaged.

2 Models

We implemented MDP homomorphic networks on top of two base architectures: MLP and CNN (exact architectures in Supplementary). We further experimented with an equivariant feature extractor, appended by a non-equivariant network, to isolate where equivariance made the greatest impact.

Basis Networks We call networks whose weights are linear combinations of basis weights basis networks. As an ablation study on all equivariant networks, we sought to measure the effects of the basis training dynamics. We compared an equivariant basis against a pure nullspace basis, i.e. an explicitly non-symmetric basis using the right-null vectors from the equivariant layer construction, and a random basis, where we skip the symmetrization step in the layer construction and use the full rank basis. Unless stated otherwise, we reduce the number of ‘channels’ in the basis networks compared to the regular networks by dividing by the square root of the group size, ending up with a comparable number of trainable parameters.

3 Results and Discussion

We show training curves for CartPole in 4(a)-4(b), Pong in Figure 4(c) and for the grid world in Figure 6. Across all experiments we observed that the MDP homomorphic network outperforms both the non-equivariant basis networks and the standard architectures, in terms of convergence speed.

This confirms our motivations that building symmetry-preserving policy networks leads to faster convergence. Additionally, when compared to the data augmentation baselines in Figure 5, using equivariant networks is more beneficial. This is consistent with other results in the equivariance literature bekkers2018roto; weiler_2018; winkels20183d; worrall2017harmonic. While data augmentation can be used to create a larger dataset by exploiting symmetries, it does not directly lead to effective parameter sharing (as our approach does). Note, in Pong we only train the first 15 million frames to highlight the difference in the beginning; in constrast, a typical training duration is 50-200 million frames mnih2016asynchronous; stooke2019rlpyt.

For our ablation experiment, we wanted to control for the introduction of bases. It is not clear a priori that a network with a basis has the same gradient descent dynamics as an equivalent ‘basisless’ network. We compared equivariant, non-equivariant, and random bases, as mentioned above. We found the equivariant basis led to the fastest convergence. Figures 4(a) and 4(c) show that for CartPole and Pong the nullspace basis converged faster than the random basis. In the grid world there was no clear winner between the two. This is a curious result, requiring deeper investigation in a follow-up.

For a third experiment, we investigated what happens if we sacrifice complete equivariance of the policy. This is attractive because it removes the need to find a transformation operator for a flattened output feature map. Instead, we only maintained an equivariant feature extractor, compared against a basic CNN feature extractor. The networks built on top of these extractors were MLPs. The results, in Figure 4(c), are two-fold: 1) Basis feature extractors converge faster than standard CNNs, and 2) the equivariant feature extractor has fastest convergence. We hypothesize the equivariant feature extractor is fastest as it is easiest to learn an equivariant policy from equivariant features. We have additionally compared an equivariant feature extractor to a regular convolutional network on the Atari game Breakout, where the difference between the equivariant network and the regular network is much less pronounced. For details, see Appendix C.

Related Work

Past work on MDP homomorphisms has often aimed at discovering the map itself based on knowledge of the transition and reward function, and under the assumption of enumerable state spaces ravindran2001symmetries; ravindran2003smdp; ravindran2004approximate; taylor2009bounding. Other work relies on learning the map from sampled experience from the MDP van2020plannable; biza2019online; mahajan2017symmetry. Exactly computing symmetries in MDPs is graph isomorphism complete narayanamurthy2008hardness even with full knowledge of the MDP dynamics. Rather than assuming knowledge of the transition and reward function, and small and enumerable state spaces, in this work we take the inverse view: we assume that we have an easily identifiable transformation of the joint state–action space and exploit this knowledge to learn more efficiently. Exploiting symmetries in deep RL has been previously explored in the game of Go, in the form of symmetric filter weights schraudolph1994temporal; clark2014teaching or data augmentation silver2016mastering. Other work on data augmentation increases sample efficiency and generalization on well-known benchmarks by augmenting existing data points state transformations such as random translations, cutout, color jitter and random convolutions kostrikov2020image; cobbe2019quantifying; laskin2020reinforcement; lee2019network. In contrast, we encode symmetries into the neural network weights, leading to more parameter sharing. Additionally, such data augmentation approaches tend to take the invariance view, augmenting existing data with state transformations that leave the state’s Q-values intact kostrikov2020image; cobbe2019quantifying; laskin2020reinforcement; lee2019network (the exception being lin2020invariant and mavalankar2020goal, who augment trajectories rather than just states). Similarly, permutation invariant networks are commonly used in approaches to multi-agent RL sukhbaatar2016learning; liu2020pic; jiang2018graph. We instead take the equivariance view, which accommodates a much larger class of symmetries that includes transformations on the action space. Abdolhosseini et al. abdolhosseini2019learning have previously manually constructed an equivariant network for a single group of symmetries in a single RL problem, namely reflections in a bipedal locomotion task. Our MDP homomorphic networks allow for automated construction of networks that are equivariant under arbitrary discrete groups and are therefore applicable to a wide variety of problems.

From an equivariance point-of-view, the automatic construction of equivariant layers is new. cohen2016steerable comes close to specifying a procedure, outlining the system of equations to solve, but does not specify an algorithm. The basic theory of group equivariant networks was outlined in cohen2016group; cohen2016steerable and cohen_homo_2019, with notable implementations to 2D roto-translations on grids worrall2017harmonic; weiler2018learning; weiler2019general and 3D roto-translations on grids Worrall_2018_ECCV; winkels20183d; weiler_2018. All of these works have relied on hand-constructed equivariant layers.

Conclusion

This paper introduced MDP homomorphic networks, a family of deep architectures for reinforcement learning problems where symmetries have been identified. MDP homomorphic networks tie weights over symmetric state-action pairs. This weight-tying leads to fewer degrees-of-freedom and in our experiments we found that this translates into faster convergence. We used the established theory of MDP homomorphisms to motivate the use of equivariant networks, thus formalizing the connection between equivariant networks and symmetries in reinforcement learning. As an innovation, we also introduced the first method to automatically construct equivariant network layers, given a specification of the symmetries in question, thus removing a significant implementational obstacle. For future work, we want to further understand the symmetrizer and its effect on learning dynamics, as well as generalizing to problems that are not fully symmetric.

Acknowledgments and Funding Disclosure

Elise van der Pol was funded by Robert Bosch GmbH. Daniel Worrall was funded by Philips. F.A.O. received funding from the European Research Council (ERC)

under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 758824 —INFLUENCE). Max Welling reports part-time employment at Qualcomm AI Research.

Broader Impact

The goal of this paper is to make (deep) reinforcement learning techniques more efficient at solving Markov decision processes (MDPs) by making use of prior knowledge about symmetries. We do not expect the particular algorithm we develop to lead to immediate societal risks. However, Markov decision processes are very general, and can e.g. be used to model problems in autonomous driving, smart grids, and scheduling. Thus, solving such problems more efficiently can in the long run cause positive or negative societal impact.

For example, making transportation or power grids more efficient, thereby making better use of scarce resources, would be a significantly positive impact. Other potential applications, such as in autonomous weapons, pose a societal risk future2015autonomous. Like many AI technologies, when used in automation, our technology can have a positive impact (increased productivity) and a negative impact (decreased demand) on labor markets.

More immediately, control strategies learned using RL techniques are hard to verify and validate. Without proper precaution (e.g. wabersich2018linear), employing such control strategies on physical systems thus run the risk of causing accidents involving people, e.g. due to reward misspecification, unsafe exploration, or distributional shift amodei2016concrete.

References

Appendix A The Symmetrizer

In this section we prove three properties of the symmetrizer: the symmetric property ($S({\textbf{W}})\in{\mathcal{W}}$ for all ${\textbf{W}}\in{\mathcal{W}_{\text{total}}}$ ), the fixing property (${\textbf{W}}\in{\mathcal{W}}\implies S({\textbf{W}})={\textbf{W}}$) , and the idempotence property ($S(S({\textbf{W}}))=S({\textbf{W}})$ for all ${\textbf{W}}\in{\mathcal{W}_{\text{total}}}$).

Here we show that the symmetrizer $S$ maps matrices ${\textbf{W}}\in{\mathcal{W}_{\text{total}}}$ to equivariant matrices $S({\textbf{W}})\in{\mathcal{W}}$. For this, we show that a symmetrized weight matrix $S({\textbf{W}})$ from Equation 16 satisfies the equivariance constraint of Equation 14.

We begin by recalling the equivariance constraint

Now note that we can drop the dependence on z, since this equation is true for all z. At the same time, we left-multiply both sides of this equation by ${\textbf{K}_{g}}^{-1}$, which is possible because group representations are invertible. This results in the following set of equations

Any W satisfying this equation satisfies Equation 18 and is thus a member of ${\mathcal{W}}$. To show that $S({\textbf{W}})$ is a member of ${\mathcal{W}}$, we thus would need show that $S({\textbf{W}})={\textbf{K}_{g}^{-1}}S({\textbf{W}}){\textbf{L}_{g}}$ for all ${\textbf{W}}\in{\mathcal{W}_{\text{total}}}$ and $g\in G$. This can be shown as follows:

Thus we see that $S({\textbf{W}})$ satisfies the equivariance constraint, which implies that $S({\textbf{W}})\in{\mathcal{W}}$. ∎

The Fixing Property

For the symmetrizer to be useful, we need to make sure that its range covers the equivariant subspace ${\mathcal{W}}$, and not just a subset of it; that is, we need to show that

We show this by picking a matrix ${\textbf{W}}\in{\mathcal{W}}$ and showing that ${\textbf{W}}\in{\mathcal{W}}\implies S({\textbf{W}})={\textbf{W}}$.

We begin by assuming that ${\textbf{W}}\in{\mathcal{W}}$, then

This means that the symmetrizer leaves the equivariant subspace invariant. In fact, the statement we just showed is stronger in saying that each point in the equivariant subspace is unaltered by the symmetrizer. In the language of group theory we say that subspace ${\mathcal{W}}$ is fixed under $G$. Since $S:{\mathcal{W}_{\text{total}}}\to{\mathcal{W}}$ and there exist matrices W such that for every ${\textbf{W}}\in{\mathcal{W}}$, $S({\textbf{W}})={\textbf{W}}$, we have shown that

The Idempotence Property

Here we show that the symmetrizer $S({\textbf{W}})$ from Equation 16 is idempotent, $S(S({\textbf{W}}))$.

Thus we see that $S({\textbf{W}})$ satisfies the equivariance constraint, which implies that $S({\textbf{W}})\in{\mathcal{W}}$. ∎

Appendix B Experimental Settings

In the main text we presented a method to construct a space of intertwiners ${\mathcal{W}}$ using the symmetrizer. This relies on us already having chosen specific representations/transformation operators for the input, the output, and for every intermediate layer of the MDP homomorphic networks. While for the input space (state space) and output space (policy space), these transformation operators are easy to define, it is an open question how to design a transformation operator for the intermediate layers of our networks. Here we give some rules of thumb that we used, followed by the specific transformation operators we used in our experiments.

For each experiment we first identified the group $G$ of transformations. In every case, this was a finite group of size $|G|$, where the size is the number of elements in the group (number of distinct transformation operators). For example, a simple flip group as in Pong has two elements, so $|G|=2$. Note that the group size $|G|$ does not necessarily equal the size of the transformation operators, whose size is determined by the dimensionality of the input/activation layer/policy.

If we stack equivariant layers, the resulting network is equivariant as a whole too . To see that this is the case, consider the following example. Assume we have network $f$, consisting of layers $f_{1}$ and $f_{2}$, which satisfy the layer-wise equivariance constraints:

With $K_{g}$ the output transformation of the network, $L_{g}$ the input transformation, and $P_{g}$ the intermediate transformation. Now,

and so the whole network $f$ is equivariant with regards to the input transformation $L_{g}$ and the output transformation $K_{g}$. Note that this depends on the intermediate representation $P_{g}$ being shared between layers, i.e. $f_{1}$’s output transformation is the same as $f_{2}$’s input transformation.

MLP-structured networks

For MLP-structured networks (CartPole), typically the activations have shape [batch_size, num_channels]. Instead we used a shape of [batch_size, num_channels, representation_size], where for the intermediate layers representation_size=|G|+1 (we have a +1 because of the bias). The transformation operators we then apply to the activations is the set of permutations for group size $|G|$ appended with a 1 on the diagonal for the bias, acting on this last ‘representation dimension’. Thus a forward pass of a layer is computed as

CNN-structured networks

For CNN-structured networks (Pong and Grid World), typically the activations have shape [batch_size, num_channels, height, width]. Instead we used a shape of [batch_size, num_channels, representation_size, height, width], where for the intermediate layers representation_size=|G|+1. The transformation operators we apply to the input of the layer is a spatial transformation on the height, width dimensions and a permutation on the representation dimension. This is because in the intermediate layers of the network the activations do not only transform in space, but also along the representation dimensions of the tensor. The transformation operators we apply to the output of the layer is just a permutation on the representation dimension. Thus a forward pass of a layer is computed as

B.2 Cartpole-v1

For values we require an invariant rather than equivariant output. This invariance is implemented by defining the output representations to be $|G|$ identity matrices of the desired output dimensionality. For predicting state values we required a 1-dimensional output, and we thus used $|G|$ 1-dimensional identity matrices, i.e. for value output $V$:

Hyperparameters

For both the basis networks and the MLP, we used Xavier initialization. We trained PPO using ADAM on 16 parallel environments and fine-tuned over the learning rates $\{0.01,0.05,0.001,0.005,0.0001,0.0003,0.0005\}$ by running 25 random seeds for each setting, and report the best curve. The final learning rates used are shown in Table 2. Other hyperparameters were defaults in RLPYT , except that we turn off learning rate decay.

Architecture

B.3 GridWorld

For states we use numpy.rot90. The stack of weights is rolled.

Hyperparameters

For both the basis networks and the CNN, we used He initialization. We trained A2C using ADAM on 16 parallel environments and fine-tuned over the learning rates $\{0.00001,0.00003,0.0001,0.0003,0.001,0.003\}$ on 20 random seeds for each setting, and reporting the best curve. The final learning rates used are shown in Table 3. Other hyperparameters were defaults in RLPYT .

Architecture

B.4 Pong

For the states we use numpy’s indexing to flip the input, i.e. w = w[..., ::-1, :], then the permutation on the representation dimension of the weights is a numpy.roll, since the group is cyclic.

Hyperparameters

For both the basis networks and the CNN, we used He initialization. We trained A2C using ADAM on 4 parallel environments and fine-tuned over the learning rates $\{0.0001,0.0002,0.0003\}$ on 15 random seeds for each setting, and reporting the best curve. The learning rates to fine-tune over were selected to be close to where the baseline performed well in preliminary experiments. The final learning rates used are shown in Table 4. Other hyperparameters were defaults in RLPYT .

Architecture

Appendix C Breakout Experiments

We evaluated the effect of an equivariant basis extractor on Breakout, compared to a baseline convolutional network. The hyperparameter settings and architecture were largely the same as those of Pong, except for the input group representation, a longer training time, and that we considered a larger range of learning rates. To ensure symmetric states, we remove the two small decorative blocks in the bottom corners.

For the states we use numpy’s indexing to flip the input, i.e. w = w[..., :, ::-1] (note the different axis than in Pong), then the permutation on the representation dimension of the weights is a numpy.roll, since the group is cyclic.

Hyperparameters

We used He initialization. We trained A2C using ADAM on 4 parallel environments and fine-tuned over the learning rates $\{0.001,0.005,0.0001,0.0002,0.0003,0.0004,0.0005,0.00001,0.00005\}$ on 15 random seeds for each setting, and reporting the best curve. The final learning rates used are shown in Table 5. Other hyperparameters were defaults in RLPYT .

Results

Figure 7 shows the result of the equivariant feature extractor versus the convolutional baseline. While we again see an improvement over the standard convolutional approach, the difference is much less pronounced than in CartPole, Pong or the grid world. It is not straightforward why. One factor could be that the equivariant feature extractor is not end-to-end MDP homomorphic. It instead outputs a type of MDP homomorphic state representations and learns a regular policy on top. As a result, the unconstrained final layers may negate some of the advantages of the equivariant feature extractor. This may be more of an issue for Breakout than Pong, since Breakout is a more complex game.

Appendix D Cartpole-v1 Deeper Network Results

We show the effect of training a deeper network – 4 layers instead of 2 – for CartPole-v1 in Figure 8. The performance of the regular depth networks in Figure 4b and the deeper networks in Figure 8 is comparable, except that for the regular MLP, the variance is much higher when using deeper networks.

Appendix E Bellman Equations