Year: 2020

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 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.

heading: 1 INTRODUCTION
text: Recently, deep reinforcement learning (RL) has achieved a large number of breakthroughs in many domains including video games (Mnih et al., 2015; Vinyals et al., 2019), and board games (Silver et al., 2017). Nonetheless, a central challenge in reinforcement learning (RL) is the sample efficiency (Kakade et al., 2003); it has been shown that the RL algorithm requires a 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 circumvent this challenge, planning-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 planning may grow intractably large for complex domain. Model-based RL methods attempt to learn a model instead of assuming that model is given, but learning an accurate model also requires a large number of samples, which is often even harder to achieve than solving the given task. Model-free RL methods can be learned solely from the environment reward, without the need of a (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 to 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 et al., 2018; Burda et al., 2018). However, when such intrinsic bonus is added to the reward, it often requires a 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 a 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 policy-based and value-based methods. We propose a 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 to a trajectory rolled out by a policy; all of its sub-path
of length k is required to be a shortest-path under the π-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-goal 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., 2018b) (RNet) to efficiently learn the cost function in an 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 a 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 on 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.

heading: 2 PRELIMINARIES
text: Markov Decision Process (MDP). We model a task as an MDP tuple M = (S,A,P,R, ρ, γ), where S is a state set, A is an action set, P is a transition probability, R is a reward function, ρ is an initial state distribution, and γ ∈ [0, 1) is a discount factor. For each state s, the value of a policy π is denoted by V π(s) = Eπ[ ∑ t γ
trt | s0 = s]. Then, the goal is to find the optimal policy π∗ that maximizes the expected return:
π∗ = arg max π
Eπs∼ρ [∑ t γ trt | s0 = s ] = arg max
π Es∼ρ [V π(s)] . (1)
Constrained MDP. A constrained Markov Decision Process (CMDP) is an MDP with extra constraints that restrict the domain of allowed policies (Altman, 1999). Specifically, CMDP introduces a constraint functionC(π) that maps a policy to a scalar, and a thresholdα ∈ R. The objective of CMDP is to maximize the expected returnR(τ) = ∑ t γ
trt of a trajectory τ = {s0, a0, r1, s1, a1, r2, s2, . . .} subject to a constraint: π∗ = arg maxπ Eτ∼π [R(τ)] , s.t. C(π) ≤ α. A popular choice of constraint is based on the transition cost function (Tessler et al., 2019) c(s, a, r, s′) ∈ R which assigns a 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(π) = Eτ∼π [ ∑ t γ
tc(st, at, rt+1, st+1)] . In this work, we propose a shortest-path constraint, that provably preserves the optimal policy of the original unconstrained MDP, while reducing the trajectory space. We will use a cost function-based formulation to implement our constraint (see Section 3 and 4).
3 FORMULATION: k-SHORTEST 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)+γV ∗(s) > 0 for all initial states s ∈ ρ and all rewarding states that optimal policy visits with non-zero probability s ∈ {s|r(s) 6= 0, π∗(s) > 0}. We exploit this mild assumption to prove that our constraint preserves optimality. Intuitively, we exclude the case when the optimal strategy for the agent is at best choosing a “lesser of evils” (i.e., 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 −|mins∈{s|π∗(s)>0} V ∗(s)| for every transition, assuming the policy is proper1. Goalconditioned RL (Nachum et al., 2018) and most of the well-known domains such as Atari (Bellemare et al., 2013), DeepMind Lab (Beattie et al., 2016), MiniGrid (Chevalier-Boisvert et al., 2018), etc., satisfy this assumption. Also, for general settings with stochastic MDP and multi-goals, we require additional assumptions to prove the optimality guarantee (See Appendix G for details).

heading: 3.1 SHORTEST-PATH POLICY AND SHORTEST-PATH CONSTRAINT
text: Let τ be a path defined by a sequence of states: τ = {s0, . . . , s`(τ)}, where `(τ) is the length of a path τ (i.e., `(τ) = |τ | − 1). We denote the set of all paths from s to s′ by Ts,s′ . A path τ∗ from s to s′ is called a shortest path from s to s′ if `(τ) is minimum, i.e., `(τ∗) = minτ∈Ts,s′ `(τ).
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) to a goal state or between any state pairs should be a counterpart. We consider a set of all admissible paths from s to s′ under a policy π: Definition 1 (Path set). T πs,s′ = {τ | s0 = s, s`(τ) = s′, pπ(τ) > 0, {st}t<`(τ) 6= s′}. That is, T πs,s′ is a set of all paths that policy π may roll out from s and terminate once visiting s′.
If the MDP is a single-goal task, i.e., there exists a unique (rewarding) goal state sg ∈ S such that sg is a terminal state, and R(s) > 0 if and only if s = sg, any shortest path from an initial state to the goal state is the optimal path with the highest return R(τ), and a policy that rolls out a shortest path is therefore optimal (see Lemma 4).2 This is because all states except for sg 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). T πs,s′,nr = {τ | τ ∈ T πs,s′ , {rt}t<`(τ) = 0}. In words, T πs,s′,nr is a set of all non-rewarding paths from s to s′ rolled out by policy π (i.e., τ ∈ T πs,s′ ) without any associated reward except the last step (i.e., {rt}t<|τ | = 0). Now we are ready to define a notion of length with respect to a policy and shortest path policy:
Definition 3 (π-distance from s to s′). Dπnr(s, s′) = logγ ( Eτ∼π: τ∈T π
s,s′,nr
[ γ`(τ) ] ) Definition 4 (Shortest path distance from s to s′). Dnr(s, s′) = minπDπnr(s, s′). We define π-distance to be the log-mean-exponential of the length `(τ) of non-rewarding paths τ ∈ T πs,s′,nr. When there exists no admissible path from s to s′ under policy π, the path length is defined to be ∞: Dπnr(s, s′) = ∞ if T πs,s′,nr = ∅. We note that when both MDP and policy are deterministic, Dπ(s, s′) recovers the natural definition of path length, Dπnr(s, s ′) = `(τ).
We call a policy a shortest-path policy from s to s′ if it roll outs a path with the smallest π-distance: Definition 5 (Shortest path policy from s to s′). π ∈ ΠSPs→s′ = {π ∈ Π | Dπnr(s, s′) = Dnr(s, s′)}. Finally, we will define the shortest-path (SP) constraint. Let SIR = {s | R(s) > 0 or ρ(s) > 0} be the union of all initial and rewarding states, and Φπ = {(s, s′) | s, s′ ∈ SIR, ρ(s) > 0, T πs,s′,nr 6= ∅} be the subset of SIR such that agent may roll out. Then, the SP constraint is applied to the nonrewarding sub-paths between states in Φπ: T πΦ,nr = ⋃ (s,s′)∈Φπ T πs,s′,nr. We note that these definitions are used in the proofs (Appendix G). Now, we define the shortest-path constraint as follows: Definition 6 (Shortest-path constraint). A policy π satisfies the shortest-path (SP) constraint if π ∈ ΠSP, where ΠSP = {π | For all s, s′ ∈ T πΦ,nr, it holds π ∈ ΠSPs→s′}.
1It is an instance of potential-based reward shaping which has optimality guarantee (Ng et al., 1999). 2We refer the readers to Appendix F for more detailed discussion and proofs for single-goal MDPs.
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, we can show that an optimal policy indeed satisfies the SP constraint in a general MDP setting. In other words, the shortest path constraint should not change optimality: Theorem 1. For any MDP, an optimal policy π∗ satisfies the shortest-path constraint: π∗ ∈ ΠSP. Proof. See Appendix G for the proof.
3.2 RELAXATION: k-SHORTEST-PATH CONSTRAINT Implementing the shortest-path constraint is, however, intractable since it requires a distance predictor Dnr(s, s
′). Note that the distance predictor addresses the optimization problem, which might be as difficult as solving the given task. To circumvent this challenge, we consider its more tractable version, namely a k-shortest path constraint, which reduces the shortest-path problem Dnr(s, s′) to a 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 7 (k-shortest-path constraint). A policy π satisfies the k-shortest-path constraint if π ∈ ΠSPk , where
ΠSPk = {π | For all s, s′ ∈ T πΦ,nr, Dπnr(s, s′) ≤ k, it holds π ∈ ΠSPs→s′}. (2)
Note that the SP constraint (Definition 6) is relaxed by adding a condition Dπnr(s, s ′) ≤ k. In other words, the k-SP constraint is imposed only for s, s′-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 MDPM, ΠSPm ⊂ ΠSPk if k < m. Proof. It is true since {(s, s′) | Dπnr(s, s′) ≤ k} ⊂ {(s, s′) | Dπnr(s, s′) ≤ m} for k < m.
Theorem 3. For an MDPM and any k ∈ R, an optimal policy π∗ is a k-shortest-path policy. Proof. Theorem 1 tells π∗ ∈ ΠSP. Eq. (2) tells ΠSP = ΠSP∞ and Lemma 2 tells ΠSP∞ ⊂ ΠSPk . Collectively, we have π∗ ∈ ΠSP = ΠSP∞ ⊂ ΠSPk .
In conclusion, Theorem 3 states that the k-SP constraint does not change the optimality of policy, and Lemma 2 states a larger k results in a larger reduction in policy search space. Thus, it motivates us to apply the k-SP constraint in policy search to more efficiently find an optimal policy. For the numerical experiment on measuring the reduction in the policy roll-outs space, please refer to Section 6.4.

heading: 4 SPRL: SHORTEST-PATH REINFORCEMENT LEARNING
text: k-Shortest-Path Cost. The objective of RL with the k-SP constraint ΠSPk can be written as:
π∗ = arg maxπ Eπ [R(τ)] , s.t. π ∈ ΠSPk , (3)
where ΠSPk = {π | ∀(s, s′ ∈ T πΦ,nr), Dπnr(s, s′) ≤ k, it holds π ∈ ΠSPs→s′} (Definition 7). We want to formulate the constraint π ∈ ΠSPk in the form of constrained MDP (Section 2), i.e., as C(π) ≤ α. We begin by re-writing the k-SP constraint into a cost-based form:
ΠSPk = {π | CSPk (π) = 0}, where CSPk (π) = ∑
(s,s′∈T πΦ,nr):Dπnr(s,s′)≤k
I [Dnr(s, s′) < Dπnr(s, s′)] . (4)
Note that I [Dnr(s, s′) < Dπnr(s, s′)] = 0 ↔ Dnr(s, s′) = Dπnr(s, s′) since Dnr(s, s′) ≤ Dπnr(s, s′) from Definition 4. Similar to Tessler et al. (2019), we apply the constraint to the on-policy trajectory τ = (s0, s1, . . .) with discounting by replacing (s, s′) with (st, st+l) where [t, t+ l] represents each segment of τ with length l:
CSPk (π) ' Eτ∼π [∑ (t,l):t≥0,l≤k γ t · I [Dnr(st, st+l) < Dπnr(st, st+l)] · I [ {rj}t+l−1j=t = 0 ]] = Eτ∼π [∑ (t,l):t≥0,l≤k γ t · I [ Dnr(st, st+l) < logγ ( Eτ∈T πst,st+l,nr [ γ|τ | ])] · I [ {rj}t+l−1j=t = 0
]] ≤ Eτ∼π [∑ (t,l):t≥0,l≤k γ t · I [Dnr(st, st+l) < k] · I [ {rj}t+l−1j=t = 0 ]] , ĈSPk (π). (5)
Algorithm 1 Reinforcement Learning with k-SP constraint (SPRL) Require: Hyperparameters: k ∈ N, λ > 0
1: for n = 1, . . . , Npolicy do 2: Rollout transitions τ = {st, at, rt}|τ |t=1 ∼ π 3: Compute the cost term {ct}|τ |t=1 as Eq. (13). 4: Update policy π to maximize the objective as Eq. (10) (e.g., run PPO train steps). 5: Update Rnet training-buffer B = B ∪ {τ}. 6: if n%TRnet = 0 then . Periodically train Rnet for NRnet times 7: for m = 1, . . . , NRnet do 8: Sample triplet (sanc, s+, s−) ∼ B. . See Appendix D.3 for detail 9: Update Rnet to minimize LRnet as Eq. (14).
Note that it is sufficient to consider only the cases l = k (because for l < k, given Dnr(st, st+k) < k, we have D(st, st+l) ≤ l < k). Then, we simplify ĈSPk (π) as
ĈSPk (π) = Eτ∼π [∑ t γ tI [Dnr(st, st+k) < k] · I [ {rj}t+k−1j=t = 0 ]] (6)
= Eτ∼π [∑ t γ tI[t ≥ k] · I [Dnr(st−k, st) < k] · I [ {rj}t−1j=t−k = 0 ]] . (7)
Finally, the per-time step cost ct is given as: ct = I[t ≥ k] · I [Dnr(st−k, st) < k] · I [ {rj}t−1j=t−k = 0 ] , (8)
where ĈSPk (π) = Eτ∼π [ ∑ t γ tct]. Note that ĈSPk (π) is an upper bound of C SP k (π), which will be minimized by the bound to 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 k-shortest-path constraint. In Eq. (8), ct depends on the previous k steps; hence, the resulting CMDP becomes a (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 as follows:
min λ>0 max θ L(λ, θ) = min λ>0 max θ
Eτ∼πθ [∑ t γ t (rt − λct) ] , (9)
where L is the Lagrangian, θ is the parameter of policy π, and λ > 0 is the Lagrangian multiplier. Since Theorem 3 shows that the shortest-path constraint preserves the optimality, we are free to set any λ > 0. Thus, we simply consider λ as a tunable positive hyperparameter, and simplify the min-max problem (9) to an RL objective with costs ct being added:
max θ
Eτ∼πθ [∑ t γ t (rt − λct) ] . (10)
Practical implementation of the cost function. We implement the binary distance discriminator I(Dnr(st−k, st) < k) in Eq. (8) using k-reachability network (Savinov et al., 2018b). The kreachability network Rnetk(s, s′) is trained to output 1 if the state s′ is reachable from the state s with less than or equal to k consecutive actions, and 0 otherwise. Formally, we take the functional form: Rnetk(s, s′) ' I (Dnr(s, s′) < k + 1) . We then estimate the cost term ct using (k − 1)-reachability network as follows:
ct = I [Dnr(st−k, st) < k] · I [ {rl}t−1l=t−k = 0 ] · I [t ≥ k] (11)
= Rnetk−1(st−k, st) · I [ {rl}t−1l=t−k = 0 ] · I [t ≥ k] . (12)
Intuitively speaking, if the agent takes a k-shortest path, then the distance between st−k and st is k, hence ct = 0. If it is not a k-shortest path, ct > 0 since the distance between st−k and st will be less than k. In practice, due to the error in the reachability network, we add a small tolerance ∆t ∈ N to ignore outliers. It leads to an empirical version of the cost as follows:
ct ' Rnetk−1(st−k−∆t, st) · I [ {rl}t−1l=t−k−∆t = 0 ] · I(t ≥ k + ∆t). (13)
In our experiment, we found that a small tolerance ∆t ' k/5 works well in general. Similar to Savinov et al. (2018b), we used the following contrastive loss for training the reachability network:
LRnet = − log (Rnetk−1(sanc, s+))− log (1− Rnetk−1(sanc, s−)) , (14) where sanc, s+, s− are the anchor, positive, and negative samples, respectively (See Appendix D.3 for the detail of training).

heading: 5 RELATED WORK
text: 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 a dynamic programming-based algorithm similar to the value iteration (Sutton & Barto, 2018) to solve it. Our main idea is inspired by (but not based on) this viewpoint. Specifically, our method does not directly solve the shortest path problem via planning; hence, our method does not require model. Our method only exploits the optimality guarantee of the shortest-path under the π-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 on learning a distance metric in state (or goal) space for to construct a high-level MDP graph and perform planning to find a 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 a constant step penalty as a distance function. Zhang et al. (2018); 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., 2018a) defined a binary distance based on reachability network (RNet) to connect near by nodes in the graph. However, the proposed distance metrics and methods can be used only for the goal-conditioned 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. (2018b) as a way to measure the novelty of a state for exploration. Intuitively, if current state is not reachable from previous states in episodic memory, it is considered to be novel. SPTM (Savinov et al., 2018a) used RNet to predict the local connectivity (i.e., binary distance) between observations in 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 to Appendix H for further discussions about other related works.

heading: 6 EXPERIMENTS

heading: 6.1 SETTINGS
text: Environments. We evaluate our SPRL on two challenging domains: MiniGrid (Chevalier-Boisvert et al., 2018) and DeepMind Lab (Beattie et al., 2016). MiniGrid is a 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) are considered. We conducted experiments on four standard tasks: FourRooms-7×7, FourRooms-11×11, KeyDoors-7×7, and KeyDoors-11×11. DeepMind Lab is a 3D environment with first person view. Along with the nature of partially-observed 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, GoalLarge3, and ObjectMany. We refer the readers to Figure 2 for examples of observations.
3GoalLarge task corresponds to the Sparse task in Savinov et al. (2018b), and our Figure 4 reproduces the result reported in Savinov et al. (2018b).
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 a 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 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-Grid agent has access to the agent’s (x, y) coordinates. It uniformly divides the world in 2D grid cells, and the agent is rewarded for visiting a novel grid cell. The ICM agent learns a forward and inverse dynamics model and uses the prediction error of the forward model to measure the novelty. We used the publicly available codebase (Savinov et al., 2018b) 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
Figure 3 shows the performance of compared methods on 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 to the PPO in the tasks with small state space (e.g., FourRooms-7×7 and KeyDoors-7×7). However, SPRL demonstrates a significant performance gain since it improves the exploitation by avoiding sub-optimality caused by taking a non-shortest-path. 6.3 RESULTS ON DeepMind Lab
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-based 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 upperbound performance of novelty-seeking 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 k-SHORTEST-PATH 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
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 ∆t?
Experimental setup. We implemented a simple tabular 7×7 Four-rooms domain where each state maps to a unique (x, y) location of the agent. The agent can take up, down, left, right primitive actions to move to the neighboring state, and the episode horizon is set to 14 steps. The goal of the agent is reaching to the goal state, which gives +1 reward and terminates the episode. We computed the ground-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 SPRL agent.
Results. Figure 5 summarizes the reduction in the trajectory space size. We searched over all possible trajectories of length 14 using breadth-first-search (BFS). Then we counted the number trajectories satisfying our k-SP constraint with varying parameters k and toler-
ance ∆t and divided by total number of trajectories (i.e., 414 = 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 ∆t = 2, we get only 24/268M size of the original search space. As we increase k, we can see more reduction in the trajectory space, which is consistent with Lemma 2. Also, increasing the tolerance ∆t slightly hurts the performance, but still achieves a large reduction (See Appendix A for more analysis on effect of k and tolerance).
6.5 QUALITATIVE RESULT ON MiniGrid
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 6 (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 a reward-free setting. We counted all the state transitions (st → st+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 a longest possible shortest path, which results in a “straight” path across the rooms. Note that this only represents a partial behavior of SPRL, since our 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 a shortest path between rewarding and initial states that is consistent with the shortest-path definition in Definition 7.

heading: 7 CONCLUSION
text: We presented the k-shortest-path constraint, which can improve the sample-efficiency of any modelfree RL method by preventing the agent from taking a sub-optimal transition. We empirically showed that our SPRL outperforms vanilla RL and strong novelty-seeking exploration baselines on two challenging domains. We believe that our framework develops a 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.

heading: A.3 STACKING OBSERVATION
text: The CMDP with k-SP constraint becomes the (k + 1)-th order MDP as shown in Eq. (8). Thus, in theory, the policy should take currrent state st augmented by stacking the k previous states as input: [st−k, st−k+1 . . . , st], where [·] is a stacks the pixel observation along the channel (i.e., color) dimension. However, stacking the observation may not lead to 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, we stacked the observation from t−m to t: [st−m, st−m+1, . . . , st]. We experimented up to m = k: up to m = 10 for DeepMind Lab and m = 5 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 is used (e.g., Savinov et al. (2018b)). Thus, we did not augment the observation in all the experiments.

heading: B ANALYSIS ON THE REACHABILITY NETWORK (RNET)

heading: B.1 ACCURACY OF THE REACHABILITY NETWORK
text: We measured the accuracy of reachability network on DeepMind Lab and MiniGrid in Figure 14 and Figure 13. The accuracy was measured on the validation set; we sampled 15,000 positive and negative samples respectively from the replay buffer of size 60,000. Specifically, for an anchor st, we sample the positive sample st′ from t′ ∈ [t+ 1, t+ k + ∆t], and the negative sample st′′ from t′′ ∈ [t+ k + ∆t+ ∆−, t+ k + ∆t+ 2∆−]. The RNet reaches the accuracy higher than 80% in
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, in which case they are in fact the positive samples.

heading: B.2 ABLATION STUDY: COMPARISON BETWEEN THE LEARNED RNET AND THE GT-RNET
text: In this section, we study the effect of RNet’s accuracy on 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 s and s′, we 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 is 1 and otherwise, the output is 0.
Result. We compared the performance of our SPRL with the learned RNet and the ground-truth RNet (GT-SPRL) in Figure 15 with the best hyperparameters. Overall, the performance of SPRL
and GT-SPRL are similar. This is partly because the learned RNet achieves a 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-7×7 and KeyDoors-7×7. This is possible since a small noise in RNet output can have a similar effect to the increased tolerance ∆t on RNet, which makes the resulting cost more dense, which may be helpful depending on the tasks and hyperparameters.

heading: B.3 ABLATION STUDY: CURRICULUM LEARNING OF RNET
text: We applied the linear scheduling of k to see if curriculum learning can improve the RNet training, and eventually improve our SPRL performance. For example, in case of FourRooms-7×7, we used k = 1 until 0.1M steps, and k = 2 until 0.2M steps, and so on, and finally k = 5 from 0.4M steps to 0.5M steps. Figure 16 and Figure 17 compares the performance of SPRL on 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 k during training RNet makes the learning unstable since changing k completely flips the learning target for some inputs; e.g, the two states that are 2 steps away are unreachable for k = 1 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.
C EXPERIMENT DETAILS OF MiniGrid DOMAIN

heading: C.1 ENVIRONMENT
text: MiniGrid is a 2D grid-world environment with diverse predefined tasks (Chevalier-Boisvert 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 orientation of movement and changing object status via interaction (e.g., key-door).
State Space. An observation st 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,w)-th element of observation tensor is (type, 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 ×W ) varies depending on the task; e.g., for FourRooms-7×7 task, the map size is 7× 7. 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.
• Turn-Counter-Clockwise: change the direction counter-clockwise by 90 degree. • Turn-Clockwise: change the direction clockwise by 90 degree. • Move-Forward: move toward direction by 1 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-doors: 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 1− 0.9(length of episode/maximum step for episode). Thus, the agent can maximize the reward by reaching to the goal location in shortest time.

heading: C.2 TASKS
text: In FourRooms-7×7 and FourRooms-11×11, the map structure has four large rooms, and the agent needs to reach to the goal. In KeyDoors-7×7 and KeyDoors-11×11, the agent needs to pick up the key, go to the door, and open the door before reaching to the goal location.

heading: C.3 ARCHITECTURE AND HYPER-PARAMETERS
text: We used a simple CNN architecture similar to (Mnih et al., 2015) for policy network. The network consists of Conv1(16x2x2-1/SAME)-CReLU-Conv2(8x2x2-1/SAME)-CReLUConv3(8x2x2-1/SAME)-CReLU-FC(512)-FC(action-dimension), where SAME padding ensures the input and output have the same size (i.e., width and height) and CReLU (Shang et al., 2016) is a non-linear activation function applied after each layer. We used Adam (Kingma & Ba, 2014) optimizer to optimize the policy network.
For hyper-parameter search, we swept over a set of hyper-parameters 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.
D EXPERIMENT DETAILS OF DeepMind Lab DOMAIN

heading: D.1 ENVIRONMENT
text: DeepMind Lab is a 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 st has the dimension of 120× 160× 3 tensor. Observation is given as a first-person view of the map structure.
Action Space and transition dynamics The episode terminates after the fixed number of steps regardless of goal being achieved. The original action space consists of seven discrete actions: Move-Forward, Move-Backward, Strafe Left, Strafe Right, Look Left, Look Right, Look Left and Move-Forward, 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).

heading: D.2 TASKS
text: We tested our agent and compared methods on three standard tasks in DeepMind Lab: GoalSmall, GoalLarge, and ObjectMany which correspond to explore goal locations small, explore goal locations large, and explore object rewards many, respectively. GoalSmall and GoalLarge has a 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 is re-spawned in a 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 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 goal is to gather as many object as possible within the episode length.
Algorithm 2 Sampling the triplet data from an episode for RNet training Require: Hyperparameters: k ∈ N, Positive bias ∆+ ∈ N, Negative bias ∆− ∈ N
1: Initialize tanc ← 0. 2: Initialize Sanc = ∅, S+ = ∅, S− = ∅. 3: while tanc < T do 4: Sanc = Sanc ∪ {stanc}. 5: t+ = Uniform(tanc + 1, tanc + k). 6: t− = Uniform(tanc + k + ∆−, T ). 7: S+ = S+ ∪ {st+}. 8: S− = S− ∪ {st−}. 9: tanc = Uniform(t+ + 1, t+ + ∆+).
return Sanc, S+, S−

heading: D.3 REACHABILITY NETWORK TRAINING
text: Similar to Savinov et al. (2018b), we used the following contrastive loss for training the reachability network:
LRnet = − log (Rnetk−1(sanc, s+))− log (1− Rnetk−1(sanc, s−)) , (15) where sanc, s+, s− 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-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 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 1M steps. Multiple tolerance. In order to improve the stability of Reachability prediction, we used the statistics over multiple samples rather than using a single-sample estimate as suggested in Eq. (13). As a choice of sampling method, we simply used multiples of tolerance. In other words, given st−(k+∆t) and st as inputs for reachability network, we instead used st−(k+n∆t) and st where 1 ≤ n ≤ N∆t, n ∈ N and N∆t is the number of tolerance samples. We used 90-percentile of N∆t outputs of reachability network, Rnetk−1(st−(k+n∆t), st), as in (Savinov et al., 2018b) to get the representative of the samples.

heading: D.4 ARCHITECTURE AND HYPER-PARAMETERS
text: Following (Savinov et al., 2018b), we used the same CNN architecture used in (Mnih et al., 2015). To fit the architecture, we resized the input observation image into 84× 84× 3 image, and normalized by dividing the pixel value by 255.
For SPRL, we used a 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., 2018b), ECO used Resnet-18 (He et al., 2016) architecture with 2-2-2-2 residual blocks and 512-dimensional output fully-connected layer to implement each branch. For SPRL, we used Resnet-12 with 2-2-1 residual blocks and 512-dimensional output fully-connected 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 are concatenated and forwarded to three4 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× 84× 3, which is smaller than the original 120× 160× 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 a 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.
4Savinov et al. (2018b) used four 512-dimensional fully-connected layers.

heading: E OPTION FRAMEWORK-BASED FORMULATION

heading: E.1 PRELIMINARY: OPTION FRAMEWORK
text: Options framework (Sutton, 1998) defines options as a generalization of actions to include temporally extended series of action. Formally, options consist of three components: a policy π : S×A → [0, 1], a termination condition β : S+ → [0, 1], and an initiation set I ⊆ S. An option 〈I, π, β〉 is available in state s if and only if s ∈ I. If the option is taken, then actions are selected according to π until the option terminates stochastically according to β. Then, the option-reward and option-transition models are defined as
ros = E { rt+1 + γrt+2 + · · ·+ γk−1rt+k | E(o, s, t) } (16)
P oss′ = ∞∑ k=1 p (s′, k) γk (17)
where t+ k is the random time at which option o terminates, E(o, s, t) is the event that option o is initiated in state s at time t, and p(s′, k) is the probability that the option terminates in s′ after k steps. Using the option models, we can re-write Bellman equation as follows:
V π(s) = E [ rt+1 + · · ·+ γk−1rt+k + γkV π(st+k) ] , (18)
= ∑ o∈O Pr[E(o, s)] [ ros + ∑ s′ P oss′V π(s′) ] . (19)
where t+ k is the random time at which option o terminates and E(o, s) is the event that option o is initiated in state s.

heading: E.2 OPTION-BASED VIEW-POINT OF SHORTEST-PATH CONSTRAINT
text: In this section, we present an option framework-based viewpoint of our shortest-path (SP) constraint. We will first show that a (sparse-reward) MDP can be represented as a weighted directed graph where nodes are rewarding states, and edges are options. Then, we show that a policy satisfying SP constraint also maximizes the option-transition probability P oss′ .
For a given MDPM = (S,A,R,P, ρ, S̄), let SR = {s|R(s) 6= 0} ⊂ S be the set of all rewarding states, where R(s) is the reward function upon arrival to state s. In sparse-reward tasks, it is assumed that |SR| << |S|. Then, we can form a weighted directed graph Gπ = (V, E) of policy π and given MDP. The vertex set is defined as V = SR ∪ ρ0 ∪ S̄ where SR is rewarding states, ρ0 is the initial states, and S̄ is the terminal states. Similar to the path set in Definition 2, let Ts→s′ denotes a set of paths transitioning from one vertex s ∈ V to another vertex s′ ∈ V:
Ts→s′ = {τ |s0 = s, s`(τ) = s′, {st}0<t<`(τ) ∩ V = ∅}. (20) Then, the edge from a vertex s ∈ V to another vertex s′ ∈ V is defined by an (implicit) option tuple: o(s, s′) = (I, π, β)(s,s′), where I = {s}, β(s) = I(s = s′), and
π(s,s ′)(τ) = { 1 Zπ(τ) for τ ∈ Ts→s′ 0 otherwise , (21)
where Z is the partition function to ensure ∫ π(s,s
′)(τ)dτ = 1. Following Eq. (16), the option-reward is given as
rπs,s′ = Eπ (s,s′) [ rt+1 + γrt+2 + · · ·+ γk−1rt+k | E(o(s,s ′), s, t) ] , (22)
= Eπ (s,s′) [ γk−1rt+k | E(o(s,s ′), s, t) ] , (23)
where t+ k is the random time at which option o(s, s′) terminates, and E(o, s, t) is the event that option o(s, s′) is initiated in state s at time t. Note that in the last equality, rt+1 = · · · = rt+k−1 = 0 holds since {st+1, . . . , st+k−1} ∩ V = ∅ from the definition of option policy π(s,s ′). Following
Eq. (17), the option transition is given as
Pπs,s′ = ∞∑ k=1 p(s′, k)γk (24)
= Eπ [ γk|s0 = s, sk = s′, {rt}t<k = 0 ] (25)
= γD π nr(s,s ′). (26) where p(s′, k) is the probability that the option terminates in s′ after k steps, and Dπnr(s, s
′) is the π-distance in Definition 3. Then, we can re-write the shortest-path constraint in terms of Pπs,s′ as follows:
ΠSP = {π|∀(s, s′ ∈ T πŝ,ŝ′,nr s.t. (ŝ, ŝ′) ∈ Φπ), Dπnr(s, s′) = min π Dπnr(s, s ′)} (27)
= {π|∀(s, s′ ∈ T πŝ,ŝ′,nr s.t. (ŝ, ŝ′) ∈ Φπ), Pπs,s′ = max π Pπs,s′} (28)
Thus, we can see that the policy satisfying SP constraint also maximizes the option-transition probability. We will use this result in Appendix F.

heading: F SHORTEST-PATH CONSTRAINT: A SINGLE-GOAL CASE
text: In this section, we provide more discussion on a special case of the shortest-path constraint (Section 3.1), when the (stochastic) MDP defines a single-goal task: i.e., there exists a unique initial state sinit ∈ S and a unique goal state sg ∈ S such that sg is a terminal state, and R(s) > 0 if and only if s = sg .
We first note that the non-rewarding path set is identical to the path set in such a setting, because the condition rt = 0(t < `(τ)) from Definition 2 is always satisfied as R(s) > 0 ⇔ s = sg and s`(τ) = sg:
T πs,s′,nr = T πs,s′ = {τ | s0 = s, s`(τ) = s′, pπ(τ) > 0, {st}t<`(τ) 6= s′} (29)
Again, T πs,s′ is a set of all path starting from s (i.e., and ending at s′ (i.e., s`(τ) = s′) where the agent visits s′ only at the end (i.e., {st}t<`(τ) 6= s′), that can be rolled out by policy with a non-zero probability (i.e., pπ(τ) > 0).
We now claim that an optimal policy satisfies the shortest-path constraint. The idea is that, since sg is the only rewarding and terminal state, maximizing R(τ) = γTR(sg) where sT = sg corresponds to minimizing the number of time steps T to reach sg. In this setting, a shortest-path policy is indeed optimal.
Lemma 4. For a single-goal MDP, any optimal policy satisfies the shortest-path constraint.
Proof. Let sinit be the initial state and sg be the goal state. We will prove that any optimal policy is a shortest-path policy from the initial state to the goal state. We use the fact that sg is the only rewarding state, i.e., R(s) > 0 entails s = sg .
π∗ = arg max π
Eτ∼πs∼ρ [∑ t γ trt ∣∣∣∣ s0 = s] (30) = arg max
π Eτ∼π
[∑ t γ trt ∣∣∣∣ s0 = sinit] (31) = arg max
π Eτ∼π
[ γTR(sg) | s0 = sinit, s`(τ) = sg ] (32)
= arg max π
Eτ∼π [ γT | s0 = sinit, s`(τ) = sg ] (33)
= arg min π
logγ ( Eτ∼π [ γT | s0 = sinit, s`(τ) = sg ]) (34)
= arg min π
Dπnr(sinit, sg), (35)
where Eq. (33) holds since R(sg) > 0 from our assumption that R(s) + V ∗(s) > 0.

heading: G PROOF OF THEOREM 1
text: We make the following assumptions on the Markov Decision Process (MDP) M: namely mild stochasticity (Definitions 8 and 9). Definition 8 (Mild stochasticity (1)). In MDPM, there exists an optimal policy π∗ and the corresponding shortest-path policy πsp ∈ ΠSP such that for all s, s′ ∈ Φπ , it holds pπ∗(s̄ = s′|s0 = s) = pπsp(s̄ = s
′|s0 = s). Definition 9 (Mild stochasticity (2)). In MDPM, the optimal policy π∗ does not visit the same state more than once: For all s ∈ S such that ρπ∗(s) > 0, it holds ρπ∗(s) = 1, where ρπ(s) , Es0∼ρ0(S),a∼π(A|s),s′∼(S|s,a) [∑T t=1 I (st = 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: π∗ ∈ ΠSP.
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 V π(s) as follows:
V π(s) = ∑ o∈O Pr[E(o, s)] [ ros + ∑ s′ P oss′V π(s′) ] (36)
= ∑
s′∈SIR pπ(s̄ = s
′|s0 = s) [ R(s′)Eτ∼π(γ`(τ)|s0 = s, s̄ = s′) + γPπs,s′V π(s′) ] (37)
= ∑
s′∈SIR pπ(s̄ = s
′|s0 = s) [ R(s′)Pπs,s′ + γP π s,s′V π(s′) ] , (38)
= ∑
s′∈SIR pπ(s̄ = s
′|s0 = s)Pπs,s′ [R(s′) + γV π(s′)] , (39)
where s̄ is the first rewarding state that agent encounters. Intuitively, pπ(s̄ = s′|s0 = s) means the probability that the s′ is the first rewarding state that policy π encounters when it starts from s. From Eq. (28), our goal is to show:
π∗ ∈ ΠSP = {π | ∀(s, s′) ∈ T πΦ,nr, Pπs,s′ = P ∗s,s′}, (40) where P ∗s,s′ = maxπ P π s,s′ .
We will prove Eq. (40) by contradiction. Suppose π∗ is an optimal policy such that π∗ 6∈ ΠSP. Then, ∃(ŝ, ŝ′ ∈ T π ∗ Φ,nr) s.t. P π∗
ŝ,ŝ′ 6= P ∗ŝ,ŝ′ . (41) Recall the definition: P ∗s,s′ = maxπ P π s,s′ . Then, for any π, the following statement is true. Pπs,s′ 6= P ∗s,s′ ↔ Pπs,s′ < P ∗s,s′ . (42) Thus, we have
Pπ ∗ ŝ,ŝ′ < P ∗ ŝ,ŝ′ (43)
Let πsp ∈ ΠSP be a shortest path policy that preserves stochastic dynamics from Definition 8. Then, we have
Pπ ∗ ŝ,ŝ′ < P ∗ ŝ,ŝ′ = P πsp ŝ,ŝ′ . (44)
Then, let’s compose a new policy π̂:
π̂(a|s) =
{ πsp(a|s) if ∃ τ ∈ T πsp ŝ,ŝ′,nr s.t. s ∈ τ
π∗(a|s) otherwise . (45)
Now consider a path τŝ→ŝ′ that agent visits ŝ at time t = i and transitions to ŝ′ at time t = j > i while not visiting any rewarding state from t = i to t = j with non-zero probability (i.e., pπsp(τ) > 0).
We can define a set of such paths as follows:
T̂ŝ→ŝ′ = {τ | ∃(i < j), si = ŝ, sj = ŝ′, {st}i<t<j ∩ SIR = ∅, pπsp(τ) > 0}. (46)
To reiterate the definitions from Definition 6: SIR = {s | R(s) > 0 or ρ(s) > 0} is the union of all initial and rewarding states, and Φπ = {(s, s′) | s, s′ ∈ SIR, ρ(s) > 0, T πs,s′,nr 6= ∅} is the subset of SIR such that agent may roll out. From Definition 9 and Eq. (45), the likelihood of a path τ under policy π̂ is given as follows:
pπ̂(τ) = { pπ∗(τ ∈ T̂ŝ→ŝ′)pπsp(τ |τ ∈ T̂ŝ→ŝ′) for τ ∈ T̂ŝ→ŝ′ pπ∗(τ) otherwise , (47)
where pπ̂(τ) is the likelihood of trajectory τ under policy π̂, pπ̂(τ ∈ T̂ŝ→ŝ′) = ∫ τ∈T̂ŝ→ŝ′ pπ̂(τ)dτ
ensures the likelihood π̂(τ) to be a valid probability density function (i.e., ∫ pπ̂(τ)dτ = 1). From the path τŝ→ŝ′ and i, j, we will choose two states sir, s′ir ∼ τŝ→ŝ′ , where sir = max
t (st|st ∈ SIR, t ≤ i), s′ir = min t (st|st ∈ SIR, j ≤ t). (48)
Note that such sir and s′ir always exist in τŝ→ŝ′ since the initial state and the terminal state satisfy the condition to be sir and s′ir.
Then, we can show that the path between sir and s′ir is not a shortest-path. Recall the definition of Dπnr(s, s ′) (Definition 3):
Dπ ∗ nr (sir, s ′ ir) := logγ ( Eτ∼π∗: τ∈T π∗
sir,s ′ ir,nr
[ γ`(τ) ]) (49)
= logγ Eτ∼π∗ [γ`(τ) | τ ∈ T π∗sir,s′ir,nr]︸ ︷︷ ︸ ♣  (50) where we will use ♣ := γ`(τ) | τ ∈ T π∗sir,s′ir,nr for a shorthand notation. Then, we have
γD π∗ nr (sir,s ′ ir) := Eτ∼π∗ [♣] (51) = pπ∗(τ ∈ T̂ŝ→ŝ′)Eτ∼π∗ [ ♣ | τ ∈ T̂ŝ→ŝ′ ] + pπ∗(τ /∈ T̂ŝ→ŝ′)Eτ∼π∗ [ ♣ | τ /∈ T̂ŝ→ŝ′ ] . (52)
(From Definition 5) < pπ∗(τ ∈ T̂ŝ→ŝ′)Eτ∼πsp [ ♣ | τ ∈ T̂ŝ→ŝ′ ] + pπ∗(τ /∈ T̂ŝ→ŝ′)Eτ∼π∗ [ ♣ | τ /∈ T̂ŝ→ŝ′ ] (53)
(From Eq. (47)) = pπ̂(τ ∈ T̂ŝ→ŝ′)Eτ∼π̂ [ ♣ | τ ∈ T̂ŝ→ŝ′ ] + pπ̂(τ /∈ T̂ŝ→ŝ′)Eτ∼π̂ [ ♣ | τ /∈ T̂ŝ→ŝ′ ] (54)
= Eτ∼π̂ [♣] = γD π̂ nr (sir,s ′ ir) (55) ⇐⇒ Dπ ∗
nr (sir, s ′ ir) > D π̂ nr(sir, s ′ ir) (56)
where Ineq. (56) is given by the fact that γ < 1. Then, Pπ ∗
sir,s′ir < P π̂sir,s′ir .
From Eq. (39), we have V π̂(sir) = ∑
s′∈SIR pπ̂(s̄ = s
′ | s0 = sir)P π̂sir,s′ [ R(s′) + γV π̂(s′) ] (57)
= pπ̂(s̄ = s ′ ir | s0 = sir)P π̂sir,s′ir [ R(s′ir) + γV π̂(s′ir) ]
+ ∑
s′∈SIR\s′ir
pπ̂(s̄ = s ′ | s0 = sir)P π̂sir,s′
[ R(s′) + γV π̂(s′) ] (58)
= pπ∗(s̄ = s ′ ir | s0 = sir)P π̂sir,s′ir [ R(s′ir) + γV π∗(s′ir) ]
+ ∑
s′∈SIR\s′ir
pπ∗(s̄ = s ′ | s0 = sir)Pπ
∗
sir,s′
[ R(s′) + γV π ∗ (s′) ]
(59)
> pπ∗(s̄ = s ′ ir | s0 = sir)Pπ
∗
sir,s′ir
[ R(s′ir) + γV π∗(s′ir) ]
+ ∑
s′∈SIR\s′ir
pπ∗(s̄ = s ′ | s0 = sir)Pπ
∗
sir,s′
[ R(s′) + γV π ∗ (s′) ]
(60)
= ∑
s′∈SIR pπ∗(s̄ = s
′ | s0 = sir)Pπ ∗
sir,s′
[ R(s′) + γV π ∗ (s′) ]
(61)
= V ∗(sir), (62) where Eq. (59) holds from the mild-stochasticity (1) and mild-stochasticity (2) assumption, and Ineq. (60) holds because P π̂sir,s′ir > P π∗ sir,s′ir and R(s′) + γV π ∗ (s′) > 0 from the non-negative optimal value assumption (See Section 2). Finally, this is a contradiction since the optimal value function V ∗(s) should be the maximum.

heading: H EXTENDED RELATED WORKS
text: Approximate state abstraction. The approximate state abstraction approaches investigate partitioning an 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 use 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 as a metric. Abel et 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-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-path constraint can be seen as a 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 a set of shortest-path policies (See Definition 5 for definition) between initial and rewarding states. It can be seen as a 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.

Review summaries:
This 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.

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.