Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks
Authors: Sungryull Sohn
Sungtae Lee
Jongwook Choi
Harm van Seijen
Honglak Lee
Mehdi Fatemi
Venue:  (2021)
Keywords: reinforcement learning
exploration
sample efficient reinforcement learning
sparse rewards

Abstract: We propose the k-Shortest-Path (k-SP) constraint: a novel constraint on the agent’s trajectory that improves the sample-efficiency in sparse-reward MDPs. We show that any optimal policy necessarily satisfies the k-SP constraint. Notably, the k-SP constraint prevents the policy from exploring state-action pairs along the non-k-SP trajectories (e.g., going back and forth).  However, in practice, excluding state-action pairs may hinder convergence of many RL algorithms. To overcome this, we propose a novel cost function that penalizes the policy violating SP constraint, instead of completely excluding it.  Our numerical experiment in a tabular RL setting demonstrate that the SP constraint can significantly reduce the trajectory space of policy. As a result, our constraint enables more sample efficient learning by suppressing redundant exploration and exploitation. Our empirical experiment results on MiniGrid and DeepMind Lab show that the proposed method significantly improves proximal policy optimization (PPO) and outperforms existing novelty-seeking exploration methods including count-based exploration, indicating that it improves the sample efficiency by preventing the agent from taking redundant actions.

Under review as a conference paper at ICLR 2021
SHORTEST-PATH CONSTRAINED REINFORCEMENT LEARNING FOR SPARSE REWARD TASKS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose the k-Shortest- Path (k-SP) constraint: a novel constraint on the agent's s trajectory that improves the sample-effcciency in sparse-reward MDPs. We show that any optimal policy necessarily satisfies the k-SP constraint. Notably, the k-SP constraint prevents the policy from exploring state-action pairs along the non-k-SP trajectories (e.g., going back and forth). However, in practice, excluding state-action pairs may hinder convergence of RL algorithms. To overcome this, we propose a novel cost function that penalizes the policy violating SP constraint, instead of completely excluding it. Our numerical experiment in a tabular RL setting demonstrate that the SP constraint can significantly reduce the trajectory space of policy. As a result, our constraint enables more sample efficient learning by suppressing redundant exploration and exploitation. Our experiments on MiniGrid and DeepMind Lab show that the proposed method significantly improves proximal policy optimization (PPO) and outperforms existing novelty-seeking exploration methods including count-based exploration, indicating that it improves the sample efficiency by preventing the agent from taking redundant actions.
INTRODUCTION
Recently, deep reinforcement learning (RL) has achieved a large number of breakthroughs in many domains including video games (Mnih et al., 2015; Vinyals al., 2019), and board games (Silver et al., 2017). Nonetheless, a central challenge in reinforcement learning (RL) is the sample effi- ciency (Kakade et al., 2003); has been shown that the RL algorithm requires large number of samples for successful learning in MDP with large state and action space. Moreover, the success of RL algorithm heavily hinges on the quality of collected samples; the RL algorithm tends to fail if the collected trajectory does not contain enough evaluative feedback (e.g., sparse or delayed reward).
To cireumvent this challenge, baanning-based methods utilize the environment's model to improve or create a policy instead of interacting with environment. Recently, combining the planning method with an efficient path search algorithm, such as Monte-Carlo tree search (MCTS) (Norvig, 2002; Coulom, 2006), has demonstrated successful results (Guo et al., 2016; Vodopivec et al., 2017; Silver et al., 2017). However, such tree search methods would require an accurate model of MDP and the complexity of plamning may grow intractably large for complex domain. Model-basee RL methods attempt to learn a model instead of assuming that model is given, but learning an accurate model also requires large number of samples, which is often even harder to achieve than solving the given task. Model-free RI. methods can be learned solely from the environment reward, without the need of (learned) model. However, both value-based and policy-based methods suffer from poor sample efficiency especially in sparse-reward tasks. To tackle sparse reward problems, researchers have proposed learn an intrinsic bonus function that measures the novelty of the state that agent visits (Schmidhuber, 1991; Oudeyer & Kaplan, 2009; Pathak et al., 2017; Savinov et al., 2018b; Choi al., 2018; Burda et al., 2018). However, when such intrinsic bonus added to the reward, it often requires careful balancing between environment reward and bonus and scheduling of the bonus scale in order to guarantee the convergence to optimal solution.
To tackle aforementioned challenge of sample efficiency in sparse reward tasks, we introduce constrained-RL framework that improves the sample efficiency of any model-free RL algorithm in sparse-reward tasks, under the mild assumptions on MDP (see Appendix G). Of note, though our framework will be formulated for policy-based methods, our final form of cost function (Eq. (10) in Section 4) is applicable to both nosecy-based and value-based methods. We propose novel k-shortest- path (k-SP) constraint (Definition 7) that improves sample efficiency of policy learning (See Figure 1). The k-SP constraint is applied trajectory rolled out by policy; all of its sub-path

---

Under review as a conference paper at ICLR 2021
Unconstrained
Constrained
k-shortest-path (k-SP) constraint (k=2)
Path
Sub-paths
k-SP?
1=0-2
RNel
SP
True
MDP
0
N/A
1--3
K-SP constraint
Path
Sub-paths
k-SP?
Roll
t=0-2
RNet
Non .SP
-out
Tree
False
B
t=1-3
RNel
SP
Initial state:
Rewarding state:
Non-rewarding state
Allowed transition:->>
Path:
RNet: RNet|
AND:
The k-SP constraint improves sample efficiency of RL methods in sparse-reward tasks by pruming out suboptimal trajectories from the trajectory space. Intuitively, the k-SP constraint means that when policy rolls out into trajectories, all of sub-paths of length & is shortest path (under a distance metric defined in terms of policy, discount factor and transition probability; see Section 3.2 for the formal definition). (Lefft) MDP and rollout tree are given. (Middle) The paths that satisfy the k-SP constraint. The number of admissible trajectories is drastically reduced. (Right) path rolled out by policy satisfies the k-SP constraint if all sub-paths of length & are shortest paths and have not received non-zero reward. We use reachability network to test a given (sub-)path is a shortest path (See Section 4 for details).
Figure 1:
of length k is required to be a shortest-path under the N-distance metric which we define in Section 3.1. We prove that applying our constraint preserves the optimality for any MDP (Theorem 3), except the stochastic and multi-gou MDP which requires additional assumptions. We relax the hard constraint into a soft cost formulation (Tessler et al., 2019), and use a reachability network (Savinov et al., 201 8b) (RNet) to efficiently learn the cost function in off-policy manner.
We summarize our contributions as the following: (1) We propose a novel constraint that can improve the sample efficiency of any model-free RL method in sparse reward tasks. (2) We present several theoretical results including the proof that our proposed constraint preserves the optimal policy of given MDP. (3) We present numerical result in tabular RL setting to precisely evaluate the effectiveness of the proposed method. (4) We propose a practical way to implement our proposed constraint, and demonstrate that it provides a significant improvement
two complex deep RL domains. (5) We demonstrate that our method significantly improves the sample-efficiency of PPO, and outperforms existing novelty-seeking methods on two complex domains in sparse reward setting.
2 PRELIMINARIES
Markoy Decision Process (MDP). We model a task as an MDP tuple M = (S,A, where S is a state set, A is an action set, P is transition probability, R is reward function, is an initial state distribution, and 7 E [0, 1) is a discount factor. For each state s, the value of a policy is denoted by V maximizes the expected return:
E 1E 7 8o s). Then, the goal is to find the optimal policy x' that
arg max E
Σ rrr 80 8 = arg max Eggrep (s))
Constrained MDP. A constrained Markov Decision Process (CMDP) is an MDP with extra con- straints that restrict the domain of allowed policies (Altman, 1999). Specifically, CMDP introduces a constraint function C(T) that maps policy a scalar, and a threshold c E R.. The objective of CMDP maximize the expected return R(T) E, 7'r, , of trajectory T (No, agz T1; 81, 01, r2; 82,..) subject to constraint: x² arg max, Enw [R(T)], s.t. C(x) a.
A popular choice of constraint is based on the transition cost function (Tessler et al., 2019) c(s, r, s') E RR which assigns scalar-valued cost to each transition. Then the constraint function for a policy π is defined as the discounted sum of the cost under the policy: C(T) = Eysx [E, "c((st, a,, T1+1, 8(41] []] In this work, propose shortest-patt constraint, that provably preserves the optimal policy of the original unconstrained MDP, while reducing the trajectory space. We will use cost funstion-based formulation implement constraint (see Section 3 and 4).
2

---

Under review as a conference paper at ICLR 2021
3 FORMULATION: k: H-OTORT PATH CONSTRAINT
We define the k-shortest-path (k-SP) constraint to remove redundant transitions (e.g., unnecessarily going back and forth), leading to faster policy learning. We show two important properties of our constraint: (1) the optimal policy is preserved. and (2) the policy search space is reduced.
In this work, we limit our focus to MDPs satisfying R(s) ((s)+7VV' +>V*(s) > 0 for all initial states & E p and all rewarding states that optimal policy visits with non-zero probability We exploit this mild assumption to prove that our constraint preserves optimality. Intuitively, we exclude the case when the optimal strategy for the agent largest but negative value) which often still means a failure. We note that this is often caused by unnatural reward function design; in principle, we can avoid this by simply offsetting reward function by a constant - (s)r conditioned RL (Nachum et al., 2018) and most of the well-known domains such as Atari (Bellemare et al., 2), DeepMind Lab (Beattie et al., 2016), MiniGrid (Chevalier-Boiveer et al., 2018), etc., satisfy this assumption. Also, for general settings with stochastic MDP and multi- goall, we require additional assumptions to prove the optimality guarantee (See Appendix G for details).
{s|r(s) * 0, (s) > 0}.
best choosing a "lesser of evils" (i.e.,
[s) for every transition, assuming the policy is proper'. Goal-
3.1 SHORTEST-PATH POLICY AND SHORTEST-PATH CONSTRAINT
Let r be a path defined by sequence of states: = (80,- .... St(r)), }. where {(T) is the length of path r (i.e, {(T) = | - 1). We denote the set of all paths from to s' by Ts,s'. A path T" from to is called a shortest path from 8 to s' if ((T) is minimum, ie.,, E(T*) = min-eT,,"" ((T).
Now we will define similar concepts (length, shortest path, etc.) with respect to a policy. Intuitively, a policy that rolls out shortest paths (up to some stochasticity) a goal state or between any state pairs should be counterpart. We consider a set of all admissible paths from to s' under a policy n:
Definition (Path set). Te.s' = {T 80 = 8, St(r) = s', (T) > O, (stltcr(r) + *... That is, Th. is a set of all paths that policy л may roll out from 8 and terminate once visiting 8'.
If the MDP is a single-goal task, i.e., there exists a unique (rewarding) goal state sg E S such that sg is a terminal state, and R(s) > 0 if and only if = $g. any shortest path from an initial state to the goal state is the optimal path with the highest return R(T), and policy that rolls out shortest path therefore optimal (see Lemma 4).2 This because all states except for 8g are non-rewarding states, but in general MDPs this is not necessarily true. However, this motivates us to limit the domain of shortest path to among non-rewarding states. We define non-rewarding paths from s to s' as follows:
Definition 2 (Non-rewarding path set). Te. (- T TTi (rt)ece()> 0}-
In words, T .ar is set of all non-rewarding paths from s' rolled out by policy (i.e., E TT.e) without any associated reward except the last step (i.e., (re (re]<t1== = 0). Now we are ready to define a notion of length with respect policy and shortest path policy:
Definition (r-distance from s'). Dhe (s, s') log,, (BIN:::TTT, ". ( [x((t]])
Definition 4 (Shortest path distance from to s'). ss, = min, D (s,
We define x-distance to be the log-mean-ext mean---pooonntialll of the length ((T) of non-rewarding paths
E T "Ta'',arr When there exists no admissible path from to s' under policy ग, the path length is defined to be oo: (s, = oo if TT."". .nr = 0. We note that when both MDP and policy are ((T).
deterministic, D (s, 8') recovers the natural definition of path length, D (8, s')
We call a policy a shortest-path policy from 8 to s' if it roll outs a path with the smallest dddisannce: Definition 5 (Shortest path policy from to s').
II
- {T II D (s, s') = Dar (s. s')}.
Finally, we will define the shortest-path (SP) constraint. Let S = {s R(s) > 0 p(s) > 03 be the union of all initial and rewarding states, and कht = ((x,5') 8, 8' E SIR p(s) 0, T. T. .ur # 0) be the subset of SRR such that agent may roll out. Then, the SP constraint applied to the non- rewarding sub- sub-paths between states in == T = -(e.e")0== TT. We note that these definitions used in the proofs (Appendix G). Now, we define the shortest- constraint follows:
Definition 6 (Shortest-path constraint). A policy & satisfies the shortest-path (SP) constraint if т SI where S1 = (- For all s, s' E TT it holds π 11 }1
'It is an instance of potential-hased reward shaping which has optimality guarantce (Ng ct al., 1999). We refer the readers to Appendix F for more detailed discussion and proofs for single-goal MDPs.
3

---

Under review as a conference paper at ICLR 2021
Intuitively, the SP constraint forces a policy to transition between initial and rewarding states via shortest paths. The SP constraint would be particularly effective in sparse-reward settings, where the distance between rewarding states is large.
Given these definitions, general MDP setting. In other words, the shortest path constraint should not change optimality:
show that optimal policy indeed satisfies the SP constraint in
Theorem 1. For any MDP, an optimal policy n² satisfies the shortest-path constraint: x² E IISP.. Proof. See Appendix G for the proof.
3.2 RELAXATION: &-SHORTEST--AAEE CONSTRAINT
Implementing the shortest-path constraint is, however, intractable since it requires distance predictor (s. s'). Note that the distance predictor addresses the optimization problem, which might be as difficult solving the given task. To circumvent this challenge, we consider its more tractable version, namely a k-shortest path constraint, which reduces the shortest- -att problem Dur (s, s') binary decision problem is the state s' reachable from s within k steps? also known as k-reachability (Savinov et al., 2018b). The k-shortest path constraint is defined as follows:
Definition (E-shortest-paate constraint). A policy x satisfies the k k-shortest- shortest-path constraint if Ih where
SP 1 = { For all s E TT (s, 8') S k. holds π E }.
(2)
Note that the SP constraint (Definition 6) is relaxed by adding a condition (s, k. other words, the k-SP constraint is imposed only for s' e'-path whose length is not greater than k. From Eq. (2), we can prove an important property and then Theorem 3 (optimality): Lemma 2. For an MDP M, I
C if m.
Proof. It is true since {(8,8) DE (s, 8') < k) C ((8,8) ( (s, S m) for < m.
Theorem 3. For MDP M and any l E R, optimal policy n² is k-shortest-palt policy. Proof. Theorem 1 tells x² E TTSP. Eq. (2) tells ITSP -TT and Lemma tells ITSP C ITSP
Collectively, we have x² E ITSP ST C ST
LI
In conclusion, Theorem 3 states that the k-SP constraint does not change the optimality of policy, and Lemma 2 states larger k results in a larger reduction in policy search space. Thus, it motivates to apply the k-SP constraint in policy search to more efficiently find an optimal policy. For the numerical experiment measuring the reduction in the policy roll-outs space, please refer to Section 6.4.
SPRL: SHORTEST-PATEE REINFORCEMENT LEARNING
A-Shortest-Path Cost.
The objective of RL with the k-SP constraint IIş can be written as:
x¹ = arg max, ES [R(T)], s.t. π E ITS.
(3)
where 11 { V(s,s' E .. D (s, s') I k, it holds &I (Definition 7). We want to formulate the constraint E S in the form of constrained MDP (Section 2), i.e., as C(T) S a. We begin by re-writing the K-SP constraint into a cost-based form:
11 = ( C (T) 0}. where (S((T)
Σ
[[ (s, (4)
(8.6'ET B..ETT...:DDAAAA Di
Note that [s,nnss, (s, = + (mn ss,s') since (nr 8') D (s,
from Definition 4. Similar to Tessler et al. (2019), we apply the constraint to the on on-policy trajectory $1,...) with discounting by replacing (s, s') with (s,, St41) where [t, + represents each segment of 7 with length l:
( (T) ~ E Euwiioorss I[Dnr(st < D (8t, 81+)) | = o]]
Ei.0)22015 7 [p (nr( < log, [E i [-1]]]
1 o]]
Eysa
E BYNT
EueyaeoueR -- I[Dur S(4) < k] x I [1r (
(5)
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Reinforcement Learning with k-SP constraint (SPRL)
Require: Hyperparametters: lt E X
1: for n = 1,..., Npolicy do
2:
Rollout transitions T {st, dz, Nt rt) ~
3: Compute the cost term {cr)
||| as Eq. (13).
4: Update policy π to maximize the objective as Eq. (10) (c.g.. run PPO train steps).
5:
Update Rnet training-buffed B B U (7).
6:
if m = then
Periodically train Rnet for No times
7:
for m L,..., NReett do
8:
Sample triplet (Sinc: 84,, 9-) ~ B. Update Rnet minimize LReet as Eq. (14).
D See Appendix D.3 for detail
9:
Note that it is sufficient to consider only the cases / = k (because for < k. given Der (8t,8 < k. I 1 < k). Then, we simplify (T((T) as
we have D (st,, S(+1)
Ch (T) = E
Σx [Drr S141) < kj [(r 14tk-1 =0]
(6)
ETTT
Dx I'I 2 k] I[D (s) k) .I (
(7)
Finally, the per-time step cost Ct is given as:
4 T| 2 k] Dur (5 01) < k] ( =
(8)
where (T) = B,~xx EE,''el Note that (T) is an upper bound of (T), which will be minimized by the bound make as little violation of the shortest-path constraint as possible. Intuitively speaking, Ct penalizes the agent from taking a non-k-shortest path at each step, so minimizing such penalties will make the policy satisfy the e-shortest-patt constraint. In Eq. (8), er depends on the previous k steps; hence, the resulting CMDP becomes (k: + 1)-th order MDP. In practice, however, we empirically found that feeding only the current time-step observation to the policy performs better than stacking the previous k-steps of observations (See Appendix A.3 for details). Thus, we did not stack the observation in all the experiments. We use the Lagrange multiplier method to convert the objective (3) into an equivalent unconstrained problem follows:
min max L(>,0) 0) min max ETT E. (r. (ra- (xa-)) X>0
X>0 9
where I. is the Lagrangian, 0 is the parameter of policy म, and À > is the Lagrangian multiplier. Since Theorem 3 shows that the shortest-path constraint preserves the optimality, we are free to set any O. Thus, we simply consider À as a tunable positive hyperparameter, and simplify the min-max problem (9) to an RL objective with costs being added:
Σ, (re Aca)
max BraNy
(10)
Practical implementation of the cost function. We implement the binary distance discriminator I(Dar (st-k, st) < k) in Eq. (8) using k-reachability network (Savinov al., 2018b). The k- reachability network Rnete(s, (s, s') is trained to output if the state s' is reachable from the state with less than or equal to l consecutive actions, and 0 otherwise. Formally, we take the functional form: Rneta (s, 8¹) ~ I1 (Dnr(s, s²) < k 1). We then estimate the cost term e using (k reeehcchaiylity network as follows:
Q I [ (St-k. s1) kl II [Im = 0] I[t 2 k]
(11)
R 8t) [(r))=)1 - 0] - kj.
(12)
Intuitively speaking, if the agent takes a k-shortest path, then the distance between 8 and 8, is k hence a = O. If it is not a k-shortest path, 6 > 0 since the distance between 8t-& and 8, will be less than k. In practice, due the error in the reachability network. we add a small tolerance At e N to ignore outliers. It leads to an empirical version of the cost as follows:
~ Rnet, 1 (St k- St) [ k-Ai 0] I(t 1 k+ At).
(13)
5

---

Under review as a conference paper at ICLR 2021
In experiment, found that small tolerance At k/5 works well in general. Similar to Savinov et al. (2018b), we used the following contrastive loss for training the reachability network:
Lrett - log (Rnets-1 1 8+)) - log (1 - Rnets- ( 8 8-)),
(14)
where Sancy 5 8_ are the anchor, positive, and negative samples, respectively (See Appendix D.3 for the detail of training).
5 RELATED WORK
Connection between shortest-path problem and planning. Many early works (Bellman, 1958; Ford Jr, 1956; Bertsekas & Tsitsiklis, 1991; 1995) have discussed (stochastic) shortest path problems in the context of MDP. They viewed the shortest-path problem as planning problem and proposed dynamic programming-basse
algorithm similar to the value iteration (Sutton & Barto, 2018) to solve it. Our main idea inspired by (but not based on) this viewpoint. Specifically, our method does not directly solve the shortest path problem via planning; hence, method does not require model. Our method only exploits the optimality guarantee of the shortest-pathe under the r-distance to prune out sub-optimal policies (i.e., non-shortest paths).
Distance metric in goal-conditioned RL. In goal-conditioned RL, there has been a recent surge of interest learning a distance metric in state (or goal) space for to construct high-level MDP graph and perform planning to find shortest-path to the goal state. Huang et al. (2019); Laskin et al. (2020) used the universal value function (UVF) (Schaul et al., 2015) with constant step penalty as a distance function. Zhang et al. 20; Laskin et al. (2020) used the success rate of transition between nodes as distance and searched for the longest path to find the plan with highest success rate. SPTM (Savinov et al., 20) defined a binary distance based on reachability network (RNet) to connect near by nodes the graph. However, the proposed distance metries and methods can be used only for the conl-condi task and lacks the theoretical guarantee in general MDP, while our theory and framework are applicable to general MDP (see Section 3.1).
Reachability network. The reachability network (RNet) was first proposed by Savinov et al. (2018) 22) as way to measure the novelty of a state for exploration. Intuitively, if current state not reachable from previous states in episodic memory, it is considered to be novel. SPTM (Savinov et al., 201 8a) used RNet to predict the local connectivity (i.e., binary distance) between observations memory for graph-based planning in navigation task. On the other hand, we use RNet for constraining the policy (i.e., removing the sub-optimal policies from policy space). Thus, in ours and in other two compared works, RNet is being employed for fundamentally different purposes.
More related works. Please refer Appendix H for further discussions about other related works.
6 EXPERIMENTS
Figure 2: An example observation of (a) FourRooms-11 11x11, (b) KeyDoors- x in MiniGrid, (c) Goallarge in DeepMind Lab, and (d) the maze layout (not available the agent) of Goallarge.
6.1 SETTINGS
Environments. We evaluate our SPRL on two challenging domains: MiniGrid (Chevalier-Boisvert al.. 2018) and DeepMind Lab (Beattie et al., 2016). MiniGrid is 2D grid world environment with challenging features such as pictorial observation, random initialization of the agent and the goal, complex state and action space where coordinates, directions, and other object statuses (e.g., key-door) considered. We conducted experiments on four standard tasks: FourRooms-7x2 FourRooms- x KeyDoors-7x7. and KeyDoors-I xx11.. DeepMind Lab a 3D environment with first person view. Along with the nature of partially- oobservl MDP, at each episode, the agent's initial and the goal location are reset randomly with a change of texture, maze structure, and colors. We conducted experiments on three standard tasks: GoalSmall, GoalLarge and ObjectMany. We refer the readers to Figure for examples of observations.
GGoll task corresponds to the Sparse task in Savinov et al. (2018h) 8b), and our Figure 4 reproduces the result reported in Savinov et al. (2018b).

---

Under review as a conference paper at ICLR 2021
Baselines. We compared our methods with four baselines: PPO (Schulman et al., 2017). episodic curiosity (ECO) (Savinov et al., 2018b), intrinsic curiosity module (ICM) (Pathak et al., 2017), and GT-Grid (Savinov et al., 2018b). The PPO is used as baseline RL algorithm for all other agents. The ECO agent is rewarded when it visits a state that is not reachable from the states in episodic memory within a certain number of actions; thus the novelty is only measured within an episode. Following Savinov et al. (2018b), we trained RNet in an off-policy manner from the agent's s experience and used it for our SPRL and ECO on both MiniGrid (Section 6.2) and DeepMind Lab (Section 6.3). For the accuracy of the learned RNet on each task, please refer to the Appendix B. The GT-Grrd agent has access the agent's (z. y) coordinates. uniformly divides the world in 2D grid cells, and the agent is rewarded for visiting novel grid cell. The ICM agent learns a forward and inverse dynamies model and uses the prediction error of the forward model to measure the novelty. We used the publicly available codebase (Savinov et al., 201 to obtain the baseline results. We used the same hyperparameter for all the tasks for a given domain- - the details are described in the Appendix. We used the standard domain and tasks for reproducibility.
6.2
RESULTS ON MiniGrid
FourRooms- 7x7
FourRooms 11x11
KeyDoor 7x7
KeyDoor
1.00
1.00
1.00
1.00
SPRL
Return
0.75
0.75
0.75
Return
0.75
PPO
0.50
0.50
0.50
0.50
ECO
ICM
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
0.2
0.4
0
0
0.5
steps (Millions)
steps (Millions)
steps (Millions)
steps (Millions)
Figure 3: Progress of average episode reward on MiniGrid tasks. We report the mean (solid curve)
and standard error (shadowed area) of the performance over six random seeds.
Figure 3 shows the performance of compared methods MiniGrid domain. SPRL consistently outperforms all baseline methods over all tasks. We observe that exploration- -based methods (i.e., ECO, ICM, and GT-Grid) perform similarly the PPO in the tasks with small state space (e.g.. FourRooms-7xx 7 and KeyDoors-7xD However, SPRL demonstrates significant performance gain since it improves the exploitation by avoiding sub-optimality caused by taking a mnr-sshootstt-tatt 6.3
RESULTS ON DeepMind Lab
GoalSmall
ObjectMann
GoalLarge
150
SPRL
return
100
return
30
GT-Grid
PPO
20
20
ICM
50
10
15 steps (Millions)
10
20
10
15
20
steps (Millions)
steps (Millions)
Figure 4: Progress of average episode reward on DeepMind Lab tasks. We report the mean (solid curve) and standard error (shadowed area) of the performance over four random seeds.
Figure 4 summarizes the performance of all the methods on DeepMind Lab tasks. Overall, our SPRL method achieves superior results compared to other methods. By the design of the task, the difficulty of exploration in each task increases in the order of GoalSmall, ObjectMany, and GoalLarge tasks, and we observe a coherent trend in the result. For harder exploration tasks, the exploration-basse
methods (GT-Grid, ICM and ECO) achieve a larger improvement over PPO: e.g., 20%, 50%. and 100% improvement in GoalSmall, ObjectMany, and GoalLarge, respectively. As shown in Lemma 2, our SPRL is expected to have larger improvement for larger trajectory space (or state and action space) and sparser reward settings. We can verify this from the result: SPRL has the largest improvement in Goallarge task, where both the map layout is largest and the reward is most sparse. Interestingly, SPRL even outperforms GT-Grid which simulates the upper- bound performance of novelty-secking exploration method. This is possible since SPRL improves the exploration by suppressing unnecessary explorations, which is different from novelty-seeking methods, and also improves the exploitation by reducing the policy search space.
6.4 ANALYSIS ON Æ-SHORTEST-PATE CONSTRAINT
In this section, we numerically evaluate the effect of our k-shortest path constraint in tabular-RL. setting. Specifically, we study the following questions: (1) Does the k-SP constraint with larger k
7

---

Under review as a conference paper at ICLR 2021
results in more reduction in trajectory space? (i.e., validation of Lemma 2) (2) How much reduction
in trajectory space does k-SP constraint provide with different k and tolerance At?
Experimental setup. We implemented a simple tab- ular 7x7 Four-rooms domain where each state maps to unique (x, y) location of the agent. The agent can take up, down, left, right primitive actions move to the neighboring state, and the episode horizon is set to 14 steps. The goal of the agent reaching the goal state, which gives +1 reward and terminates the episode. We computed the ground-trun truth distance between a pair of states to implement the k-shortest path constraint, We used the ground-truth distance function instead of the learned RNet to implement the exact SPRI. agent.
Trajectory space reduction
Reduction ratio (%)
10
A =
===1
A =
10
10
K-3
K=7
K=11
Figure 5: (Left) 7x7 Tabular four-rooms domain with initial agent location (red) and the goal location (green). (Right) The trajec- tory space reduction ratio (%) before and af- ter constraining the trajectory space for ious k and A with k-SP constraint, Even small can greatly reduce the trajectory space with reasonable tolerance At.
Figure 5 summarizes the reduction in the tra- jectory space size. We searched over all possible tra- jectories of length 14 using breadth- wenetth--iisttseee first-search (BFS).
Results.
Then we counted the number trajectories satisfying our k-SP constraint with varying parameters h and toler- ance At and divided by total number of trajectories (i.e., 4t 268M). The result shows that our k-SP constraint drastically reduces the trajectory space even in a simple 2D grid domain; with very small k = 3 and no tolerance At 2, we get only 24/ 24/268M size of the original search space. As we increase we can see more reduction in the trajectory space, which is consistent with Lemma Also, increasing the tolerance At slightly hurts the performance, but still achieves large reduction (See Appendix for more analysis on effect of & and tolerance).
6.5 QUALITATIVE RESULT ON MiniGrid
(a) Random
(b) GT-UCB
(c) SPRL
(d) SPRL+Reward
Figure 6: Transition count maps for baselines and SPRL: (a), (b), and (c) are in reward-free (light green) while (d) is in reward-aware (dark green) setting. In reward-free settings (a-c), we show rewarding states in light green only for demonstration purpose. The location of agent's initial state (orange) and rewarding states (dark green) are fixed. The episode length is limited to 500 steps.
We qualitatively study what type of policy is learned with the k-SP constraint with the ground-truth RNet in NineRooms domain of MiniGrid. Figure (a-c) shows the converged behavior of our SPRL (k 15), the ground-truth count- based exploration (Lai & Robbins, 1985) agent (GT-UCB) and uniformly random policy (Random) in reward-free setting. We counted all the state transitions (s, + 1)+1) of each agent's roll-out and averaged over 4 random seeds. Random relies on the random walk and cannot explore further than the initial few rooms. GT-UCB seeks for a novel states, and visits all the states uniformly. SPRL learns to take longest possible shortest path, which results in a "straight" path across the rooms. Note that this only represents a partial behavior of SPRL, since cost also considers the existence of non-zero reward (see Eq. (8)). Thus, in (d), we tested SPRL while providing only the existence of non-zero reward (but not the reward magnitude). SPRL learns to take shortest path between rewarding and initial states that is consistent with the shortest-path definition in Definition 7.
7 CONCLUSION
We presented the k-shortest-path constraint, which can improve the sample-efficiency of any model- free RL method by preventing the agent from taking sub-optimal transition. We empirically showed that our SPRL outperforms vanilla RL and strong novelty-seekingg challenging domains. We believe that our framework develops unique direction for improving the sample efficiency in reinforcement learning; hence, combining our work with other techniques for better sample efficiency will be interesting future work that could benefit many practical tasks.
exploration baselines on two
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state abstraction. In International Conference on Machine Learning, pp. 2915-2923, 2016.
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. In International Conference on Machine Learning, pp. 10-19, 2018.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Charles Beattie, Joel Z Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Víctor Valdés, Amir Sadik, al. Deepmind lab. arXiv preprint arXiv:1612.03801, 2016.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Richard Bellman. On routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Dimitri Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-595, 1991.
Dimitri P Bertsekas and John Tsitsiklis. Neuro-dynamic programming: an overview. In Proceedings of 1995 34th IEEE Conference on Decision and Control, volume 1, pp. 560-564. IEEE, 1995.
Dimitri P Bertsekas, David Castanon, al. Adaptive aggregation methods for infinite horizon dynamic programming. 1988.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprini arXiv: 1810. 12894, 2018.
Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic markov decision processes. arXiv preprint arXiv:1911.09291 2019.
Maxime Shevalier-Boisvers Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https://///
sereecb/yymmaee h//gg/ymmmmii aepm-minigriie 2018.
Jongwook Choi, Yijie Guo, Marcin Moczulski, Junhyuk Oh, Neal Wu, Mohammad Norouzi, and Honglak Lee. Contingency-aware exploration in reinforcement learning. arXiv preprint 1 2018.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Thomas L Dean, Robert Givan, and Sonia Leach. Model reduction techniques for computing approximately optimal solutions for markov decision processes. arXiv preprint arXiv: 2013.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint arXiv: 080.000561 2018.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metries for finite markov decision processes. In UAI, volume 4, pp. 162-169, 2004.
Lester R Ford Jr. Network flow theory. Technical report, Rand Corp Santa Monica Ca, 1956.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):163-222 2003.
Xiaoxiao Guo, Satinder Singh, Richard Lewis, and Honglak Lee. Deep learning for reward design to improve monte carlo tree search in atari games. arXiv preprint 1rXvv//604.07095 2016.

---

Under review as a conference paper at ICLR 2021
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Irina Higgins, Arka Pal, Andrei Rusu, Loic Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, and Alexander Lerchner. Darla: Improving zero-shot transfer in reinforcement learning. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1480-1490. JMLR. org, 2017.
Zhiao Huang, Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching. In Advances in Neural Information Processing Systems, pp. 1940-1950, 2019.
Sham Machandranath Kakade et al. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
Khimya Khetarpal and Doina Precup. Attend before you act: Leveraging human visual attention for continual learning. arXiv preprint arXiv: 1rX1v:1807.09664, 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Michael Laskin, Scott Emmons, Ajay Jain, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak.
Sparse graphical memory for robust planning. arXiv preprint arXiv:2003.0644 2020.
Lihong Li, Thomas Walsh, and Michael Littman. Towards a unified theory state abstraction for mdps. In ISAIM, 2006.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529 533, 2015.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3303-3313, 2018.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application reward shaping. ICML, volume 99, pp. 278-287, 1999.
Russel Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2002.
Sieree-vee, Oudeyer and Frederic Kaplan. What is intrinsic motivation? typology of computational approaches. Frontiers in neurorobotics, 1:6, 2009.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 2778-2787, JMLR. org, 2017.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. arXiv preprint 1803:00033303 2018a.
Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Mare Pollefeys, Timothy Lillicrap, and Sylvain Gelly. Episodic curiosity through reachability. ICLR, 2018b.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference on machine learning, pp. 1312-1320, 2015.
Jürgen Schmidhuher. Adaptive confidence and adaptive curiosity. In Institut Informatik, Technische Universitat Munchen, Arcisstr. 21, 800 Munchen 2. Citeseer, 1991.
J Schulman, F Wolski, P Dhariwal, A Radford, and O Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.033777 2017
10

---

Under review as a conference paper at ICLR 2021
Wenling Shang, Kihyuk Sohn, Diogo Almeida, and Honglak Lee. Understanding and improving convolutional neural networks via concatenated rectified linear units. In international conference machine learming. pp. 2217-2225, 2016.
David Silver, Julian Schrittieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354-333 359,, 2017.
Richard S Sutton. Between mdps and semi-mdps: Learning, planning, and representing knowledge at multiple temporal scales. 1998.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. ICLR, 2019.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Voluue 70, pp. 3540-3549. JMLR. org, 2017.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(77822:350-354 2019.
Tom Vodopivec, Spyridon Samothrakis, and Branko Ster. On monte carlo tree search and reinforce-
ment learning. Journal of Artificial Intelligence Research, 60:881-936.1 2017.
Amy Zhang, Adam Lerer, Sainbayar Sukhbaatar, Rob Fergus, and Arthur Szlam. Composable planning with attributes. ICML, 2018.

---

Under review as a conference paper at ICLR 2021
Appendix: Shortest-path reinforcement learning
A
MORE ABLATION STUDY
GoalSmall
ObjectMany
GoalLarge
30
40
return
100
return
return
20
20
K=30
10
0
0
10
2.5
7.5
10
2.5
5
7.5
10
steps (Millions)
steps (Millions)
steps (Millions)
Average episode reward of SPRL with varying & 11 3, 10, 30 as a function of environment steps for DeepMind Lab tasks. Other typer-parameters are kept same the best hyper--prrmma parameter. The best performance is obtained with 10.
Figure 7:
FourRooms-7x7
FourRooms-11x40
KeyDoer-7x7
KeyDoor- 11x01r
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
return
return
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
0.2
0.4
0
0.5 steps (Millions)
4
steps (Millions)
(Millions)
steps (Millions)
Figure 8: Average episode reward of SPRL with varying =3, 5, 7 function of environment steps for MiniGrid tasks. Other hyper-parametens are kept same as the best typer-parameter The best performance is obtained with k = 5.
A.1 EFFECT OF
As proven in Lemma and shown in Section 6.4, the larger kt the k-shortest constraint promises a larger reduction in policy space, which results in a faster learning. However, with our practical implementation of SPRL with a learned (imperfect) reachability network, overly large has drawback. Intuitively speaking, it is harder for policy to satisfy the k-shortest constraint, and the supervision signal given by our cost function becomes sparser (i.e., almost always penalized). Figure 7 and 8 shows the performance of SPRL DeepMind Lab and MiniGrid domains with varying k. In both domains we can see that there exists a "sweet spot" that balances between the reduction in policy space and sparsity of the supervision (e.g., k 10 for DeepMind Lab and l: = 5 for MiniGrid).
GoalSmall
ObjectMany
GoalLarge
30
40
return
100
return
return
4t
20
2t=2
20
50
At=3
At=5
10
0
5 steps (Millions)
10
2.5
7.5
10
2.5
5
7.5
10
steps (Millions)
steps (Millions)
Figure 9: Average episode reward of SPRL with varying At =1, 2, 3, 5 as function of environment steps for DeepMind Lab tasks. Other hyper-parameters kept same the best hyper-parameter. The best performance is obtained with At = 1.
A.2 EFFECT OF TOLERANCE AL
Adding the tolerance At to our k-SP constraint makes it "softer" by allowing At-steps of redundancy in transition (See Eq. (13)). Intuitively, a small tolerance may improve the stability of RNet by incorporating a possible noise in RNet prediction, but too large tolerance will make it less effective on removing sub-optimality in transition. Figure 9 and 10 show the performance of SPRL on DeepMind Lab and MiniGrid domains with varying tolerance At. Similar to k,
that there exists
12

---

Under review as a conference paper at ICLR 2021
FourRooms-7v 7x7
FourRooms: courRooms-11xll 11x11
KeyDoor- 7x7
KnyDoor 1 11x11
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.50
0.50
0.50
A1=10
15=15
0.50
0.25
0.25
0.25
05-25
A1=50
0.25
0.00
0.00
0.00
0.00
0.75
steps (Millions)
sleps (Millions)
steps (Millions)
steps (Millions)
Figure 10: Average episode reward of SPRL with varying At =10, 15, 25, 50 as a function of environment steps for MiniGrid tasks. Other hyper-parameters are kept same the best hyper- parameter. The best performance is obtained with At = 25.
"sweet spot" that balances between the reduction in policy space and stabilization of noisy RNet output (e.g-, Át 25) MiniGrid. Note that the best tolerance values for DeepMind Lab and MiniGrid vastly different. This is mainly because used multiple tolerance sampling (See Appendix D) for DeepMind Lab but not for MiniGrid. Since the multiple tolerance sampling also improves the stability of RNet, larger tolerance has less benefit compared to its disadvantage.
GoalSmall
ObjectMany
GoalLarge
60
150
30
return
return
return
40
100
#stack=0
#stack=1
20
20
#stack=5
#stack=10
10
0
10 steps (Millions)
20
10
15
20
5
10
15
20
steps (Millions)
steps (Millions)
Figure 11: Average episode reward of SPRL with varying observation stacking dimension of 0, 1, 5, 10 as a function of environment steps for DeepMind Lab tasks. Other hyper- parameters are kept same as the best sypee-parameter. The best performance is obtained without stacking (f.e., #stack=0).
hyper-parameters
FourRooms-7xx
7x7
FourRoams-112s
KeyDoor-7x 7x7
KeyDoor-11x11
1.00
1.00
1.00
1.00
#stack=0
retum
0.75
retum
0.75
0.75
0.75
#slack=5
#stack-1
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
0.2
0.4
0
steps (Millions)
steps (Millions]
steps (Millions)
steps (Millians)
Figure 12: Average episode reward of SPRL with varying observation stacking dimension of 1, 5 as function of environment steps for MiniGrid tasks. Other best hyper-parameter The best performance is obtained without stacking (i.e., #stack=0)
are kept same as the
A.3 STACKING OBSERVATION
The CMDP with k-SP constraint becomes the (A: 1)-th order MDP as shown in Eq. (8). Thus, in theory, the policy should take currrent state augmented by stacking the A previous states as input: [st-,, St-k+ stJ,, st], where |:] is a stacks the pixel observation along the channel (i.e.,
color) dimension. However, stacking the observation may not lead the best empirical results in practice. Figure 11 and 12 show the performance of SPRL on DeepMind Lab and MiniGrid domains with varying stacking dimension. For stack=m,
stacked the observation from L. - to [s-m,, 8t St-m+1;-.- St]- We experimented up to m = k: up to m = 10 for DeepMind Lab and m for MiniGrid. The result shows that stacking the observation does not necessarily improves the performance for MDP order greater than 1, which is often observed when the function approximation used (e.g., Savinov et (2018b)). Thus, we did not augment the observation in all the experiments.
13

---

Under review as a conference paper at ICLR 2021
B ANALYSIS ON THE REACHABILITY NETWORK (RNET)
B.I ACCURACY OF THE REACHABILITY NETWORK
We measured the accuracy of reachability network on DeepMind Lab and MiniGrid in Figure 14 and Figure 13. The accuracy
measured on the validation set; sampled 15,000 positive and negative samples respectively from the replay buffer of size 60,000. Specifically, for an anchor 8t, we sample the positive sample sy from E' [++ +1, 1,1t+K At), and the negative sample se from
t" E [ + k + A + A-, + k At 2A_ The RNet reaches the accuracy higher than 80% in
100
FourRooms
100
100
KeyDoor
100
Door 11x11
Accuracy9%)
Accuracy)9g)
Accuracy9%)
Accuracy(%)
80
80
80
80
60
60
60
60
0.4
steps (Millions)
steps (Millions)
steps (Millions)
steps (Millions)
Figure 13: The accuracy of the learned reachability network on (a) FourRooms-7%: (b) FourRooms-
11x11, (c) KeyDoors-7x: and (d) KeyDoors- /x MiniGrid in terms of environment steps.
GoalSmall
ObjectMany
GoalLarge
100
100
100
Accuracy(%)
Accuracy(%)
Accuracy(%)
80
80
80
60
60
60
0
10
15
20
5
10
15
20
5
10
15
20
steps (Millions)
steps (Millions)
steps (Millions)
Figure 14: The accuracy of the learned reachability network on (a) GoalSmall (b) ObjectMany, and (c) GoalLarge in DeepMind Lab in terms of environment steps.
only 0.4M steps in both MiniGrid and DeepMind Lab. We note that this is quite high considering the unavoidable noise in the negative samples: i.e., since the negative samples are sampled based on the temporal distance, not based on the actual reachability, they have non-zero probability of being reachable, which case they are in fact the positive samples.
B.2 ABLATION STUDY: COMPARISON BETWEEN THE LEARNED RNET AND THE GT-RNET
In this section, study the effect of RNet's accuracy the SPRL's performance. To this end, we implement and compare the ground-truth reachability network by computing the ground-truth distance between a pair of states in MiniGrid.
Ground-truth reachability network was implemented by computing the distance between the two state inputs, and comparing with k. For the state inputs and s', roll out all possible k-step trajectories starting from the state s using the ground-truth single-step forward model. If s' is ever visited during the roll-out, the output of k-reachability network and otherwise, the output is 0.
FaurRooms- 7x7
FaurRooms 11x11
KeyDoar 7x7
KeyDoar-114 11x11
1.00
1.00
1.00
1.00
Retum
0.75
Return
0.75
Return
0.75
Retum
0.75
0.50
0.50
0.50
0.50
GT-SPRL
0.00
0.4
0.00
0.00
0.5 steps (Millions)
0.00
steps (Millions)
steps (Millions)
steps (Millions)
Figure 15: The accuracy of the learned reachability network on (a) FourRooms-7x (b) FourRooms-
11x11, (c) KeyDoors-7x7 and (d) KeyDoors- 11 1 in MiniGrid in terms of environment steps.
Result. We compared the performance of our SPRL with the learned RNet and the ground -truth RNet (GT-SPRI)) in Figure 15 with the best hyperparameters. Overall, the performance of SPRL
14

---

Under review as a conference paper at ICLR 2021
and GT-SPRL are similar. This is partly because the learned RNet achieves quite high accuracy in early stage of learning (see Figure 13). Interestingly, we can observe that our SPRL with learned RNet performs better than SPRL with GT-RNet on FourRooms-7x and KeyDoors-7x7. This is possible since a small noise RNet output can have a similar effect to the increased tolerance At on RNet, which makes the resulting cost more dense, which may be helpful depending the tasks and hyperparameters.
B.3 ABLATION STUDY: CURRICULUM LEARNING OF RNET
We applied the linear scheduling of see curriculum learning can improve the RNet training, and eventually improve our SPRL performance. For example, in case of FourRooms-7x 7, we used until O.IM steps, and 0.5M steps. Figure 16 and Figure 17 compares the performance of SPRL four MiniGrid tasks and three DeepMind Lab tasks with and without curriculum learning applied respectively. The result shows that, however, the curriculum learning is not helpful for RNet training. We conjecture that changing & during training RNet makes the learning unstable since changing i completely flips the learning target for some inputs; e.g, the
until 0.2M steps, and so on, and finally
from 0.4M steps to
states that 2 steps away are unreachable for k but reachable for k = 2. In Figure 18, we compared the RNet accuracy when RNet was trained with and without curriculum learning. We can observe that curriculum learning achieves similar or lower RNet accuracy with higher standard error, which indicates that the curriculum learning makes RNet training unstable.
FourRooms-7x7
FourRooms-7x7
KeyDoor-7x7
KeyDoor-11xd
1.00
1.00
1.00
Retur
0.75
Retum
0.75
0.75
Reburm
1.0
SPRL Curriculum
SPRL
0.50
0.50
0.5
0.25
0.00
0.00
0.00
0.2
0.5 steps (Millions)
steps (Millions)
steps (Millions)
steps (Millions)
The performance of SPRL with and without curriculum learning of RNet on (a) FourRooms-7x7 (b) FourRooms-lIxll (c) KeyDoors-7x7 and (d) KeyDoors-11 x111 in MiniGrid.
Figure 16:
GoalSmall
ObjectMany
GoalLarge
150
60
30
Return
100
Return
Return
40
20
SPRL SPRL-Curriculum
20
10
0
2.5
7.5
0
2.5
7.5
10
2.5
5
7.5
10
steps (Millions)
steps (Millions)
steps (Millions)
Figure 17: The performance of SPRL with and without curriculum learning of RNet on (a) GoalSmall (b) ObjectMany, and (c) GoalLarge in DeepMind Lab in terms of environment steps.
GoalSmall
ObjectMany
GoalLarge
100
100
100
Accuracy(%)
Accuracy(P))
Accuracy(96
80
80
SPRL
60
60
Curriccuiuulmm
60
2.5
5
7.5
10
2.5
5
7.5
2.5
5
7.5
10
steps (Millions)
steps (Millions)
steps (Millions)
Figure 18: The accuracy the learned reachability network with and without curriculum learning of RNet (a) GoalSmall (b) ObjectMany, and (c) GoalLarge in DeepMind Lab in terms of environment steps.
15

---

Under review as a conference paper at ICLR 2021
C EXPERIMENT DETAILS OF MiniGrid DOMAIN
C.I ENVIRONMENT
MiniGrid is 2D grid-world environment with diverse predefined tasks (Chevalier-Boiss et al., 2018). It has several challenging features such as pictorial observation, random initialization of the agent and the goal, complex action space and transition dynamics involving agent's 's orientation of movement and changing object status via interaction (e.g., key-door).
State Space. An observation is represented as H W C tensor, where H and W are the height and width of map respectively, and C is features of the objects in the grid. The (h, wi-th element of observation tensor (lype, color, status) of the object and for the coordinate of agent, the (h, w)-th element is (type, 0, direction). The map size (i.e., H X W) varies depending on the task; e.g., for FourRooms-7xx 7 task, the map size 7 x
Action Space and transition dynamics The episode terminates in 100 steps, and the episode may terminate earlier if the agent reaches the goal before 100 steps. The action space consists of seven discrete actions with the following transitions.
change the direction counter-clokkwise by 90 degree. Turn-Clockwise: change the direction clockwise by 90 degree.
Turn-Counter-Clockkk
Move-Forward: move toward direction by step unless blocked by other objects.
Pick-up-key: pickup the key if the key is in front of the agent.
Drop-the-key: drop the key in front of the agent.
Open/Close-doorzz open/close the door if the door is in front of the agent.
Optional-action not used
Reward function. The reward is given only if the agent reaches the goal location, and the reward magnitude is (Ienthh of episode /maximum step for episode). Thus, the agent can maximize the reward by reaching to the goal location shortest time.
C.2 TASKS
In FourRooms-7x 7 and FourRooms- I 11, the map structure has four large rooms, and the agent needs to reach to the goal. In KeyDoors-7x7 and KeyDoors-I / 11 the agent needs to pick up the key, go to the door, and open the door before reaching to the goal location.
C.3 ARCHITECTURE AND HYPER-PARAMETER
We used a simple CNN architecture similar to (Mnih et al., 2015) for policy network. The network consists of Convl 116xx2211///s SAME) -CReLJJConv2 (8x2x2-1/SAMXE SAMM)))--LML. -CReLU- Conv3 (8x2x2-1/ SAME)) -CRELU-FC ( (512) -FC (actionndimensioo padding ensures the input and output have the same size (i.e., width and height) and CReLU (Shang et al., 2016) is non-linear activation function applied after each layer. We used Adam (Kingma & Ba, 2014) optimizer optimize the policy network.
where SAME
search, we swept over a set of hyper-parameten specified in Table 1, and chose the best one in terms of the mean AUC over all the tasks, which is also summarized in Table 1.
For
D EXPERIMENT DETAILS OF DeepMind Lab DOMAIN
D.1 ENVIRONMENT
DeepMind Lab is 3D-game environment with first-person view. Along with random initialization of the agent and the goal, complex action space including directional change, random change of texture, color and maze structure are features that make tasks in DeepMind Lab hard to be learned.
State Space. An observation s; has the dimension of 120 160 3 tensor. Observation is given as first-person view of the map structure.
Action Space and transition dynamics The episode terminates after the fixed number steps regardless of goal being achieved. The original action space consists of seven discrete actions: Move-Forward, Nove-Backward, Strafe Left, Strafe Right, Look Left, Look Right, Look Left and Move-Porward, Look Right and Move-Forward. In our experiment, we used eight discrete actions with the additional action Fire as in (Higgins et al., 2017; Vezhnevets et al., 2017; Savinov et al., 2018b; Espeholt et al., 2018; Khetarpal & Precup, 2018).
16

---

Under review as a conference paper at ICLR 2021
PPO
Hyperparameters
Sweep range
Final value
Learning rate
0.001, 0.002, 0.003 0.003, 0.005, 0.01, 0.02, 0.05
0.003
Entropy
0.01
ICM
Hyperparameters
Sweep range
Final value
Learning rate
0.001, 0.002, 0.003
0.003
Entropy Forward/Invesse model loss weight ratio
0.01
0.2, 0.5, 0.8, 1.0 0.03, 0.1, 0.3, 1.0
0.8
Curiosity module loss weight
0.3
ICM bonus weight
0.1, 0.3, 1.0, 3.0
0.1
GT-Grid
Hyperparameters
Sweep range
Final value
Learning rate
0.001, 0.002, 0.003
0.003
Entropy GT-Grid bonus weight
0.01
0.003, 0.01, 0.03, 0.1, 0.3
0.01
ECO
Hyperparameters
Sweep range
Final value
Learning rate
0.003
Entropy
0.01
3,5, 0.001, 0.002, 0.005, 0.01
3
ECO bonus weight
0.001
SPRL
Hyperparameters
Sweep range
Final value
Learning rate
0.003, 0.01
0.01
Entropy
0.01
k
2,
2
Tolerance (A))
Negative bias (A )
10,
20
Positive bias (A+)
5
Cost scale (A)
0.001, 0.002. 0.005
0,002
Na
30, 60
60
Table The range hyperparameters sweeped over and the final hyperparameters used in MiniGrid domain.
D.2 TASKS
We tested our agent and compared methods three standard tasks in DeepMind Lab: GoalS- mall, GoalLarge, and ObjectMany which correspond to wtw.eeegpllllooatiooooooooo.o poplooreegpll.ocationo
and explore_ob wtw.oorreooeettreewaaddeeo.ee _many, respectively. GoalSmall and GoalLarge has single goal in the maze, but the size of the maze is larger in GoalLarge than GoalSmall. The agent and goal locations are randomly set in the beginning of the episode and the episode length is fixed to 1,350 steps for GoalSmall and 1,800 steps for GoalLarge. When the agent reaches the goal, it positively rewards the agent and the agent re-spawned in random location without terminating the episode, such that the agent can reach to the goal multiple times within a single episode. Thus, the agent's 's goal is to reach to the goal location as many times as possible within the episode length. ObjectMany has multiple objects in the maze, where reaching to the object positively rewards the agent and the object disappears. The episode length is fixed to 1,800 steps. The agent's 's goal is to gather many object possible within the episode length.
17

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Sampling the triplet data from an episode for RNet training
Require: Hyperparameters: k E N, Positive bias A+ E N, Negative bias A E EN
I: Initialize Lnnc -- 0.
2: Initialize Sanc = 0, S+ = 0, S_ = D.
3: while lane T do
4: Sanc = anc U { /.
5: 4 Uniform| Lanc + 1, fanc k).
6:
f- = Uniform Fane + k: + A TT).
7:
S+ St (
(8t+1
8:
S_ = S_ U (
9: tane Uniform (t+ + 1,t_ + +
refurn Sanc, S+, S
D.3 REACIABILITY NETWORK TRAINING
Similar to Savinov et al. (2018b), we used the following contrastive loss for training the reachability network:
Rnet = log (Rnetz-1(sane )) - log (1 Rnnet=-($annee $ $_)),
(15)
where Sanc, 8_ are the anchor, positive, and negative samples, respectively. The anchor, positive and negative samples are sampled from the same episode, and their time steps are sampled according to Algorithm 2. The RNet is trained in an off- off-policy manner from the replay buffer with the size of 60K environment steps collecting agent's online experience. We found that adaptive scheduling of RNet is helpful for faster convergence of RNet. Out of 20M total environment steps, for the first 1M, 1M, and 1 18M environment steps, we updated RNet every 6K, 12K, and 36K environment steps, respectively. For all three environments of DeepMind Lab, RNet accuracy was ~ 0.9 after IM steps.
Multiple tolerance. order to improve the stability of Reachability prediction, we used the statistics over multiple samples rather than using single-sample estimate suggested in Eq. (13). As a choice of sampling method, we simply used multiples of tolerance. In other words, given ((+(+AA)) and 8 as inputs for reachability network, we instead used (t-(k+aAr) and 8t where 1 1 n S NA n E N and NA is the number of tolerance samples. We used 90- 90-percentile of NA outputs of reachability network, Rnet, (8)-()+n2()) 8t), as in (Savinov et al., 2018b) to get the representative of the samples.
D.4 ARCHITECTURE AND
Following (Savinov et al., 2018b), we used the same CNN architecture used in (Mnih al., 2015). To fit the architecture, we resized the input observation image into 84 84 x 3 image, and normalized by dividing the pixel value by 255.
For SPRL, we used smaller reachability network (RNet) architecture compared to ECO to reduce the training time. The RNet is based on siamese architecture with two branches. Following (Savinov et al., 201 8b), ECO used Resnet-18 (He et al., 2016) architecture with 2-2-2-2 residual blocks and 112-dimensional output fully conne-co layer to implement each branch. For SPRL, we used Resnet- 12 with 2-2-1 residual blocks and 51 12-dimensional output folnecco layer to implement each branch. The RNet takes two states as inputs, and each state is fed into each branch. The outputs of the two branches concatenated and forwarded to three* 51 512-dimensional fully-connected layers to produce one-dimensional sigmoid output, which predicts the reachability between two state inputs. We also resized the observation to the same dimension as policy (i.e., 84 x 84 which is smaller than the original 120 x 160 x 3 used in (Savinov et al., 2018b)).
For all the baselines (i.e., PPO. ECO, ICM, and GT-Grid), we used the best hyperparameter used in (Savinov et al., 2018b). For SPRL, we searched over set of hyperparameters specified in Table 2, and chose the best one in terms of the mean AUC over all the tasks, which is also summarized in Table 2.
Savinov et al. (2018b) used four 512-dimensional fully-connected layers.
18

---

Under review as a conference paper at ICLR 2021
Hyperparameters for SPRL
Sweep range
Final value
Learning rate
0.0003
Entropy k
0.004
3, 10,30
10
Tolerance (At)
1,
Negative bias (A-)
5, 10,
20
Positive bias (A )
5
Cost scale (A)
0.02, 0.06, 0.2
0.06
Optimizer
Adam
NA
200
Table 2: The range of hyperparameters sweeped over and the final hyperparameters used for SPRL method in DeepMind Lab domain.
19

---

Under review as a conference paper at ICLR 2021
E OPTION FRAMEWORK WOR-RRKKK---DDDDDD BASED FORMULATION
E.1 PRELIMINARY: OPTION FRAMEWORK
Options framework (Sutton, 1998) defines options as generalization of actions to include temporally extended series of action. Formally, options consist of three components: policy S x A - (0, 1], a termination condition 3 : S + [0, IJ, and an initiation set I C S. An option (Z, ग., 3) is available in state if and only if Z. If the option is taken, then actions are selected according the option terminates stochastically according to B. Then, the option-reward and option-transition models are defined as
until
r E (ri-1 + 72442 + + reth E(o,
(16)
P Σ p (s',k))
(17)
k=1
where t + k is the random time at which option terminates, E(o, t) is the event that option is initiated in state 8 at time i, and p(s', k) is the probability that the option terminates in s' after k steps. re-write Bellman equation follows:
Using the option models,
V (s) = E [re41 +
retk + 1 ~V (8L-
(18)
= Σ Pr(F(o,
r EP.
(19)
oEO
where + k is the random time at which option terminates and Elo, s) is the event that option o is initiated in state s.
E.2 OPTION-BASED VIEW-POINT OF SHORTEST-PATE CONSTRAINT
In this section, present option framework- based viewpoint of our shortest-path (SP) constraint. We will first show that (sparse-reward) MDP can be represented as weighted directed graph where nodes rewarding states, and edges options. Then, show that policy satisfying SP constraint also maximizes the option-transition transition probability P
For given MDP M RS P. S), let S {s|R(s) o 0) C be the set of all rewarding states, where R(s) is the reward function upon arrival to state In sparse-reward tasks, it is assumed that [ << |S]. Then, we can form a weighted directed graph G = (V, E) of policy т and given is defined as V S U pa U where S is rewarding states, Po is the initial
MDP. The vertex states, and S is the terminal states. Similar to the path set in Definition 2, let Ta denotes a set of paths transitioning from vertex E V to another vertex s' V:
To
{r|30 8, Sc(F) = s', {stJucC<((()) nv -V=0) 0}.
(20)
Then, the edge from vertex V to another vertex s' V is defined by (implicit) option tuple o(s, s') = (I, n, () where I = ((s) = I(s = s'), and
t (s. (7) = { 1z (T) for Tx
(21)
0 otherwise
where Z is the partition function to ensure f ā (= (T) Following Eq. (16), the option-reward given
B 8,8'
ret1 + yr4t2 +
x reth E(o(m.)) ,,,)) s,t)
(22)
y 2 Teth E(o(+.') s, s.
(23)
where 1. + la is the random time at which option o(s, 8') terminates, and E(o, 8, () is the event that option o(s, s') is initiated in state time f. Note that in the last equality, r++1 T
holds since Sttkka O V 9 from the definition of option policy ((5,8") Following
1
20

---

Under review as a conference paper at ICLR 2021
Eq. (17), the option transition is given
P 0,0'
=
Σ pls k)
(24)
1=
= E |s0 3, = s', sretrec
(25)
= - (o,o'))
(26)
where p(s', k) is the probability that the option terminates s' after & steps, and D (s, 8') is the r-distance in Definition 3. Then, we can re-write the shortest-path constraint in terms of P as follows:
1I = { s' E T s.t. (8,8) E 4"), ( min D (s,s'))
(27)
= [ E T. s.t. (8, E 2"), P. = max P.,
(28)
Thus, we can see that the policy satisfying SP constraint also maximizes the option transittnnniiion probability. We will use this result in Appendix F.
F SHORTEST-PATH CONSTRAINT: SINGLE-GOAL CASE
In this section, we provide more discussion on special case of the shortest-path constraint (Sec- tion 3.1), when the (stochastic) MDP defines a single-goal task: Le., there exists unique initial state Sint E S and unique goal state 8g S such that sg terminal state, and R(s) > 0 if and only if s = 5g.
We first note that the non-rewarding path set is identical to the path set in such setting, because the condition T2 = 0( < {(T)) from Definition 2 is always satisfied as R(s) > O + s $g and
8((r)) 8g-
Te. T {T 80 = 8, 86()) p=(T) > 0, (8thece))) # 8'}
(29)
Again, Th. is a set of all path starting from 8 (i.e., and ending at s' (i.e., 8t(r) = s') where the agent visits s' only at the end (i.e., (81)4<07)) # s'), that can be rolled out by policy with non-zero probability (i.e., Pa (T) > 0).
We now claim that an optimal policy satisfies the shortest-path constraint. The idea is that, since sy is the only rewarding and terminal state, maximizing R(T) = -- R(ss)) where sT 8g corresponds to minimizing the number of time steps to reach 8g. In this setting, shortest-path policy is indeed optimal.
Lemma 4. For single-gon goolle-gaalaan MDP, any optimal policy satisfies the shortest-path constraint.
Proof. Let Simi be the initial state and 8g be the goal state. We will prove that any optimal policy shortest-path path policy from the initial state to the goal state. We use the fact that 8g is the only rewarding state, i.e., R(s) > 0 entails
3g.
n² arg max ET
grup
Σ rrr
80
(30)
arg max R
Σe r'r:
80 Sinit
(31)
arg max B
[> R(sg)
|80 Smnt St(r) = sqg]
(32)
= arg max 1 [ 880 = Binit: Be(T) = 88]
(33)
= arg min log, ( TB [ 80 = Sinit; 86(7) (8g)
(34)
arg min D Sinits (Sinits $z).
(35)
where Eq. (33) holds since R(s,) 0 from assumption that R(s) + (s) 0.
21

---

Under review as a conference paper at ICLR 2021
G PROOF OF THEOREM
We make the following assumptions on the Markov Decision Process (MDP) M: namely mild stochasticity (Definitions and 9).
Definition 8 (Mild stochasticity (1)). In MDP M, there exists an optimal policy x² and the corre- sponding shortest-path policy TP 11st such that for all s,s' E o², holds px- (5 =s'(s0 5)
Pxep (3 = s0|s0 = 8).
Definition 9 (Mild stochasticity (2)). In MDP M. the optimal policy x² does not visit the same
state more than once: For all E S such that (s) > 0, it holds (x)(s) = 1, where Pa (s) -
E 1 (s; = s) is the state-visitation count.
In other words, we assume that the optimal policy does not have a cycle. One common property of MDP that meets this condition is that the reward disappearing after being acquired by the agent. We note that this assumption holds for many practical environments. In fact, in many cases as well as Atari, DeepMind Lab, etc.
Theorem 1. For any MDP with the mild stochasticity condition, an optimal policy satisfies the shortest-path constraint: x² E 11
Proof. For simplicity, we prove this based on the option-based view point (see Appendix E). By plugging Eq. (23) and Eq. (25) into Eq. (19), we can re-write the Bellman equation of the value function (=)s as follows:
(s) = Σ Pr(E(o, 8)]
r + EeO
po (s')
(36)
aEO
Σ (3 = s'|s0 s)
= 8,8 s0) P..
(37)
s'ESIR
Σ (3 = 8'130 s) [R(s') ( + + (=)))
(38)
S'ERIR
Σ (= s s0 PT. R(S') + +5)(
(39)
S'RIRR
where & is the first rewarding state that agent encounters. Intuitively, (= s'|so s) means the probability that the s' is the first rewarding state that policy æ encounters when it starts from 8. From Eq. (28), our goal is to show:
x' STSP { V(s 8') E To PT
P ::
(40)
where p S,8' max, pa S,5'
We will prove Eq. (40) by contradiction. Suppose 7t is an optimal policy such that n" g ITSP. Then,
3(8, E To,n)) s.t. P + P Recall the definition: P = max, P Then, for any n, the following statement true.
(41)
ps #
P s, + p < P
(42)
Thus, we have
p 5,3'
P
(43)
Let Tap E LISP be shortest path policy that preserves stochastic dynamics from Definition 8. Then, we have
P.. Pj = =p700 TTop
(44)
Then, let's compose a new policy #:
*(als) = F. (als) n"' (als) otherwise
3r E T. s.t. 8 ET
(45)
Now consider a path Ta- that agent visits $ at time = i and transitions to s' at time t = j > i while not visiting any rewarding state from i to j with non-zero probability (i.e., Pr. (7) > 0).
22

---

Under review as a conference paper at ICLR 2021
We define set of such paths as follows:
T=-3' = {r 3 < j), 8; = 8, 8, = 8', (ottecte n =0, (T) (T)> 0}.
(46)
To reiterate the definitions from Definition 6: S = {s R(s)) ) > or p(rp(s) > 00 is the union of all initial and rewarding states, and o ((s,s') 8, E SRR p(s) > 0, T ,r F (i) is the subset of SRR such that agent may roll out.
From Definition 9 and Eq. (45), the likelihood of path under policy क is given as follows:
P+ (T) = Pr (T T8 Pr,, (T/T E Tamar) for Ta-28 Px (T)
(47)
otherwise
where Pa (T) is the likelihood of trajectory T under policy 4, Pa(r E T = Seet Pa (T)
ensures the likelihood (T)) to be valid probability density function (i.e., J ps pT(TT)TT 1). From the path T3-33' and é.j, we will choose two states Siz, Sir Ta-+8', where
Sir max( s i), b min(se]ss S j S l).
(48)
Note that such 8ir and s/g always exist in T since the initial state and the terminal state satisfy condition to be 8ir and b/2-
Then, we can show that the path between fir and sy is not shortest-path, Recall the definition of D ss) (Definition 3):
D (Sies 5/r) log,
E B TET
(49)
rET
= -oogy
Ryywa
(ge(T) T E T
(50)
where we will use & 7((rr T E Meis/,ur for a shorthand notation. Then, we have
p (Baish)) = Buy (8)
(51)
P (T E Ts-s' ) B
T E T8-a8
+ P (T & Ts E
T of T T--08
(52)
(From Definition 5) < (T- E Ts-18 )
T E Ts-188
+ Pa. (T $ Tamsi Brrn
T $ T T8
(53)
(From Eq. (47)) = -Pa(T (T E 8 Ern
E To-s8
+ pT(T (T & To-s8r )
2
(54)
Eywa ($)
7 D (8ar(tt)
(55)
D (Siry x/r)) (Sirs (/1))
(Sirs
(56)
where Ineq. (56) is given by the fact that 7 < 1. Then, p= S < pa
23

---

Under review as a conference paper at ICLR 2021
From Eq. (39), we have
v (sir) = Σ
(* = 8 800 = (ir) sinal [R('')
+ +>]*
(57)
s'ESin
= PA (8 1/1 80 81g) 8ir) str.f/ [R($()) +>V*(s()))
+ Σ
pa (8 = 800 = 81x) P [R(s') + +v
(58)
s'ESIN
= Pz (3 = S/r
30
Sm
p
R((1 + + (s/+)
Σ
Pr- (3 = 8' 80 = Pr se.
R((s)) +yV= (8))
(59)
s'EStn
> ps (3 = 5/r
30
Sir)
[R($(v) + ~ (s/rr)
Σ
Pr- (3 ss
Su
Siz p 8y.5
[((*)+
+ +zV=
(60)
Σ
Pa. 5 80 Sir) p
[R(s')+ ((('')+>V='0 (6))
(61)
S'ESIR
= =V'(su),
(62)
where Eq. (59) holds from the mild-stochasticity (1) and hhlddstochhsttictty (2) assumption, and Ineq. (60) holds because p P P and R(s') + /V= (s') from the non-negative optimal value assumption (See Section 2). Finally, this is contradiction since the optimal value function V*()) should be the maximum.
24

---

Under review as a conference paper at ICLR 2021
H EXTENDED RELATED WORKS
Approximate state abstraction. The approximate state abstraction approaches investigate parti- tioning MDP's state space into clusters of similar states while preserving the optimal solution. Researchers have proposed several state similarity metrics for MDPs. Dean et al. (2013) proposed to the bisimulation metrics (Givan et al., 2003; Ferns et al., 2004), which measures the difference in transition and reward function. Bertsekas et al. (1988) used the magnitude of Bellman residual metric. Abel al. (2016; 2018); Li et al. (2006) used the different types of distance in optimal Q-value to measure the similarity between states to bound the sub-op uub-optimality in optimal value after the abstraction. Recently, Castro (2019) extended the bisimulation metrics to the approximate version for deep-RL setting where tabular representation of state is not available.
Our shortest-pale constraint can be seen as form of state abstraction, in that ours also aim to reduce the size of MDP (i.e., state and action space) while preserving the "solution quality". However, our method does so by removing sub-optimal policies, not by aggregating similar states (or policies).
Connection to Option framework Our shortest-path constraint constrains the policy space to set of shottest-path policies (See Definition 5 for definition) between initial and rewarding states. It can be seen as set of options (Sutton, 1998) transitioning between initial and rewarding states. We refer the readers to Appendix E for the detailed description about option framework based formulation of our framework.
25


Reviews:
[{"review_id": "gnMTIIHcnV", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThis paper proposes a new constraint for constrained MDP, based on k-shortest path, which helps improve sample efficiency for (model-free) RL algorithms in sparse-reward MDP, while theoretically proving that the constraint retains the same optimal policy in the original MDP. Intuitively, for sparse (positive) reward setting, the optimal policy should reach the positive reward states with the shortest path (as it has the lowest discounting). The relaxed form of the constraint considers the that the distance between two states is less than $k$, rather than being optimal length (which the optimal policy still also satisfies). The constraint is then converted into its Lagrangian form as a cost term to the reward (i.e. a type of reward shaping). Practically, this requires a k-reachability network (RNet), which is a binary distance discriminator judging whether the distance between two states are reachable within $k$ steps. This network is trained with contrastive loss, similar to prior work SPTM by Savinov et al., 2018. However, SPTM uses RNet for graph-based planning (i.e. the local distance between states), while this paper uses RNet as the cost/constraint on the policy objective function. Experiments were conducted in several maze navigation environments (2D grid world MiniGrid, to first person 3D maze environments in DeepMind Lab), showing promising results compared to several baselines which use intrinsic curiosity. Several ablations were performed on the hyperparameters ($k$, and tolerance $\\delta t$ on the constraint), as well as some qualitative examples of the policies learned compared to novelty reward shaping.\n\n\n**Strengths**:\n- There has been a lot of work with goal-conditioned RL with sparse reward. The advantage of this paper is that this approach converts the notion of reaching goals into a constraint that is applicable to general MDPs. \n- The theoretical results (under some mild assumptions such as positive cumulative reward, mild stochasticity) appear to be correct, although I am not absolutely certain. \n- Empirically the experiments were designed well to study the effects of its hyperparameters ($k$, and tolerance $\\delta t$ on the constraint), and performs strongly as the task is harder (sparser reward / long trajectories) compared to its baselines\n\n**Weaknesses**:\n- It is still unclear to me about the potential performance gap between using an imperfect RNet versus an oracle ground truth distance discriminator. See my question below for some more detail\n- In the experimental sections, some sections are unclear about whether the RNet is used or not. For example, RNet is not used in 6.2 (MiniGrid), while is used in 6.3 (DeepMindLab) but required reading appendix to confirm. I am not sure for 6.4 and 6.5 whether RNet is used at all (I think it is not). Please clarify for me and in the paper. \n\n**Recommendation**:\n I recommend this paper a marginally above acceptance threshold. Overall I think that it is a well-written paper with thorough theoretical and empirical results. There are some clarification parts that can improve the paper even further.\n\n**Questions**:\n1. My main question is what is the performance difference between having the ground truth distance versus using the RNet? For example, can you compare the performance of 6.2 if RNet was used here? I understand RNet is not used in 6.2 for the purpose of understanding the objective. I would the oracle RNet would give the upper bound on the performance on SPRL, but how much worse is using RNet in those environments?\n2. Perhaps outside of the scope of this paper, but I am curious about how SPRL would perform if there was a curriculum on the $k$ and $\\delta t$ value, rather than a fixed value that is treated as a hyper parameter. Perhaps the authors have some intuition or have actually tried this as well. \n3. Please clarify about the use of RNet vs. Ground truth distance in the section 6.4/6.5. \n\n**After rebuttal responses**:\n\nI have read the authors’ response to my concerns, as well as the other reviews. I maintain my current evaluation with a weak acceptance of the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ha8YhYCWjb", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a novel k-shortest-path constraint that prevents over-exploration by exploit the combinatorial structure (i.e. shortest path) of sparse reward tasks. It is proved theoretically that the k-shortest-path constraint maintains the optimal policy. Empirical evidence shows that the k-SP constraint indeed significantly improves the sample complexity over baseline algorithms in benchmarking environments. \n\nWhile I certainly agree that sparse reward tasks is important, one of the biggest challenges in sparse reward tasks is when the environment has a large state space. When the state space is finite and small, there is no doubt that many algorithms (even  algorithms with no deep learning method) can solve the task. However, for a large state space and sparse reward task (such as the robotics tasks in Mujoco environments[1], Montezuma's Revenge in Atari environments), I'm not sure whether the k-SP constraint is enough for efficiently solve the task. The k-SP constraint essentially tells the agent to avoid going to duplicated states. Even so, due to large state space, it is unlikely that the agent can observe non-zero reward without extra guidance. To be more specific, could the author(s) provide more discussion compared to HER (Hindsight Experience Replay) and hierarchical reinforcement learning?\n\nOverall, the paper is well-written, and the empirical results are clear. Therefore, I would recommend a weak acceptance.\n\n[1] http://gym.openai.com/envs/#robotics", "extra_scores": {}, "extra_text": {}}, {"review_id": "CJ2mOpPT6iv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a k-shortest-path constrained reinforcement learning method for solving sparse reward MDPs. Under the assumption that the MDP is a single-goal task and by utilizing a novel cost function, the proposed method is demonstrated to outperform a few baselines in terms of sample efficiency.\n\nPro:\nThe technique along with its theoretical property are well developed.\n\nCareful numerical studies are provided to evaluate the effect of the k-shortest constraint in a tabular-RL settings  \n\nCons:\nIt is unclear how this method and its theoretical results can be generalized to other settings where the rewards are less sparse than single-goal MDP settings, but still very sparse.\n\nThe experiments for testing the proposed method are all based on navigation tasks, which give us an impression that the proposed method is only applicable to a specific problem. It might be better to consider a different type of domains.\n\nThe compared baseline methods are very limited and not necessarily ideal candidates for solving sparse reward problems. There are other approaches, such as hierarchical reinforcement learning which can also solve sparse reward problems , e.g., eigen-options [1] might also worth to compare. \n[1] Machado et al. A Laplacian Framework for Option Discovery in Reinforcement Learning, imcl2017.\n\nOther questions:\nIs there a convergence guarantee for algorithm 1? \n\nIt might be better to provide some computational complexity analysis of algorithm 1.\n\nWhat is the motivation of using k-reachability network to implement the binary distance discriminator?\n\n--------------after the rebuttal---------------\nI appreciated the authors' effort in addressing my comments and questions. I maintain my score of weak acceptance for this paper. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AHtUA8ck3oL", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes the k-Shortest-Path (k-SP) constraint to restrict the agent’s trajectory to avoid redundant exploration and thus improves sample efficiency in sparse-reward MDPs. Specifically, k-SP constraint is applied to a trajectory rolled out by a policy where all of its sub-path of length k is required to be a shortest-path under the π-distance metric. Instead of a hard constraint, a cost function-based formulation is proposed to implement the constraint. The method can improve the sample efficiency in sparse reward tasks and also preserve the optimality of given MDP. Numerical results in the paper also demonstrate the effectiveness of k-SP compared with existing methods on two domains (1) Mini-Grid and (2) DeepMind Lab in sparse reward settings.\n\nOverall, the paper is well written and clearly conveys the main idea and the main results of the work. The idea and motivation of the paper are very intuitive and very reasonable. The theoretical results are immediately following the ideas. The algorithm proposed has a clear structure and is easy to understand and implement. For experiments, the new algorithm consistently outperforms existing studies on a set of MDPs where there exists a goal state (as both the unique reward state and the terminal state). Some important discussions are highlighted to introduce the algorithm,. Moreover, the proposed mechanism seems to be an inspiration for future work considering the state space exploration related to sample efficiency.\n\nHowever, I wasn't fully convinced by the paper about relevance. Reinforcement learning aims to learn in an environment by trial and error without prior knowledge about the environment. As the problems considered by the paper are with episodic rewards (in both theory and experiments), *the problem themselves are shortest path problems*. Using the shortest path constraint to solve shortest path problems seems not fair to be placed among a set of learning algorithms. Armed with this prior knowledge, the algorithm outperforms marginally (though consistently) compared with pure learning-based algorithms, only with its best choice of k. I believe it would fall short if placed among search algorithms. Some strong justifications are needed for the work to be relevant.\n\nPros: \n1.\tThe paper considers a practical problem in reinforcement learning: sample efficiency in sparse reward tasks. The RL algorithm tends to fail if the collected trajectory does not contain enough evaluative feedback. The idea of using a constrained-RL framework and cost function to tackle the problem is natural and has been well motivated given some drawbacks in existing work mentioned in section 5.\n2.\tThe relaxation from the shortest path to k-SP is well explained. The novel cost function introduced to penalizes the policy-violating SP constraint can tackle some limitations of existing methods. For example, it can preserve the convergence and optimality of the policy. \n3.  This paper provides convincing numerical experiments to show the effectiveness of the proposed framework. The ablation studies are also helpful to show the effects of hyperparameters. \n  \nCons: \n1. The choice of k is not clear.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a shortest path constraint for the reinforcement learning algorithm to improve efficiency in sparse-reward scenarios. The experiments are shown in navigation tasks in first-person maze and grid world. Reviewers found the idea interesting and the paper well-written but none of them championed the paper for clear acceptance. The authors provided a detailed thoughtful rebuttal. All the reviewers acknowledged the rebuttal followed by discussion. After considering rebuttal, review, and discussion, both AC and reviewers feel that experiments don't fully support and justify the algorithm. The main issue is that the results are shown only for the shortest pathfinding problems where the shortest path constraint is shown to be helpful. Hence, it is recommended to run it on diverse scenarios and standard benchmarks like the Atari games suite. Please refer to the reviews for final feedback and suggestions to strengthen the future submission.
Decision: Reject