Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks

Sungryull Sohnequal,umich,lg
Sungtae Leeequal,yonsei
Jongwook Choiumich
Harm van Seijenms
Mehdi Fatemims
Honglak Leelg,umich

umichUniversity of Michigan
yonseiYonsei University
msMicrosoft Research
lgLG AI Research
Sungryull<EMAIL_ADDRESS>Deep Reinforcement Learning, ICML

We propose the $k$-Shortest-Path () 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  constraint. Notably, the  constraint prevents the policy from exploring state-action pairs along the non- trajectories (, going back and forth). However, in practice, excluding state-action pairs may hinder the 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 demonstrates 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 , , , and  show that the proposed method significantly improves proximal policy optimization (PPO) and outperforms existing novelty-seeking exploration methods including count-based exploration even in continuous control tasks, indicating that it improves the sample efficiency by preventing the agent from taking redundant actions. [The code is available on https://github.com/srsohn/shortest-path-rl]

§ INTRODUCTION

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 the 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 (, 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 the 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 a 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 the sparse reward problem, 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., 2018, Choi et al., 2018, Burda et al., 2018].
However, when such an intrinsic bonus is added to the reward, it often requires a careful balancing between environment reward and bonus and scheduling of the bonus scale to guarantee the convergence to an optimal solution.

The $k$-SP constraint improves the sample efficiency of
RL methods in sparse-reward tasks by pruning out suboptimal trajectories from the trajectory space.
Intuitively, the $k$-SP constraint means that when a policy rolls out into trajectories, all of the sub-paths of length $k$ is the shortest path (under a distance metric defined in terms of policy, discount factor, and transition probability; see
for the formal definition).
(Left) MDP and a rollout tree are given.
(Middle) The paths that satisfy the $k$-SP constraint. The number of admissible trajectories is drastically reduced.
(Right) A path rolled out by a policy satisfies the $k$-SP constraint if all sub-paths of length $k$ are shortest paths and have not received a non-zero reward. We use a reachability network to test if a given (sub-)path is the shortest path (See <Ref> for details).

To tackle the 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 <Ref>).
Of note, though our framework will be formulated for policy-based methods,
our final form of the cost function (<Ref> in <Ref>) applies to both policy-based and value-based methods.
We propose a novel $k$-shortest-path
() constraint (<Ref>) that improves the sample efficiency of policy learning (See <Ref>).
The  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 $\pi$-distance metric which we define in <Ref>.
We prove that applying our constraint preserves the optimality for any MDP (<Ref>), 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., 2018] (RNet) to efficiently learn the cost function in an off-policy manner.

We summarize our contributions as the following:
We propose a novel constraint that can improve the sample efficiency of any model-free RL method in sparse reward tasks.
We present several theoretical results including the proof that our proposed constraint preserves the optimal policy of given MDP.
We present a numerical result in tabular RL setting to precisely evaluate the effectiveness of the proposed method.
We propose a practical way to implement our proposed constraint and demonstrate that it provides a significant improvement on four complex deep RL domains.
We demonstrate that our method significantly improves the sample efficiency of PPO, and outperforms existing novelty-seeking methods on four complex domains in sparse reward settings.

§ PRELIMINARIES

Markov Decision Process (MDP).
We model a task as an MDP tuple $\mathcal{M}=(\mc{S},\mc{A},\mc{P},\mc{R},\rho ,\gamma)$, where  $\mc{S}$ is a state set, $\mc{A}$ is an action set, $\mc{P}$ is a transition probability, $\mc{R}$ is a reward function, $\rho$ is an initial state distribution, and $\gamma \in [0,1)$ is a discount factor.
For each state $s$, the value of a policy $\pi$ is denoted by $V^{\pi}(s)=\mbb{E}^{\pi}{ \left[ \sum_{t} \gamma^t r_t \mid s_0 = s \right] }.$
Then, the goal is to find the optimal policy $\pi^*$ that maximizes the expected return:

\begin{align}
\pi^*
&=\argmax_{\pi} \mbb{E}^{\pi}_{s\sim\rho}{ \Big[ \textstyle\sum_{t} \gamma^t r_t \mid s_0 = s \Big] }\\
&= \argmax_{\pi} \mbb{E}_{s\sim\rho}\left[ V^\pi(s) \right].
\end{align}

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 function $C(\pi)$ that maps a policy to a scalar, and a threshold $\alpha\in\mbb{R}$.
The objective of CMDP is to maximize the expected return $R(\tau) = \sum_t \gamma^t r_t$ of a trajectory $\tau=\{s_0, a_0, r_1, s_1, a_1, r_2, s_2, \ldots \}$ subject to a constraint:
$ %
\pi^{*} =\textstyle\argmax_{\pi} \mbb{E}_{\tau\sim\pi}\left[ R(\tau) \right],\text{ s.t. }C(\pi) \leq \alpha.
A popular choice of constraint is based on the transition cost function [Tessler et al., 2019] $c(s, a, r, s')\in\mbb{R}$ which assigns a scalar-valued cost to each transition. Then the constraint function for a policy $\pi$ is defined as the discounted sum of the cost under the policy:
$ %
C(\pi) = \mbb{E}_{\tau\sim\pi}\left[ \textstyle\sum_t \gamma^t c(s_t, a_t, r_{t+1}, s_{t+1})\right].
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 <Ref> and <ref>).

§ FORMULATION: $K$-SHORTEST-PATH CONSTRAINT

We define the $k$-shortest-path (k-SP) constraint to remove redundant transitions (, 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)+\gamma V^*(s) > 0$ for all initial states $s \ s.t \ \rho(s) > 0$ and all rewarding states that optimal policy visits with non-zero probability $s\in \{s| r(s)\neq 0 , p_{\pi^*}(s)>0\}$ where $p_{\pi}(s)$ is a probability of visiting state $s$ with policy $\pi$.
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” (, 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 the reward function by a constant $-\lvert \min_{s\in\{s| p_{\pi^*}(s)\}} V^*(s)\rvert$ for every transition, assuming the policy is proper
[It is an instance of potential-based reward shaping which has optimality guarantee [Ng et al., 1999].].
Goal-conditioned RL [Nachum et al., 2018], most of the well-known domains such as Atari [Bellemare et al., 2013],  [Beattie et al., 2016],  [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 <Ref> for details).

§.§ Shortest-path Policy and Shortest-path Constraint

Let $\tau$ be a path defined by a sequence of states: $\tau = \{s_0,\ldots,s_{\ell(\tau)}\}$,
where $\ell(\tau)$ is the length of a path $\tau$ (, $\ell(\tau) = |\tau| - 1$).
We denote the set of all paths from $s$ to $s'$ by $\mathcal{T}_{s,s'}$.
A path $\tau^*$ from $s$ to $s'$ is called a shortest path from $s$ to $s'$ if $\ell(\tau^*)$ is minimum,
, $\ell(\tau^*) = \smash{\min_{\tau \in \mathcal{T}_{s,s'}} \ell(\tau)}$.

Now we will define similar concepts (length, shortest path, ) 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 $\pi$:

$\gpathsetpi=\{\tau \mid s_0=s, s_{\ell(\tau)}=s', p_\pi(\tau)>0, s_t\neq s'\text{ for }\forall t<\ell(\tau) \}$.
That is,
$\gpathsetpi$ is a set of all paths that policy $\pi$ may roll out
from $s$ and terminate once visiting $s'$.

If the MDP is a single-goal task, , there exists a unique (rewarding) goal state $s_g \in \mathcal{S}$
such that $s_g$ is a terminal state, and $R(s) > 0$ if and only if $s = s_g$,
any shortest path from an initial state to the goal state is the optimal path with the highest return $R(\tau)$,
and a policy that always rolls out a shortest path from an initial state to the goal state is therefore optimal (see <Ref>).[
We refer the readers to <Ref> for more detailed discussion and proofs for single-goal MDPs.  ]
This is because all states except for $s_g$ are non-rewarding states,
but in general MDPs this is not necessarily true.
However, this motivates us to limit the domain of the shortest path to
non-rewarding states.
We define non-rewarding paths from $s$ to $s'$ as follows:

$\pathsetpi=\{\tau \mid \tau \in\gpathsetpi, r_{t}=0\text{ for  }\forall t<\ell(\tau) \}$.

In words, $\smash{\pathsetpi}$ is a set of all non-rewarding paths from $s$ to $s'$
rolled out by policy $\pi$ (, $\tau\in\smash{\gpathsetpi}$) without any associated reward except the last step (, $r_{t}=0\text{ for  }\forall t<\ell(\tau) $).
Now we are ready to define a notion of length with respect to a policy
and shortest path policy:

$\distpi=\log_\gamma \big(
\mathbb{E}_{\tau \sim \pi :~ \tau \in \pathsetpi} \left[ \gamma^{\ell(\tau)} \right]
\big)$

We define $\pi$-distance to be the log-mean-exponential of the length $\ell(\tau)$ of non-rewarding paths
$\tau \in \smash{\pathsetpi}$. To be thorough, $pi$-distance is not a "distance" but a quasi-metric since by definition, $pi$-distance is asymmetric.
When there exists no admissible path from $s$ to $s'$ under policy $\pi$,
the path length is defined to be $\infty$: $\smash{\distpi}=\infty$ if $\smash{\pathsetpi} = \emptyset$.
We note that when both MDP and policy are deterministic, $D^\pi(s, s')$ recovers
the natural definition of path length, $\distpi = \ell(\tau)$.

We call a policy a shortest-path policy from $s$ to $s'$ if it rolls out a path with the smallest $\pi$-distance:

$\pi \in \Pispss=\{\pi \in \Pi  \mid \distpi=\dist \}$.

Finally, we will define the shortest-path (SP) constraint.
Let $\nrstate=\{s \mid R(s)>0\text{ or }\rho(s)>0 \}$ be the union of all initial and rewarding states, and  $\smash{\nrstatepair=\{(s, s') \mid s, s' \in \nrstate, \rho(s)>0, \pathsetpi\neq\emptyset\}}$ be the subset of $\smash{\nrstate}$ such that agent may roll out.
Then, the SP constraint is applied to the non-rewarding sub-paths between states in $\nrstatepair$: $\pathsetpiphi=\bigcup_{(s, s')\in\nrstatepair}{\pathsetpi}$.
We note that these definitions are used in the proofs (<Ref>).
Now, we define the shortest-path constraint as follows:

A policy $\pi$ satisfies the shortest-path (SP) constraint if
$\pi \in \Pisp$, where
\Pisp =
\{
\pi \mid \text{For all~} s, s'\in\pathsetpiphi,
\text{it holds~}
\pi\in\Pispss
\}.

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:

For any MDP, an optimal policy $\pi^*$ satisfies the shortest-path constraint: $\pi^*\in\Pisp$.

See Appendix <ref> for the proof.

§.§ Relaxation: $k$-shortest-path Constraint

Implementing the shortest-path constraint is, however, intractable since it requires a distance predictor $\dist$. 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 $\dist$ to a binary decision problem — is the state $s'$ reachable from $s$ within $k$ steps? — also known as $k$-reachability [Savinov et al., 2018].
The $k$-shortest path constraint is defined as follows:

A policy $\pi$ satisfies the $k$-shortest-path constraint if
$\pi \in \Piksp$, where

\begin{align}
\Piksp =
\{
\pi \mid &\text{For all~} s, s'\in\pathsetpiphi,  \distpi \leq k,\nonumber
\\
&\text{it holds~}
\pi\in\Pispss
\}.\label{def:ksp}
\end{align}

Note that the SP constraint (<Ref>) is relaxed by adding a condition $\distpi\leq k$.
In other words, the  constraint is imposed only for $s,s'$-path whose length is not greater than $k$.
From <Ref>, we can prove an important property and then <Ref> (optimality):

For an MDP $\mc{M}$, $\Pimsp\subset\Piksp$ if $k < m$.

It is true since $\{(s,s') \mid \distpi\leq k\} \subset \{(s,s') \mid \distpi\leq m\}$ for $k<m$.

For an MDP $\mc{M}$ and any $k\in\mbb{R}$, an optimal policy $\pi^*$ is a $k$-shortest-path policy.

<Ref> tells $\pi^* \in \Pisp$.
<Ref> tells $\Pisp = \Piinfsp$ and
<Ref> tells $\Piinfsp \subset \Piksp$.
Collectively, we have
$\pi^*   \in     \Pisp  =      \Piinfsp      \subset       \Piksp.$

In conclusion, <Ref> states that
the  constraint does not change the optimality of policy,
and <Ref> states a larger $k$ results in a larger reduction in policy search space.
Thus, it motivates us to apply the  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 <Ref>.

§ SHORTEST-PATH REINFORCEMENT LEARNING (SPRL)

An example observation of (a) ,
(b)  in , (c) the maze layout (not available to the agent) of , (d) in , and (e)  in .

In <Ref>, we defined our constraint and proved that it preserves the optimality. In this section, we derive how the constraint on policy can be estimated by the cost that can be computed from the agent's on-policy trajectory. The proposed intrinsic cost term can be subtracted from the extrinsic reward and optimized together via any model-free RL method.

$k$-shortest-path Cost.
The objective of RL with the  constraint $\Piksp$ can be written as:

\begin{align}
\pi^* &= \textstyle\argmax_{\pi} \mbb{E}^{\pi}\left[ R(\tau) \right],\ \  \text{s.t.}\ \ \pi\in\Piksp,\label{eq:ksp-problem}
\end{align}

$\Piksp = \{\pi \mid \forall (s, s'\in\pathsetpiphi),  \distpi \leq k, \text{it holds~}\pi\in\Pispss\}$ (<Ref>).
We want to formulate the constraint $\pi \in \Piksp$ in the form of constrained MDP (<Ref>),
, as $C(\pi) \le \alpha$.
We begin by re-writing the  constraint into a cost-based form:

\begin{align}
\hspace*{-5pt}
&\Piksp = \{\pi \mid \csp_k(\pi) = 0\}, \text{ where }\\
&\csp_k(\pi)=\sum_{(s,s'\in\pathsetpiphi):\distpi\leq k} \mbb{I}\left[ \dist < \distpi \right].
\label{eq:cost-form1}
\end{align}

Note that $\mbb{I}\left[ \dist < \distpi \right]=0 \leftrightarrow \dist = \distpi$ since $\dist\leq \distpi$ from <Ref>.
Similar to Tessler et al., 2019, we apply the constraint to the on-policy trajectory $\tau=(s_0, s_1, \ldots)$ with discounting by replacing $(s, s')$ with $(s_t, s_{t+l})$ where $[t, t+l]$ represents each segment of $\tau$ with length $l$:

\begin{align}
\csp_k(\pi)
&\simeq  \mbb{E}_{\tau\sim\pi} \left[ \csp_k(\tau) \right], \\
\csp_k(\tau)
&= \textstyle\sum_{(t, l): t\geq 0, l\leq k}~
\gamma^t
\cdot \left( \prod_{j=t}^{t+l-1}{\mathbb{I} \left[
r_j=0\right]} \right) \nonumber\\
&\qquad \cdot \mathbb{I} \left[ D_\nr(s_t, s_{t+l})< D^\pi_\nr(s_t, s_{t+l})  \right] \label{eq:csp-before}\\
\textstyle\sum_{(t, l): t\geq 0, l\leq k}~
\gamma^t
\cdot \left( \prod_{j=t}^{t+l-1}{\mathbb{I} \left[
r_j=0\right]} \right) \nonumber\\
&\qquad \cdot\mathbb{I} \left[
D_\nr(s_t, s_{t+l}) < k
\right]\label{eq:cmdp-derivation-cont}\\
&\triangleq \hatcsp_k(\pi),
\end{align}

where the Inequality. (<ref>) holds because $D^\pi_\nr(s_t, s_{t+l})=\log_\gamma\left( \mathbb{E}_{\tau \in \mathcal{T}_{s_t, s_{t+l},\nr}^{\pi} }\left[ \gamma^{|\tau|} \right]\right)<k$ from Jensen's inequality.
Note that it is sufficient to consider only the cases $l = k$
(because for $l < k$, given $D_\nr(s_t, s_{t+k}) < k$, we have $D(s_t, s_{t+l}) \le l < k$).
Then, we simplify $\hatcsp_k(\tau)$ as

\begin{align}
&\hatcsp_k(\tau) %
= \textstyle\sum_{t}
\gamma^t \mathbb{I} \left[D_\nr(s_t, s_{t+k}) < k \right] \prod_{j=t}^{t+k-1}{\mathbb{I} \left[
\gamma^t
\mathbb{I} [t \ge k]\mathbb{I} \left[
D_\nr(s_{t-k}, s_t) < k
\right] \prod_{j=t-k}^{t-1}{\mathbb{I} \left[
\label{eq:cmdp-derivation}
\end{align}

Finally, the per-time step cost $c_t$ is given as:

\begin{align}
c_t = \mathbb{I} [t \ge k]
\cdot \mathbb{I} \left[
D_\nr(s_{t-k}, s_t) < k
\right]
\cdot \prod_{j=t-k}^{t-1}{\mathbb{I} \left[
\label{eq:cost}
\end{align}

where $\hatcsp_k(\pi) = \mathbb{E}_{\tau \sim \pi}\left[ \sum_t \gamma^t c_t \right]$.
Note that $\hatcsp_k(\pi)$ is an upper bound of $\csp_k(\pi)$,
which will be minimized by the bound to make as little violation of the shortest-path constraint as possible.
Intuitively speaking, $c_t$ 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 <Ref>, $c_t$ 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 <Ref> for details). Thus, we did not stack the observation in all the experiments.
We use the Lagrange multiplier method to convert the objective (<ref>) into an equivalent unconstrained problem as follows:

\begin{align}
\min_{\lambda>0}\max_{\theta} L(\lambda, \theta) = \min_{\lambda>0}\max_{\theta}\mbb{E}_{\tau\sim\pi_{\theta}}\Big[ \textstyle\sum_t{\gamma^t \left( r_t - \lambda c_t\right)} \Big],   \label{eq:ksp-problem-3}
\end{align}

where $L$ is the Lagrangian, $\theta$ is the parameter of policy $\pi$, and $\lambda> 0$ is the Lagrangian multiplier. While in ordinary Lagrange multiplier method $\lambda$ is unique since Theorem <ref> shows that the shortest-path constraint preserves the optimality, we can control how much weight we will give to the constraint, i.e., we are free to set any $\lambda>0$.

Thus, we simply consider  $\lambda$ as a tunable positive hyperparameter, and  simplify the min-max problem (<ref>) to an RL objective with costs $c_t$ being added:

\begin{align}
\max_{\theta}\mbb{E}_{\tau\sim\pi_{\theta}}\Big[ \textstyle\sum_t{ \gamma^t \left( r_t - \lambda c_t\right)} \Big].\label{eq:ksp-problem-4}
\end{align}

Progress of average episode reward
on  tasks. We report the mean (solid curve) and standard error (shadowed area) of the performance over six random seeds.

Practical Implementation of the Cost Function.
We implement the binary distance discriminator $\mbb{I}( D_\nr(s_{t-k}, s_{t}) < k)$ in <Ref>
using the $k$-reachability network [Savinov et al., 2018]. The $k$-reachability network $\text{Rnet}_k(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:
\text{Rnet}_{k}(s, s') \simeq \mbb{I}\left( D_\nr(s,s') < k+1 \right).
We then estimate the cost term $c_t$ using $(k-1)$-reachability network as follows:

\begin{align}
&c_t= \mbb{I}\left[ D_\nr(s_{t-k},s_{t})< k\right] \mbb{I}\left[t\geq k\right]
\prod_{j=t-k}^{t-1}{\mathbb{I} \left[
&= \text{Rnet}_{k-1}(s_{t-k}, s_t)
\mbb{I}\left[t\geq k\right]
\prod_{j=t-k}^{t-1}{\mathbb{I} \left[
\vspace*{-5pt}
\end{align}

Intuitively speaking, if the agent takes a $k$-shortest path, then the distance between $s_{t-k}$ and $s_t$ is $k$, hence $c_t = 0$.
If it is not a $k$-shortest path, $c_t > 0$ since the distance between $s_{t-k}$ and $s_t$ will be less than $k$.
In practice, due to the error in the reachability network, we add a small tolerance $\Delta t\in\mbb{N}$ to ignore outliers.
It leads to an empirical version of the cost as follows:

\begin{align}
c_t \simeq & \text{Rnet}_{k-1}(s_{t-k-\Delta t}, s_t)\cdot \prod_{j=t-k-\Delta t}^{t-1}{\mathbb{I} \left[
r_j=0\right]} \nonumber\\
&\cdot \mbb{I}( t \geq k+\Delta t).
\label{eq:cost-tol}
\vspace*{-3pt}
\end{align}

In our experiment, we found that a small tolerance $\Delta t \simeq k/5$ works well in general.
Similar to Savinov et al., 2018, we used the following contrastive loss for training the reachability network:

\begin{align} %
\mathcal{L}_{\text{Rnet}} = &- \log\left(\text{Rnet}_{k-1}(s_{\text{anc}}, s_+) \right) \\
&- \log\left(1 - \text{Rnet}_{k-1}(s_{\text{anc}}, s_-) \right),
\label{eq:rnet-loss}
\end{align}

where $s_{\text{anc}}, s_+, s_-$ are the anchor, positive, and negative samples, respectively (See <Ref> for the detail of training).

§ RELATED WORK

Shortest-path Problem and Planning.
Many early works [Bellman, 1958, Ford Jr, 1956, Bertsekas & Tsitsiklis, 1991, Bertsekas & Tsitsiklis, 1995] have discussed (stochastic) shortest path problems in the context of MDP. They viewed the shortest path problem as a 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 a forward model for planning. Our method only exploits the optimality guarantee of the shortest-path under the $\pi$-distance to prune out sub-optimal policies (, non-shortest paths).

Distance Metric in Goal-conditioned RL.
In goal-conditioned RL, there has been a recent surge of interest in learning a distance metric in state (or goal) space 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 the highest success rate. SPTM [Savinov et al., 2018] defined a binary distance based on the reachability network (RNet) to connect nearby nodes in the graph.
However, the proposed distance metrics and methods can be used only for the goal-conditioned task and lack the theoretical guarantee in general MDP, while our theory and framework are applicable to general MDP (see <Ref>).

Reachability Network.
The reachability network (RNet) was first proposed by Savinov et al., 2018 as a way to measure the novelty of a state for exploration. Intuitively, if the current state is not reachable from previous states in episodic memory, it is considered to be novel.
SPTM [Savinov et al., 2018] used RNet to predict the local connectivity (, binary distance) between observations in memory for graph-based planning in a navigation task.
Zhang et al., 2020 used the k-adjacency network, which is analogous to the RNet, to improve the subgoal generation of hierarchical reinforcement learning (HRL) by constraining the goal space into adjacent states from the current state.
On the other hand, we use RNet for constraining the policy (, removing the sub-optimal policies from policy space). Thus, in ours and the other three compared works, RNet is being employed for fundamentally different purposes.

Sparse Reward Problem.
One of the most famous approaches to tackle the sparse reward problem in RL is intrinsic motivation [Bellemare et al., 2016, Pathak et al., 2017, Savinov et al., 2018, Burda et al., 2018]. By adding intrinsic reward, they aim to transform the original sparse reward problem into a dense reward problem. Bellemare et al., 2016 is one of the pioneer works that formulated the intrinsic reward based on the pseudo count of state visitation to measure the state novelty. Pathak et al., 2017, Burda et al., 2018 designed an intrinsic reward using prediction error. Savinov et al., 2018 defined the intrinsic reward based on whether the current state is “reachable” from the previously visited states, where the reachability between a pair of states is predicted by a neural network that is trained via temporal contrastive learning.
Florensa et al., 2017 created a curriculum based on the starting positions in training to tackle the sparse reward problem. The positions near the goal are considered easy and the positions far from the goal are considered hard.  Riedmiller et al., 2018 formed the sparse reward problem into multiple low-level tasks. After designing an auxiliary reward function and learning a policy for every task, they learned a high-level policy that decides the sequence of low-level policies. Ecoffet et al., 2019 proposed to learn a policy that can go back to previously visited states, such that the agent can perform a directed exploration around the promising state. Our  is not concerned with measuring the state novelty but aims to shrink the policy search space to improve the sample efficiency of RL algorithms. The exploration is promoted as a byproduct of the reduced policy search space.

More Related Works.
Please refer to <Ref> for further discussions about other related works.

§ EXPERIMENTS

Progress of average episode reward
on  tasks. We report the mean (solid curve) and standard error (shadowed area) of the performance over four random seeds.

Progress of average episode reward
on tasks. We report the mean (solid curve) and standard error (shadowed area) of the performance over four random seeds. The performances of PPO and ICM in are both zero, hence invisible in the figure.

Progress of average episode reward on  tasks. We report the mean (solid curve) and standard error (shadowed area) of the performance over four random seeds.

§.§ Settings

We evaluate our  on four challenging domains:  [Chevalier-Boisvert et al., 2018],  [Beattie et al., 2016],  [Bellemare et al., 2013], and  [Plappert et al., 2018].
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 (, key-door) are considered.
We conducted experiments on four standard tasks: , , , and .
is a 3D environment with a 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: , [ task corresponds to the Sparse task in Savinov et al., 2018, and our <Ref> reproduces the result reported.]
, and .
For , among 52 games we chose two sparse-reward tasks (, ), one dense-reward task (), and three non-navigational tasks (, , ) where the agent receives reward by hitting the enemy by firing a bullet or removing the obstacle by installing a bomb.
is a continuous control environment with a two-fingered gripper. Initial locations of the agent and the goal change every episode. We made two changes in the environment to make it a sparse-reward task.
The agent receives +1 reward if the agent reaches the goal and 0 rewards otherwise. Also, the episode terminates when the agent reaches the goal such that the agent can receive a non-zero reward at most once in an episode.
We conducted experiments on all four tasks: , , , . We refer the readers to <Ref> for examples of observations. See <Ref>, <Ref>, <Ref>, and  <Ref>
for more details of , , , and  respectively.

We compared our methods with four baselines:  [Schulman et al., 2017], episodic curiosity () [Savinov et al., 2018], intrinsic curiosity module () [Pathak et al., 2017], and  [Savinov et al., 2018].
The  is used as a baseline RL algorithm for all other agents.
The  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., 2018, we trained RNet in an off-policy manner from the agent's experience and used it for our  and  on    (<Ref>),  (<Ref>),  (<Ref>) and  (<Ref>). For the accuracy of the learned RNet on each task, please refer to <Ref>.
The  agent has access to the agent's ($x$, $y$) coordinates. It uniformly divides the world into 2D grid cells, and the agent is rewarded for visiting a novel grid cell.
The  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., 2018]
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.

§.§ Results on

<Ref> shows the performance of all the methods on the  domain.
consistently outperforms all the baseline methods over all tasks.
We observe that exploration-based methods (, , , and ) perform similarly to the  in the tasks with small state space (,  and ).
However,  demonstrates a significant performance gain since it improves the exploitation by avoiding sub-optimality caused by taking a non-shortest-path.

§.§ Results on

<Ref> shows the performance of all the methods on  tasks.
Overall,  achieves superior results compared to other methods.
By the task design, the difficulty of exploration increases in the order of , , and  tasks, and we observe a coherent trend in the result.
For harder exploration tasks, the exploration-based methods (,  and ) achieve a larger improvement over : , 20%, 50%, and 100% improvement in , , and , respectively.
As shown in <Ref>,  is expected to have larger improvement for larger trajectory space and sparser reward settings.
We can verify this from the result:  has the largest improvement in  task, where both the map is largest and the reward is most sparse. Interestingly,  even outperforms  which simulates the upper-bound performance of novelty-seeking exploration method. This is possible since  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.

(Left) 7$\times$7 Tabular four-rooms domain with initial agent location (red) and the goal location (green). (Right) The trajectory space reduction ratio (%) before and after constraining the trajectory space for various $k$ and $\Delta t$ with  constraint. Even a small $k$ can greatly reduce the trajectory space with a reasonable tolerance $\Delta t$.

0.16(d) +Reward

Transition count maps for baselines and :
(a), (b), and (c) are in a reward-free
while (d) is in a reward-aware setting.
In reward-free settings (a-c), we show rewarding states in light green only for the visualization, but the agent does not receive rewards from the environment.
The location of the agent's initial state (orange) and rewarding states (dark green) are fixed.
The episode length is limited to 500 steps.

§.§ Results on

One of the main challenges in is the distribution shift in the state space within a task.
Unlike  and , many tasks involve the transition between different rooms in each of which the agent observes a significantly different set of states.
This induces instability in the RNet training; RNet often overfits to the initial room and performs poorly when the agent navigates to the different rooms.
To mitigate this problem, we added the weight decay for the RNet training.
For other technical details, please refer to <Ref>.

<Ref> summarizes the performance of all the methods on tasks.
outperforms all the baseline methods on five out of six tasks except for , which is a dense reward task. We note that other exploration methods,   and , also perform poorly on this task.
For the sparse reward task, especially in ,  achieves the performance comparable to the SOTA exploration methods such as RND [Burda et al., 2018] (1000 score at 50M steps with 32 parallel environments.  used 12 parallel environments.) and SOTA exploitation methods such as  SIL [Oh et al., 2018] (2500 score at 50M steps). Lastly,  achieves the largest improvement to the  in non-navigational tasks (, , ). This verifies that our  constraint is not limited to just the geometric path but can be applied to any general trajectory, or a sequence of state transitions, in MDP.

§.§ Results on

<Ref> summarizes the performance of all the methods on tasks.
outperforms all the baseline methods on every task except for , in which all the compared methods perform similarly well.
We also found that the performance improvement of the exploration methods such as , , and  over  is larger for the tasks with sparser reward; the reward is the densest in  while the most sparse in .
As suggested by our theory, this result shows that  is not restricted to the domains with discrete action space but performs well on the continuous control domain.
We present the additional results in <Ref> showing that the reachability network, which is the key component of , can be efficiently trained and accurately compute the state proximity in the continuous control domain.

§.§ Quantitative Analysis on $k$-SP Constraint

In this section, we numerically evaluate the effect of our $k$-shortest path constraint in a tabular-RL setting. Specifically, we study the following questions:
(1) Does the  constraint with larger $k$ results in more reduction in trajectory space? (, validation of <Ref>)
(2) How much reduction in trajectory space does  constraint provide with different $k$ and tolerance $\Delta t$?

We implemented a simple tabular 7x7 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 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.

<Ref> 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 of trajectories satisfying our  constraint with varying parameters $k$ and tolerance $\Delta t$ and divided by the total number of trajectories (, $4^{14}=268$M).
The result shows that our  constraint drastically reduces the trajectory space even in a simple 2D grid domain; with a very small $k=3$ and no tolerance $\Delta t=2$, we get only $24/268$M size of the original search space.
As we increase $k$, we can see more reduction in the trajectory space, which is consistent with <Ref>.
Also, increasing the tolerance $\Delta t$ slightly hurts the performance, but still achieves a large reduction (See <Ref> for more analysis on the effect of $k$ and tolerance).

§.§ Qualitative Analysis on

We qualitatively studied what type of policy is learned with the  constraint with the ground-truth RNet in NineRooms domain of .
<Ref> (a-c) shows the converged behavior of  ($k=15$), the ground-truth count-based exploration [Lai & Robbins, 1985] agent (), and uniformly random policy () in a reward-free setting.
We counted all the state transitions ($s_t\rightarrow s_{t+1}$) of each agent's roll-out and averaged over 4 random seeds.
cannot explore further than the initial few rooms.  seeks novel states and visits all the states uniformly.  learns to take the longest possible shortest path, which results in a “straight” path across the rooms.
Note that this only represents a partial behavior of , since our cost also considers the existence of non-zero reward (see <Ref>). Thus, in (d), we tested  while providing only the existence of non-zero reward (but not the reward magnitude).  learns to take the shortest path between rewarding and initial states that is consistent with the shortest-path definition in <Ref>.

§ 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 transitions. We empirically showed that  outperforms vanilla RL and strong novelty-seeking exploration baselines on four 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 an  interesting future work that could benefit many practical tasks.

This research is supported in part by NSF IIS #1453651 and Korea Foundation for Advanced Studies.

[Abel et al., 2016]
Abel, D., Hershkowitz, D., and Littman, M.
Near optimal behavior via approximate state abstraction.
In International Conference on Machine Learning, pp.  2915–2923, 2016.

[Abel et al., 2018]
Abel, D., Arumugam, D., Lehnert, L., and Littman, M.
State abstractions for lifelong reinforcement learning.
In International Conference on Machine Learning, pp.  10–19,

[Altman, 1999]
Altman, E.
Constrained Markov decision processes, volume 7.
CRC Press, 1999.

[Beattie et al., 2016]
Beattie, C., Leibo, J. Z., Teplyashin, D., Ward, T., Wainwright, M.,
Küttler, H., Lefrancq, A., Green, S., Valdés, V., Sadik, A., et al.
Deepmind lab.
arXiv preprint arXiv:1612.03801, 2016.

[Bellemare et al., 2013]
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M.
The arcade learning environment: An evaluation platform for general
Journal of Artificial Intelligence Research, 47:0
253–279, 2013.

[Bellemare et al., 2016]
Bellemare, M. G., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and
Munos, R.
Unifying count-based exploration and intrinsic motivation.
arXiv preprint arXiv:1606.01868, 2016.

[Bellman, 1958]
Bellman, R.
On a routing problem.
Quarterly of applied mathematics, 160 (1):0
87–90, 1958.

[Bertsekas & Tsitsiklis, 1991]
Bertsekas, D. P. and Tsitsiklis, J. N.
An analysis of stochastic shortest path problems.
Mathematics of Operations Research, 160 (3):0
580–595, 1991.

[Bertsekas & Tsitsiklis, 1995]
Bertsekas, D. P. and Tsitsiklis, J. N.
Neuro-dynamic programming: an overview.
In Proceedings of 1995 34th IEEE Conference on Decision and
Control, volume 1, pp.  560–564. IEEE, 1995.

[Bertsekas et al., 1988]
Bertsekas, D. P., Castanon, D. A., et al.
Adaptive aggregation methods for infinite horizon dynamic

[Burda et al., 2018]
Burda, Y., Edwards, H., Pathak, D., Storkey, A., Darrell, T., and Efros, A. A.
Large-scale study of curiosity-driven learning.
arXiv preprint arXiv:1808.04355, 2018a.

[Burda et al., 2018]
Burda, Y., Edwards, H., Storkey, A., and Klimov, O.
Exploration by random network distillation.
arXiv preprint arXiv:1810.12894, 2018b.

[Castro, 2019]
Castro, P. S.
Scalable methods for computing state similarity in deterministic
markov decision processes.
arXiv preprint arXiv:1911.09291, 2019.

[Chevalier-Boisvert et al., 2018]
Chevalier-Boisvert, M., Willems, L., and Pal, S.
Minimalistic gridworld environment for openai gym.
<https://github.com/maximecb/gym-minigrid>, 2018.

[Choi et al., 2018]
Choi, J., Guo, Y., Moczulski, M., Oh, J., Wu, N., Norouzi, M., and Lee, H.
Contingency-aware exploration in reinforcement learning.
arXiv preprint arXiv:1811.01483, 2018.

[Coulom, 2006]
Coulom, R.
Efficient selectivity and backup operators in monte-carlo tree
In International conference on computers and games, pp.  72–83. Springer, 2006.

[Dean et al., 2013]
Dean, T. L., Givan, R., and Leach, S.
Model reduction techniques for computing approximately optimal
solutions for markov decision processes.
arXiv preprint arXiv:1302.1533, 2013.

[Dhariwal et al., 2017]
Dhariwal, P., Hesse, C., Klimov, O., Nichol, A., Plappert, M., Radford, A.,
Schulman, J., Sidor, S., Wu, Y., and Zhokhov, P.
Openai baselines.
<https://github.com/openai/baselines>, 2017.

[Ecoffet et al., 2019]
Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K. O., and Clune, J.
Go-explore: a new approach for hard-exploration problems.
arXiv preprint arXiv:1901.10995, 2019.

[Espeholt et al., 2018]
Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron,
Y., Firoiu, V., Harley, T., Dunning, I., et al.
Impala: Scalable distributed deep-rl with importance weighted
actor-learner architectures.
arXiv preprint arXiv:1802.01561, 2018.

[Ferns et al., 2004]
Ferns, N., Panangaden, P., and Precup, D.
Metrics for finite markov decision processes.
In UAI, volume 4, pp.  162–169, 2004.

[Florensa et al., 2017]
Florensa, C., Held, D., Wulfmeier, M., Zhang, M., and Abbeel, P.
Reverse curriculum generation for reinforcement learning.
In Conference on robot learning, pp.  482–495. PMLR, 2017.

[Ford Jr, 1956]
Ford Jr, L. R.
Network flow theory.
Technical report, Rand Corp Santa Monica Ca, 1956.

[Givan et al., 2003]
Givan, R., Dean, T., and Greig, M.
Equivalence notions and model minimization in markov decision
Artificial Intelligence, 1470 (1-2):0
163–223, 2003.

[Guo et al., 2016]
Guo, X., Singh, S., Lewis, R., and Lee, H.
Deep learning for reward design to improve monte carlo tree search in
atari games.
arXiv preprint arXiv:1604.07095, 2016.

[He et al., 2016]
He, K., Zhang, X., Ren, S., and Sun, J.
Deep residual learning for image recognition.
In Proceedings of the IEEE conference on computer vision and
pattern recognition, pp.  770–778, 2016.

[Higgins et al., 2017]
Higgins, I., Pal, A., Rusu, A., Matthey, L., Burgess, C., Pritzel, A.,
Botvinick, M., Blundell, C., and Lerchner, A.
Darla: Improving zero-shot transfer in reinforcement learning.
In Proceedings of the 34th International Conference on Machine
Learning-Volume 70, pp.  1480–1490. JMLR. org, 2017.

[Huang et al., 2019]
Huang, Z., Liu, F., and Su, H.
Mapping state space using landmarks for universal goal reaching.
In Advances in Neural Information Processing Systems, pp.  1940–1950, 2019.

[Kakade et al., 2003]
Kakade, S. M. et al.
On the sample complexity of reinforcement learning.
PhD thesis, University of London London, England, 2003.

[Khetarpal & Precup, 2018]
Khetarpal, K. and Precup, D.
Attend before you act: Leveraging human visual attention for
continual learning.
arXiv preprint arXiv:1807.09664, 2018.

[Kingma & Ba, 2014]
Kingma, D. P. and Ba, J.
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980, 2014.

[Lai & Robbins, 1985]
Lai, T. L. and Robbins, H.
Asymptotically efficient adaptive allocation rules.
Advances in applied mathematics, 60 (1):0
4–22, 1985.

[Laskin et al., 2020]
Laskin, M., Emmons, S., Jain, A., Kurutach, T., Abbeel, P., and Pathak, D.
Sparse graphical memory for robust planning.
arXiv preprint arXiv:2003.06417, 2020.

[Li et al., 2006]
Li, L., Walsh, T. J., and Littman, M. L.
Towards a unified theory of state abstraction for mdps.
In ISAIM, 2006.

[Mnih et al., 2015]
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare,
M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.
Human-level control through deep reinforcement learning.
Nature, 5180 (7540):0 529–533, 2015.

[Nachum et al., 2018]
Nachum, O., Gu, S. S., Lee, H., and Levine, S.
Data-efficient hierarchical reinforcement learning.
In Advances in Neural Information Processing Systems, pp.  3303–3313, 2018.

[Ng et al., 1999]
Ng, A. Y., Harada, D., and Russell, S.
Policy invariance under reward transformations: Theory and
application to reward shaping.
In ICML, volume 99, pp.  278–287, 1999.

[Norvig, 2002]
Norvig, P. R.
Artificial Intelligence: A Modern Approach.
Prentice Hall, 2002.

[Oh et al., 2018]
Oh, J., Guo, Y., Singh, S., and Lee, H.
Self-imitation learning.
In International Conference on Machine Learning, pp.  3878–3887. PMLR, 2018.

[Oudeyer & Kaplan, 2009]
Oudeyer, P.-Y. and Kaplan, F.
What is intrinsic motivation? a typology of computational approaches.
Frontiers in neurorobotics, 1:0 6, 2009.

[Pathak et al., 2017]
Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T.
Curiosity-driven exploration by self-supervised prediction.
In Proceedings of the 34th International Conference on Machine
Learning-Volume 70, pp.  2778–2787. JMLR. org, 2017.

[Plappert et al., 2018]
Plappert, M., Andrychowicz, M., Ray, A., McGrew, B., Baker, B., Powell, G.,
Schneider, J., Tobin, J., Chociej, M., Welinder, P., et al.
Multi-goal reinforcement learning: Challenging robotics environments
and request for research.
arXiv preprint arXiv:1802.09464, 2018.

[Riedmiller et al., 2018]
Riedmiller, M., Hafner, R., Lampe, T., Neunert, M., Degrave, J., Wiele, T.,
Mnih, V., Heess, N., and Springenberg, J. T.
Learning by playing solving sparse reward tasks from scratch.
In International Conference on Machine Learning, pp.  4344–4353. PMLR, 2018.

[Savinov et al., 2018]
Savinov, N., Dosovitskiy, A., and Koltun, V.
Semi-parametric topological memory for navigation.
arXiv preprint arXiv:1803.00653, 2018a.

[Savinov et al., 2018]
Savinov, N., Raichuk, A., Marinier, R., Vincent, D., Pollefeys, M., Lillicrap,
T., and Gelly, S.
Episodic curiosity through reachability.
ICLR, 2018b.

[Schaul et al., 2015]
Schaul, T., Horgan, D., Gregor, K., and Silver, D.
Universal value function approximators.
In International conference on machine learning, pp.  1312–1320, 2015.

[Schmidhuber, 1991]
Schmidhuber, J.
Adaptive confidence and adaptive curiosity.
In Institut fur Informatik, Technische Universitat Munchen,
Arcisstr. 21, 800 Munchen 2. Citeseer, 1991.

[Schulman et al., 2017]
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.
Proximal policy optimization algorithms.
arXiv preprint arXiv:1707.06347, 2017.

[Shang et al., 2016]
Shang, W., Sohn, K., Almeida, D., and Lee, H.
Understanding and improving convolutional neural networks via
concatenated rectified linear units.
In international conference on machine learning, pp.  2217–2225, 2016.

[Silver et al., 2017]
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez,
A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al.
Mastering the game of go without human knowledge.
Nature, 5500 (7676):0 354–359, 2017.

[Sutton, 1998]
Sutton, R. S.
Between mdps and semi-mdps: Learning, planning, and representing
knowledge at multiple temporal scales.

[Sutton & Barto, 2018]
Sutton, R. S. and Barto, A. G.
Reinforcement learning: An introduction.
MIT press, 2018.

[Tessler et al., 2019]
Tessler, C., Mankowitz, D. J., and Mannor, S.
Reward constrained policy optimization.
ICLR, 2019.

[Vezhnevets et al., 2017]
Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver,
D., and Kavukcuoglu, K.
Feudal networks for hierarchical reinforcement learning.
In Proceedings of the 34th International Conference on Machine
Learning-Volume 70, pp.  3540–3549. JMLR. org, 2017.

[Vinyals et al., 2019]
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung,
J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al.
Grandmaster level in starcraft ii using multi-agent reinforcement
Nature, 5750 (7782):0 350–354, 2019.

[Vodopivec et al., 2017]
Vodopivec, T., Samothrakis, S., and Ster, B.
On monte carlo tree search and reinforcement learning.
Journal of Artificial Intelligence Research, 60:0
881–936, 2017.

[Zhang et al., 2018]
Zhang, A., Lerer, A., Sukhbaatar, S., Fergus, R., and Szlam, A.
Composable planning with attributes.
ICML, 2018.

[Zhang et al., 2020]
Zhang, T., Guo, S., Tan, T., Hu, X., and Chen, F.
Generating adjacency-constrained subgoals in hierarchical
reinforcement learning.
arXiv preprint arXiv:2006.11485, 2020.

Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks

§ MORE ABLATION STUDY

Average episode reward of  with varying $k=$1, 3, 10, 30 as a function of environment steps for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. The best performance is obtained with $k=10$.

Average episode reward of  with varying $k=$3, 5, 7 as a function of environment steps for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. The best performance is obtained with $k=5$.

§.§ Effect of $k$

As proven in Lemma <ref> and shown in <Ref>, the larger $k$, the $k$-shortest constraint promises a larger reduction in policy space, which results in faster learning. However, with our practical implementation of  with a learned (imperfect) reachability network, overly large $k$ has a 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 (, almost always penalized). Figure <ref> and <ref> shows the performance of  on  and  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 (, $k=10$ for  and $k=5$ for ). In practice, we performed grid-search over the hyper-parameter $k$.

Training multiple reachability networks with different $k$'s may achieve the advantages of both low and high $k$. But practically, training multiple reachability networks requires high computational cost and more extensive hyperparameter search, which can be intractable. Thus, we instead tried the curriculum learning of $k$; , starting from low $k$ and gradually increasing it up to the target $k$. However, we found that curriculum learning makes the training of the reachability network unstable when $k$ changes which results in lower performance.

Average episode reward of  with varying $\Delta t=$1, 2, 3, 5 as a function of environment steps for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. The best performance is obtained with $\Delta t=1$.

Average episode reward of  with varying $\Delta t=$10, 15, 25, 50 as a function of environment steps for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. The best performance is obtained with $\Delta t=25$.

§.§ Effect of tolerance $\Delta t$

Adding the tolerance $\Delta t$ to our  constraint makes it “softer” by allowing $\Delta t$-steps of redundancy in transition (See <Ref>). Intuitively, a small tolerance may improve the stability of RNet by incorporating a possible noise in RNet prediction, but a very large tolerance will make it less effective in removing sub-optimality in transition.
Figure <ref> and <ref> show the performance of  on  and  domains with varying tolerance $\Delta t$. Similar to $k$, we can see that there exists a “sweet spot” that balances between the reduction in policy space and stabilization of noisy RNet output (, $\Delta t=25$) in .
Note that the best tolerance values for  and  are vastly different. This is mainly because we used multiple tolerance sampling (See <Ref>) for  but not for . Since the multiple tolerance sampling also improves the stability of RNet, larger tolerance has less benefit compared to its disadvantage.

Average episode reward of  with varying observation stacking dimension of 0, 1, 5, 10 as a function of environment steps for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. The best performance is obtained without stacking (, #stack=0).

Average episode reward of  with varying observation stacking dimension of 0, 1, 5 as a function of environment steps for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. The best performance is obtained without stacking (, #stack=0)

§.§ Stacking observation

The CMDP with  constraint becomes the $(k+1)$-th order MDP as shown in <Ref>. Thus, in theory, the policy should take current state $s_t$ augmented by stacking the $k$ previous states as input: $[s_{t-k}, s_{t-k+1}\ldots, s_t]$, where $[\cdot]$ is a stacking of the pixel observation along the channel (, color) dimension. However, stacking the observation may not lead to the best empirical results in practice.
Figure <ref> and <ref> show the performance of  on  and  domains with varying stacking dimensions. For stack=$m$, we stacked the observation from $t-m$ to $t$: $[s_{t-m}, s_{t-m+1}, \ldots, s_t]$. We experimented up to $m=k$: up to $m=10$ for  and $m=5$ for . The result shows that stacking the observation does not necessarily improve the performance for MDP order greater than 1, which is often observed when the function approximation is used (, Savinov et al., 2018). Thus, we did not augment the observation in all the experiments.

Average episode reward of  with varying sparsity controlled by substep $N=2, 3, 4, 6$ for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. As sparsity grows, the difference between  and the baselines increase accordingly.

§.§ Effect of Sparsity of the reward

We evaluated  on with a smaller “substep” (, the number of action repetitions) $\substep$ to make the reward sparser, while keeping the episode length $\times$ substep the same to ensure the task is solvable within the episode length.
The default $\substep$ is 20, and we used $\substep=2,3,4,6$. <Ref> summarizes the experiment result on varying sparsity of the reward. We can see that as the reward becomes sparser, the performance gap between  and the baselines becomes larger, which is consistent with our theory.

Average episode reward of  with varying stochasticity using action noise of $\mathcal{N}(0, \sigma^2)$ where $\sigma=0.03, 0.1, 0.3$ for  tasks. Other hyper-parameters are kept same as the best hyper-parameter. We observe that the performance is preserved the most for  when stochasticity changes.

§.§ Effect of stochasticity of the environment

<Ref> summarizes the experiment result on varying stochasticity with a sparser version of  tasks. We used an additive action noise following $\mathcal{N}(0, \sigma^2)$ with $\sigma=0.03, 0.1, 0.3$ to vary the stochasticity of the environment. Also, we used substep $\substep=3,8,10,10$ for Reach, Push, Slide, Pick respectively to make the reward sparser. This change was made to clearly observe the performance difference when stochasticity changes. The performance of  does not degrade much as the stochasticity increases compared to the other baselines indicating that SPRL robustly performs well in stochastic environments.

§ ANALYSIS ON THE REACHABILITY NETWORK (RNET)

0.20 (a)
0.25 (b)
0.20 (c)
0.25 (d)

The accuracy of the learned reachability network on (a)  (b) , (c)  and (d)  in  in terms of environment steps.

0.30 (a)

The accuracy of the learned reachability network on (a)  (b) , and (c)  in  in terms of environment steps.

0.25 (a)
0.25 (b)
0.25 (c)

0.25 (d)
0.25 (e)
0.25 (f)

The accuracy of the learned reachability network on (a) (b) , (c) , (d) , (e) , and (f) in in terms of environment steps.

0.20 (a)
0.25 (b)
0.20 (c)
0.25 (d)

The accuracy of the learned reachability network on (a)  (b) , (c)  and (d)  in  in terms of environment steps.

§.§ Accuracy of the reachability network

We measured the accuracy of the reachability network on , , , and  in <Ref>, <Ref>, <Ref>, and <Ref>.
The accuracy was measured on the validation set, where we constructed the validation set by sampling 15,000 positive and negative samples respectively from the replay buffer of size 60,000 for , , and 7,500 positive and negative samples respectively from the replay buffer of size 30,000 for , . Specifically, for an anchor $s_t$, we sample the positive sample $s_{t'}$ from $t'\in [t+1,t+k+\Delta t]$, and the negative sample $s_{t''}$ from $t''\in[t+k+\Delta t + \Delta_{-},t+k+\Delta t + 2\Delta_{-}]$.

The RNet reaches an accuracy higher than 80% in only 0.4M steps in both  and . We note that this is quite high considering the unavoidable noise in the negative samples; since the negative samples are sampled based on the temporal distance, not based on the actual reachability, they have a non-zero probability of being reachable, in which case they are in fact the positive samples. For most of the games of , the accuracy of RNet was above 90% except for where the distribution shift in the state space occurs within a task. We note that RNet maintains a high accuracy above 80% throughout the whole training process due to the additional stabilizing techniques such as weight decay. See <Ref> for more details.
<Ref> summarizes the performance of RNet in  tasks. Overall, RNet achieves more than 95% accuracy in less than 1M steps on all four tasks. Considering that predicting the shortest-path distance is much harder in the continuous action domain than the discrete action domains, this result indicates that RNet can be efficiently trained from the time contrastive learning objective even in challenging continuous action domains.

§.§ Ablation study: comparison between the learned RNet and the GT-RNet

In this section, we study the effect of RNet's accuracy on the '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 .

0.20 (a)
0.25 (b)
0.20 (c)
0.25 (d)

The accuracy of the learned reachability network on (a)  (b) , (c)  and (d)  in  in terms of environment steps.

Ground-truth reachability network
Ground-truth reachability network was implemented by computing the distance between the two-state inputs, and comparing it 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 the $k$-reachability network is 1 and otherwise, the output is 0.

We compared the performance of our  with the learned RNet and the ground-truth RNet (GT-SPRL) in <Ref> with the best hyperparameters.
Overall, the performance of  and GT-SPRL are similar. This is partly because the learned RNet achieves quite high accuracy in the early stage of learning (see <Ref>). Interestingly, we can observe that our SPRL with learned RNet performs better than SPRL with GT-RNet on  and . This is possible since a small noise in RNet output can have a similar effect to the increased tolerance $\Delta t$ on RNet, which makes the resulting cost denser, which may be helpful depending on the tasks and hyperparameters.

§ QUALITATIVE ANALYSIS ON COST

0.10 (a)

0.10 (b)

The visualization of and non-trajectories in Room 6 of .
We visualized the agent's trajectories where it receives (a) low cost (, lowest 25%) and (b) high cost (, highest 25%) for 60 steps. The intensity of the red color shows the count of the visited coordinate of the agent. In high cost trajectory, agent tends to move back and forth between the ladder and the right corner of room 6 while in low cost trajectory, agent moves forward without redundancy in the transition.

We visually inspected the agent's trajectory with high and low cost to see whether  can correctly differentiate the shortest-path trajectory.
<Ref> (a) is the visualization of the agent's trajectory with low cost (, shortest-path) trajectory and <Ref> (b) shows the trajectory with high cost (, non-shortest path).
We can observe that when the agent's trajectory has many redundancies (, moving back-and-forth or staying still in the same place), a high cost is given to the agent, while the agent is less penalized when it takes the shortest path.

§ EXPERIMENT DETAILS OF  DOMAIN

§.§ Environment

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 the agent's orientation of movement and changing object status via interaction (e.g., key-door).

State Space.
An observation $\mb{s}_t$ is represented as $H\times W\times C$ tensor, where $H$ and $W$ are the height and width of the map respectively, and $C$ is the 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 the agent, the $(h,w)$-th element is $(type,\;0 ,\;direction)$. The map size (, $H\times W$) varies depending on the task; , for task, the map size is $7\times 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.

* : change the $direction$ counter-clockwise by 90 degree.

* : change the $direction$ clockwise by 90 degree.

* : move toward $direction$ by 1 step unless blocked by other objects.

* : pickup the key if the key is in front of the agent.

* : drop the key in front of the agent.

* : open/close the door if the door is in front of the agent.

* : not used

Reward function.
The reward is given only if the agent reaches the goal location, and the reward magnitude is $1 - 0.9(\text{length of episode} / \text{maximum step for an episode})$. Thus, the agent can maximize the reward by reaching the goal location in the shortest time.

§.§ Tasks

In and , the map structure has four large rooms, and the agent needs to reach the goal. In and , the agent needs to pick up the key, go to the door, and open the door before reaching the goal location.

§.§ Architecture and hyper-parameters

We used a simple CNN architecture similar to [Mnih et al., 2015] for the policy network.
The network consists of -------, where  padding ensures the input and output have the same size (, 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 <Ref>, and chose the best one in terms of the mean AUC over all the tasks, which is also summarized in <Ref>.

Hyperparameters     Sweep range     Final value
Learning rate               0.001, 0.002, 0.003     0.003

Entropy                     0.003, 0.005, 0.01, 0.02, 0.05     0.01

Hyperparameters     Sweep range     Final value
Learning rate               0.001, 0.002, 0.003     0.003

Entropy                     -     0.01

Forward/Inverse model loss weight ratio     0.2, 0.5, 0.8, 1.0     0.8

Curiosity module loss weight     0.03, 0.1, 0.3, 1.0     0.3

bonus weight     0.1, 0.3, 1.0, 3.0     0.1

Hyperparameters     Sweep range     Final value
Learning rate               0.001, 0.002, 0.003     0.003

Entropy                     -     0.01

bonus weight      0.003, 0.01, 0.03, 0.1, 0.3     0.01

Hyperparameters     Sweep range     Final value
Learning rate               -     0.003

Entropy                     -     0.01

$k$                         3, 5, 7     3

bonus weight         0.001, 0.002, 0.005, 0.01     0.001

Hyperparameters     Sweep range     Final value
Learning rate               0.003, 0.01     0.01

Entropy                     -     0.01

$k$                         2, 5     2

Tolerance ($\Delta t$)      -     1

Negative bias ($\Delta^-$)         10, 20     20

Positive bias ($\Delta^+$)         -     5

Cost scale ($\lambda$)      0.001, 0.002, 0.005     0.002

$N_{\Delta t}$     30, 60     60

The range of hyperparameters sweeped over and the final hyperparameters used in  domain.

§ EXPERIMENT DETAILS OF  DOMAIN

§.§ Environment

is a 3D-game environment with a 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  hard to be learned.

State Space.
A state $\mb{s}_t$ has the dimension of $84\times 84\times 3$. The state is given as a first-person view of the map structure. We resized the $RGB$ image into $84\times 84\times 3$ $RGB$ image and normalized it by dividing the pixel value by 255.

Action Space and transition dynamics
The episode terminates after the fixed number of steps regardless of the goal being achieved.
The original action space consists of seven discrete actions: , , , , , , , . In our experiment, we used eight discrete actions with the additional action  as in Higgins et al., 2017, Vezhnevets et al., 2017, Savinov et al., 2018, Espeholt et al., 2018, Khetarpal & Precup, 2018.

§.§ Tasks

We tested our agent and compared methods on three standard tasks in : , , and  which correspond to , , and , respectively.
and  have a single goal in the maze, but the size of the maze is larger in  than . The agent and goal locations are randomly set at the beginning of the episode and the episode length is fixed to 1,350 steps for  and 1,800 steps for . 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 the goal multiple times within a single episode. Thus, the agent's goal is to reach the goal location as many times as possible within the episode length.
has multiple objects in the maze, where reaching 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 objects as possible within the episode length.
Sampling the triplet data from an episode for RNet training
[1]
Hyperparameters: $k\in\mbb{N}$, Positive bias $\Delta^{+}\in\mbb{N}$, Negative bias $\Delta^{-}\in\mbb{N}$
Initialize $t_{\text{anc}}\leftarrow 0$.
Initialize $S_{\text{anc}}=\emptyset$, $S_{+}=\emptyset$, $S_{-}=\emptyset$.
$t_{\text{anc}} < T$
$S_{\text{anc}} = S_{\text{anc}} \cup \{s_{t_{\text{anc}}}\}$.
$t_{+}=\text{Uniform}(t_{\text{anc}}+1, t_{\text{anc}}+k)$.
$t_{-}=\text{Uniform}(t_{\text{anc}}+k+\Delta^{-}, T)$.
$S_{+} = S_{+} \cup \{s_{t_{+}}\}$.
$S_{-} = S_{-} \cup \{s_{t_{-}}\}$.
$t_{\text{anc}}=\text{Uniform}(t_{+}+1, t_{+}+\Delta^{+})$.
Return $S_{\text{anc}}, S_{+}, S_{-}$

§.§ Reachability network Training

Similar to Savinov et al., 2018, we used the following contrastive loss for training the reachability network:

\begin{align} %
\mathcal{L}_{\text{Rnet}} = - \log\left(\text{Rnet}_{k-1}(s_{\text{anc}}, s_+) \right) - \log\left(1 - \text{Rnet}_{k-1}(s_{\text{anc}}, s_-) \right),\label{eq:rnet-loss2}
\end{align}

where $s_{\text{anc}}, 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 <Ref>.
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 , RNet accuracy was $\sim0.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 <Ref>.
As a choice of sampling method, we simply used multiples of tolerance. In other words, given $s_{t-(k+\Delta{}t)}$ and $s_t$ as inputs for reachability network, we instead used $s_{t-(k+n\Delta{}t)}$ and $s_t$ where $1 \le n \le N_{\Delta t}$, $n \in \mathbb{N}$ and $N_{\Delta t}$ is the number of tolerance samples. We used 90-percentile of $N_{\Delta t}$ outputs of reachability network, Rnet$_{k-1}(s_{t-(k+n\Delta{}t)}, s_t)$, as in [Savinov et al., 2018] to get the representative of the samples.

§.§ Architecture and hyper-parameters

Following [Savinov et al., 2018], we used the same CNN architecture used in [Mnih et al., 2015].

For , we used a smaller reachability network (RNet) architecture compared to  to reduce the training time.
The RNet is based on the siamese architecture with two branches.
Following [Savinov et al., 2018],  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 , 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 three[Savinov et al., 2018 used four 512-dimensional fully-connected layers.] 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 (, $84\times 84\times 3$, which is smaller than the original $120\times 160\times 3$ used in [Savinov et al., 2018]).

For all the baselines (, , , , and ), we used the best hyperparameter used in [Savinov et al., 2018]. For , we searched over a set of hyperparameters specified in <Ref>, and chose the best one in terms of the mean AUC over all the tasks, which is also summarized in <Ref>.

Hyperparameters for      Sweep range     Final value
Learning rate               -     0.0003

Entropy                     -     0.004

$k$                         3, 10, 30     10

Tolerance ($\Delta t$)      1, 3, 5     1

Negative bias ($\Delta^-$)         5, 10, 20     20

Positive bias ($\Delta^+$)         -     5

Cost scale ($\lambda$)      0.02, 0.06, 0.2     0.06

Optimizer                   -     Adam

$N_{\Delta t}$     -     200

The range of hyperparameters sweeped over and the final hyperparameters used for our  method in  domain.

§ EXPERIMENT DETAILS OF DOMAIN

§.§ Environment

is an important and prominent benchmark in deep reinforcement learning with a high-dimensional visual input. One of the main benefits of using as a testbed is that it covers not only navigational tasks but various tasks such as avoiding and destroying enemies by firing a bullet or changing the map structure using bombs as explained in [Bellemare et al., 2013]. Because of the diversity of the task is covering, solving shows that the algorithm has a certain degree of generality.
There exists a variety of preprocessing details for . We mostly followed the implementation of OpenAI Baselines [Dhariwal et al., 2017]. For detailed information, see <Ref>.

Parameter     Value
Image Width               84

Image Height              84

Grayscaling               Yes

Number of Actions       18

Action Repetitions      4

Frame Stacking         4

End of episode when life lost         No

Reward Clipping      [-1,1]

Discount($\gamma$)                   0.99

Max Episode Length     10000

Number of parallel workers              12

Preprocessing details for

State Space.
A state $\mb{s}_t$ is represented as $84\times 84\times 4$. We stacked 4 consecutive frames achieved by taking the same action 4 times in a row and resized $RGB$ image into $84\times 84\times 1$ gray image and normalized by dividing the pixel value by 255.

Action Space and transition dynamics
The episode terminates when the agent loses all of the lives given.
The action space consists of eighteen discrete actions as in [Bellemare et al., 2013].

§.§ Various Tasks of : Navigational and Non-navigational

We tested our agent and compared methods on navigational and non-navigational tasks in : , , , , , .
is a famous game as a hard exploration game in . An agent should pick up the items such as a key to open the door or a knife to destroy the enemy. In , an agent should cross the road while avoiding the car. is a game where an agent should eat the items and avoid the enemy. Three games mentioned until now have a  navigational feature meaning that the agent can move toward a certain coordinate to get the score. However, the three games to be mentioned have a non-navigational feature meaning that the agent should not only get to a certain coordinate but also use specific action to get the score. In and , an agent should shoot a bullet. In , an agent can install a bomb to break the wall and move forward. By adding , , and to our testbed, we evaluated how  performs in non-navigational tasks.

§.§ Reachability network Training

We followed the details of reachability network training for  except for 1) replay buffer size and 2) reachability network training frequency. We changed the size of the replay buffer for the reachability network from $60K$ environment steps to $30K$ environment steps. To avoid overfitting of the reachability network, we enlarged the reachability network training frequency from 6K environment steps to 150K environment steps after the initial 1M environment steps.

Stabilizing Reachability Network.
In some of the games of , within a task exists a distributional shift in the state space that hinders stable reachability network training. Therefore we had to use some techniques to mitigate the instability problem of the reachability network: Weight decay and Label smoothing. We used weight decay with the factor of 0.03 and label smoothing of 0.1. Also instead of using current and future states as inputs, we used current and pixel-level subtraction of current and future states which stabilized the learning.

§.§ Architecture and hyper-parameters

For the policy architecture, we used the same CNN architecture used in Mnih et al., 2015.
For the reachability network, we used the same architecture used for  except for the input layer. For the input layer, we used $(\mb{s}_t, \mb{s}_t - \mb{s}_{t-k})$ instead of $(\mb{s}_t, \mb{s}_{t-k})$. This change helped the reachability network to avoid suffering from overfitting when the distribution shift in the state space occurs.

For hyper-parameter search, we swept over a set of hyper-parameters specified in <Ref> and chose the best one in terms of the mean AUC over all the tasks, which is also summarized in <Ref>.

Hyperparameters     Sweep range     Final value
Learning rate               0.0001, 0.0002, 0.0003, 0.0005     0.0005

Entropy                     0.001, 0.003, 0.005, 0.01, 0.03     0.01

Hyperparameters     Sweep range     Final value
Learning rate               0.0005     0.0005

Entropy                     -     0.01

Forward/Inverse model loss weight ratio     1.0     1.0

Curiosity module loss weight     1.0     1.0

bonus weight     0.0001, 0.0003, 0.001, 0.003, 0.01     0.01

Hyperparameters     Sweep range     Final value
Learning rate               0.0001, 0.0003, 0.0005     0.0005

Entropy                     -     0.01

bonus weight         0.001, 0.003, 0.01, 0.03, 0.1     0.001

Hyperparameters     Sweep range     Final value
Learning rate                0.0003, 0.0005     0.0005

Entropy                     -     0.01

cost scale ($\lambda$)      0.01, 0.03, 0.05, 0.1     0.05

3cReachability network (for  and )

$k$                         5, 8, 12, 15     12

Tolerance ($\Delta t$)      -     1

Negative bias ($\Delta^-$)         80, 100, 120     80

Positive bias ($\Delta^+$)         -     5

$N_{\Delta t}$     30, 50, 100, 200, 400     200

The range of hyperparameters sweeped over and the final hyperparameters used in domain.

§ EXPERIMENT DETAILS OF DOMAIN

§.§ Environment

is a continuous control environment with a two-fingered gripper. By controlling the gripper, specific interaction between the gripper and the object needs to be accomplished for a given task. The agent and the goal locations are randomly initialized at each episode and these features make the environment difficult to solve.

State Space.
At each time step $t$, the state input $s_t$ is a vector ($16$-dimensional for  and $31$-dimensional for , , and ) consisting of the location and the velocity of the gripper. When the object exists in the task, the location, rotation, linear and angular velocities of the object are also included in the state $s_t$.

Action Space
The action space is continuous. Actions are total 4 dimensional: 3 dimensions for gripper movement and 1 dimension for the opening of the gripper.

Modification in the environment
We made two modifications in the episode termination and the reward function to make it a sparse-reward task.
The agent receives +1 reward if the agent reaches the goal and 0 rewards otherwise. Also, the episode terminates when the agent reaches the goal such that the agent can receive a non-zero reward at most once in an episode.

§.§ Tasks

Four tasks are available in the  domain: , , ,

*  : The goal is to push a box to a target location. The gripper can only push in this task since fingers are not controllable.

*  : The goal is to move the gripper to a target location. This is the easiest task in  since moving the gripper is a fundamental skill required in all four tasks.

*  : The goal is to hit the object, let the object slide, and stop at the desired location by friction.

*  : The goal is to grasp a box and move the box to the target location.

§.§ Reward Normalization

We used reward normalization analogous to Burda et al., 2018, , “dividing the rewards by a running estimate of the standard deviation of the sum of discounted rewards”. Reward normalization has been particularly effective in the  environment on every algorithm. We leave the analysis of this phenomenon as future work.

§.§ Architecture and hyper-parameters

We used a simple MLP architecture for policy network.
The network consists of --------. The reachability network was also a simple MLP network. The network consists of -------------. We used Adam [Kingma & Ba, 2014] optimizer to optimize both networks.

For hyper-parameter search, we swept over a set of hyper-parameters specified in <Ref> and chose the best one in terms of the mean AUC over all the tasks, which is also summarized in <Ref>.

Hyperparameters     Sweep range     Final value
Learning rate               -     0.0005

Entropy                     0.001, 0.003, 0.01     0.01

Action Noise                -     0.003

Hyperparameters     Sweep range     Final value
Learning rate               -     0.0005

Entropy                     -     0.001

Action Noise                -     0.003

Forward/Inverse model loss weight ratio     -     1.0

Curiosity module loss weight     -     1.0

bonus weight     0.0001, 0.0002, 0.0003, 0.0005, 0.001, 0.003, 0.01     0.001

Hyperparameters     Sweep range     Final value
Learning rate               -     0.0005

Entropy                     -     0.001

Action Noise                -     0.003

bonus weight         0.0001, 0.0002, 0.0003, 0.0005, 0.001, 0.003, 0.01     0.0001

Bias                        0.5, 1.0     1.0

Hyperparameters     Sweep range     Final value
Learning rate                -     0.0005

Entropy                     -     0.001

cost scale ($\lambda$)      0.0001, 0.0002, 0.0003, 0.0005, 0.001, 0.003, 0.01     0.05

Bias                        0.5, 1.0     1.0

3cReachability network (for  and )

$k$                         -     10

Tolerance ($\Delta t$)      -     1

Negative bias ($\Delta^-$)         1, 2, 3, 5, 8, 12     12

Positive bias ($\Delta^+$)         -     5

$N_{\Delta t}$     -     20

The range of hyperparameters swept over and the final hyperparameters used in  domain.

§ OPTION FRAMEWORK-BASED FORMULATION

§.§ Preliminary: option framework

Options framework [Sutton, 1998] defines options as a generalization of actions to include a temporally extended series of action. Formally, options consist of three components: a policy $\pi: \mathcal{S} \times \mathcal{A} \rightarrow$ $[0,1],$ a termination condition $\beta: \mathcal{S}^{+} \rightarrow[0,1],$ and an initiation set $\mathcal{I} \subseteq \mathcal{S} .$ An option $\langle\mathcal{I}, \pi, \beta\rangle$ is available in state $s$ if and only if $s \in \mathcal{I}$.
If the option is taken, then actions are selected according to $\pi$ until the option terminates stochastically according to $\beta $.
Then, the option-reward and option-transition models are defined as

\begin{align}
r_{s}^{o} &= \mathbb{E}\left\{r_{t+1}+\gamma r_{t+2}+\cdots+\gamma^{k-1} r_{t+k} \mid E(o, s, t)\right\}\label{eq:opt-rew}\\
P_{s s^{\prime}}^{o}&=\sum_{k=1}^{\infty} p\left(s^{\prime}, k\right) \gamma^{k}\label{eq:opt-trans}
\end{align}

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:

\begin{align}
V^\pi(s) &= \mbb{E}\left[
r_{t+1}+\cdots+\gamma^{k-1}r_{t+k}+\gamma^k V^\pi(s_{t+k})
\right],\\
&=\sum_{o\in\mc{O}} Pr[ E(o, s) ] \left[ r_s^{o} + \sum_{s'} P_{ss'}^oV^\pi(s') \right].\label{eq:opt-bellman}
\end{align}

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

§.§ Option-based view-point of shortest-path constraint

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_{s s^{\prime}}^{o}$.

For a given MDP $\mathcal{M}=(\mc{S, A, R, P},\rho, \bar{\mc{S}})$, let $\mc{S}^{R}=\{s|R(s)\neq 0\}\subset\mc{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 $|\mc{S}^{R}| << |\mc{S}|$.
Then, we can form a weighted directed graph $G^\pi=(\mc{V}, \mc{E})$ of policy $\pi$ and given MDP.
The vertex set is defined as $\mc{V}=\mc{S}^{R}\cup\rho_0\cup\bar{\mc{S}}$ where $\mc{S}^{R}$ is rewarding states, $\rho_0$ is the initial states, and $\bar{\mc{S}}$ is the terminal states.
Similar to the path set in <Ref>, let $\mc{T}_{s\rightarrow s'}$ denotes a set of paths transitioning from one vertex $s\in \mc{V}$ to another vertex $s'\in \mc{V}$:

\begin{align}
\mc{T}_{s\rightarrow s'}=\{\tau|s_0=s, s_{\ell(\tau)}=s', \{s_t\}_{0<t<\ell(\tau)}\cap \mc{V}=\emptyset  \}.
\end{align}

Then, the edge from a vertex $s\in \mc{V}$ to another vertex $s'\in \mc{V}$ is defined by an (implicit) option tuple: $o(s, s') = (\mc{I}, \pi, \beta)_{(s,s')}$, where $\mc{I}=\{s\}$, $\beta(s)=\mbb{I}(s=s')$, and

\begin{align}
\pi^{(s, s')}(\tau)=
\begin{cases}
\frac{1}{Z}\pi (\tau)   &   \text{for }\tau\in\mc{T}_{s\rightarrow s'}\\
0                       &   \text{otherwise}
\end{cases},
\end{align}

where $Z$ is the partition function to ensure $\int\pi^{(s, s')}(\tau)d\tau=1$.
Following <Ref>, the option-reward is given as

\begin{align}
r^{\pi}_{s, s'}
&=\mbb{E}^{\pi^{(s,s')}}\left[ r_{t+1}+\gamma r_{t+2}+\cdots+\gamma^{k-1}r_{t+k} \mid E(o^{(s,s')}, s, t) \right],\\
&=\mbb{E}^{\pi^{(s,s')}}\left[ \gamma^{k-1}r_{t+k} \mid E(o^{(s,s')}, s, t)  \right]\label{eq:opt-rew2},
\end{align}

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, $r_{t+1}=\cdots=r_{t+k-1}=0$ holds since $\{s_{t+1},\ldots, s_{t+k-1}\} \cap \mc{V}=\emptyset$ from the definition of option policy $\pi^{(s, s')}$.
Following <Ref>, the option transition is given as

\begin{align}
\trans
&=\sum_{k=1}^{\infty} p(s', k)\gamma^k\\
&=\mathbb{E}^\pi\left[\gamma^k|s_0=s, s_{k}=s', \{r_t\}_{t< k}=0\right] \label{eq:opt-trans2}\\
\end{align}

where $p(s', k)$ is the probability that the option terminates in $s'$ after $k$ steps, and $\distpi$ is the $\pi$-distance in <Ref>.
Then, we can re-write the shortest-path constraint in terms of $\trans$ as follows:

\begin{align}
\Pisp &= \{\pi|\forall(s, s'\in\mc{T}^{\pi}_{\hat{s}, \hat{s}', \text{nr}} \text{~s.t.~} (\hat{s}, \hat{s}')\in\nrstatepair),\ \distpi = \min_{\pi} \distpi\}\\
&=  \{\pi|\forall(s, s'\in\mc{T}^{\pi}_{\hat{s}, \hat{s}', \text{nr}} \text{~s.t.~} (\hat{s}, \hat{s}')\in\nrstatepair),\ \trans = \max_{\pi} \trans \}
\label{eq:option-shortest-path-policy}
\end{align}

Thus, we can see that the policy satisfying SP constraint also maximizes the option-transition probability. We will use this result in Appendix <ref>.

§ SHORTEST-PATH CONSTRAINT: A SINGLE-GOAL CASE

In this section, we provide more discussion on a special case of the shortest-path constraint (<Ref>), when the (stochastic) MDP defines a single-goal task:
, there exists a unique initial state $s_{\text{init}}\in\mc{S}$ and a unique goal state $s_g\in\mc{S}$ such that $s_g$ is a terminal state, and $R(s) > 0$ if and only if $s = s_g$.

We first note that the non-rewarding path set is identical to the path set in such a setting, because the condition $r_t = 0 (t<\ell(\tau))$ from <Ref> is always satisfied as $R(s) > 0 \Leftrightarrow s = s_g$ and $s_{\ell(\tau)} = s_g$:

\begin{align}
\pathsetpi = \gpathsetpi=\{\tau \mid s_0=s, s_{\ell(\tau)}=s', p_\pi(\tau)>0, \{s_t\}_{t<\ell(\tau)}\neq s' \}
\end{align}

Again, $\gpathsetpi$ is a set of all path starting from $s$ (,
and ending at $s'$ (, $s_{\ell(\tau)}=s'$)
where the agent visits $s'$ only at the end (, $\{s_t\}_{t<\ell(\tau)}\neq s'$),
that can be rolled out by policy with a non-zero probability (, $p_\pi(\tau)>0$).

We now claim that an optimal policy satisfies the shortest-path constraint.
The idea is that, since $s_g$ is the only rewarding and terminal state, maximizing $R(\tau) = \gamma^T R(s_g)$ where $s_T = s_g$ corresponds to minimizing the number of time steps $T$ to reach $s_g$.
In this setting, a shortest-path policy is indeed optimal.

For a single-goal MDP, any optimal policy satisfies the shortest-path constraint.

Let $s_{\text{init}}$ be the initial state and $s_g$ 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 $s_g$ is the only rewarding state, , $R(s) > 0$ entails $s = s_g$.

\begin{align}
\pi^* &= \argmax_\pi \mbb{E}^{\tau\sim\pi}_{s\sim\rho} \left[\textstyle\sum_{t}{\gamma^t r_t\biggmid s_0=s}\right]\\
&=\argmax_\pi \mbb{E}^{\tau\sim\pi}\left[\textstyle\sum_{t}{\gamma^t r_t\biggmid s_0=s_{\text{init}}}\right]\\
&=\argmax_\pi \mbb{E}^{\tau\sim\pi} \left[\gamma^T R(s_g) \mid s_0=s_{\text{init}}, s_{\ell(\tau)}=s_g \right]\\
&=\argmax_\pi \mbb{E}^{\tau\sim\pi} \left[\gamma^T \mid s_0=s_{\text{init}}, s_{\ell(\tau)}=s_g \right]\label{eq:g-sp-optimal}\\
\log_\gamma \left( \mbb{E}^{\tau\sim\pi}\left[\gamma^{T} \mid s_0=s_{\text{init}}, s_{\ell(\tau)}=s_g\right] \right)\\
&=\argmin_\pi D_{\text{nr}}^{\pi}(s_{\text{init}},s_g),\label{eq:sp-optimal}
\end{align}

where <Ref> holds since $R(s_g)>0$ from our assumption that $R(s)+V^*(s)>0$.

§ PROOF OF <REF>

We make the following assumptions on the Markov Decision Process (MDP) $\mathcal{M}$: namely mild stochasticity (<Ref>).

In MDP $\mathcal{M}$, there exists an optimal policy $\pi^*$ and the corresponding shortest-path policy $\pi^{sp}\in\Pisp$ such that for all $s,s'\in\nrstatepair$, it holds $p_{\pi^*}(\bar{s}=s'|s_0=s)=p_{\pi^{sp}}(\bar{s}=s'|s_0=s)$.

In MDP $\mathcal{M}$, the optimal policy $\pi^*$ does not visit the same state more than once:
For all $s \in \mathcal{S}$ such that $\rho_{\pi^*}(s)>0$,
it holds $\rho_{\pi^*}(s)=1$, where $\rho_{\pi}(s) \triangleq \mathbb{E}_{s_0\sim\rho_{0}(S), a \sim \pi(A|s), s'\sim(S|s,a) }\left[\sum_{t=1}^{T} \mathbb{I}\left(s_{t}=s\right)\right]$ 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 , , etc.

For any MDP with the mild stochasticity condition, an optimal policy $\pi^*$ satisfies the shortest-path constraint: $\pi^*\in\Pisp$.

For simplicity, we prove this based on the option-based view point (see <Ref>).
By plugging <Ref> and <Ref> into <Ref>, we can re-write the Bellman equation of the value function $V^\pi(s)$ as follows:

\begin{align}
&=\sum_{o\in\mc{O}} Pr[ E(o, s) ] \left[
r_s^{o} + \sum_{s'} P_{ss'}^oV^\pi(s')
\right]\\
&=\sum_{s' \in \nrstate} p_{\pi}( \bar{s}=s'|s_0=s)\left[
R(s')\mbb{E}^{\tau\sim\pi}(\gamma^{\ell(\tau)}|s_0=s, \bar{s}=s') +  \gamma\trans V^\pi(s')
\right]\\
&=\sum_{s' \in \nrstate} p_{\pi}( \bar{s}=s'|s_0=s)\left[
R(s') \trans +  \gamma\trans V^\pi(s')
\right],\\
&=\sum_{s' \in \nrstate} p_{\pi}( \bar{s}=s'|s_0=s)\trans\left[
R(s') + \gamma V^\pi(s')
\right],\label{eq:opt-value}
\end{align}

where $\bar{s}$ is the first rewarding state that agent encounters. Intuitively, $p_{\pi}( \bar{s}=s'|s_0=s)$ means the probability that the $s'$ is the first rewarding state that policy $\pi$ encounters when it starts from $s$.
From <Ref>, our goal is to show:

\begin{align}
\pi^*\in \Pisp = \{\pi \mid \forall(s,s')\in \pathsetpiphi, \trans = \transshort\},
\label{eq:pi-in-pisp-proof}
\end{align}

where $ \transshort=\max_{\pi}\trans$.

We will prove <Ref> by contradiction. Suppose $\pi^*$ is an optimal policy such that $\pi^*\not\in \Pisp$. Then,

\begin{align}
\exists (\widehat{s}, \widehat{s}'\in \pathsetoptpiphi) &\text{ s.t. } \transopthat \neq \transshorthat.
\end{align}

Recall the definition: $\transshort=\max_{\pi} \trans$. Then, for any $\pi$, the following statement is true.

\begin{align}
\trans \neq \transshort &\leftrightarrow \trans < \transshort.
\end{align}

Thus, we have

\begin{align}
\transopthat < \transshorthat
\end{align}

Let $\pi_{sp}\in\Pisp$ be a shortest path policy that preserves stochastic dynamics from <Ref>.
Then, we have

\begin{align}
\transopthat < \transshorthat = P^{\pi_{sp}}_{\hat{s}, \hat{s}'}.\label{ineq:PP}
\end{align}

Then, let's compose a new policy $\widehat{\pi}$:

\begin{align}
\widehat{\pi}(a|s)=
\begin{cases}
\pi_{sp}(a|s) & \text{if } \exists \ \tau\in\mc{T}_{\hat{s}, \hat{s}', \text{nr}}^{\pi_{sp}}\text{ s.t. }s\in\tau \\
\pi^{*}(a|s) & \text{otherwise}
\end{cases}.\label{def:compose_policy}
\end{align}

Now consider a path $\tau_{\hat{s}\rightarrow \hat{s}'}$ that agent visits $\hat{s}$ at time $t=i$ and transitions to $\hat{s}'$ at time $t=j > i$ while not visiting any rewarding state from $t=i$ to $t=j$ with non-zero probability (, $p_{\pi_{\text{sp}}}(\tau)>0$). We can define a set of such paths as follows:

\begin{align}
\pathsethathat=\{\tau \mid \exists(i<j), s_i=\hat{s}, s_{j}=\hat{s}', \{s_t\}_{i<t<j}\cap \mc{\nrstate}=\emptyset, p_{\pi_{\text{sp}}}(\tau)>0  \}.
\end{align}

To reiterate the definitions from <Ref>:
$\nrstate=\{s \mid R(s)>0\text{ or }\rho(s)>0 \}$ is the union of all initial and rewarding states,
and $\nrstatepair=\{(s, s') \mid s, s' \in \nrstate, \rho(s)>0, \pathsetpi\neq\emptyset\}$ is the subset of $\nrstate$ such that agent may roll out.

From <Ref> and <Ref>, the likelihood of a path $\tau$ under policy $\hat{\pi}$ is given as follows:

\begin{align}
\begin{cases}
p_{\pi^*}(\tau\in\pathsethathat)p_{\pi_{\text{sp}}}(\tau|\tau\in\pathsethathat) & \text{for }\tau\in\pathsethathat\\
p_{\pi^*}(\tau) & \text{otherwise}
\end{cases},\label{eq:likelihood-comp}
\end{align}

where $p_{\widehat{\pi}}(\tau)$ is the likelihood of trajectory $\tau$ under policy $\widehat{\pi}$, $p_{\widehat{\pi}}(\tau\in\pathsethathat)=\int_{\tau\in\pathsethathat}{p_{\widehat{\pi}}(\tau)d\tau}$ ensures the likelihood $\widehat{\pi}(\tau)$ to be a valid probability density function (, $\int p_{\widehat{\pi}}(\tau)d\tau = 1$).
From the path $\tau_{\hat{s}\rightarrow \hat{s}'}$ and $i, j$, we will choose two states $s_{\text{ir}}, s'_{\text{ir}}\sim\tau_{\hat{s}\rightarrow \hat{s}'}$, where

\begin{align}
s_{\text{ir}}=\max_t (s_t| s_t\in\nrstate, t \leq i),
\quad
s'_{\text{ir}}=\min_t (s_t| s_t\in\nrstate, j\leq t).
\end{align}

Note that such $s_{\text{ir}}$ and $s'_{\text{ir}}$  always exist in $\tau_{\hat{s}\rightarrow \hat{s}'}$ since the initial state and the terminal state satisfy the condition to be $s_{\text{ir}}$ and $s'_{\text{ir}}$.

Then, we can show that the path between $s_{\text{ir}}$ and $s'_{\text{ir}}$ is not a shortest-path.
Recall the definition of $\distpi$ (<Ref>):

\begin{align}
D_{\text{nr}}^{\pi^*}(s_{\text{ir}}, s_{\text{ir}}')
&\defeq \log_\gamma \left(\mathbb{E}_{\tau \sim \pi^* :~ \tau \in \mc{T}^{\pi^*}_{\initstir, \laststir, \text{nr}}} \left[ \gamma^{\ell(\tau)} \right]\right)\\
&= \log_\gamma \left(\mathbb{E}_{\tau\sim\pi^*} \underbrace{ \left[
\gamma^{\ell(\tau)} \mid \tau \in \mathcal{T}^{\pi^*}_{s_{\text{ir}}, s_{\text{ir}}', \text{nr}}
\right]
\right)
\end{align}

where we will use $\clubsuit \defeq \gamma^{\ell(\tau)} \mid \tau \in \mathcal{T}^{\pi^*}_{s_\text{ir}, s'_\text{ir}, \text{nr}}$  for a shorthand notation.
Then, we have

\begin{align}
\gamma^{D_{\text{nr}}^{\pi^*}(s_{\text{ir}}, s_{\text{ir}}')}
&\defeq \mathbb{E}_{\tau \sim \pi^*} \left[ \clubsuit \right]\\
&=p_{\pi^*}(\tau\in\pathsethathat) \mathbb{E}_{\tau \sim \pi^*} \left[
\clubsuit \mid \tau\in\pathsethathat \right]\nn\\
&\hspace{5em}+p_{\pi^*}(\tau\notin\pathsethathat)\mathbb{E}_{\tau \sim \pi^*} \left[
\clubsuit \mid \tau\notin\pathsethathat \right]
\hspace*{5em}{\color{white}.}\\
\text{(From~\Cref{def:sp-policy})}\
&<p_{\pi^*}(\tau\in\pathsethathat) \mathbb{E}_{\tau\sim\pi_{\text{sp}}}\left[ \clubsuit \mid \tau\in \pathsethathat\right]\nn\\
&\hspace{5em}+p_{\pi^*}(\tau\notin\pathsethathat)\mathbb{E}_{\tau\sim\pi^*}\left[ \clubsuit \mid \tau\notin \pathsethathat\right]\\
\text{(From~\Cref{eq:likelihood-comp})}\
&=p_{\widehat{\pi}}(\tau\in\pathsethathat) \mathbb{E}_{\tau\sim\widehat{\pi}}\left[ \clubsuit \mid \tau\in \pathsethathat\right]\nn\\
&\hspace{5em}+p_{\widehat{\pi}}(\tau\notin\pathsethathat)\mathbb{E}_{\tau\sim\widehat{\pi}}\left[ \clubsuit \mid  \tau\notin \pathsethathat\right]\\
&=\mathbb{E}_{\tau \sim \widehat{\pi}} \left[ \clubsuit \right]
=\gamma^{D_{\text{nr}}^{\widehat{\pi}}(s_{\text{ir}}, s_{\text{ir}}')}\label{ineq:lemma}\\
&\Longleftrightarrow D_{\text{nr}}^{\pi^*}(s_{\text{ir}}, s'_{\text{ir}})>D_{\text{nr}}^{\widehat{\pi}}(s_{\text{ir}}, s'_{\text{ir}}) \label{ineq:lemma-final}
\end{align}

where Ineq. (<ref>) is given by the fact that $\gamma<1$. Then, $P^{\pi^*}_{s_{\text{ir}}, s_{\text{ir}}'} < P^{\widehat{\pi}}_{s_{\text{ir}}, s_{\text{ir}}'}$.

From <Ref>, we have

\begin{align}
\hspace*{-5em}
&=\sum_{s'\in\nrstate}p_{\widehat{\pi}}( \bar{s}=s' \mid s_0=\initstir)P^{\widehat{\pi}}_{\initstir, s'}\left[R(s')+\gamma V^{\widehat{\pi}}(s')\right]\\
&=p_{\widehat{\pi}}( \bar{s}=\initstir' \mid  s_0=\initstir)P^{\widehat{\pi}}_{\initstir,\laststir}\left[R(\laststir)+\gamma V^{\widehat{\pi}}(\laststir)\right] \nonumber\\
&\hspace{5em} + \sum_{s'\in\nrstate\setminus\laststir}p_{\widehat{\pi}}( \bar{s}=s' \mid  s_0=\initstir)P^{\widehat{\pi}}_{\initstir, s'}\left[R(s')+\gamma V^{\widehat{\pi}}(s')\right]\\
&=p_{\pi^*}( \bar{s}=\initstir' \mid  s_0=\initstir)P^{\widehat{\pi}}_{\initstir,\laststir}\left[R(\laststir)+\gamma V^{\pi^*}(\laststir)\right] \nonumber\\
&\hspace{5em} + \sum_{s'\in\nrstate\setminus\laststir}p_{\pi^*}( \bar{s}=s' \mid s_0=\initstir)P^{\pi^*}_{\initstir, s'}\left[R(s')+\gamma V^{\pi^*}(s')\right]\label{eq:mild2}\\
&>p_{\pi^*}( \bar{s}=\initstir' \mid  s_0=\initstir)P^{\pi^{*}}_{\initstir,\laststir}\left[R(\laststir)+\gamma V^{\pi^*}(\laststir)\right] \nonumber\\
&\hspace{5em} + \sum_{s'\in\nrstate\setminus\laststir}p_{\pi^*}( \bar{s}=s' \mid s_0=\initstir)P^{\pi^*}_{\initstir, s'}\left[R(s')+\gamma V^{\pi^*}(s')\right]\label{ineq:opt-value}\\
&=\sum_{s'\in\nrstate}p_{\pi^*}( \bar{s}=s' \mid  s_0=\initstir)P^{\pi^{*}}_{\initstir, s'}\left[R(s')+\gamma V^{\pi^{*}}(s')\right]\\
\end{align}

Eq. (<ref>) holds from the mild-stochasticity (1) and mild-stochasticity (2) assumption, and Ineq. (<ref>) holds because $P^{\widehat{\pi}}_{\initstir, \laststir}>P^{\pi^{*}}_{\initstir, \laststir}$ and $R(s')+\gamma V^{\pi^{*}}(s')>0$ from the non-negative optimal value assumption (See <Ref>).
Finally, this is a contradiction since the optimal value function $V^{*}(s)$ should be the maximum.

§ EXTENDED RELATED WORKS

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, Abel et al., 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 the deep-RL setting where the 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 (, 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 <Ref> 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 <ref> for the detailed description of the option framework-based formulation of our framework.