Better state exploration using action sequence equivalence
Authors: Nathan Grinsztajn
Toby Johnstone
Johan Ferret
Philippe Preux
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement learning
priors
structure
exploration

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 \emph{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.

Under review as a conference paper at ICLR 2022
BETTER STATE EXPLORATION USING ACTION SE- QUENCE EQUIVALENCE
Anonymous authors Paper under double-blind review
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 exploiting priors about action sequence equivalence: that is, when different sequences of actions produce the same effect. We propose 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 convex optimization problem. By replacing the usual e-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 (Mmih 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 new task, including understanding of physics, semantics, and affordances (Dubey et al. 2018).
The considerable quantity of data necessary 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 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. Mahajann & Tulabandhula (2017) and Biza & Jr. (2019) learn simpler representations of MDPs that exhibit symmetrical structure, while van der Pol al. (2020) show that environment invariances can be hard-coded into equivariant neural networks.
fundamental challenge standing in the way of improved sample efficiency 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 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 gridworld (called RotationGrid hereafter) where the agent can move forward (1) and rotate to the left (sn) or to the right (C), 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 previously visited states, following the reasoning Tabu search (Glover 1986). We observe further that cvr and von both lead to the same state (represented as state 4 in Figure D 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 new method taking advantage of Equivalent Action SEquences for Exploration (EASEE), an overview which can be found in Figure [ 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

---

Under review as a conference paper at ICLR 2022
Input
Graph Construction
Action Probability Inference
n00e
0001
Figure 1: Illustrtiion 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 (A 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.
inexpensive and can be done once and for all before learning begins, providing principled and tractable exploration policy that takes into account environment structure. This policy can easily be injected into existing reinforcement learning algorithms substitute for e-greedy exploration.
Our contribution threefold. First, we formally introduce the notion equivalent action sequences, novel type of structure in Markov Decision Processes. Then, we show that priors on this type of structure can easily be exploited during offiine exploration by solving a convex optimization problem. Finally, we provide experimental insights and show that incorporating EASEE into DQN (Mnih et al. 2015) improves agent performance several environments with various structures.
Overview We assume that we have sets of equivalent action-sequences for the environment. Equiv- alent action sequences are sequences that lead to the same state. These sequences are used build 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. naive exploration scheme like e-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.
2 RELATED WORK
Improved Exploration
The problem of ensuring that agents see sufficiently diverse states has received lot of attention from the RL community. Many methods rely on intrinsic rewards (Schmid)
huber 1991 Chentanez et al. 2005 Şimşek & Barto 2006 Lopes et al. 2012 Bellemare et al. 2016 Ostrovski et al. Pathak et al. 2017) to entice agents unseen or misunderstood areas.
tabular setting. these take the form of count-based exploration bonuses which guide the agent toward poorly visited states (e.g. Sttrhll & Littman (2088). ). Scaling this method requires the use of function approximators (Burda et al.) 2019 Badia et al.) 2020 Flet-Berliac al., 2021). Unlike FASEE, these methods necessitate the computation of nta-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 ours. In Gupta et al. (2018) exploration strategies are learned from prior experience. Unlike EASEE this requires meta training over distribution of tasks.
Redundancies in Trajectories The idea that different trajectories overlap and induce redun- dancies in state visitation used in Leurent & Maillard (2020) and Czech et al. (2020) in the case of Monte-Carlo tree search. However, they require generative model, and propose new Bellman operator to update node values according to newly uncovered transitions rather than modifying exploration. Closer to work, Caselles-Dupré al. (2020) study structure in action sequences,
2

---

Under review as a conference paper at ICLR 2022
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 meta-heuristic which uses knowledge of the past escape local optima. is popular for combinatorial optimization (Hertz. & Werra 2005). Like our approach, relies on local structure: actions which are known 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 Abbramson Wechsler (2003), tabu search is combined with reinforcement learning, using action priors. However, their method cannot make use of more complex action- sequene structure.
Maximum State- Visitation Entropy Our goal to explore as uniformly as possible every nearby state can be seen as 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 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., 22199)
Guo et al. 202T) can make of priors about state similarities, they learn global policy and cannot
exploit structure 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.) (016) or learning representations (Chandak et al.) 2019). [avakoli al. (0188) manage high-diig eigh-dimensional action spaces by assuming degree independence between each dimension. Farquhar et al. (2020) introduce 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 actions through their context in demonstrations.
FORMALISM
3.1 EQUIVALENCE OVER ACTION SEQUENCES
We consider a Markov Decision Process (MDP) defined as 5-tuple M (8, TT, R), with S the set of states, A the action set, T the transition function, R the reward function and the discount factor 7. The set of actions assumed to be finite |A] < oc. 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 actions are analogous to strings over the set of symbols A (possible actions). The set of all possible sequences of actions is denoted A' U A where A is the set of all sequences of length & and A contains as single element the empty sequence A. We use for the concatenation operator, such that for V1 , 122 E Ah 01.12 E th2 The transition function 7 S x A + S gives the next state s' when action is taken in state T(s, a) s'. We recursively extend this operator to action sequences T: S A + such that, Vs E S, Va E A, Vw E A":
T(s, = ((s, w.a) T (T w),a)
Intuitively, this operator gives the new state of the MDP after sequence of actions performed from state 8.
Definition (Equivalent sequences). We say that two action sequences a ...on and d1 ...d', A
are equivalent at state S if
T(s 1s..1.... an) = T(s, (s..s,....aa ....)
(1)
Two sequences of actions are equivalent over M if they are equivalent at state s for all s in S. This is written:
01 ... On ~M 0j ... a'
3

---

Under review as a conference paper at ICLR 2022
This means that we consider two sequences of actions to be equivalent when following 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 casily 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 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 MDP .M and several equivalent sequence pairs ~ w1, 02 W2. ....... On Wh, we say that Q {[V1, wi }, {12, w2].... {Un, Wn an equivalence set over M.
Formally, Q is a set of pairs of elements of A", such that Ω C (A*)². By abuse of notation, we write w E 52 if (u, 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 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. W1, W2, Wg wa E A' such that
W1 W2
W3 ~ W4
then the concatenation of the sequences also equivalent sequences:
Wi - W3 W2 W0
The proof is given in Appendix A.1 We are now going to define formally the fact that the equivalence of two sequences be deduced from 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 ~ by applying
(a.a).a (a).a
times the equivalence a.o. parentheses. More generally and intuitively, the equivalence of two action sequences and w can be deduced from Ω which we denote v ~n w, if v can be changed into w iteratively, chaining equivalences of Q.
and rearranging the
More formally, write ~ w if can be changed to w one steps, meaning:
#1 U1 222
3us U2 01, W1 E A' such that
w #j "1 .42
(3)
U1 W1 E Ω
For n 2 2. we say that v can be changed into wo in n steps if there is sequence U1...., E A such that ~ U1 ~h ~ V22 w. Finally, we say that ~n w if there is N such that can be changed into in steps. The relation ~g is thus formal way of extending equivalences from fixed equivalence set Qt and 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 equivalence set Ω, <a is equivalence relationship. Furthermore, for U, w E A", v aa w + v W.
The proof is given in Appendix A.2 Given this relation between ~ and ~D, we will simplify the notation in what follows by writing instead of ~q when the equivalence set considered is unambiguous. As ~gg 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.
4

---

Under review as a conference paper at ICLR 2022
0
2
3
4
Figure Example of iterative graph construction with f2 {ala; A, agai [1a2] and maximum depth of 2. The 8th construction step corresponds to the pruning of the edge (1. 0).
3.2 LOCAL-DYNAMICS GRAPH
We leverage the equivalences defined above determine a model of the MDP up a few timesteps. As traditionally done in Monte-Carlo Tree Search (Coulom (007), an MDP (S, A, T, R, with deterministic dynamics can be locally unrolled to produce a tree, where a node of depth represents a sequence of actions v E Ah, and the edges represent transitions between such sequences. The root of the tree corresponds to the empty action sequence A. Here we adopt the same formalism, except that equivalent sequences will point to the same node.
Given a tree T of depth E N corresponding equivalence set Ω we call local-dynamics graph of depth under equivalence Q the graph G = (V, E) corresponding to the tree T where nodes are quotiented with the equivalence relation ~np Intuitively, it means that nodes corresponding to equivalent action sequences 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.
partial unrolling of sequences in AA', and an
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 ~a, the action space A is untouched. Given node n corresponding to a sequence w E AA", and an action a E .A. T(n, a) is the node representing the sequence w.a. E AA. Nodes representing sequences of length exactly d are final states. The initial state to is the empty sequence A. This MDP represents the local dynamics induced by ~n from given root state. We detail in the next section how construct such graphs in practice, and how to use these sub-MDPs for better exploration.
EQUIVALENT ACTION SEQUENCES FOR EXPLORATION (EASEE)
4.1 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 == {a1, a2} and iteratively expand the graph by unrolling the nodes at the edges of the graph. Steps 2 and 3 create nodes and 2 corresponding to action sequences 01 and d2 respectively. In a tree, the expansion of node corresponding to sequence E A with the action a E AA always leads to the creation of a new leaf that results from the sequence of actions w.a E + However, in a local-dynamics graph the node representing without creating a new node. As a final construction step, we prune edges which go backward the dycal-dynamics graph, like (1, 0) in Fig. 2 such that the resulting graph is DAG. This is motivated by the fact that we are interested in finding good exploration policy: an action which takes us back previously visited state should be ignored.
{ajal A, 02aj 01a2). Starting from the root node (first step), we
might already be present, in which case we add an edge from
5

---

Under review as a conference paper at ICLR 2022
From a practical point of view, the graph construction algorithm takes input the action set A, the sequence equivalence set Ω2 and the desired depth d, and outputs a DAG. Informally, it starts from a graph G (V, Æ) reduced to root state {0} and iteratively expands & 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 node with action
A, check every sequence stored in if w.a appears in S2 and if a node corresponding to an equivalent sequence of w.a is already in V. If it the case, we simply add an edge from n to this node, otherwise we create a new node representing w.a. We provide more detailed implementation of this algorithm in Appendix A.3
Proposition 2. The complexity of this graph construction algorithm is upper bounded by O ([4))))
The proof is given in Appendix AA.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 [AA although it can be much smaller thanks to the redundancies induced by S2. A more precise formula is O [[])))) where |V] is the number of nodes in the final graph and depends the structure Ω. Q. Despite this exponential theoretical complexity, the goal is to use this algorithm locally, thus for small depths. In practice we found that local- bocal-dynamics graphs could be computed within few seconds on a standard laptop.
4.2 FROM LOCAL-DYNAMIC. GRAPH TO LOCAL EXPLORATION POLICY
Once the local-dynamics graph (V, E) has been constructed, our goal is to find good local explo- ration 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 F. Ideally, we would want to find a policy æ such that all nodes in the local-dynamies graph are visited equally often.
Given a policy æ, a state v E V and an action a E A. we denote pv. and pv, a) the t-steps state distribution and state-action distribution respectively. Formally, Px,((v) P (v, v) and (v, a) = (2 = v. a = a).
Ideally would like each t-step state distribution to be uniform. However, depending the exact local-dynamics graph this may or may not be possible (see [igure[[oor an example where obtaining 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 (p ( (vo), (V1) (U.))...,,> Px,
(Pr,)), where I/ is the Shannon en- tropy. For a local-dynamics graph of depth d E N, we define our global objective as maximizing J(x) = J(m,,,, ....)) = 2 Di= (PT,)). Other global objectives are possible, for example optimizing entropy over only the final states, or some other weighted mixture. In practice, over simple experiments, observed that changes in the entropy mixture hardly induced any variation in the computed policies and agent behavior.
v]-] (VV)))
Informally, our objective can be understood 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 subset of the most interesting states, therefore biasing ex exploration toward promising areas.
We consider K., the set of joint distributions (po, Pi,-. pa) which verifies the following properties
Vt S d, a) 2 p 1 (v)
Vu Vu E.EA = poo()) =
Vt < d, Pei EveV.OEA Pelv', Pv a)
We denote D(A) the set of distributions over A. From any (po, Pl. paa= K. it possible find
a time-dependent policy V x (o,..... .00...,,] d} + D(A) such that pn Pr.0.P1 P1 Pr.l,.... : Pa.d.
and for any policy we have (Pn,0- Px. . Px.1) K. (Puterman 2014).
As the entropy is concave, the function J is a coneave function over IC. Moreover, the constraints defining K are linear. Therefore,
max (EK
J(p..... ((p)....pp.)
(4)

---

Under review as a conference paper at ICLR 2022
can be solved efficiently using any convex solver. In our implementation, use CVXPY Diamond & Boyd 2016 Agrawal al. 2018). Once (pi..... P2) arg maxx J is computed, we can immediately calculate a time-dependent policy n" from such a distribution (Puterman 2014 with:
(v,
Ty (v, a)
(5)
pt (v)
As the local-dynamics graph (V, E) is DAG, the set of nodes Vo. Vi...., Va which can be reached respectively at timesteps 0, 1.....f d are disjoint. Therefore any time-dependent policy defined on V can be framed as stationary policy. Considering for example n², we can write x (v, = (o( e E Vo, x (1, - of (v, if Vi...., and (w, T2 if Va-
4.3 FROM LOCAL EXPLORATION TO GLOBAL POLICY
The optimal n² determined in the previous section then be used to guide exploration. With an e-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-dynamies graph, and initialize the current state
A. Everytime an action a is performed, v is updated such that v f v.a, and reinitialized to A after sequence of length d. At each exploration step, instead of sampling uniformly. EASEE samples according to the distribution x (V,-). Pseudocode for this process can be found in Appendix A.5
5
RESULTS
For every experiments, additional details about environments and hyperparameters are given in Appendix B
5.1 PURE EXPLORATION
To get better understanding of EASEE, we consider two simple gridworld environments with different structures: CardinalGrid and RotationGrid. These environments are both 100 x 100 gridworlds, but with different action structures. In CardinalGrid, the agent can move one square in the four cardinal directions (-, +. 1, 1,4), whereas in RotationGrid, the agent can move either forward one square (t), rotate 90º on the spot to the left (e) or to the right (n)) The agent starts in the middle of the grid and can explore for 100 timesteps, after which the environment is reset.
In CardinalGrid, consider the 4 equivalence sets:
(-)))))))) ( + and f- commute ")
(-xie- N~41) ("all actions commute")
(-eve- - メイン A} ("all actions commute and - A') Op--e,,,,<+ -イー A, ~~ A} (" actions commute and - - ~-~ ?),
while RotationGrid, we consider the three equivalence sets:
foo A}
forn A, Ar A}
forw Dow N,00w5)).
Fig. 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 standard uniform exploration policy. For both environments, greater equivalence set leads to more efficient exploration. In the cuvironmentCardinalGiii for example, for fixed depth 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 t,, and f the inverse of L. 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 longer action sequences.
7

---

Under review as a conference paper at ICLR 2022
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 all configurations considered: it allows the agent to visit more states within single trajectory. and well as across a thousand. It gives insight about the sample-effiieney gain which can be achieved using EASER over a standard random policy. In the CardinalGrid setting, EASEE visits more unique states over 100 episodes than uniform exploration over 1000.
300 ----
and commute
----
all actions commute
actions commute and A
sctions
240
an-A
130
Uniue visted
120
250
DAG depth
DAG depth
(a) CardinalGrid
(b) RotationGrid
3000
baseline
baseline
actions commute and
1000
ar and m/
2500
1500
Unique
1000
400
200
10
100
(c) CardinalGrid
(d) RotationGrid
Figure 3: (a, b): Ratio of the number of unique visited states during 100 episodes following
EASEE over standard e-greedy policy, for different equivalence sets and depths in the environments GrrdinalGrid and RotationGrid respectively. (c, d): Number of unique visited states according to the number episodes for EASEE with a fixed depth of 4 compared standard e-greedy policy.
5.2 MINIGRID
The Minimalistic Gridworld Environment (MiniGrid) is suite of environments that test diverse capabilitics RL agents Chhiseiir-Boisseett et al.) 2018). We evaluated the influence of adding EASEE to Q-learning
the DoorKey task. The environment is 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 PICKUP the key when facing it and OPEN the door when carrying the key. The EASEE version of the Q-leaming assumes the following action sequence equivalences:
those of RotationGrid with two extra actions: the agent may
00^A
500A
00000
OPEN OPEN OPEN
PICKUP PICKUP PICKUP
The reward over this training is presented in Figure 4a version outperforms classic Q-learning.
Using a depth of 6, the EASEE augmented
8

---

Under review as a conference paper at ICLR 2022
5.3 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 reward of +1 when the ball is caught and - when 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 also the length of single episode. The mean reward over training is plotted in Figure 4b
3.2
Newnee
6.2
-0a
62-
DON
63
2.6
25
Number of timestaps
les
Number timestopps (10P)
04
(a) DoorKey (15 random seeds)
(b) Catcher (20 random seeds)
(c) Freeway (20 random seeds)
Figure 4: Mean reward over training with 95% confidence intervals.
5.4 FREEWAY
We test our method on the Atari 2600 game Freeway (Bellemare et al., 2013). To illustrate EASEE'S performance in non-deterministic setting, we add stochasticity to the dynamics of the game using sticky actions (Machado et al.) 2018). The agent has to cross road with multiple lanes without getting hit by the cars, and receives reward when it reaches safety on the other side. The action space is composed of 3 actions moving forward of lane (t), moving backward of I lane (L), and passing (-). As cars arrive randomly, it is not easy find priors action equivalences in this environment. Since passing and moving backwards can sometimes be useful to avoid cars we cannot forbid these actions. However, 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 4 actions without moving forward, and compute the exploration policy on the remaining nodes. Results can be seen in Fig. 4c
have prior knowledge that performing these two actions does
6 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 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 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 e-greedy and improve at little cost RL algorithms, which traditionally start from tabula rasa setting, learning everything from scratch.
We expect EASEE be robust to slight enrors 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 all but few states. In such cases, the exploration policy 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 less pronounced: the details are given in Appendix B.4] as well as possible explanations.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
In an effort to help with reproducibility, we provide a light-weight implementation of the experiments discussed in sections 5.1 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 [3.2 and Appendix [.3 respectively. Additionally, the pseudo-code for the proposed methods is given Appendix A.3
8
ETHICS STATEMENT
A direct application of this paper is to make reinforcement learning techniques in general, and deep networks in particular, more efficient 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 environmentaall-fiion methods.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Myriam Abramson and Harry Wechsler. Tabu search exploration for on-policy reinforcement learning. In International Joint Conference on Neural Networks, 2003.
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1))42-60, 2018.
Adria Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andrew Bolt, and Charles Blundell. Never give up: Learning directed exploration strategies. International Conference on Learning Representations, 2020.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling, The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, jun 2013.
Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, 2016.
Ondrej Biza and Robert Platt Jr. Online abstraction with mdp homomorphisms for deep learning. In International Conference Autonomous Agents and Mulliagent Systems, 2019.
Yuri Burda, Harrison Edwards, Amos J. Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019.
Hugo Caselles-Dupré, Michael Garcia-Ortiz, and David Filliat. On the sensory commutativity of action sequences for embodied agents. arXiv preprint arXiv:2002.056630, 2020.
Yash Chandak, Georgios Theocharous, James Kostas, Scott M. Jordan, and Philip S. Thomas. Learning action representations for reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings Machine Learning Research, pp. 941-950. PMLR, 2019. URL http://procedinggs www.inngg..r......... v97/chandak html
Nuttapong Chentanez, Andrew Barto, and Satinder Singh. Intrinsically motivated reinforcement learning. In Advances in Neural Information Processing Systems, 2005.
Maxime Chevalier-Boisverr, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https:: / htt.ttt.t.uuu.ggo/ thub. com/ma mecb/ gym-ggmmminnim mi 2018.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Computers and Games, 2007.
Özgür Şimşek and Andrew G. Barto. An intrinsic reward mechanism for efficient exploration. In International Conference Machine Learning, 2006.
Johannes Czech, Patrick Korus, and Kristian Kersting. Monte-carlo graph search for alphazero. arXiv preprint ar axXiv:2012.11044 2020.
D. P. de Farias and B. Van Roy. The linear programming approach to approximate dynamic program- ming. Operations Research, 2003.
Steven Diamond and Stephen Boyd. CVXPY: Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Rachit Dubey, Pulkit Agrawal, Deepak Pathak, Thomas I.. Griffiths, and Alexei Efros. Investigating human priors for playing video games. In International Conference on Machine Learning, 2018 8.
Gabriel Dulac-Amold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv: 1512. 0.7677 2016.
11

---

Under review as a conference paper at ICLR 2022
Gregory Farquhar, Laura Gustafson, Zeming Lin, Shimon Whiteson, Nicolas Usunier, and Gabriel Synnaeve. Growing action spaces. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3040-3051. PMIR, 2020. URL http:://pocceddd ings html
mlr. wttss///11//aarpaaaaaa
Yannis Flet-Berliac, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist, Adversarially guided actor-critic. In International Conference on Learning Representations, 2021.
Fred Glover. Future paths for integer programming and links artificial intelligence. Computers & Operations Research, 1986.
Nathan Grinsztajn, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist. There is no turning back: self-supervised approach for reversibility-wware reinforcement learning. arXiv preprint 106.04200 2021.
Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Alaa Saade, Shantanu Thakoor, Bilal Piot, Bernardo Ávila Pires, Michal Valko, Thomas Mesnard, Tor Lattimore, and Rémi Munos. Geometric entropic exploration. arXiv preprint wrXiv:2101.00000 000255, 2021.
Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, and Sergey Levine. Meta- reinforcement learning structured exploration strategies. and R. Garnett (eds.), Advances in Neural Information Processing
Bengio, H. Wallach, H. Larochelle,
K. Grauman, N. Systems, volume 31. Curran Associates, Inc., 2018. htRt:s/tt:////tttt pttpteeiss///.ooooeinnn...ss wwwp://oooceiiinoo.eeeeeeee..p.e neurips cC/ cc/paper/2011 22118/ file/ 4de 54 wwc.ccc9cccc8880 wwwcee (aceeeeeeeeceeeeeeeeeeeeeee11110 www.1199ddaPaaappppeeee Paper.
Elad Hazan, Sham M. Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning. 2019.
A. Hertz and D. Werra. The tabu search metaheuristic: How used it. Annals of Mathematics and Artificial Intelligence, 2005.
E. T. Jaynes. Information theory and statistical mechanics. Phys. Rev., 1957.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric P. Xing, Sergey Levine, and Ruslan Salakhut- dinov. Efficient exploration via state marginal matching. arXiv preprint 1:X.v::90.005777 2019.
Edouard Leurent and Odalric-Ambrym Maillard. Monte-carlo graph search: the value of merging similar states. In Asian Conference on Machine Learning, 2020.
Manuel Lopes, Tobias Lang, Mare Toussaint, and Pierre-yves Oudeyer. Exploration in model- based reinforcement learning by empirically estimating learning progress. In Advances in Neural Information Processing Systems, 2012.
Marlos Machado, Marc Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents (extended abstract). In 7iwenty-Seventh International Joint Conference on Artificial Intelligence (ICCAI), 2018. doi: 10.24963ijccai.00 2018///77..1//8877..
Anuj Mahajan and Theja Tulabandhula. Symmetry learning for function approximation in reinforce- ment learning. In International Joint Conference on Artificial Intelligence, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charlie Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533, 2015.
Georg Ostrovski, Mare G. Bellemare, Aäron van den Oord, and Rémi Munos. Count-based exploration with neural density models. International Conference on Machine Learning, 2017.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference Machine Learning, 2017.
12

---

Under review as a conference paper at ICLR 2022
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Antonin Raffin. RI baselines Zoo. http:////gtthh...oo///aaa/////// 2018.
zoo
Antonin Raffin, Ashley Hill, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, and Noah Dormann. Stable baselines3. 2019.
Andrei A. Rusu, Neil C. Rabinowitz, Guillaume Desjardins, Hubert Soyer, J. Kirkpatrick, K. Kavukcuoglu, Razvan Pascanu, and R. Hadsell. Progressive neural networks, arXiv preprint arXiv:1606.04671, 2016.
J. Schmidhuber. A possibility for implementing curiosity and boredom in model- model-building neural controllers. In International Conference on Simulation of Adaptive Behavior, 1991.
David Silver, Aja Huang, Christopher Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schritwwesser, loannis Antonogiou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484-503, 503, 2016. URL http: 6961 html
7 //www. nature com nawurattueeeeeeeoaa http://ooo..a///////////////////
Alexander L. Strehl and Michael I.. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 2008.
Arash Tavakoli, Fabio Pardo, and Petar Kormushev. Action branching architectures for deep reinforce- ment learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intellignnce (EAAI-18), 2018.
Guy Tennenholtz and Shie Mannor. The natural language of actions. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 66205 PMLR, 2019. URL URL/atpp./pprceeednn html
mlr. www.pprssssse.. v9 /ttress/777/tmmmoooltlll/
Marin Toromanoff, Emilie Wirbel, and Fabien Moutarde. Is deep reinforcement learning really superhuman on atari? leveling the playing field. arXiv preprint arXiv: 1908. 04683, 2019.
Elise van der Pol, Daniel Worrall, Herke van Hoof, Frans Oliehock, and Max Welling. Mdp homomorphic networks: Group symmetries in reinforeement learning. In Advances in Neural Information Processing Systems, 2020.
13

---

Under review as a conference paper at ICLR 2022
We organize the supplementary material 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
Proposition we have two pairs of equivalent sequences over M. i.e. W1, w2 wa wa E A such
that
W1 W2
W3 W4
then the concatenation of the sequences are also equivalent sequences:
W1 W/ W2 W2
Proof. For any S, we have T(8, w1) (s, w2) as wi w2. We apply the same property for Wy and u4 the state T(s, wi):
T(T wi), wz) T(T(s, ()),, wa) T(s,, 11 w))w3) = T(s, w2.W4)
Therefore W1.W3 W2.W44.
A.2 PROOF OF THEOREM 1
Theorem 1. Given an equivalence set ~i is an equivalence relationship. Furthermore, for E A", onp =
wo is equivalence relation ue A"
Proof.
We immediately have r v by choosing U1 A in equation 3 and therefore mag V. thus is reflexive.
is clear from its definition that ~ is symmetric, ~ symmetric. Then, suppose that v ~Q w. We have n E N and V1,..., on E A* such that v ~ 01 ~ ... ~ on ~ w, therefore ~ Un ~ ... ~ U1 ~ v, thus w ~a v. Hence ~a is symmetric.
If u oy v and v ~a w. we have nı, ng E N, and u1...., un, A", U1. Ung E At. 1
such that ~ un m ~o the oh and ~i ~q wi Ung ~a w. It then clear that u oq U1 ~q ... ag Therefore cop transitive.
~g uny ~g n Un an ... aa Una ~o w, and thus u mag w.
The relation ~g is reflexive, symmetric and transitive. Therefore it is an equivalence relation.
rep implies
Proof. Let A". From Proposition I we immediately get ~ = ~M Then prove by immediate induction that Yn E N, Uy...., En A+,, v m 2i ~ ~ Un w, from which we deduce <gg implies e
m w = 0
14

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Graph Construction
Input Action set A; Input Equivalence set 92;
Input Maximum tree depth d:
Initialize the graph Initialize the set of states to expand S = {0};
(V, E) with V {0) and V 0;
Initialize the current tree depth =
Initialize dictionary & which stores partial sequences of Ω for each state of V while / < and + do newStates = {1:
for each state in S do for each action in A do
/ * create a node corresponding to (sstate, action) newState expandNode(state, action, f2, E); if newState not in V then
Because of sequence redundancies, the state may already appear in the graph.
V (newState]
newStates +- newStates U(newStatee::
end
E ((state, newState));
/ * Update the equivalences & (newState) to account for the new ways of reaching newState
E + UpdateDDicnewStute E, {)
end
end
1 - 1+
- newStates:
end
/* Prune edges such that the resulting graph is a DAG. T= GraphToDAG(();
Output DAG G;
15

---

Under review as a conference paper at ICLR 2022
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 92, and the desired depth d, and outputs a DAG. Informally, it starts from graph G (V; F.) reduced to root state {0) and iteratively expands G until distance to the root is reached. For a node n V we store in (v)) sequences which reach v, and are prefixes of sequences of S2. When expanding state E V using an action E A (Line. [2], look at every partial sequence s E E(v). If s.a is in Q2 it means that we have found a redundant sequence. If the equivalent sequence has already been computed, it means that node u representing T(u, s.a) has previously been added in G. Otherwise, we add a new node u. In both case, we update the equivalences (w) to account for the new ways of reaching u (Line. 18).
A.4 GRAPH CONSTRUCTION COMPLEXITY
constructing the graph necessitates three intricate loops: The first one goes over every internal node V. the second one loops the set of actions A, and the last loops over every partial sequence which allows to reach v from a parent node. Inside these three loops, one has compare the partial sequence with every sequence of ?. As sequence length in Q can be bounded by d, the complexity cost inside the tree loops is bounded by (((2)) d). The total complexity is therefore lower than [[[]] [[]d) O(VIIA (dd) As [V] I |Al the complexity can also be bounded by O(IA4 2d (dd).
As shown in Section 3.2
A.5 MODIFIED DQN
Our modified version of the DQN algorithm can be found at Algorithm
Algorithm 2: Modified DQN
Initialize replay memory D and Q-networks Qo and QP: Determine local-dynamics graph and the associated optimal exploration policy n": for episode = I to M do
Initialize new episode;
for = to T do
C C- set new c value with c-decay (e usually anneals linearly or is constant); Initialize at empty sequence v 4- A;
i 11) then
Sample exploring action a, n²" (v.-);
else end
Select greedy action a;;
U.O, (append a the end of sequence Execute a, and observe next state 8+41 and reward T: Store (5e, de, Ft, 8t4+) in replay buffer D Update 0 and 0' normally with minibatches from replay buffer D; if Length(v)=d then
Reset u <- A;
end
end
end
A.6 POSSIBLE EXTENSION TO 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. [ the construction of local-dynamies graph (Section 3.2 and the construction of local exploration policy by solving a convex problem (Section 4.2p. We now detail for each step the necessary changes to adapt EASEE to M (S, R, 7). MDP with stochastic dynamics.
16

---

Under review as a conference paper at ICLR 2022
Action Sequence equivalences: the difference with the deterministic case here is that given an action a E AA and state 8 E S. T(s. a) is not a state but a distribution over the set of states S. Therefore every equality considered in Section has an equality between two states but between two distributions. Other than this the formalism can be kept identical. Intuitively, two sequences of actions equivalent if they lead the same state distribution from any given state, i.e. if they produce the same effect everywhere.
be understood not as
Local-Dynamics Graph: Here, the formalism can again be kept identical. A node in the local-dynamics graph will represent state anymore, but rather 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 stochastic setting would require encoding additional priors about the distributions represented by the nodes of the docal-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.I GRIDWORLDS
5 We tested EASEE on the DoorKey task. An illustration of the initial state is given in Fig. 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 17 grids. The agent has 3249 timesteps reach the goal and receive reward of before the environment is reset.
Figure 5: Example of initial state of DoorKey environment.
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 block per timestep, so each episode lasts 30 timesteps.
We use the same architecture for the DQN with and without EASEE. Each observation is 60 x 30 image. The feature extractor network is CNN composed of convolution layers with kernel size followed by ReLU activation. In both cases, update the online network every 4 timesteps, and the target network every 10 timesteps. We use a replay buffer of size 10 and sample batches of size 32. We the Adam optimizer with learning rate of 10-4
17

---

Under review as a conference paper at ICLR 2022
We train for 3.10" 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).
B.3 FREEWAY
00
00
ACII-TSION
Figure 6: The Freeway environment from Atari 2600.
Environment In Freeway, the agent has to cross a road with multiple lanes without getting hit by the cars. It only receives reward when it safely reaches the other side of the road. An illustration is given Fig. 6. The agent represented by the yellow chicken.
To add stochasticity the dynamic of the environment, 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 x 84 x 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.
sticky actions proposed in Machado
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 MniM et al. (2015). We update the online network every 4 timesteps, and the target network every 10a timesteps. We use replay buffer of size 103, and sample batches of size 32. We use the Adam optimizer with learning rate of 10-1
We train for 10" timesteps. The exploration parameter is linearly annealed from down to 0.01 over 10% of the training period, which are the default in Raflin (2018) for Atari games. Other DQN hyperparameters were defaults in Raffin et al. (2019).
B.4 ADDITIONAL EXPERIMENTS
Environments We experimented EASEE on two other Atari environments, where the action sequence structures are less forwidd The three environments preprocessed 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 "FTRE" button). The action space is composed of 18 actions NOOP, FIRE, UP, RIGHT, LEFT, DOWN, UPRIGHT, UPLEFT, DOWNRIGHT, DOWNLEFT, UPFIRE. RIGHTFIRE. LEFTFIRE IRE, DOWNFIRS UPRIGHTFIRE UPLEFTFIRE, DOWNRIGHTFIRE DOWNLEFTFIRE We incorporated priors by decomposing actions, the form of UPRIGHT UP U..IIGH, UPLEFT ~ UP.LEFT, UPRIGHTFIRE UPRIGHT F FIRE, UPLEFTFIRE UPLEFT. FIREF..FIRRR FIRE, etc...
The goal of the game is to shoot targets, which include rabbits, ducks, owls, scroll across the screen in alternating directions, and sometimes come at the player. The player only move in direction, such that the action space is composed of 6 actions: [NOOP, FIRE, RIGHT, LEFT, RIGHTF IRE, LEFTF IRE]. As NOOP is not an useful ac- tion, EASEE could get edge simply by adding the equivalence NOOP A. For fair
Carnival:
18

---

Under review as a conference paper at ICLR 2022
DQN
5000
DON
80
DON + EASEE
DON EASEE
4000
Reward
60
Reward
2000
20
1000
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
0.0
0.5
1.0
1.5
2.0
Number of timesteps
1e7
Number timesteps
1e7
(a) Boxing
(b) Carnival
Figure 7: Performances of DQN and DQN + EASEE on the Atari 2600 games Boxing, Carnival. 95% confidence interval over 10 random seeds is shown.
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 BppendixB.3 In all three environments, EASEE is used with depth of 4.
We can see the results on Fig improvement for Carnival. This can come from various factors:
Results
can see a slight gain for Boxing, and a marginal
When the number of action sequence equivalences considered is small compared to the number of actions, 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 standard DQN.
The action sequence equivalences considered here are only approximately true. In boxing, is only approximately true that UPRIGHT ~ UP RIGHT for example. In Carnival, RIGHT and LEFT commute long as the player is the edges of the screen, in which RICHT or LEFT could have no effect. In both cases, this induces a bias that may harm performance.
19


Reviews:
[{"review_id": "oepR33aM6ug", "reviewer": "Reviewer_FrAt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea proposed in the paper is quite elegant, albeit its realization is quite complex. The paper does a great job at explaining all the steps that go from equivalent sequences of actions, to an actual local policy that can be queried for an exploratory action. Overall, the paper is well-written, even if its complexity is sometimes a bit difficult for the reader.\n\nI think that the paper would greatly benefit from a quick summary of what it does. In the introduction, the last paragraph gives a bit of guidance, but already a bit too technical in my opinion (\"Then, we show that priors on this type of structure can easily be exploited during offline exploration by solving a convex optimization problem\") for instance. I would put, either in the introduction or in a dedicated \"Overview\" section, an intuition of the steps that the algorithm takes:\n\n- Assume that we have sets of equivalent actions sequences for the environment. Equivalent action sequences are sequences that lead to the same state (please correct me if I'm wrong)\n- These sequences are used, from a current state $s_t$, to build a DAG, that sorts of 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. This is the information that we want to extract.\n- In a Q-Learning-like algorithm, every time-step, construct the DAG above for $s_t$, then, with probability $\\varepsilon$, execute an exploratory action $a_t$ that maximizes the entropy of the future visited states.\n\nA further intuition about the fact that the resulting exploratory policy will, basically, assign low probabilities to actions that share a same future outcome, may also help the reader understand why the proposed algorithm is beneficial to exploration.\n\nSomething else that could be made clearer is when the state-space has to be discretized. It seems that the DAG nodes don't consider states, but it is not that clear to me, and I have the feeling that explicitly mentioning what happens to the states in the Freeway example may help.\n\nOther than that, I think that the paper is highly novel and proposes a complicated (but justified) algorithm. As such, I recommend accepting it.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper is relatively well-written, and proposes a sound algorithm that leads to good empirical results (even if the amount of empirical results is quite low). The algorithm is general enough to be applicable to an Atari game, with minimal engineering effort. The approach is quite novel, and multi-disciplinary (RL, information theory, convex optimization). As such, I think that the paper will be very interesting to people attending ICLR, and recommend accepting it.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HCiKSbUe9j5", "reviewer": "Reviewer_Ln9a", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n-The paper formalizes an interesting phenomenon of equivalent action sequences that exists in some MDPs. \n\n-The method to construct a sampling policy that maximizes entropy is interesting. It uses a local dynamics graph built using action sequence equivalence knowledge  + convex optimization to  accomplish this.\n\n\nWeaknesses:\n\n-The formulation of equivalent action sequences could be simplified -- although nice, I’m not sure all of the formality is necessary here.\n\n-The method is designed for deterministic MDPs, in which case it is believable that the transitions are known. The authors also discuss an extension to the stochastic case, where equivalences are determined based on next state distributions. This seems nearly impossible in the model-free RL setting. Even in a dynamic programming setup where the stochastic transitions are fully known, it can be difficult to verify equality of distributions. Moreover, even if it were possible to verify, I cannot think of any problem where we’d expect equality of next state distributions between action sequences.\n\n-All experiments are performed on simple domains. It is unclear how applicable this method is in real problems.\n", "summary_of_the_paper": "This paper considers a property of MDPs where multiple sequences of states end up at the same action. The main contributions of this paper are (1) a formalization of the action sequence phenomenon, (2) an algorithm to build a local dynamics graph, (3) a simple exploration procedure based on the local dynamics graph.\n", "summary_of_the_review": "Overall, I am not convinced that the method is truly useful in real settings beyond the deterministic + spatial problems that the paper focuses on. The formalization of equivalent action sequences satisfied my curiosity but is perhaps slightly overkill and unnecessary. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6i_IFHX8KJ4", "reviewer": "Reviewer_5h9r", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written very clearly and the contributions are easy to follow. The idea of using explicit equivalences is fairly simple and I found it surprising this has not been done before (or at least, I couldn't find such a reference). I was thinking about how this work could be meaningfully built upon to improve a general zero-knowledge RL algorithm. I see only a single extension, where the exploration strategies are learned: however this is already studied in prior work [1]. The paper therefore seems to fill a \"void\" in the hand-crafted case with known priors. I don't find this sufficiently significant as its own contribution. Additionally, the applicability seems to be limited to grid-like MDPs, where it is easy to hand-craft the action-equivalences. For more general environments the improvement seems marginal (Figure 7). \nA suggestion how to make the work and empirical results more interesting: perhaps the problem can be cast as a Bayesian update using the hand-crafted priors with meta-learning [1].\n\nOther notes:\n\n- \"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.\" Why? Can you give an example when this would not be possible? I believe it should be straightforward to use uniform strategy in the abstracted MDP and translate it back to the original problem. Since this is much simpler than solving the optimization problem, it would be preferrable, and a comparison to the max-entropy solution should be made.\n- Action Space Structure: there is no explanation how the last 3 references relate to the work.\n\n\n[1] Meta-Reinforcement Learning of Structured Exploration Strategies, Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, Sergey Levine\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "I recommend 5) marginally below the acceptance threshold. There is existing literature that tackles the problem of exploration in a more general way without handcrafting prior knowledge into the problem.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This well-written paper introduces an improved exploration strategy by exploiting knowledge about sequences of actions that lead to the same state. The idea is straightforward and easy to understand and apply, which makes it potentially interesting. An important downside is the limited applicability of the method, as there mainly seems to be an advantage in (mostly deterministic) grid-like MDPs. In addition, priors about action-sequence equivalences have to be available. Overall, the contribution of the paper is not deemed significant enough for publication at a top-tier conference like ICLR by the majority of the reviewers as well as myself. For these reasons, I recommend rejection.
Decision: Reject