Computer Science
Computer Science-2021.gz:143323
Computer Science
bd6b81b271d1ac7efaa92d3a448a74b48822f7bf
More Efficient Exploration with Symbolic Priors on Action Sequence Equivalences

Incorporating prior knowledge in reinforcement learning algorithms is mainly an open question. Even when insights about the environment dynamics are available, reinforcement learning is traditionally used in a tabula rasa setting and must explore and learn everything from scratch. In this paper, we consider the problem of exploiting priors about action sequence equivalence: that is, when different sequences of actions produce the same effect. We propose a new local exploration strategy calibrated to minimize collisions and maximize new state visitations. We show that this strategy can be computed at little cost, by solving a convex optimization problem. By replacing the usual epsilon-greedy strategy in a DQN, we demonstrate its potential in several environments with various dynamic structures.


INTRODUCTION
Despite the rapidly improving performance of Reinforcement Learning (RL) agents on a variety of tasks (Mnih et al., 2015;Silver et al., 2016), they remain largely sample-inefficient learners compared to humans (Toromanoff et al., 2019). Contributing to this is the vast amount of prior knowledge humans bring to the table before their first interaction with a new task, including an understanding of physics, semantics, and affordances (Dubey et al., 2018).
The considerable quantity of data necessary to train agents is becoming more problematic as RL is applied to ever more challenging and complex tasks. Much research aims at tackling this issue, for example through transfer learning (Rusu et al., 2016), meta learning, and hierarchical learning, where agents are encouraged to use what they learn in one environment to solve a new task more quickly. Other approaches attempt to use the structure of Markov Decision Processes (MDP) to accelerate learning without resorting to pretraining. Mahajan & Tulabandhula (2017) and Biza & Jr. (2019) learn simpler representations of MDPs that exhibit symmetrical structure, while van der Pol et al. (2020) show that environment invariances can be hard-coded into equivariant neural networks.
A fundamental challenge standing in the way of improved sample efficiency is exploration. We consider a situation where the exact transition function of a Markov Decision Process is unknown, but some knowledge of its local dynamics is available under the form of a prior expectation that given sequences of actions have identical results. This way of encoding prior knowledge is sufficiently flexible to describe many useful environment structures, particularly when actions correspond to agent movement. For example, in a gridworld (called RotationGrid hereafter) where the agent can move forward (↑) and rotate 90 • to the left ( ) or to the right ( ), the latter two actions are the inverse of each other, in that performing one undoes the effect of the other. During exploration, to encourage the visitation of not yet seen states, it is natural to simply ban sequences of actions that revert to previously visited states, following the reasoning of Tabu search (Glover, 1986). We observe further that and both lead to the same state (represented as state 4 in Figure 1). If actions

Graph Construction
Action Probability Inference Input Figure 1: Illustration of EASEE on RotationGrid environment. The input is information about the dynamics of the environment known in advance under the form of action sequence equivalences (Λ denotes the empty action sequence). This is used to construct a representation of all the unique states that can be visited in 3 steps. The probabilities of sampling each action are then determined to explore as uniformly as possible. The probabilities of visiting each unique state are displayed on the right.
were uniformly sampled, the chances of visiting this state would be much higher than any of the others. Based on these observations, we introduce a new method taking advantage of Equivalent Action SEquences for Exploration (EASEE), an overview of which can be found in Figure 1. EASEE looks ahead several steps and calculates action sampling probabilities to explore as uniformly as possible new states conditionally on the action sequence equivalences given to it. It constructs a partial MDP which corresponds to a local representation of the true MDP around the current state. We then formulate the problem of determining the best distribution over action sequences as a linearly constrained convex optimization problem. Solving this optimization problem is computationally inexpensive and can be done once and for all before learning begins, providing a principled and tractable exploration policy that takes into account environment structure. This policy can easily be injected into existing reinforcement learning algorithms as a substitute for -greedy exploration.
Our contribution is threefold. First, we formally introduce the notion of equivalent action sequences, a novel type of structure in Markov Decision Processes. Then, we show that priors on this type of structure can easily be exploited during offline exploration by solving a convex optimization problem. Finally, we provide experimental insights and show that incorporating EASEE into a DQN (Mnih et al., 2015) improves agent performance in several environments with various structures.

RELATED WORK
Curiosity-driven Exploration The problem of ensuring that agents see sufficiently diverse states has received a lot of attention from the RL community. Many methods rely on intrinsic rewards (Schmidhuber, 1991;Chentanez et al., 2005;Şimşek & Barto, 2006;Lopes et al., 2012;Bellemare et al., 2016;Ostrovski et al., 2017;Pathak et al., 2017) to entice agents to unseen or misunderstood areas. In the tabular setting, these take the form of count-based exploration bonuses which guide the agent toward poorly visited states (e.g. Strehl & Littman (2008)). Scaling this method requires the use of function approximators (Burda et al., 2019;Badia et al., 2020;Flet-Berliac et al., 2021). Unlike EASEE, these methods necessitate the computation of non-stationary and vanishing novelty estimates, which require careful tuning to balance learning stability and exploration incentives. Moreover, because these bonuses are learned, and do not allow for the use of prior structure knowledge, they constitute an orthogonal approach to ours.

Redundancies in Trajectories
The idea that different trajectories can overlap and induce redundancies in state visitation is used in Leurent & Maillard (2020) and Czech et al. (2020) in the case of Monte-Carlo tree search. However, they require a generative model, and propose a new Bellman operator to update node values according to newly uncovered transitions rather than modifying exploration. Closer to our work, Caselles-Dupré et al. (2020) study structure in action sequences, but restrict themselves to commutative properties. Tabu search (Glover, 1986) is a meta-heuristic which uses knowledge of the past to escape local optima. It is popular for combinatorial optimization (Hertz & Werra, 2005). Like our approach, it relies on a local structure: actions which are known to cancel out recent moves are deemed tabu, and are forbidden for a short period of time. This prevents cycling around already found solutions, and thus encourages exploration. In Abramson & Wechsler (2003), tabu search is combined with reinforcement learning, using action priors. However, their method cannot make use of more complex action-sequence structure.
Maximum State-Visitation Entropy Our goal to explore as uniformly as possible every nearby state can be seen as a local version of the Maximum State-Visitation Entropy problem (MSVE) (de Farias & Van Roy, 2003;Hazan et al., 2019;Lee et al., 2019;Guo et al., 2021). MSVE formulates exploration as a policy optimization problem whose solution maximizes the entropy of the distribution of visited states. Although some of these works (Hazan et al., 2019;Lee et al., 2019;Guo et al., 2021) can make use of priors about state similarities, they learn a global policy and cannot exploit structure in action sequences.
Action Space Structure The idea of exploiting structure in action spaces is not new. Large discrete action spaces may be embedded in continuous action spaces either by leveraging prior information (Dulac-Arnold et al., 2016) or learning representations (Chandak et al., 2019). Tavakoli et al. (2018) manage high-dimensional action spaces by assuming a degree of independence between each dimension. These methods aim to improve the generalization of policies to unseen actions rather than enhancing exploration. Tennenholtz & Mannor (2019) provide an understanding of actions through their context in demonstrations. Farquhar et al. (2020) introduce a curriculum of progressively growing action spaces to accelerate learning. Certain characteristics of actions, such as reversibility, can be learned through training, as in Grinsztajn et al. (2021).

EQUIVALENCE OVER ACTION SEQUENCES
We consider a Markov Decision Process (MDP) defined as a 5-tuple M = (S, A, T, R, γ), with S the set of states, A the action set, T the transition function, R the reward function and the discount factor γ. The set of actions is assumed to be finite |A| < ∞. We restrict ourselves to deterministic MDPs. A possible extension to MDPs with stochastic dynamics is discussed in Appendix A.6.
In the following, the notations are borrowed from formal language theory. Sequences of actions are analogous to strings over the set of symbols A (possible actions). The set of all possible sequences of actions is denoted A = ∞ k=0 A k where A k is the set of all sequences of length k and A 0 contains as single element the empty sequence Λ. We use . for the concatenation operator, such that for v 1 ∈ A h1 , v 2 ∈ A h2 , v 1 .v 2 ∈ A h1+h2 . The transition function T : S × A → S gives the next state s when action a is taken in state s: T (s, a) = s . We recursively extend this operator to action sequences T : S × A → S such that, ∀s ∈ S, ∀a ∈ A, ∀w ∈ A : Intuitively, this operator gives the new state of the MDP after a sequence of actions is performed from state s.
Definition 1 (Equivalent sequences). We say that two action sequences a 1 . . . a n and a 1 . . . a m ∈ A are equivalent at state s ∈ S if T (s, a 1 . . . a n ) = T (s, a 1 . . . a m ) (1) Two sequences of actions are equivalent over M if they are equivalent at state s for all s in S. This is written: a 1 . . . a n ∼ M a 1 . . . a m This means that we consider two sequences of actions to be equivalent when following one or the other will always lead to the same state. When the considered MDP M is unambiguous, we simplify the notation by writing ∼ instead of ∼ M .
We argue that some priors about the environments can be easily encoded as a small set of action sequence equivalences. For example, we may know that going left then right is the same thing as going right then left, that rotating two times to the left is the same thing as rotating two times to the right, or that opening a door twice is the same thing as opening the door once. All these priors can be encoded as a set of equivalences: Definition 2 (Equivalence set). Given a MDP M and several equivalent sequence Formally, Ω is a set of pairs of elements of A , such that Ω ⊂ (A ) 2 . By abuse of notation, we write Intuitively, it is clear that action sequence equivalences can be combined to form new, longer equivalences. For example, knowing that going left then right is the same thing as going right then left, we can deduce that going two times left then two times right is the same thing as going two times right then two times left. In the same fashion, if opening a door twice produces the same effect as opening it once, opening three times the door does the same. We formalize these notions in what follows. First, we note that equivalent sequences can be concatenated. Proposition 1. If we have two pairs of equivalent sequences over M, i.e. w 1 , then the concatenation of the sequences are also equivalent sequences: The proof is given in Appendix A.1. We are now going to define formally the fact that the equivalence of two sequences can be deduced from an equivalence set Ω. We first consider the previous example where an action a has the effect of opening a door, such that a.a ∼ a. We can then write a.a.a ∼ (a.a).a ∼ (a).a ∼ a.a ∼ a by applying two times the equivalence a.a ∼ a and rearranging the parentheses. More generally and intuitively, the equivalence of two action sequences v and w can be deduced from Ω, which we denote v ∼ Ω w, if v can be changed into w iteratively, chaining equivalences of Ω.
More formally, we write v ∼ 1 Ω w if v can be changed to w in one step, meaning: Finally, we say that v ∼ Ω w if there is n ∈ N such that v can be changed into w in n steps. The relation ∼ Ω is thus a formal way of extending equivalences from a fixed equivalence set Ω, and at first glance not connected with ∼, which deals with the equivalences of the MDP dynamics. We now show a connection between the two notions. Theorem 1. Given an equivalence set Ω, ∼ Ω is an equivalence relationship. Furthermore, for The proof is given in Appendix A.2. Given this relation between ∼ and ∼ Ω , we will simplify the notation in what follows by writing ∼ instead of ∼ Ω when the equivalence set considered is unambiguous. As ∼ Ω is an equivalence relationship, it provides a partition over action sequences: two action sequences in the same set lead to the same final state from any given state.

LOCAL-DYNAMICS GRAPH
We leverage the equivalences defined above to determine a model of the MDP up to a few timesteps. As traditionally done in Monte-Carlo Tree Search (Coulom, 2007), an MDP (S, A, T, R, γ) with deterministic dynamics can be locally unrolled to produce a tree, where a node of depth h represents a sequence of actions v ∈ A h , and the edges represent transitions between such sequences. The root of the tree corresponds to the empty action sequence Λ. Here we adopt the same formalism, except that equivalent sequences will point to the same node.
Given a tree T of depth d ∈ N corresponding to a partial unrolling of sequences in A , and an equivalence set Ω, we call local-dynamics graph of depth d under equivalence Ω the graph G = (V, E) corresponding to the tree T where nodes are quotiented with the equivalence relation ∼ Ω . Intuitively, it means that nodes corresponding to equivalent action sequences are merged. In this case, the resulting graph is not necessarily a tree. In the following, unless the distinction is necessary, we identify action sequences with their equivalence classes.
The graph G gives rise to a new, smaller MDP resulting from M: the state space V is the set of action sequences smaller than d quotiented by the equivalence relation ∼ Ω , the action space A is untouched. Given a node n corresponding to a sequence w ∈ A , and an action a ∈ A, T (n, a) is the node representing the sequence w.a ∈ A . Nodes representing sequences of length exactly d are final states. The initial state v 0 is the empty sequence Λ. This MDP represents the local dynamics induced by ∼ Ω from a given root state. We detail in the next section how to construct such graphs in practice, and how to use these sub-MDPs for a better exploration.

FROM EQUIVALENT ACTIONS TO LOCAL-DYNAMICS GRAPH
Producing the local-dynamics graph involves considering all possible action sequences and merging those that are equivalent. Figure 2 illustrates the construction of a local-dynamics graph, given A = {a 1 , a 2 } and Ω = {a 1 a 1 ∼ Λ, a 2 a 1 ∼ a 1 a 2 }. Starting from the root node 0 (first step), we iteratively expand the graph by unrolling the nodes at the edges of the graph. Steps 2 and 3 create nodes 1 and 2 corresponding to action sequences a 1 and a 2 respectively. In a tree, the expansion of a node corresponding to a sequence w ∈ A h with the action a ∈ A always leads to the creation of a new leaf that results from the sequence of actions w.a ∈ A h+1 . However, in a local-dynamics graph the node representing w.a might already be present, in which case we add an edge from w without creating a new node. In Figure 2, this case occurs at the 4 th and the 6 th construction steps. The first case corresponds to adding the action a 1 to the node 1, which represents the action sequence a 1 .a 1 . Since a 1 .a 1 ∼ Λ ∈ Ω, we simply add an edge from 1 to 0. The second case occurs when expanding node 2 with the action a 1 , leading to the action sequence a 2 .a 1 ∼ Ω a 1 .a 2 . Since node 3 already represents a 1 .a 2 , we simply add an edge from node 2 to node 3. As a final construction step, we prune edges which go backward in the local-dynamics graph, like (1, 0) in Fig. 2, such that the resulting graph is a DAG. This is motivated by the fact that we are interested in finding a good exploration policy: an action which takes us back to a previously visited state should be ignored.
From a practical point of view, the graph construction algorithm takes as input the action set A, the sequence equivalence set Ω, and the desired depth d, and outputs a DAG. Informally, it starts from a graph G = (V, E) reduced to a root state {0} and iteratively expands G until a distance d to the root is reached. We store in each node every action sequence which allows to reach it from any parent nodes. For example, in Fig.2, the node 3 can be reached from the node 0 with sequences {a 1 .a 2 , a 2 .a 1 }, from node 1 with sequence {a 2 } and from node 2 with sequence {a 1 }, thus the set of sequences stored in node 3 would be {a 1 , a 2 , a 1 .a 2 , a 2 .a 1 }. When expanding a node n with an action a ∈ A, we check every sequence w stored in n if w.a appears in Ω, and if a node corresponding to an equivalent sequence of w.a is already in V . If it is the case, we simply add an edge from n to this node, otherwise we create a new node representing w.a. In practice, this algorithm can be refined: in each node, we only store sequences which are subsequences of sequences in Ω. We provide a more detailed implementation of this algorithm in Appendix A.3.
Proposition 2. The complexity of this graph construction algorithm is upper bounded by O |A| 2d |Ω|d .
The proof is given in Appendix A.4. It is to be noted that this upper bound is in general far larger than the actual number of operations. Indeed, it supposes that the number of nodes in the graph is |A| d , although it can be much smaller thanks to the redundancies induced by Ω. A more precise formula is O |V ||A| d |Ω| , where |V | is the number of nodes in the final graph and depends on the structure of Ω. Despite this exponential theoretical complexity, the goal is to use this algorithm locally, thus for small depths. In practice we found that local-dynamics graphs could be computed within a few seconds on a standard laptop.

FROM LOCAL-DYNAMICS GRAPH TO LOCAL EXPLORATION POLICY
Once the local-dynamics graph (V, E) has been constructed, our goal is to find a good local exploration policy in the resulting MDP as defined in Section 3.2. We recall that its set of states is V , and its actions dynamics are given by the edges E. Ideally, we would want to find a policy π such that all nodes in the local-dynamics graph are visited equally often.
Given a policy π, a state v ∈ V and an action a ∈ A, we denote p π,t (v) and p π,t (v, a) the t-steps state distribution and state-action distribution respectively. Formally, p π,t (v) = P π (v t = v) and p π,t (v, a) = P π (v t = v, a t = a).
Ideally we would like each t-step state distribution to be uniform. However, depending on the exact local-dynamics graph this may or may not be possible. Instead, following the principle of maximum entropy (Jaynes, 1957), we frame the objective of balancing the state distribution at step t as maximizing H([p π,t (v 0 ), p π,t (v 1 ), . . . , p π,t (v |V |−1 )] = H(p π,t ), where H is the Shannon entropy. For a local-dynamics graph of depth d ∈ N, we define our global objective as maximizing J(π) =J(p π,1 , . . . , p π,d ) = 1 d d t=1 H(p π,t ). Other global objectives are possible, for example optimizing entropy over only the final states, or some other weighted mixture. In practice, over simple experiments, we observed that changes in the entropy mixture hardly induced any variation in the computed policies and agent behavior.
Informally, our objective can be understood as maximizing state diversity locally, for every timestep smaller than d. For environments where additional priors about state interests are available, one could adapt the quantity J to compute the entropy on a subset of the most interesting states, therefore biasing exploration toward promising areas.
As the entropy H is concave, the functionJ is a concave function over K. Moreover, the constraints defining K are linear. Therefore, max (p1,...,p d )∈KJ (p 1 , . . . , p n ) can be solved efficiently using any convex solver. In our implementation, we use CVXPY (Diamond & Boyd, 2016;. Once (p 1 , . . . , p d ) = arg max KJ is computed, we can immediately calculate a time-dependent policy π from such a distribution (Puterman, 2014) with: As the local-dynamics graph (V, E) is a DAG, the set of nodes V 0 , V 1 , . . . , V d which can be reached respectively at timesteps t = 0, t = 1, . . . , t = d are disjoint. Therefore any time-dependent policy defined on V can be framed as a stationary policy. Considering for example π , we can write

FROM LOCAL EXPLORATION TO GLOBAL POLICY
The optimal π determined in the previous section can then be used to guide exploration. With an -greedy policy, each step has a probability of being an exploration step, where an action is sampled uniformly. Instead, we keep in memory the local-dynamics graph, and initialize the current state at v = Λ. Everytime an action a is performed, v is updated such that v ← v.a, and reinitialized to Λ after a sequence of length d. At each exploration step, instead of sampling a uniformly, EASEE samples a according to the distribution π (v, ·). Pseudocode for this process can be found in Appendix A.5.

RESULTS
For every experiments, additional details about environments and hyperparameters are given in Appendix B.

PURE EXPLORATION
To get a better understanding of EASEE, we consider two simple gridworld environments with different structures: CardinalGrid and RotationGrid. These environments are both 100 × 100 gridworlds, but with different action structures. In CardinalGrid, the agent can move one square in the four cardinal directions (→, ←, ↑, ↓), whereas in RotationGrid, the agent can move either forward one square (↑), or rotate 90 • on the spot to the left ( ) or to the right ( ). The agent starts in the middle of the grid and can explore for 100 timesteps, after which the environment is reset.
In CardinalGrid, we consider the 4 equivalence sets: • while in RotationGrid, we consider the three equivalence sets: Fig. 3 shows the benefits of exploiting the structure of the action space for exploration. Figures 3a, 3b show the ratio of the number of unique states visited using EASEE over a standard uniform exploration policy. For both environments, a greater equivalence set leads to a more efficient exploration. In the environmentCardinalGrid for example, for a fixed depth of 6, adding the information that → and ← commute and that every actions commute allow to reach respectively 10% and 60% more states in 100 episodes. Furthermore, extra equivalences encoding that → is the inverse of ←, and ↑ the inverse of ↓ increase the number of new states encountered threefold. It can also be seen that deeper graphs provide better exploration, which is expected: using deeper graphs results in exploiting equivalence priors over longer action sequences. Figures 3c, 3d show the number of unique states visited with respect to the total number of episodes of exploration. We see that EASEE benefits exploration in all configurations considered: it allows the agent to visit more states within a single trajectory, and as well as across a thousand. It gives insight about the sample-efficiency gain which can be achieved using EASEE over a standard random policy. In the CardinalGrid setting, EASEE visits more unique states over 100 episodes than uniform exploration over 1000.

MINIGRID
The Minimalistic Gridworld Environment (MiniGrid) is a suite of environments that test diverse capabilities in RL agents (Chevalier-Boisvert et al., 2018). We evaluated the influence of adding EASEE to Q-learning on the DoorKey task. The environment is a gridworld split into two rooms separated by a locked door. The agent must collect a key to get to the objective in the other room.The dynamics of the environment are those of RotationGrid with two extra actions: the agent may PICKUP the key when facing it and OPEN the door when carrying the key. The EASEE version of the Q-learning assumes the following action sequence equivalences: The reward over this training is presented in Figure 4a. Using a depth of 6, the EASEE augmented version outperforms classic Q-learning.

CATCHER
We test EASEE on a game of Catcher, where the agent must catch a ball falling vertically with a paddle that can move left and right. It receives a reward of +1 when the ball is caught and −1 when it is missed. The prior we incorporate into the exploration is that the actions commute i.e. ←→∼→←. For faster learning we restrict each episode to a single ball drop, with the agent starting in the middle of the environment.
We choose a depth of 30 for EASEE. This is also the length of a single episode. The mean reward over training is plotted in Figure 4b.

FREEWAY
We test our method on the Atari 2600 game Freeway (Bellemare et al., 2013). The agent has to cross a road with multiple lanes without getting hit by the cars, and receives a reward when it reaches safety on the other side. The action space is composed of 3 actions : moving forward of 1 lane (↑), moving backward of 1 lane (↓), and passing (-). As cars arrive randomly, it is not easy to find priors on action equivalences in this environment. Since passing and moving backwards can sometimes be useful to avoid cars we cannot forbid these actions. However, we have prior knowledge that performing these two actions does not lead to visiting new lanes. We restrict the use of these actions with Ω = {↓∼↓↓, -↓∼↓-}, which has the effect of removing every node which is reached by chaining two ↓ actions without moving forward, and compute the exploration policy on the remaining nodes. Results can be seen in Fig. 4c. Interestingly, incorporating such a prior does not lead to better sample-efficiency, as in the previous environments, but to a better final policy.

DISCUSSION
We assume that implementers of reinforcement learning agents can provide insights about the environment, despite not knowing its precise dynamics or optimal policy.
In this work, we argue that some of these insights can be efficiently represented using the notion of action-sequence equivalence, which we formalize. We propose a method to incorporate such priors in classic Q-learning algorithms and demonstrate empirically its ability to improve sample efficiency and performance. More precisely, our approach can be divided into two steps: first, the construction of a graph representing the local dynamics, and then the resolution of a convex optimization problem aiming to balance node visitation. We show that incorporating such prior knowledge can replace standard -greedy and improve at little cost RL algorithms, which traditionally start from a tabula rasa setting, learning everything from scratch.
We expect EASEE to be robust to slight errors in the action sequence equivalence set. It may be that the states at the end of two sequences are not exactly the same but very similar, or that an action-sequence equivalence is verified at all but a few states. In such cases, the exploration policy we determine is not optimal, but should be much closer to optimality than uniformly sampling actions.
We additionally experimented with EASEE on two other Atari games, where the improvements are less pronounced: the details are given in Appendix B.4, as well as possible explanations.
We organize the supplementary material as follows. In Appendix A we include the proofs of results from the main text, as well as additional details about the proposed algorithms, including pseudo-code. In Appendix B we detail our experimental procedure, including hyperparameters for all methods used.

A TECHNICAL ELEMENTS AND PROOFS
A.1 PROOF OF PROPOSITION 1 Proposition 1. If we have two pairs of equivalent sequences over M, i.e. w 1 , w 2 , w 3 , w 4 ∈ A such that w 1 ∼ w 2 w 3 ∼ w 4 then the concatenation of the sequences are also equivalent sequences: Proof. For any s ∈ S, we have T (s, w 1 ) = T (s, w 2 ) as w 1 ∼ w 2 . We apply the same property for w 3 and w 4 on the state T (s, w 1 ): A.2 PROOF OF THEOREM 1 Theorem 1. Given an equivalence set Ω, ∼ Ω is an equivalence relationship. Furthermore, for v, w ∈ A , v ∼ Ω w ⇒ v ∼ w.
∼ Ω is an equivalence relation Let u, v, w ∈ A . Proof.
• It is clear from its definition that ∼ 1 Ω is symmetric, as ∼ is symmetric. Then, we suppose that v ∼ Ω w. We have n ∈ N and v 1 , . . . , v n ∈ A such that v ∼ 1 Hence ∼ Ω is symmetric.
• If u ∼ Ω v and v ∼ Ω w, we have n 1 , n 2 ∈ N, and u 1 , . . . , The relation ∼ Ω is reflexive, symmetric and transitive. Therefore it is an equivalence relation.

A.3 GRAPH CONSTRUCTION ALGORITHM
We present in Algorithm 1 an overview of the graph construction algorithm. It takes as input the action set A, the sequence equivalence set Ω, and the desired depth d, and outputs a DAG. Informally, it starts from a graph G = (V, E) reduced to a root state {0} and iteratively expands G until a distance L to the root is reached. For a node n ∈ V we store in E(v) sequences which reach v, and are prefixes of sequences of Ω. When expanding a state v ∈ V using an action a ∈ A (Line. 12), we look at every partial sequence s ∈ E(v). If s.a is in Ω, it means that we have found a redundant sequence. If the equivalent sequence has already been computed, it means that a node u representing T (v, s.a) has previously been added in G. Otherwise, we add a new node u. In both case, we update the equivalences E(u) to account for the new ways of reaching u (Line. 18).

A.4 GRAPH CONSTRUCTION COMPLEXITY
As shown in Section 3.2, constructing the graph necessitates three intricate loops: The first one goes over every internal node n ∈ V , the second one loops over the set of actions A, and the last one loops over every partial sequence which allows to reach v from a parent node. Inside these three loops, one has to compare the partial sequence with every sequence of Ω. As sequence length in Ω can be bounded by d, the complexity cost inside the tree loops is bounded by O(|Ω|d). The total complexity is therefore lower than O(|V ||A||A| d−1 |Ω|d) = O(|V ||A| d |Ω|d). As |V | ≤ |A| d , the complexity can also be bounded by O(|A| 2d |Ω|d).

A.5 MODIFIED DQN
Our modified version of the DQN algorithm can be found at Algorithm 2.
Algorithm 2: Modified DQN Initialize replay memory D and Q-networks Q θ and Q θ ; Determine local-dynamics graph G and the associated optimal exploration policy π ; for episode = 1 to M do Initialize new episode; for t = 1 to T do ← set new value with -decay ( usually anneals linearly or is constant); Initialize at empty sequence v ← Λ; if U([0, 1]) < then Sample exploring action a t ∼ π (v, ·); else Select greedy action a t ; end v ← v.a t (append a t to the end of sequence v); Execute a t and observe next state s t+1 and reward r t ; Store (s t , a t , r t , s t+1 ) in replay buffer D Update θ and θ normally with minibatches from replay buffer D; if Length(v)=d then Reset v ← Λ; end end end

A.6 POSSIBLE EXTENSION TO THE STOCHASTIC CASE
In this section we discuss the possibility of extending EASEE to the case of MDPs with stochastic transitions. EASEE relies on three components: the formalization of action sequence equivalences (Def. 1), the construction of a local-dynamics graph (Section 3.2), and the construction of a local exploration policy by solving a convex problem (Section 4.2). We now detail for each step the necessary changes to adapt EASEE to M = (S, A, T, R, γ), a MDP with stochastic dynamics.
• Action Sequence equivalences: the difference with the deterministic case here is that given an action a ∈ A and a state s ∈ S, T (s, a) is not a state but a distribution over the set of states S. Therefore every equality considered in Section 3.1 has now to be understood not as an equality between two states but between two distributions. Other than this the formalism can be kept identical. Intuitively, two sequences of actions are equivalent if they lead to the same state distribution from any given state, i.e. if they produce the same effect everywhere.
• Local-Dynamics Graph: Here, the formalism can again be kept identical. A node in the local-dynamics graph will not represent a state anymore, but rather a distribution over S.
• Local Exploration Policy: Solving directly the objective given in equation 4 would lead to maximize the diversity among state distributions encountered. As is, it would not necessarily lead to a better diversity among states, as two different distributions can have an almost similar support. Therefore, adapting EASEE to a stochastic setting would require encoding additional priors about the distributions represented by the nodes of the local-dynamics graph, which we leave for future work. If we suppose that the distributions encountered have disjoint supports, and that their entropy is the same, EASEE can be applied without modification.

B EXPERIMENTAL DETAILS
B.1 GRIDWORLDS We tested EASEE on the DoorKey task. An illustration of the initial state is given in Fig. 5. The agent is represented by the red triangle. The yellow key is necessary to open the yellow door. The two room are respectively 12 × 17 and 4 × 17 grids. The agent has 3249 timesteps to reach the goal and receive a reward of 1 before the environment is reset.

B.2 CATCHER
The paddle is 1 block wide. The environment is 60 blocks wide and 30 blocks high. The ball and the paddle both move at a rate of 1 block per timestep, so each episode lasts 30 timesteps.
We use the same architecture for the DQN with and without EASEE. Each observation is a 60 × 30 image. The feature extractor network is a CNN composed of 3 convolution layers with kernel size 3 followed by ReLU activation. In both cases, we update the online network every 4 timesteps, and the target network every 10 3 timesteps. We use a replay buffer of size 10 4 , and sample batches of size 32. We use the Adam optimizer with a learning rate of 10 −4 . Architecture and hyperparameters We use the same architecture and the exact same DQN parameters as in AppendixB.3. In all three environments, EASEE is used with a depth of 4.

Results
We can see the results on Fig.7. We can see a slight gain for Boxing, and a marginal improvement for Carnival. This can come from various factors: • When the number of action sequence equivalences considered is small compared to the number of actions, as it is the case for Carnival, the exploration policy computed with EASEE is very much like a uniform policy. It logically makes its performances converge toward those of a standard DQN.
• The action sequence equivalences considered here are only approximately true. In boxing, it is only approximately true that UPRIGHT ∼ UP.RIGHT for example. In Carnival, RIGHT and LEFT commute as long as the player is not at the edges of the screen, in which case RIGHT or LEFT could have no effect. In both cases, this induces a bias that may harm performance.