Year: 2021

Abstract:
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 -greedy strategy in a DQN, we demonstrate its potential in several environments with various dynamic structures.

heading: 1 INTRODUCTION
text: 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 (x) or to the right (y), 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 yy and xx both lead to the same state (represented as state 4 in Figure 1). If actions 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.
Overview We assume that we have sets of equivalent action-sequences for the environment. Equivalent action sequences are sequences that lead to the same state. These sequences are used to build a DAG that models where the agent will end up after any sequence of actions of length d. Because some sequences are equivalent, several parent nodes may share a child node. A naive exploration scheme like -greedy would waste resources by over exploring such child nodes. Instead, we leverage this information using the DAG constructed above; our method executes an exploratory action that maximizes the entropy of the future visited states.

heading: 2 RELATED WORK
text: Improved 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; Şimş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. In Gupta et al. (2018) exploration strategies are learned from prior experience. Unlike EASEE this requires meta-training over a distribution of tasks.
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. Grinsztajn et al. (2021) quantifies the probability of cycling back to a previously visited state, motivated by the analysis of reversible actions. 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. Farquhar et al. (2020) introduce a curriculum of progressively growing action spaces to accelerate learning. These methods aim to improve the generalization of policies to unseen actions in large action spaces rather than enhancing exploration. Leveraging previous trajectories to extract prior knowledge, Tennenholtz & Mannor (2019) provide an understanding of actions through their context in demonstrations.

heading: 3 FORMALISM

heading: 3.1 EQUIVALENCE OVER ACTION SEQUENCES
text: We consider a Markov Decision Process (MDP) defined as a 5-tupleM = (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=0Ak where Ak is the set of all sequences of length k and A0 contains as single element the empty sequence Λ. We use . for the concatenation operator, such that for v1 ∈ Ah1 , v2 ∈ Ah2 , v1.v2 ∈ Ah1+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?:
T (s,Λ) = s
T (s, w.a) = T (T (s, 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 a1 . . . an and a′1 . . . a′m ∈ A? are equivalent at state s ∈ S if
T (s, a1 . . . an) = T (s, a ′ 1 . . . a ′ m) (1)
Two sequences of actions are equivalent overM if they are equivalent at state s for all s in S. This is written:
a1 . . . an ∼M a′1 . . . a′m (2)
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 MDPM 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 pairs v1 ∼ w1, v2 ∼ w2, . . . , vn ∼ wn, we say that Ω = {{v1, w1}, {v2, w2}, . . . {vn, wn}} is an equivalence set overM.
Formally, Ω is a set of pairs of elements of A?, such that Ω ⊂ (A?)2. By abuse of notation, we write v ∼ w ∈ Ω if {v, w} ∈ Ω. 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 overM, i.e. w1, w2, w3, w4 ∈ A? such that
w1 ∼ w2
w3 ∼ w4
then the concatenation of the sequences are also equivalent sequences:
w1 · w3 ∼ w2 · w4
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 steps, meaning:
∃u1, u2, v1, w1 ∈ A?such that  v = u1.v1.u2 w = u1.w1.u2
v1 ∼ w1 ∈ Ω (3)
For n ≥ 2, we say that v can be changed into w in n steps if there is a sequence v1, . . . , vn ∈ A? such that v ∼1Ω v1 ∼1Ω · · · ∼1Ω vn = w. 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 v, w ∈ A?, v ∼Ω w ⇒ v ∼ w.
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.

heading: 3.2 LOCAL-DYNAMICS GRAPH
text: 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 ∈ Ah, 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 fromM: 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 v0 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.

heading: 4 EQUIVALENT ACTION SEQUENCES FOR EXPLORATION (EASEE)

heading: 4.1 FROM EQUIVALENT ACTIONS TO LOCAL-DYNAMICS GRAPH
text: 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 = {a1, a2} and Ω = {a1a1 ∼ Λ, a2a1 ∼ a1a2}. 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 a1 and a2 respectively. In a tree, the expansion of a node corresponding to a sequence w ∈ Ah with the action a ∈ A always leads to the creation of a new leaf that results from the sequence of actions w.a ∈ Ah+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. 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. 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. 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.

heading: 4.2 FROM LOCAL-DYNAMICS GRAPH TO LOCAL EXPLORATION POLICY
text: 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π(vt = v) and pπ,t(v, a) = Pπ(vt = v, at = 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 (see Figure 1 for an example where obtaining a uniform distribution is impossible). 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(v0), pπ,t(v1), . . . , 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=1H(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.
We consider K, the set of joint distributions (p0, p1, . . . pd) which verifies the following properties:
• ∀t ≤ d, pt(v, a) ≥ 0 • ∀v ∈ V, ∑ a∈A p0(v, a) = p0(v) = 1v0(v)
• ∀t < d, ∑ a∈A pt+1(v, a) = ∑ v′∈V,a∈A pt(v ′, a)P(v | v′, a)
We denote D(A) the set of distributions over A. From any (p0, p1, . . . , pd) ∈ K, it is possible to find a time-dependent policy π : V ×{0, . . . , d} → D(A) such that p0 = pπ,0, p1 = pπ,1, . . . , pd = pπ,d, and for any policy π we have (pπ,0, pπ,1, . . . , pπ,t) ∈ K (Puterman, 2014).
As the entropy H is concave, the function J̃ is a concave function over K. Moreover, the constraints defining K are linear. Therefore,
max (p1,...,pd)∈K J̃(p1, . . . , pn) (4)
can be solved efficiently using any convex solver. In our implementation, we use CVXPY (Diamond & Boyd, 2016; Agrawal et al., 2018). Once (p?1, . . . , p ? d) = arg maxK J̃ is computed, we can immediately calculate a time-dependent policy π? from such a distribution (Puterman, 2014) with:
π?t (v, a) = p?t (v, a)
p?t (v) (5)
As the local-dynamics graph (V,E) is a DAG, the set of nodes V0, V1, . . . , Vd 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 π?(v, ·) = π?0(v, ·) if v ∈ V0, π?(v, ·) = π?1(v, ·) if v ∈ V1, . . . , and π?(v, ·) = π?d(v, ·) if v ∈ Vd.

heading: 4.3 FROM LOCAL EXPLORATION TO GLOBAL POLICY
text: 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.

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

heading: 5.1 PURE EXPLORATION
text: 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 (x) or to the right (y). 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:
• {→←∼←→} (“→ and← commute ”) • {→←∼←→, ↑↓∼↓↑} (“all actions commute”) • {→←∼←→, ↑↓∼↓↑,→←∼ Λ} (“all actions commute and→←∼ Λ”) • {→←∼←→, ↑↓∼↓↑,→←∼ Λ, ↑↓∼ Λ} (“ all actions commute and→←∼↑↓∼ Λ ”),
while in RotationGrid, we consider the three equivalence sets:
• {yx∼ Λ} • {yx∼ Λ,xy∼ Λ} • {yx∼ Λ,xy∼ Λ,yy∼xx}.
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.

heading: 5.2 MINIGRID
text: 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:
yx ∼ Λ xy ∼ Λ xx ∼yy OPEN ∼ OPEN · OPEN

heading: PICKUP ∼ PICKUP · PICKUP
text: The reward over this training is presented in Figure 4a. Using a depth of 6, the EASEE augmented version outperforms classic Q-learning.

heading: 5.3 CATCHER
text: 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.

heading: 5.4 FREEWAY
text: We test our method on the Atari 2600 game Freeway (Bellemare et al., 2013). To illustrate EASEE’s performance in a non-deterministic setting, we add stochasticity to the dynamics of the game using sticky actions (Machado et al., 2018). 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.

heading: 6 DISCUSSION
text: 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.

heading: 7 REPRODUCIBILITY STATEMENT
text: In an effort to help with reproducibility, we provide a light-weight implementation of the experiments discussed in sections 5.1 and 5.2. For Catcher and Atari environments, all details of the environments, as well as the preprocessing steps and the hyperparameters we chose are described in Appendix B.2 and Appendix B.3 respectively. Additionally, the pseudo-code for the proposed methods is given in Appendix A.3.

heading: 8 ETHICS STATEMENT
text: A direct application of this paper is to make reinforcement learning techniques in general, and deep Q networks in particular, more efficient at solving Markov decision processes by making use of prior knowledge about action sequence equivalences. On its own, we do not expect EASEE to have immediate societal risks. Moreover, approaches incorporating prior knowledge in reinforcement learning algorithms often increase sample efficiency at little cost, thereby leading to less expensive and more environmentally-friendly methods.

heading: A TECHNICAL ELEMENTS AND PROOFS

heading: A.1 PROOF OF PROPOSITION 1
text: Proposition 1. If we have two pairs of equivalent sequences overM, i.e. w1, w2, w3, w4 ∈ A? such that
w1 ∼ w2
w3 ∼ w4
then the concatenation of the sequences are also equivalent sequences:
w1 · w3 ∼ w2 · w4
Proof. For any s ∈ S, we have T (s, w1) = T (s, w2) as w1 ∼ w2. We apply the same property for w3 and w4 on the state T (s, w1):
T (T (s, w1), w3) = T (T (s, w2), w4)
T (s, w1.w3) = T (s, w2.w4)
Therefore w1.w3 ∼ w2.w4.

heading: A.2 PROOF OF THEOREM 1
text: 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?.

heading: Proof.
text: • We immediately have v ∼1Ω v by choosing v1 = Λ in equation 3, and therefore v ∼Ω v, thus ∼Ω is reflexive.
• It is clear from its definition that∼1Ω is symmetric, as∼ is symmetric. Then, we suppose that v ∼Ω w. We have n ∈ N and v1, . . . , vn ∈ A? such that v ∼1Ω v1 ∼1Ω · · · ∼1Ω vn ∼1Ω w, therefore w ∼1Ω vn ∼1Ω · · · ∼1Ω v1 ∼1Ω v, thus w ∼Ω v. Hence ∼Ω is symmetric.
• If u ∼Ω v and v ∼Ω w, we have n1, n2 ∈ N, and u1, . . . , un1 ∈ A?, v1, . . . , vn2 ∈ A?, such that u ∼1Ω u1 ∼1Ω · · · ∼1Ω un1 ∼1Ω v and v ∼1Ω v1 ∼1Ω · · · ∼1Ω vn2 ∼1Ω w. It is then clear that u ∼1Ω u1 ∼1Ω · · · ∼1Ω un1 ∼1Ω v ∼1Ω v1 ∼1Ω · · · ∼1Ω vn2 ∼1Ω w, and thus u ∼Ω w. Therefore ∼Ω is transitive.
The relation ∼Ω is reflexive, symmetric and transitive. Therefore it is an equivalence relation.
∼Ω implies ∼
Proof. Let v, w ∈ A?. From Proposition 1, we immediately get v ∼1Ω w ⇒ v ∼M w. Then we can prove by immediate induction that ∀n ∈ N, v1, . . . , vn ∈ A?, v ∼1Ω v1 ∼1Ω · · · ∼1Ω vn ∼1Ω w ⇒ v ∼ w, from which we deduce v ∼Ω w implies v ∼ w.
Algorithm 1: Graph Construction Input Action set A; Input Equivalence set Ω; Input Maximum tree depth d; Initialize the graph G = (V,E) with V = {0} and V = ∅ ; Initialize the set of states to expand S = {0} ; Initialize the current tree depth l = 0; Initialize a dictionary E which stores partial sequences of Ω for each state of V ; while l < d and S 6= ∅ do
newStates = {} ; for each state in S do
for each action in A do /* create a node corresponding to T (state, action) */
12 newState = expandNode(state, action, Ω, E) ; if newState not in V then
/* Because of sequence redundancies, the state may already appear in the graph. */ V ← V ∪ {newState} ; newStates← newStates ∪{newState} ;
end E ← E ∪ {(state, newState)} ; /* Update the equivalences E(newState) to account for
the new ways of reaching newState */ 18 E ← UpdateDic(newState, E , Ω) ;
end end l← l + 1; S ← newStates ;
end /* Prune edges such that the resulting graph is a DAG. */ T = GraphToDAG(G) ; Output DAG G;

heading: A.3 GRAPH CONSTRUCTION ALGORITHM
text: 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).

heading: A.4 GRAPH CONSTRUCTION COMPLEXITY
text: 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 actionsA, 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).

heading: A.5 MODIFIED DQN
text: 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 at ∼ π?(v, ·); else
Select greedy action at; end v ← v.at (append at to the end of sequence v); Execute at and observe next state st+1 and reward rt ; Store (st, at, rt, st+1) in replay buffer D Update θ and θ′ normally with minibatches
from replay buffer D; if Length(v)=d then
Reset v ← Λ; end
end end

heading: A.6 POSSIBLE EXTENSION TO THE STOCHASTIC CASE
text: 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 toM = (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.

heading: B EXPERIMENTAL DETAILS

heading: B.1 GRIDWORLDS
text: 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.

heading: B.2 CATCHER
text: 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 103 timesteps. We use a replay buffer of size 104, and sample batches of size 32. We use the Adam optimizer with a learning rate of 10−4.
We train for 3.105 timesteps. The exploration parameter is linearly annealed from 1 down to 0.05 over 20% of the training period. Other DQN hyperparameters were defaults in Raffin et al. (2019).

heading: B.3 FREEWAY
text: Environment In Freeway, the agent has to cross a road with multiple lanes without getting hit by the cars. It only receives a reward when it safely reaches the other side of the road. An illustration is given in Fig. 6. The agent is represented by the yellow chicken.
To add stochasticity to the dynamic of the environment, we use sticky actions as proposed in Machado et al. (2018), with a stickiness parameter of 0.25. More precisely, the environment has 0.25 probability of executing the previous action again instead of the current desired action. The frame is recast as a 84 × 84 × 3 image, and the number of frames to skip between each observation is set to 4. The reward is scaled to [-1, 1]. An observation corresponds to 4 stacked game frames.
Architecture and hyperparameters We use the same architecture for the DQN with and without EASEE. Input images first go through a convolutional neural network, with the same architecture as in Mnih et al. (2015). We update the online network every 4 timesteps, and the target network every 103 timesteps. We use a replay buffer of size 105, and sample batches of size 32. We use the Adam optimizer with a learning rate of 10−4.
We train for 107 timesteps. The exploration parameter is linearly annealed from 1 down to 0.01 over 10% of the training period, which are the default in Raffin (2018) for Atari games. Other DQN hyperparameters were defaults in Raffin et al. (2019).

heading: B.4 ADDITIONAL EXPERIMENTS
text: Environments We experimented EASEE on two other Atari environments, where the action sequence structures are less straight-forward. The three environments are preprocessed as explained in AppendixB.3.
• Boxing: This game shows a top-down view of two boxers. The player can move in all four directions, and punch his opponent (pressing the “FIRE” button). The action space is composed of 18 actions : NOOP, FIRE, UP, RIGHT, LEFT, DOWN, UPRIGHT, UPLEFT, DOWNRIGHT, DOWNLEFT, UPFIRE, RIGHTFIRE, LEFTFIRE, DOWNFIRE, UPRIGHTFIRE, UPLEFTFIRE, DOWNRIGHTFIRE, DOWNLEFTFIRE. We incorporated priors by decomposing actions, in the form of UPRIGHT ∼ UP.RIGHT, UPLEFT ∼ UP.LEFT, UPRIGHTFIRE ∼ UPRIGHT . FIRE, UPLEFTFIRE ∼ UPLEFT . FIRE, etc...
• Carnival: The goal of the game is to shoot at targets, which include rabbits, ducks, owls, scroll across the screen in alternating directions, and sometimes come at the player. The player can only move in 1 direction, such that the action space is composed of 6 actions: [NOOP, FIRE, RIGHT, LEFT, RIGHTFIRE, LEFTFIRE]. As NOOP is not an useful action, EASEE could get an edge simply by adding the equivalence NOOP ∼ Λ. For a fair
comparison, we restricted the action space to meaningful actions by removing NOOP for both EASEE and the baseline. We limited ourselves to the commutative property of RIGHT and LEFT: RIGHT . LEFT ∼ LEFT . RIGHT.
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.

Review summaries:
In the context of reinforcement learning, authors propose an exploration strategy based on environment-specific prior knowledge of action equivalence. An example of such equivalence is rotating 180° twice in a grid world, as the agent comes back to the same original state: the action sequence forms an identity in this case. The proposed exploration, instead of picking a random action with probability (\epsilon)/(number of actions), builds an abstracted lookahead tree of specified depth that merges equivalent action sequences and adjusts the distribution of \epsilon over them. Authors demonstrate this i) increases the number of unique state visitations in grid-world examples, and ii) DQN with their exploration strategy achieves a higher reward faster than the baseline. 

The paper proposes a method that, from a simple encoding of sequences of actions that have equivalent outcome in an MDP, allows to compute a local policy for local high-quality exploration (it replaces the random action of $\varepsilon$-greedy with an action that maximizes the entropy of future visited states). Full algorithmic details about how to do that are given in the paper, and experiments on a few environments show that the method is promising. The Freeway experiment is particularly interesting, as it shows that a (small) benefit can be obtained from the method even on an Atari game, with minimal domain knowledge (only a few equivalent action sequences are encoded), and using a slightly modified DQN algorithm.