Many hierarchical reinforcement learning (RL) applications have empirically verified that incorporating prior knowledge in reward design improves convergence speed and practical performance. We attempt to quantify the computational benefits of hierarchical RL from a planning perspective under assumptions about the intermediate state and intermediate rewards frequently (but often implicitly) adopted in practice. Our approach reveals a trade-off between computational complexity and the pursuit of the shortest path in hierarchical planning: using intermediate rewards significantly reduces the computational complexity in finding a successful policy but does not guarantee to find the shortest path, whereas using sparse terminal rewards finds the shortest path at a significantly higher computational cost. We also corroborate our theoretical results with extensive experiments on the MiniGrid <cit.> environments using Q-learning and other popular deep RL algorithms.

Keywords: Hierarchical reinforcement learning, planning.

§ INTRODUCTION

Markov decision processes (MDPs) <cit.> provide a powerful framework for reinforcement learning (RL) <cit.> and planning <cit.> tasks. In particular, many of these practical tasks <cit.> possess hierarchical structures, meaning that the agent must first accomplish sub-goals to reach the terminal state. To encourage the agent to visit these sub-goals, the reward functions for these hierarchical MDPs <cit.> are often carefully designed based on the designers' prior knowledge. <cit.> introduced a framework that decomposes the original MDP into “subMDPs”, and demonstrated that hierarchical structures indeed lead to statistical and computational efficiency, under certain assumptions. <cit.> indeed provides an insightful framework for studying hierarchical RL, but it does not clearly address how the framework connects back to practice. To bridge hierarchical RL theory and RL practice, for a given hierarchical MDP, we consider the intermediate states as the non terminal states that provide positive rewards to the agent. Then we show that under some practical assumptions on the intermediate states and  simple conditions on the intermediate rewards, hierarchical RL is indeed more computationally efficient for learning a successful policy that guides the agent from the initial state to a terminal state. In particular, we study the computational efficiency for learning a successful policy in the sense of being able to complete the task. From a theoretical perspective, our results corroborate the computational benefits of hierarchical RL stated in <cit.>.

§.§ Motivating Examples

We first start with two examples (the Maze and the Pacman Game in Figure <ref>) to reveal the existence of hierarchical structures in different tasks. The Maze problem does not have a hierarchical structure, as its configuration remains unchanged during an episode. In contrast, the Pacman game intrinsically possesses hierarchical structures, because every time the Pacman consumes a food pellet, the configuration of the MDP changes irreversibly.

We conduct a toy experiment on the Pacman game to demonstrate how the design of intermediate states and intermediate rewards affects the behavior of an agent under the greedy policy <cit.>. In the Pacman game, the agent (Pacman) needs to consume all the food while avoiding the ghost. Intuitively, if we want the Pacman to win the game, we need to design the MDP such that the agent receives positive rewards for winning, consuming food, surviving (not being caught by the ghost), and negative rewards for losing (being caught by the ghost). With the aforementioned intuition, we design several different reward functions for the Pacman game. Comparing reward settings (1), (2), and (3) in Table <ref>, the Pacman performs better when the MDP contains positive intermediate rewards for consuming food. This observation matches the common belief that integrating prior knowledge of the task into the MDP design is generally helpful. However, incorporating “too much” prior knowledge could negatively affect the performance. In setting (4), where the Pacman receives a positive reward for survival, the Pacman focuses more on dodging the ghost rather than consuming food, and eventually gets caught by the ghost. At this point, a natural question is:

How does the design of intermediate rewards affect the behavior of a greedy policy in hierarchical MDPs?

[step=1cm, gray, very thin] (0, -5) grid (6, 0);
[blue!20!white] (0.5, -0.5) circle (0.3cm);
[green!20!white] (5.5, -4.5) circle (0.3cm);

[black, line width=1.5] (0.0, 0.0) – (6.0, 0.0) – (6.0, -4.0);
[black, line width=1.5] (6.0, -5.0) – (0.0, -5.0) – (0.0, -1.0);
[black, line width=1.5] (2.0, 0.0) – (2.0, -1.0) – (1.0, -1.0) – (1.0, -3.0);
[black, line width=1.5] (1.0, -4.0) – (2.0, -4.0) – (2.0, -2.0) – (3.0, -2.0) – (3.0, -5.0);
[black, line width=1.5] (4.0, 0.0) – (4.0, -3.0);
[black, line width=1.5] (3.0, -1.0) – (4.0, -1.0);
[black, line width=1.5] (5.0, -1.0) – (6.0, -1.0);
[black, line width=1.5] (6.0, -1.0) – (5.0, -1.0) – (5.0, -4.0);
[black, line width=1.5] (4.0, -4.0) – (4.0, -5.0);

[cyan!80!black, line width=1.0, dashed, ->] (0.5, -0.8) – (0.5, -3.5) – (1.5, -3.5) – (1.5, -1.5) – (3.5, -1.5) – (3.5, -3.5) – (4.5, -3.5) – (4.5, -4.5) – (5.2, -4.5);

Bounding Box
[black] (6.5,0) – (6.5,-2) – (8.5,-2) – (8.5,0) – cycle;

[blue!20!white] (7.0, -0.5) circle (0.3cm);
[green!20!white] (7.0, -1.5) circle (0.3cm);

[right, font=] (A) at (7.3,-0.5) Start;
[right, font=] (B) at (7.3,-1.5) End;

[step=1cm, gray, very thin] (0, -5) grid (6, 0);

[green!30!white] (1.5, -1.5) circle (0.2cm);
[green!30!white] (1.5, -3.5) circle (0.2cm);
[green!30!white] (4.5, -1.5) circle (0.2cm);
[green!30!white] (4.5, -3.5) circle (0.2cm);
[fill=yellow!95!black,rotate around=45:(0.5,-0.5)] (0.5,-0.5) – (0.8,-0.5) arc (0:270:0.3cm);
[fill=blue] (0,0.1) – (0,0.5) arc (+180:0:0.3) – (0.6,0.1) –
(0.5,0.15) – (0.4,0.1) – (0.3,.15) – (0.2,0.1) – (0.1,.15) – cycle;

in 0.17,0.43
[white] (,0.5) circle[radius=0.1];
[black] (-0.02,0.52) circle[radius=0.05];

[black, line width=1.5] (0.0, 0.0) – (6.0, 0.0) – (6.0, -5.0) – (0.0, -5.0) – cycle;
[black, line width=1.5] (2.0, -1.0) – (3.0, -1.0) – (3.0, -4.0) – (2.0, -4.0) – cycle;

[black] (6.5,0) – (9.0,0) – (9.0,-3) – (6.5,-3) – cycle;
[right, font=] (A) at (7.3,-0.5) Pacman;
[right, font=] (B) at (7.3,-1.5) Ghost;
[right, font=] (C) at (7.3,-2.5) Foods;
[fill=yellow!95!black,rotate around=45:(7.0,-0.5)] (7.0,-0.5) – (7.3,-0.5) arc (0:270:0.3cm);
[fill=blue] (0,0.1) – (0,0.5) arc (+180:0:0.3) – (0.6,0.1) –
(0.5,0.15) – (0.4,0.1) – (0.3,.15) – (0.2,0.1) – (0.1,.15) – cycle;
in 0.17,0.43
[white] (,0.5) circle[radius=0.1];
[black] (,0.52) circle[radius=0.05];

[green!30!white] (7.0, -2.5) circle (0.2cm);

Examples of two practical tasks. The thick curves represent walls. The agent can take actions from {left, right, up, down} and move to the corresponding adjacent locations. The agent stays at the original location if it hits a wall after taking an action. (a): In the maze problem, each state in the MDP is the agent's position. The goal is to find the end from the start. The shortest path is marked with blue dashed curves. (b): In the Pacman game, each state contains the position of the Pacman, the ghost, and all remaining food pellets. The agent (Pacman) needs to consume all the pellets while avoiding the ghost and each food pellet can only be eaten once. The ghost moves simultaneously with the Pacman. The Pacman wins once all pellets are consumed and loses if it is caught by the ghost. We use the TikZ code from <https://gist.github.com/neic/9546556> to draw the ghost.

1c0 ep     1c100 eps     1c500 eps     1c1000 eps     1c1500 eps     1c2000 eps     1c2500 eps

(1)     0     0     0.0%     0.1%     0.1%     0.6%     89.5%     93.7%     96.0%

(2)     1     0     0.0%     0.5%     33.0%     78.0%     92.6%     97.8%     98.4%

(3)     10     0     0.0%     0.1%     57.8%     93.6%     95.7%     97.0%     97.9%

(4)     1     1     0.0%     0.0%     1.9%     2.5%     2.2%     7.7%     12.9%

The win rate (averaged among 1000 trials) of the Pacman game shown in Figure <ref> after $\{0, 100, 500, 1000, 1500, 2000, 2500 \}$ Q-learning training episodes under a greedy policy. We compare the performance under 4 different reward function designs. In all settings, the winning reward is 10 and the losing reward is -10. $r_f$ is the reward of consuming a food pellet. The Pacman receives a survival reward $r_s$ if it is not caught by the ghost after taking an action. Our implementation of the Pacman is based on the code from Berkeley CS188 (<https://inst.eecs.berkeley.edu/ cs188/ fa18/project3.html>). Details of the experiments are provided in Appendix <ref>.

§.§ Our Formulation and Main Results

To study the conditions under which hierarchical RL problems with intermediate rewards enjoy computational benefits, as demonstrated in setting (2) and (3) of the Pacman game in Table <ref> in Section <ref>, we consider two MDP settings (shown in Figure <ref>): 1) one-way single-path (OWSP) and 2) one-way multi-path (OWMP). In both settings, we assume the existence of  states that behave like “one-way” checkpoints that cannot be revisited. Intermediate rewards are assigned to the arrival at such states. Many practical RL tasks implicitly adopt this one-way property as practitioners often identify sub-goals and assign a one-time reward for their completion in solving challenging tasks. For the case where intermediate states are not one-way, we provide an example where the agent gets stuck at an intermediate state permanently instead of pursing the terminal states, if the intermediate rewards are not “properly” designed. As we observed in setting (4) of the Pacman game in Table <ref>, improperly designed intermediate rewards can negatively affect the agent's ability to find a successful policy.

[fill=white] (0.5, 0.5) circle (0.3cm);
[below,font=] at (0.5,0) $s_0$;
[black] (1, 0.6) – (1.8, 1.2);
[black] (1, 0.4) – (1.8, -0.2);
[font=] at (2.5,1.2) $\dots$;
[font=] at (2.5,0.65) $\vdots$;
[font=] at (2.5,-0.2) $\dots$;
[->,black] (3.2, 1.2) – (4, 0.6);
[->,black] (3.2, -0.2) – (4, 0.4);
[fill=white] (4.5, 0.5) circle (0.3cm);
[below,font=] at (4.5,0) $s_{i_1}$;

[black] (5, 0.6) – (5.8, 1.2);
[black] (5, 0.4) – (5.8, -0.2);
[font=] at (6.5,1.2) $\dots$;
[font=] at (6.5,0.65) $\vdots$;
[font=] at (6.5,-0.2) $\dots$;
[->,black] (7.2, 1.2) – (8, 0.6);
[->,black] (7.2, -0.2) – (8, 0.4);

[fill=white] (8.5, 0.5) circle (0.3cm);
[below,font=] at (8.5,0) $s_{i_2}$;

[font=] at (10.5,0.5) $\dots$;
[fill=white] (12.5, 0.5) circle (0.3cm);
[below,font=] at (12.5,0) $s_{i_N}$;
[->,black] (9, 0.5) – (9.8, 0.5);
[->,black] (11.2, 0.5) – (12, 0.5);

[black] (13.0, 0.6) – (13.8, 1.2);
[black] (13.0, 0.4) – (13.8, -0.2);
[font=] at (14.5,1.2) $\dots$;
[font=] at (14.5,0.65) $\vdots$;
[font=] at (14.5,-0.2) $\dots$;
[fill=white] (16.5, 0.5) circle (0.3cm);
[fill=white] (16.5, 0.5) circle (0.2cm);
[below,font=] at (16.5,0) $\mc S_{T^+}$;
[->,black] (15.2, 1.2) – (16.0, 0.6);
[->,black] (15.2, -0.2) – (16.0, 0.4);

In this case, all intermediate states $\mc S_I=\{s_{i_1},s_{i_2},\dots,s_{i_N}\}$ have to be visited in a certain order.

[fill=white] (0.5, 0.5) circle (0.3cm);
[below,font=] at (0.5,0) $s_0$;
[black] (1, 0.6) – (1.8, 1.5);
[black] (1, 0.4) – (1.8, -0.5);
[font=] at (2.5,1.5) $\dots$;
[font=] at (2.5,0.65) $\vdots$;
[font=] at (2.5,-0.5) $\dots$;
[->,black] (3.2, 1.5) – (4, 1.5);
[->,black] (3.2, -0.5) – (4, -0.5);
[fill=white] (4.5, 1.5) circle (0.3cm);
[below,font=] at (4.5,1.0) $s_{i_{j_1}}$;
[fill=white] (4.5, -0.5) circle (0.3cm);
[below,font=] at (4.5,-1.0) $s_{i_{j^\prime_1}}$;

[black] (5, 1.6) – (5.8, 2.2);
[black] (5, 1.4) – (5.8, 0.8);
[font=] at (6.5,2.2) $\dots$;
[font=] at (6.5,1.65) $\vdots$;
[font=] at (6.5,0.8) $\dots$;
[->,black] (7.2, 2.2) – (8, 1.6);
[->,black] (7.2, 0.8) – (8, 1.4);

[fill=white] (8.5, 1.5) circle (0.3cm);
[below,font=] at (8.5,1.0) $s_{i_{j_2}}$;

[black] (5, -0.4) – (5.8, 0.2);
[black] (5, -0.6) – (5.8, -1.2);
[font=] at (6.5,0.2) $\dots$;
[font=] at (6.5,-0.35) $\vdots$;
[font=] at (6.5,-1.2) $\dots$;
[->,black] (7.2, 0.2) – (8, -0.4);
[->,black] (7.2, -1.2) – (8, -0.6);

[fill=white] (8.5, -0.5) circle (0.3cm);
[below,font=] at (8.5,-1.0) $s_{i_{j^\prime_2}}$;

[black] (9, 1.5) – (9.8, 1.5);
[->,black] (11.2, 1.5) – (12, 1.5);
[font=] at (10.5,1.5) $\dots$;
[fill=white] (12.5, 1.5) circle (0.3cm);
[below,font=] at (12.5,1.0) $s_{i_{j_m}}$;

[font=] at (10.5,0.65) $\vdots$;

[black] (9, -0.5) – (9.8, -0.5);
[->,black] (11.2, -0.5) – (12, -0.5);
[font=] at (10.5,-0.5) $\dots$;
[fill=white] (12.5, -0.5) circle (0.3cm);
[below,font=] at (12.5,-1.0) $s_{i_{j^\prime_{m^\prime}}}$;

[black] (13.0, 1.5) – (13.8, 1.5);
[font=] at (14.5,1.5) $\dots$;
[font=] at (14.5,0.65) $\vdots$;
[black] (13.0, -0.5) – (13.8, -0.5);
[font=] at (14.5,-0.5) $\dots$;
[below,font=] at (16.5,0) $\mc S_{T^+}$;
[->,black] (15.2, 1.5) – (16.0, 0.6);
[->,black] (15.2, -0.5) – (16.0, 0.4);
[fill=white] (16.5, 0.5) circle (0.3cm);
[fill=white] (16.5, 0.5) circle (0.2cm);

In this case, only a subset of intermediate states $\mc S_J = \{s_{i_{j_1}},s_{i_{j_2}},\dots,s_{i_{j_m}}\}$ (or $\mc S_{J^\prime} = \{s_{i_{j^\prime_1}},s_{i_{j^\prime_2}},\dots,s_{i_{j^\prime_{m^\prime}}}\}$) with at least $n$ states ($m,m^\prime\geq n$) have to be visited in a certain order.

The transition graph of different settings in Assumption <ref>

The OWSP Setting.
Intuitively, the OWSP setting, which rewards the one-way checkpoints in addition to terminal rewards is more computationally efficient than only having terminal rewards, because the OWSP setting reduces the problem from finding the terminal states to finding the closest intermediate states. For example, consider the environment provided in Figure <ref>, the number of value iterations required to obtain a greedy successful policy using sparse terminal rewards equals 8 steps (the distance or minimum required steps from the initial state $s_0$ to the terminal state $\mc S_T$), whereas the OWSP intermediate reward setting (Figure <ref>) reduces such computational complexity to 3 (the maximum distance between two intermediate states). The computational complexity (for obtaining a successful policy) using sparse terminal rewards and the OWSP intermediate reward settings are formalized in Proposition <ref> and <ref>, respectively. In addition, Proposition <ref> and <ref> show that the greedy policy finds the shortest path to $\mc S_T$ in both sparse terminal rewards and OWSP intermediate reward setting.

[step=1cm, gray, very thin] (0, -4) grid (4, 0);
[blue!20!white] (0.5, -0.5) circle (0.3cm);
[green!20!white] (3.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (2.8,-1.2) – (2.8,-1.8) – (2.2,-1.8) – cycle;
[fill=cyan!20!white] (1.2,-2.2) – (1.8,-2.8) – (1.2,-2.8) – cycle;

[font=] (a11) at (0.5,-0.5) $0$;
[font=] (a12) at (1.5,-0.5) $0$;
[font=] (a13) at (2.5,-0.5) $0$;
[font=] (a14) at (3.5,-0.5) $0$;
[font=] (a21) at (0.5,-1.5) $0$;
[font=] (a22) at (1.5,-1.5) $0$;
[font=] (a23) at (2.5,-1.5) $0$;
[font=] (a24) at (3.5,-1.5) $0$;
[font=] (a31) at (0.5,-2.5) $0$;
[font=] (a32) at (1.5,-2.5) $0$;
[font=] (a33) at (2.5,-2.5) $0$;
[font=] (a34) at (3.5,-2.5) $0$;
[font=] (a41) at (0.5,-3.5) $0$;
[font=] (a42) at (1.5,-3.5) $0$;
[font=] (a43) at (2.5,-3.5) $0$;
[font=] (a44) at (3.5,-3.5) $0$;

[font=] (a) at (2.0,-4.5) $k=0$;

[black, line width=1.5] (0.0, 0.0) – (4.0, 0.0) – (4.0, -4.0) – (0.0, -4.0) – cycle;
[black, line width=1.5] (3.0, 0.0) – (3.0, -1.0) – (2.0, -1.0);
[black, line width=1.5] (0.0, -1.0) – (1.0, -1.0) – (1.0, -2.0) – (2.0, -2.0);
[black, line width=1.5] (2.0, -3.0) – (4.0, -3.0);

[step=1cm, gray, very thin] (5, -4) grid (9, 0);
[blue!20!white] (5.5, -0.5) circle (0.3cm);
[green!20!white] (8.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (7.8,-1.2) – (7.8,-1.8) – (7.2,-1.8) – cycle;
[fill=cyan!20!white] (6.2,-2.2) – (6.8,-2.8) – (6.2,-2.8) – cycle;

[font=] (b11) at (5.5,-0.5) $0$;
[font=] (b12) at (6.5,-0.5) $0$;
[font=] (b13) at (7.5,-0.5) $0$;
[font=] (b14) at (8.5,-0.5) $0$;
[font=] (b21) at (5.5,-1.5) $0$;
[font=] (b22) at (6.5,-1.5) $0$;
[font=] (b23) at (7.5,-1.5) $0$;
[font=] (b24) at (8.5,-1.5) $0$;
[font=] (b31) at (5.5,-2.5) $0$;
[font=] (b32) at (6.5,-2.5) $0$;
[font=] (b33) at (7.5,-2.5) $0$;
[font=] (b34) at (8.5,-2.5) $0$;
[font=] (b41) at (5.5,-3.5) $0$;
[font=] (b42) at (6.5,-3.5) $0$;
[font=] (b43) at (7.5,-3.5) $B$;
[font=] (b44) at (8.5,-3.5) $0$;

[font=] (b) at (7.0,-4.5) $k=1$;

[black, line width=1.5] (5.0, 0.0) – (9.0, 0.0) – (9.0, -4.0) – (5.0, -4.0) – cycle;
[black, line width=1.5] (8.0, 0.0) – (8.0, -1.0) – (7.0, -1.0);
[black, line width=1.5] (5.0, -1.0) – (6.0, -1.0) – (6.0, -2.0) – (7.0, -2.0);
[black, line width=1.5] (7.0, -3.0) – (9.0, -3.0);

[step=1cm, gray, very thin] (10, -4) grid (14, 0);
[blue!20!white] (10.5, -0.5) circle (0.3cm);
[green!20!white] (13.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (12.8,-1.2) – (12.8,-1.8) – (12.2,-1.8) – cycle;
[fill=cyan!20!white] (11.2,-2.2) – (11.8,-2.8) – (11.2,-2.8) – cycle;

[font=] (c11) at (10.5,-0.5) $0$;
[font=] (c12) at (11.5,-0.5) $0$;
[font=] (c13) at (12.5,-0.5) $0$;
[font=] (c14) at (13.5,-0.5) $0$;
[font=] (c21) at (10.5,-1.5) $0$;
[font=] (c22) at (11.5,-1.5) $0$;
[font=] (c23) at (12.5,-1.5) $0$;
[font=] (c24) at (13.5,-1.5) $0$;
[font=] (c31) at (10.5,-2.5) $0$;
[font=] (c32) at (11.5,-2.5) $\gamma^2B$;
[font=] (c33) at (12.5,-2.5) $0$;
[font=] (c34) at (13.5,-2.5) $0$;
[font=] (c41) at (10.5,-3.5) $\gamma^2 B$;
[font=] (c42) at (11.5,-3.5) $\gamma B$;
[font=] (c43) at (12.5,-3.5) $B$;
[font=] (c44) at (13.5,-3.5) $0$;

[font=] (c) at (12.0,-4.5) $k=2$;

[black, line width=1.5] (10.0, 0.0) – (14.0, 0.0) – (14.0, -4.0) – (10.0, -4.0) – cycle;
[black, line width=1.5] (13.0, 0.0) – (13.0, -1.0) – (12.0, -1.0);
[black, line width=1.5] (10.0, -1.0) – (11.0, -1.0) – (11.0, -2.0) – (12.0, -2.0);
[black, line width=1.5] (12.0, -3.0) – (14.0, -3.0);

[step=1cm, gray, very thin] (16, -4) grid (20, 0);
[blue!20!white] (16.5, -0.5) circle (0.3cm);
[green!20!white] (19.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (18.8,-1.2) – (18.8,-1.8) – (18.2,-1.8) – cycle;
[fill=cyan!20!white] (17.2,-2.2) – (17.8,-2.8) – (17.2,-2.8) – cycle;

[font=] (d11) at (16.5,-0.5) $\gamma^7 B$;
[font=] (d12) at (17.5,-0.5) $\gamma^6 B$;
[font=] (d13) at (18.5,-0.5) $\gamma^7 B$;
[font=] (d14) at (19.5,-0.5) $\gamma^6 B$;
[font=] (d21) at (16.5,-1.5) $\gamma^4 B$;
[font=] (d22) at (17.5,-1.5) $\gamma^5 B$;
[font=] (d23) at (18.5,-1.5) $\gamma^4 B$;
[font=] (d24) at (19.5,-1.5) $\gamma^5 B$;
[font=] (d31) at (16.5,-2.5) $\gamma^3 B$;
[font=] (d32) at (17.5,-2.5) $\gamma^2 B$;
[font=] (d33) at (18.5,-2.5) $\gamma^3 B$;
[font=] (d34) at (19.5,-2.5) $\gamma^4 B$;
[font=] (d41) at (16.5,-3.5) $\gamma^2 B$;
[font=] (d42) at (17.5,-3.5) $\gamma B$;
[font=] (d43) at (18.5,-3.5) $B$;
[font=] (d44) at (19.5,-3.5) $0$;

[font=] (d) at (18.0,-4.5) $k=8$;

[black, line width=1.5] (16.0, 0.0) – (20.0, 0.0) – (20.0, -4.0) – (16.0, -4.0) – cycle;
[black, line width=1.5] (19.0, 0.0) – (19.0, -1.0) – (18.0, -1.0);
[black, line width=1.5] (16.0, -1.0) – (17.0, -1.0) – (17.0, -2.0) – (18.0, -2.0);
[black, line width=1.5] (18.0, -3.0) – (20.0, -3.0);

[font=] (c) at (15,-2) $\dots$;

[blue!20!white] (22.5, -0.5) circle (0.3cm);
[fill=cyan!20!white] (22.8,-1.2) – (22.8,-1.8) – (22.2,-1.8) – cycle;
[fill=cyan!20!white] (22.2,-2.2) – (22.8,-2.8) – (22.2,-2.8) – cycle;
[green!20!white] (22.5, -3.5) circle (0.3cm);

[right,font=] (A) at (21,-0.5) $s_0$;
[right,font=] (B) at (21,-1.5) $s_{i_1}$;
[right,font=] (C) at (21,-2.5) $s_{i_2}$;
[right,font=] (D) at (21,-3.5) $\mc S_{T}$;

[black] (21,0) – (21,-4) – (23,-4) – (23,0) – cycle;

An example of the evolution of a zero-initialized value function during synchronous value iteration in the one-way single-path (Assumption <ref> (a)) in sparse reward setting (Table <ref>). Each block in the $4\times4$ grid represents a state, the green state is the terminal state, the blue state is the initial state, and the thick curves represent walls that the agent cannot pass through. The cyan triangles are the one-way intermediate states. The orientation of the apex of a given cyan triangle represents the direction of each intermediate state. Namely, $s_{i_1}$ can only be visited from the left, and $s_{i_2}$ can only be visited from the right, and neither $s_{i_1}$ nor $s_{i_2}$ can be revisited. The agent can choose any action from $\{\text{left, right, up, down}\}$, and the agent will stay in the same state if it takes an action that hits the wall. Note that the value function of the terminal state remains 0 because the MDP stops once the agent reaches $\mc S_T$, so for any terminal state $s_t\in \mc S_T$, $V_k(s_t)$ is never updated.

[step=1cm, gray, very thin] (0, -4) grid (4, 0);
[blue!20!white] (0.5, -0.5) circle (0.3cm);
[green!20!white] (3.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (2.8,-1.2) – (2.8,-1.8) – (2.2,-1.8) – cycle;
[fill=cyan!20!white] (1.2,-2.2) – (1.8,-2.8) – (1.2,-2.8) – cycle;

[font=] (a11) at (0.5,-0.5) $0$;
[font=] (a12) at (1.5,-0.5) $0$;
[font=] (a13) at (2.5,-0.5) $0$;
[font=] (a14) at (3.5,-0.5) $0$;
[font=] (a21) at (0.5,-1.5) $0$;
[font=] (a22) at (1.5,-1.5) $0$;
[font=] (a23) at (2.5,-1.5) $0$;
[font=] (a24) at (3.5,-1.5) $0$;
[font=] (a31) at (0.5,-2.5) $0$;
[font=] (a32) at (1.5,-2.5) $0$;
[font=] (a33) at (2.5,-2.5) $0$;
[font=] (a34) at (3.5,-2.5) $0$;
[font=] (a41) at (0.5,-3.5) $0$;
[font=] (a42) at (1.5,-3.5) $0$;
[font=] (a43) at (2.5,-3.5) $0$;
[font=] (a44) at (3.5,-3.5) $0$;

[font=] (a) at (2.0,-4.5) $k=0$;

[black, line width=1.5] (0.0, 0.0) – (4.0, 0.0) – (4.0, -4.0) – (0.0, -4.0) – cycle;
[black, line width=1.5] (3.0, 0.0) – (3.0, -1.0) – (2.0, -1.0);
[black, line width=1.5] (0.0, -1.0) – (1.0, -1.0) – (1.0, -2.0) – (2.0, -2.0);
[black, line width=1.5] (2.0, -3.0) – (4.0, -3.0);

[step=1cm, gray, very thin] (5, -4) grid (9, 0);
[blue!20!white] (5.5, -0.5) circle (0.3cm);
[green!20!white] (8.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (7.8,-1.2) – (7.8,-1.8) – (7.2,-1.8) – cycle;
[fill=cyan!20!white] (6.2,-2.2) – (6.8,-2.8) – (6.2,-2.8) – cycle;

[font=] (b11) at (5.5,-0.5) $0$;
[font=] (b12) at (6.5,-0.5) $0$;
[font=] (b13) at (7.5,-0.5) $0$;
[font=] (b14) at (8.5,-0.5) $0$;
[font=] (b21) at (5.5,-1.5) $0$;
[font=] (b22) at (6.5,-1.5) $B_I$;
[font=] (b23) at (7.5,-1.5) $0$;
[font=] (b24) at (8.5,-1.5) $0$;
[font=] (b31) at (5.5,-2.5) $0$;
[font=] (b32) at (6.5,-2.5) $0$;
[font=] (b33) at (7.5,-2.5) $B_I$;
[font=] (b34) at (8.5,-2.5) $0$;
[font=] (b41) at (5.5,-3.5) $0$;
[font=] (b42) at (6.5,-3.5) $0$;
[font=] (b43) at (7.5,-3.5) $B$;
[font=] (b44) at (8.5,-3.5) $0$;

[font=] (b) at (7.0,-4.5) $k=1$;

[black, line width=1.5] (5.0, 0.0) – (9.0, 0.0) – (9.0, -4.0) – (5.0, -4.0) – cycle;
[black, line width=1.5] (8.0, 0.0) – (8.0, -1.0) – (7.0, -1.0);
[black, line width=1.5] (5.0, -1.0) – (6.0, -1.0) – (6.0, -2.0) – (7.0, -2.0);
[black, line width=1.5] (7.0, -3.0) – (9.0, -3.0);

[step=1cm, gray, very thin] (10, -4) grid (14, 0);
[blue!20!white] (10.5, -0.5) circle (0.3cm);
[green!20!white] (13.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (12.8,-1.2) – (12.8,-1.8) – (12.2,-1.8) – cycle;
[fill=cyan!20!white] (11.2,-2.2) – (11.8,-2.8) – (11.2,-2.8) – cycle;

[font=] (c11) at (10.5,-0.5) $0$;
[font=] (c12) at (11.5,-0.5) $\gamma B_I$;
[font=] (c13) at (12.5,-0.5) $0$;
[font=] (c14) at (13.5,-0.5) $0$;
[font=] (c21) at (10.5,-1.5) $0$;
[font=] (c22) at (11.5,-1.5) $B_I$;
[font=] (c23) at (12.5,-1.5) $\gamma B_I$;
[font=] (c24) at (13.5,-1.5) $0$;
[font=] (c31) at (10.5,-2.5) $0$;
[font=] (c32) at (11.5,-2.5) $0$;
[font=] (c33) at (12.5,-2.5) $B_I$;
[font=] (c34) at (13.5,-2.5) $\gamma B_I$;
[font=] (c41) at (10.5,-3.5) $0$;
[font=] (c42) at (11.5,-3.5) $\gamma B$;
[font=] (c43) at (12.5,-3.5) $B$;
[font=] (c44) at (13.5,-3.5) $0$;

[font=] (c) at (12.0,-4.5) $k=2$;

[black, line width=1.5] (10.0, 0.0) – (14.0, 0.0) – (14.0, -4.0) – (10.0, -4.0) – cycle;
[black, line width=1.5] (13.0, 0.0) – (13.0, -1.0) – (12.0, -1.0);
[black, line width=1.5] (10.0, -1.0) – (11.0, -1.0) – (11.0, -2.0) – (12.0, -2.0);
[black, line width=1.5] (12.0, -3.0) – (14.0, -3.0);

[step=1cm, gray, very thin] (15, -4) grid (19, 0);
[blue!20!white] (15.5, -0.5) circle (0.3cm);
[green!20!white] (18.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (17.8,-1.2) – (17.8,-1.8) – (17.2,-1.8) – cycle;
[fill=cyan!20!white] (16.2,-2.2) – (16.8,-2.8) – (16.2,-2.8) – cycle;

[font=] (c11) at (15.5,-0.5) $\gamma^2 B_I$;
[font=] (c12) at (16.5,-0.5) $\gamma B_I$;
[font=] (c13) at (17.5,-0.5) $\gamma^2 B_I$;
[font=] (c14) at (18.5,-0.5) $0$;
[font=] (c21) at (15.5,-1.5) $0$;
[font=] (c22) at (16.5,-1.5) $\alpha$;
[font=] (c23) at (17.5,-1.5) $\gamma B_I$;
[font=] (c24) at (18.5,-1.5) $\gamma^2 B_I$;
[font=] (c31) at (15.5,-2.5) $0$;
[font=] (c32) at (16.5,-2.5) $\gamma^2 B$;
[font=] (c33) at (17.5,-2.5) $B_I$;
[font=] (c34) at (18.5,-2.5) $\gamma B_I$;
[font=] (c41) at (15.5,-3.5) $\gamma^2 B$;
[font=] (c42) at (16.5,-3.5) $\gamma B$;
[font=] (c43) at (17.5,-3.5) $B$;
[font=] (c44) at (18.5,-3.5) $0$;

[font=] (c) at (17.0,-4.5) $k=3$;

[black, line width=1.5] (15.0, 0.0) – (19.0, 0.0) – (19.0, -4.0) – (15.0, -4.0) – cycle;
[black, line width=1.5] (18.0, 0.0) – (18.0, -1.0) – (17.0, -1.0);
[black, line width=1.5] (15.0, -1.0) – (16.0, -1.0) – (16.0, -2.0) – (17.0, -2.0);
[black, line width=1.5] (17.0, -3.0) – (19.0, -3.0);

[black] (20,0) – (20,-4) – (22,-4) – (22,0) – cycle;

[blue!20!white] (21.5, -0.5) circle (0.3cm);
[fill=cyan!20!white] (21.8,-1.2) – (21.8,-1.8) – (21.2,-1.8) – cycle;
[fill=cyan!20!white] (21.2,-2.2) – (21.8,-2.8) – (21.2,-2.8) – cycle;
[green!20!white] (21.5, -3.5) circle (0.3cm);

[right,font=] (A) at (20,-0.5) $s_0$;
[right,font=] (B) at (20,-1.5) $s_{i_1}$;
[right,font=] (C) at (20,-2.5) $s_{i_2}$;
[right,font=] (D) at (20,-3.5) $\mc S_{T}$;

An example of the evolution of a zero-initialized value function during synchronous value iteration in the one-way single-path (Assumption <ref> (a)) intermediate reward setting (Table <ref>). $\alpha=B_I+\gamma^2 B_I$, and the remaining settings are the same as Figure <ref>.

The OWMP Setting. Similar to the OWSP setting, the OWMP is more computationally efficient than using sparse terminal rewards, provided the conditions allow a greedy policy to recursively find the closest intermediate state and eventually reach the terminal state. Theorem <ref> and Theorem <ref> characterize such conditions and the associated computational complexity of finding a successful policy. Nevertheless, unlike the OWSP setting or the sparse terminal reward setting, such a policy does not necessarily find the shortest path from $s_0$ to $\mathcal{S}_T$. Our result in the OWMP setting illustrates a trade-off between the computational complexity and the pursuit of shortest path –  adding intermediate rewards based on prior knowledge generally reduces computational complexity, but it does not guarantee to find the shortest path.

Connections to Practice. We discuss how OWSP and OWMP settings connect to practical RL tasks in  Section <ref>. Moreover, we also provide extensive experiments in Section <ref> under both the OWSP and OWMP settings to demonstrate their computational benefits and OWMP's trade-off between computational complexity and the shortest path, using both traditional $\eps$-greedy Q-learning and popular deep RL methods such as DQN <cit.>, A2C <cit.>, and PPO <cit.>. Our results shed light on explaining the success of RL in large-scale planning tasks without suffering explosion in computational complexity.

§.§ Organization of this Paper

The rest of this paper is organized as follows. In Section <ref>, we introduce the basics of MDPs and the definition of successful policies. In Section <ref>, we provide the formal definition of intermediate states and some related assumptions (Section <ref>). We then discuss how these assumptions are well reflected in RL tasks observed in practice (Section <ref>). In Section <ref>, we separate hierarchical planning into different settings and provide the computational complexity of finding a successful trajectory for each setting in Section <ref>. In Section <ref>, we discuss the connection between the trajectory generated by a greedy policy and the shortest path for each setting. We then provide experimental results in Section <ref> to corroborate our theoretical results in Section <ref>. In Section <ref>, we discuss the connection between our work and some prior works, and the implication of our results. The proof and experimental details are deferred to the appendix.

§ BACKGROUND AND PROBLEM FORMULATION

§.§ Assumptions of the MDP

Basics of MDPs. We use a quintuple $\mc M = (\mc S,\mc A, P, r, \gamma)$ to denote an MDP, where $\mc S$ is a finite state space, $\mc A$ is a finite action space, $\gamma \in (0,1)$ is the discount factor, $r:(\mc S\times \mc A)\times \mc S \mapsto [0,\infty)$ is the reward function of each state-action pair $(s,a)$ and its subsequent state $s_a$, and $P$ is the probability transition kernel of the MDP, where $P(s_a|s,a)$ denotes the probability of the subsequent state $s_a$ of a state-action pair $(s,a)$. In particular, we focus on deterministic MDPs: the transition kernel satisfies $\forall (s,a)\in \mc S\times\mc A$, $\exists s_a\in \mc S$, such that $P(s_a|s,a)=1$ and reward function $r(s,a,s_a)$ only depends on the subsequent state $s_a$. We say a state $s^\prime$ is reachable from $s$ if there exists a path or a sequence of actions  $\{a_1,a_2,\dots,a_n\}$ that takes the agent from $s$ to $s^\prime$.[A similar definition of reachability appears in <cit.>.] Note that the definition of reachability does not necessarily imply $s$ is reachable from $s$, since there may not exist a path from $s$ to itself. Our model also considers a fixed initial state $s_0\in \mc S$ and terminal states $\mc S_T\subset \mc S$. Without further explanation, we assume the terminal state $\mc S_T$ is reachable from all $s\in \mc S$. All in all, MDP begins at state $s_0$ and stops once the agent reaches any state $s\in \mc S_T$.

Given an MDP $\mc M = (\mc S,\mc A, P, r, \gamma)$ with initial state $s_0\in \mc S$, $\forall s\in \mc S\backslash \mc S_T,s^\prime \in \mc S$, we define the distance $D(s,s^\prime): \mc S\times \mc S\mapsto \bb N$ as the minimum number of required steps $(\geq 1)$ from $s$ to $s^\prime$. We slightly abuse the notation of $D(\cdot,\cdot)$ by writing $D(s,\mc S_{T}) \doteq \underset{s^\prime \in \mc S_{T}}{\min} D(s,s^\prime)$ as the minimum distance from $s$ to $\mc S_{T}$.

§.§ Successful Q-functions for Planning Problems

In the preceding deterministic MDP formulation, we aim at solving a deterministic MDP planning problem <cit.>. Specifically, we adopt the Optimal Deterministic Planning setting suggested by <cit.>,[See the paragraph “Planning Problems in the AI Tradition” of Section 2.10.2 in <cit.>] where policies that lead the agent from $s_0$ to $\mc S_T$ are more favorable than those that do not, regardless of the total number of required actions. We say a Q-function is successful if its associated greedy policy <cit.> leads the agent to the terminal states $\mc S_T$ from the initial state $s_0$.

Given a deterministic MDP $\mc M = (\mc S,\mc A, P, r, \gamma)$, with initial state $s_0$. We say $Q(\cdot,\cdot)$ is a successful Q-function of $\mc M$ if the greedy policy with respect to $Q$ generates a path $\{s_0,a_0,s_1,a_1,\dots, s_H\}$ such that $\forall i = 0,1,\dots,H-1$, $s_i\notin \mc S_{T}$ and $s_H\in \mc S_{T}$.

All theoretical results of this work are based on synchronous value iteration:

\begin{equation}
\begin{split}
\label{eq:SyncValueIter}
V_{k+1}(s)&\doteq\max_{a\in \mc A}\left\{Q_k(s,a)\right\},\;\forall s\in \mc S,\\
Q_k(s,a) &= r(s,a,s_a)+\gamma V_k(s_a),\;\forall (s,a)\in \mc S\times \mc A.
\end{split}
\end{equation}

The convergence of synchronous value iteration has been well studied <cit.>, hence we use it as a starting point for studying the effect of intermediate states and intermediate rewards to be introduced later in Section <ref>.

§ INTERMEDIATE STATES AND INTERMEDIATE REWARDS

We now introduce the intermediate states and intermediate rewards. We begin with introducing the definition and related assumptions of intermediate states in Section <ref>. We also associate how the assumptions we make about intermediate states connect to practical applications in Section <ref>. Based on the definition of the intermediate state, we establish the sparse reward setting and the intermediate reward setting to be used for our theoretical results (Section <ref>) and experiments (Section <ref>) in Section <ref>.

§.§ Intermediate States

We state the formal definition of intermediate states in Definition <ref>, and provide two follow-up assumptions (Assumption <ref>, <ref>) regarding the intermediate states.

Given an MDP $\mc M = (\mc S,\mc A, P, r, \gamma)$ with initial state $s_0\in \mc S$ and terminal states $\mc S_{T}$, we define intermediate states set $\mc S_I = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}\subset \mc S\backslash \mc S_T$ as the states that satisfy

\begin{equation}
r(s,a,s_a)>0,\;\forall s_a\in \mc S_{I},
\end{equation}

where $s_a$ is the subsequent state of the state-action pair $(s,a)$.

[One-Way Intermediate States]

Given an MDP $\mc M = (\mc S,\mc A, P, r, \gamma)$ with initial state $s_0\in \mc S$, terminal states $\mc S_{T}$, and intermediate states $\mc S_I$, we assume that each intermediate state $s_{i_j}\in \mc S_{I}$ can only be visited at most once in one episode under any policy, namely, $\forall j\in [N],\;D(s_{i_j},s_{i_j})=\infty$.

Intuitively, Assumption <ref> characterizes the states that “irreversibly change the environment” in one episode, upon the agent's arrival. For example, in the Pacman game (Figure <ref>), if the agent (Pacman) reaches a location $(x,y)$ that contains a food pellet, then the whole environment changes irreversibly, because a food, once consumed, cannot appear again at $(x,y)$, unless the whole environment is reset. Similarly for the door & key environment <cit.> that will be presented in Section <ref>, once the agent picks up a key at location $(x,y)$, it possesses the key for the rest of that episode.
Assumption <ref> is widely adopted in practice, as many sub-goals identified by designers are usually one-way.

[Different Settings of Intermediate States]

Given an MDP $\mc M = (\mc S,\mc A, P, r, \gamma)$ with initial state $s_0\in \mc S$, intermediate states set $\mc S_I = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$ and terminal states $\mc S_{T}$ satisfying Assumption <ref>, we will be studying these different settings of $\mc S_I$:

* Any path from $s_0$ to $\mc S_{T}$ has to visit all states in $\mc S_I$ in a certain order (i.e., in the order of $s_{i_1},s_{i_2},\dots,s_{i_N}$).

* Any path from $s_0$ to $\mc S_{T}$ has to visit at least $n$ intermediate states $\{s_{i_j}|s_{i_j}\in \mc S_I,j\in \mc J \subset[N], |\mc J| \geq n \}$ in a certain order.

Assumptions <ref> and <ref> characterize intermediate states as different one-way paths consisting of hierarchical sub-goals that the agent has to complete in a certain order. If we consider all paths from $s_0$ to $\mc S_T$ that pass though the same intermediate states as an equivalence class, the MDP planning problem using setting (a) is a single-path problem, while setting (b) is a multi-path problem. Additionally, Assumption <ref> indicates that from a given state $s$, only a few intermediate states in $s_i\in\mc S_I$ can be directly visited (without first visiting any other intermediate states). Thus, it is worth considering the directly reachable intermediate (and terminal) states from a given state $s$ and the minimum distance between two intermediate states.

Given an MDP $\mc M = (\mc S,\mc A, P, r, \gamma)$ with terminal states $\mc S_{T}$ and intermediate states $\mc S_I = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$ satisfying Assumption <ref>, $\forall s \in \mc S\backslash\mc S_{T}$, let $\mc I_d(s)\subset [N]$ denote the indices of directly reachable intermediate states of $s$. That is, $\forall j\in \mc I_d(s)$, there exists a path from $s$ to the intermediate state $s_{i_j}$ in the transition graph of $\mc M$ that does not visit any other intermediate state.

Similar to the intermediate states $\mc S_I$, we say the terminal states $\mc S_T$ are directly reachable from a state $s$ if there exists a path from $s$ to $\mc S_T$ that does not contain any intermediate states.
[Minimum Distance Between Two Intermediate States]

Given an MDP $\mc M = (\mc S,\mc A, P, r, \gamma)$ with terminal states $\mc S_{T}$ and intermediate states set $\mc S_I = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$ satisfying Assumption <ref>, $\forall s\in \mc S\backslash\mc S_{T}$, we assume the distance between any two intermediate states is least $h \in \bb N^+$, and the distance between any intermediate state and $\mc S_{T}$ is also at least $h$. Namely, $\forall s_{i_j}\in \mc S_{I}$, we have

\begin{equation}
\min_{j^\prime \in \mc I_d(s_{i_j})} D(s_{i_j},s_{i_{j^\prime}}) \geq h,\; \text{ and } \min_{j \in [N]} D(s_{i_j},\mc S_{T}) \geq h,
\end{equation}

where $\mc I_d(s_{i_j})$ is the set of indices of directly reachable intermediate states from $s_{i_j}$ (see Definition <ref>).

In practice, although the minimum distance $h$ between two intermediate states (and an intermediate state to $\mc S_{T}$) is task dependent, it is generally fair to assume that $h$ satisfies $1<h<D(s_0,S_T)$.

§.§ The Interpretation of Intermediate States

We list several practical tasks that adopt Assumption <ref> in Table <ref> to interpret Assumption <ref>. Note that in many practical tasks, the designers usually construct the intermediate states and intermediate rewards based on their understanding of the tasks. As illustrated in Table <ref>, the multi-path intermediate state setting (Assumption <ref> (b)) is more common in practical tasks than the single-path setting (Assumption <ref> (a)), because the single-path setting is essentially a special case of the multi-path setting.

Assumption <ref>     (a)     (b)

Maze (Figure <ref>)

Pacman (Figure <ref>)

Montezuma (<cit.>)

Go (<cit.>)

Dota2 (<cit.>)

StarCraft II (<cit.>)

Honor of Kings (<cit.>)

Examples of some RL applications that adopt different settings in Assumption <ref>.

Assumption <ref> does not hold for the Maze (See Figure <ref>) because the agent can repeatedly visit any state in the maze. As for Go, Assumption <ref> also does not hold because the existence of hierarchical structures in Go remains ambiguous. Except for the Maze problem and Go, Assumption <ref> (b) fits the others practical tasks in Table <ref> naturally. Moreover, the stronger Assumption <ref> (a) holds for Montezuma because it requires the agent to vi sit specific states in a certain order, e.g., the agent will need to pick up a key and unlock a door to proceed to the next chapter. The Pacman game satisfies Assumption <ref> (b). If one views each state where “the Pacman consumes a food pellet” as an intermediate state, then each episode of the Pacman game contains $n$ (the total number of food) intermediate states, and these states appear in the order in which the number of available food is decreasing. As for Dota2, StarCraft II, and Honor of Kings, their winning conditions require the agent to “destroy” the enemy's base. However, the enemy's base is not assailable before the agent completes several subtasks. For example, in Dota2 or Honor of Kings, 3 towers block each of the roads to the enemy's base. The agent must first sequentially destroy the 3 towers to reach the enemy's base. [Information on the rules and gameplay of Dota are available online; i.e., <https://purgegamers.true.io/g/dota-2-guide/>. The rule of Honor of Kings is similar to Dota2.] If one views the state where the agent destroys a tower in Dota2 or Honor of Kings as an intermediate state, Assumption <ref> (b) is naturally satisfied, because the agent need to visit at least 3 intermediate states to attack the enemy's base.

§.§ Rewards

In our formulation, the reward function $r(s,a,s_a)$ of state-action pair $(s,a)$ only depends on the subsequent state $s_a$. In particular, our theoretical results (Section <ref>) and experiments (Section <ref>) will focus on comparing these two reward settings: the sparse reward setting where there are no intermediate states in the environment hence the agent only receives positive rewards at $\mc S_T$, and the intermediate reward setting, meaning that the environment contains intermediate states so the agent receives rewards at both $\mc S_T$ and $\mc S_I$. Formally, we write the reward functions of the sparse reward setting and the intermediate reward setting as follows:

1c     2cSparse Rewards     3cIntermediate Rewards

$r(s,a,s_a)$    $B$     $0$     $B$     $B_I$     0

Condition     $s_a\in \mc S_T$     $s_a\in \mc S\backslash \mc S_T$     $s_a\in \mc S_T$     $s_a\in \mc S_I$     $s_a\in \mc S\backslash (\mc S_T\cup \mc S_I)$

The sparse reward setting and the intermediate reward setting.

Note that in this work we only consider the intermediate reward setting in Table <ref> where all intermediate rewards have the same magnitude. Such setting matches the Pacman game, where we assign all food with equal intermediate rewards, but it does not reflect other the general hierarchical tasks mentioned in Section <ref>, whose intermediate rewards are usually different. Nevertheless, our theoretical results in Section <ref> relying on the equal magnitude of intermediate rewards can be further generalized to the case where intermediate rewards are different, and we would like to leave such generalization for future.

§ MAIN RESULTS

In this section, we study the conditions for both the sparse reward and intermediate reward setting, under which the Q-function $Q_k(\cdot,\cdot)$ is a successful Q-function (Definition (<ref>)), where $Q_k(\cdot,\cdot)$ is the Q-function after $k$ update of synchronous value iteration (<ref>) from zero initialization:
\begin{equation}
\label{eq:zero_init}
Q_0(s,a) = 0,\; V_0(s) = 0,\;\forall (s,a)\in \mc S\times\mc A.
\end{equation}

And if $Q_k(\cdot,\cdot)$ is indeed a successful Q-function, we further discuss the computational complexity $k$ (the minimum number of synchronous value iterations)
of obtaining a successful $Q_k(\cdot,\cdot)$.

For the sparse reward setting, we first show that for a large of enough $k$, $Q_k(\cdot,\cdot)$ is a successful Q-function and provide its computational complexity in Section <ref>. Next, we discuss these following MDP settings:

* The One-Way Single-Path (OWSP) setting: Assumption <ref> and Assumption <ref> (a) are satisfied;

* The One-Way Multi-Path (OWMP) setting: Assumption <ref> and Assumption <ref> (b) are satisfied;

* The Non One-Way (NOW) setting: Assumption <ref> is not satisfied.

For the OWSP setting, we show that $Q_k(\cdot,\cdot)$ is a successful Q-function for sufficiently large $k$ and provide its computational complexity in Section <ref>. For the OWMP setting, we introduce a sufficient condition under which $Q_k(\cdot,\cdot)$ is successful for a large enough $k$, and the corresponding computational complexity in Section <ref>. As for the NOW setting, we provide an example where $Q_k(\cdot,\cdot)$ is not successful for any $k$ in Section <ref>.

§.§ Sparse Rewards

Given zero-initialized value functions (<ref>), Figure <ref> demonstrates the evolution of $V_k(s)$ as the number of synchronous value iterations ($k$) increases. A direct implication of Figure <ref> is that, at iteration $k$, $\forall s\in \mc S\backslash \mc S_T$, given $d = D(s,\mc S_T)$, the value function $V_k(\cdot)$ satisfies:

\begin{equation}
\label{eq:SparseRewardValueMainText}
V_k(s) = \gamma^{d-1}B\cdot \indicator{d\leq k}.
\end{equation}

The derivation of (<ref>) is provided in Lemma <ref>. With (<ref>), we can expect that, when $k\geq D(s_0,\mc S_T)$, the value function at the initial state $V_k(s_0)$ would be positive. As a result, a greedy policy that recursively finds the next state with the largest value from $s_0$, will generate a path which eventually reaches $\mc S_T$, whenever $k\geq D(s_0,\mc S_T)$. More precisely, we have:

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with terminal states $\mc S_{T}$ and initial state $s_0$. If the reward function $r(\cdot)$ follows the sparse reward setting (Table <ref>) and the value function and Q-function are zero-initialized (<ref>), then after any $k\geq D(s_0,\mc S_{T})$  synchronous value iteration updates (<ref>), the Q-function $Q_k$ is a successful Q-function, and a greedy policy follows the shortest path from $s_0$ to $\mc S_T$.

We provide a sketch proof here and leave the details in Appendix <ref>. With (<ref>) from Lemma <ref>, we can write the value function in this setting as $V_k(s) = \gamma^{d-1}B\cdot\indicator{d\leq k}, d = D(s, \mathcal{S}_T)$. Hence a greedy policy taking the agent to the subsequent state with maximum value function will lead the agent one step closer to $\mc S_T$. Recursively applying the same argument, we conclude that after $k\geq D(s_0,\mc S_T)$ synchronous value iterations, an agent following the greedy policy finds $\mc S_T$ from $s_0$.

§.§ One-Way Single-Path  Intermediate Rewards

Similar to the sparse reward setting, we first illustrate the evolution of the one-way single-path (OWSP) intermediate rewards in Figure <ref>. The MDP environment provided in Figure <ref> indeed follows the one-way single-path setting, because all paths from $s_0$ to $\mc S_T$ must visit $s_{i_1}$, $s_{i_2}$ in that order. As shown in Figure <ref>, after $k$ synchronous iterations, the value function at each state $s$ equals to the sum of discounted rewards from all future intermediate states and the terminal states. The value function of each state at iteration $k$ is provided in Lemma <ref>. In this case, when $k$ satisfies

\begin{equation*}
k \geq \max\{D(s_0,s_{i_1}),D(s_{i_1},s_{i_2}),\dots, D(s_{i_{N-1}},s_{i_N}), D(s_{i_N},\mc S_{T})\},
\end{equation*}

$Q_k(\cdot,\cdot)$ is a successful Q-function and a greedy policy will recursively find the next intermediate state, eventually reaching $\mc S_T$. More precisely, we have:

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref> and <ref> (a). If the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>) and the value function and Q-function are zero-initialized (<ref>), then after

\begin{equation}
k\geq d_{\max}\doteq\max\{D(s_0,s_{i_1}),D(s_{i_1},s_{i_2}),\dots, D(s_{i_{N-1}},s_{i_N}), D(s_{i_N},\mc S_{T})\}
\end{equation}

synchronous value iteration updates (<ref>), the Q-function $Q_k$ is a successful Q-function, and a greedy policy follows the shortest path from $s_0$ to $\mc S_T$.

The proof of Proposition <ref> is similar to Proposition <ref>. We defer the details to Appendix <ref>. To outline, we provide an explicit formulation of $V_k(s)$ for this setting in Lemma <ref>, and show that when $k\geq d_{\max}$, the greedy policy will lead the agent one step forward to the next closest intermediate state and eventually reach $\mc S_T$.

Comparing to Proposition <ref>, we know that, the computational complexity (in terms of obtaining a successful Q-function) of an MDP $\mc M$ with the sparse reward setting can be reduced from $D(s_0,\mc S_T)$ to

\begin{equation*}
\max\{D(s_0,s_{i_1}),D(s_{i_1},s_{i_2}),\dots, D(s_{i_{N-1}},s_{i_N}), D(s_{i_N},\mc S_{T})\},
\end{equation*}

if $\mc M$ adopts the OWSP intermediate reward setting.

§.§ One-Way Multi-Path Intermediate Rewards

Unfortunately, as shown in Table <ref>, the intermediate states in many practical tasks are more complicated than the OWSP setting, as there may exist many different paths from $s_0$ to $\mc S_{T}$. Hence, it is worth studying a more practical setting, the one-way multi-path intermediate (OWMP) reward setting.

The intuition for the computational complexity of obtaining a successful Q-function in the OWMP setting is similar to the OWSP setting. For a state $s\in \mc S$, under some conditions regarding rewards $B$, $B_I$, and intermediate states $\mc S_I$, the greedy policy leads the agent to the closest directly reachable intermediate state $s_{i_{j_1}}$ of $s$ (Definition <ref>) for a sufficient number of value iterations $k$. From any intermediate $s_{i_{j_{m}}}\in \mc S_I$, the greedy policy takes the agent to the closest directly reachable intermediate state $s_{i_{j_{m+1}}}$ of $s_{i_{j_{m}}}$ and eventually reach $\mc S_{T}$, since intermediate states cannot be revisited and number of total intermediate states is finite.
The next theorem characterizes the sufficient condition for an agent starting from $s\in \mc S\backslash \mc S_T$ following a greedy policy to find the closest directly reachable intermediate of $s$.

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states  $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref>, <ref> (b), and <ref>, if the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>) and the value function and Q-function are zero-initialized (<ref>), then $\forall s \in \mc S\backslash\mc S_{T}$ that cannot directly reach $\mc S_{T}$, after

\begin{equation}
k\geq d = D(s,\mc S_{I}) \doteq \min_{j\in \mc I_d(s)}D(s,s_{i_j})
\end{equation}

synchronous value iteration updates (<ref>), an agent following the greedy policy will find the closest directly reachable intermediate state $s_{i_{j^\star}}$ of $s$ ($D(s,s_{i_{j^\star}}) = D(s,\mc S_{I})$), given  $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$ if $\gamma+\gamma^h\leq 1$ or $\frac{B}{B_I}\in\paren{\frac{1}{1-\gamma^h},\frac{1-\gamma}{\gamma^{1+h}}}$ if $\gamma+\gamma^h>1$, where $h$ is the minimum distance between any two intermediate states (Assumption <ref>).

Here we highlight some key insights of the proof and leave the details in Appendix <ref>. We first show that, when $k$ is not large ($k<D(s,\mc S_I)+h$), the value function $V_k(s)$ has the same property as the sparse reward setting provided in Proposition <ref>, namely, $V_k(s)$ increases as $D(s,\mc S_I)$ decreases. Then we show the monotonicity between $V_k(s)$ and $D(s,\mc S_I)$ still holds, $\forall k\geq D(s,\mc S_I)+h$, if the terminal reward $B$ and intermediate reward $B_I$ satisfy the condition mentioned in Theorem <ref>. With the monotonicity of $V_k(s)$ and $D(s,\mc S_I)$, we conclude a greedy policy leads the agent to find the closest intermediate state.

A direct implication of Theorem <ref> is that, when the magnitude of the terminal reward $B$ is not significantly larger than the intermediate reward $B_I$, $\forall s\in \mc S\backslash \mc S_{T}$, after $k\geq \underset{s\in \mc S\backslash \mc S_{T}}{\max}\underset{j\in \mc I_d(s)}{\min}D(s,s_{i_j})$ iteration of synchronous value iteration updates, the greedy policy leads the agent to an intermediate $s_{i_{j^\star}}$, from which $\mc S_{T}$ is directly reachable. The next theorem illustrates the condition under which an agent following the greedy policy will pursue the shortest path to $\mc S_{T}$, when $\mc S_{T}$ is directly reachable.

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states  $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref>, <ref> (b), and <ref>, the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>), and the value function, Q-function are zero-initialized (<ref>). $\forall s \in \mc S\backslash\mc S_{T}$, let

\begin{equation}
d = D(s,\mc S_{T}) \; \text{ and }\; d_I = D(s,\mc S_{I}) \doteq \min_{j\in \mc I_d(s)} D(s,s_{i_j}).
\end{equation}

If $\mc S_{T}$ is directly reachable from $s$, and $d$ and $d_I$ satisfy

\begin{equation}
d_I+\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}},&\text{ if }\;\frac{B}{B_I}<\frac{1}{1-\gamma^h},\\
d_I+\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}},&\text{ if }\;\frac{B}{B_I}\geq \frac{1}{1-\gamma^h},
\end{cases}
\;\text{ and }\; d<d_I+h-1,
\end{equation}

where $h$ is the minimum distance between two intermediate states (Assumption <ref>), then after $k\geq d$ synchronous value iteration updates (<ref>), an agent following the greedy policy will pursue the shortest path to $\mc S_{T}$.

The proof of Theorem <ref> has the same flavor as the proof of Theorem <ref>. We first provide an explicit expression of the value function $V_k(s)$ for $k\leq d_I+h$, in Lemma <ref>. Then we show the value function is monotonically decreasing as the distance $D(s,\mc S_T)$ increases for all $k\geq d$, when the conditions in Theorem <ref> are satisfied. Finally, we use the monotonicity of $V_k(s)$ to show that greedy policies find the shortest path to $\mc S_T$. The proof of Theorem <ref> is provided in Appendix <ref>.

Intuitively, Theorem <ref> indicates that, if a state $s$ is “close enough” to the terminal states $\mc S_T$, then the greedy policy will lead the agent from $s$ to $\mc S_T$ following the shortest path, given sufficient number of value iteration updates. Note that Theorem <ref> implicitly uses the fact that, in the OWMP setting, there could exist some states from which both $\mc S_I$ and $\mc S_T$ are directly reachable (see Figure <ref>).

All in all, when $B$ and $B_I$ satisfy the conditions in Theorem <ref> and when $k\geq \underset{s\in \mc S\backslash\mc S_T}{\max}\underset{j\in \mc I_d(s)}{\min}D(s,s_{i_j})$, an agent following the greedy policy will recursively find the closest directly reachable intermediate state, until the terminal state $\mc S_T$ is directly reachable. When $\mc S_T$ is directly reachable and $D(s,\mc S_T)$, $D(s,\mc S_I)$ satisfy the conditions provided in Theorem <ref>, the agent following the greedy policy will pursue the shortest path to $\mc S_T$. We shall clarify that our theoretical results (Theorem <ref> and <ref>) on the OWMP setting only provides sufficient conditions of obtaining successful Q-functions, but successful Q-functions can actually be obtained under broader conditions, as will be presented in Section <ref>.

§.§ Non One-Way Intermediate Rewards

The non one-way intermediate (NOW) reward setting refers to the traditional MDP planning problems <cit.>, where we do not have additional assumptions on the intermediate states. The theoretical results regarding general MDP planning is out of the scope of this work, as we mainly focus the cases where the intermediate states have hierarchical structures. Still, to demonstrate the effect of non-ideal reward design, we provide an example where synchronous value iteration never finds a successful Q-function in Example <ref>.

[Synchronous Value Iteration Fails to Output a Successful Q-function]

Suppose we are given an MDP environment as shown in Figure <ref>, with $B=10$, $B_I=100$, and $\gamma = 0.9$. The value function converges when $k\geq 2$. However, $\forall k \geq 1$, a greedy policy will stay in $s_i$ instead of moving to $\mc S_T$.

[step=1cm, gray, very thin] (0, -2) grid (2, 0);
[blue!20!white] (0.5, -0.5) circle (0.25cm);
[green!20!white] (1.5, -1.5) circle (0.25cm);

[cyan!20!white] (1.5, -0.5) circle (0.25cm);

[font=] (a11) at (0.5,-0.5) $0$;
[font=] (a12) at (1.5,-0.5) $0$;
[font=] (a21) at (0.5,-1.5) $0$;
[font=] (a22) at (1.5,-1.5) $0$;

[font=] (a) at (1.0,-2.5) $k=0$;

[black, line width=1.5] (0.0, 0.0) – (2.0, 0.0) – (2.0, -2.0) – (0.0, -2.0) – cycle;

[step=1cm, gray, very thin] (3, -2) grid (5, 0);
[blue!20!white] (3.5, -0.5) circle (0.25cm);
[green!20!white] (4.5, -1.5) circle (0.25cm);

[cyan!20!white] (4.5, -0.5) circle (0.25cm);

[font=] (b11) at (3.5,-0.5) $100$;
[font=] (b12) at (4.5,-0.5) $100$;
[font=] (b21) at (3.5,-1.5) $10$;
[font=] (b22) at (4.5,-1.5) $0$;

[font=] (b) at (4.0,-2.5) $k=1$;

[black, line width=1.5] (3.0, 0.0) – (5.0, 0.0) – (5.0, -2.0) – (3.0, -2.0) – cycle;

[step=1cm, gray, very thin] (6, -2) grid (8, 0);
[blue!20!white] (6.5, -0.5) circle (0.25cm);
[green!20!white] (7.5, -1.5) circle (0.25cm);

[cyan!20!white] (7.5, -0.5) circle (0.25cm);

[font=] (c11) at (6.5,-0.5) $100$;
[font=] (c12) at (7.5,-0.5) $100$;
[font=] (c21) at (6.5,-1.5) $90$;
[font=] (c22) at (7.5,-1.5) $0$;

[font=] (c) at (7.0,-2.5) $k=2$;

[black, line width=1.5] (6.0, 0.0) – (8.0, 0.0) – (8.0, -2.0) – (6.0, -2.0) – cycle;

[black] (9,0) – (9,-2.5) – (10.4,-2.5) – (10.4,0) – cycle;

[blue!20!white] (10, -0.5) circle (0.25cm);
[cyan!20!white] (10, -1.25) circle (0.25cm);
[green!20!white] (10, -2.0) circle (0.25cm);

[right,font=] (A) at (9.0,-0.5) $s_0$;
[right,font=] (B) at (9.0,-1.25) $s_{i}$;
[right,font=] (C) at (9.0,-2.0) $\mc S_{T}$;

An example of the evolution of a zero-initialized value function during synchronous value iteration in the non one-way intermediate reward setting, with $B=10$, $B_I=100$, and $\gamma = 0.9$. The agent may move left, right, up, or down. The cyan circle is the intermediate state that can be repeatedly visited from $s_0$ and from itself (by taking actions “right” and “up” and hitting a wall). The remaining settings are the same as Figure <ref>.

As shown in Example <ref>, if we set the intermediate rewards $B_I$ on some non one-way intermediate states, and when the intermediate rewards are significantly larger than the terminal rewards, a greedy policy will lead the agent to visit the intermediate states repeatedly rather than pursuing the terminal states. A direct implication from Example <ref> is that, to prevent an agent from staying at non one-way intermediate states, the intermediate rewards on these non one-way intermediate states should be relatively small.

§ CONNECTIONS TO FINDING THE SHORTEST PATH

In this section, we discuss the connection between the different reward settings (sparse reward, OWSP, OWMP, NOW in Section <ref>) and how they connect to finding the shortest path. Finding the shortest path is of particular interest because a shorter path is usually preferable in the Classical Deterministic Planning problems <cit.>. We will discuss how our theoretical results of different settings (sparse rewards, OWSP, and OWMP intermediate reward) connect to finding the shortest path as follows.

The Sparse Reward Setting.
The sparse reward setting requires no prior knowledge nor assumptions of the hierarchical structures of the tasks, because it contains no intermediate states. Hence, it can further be applied to non-hierarchical tasks. In addition, as illustrated in Proposition <ref>, the successful policy obtained by synchronous value iteration pursues the shortest path but at the cost of high computational complexity ($D(s_0,\mc S_T)$ synchronous value iteration). The computational complexity in the sparse reward setting motivates the use of intermediate rewards: practical tasks with well-designed intermediate rewards should be more computationally efficient than the same task with only sparse terminal rewards.

The OWSP Intermediate Reward Setting.
As mentioned in Section <ref>, the OWSP intermediate reward setting only applies to limited number of tasks seen in practice. However, when the tasks of interest indeed possess such hierarchical structures and the one-way intermediate states are clearly identified by the designers, Proposition <ref> shows that the computational complexity of obtaining a successful Q-function can be significantly reduced, and a greedy policy will find the shortest path from $s_0$ to $\mc S_T$.

The OWMP Intermediate Reward Setting. Theorem <ref> demonstrates that the OWMP setting also can reduce the computation complexity of obtaining a successful Q-function to  $\underset{s}{\max}\underset{j\in \mc I_d(s)}{\min}D(s,s_{i_j})$. Compared to the OWSP setting, the OWMP intermediate setting has much broader practical applications. Though the OWMP intermediate setting is more relevant, the downside is that generally a greedy policy with a successful Q-function will pursue the closest intermediate states instead of the shortest path to $\mc S_T$. The trade-off between computational complexity and achieving the shortest path is provided in Figure <ref>: A greedy policy reaches $\mc S_T$ when $k$ (the number of synchronous value iterations) equals 1 or 2, by recursively pursuing the closest intermediate state (path 1). When $k>2$ and the terminal rewards $B$ and intermediate rewards $B_I$ satisfy the conditions stated in Theorem <ref>, the greedy policy will find $\mc S_T$ via the shortest path (path 2).

[step=1cm, gray, very thin] (0, -4) grid (4, 0);
[blue!20!white] (0.5, -0.5) circle (0.3cm);
[green!20!white] (0.5, -3.5) circle (0.3cm);

[fill=cyan!20!white] (1.2,-0.2) – (1.8,-0.5) – (1.2,-0.8) – cycle;
[fill=cyan!20!white] (2.2,-0.2) – (2.8,-0.5) – (2.2,-0.8) – cycle;
[fill=cyan!20!white] (2.2,-0.2) – (2.8,-0.5) – (2.2,-0.8) – cycle;
[fill=cyan!20!white] (3.2,-0.2) – (3.8,-0.2) – (3.5,-0.8) – cycle;
[fill=cyan!20!white] (3.2,-1.2) – (3.8,-1.2) – (3.5,-1.8) – cycle;
[fill=cyan!20!white] (3.2,-1.2) – (3.8,-1.2) – (3.5,-1.8) – cycle;
[fill=cyan!20!white] (3.2,-2.2) – (3.8,-2.2) – (3.5,-2.8) – cycle;
[fill=cyan!20!white] (3.2,-3.5) – (3.8,-3.2) – (3.8,-3.8) – cycle;
[fill=cyan!20!white] (2.2,-3.5) – (2.8,-3.2) – (2.8,-3.8) – cycle;
[fill=cyan!20!white] (1.2,-3.5) – (1.8,-3.2) – (1.8,-3.8) – cycle;

[black, line width=1.5] (0.0, 0.0) – (4.0, 0.0) – (4.0, -4.0) – (0.0, -4.0) – cycle;
[black, line width=1.5] (1.0, -1.0) – (3.0, -1.0) – (3.0, -3.0) – (1.0, -3.0) – cycle;

[cyan!80!black, line width=0.75, dashed, ->] (0.8, -0.5) – (3.5, -0.5) – (3.5, -3.5) – (0.8, -3.5);
[green!80!black, line width=0.75, dashed, ->] (0.5, -0.8) – (0.5, -3.2);

[black] (5,0) – (5,-4) – (9,-4) – (9,0) – cycle;

[blue!20!white] (6.5, -0.5) circle (0.3cm);
[green!20!white] (8.5, -0.5) circle (0.3cm);
[fill=cyan!20!white] (6.2,-1.2) – (6.2,-1.8) – (6.8,-1.5) – cycle;
[fill=cyan!20!white] (7.2,-1.2) – (7.8,-1.2) – (7.5,-1.8) – cycle;
[fill=cyan!20!white] (8.8,-1.2) – (8.8,-1.8) – (8.2,-1.5) – cycle;
[cyan!80!black, line width=0.75, dashed, ->] (6.5, -2.5) – (8.5, -2.5);
[green!80!black, line width=0.75, dashed, ->] (6.5, -3.5) – (8.5, -3.5);

[right,font=] (A) at (5,-0.5) $s_0$;
[right,font=] (B) at (7,-0.5) $\mc S_{T}$;
[right,font=] (C) at (5,-1.5) $\mc S_I$;
[right,font=] (D) at (5,-2.5) Path 1;
[right,font=] (E) at (5,-3.5) Path 2;

The trade-off between the minimum computational complexity and the pursuit of the shortest path in the OWMP intermediate reward setting. The cyan isosceles triangles are the one-way intermediate states and the orientations of each
isosceles triangle represents the direction of each intermediate state – the agent at a given intermediate state can only visit the next state pointed by the orientation of the apex. The remaining settings are the same as Figure <ref>.

§ EXPERIMENT

We experimentally verify in several OpenAI Gym MiniGrid environments <cit.> that the agent is able to learn a successful trajectory more quickly in OWSP and OWMP intermediate reward settings than the sparse reward setting. We verify our findings on $\eps$-greedy asynchronous Q-learning algorithm, and three popular deep RL algorithms: DQN <cit.>, A2C <cit.>, and PPO <cit.>. For all experiments, the agent observes the whole environment. For asynchronous Q-learning, each state is represented as a string encoding of the grid. For deep RL algorithms, each state is an image of the grid. The detailed parameters and additional related experiments are provide in Appendix <ref>. See https://github.com/kebaek/minigridhttps://github.com/kebaek/minigrid for the code to run all presented experiments.

§.§ Environmental Setting

Single-Path Maze. The 7x7 grid maze (Figures <ref> and <ref>) consists of a single path that the agent must navigate through to reach the terminal state. This environment will be used to study the computational benefit of having well-designed intermediate rewards for the OWSP setting. See Figure <ref> for possible actions and reward design. Note that this maze environment is one-way since each intermediate reward may only be obtained once, i.e., the blue circle disappears from the environment once the agent reaches the corresponding square.

3-Door/4-Door. These 9x9 grid mazes (Figures <ref> and <ref>) consist of 3 different paths to to the terminal state each sealed by a series of locked doors. Each door has a corresponding key of the same color. The goal of the agent is to reach the terminal state by picking up the corresponding keys to unlock all the doors along at least one of the three paths. Note that this environment is one-way since a door cannot lock once unlocked and a key cannot be dropped once picked up. These environments will be used to study the computational benefit of having well-designed intermediate rewards and the trade-off between computational complexity and shortest path for the OWMP setting (Section <ref>).

Sparse reward

Intermediate reward

3-Door env.

4-Door env.

The red triangle is the agent and the green square is the terminal state. (a)-(b): The Single-Path Maze environment. Agent takes actions from {go forward, turn $90^\circ$, turn $-90^\circ$}. For the sparse reward setting (a), the agent receives a terminal reward of +10. For the intermediate reward setting (b), the agent also receives +1 for arriving at any square with a blue circle. (c)-(d): The Door-Key environments. Agent takes actions from {go forward, turn $90^\circ$, turn $-90^\circ$, pick up key, open door}. For the sparse reward setting of (c) and (d), the terminal reward is +10. For the intermediate reward setting of (c) and (d), the agent also receives +2 for picking up a key or opening a door. All rewards in environments (a)-(d) can only be obtained once per episode.

§.§ Results

On the Single-Path Maze environment and the 3-Door environment, we compare the number of training episodes required for the agent to find a successful policy in the sparse reward setting and the intermediate reward setting (See Figure <ref> and <ref> for more details about reward design).
For 0.8 $\eps$-greedy Q-learning, we train 100 independent models and evaluate each model once, for a total of 100 trials. For the deep RL algorithms, we train 10 independent models, and evaluate each model 10 times with different seeds, for a total of 100 trials. Win rate is computed as the number of trials that reach the terminal state out of 100.

As expected, we observe that it takes $\eps$-greedy Q-learning 36 episodes to reach a win rate of $100\%$ whereas in the sparse reward setting, $\eps$-greedy Q-learning is only able to reach a win rate of $10\%$ for the same number of episodes (See Table <ref>). Similarly for the 3-Door setting, if the agent is also rewarded for picking up keys and opening doors, significantly less training episodes are required to obtain a win rate of $100\%$ (See Table <ref>). We observe a similar phenomena on popular deep RL algorithms: DQN, A2C, and PPO (See Figure <ref>). Our experimental findings on the computational benefits of using intermediate rewards corroborate our theoretical claim in Section <ref>.

3c|Maze (Figure <ref> and <ref>)     3c3-Door (Figure <ref>)

# Episodes     Sparse     Intermediate     # Episodes     Sparse     Intermediate

18	    6/100    59/100     40    	3/100     90/100

24	    7/100    82/100     80     10/100     100/100

30	    6/100    95/100     120    	43/100     100/100

36	    10/100      100/100     160     74/100    100/100

Asynchronous Q-learning: Computational Complexity. We report the number of wins out of 100 trials (100 training sessions evaluated once each) after different training episodes for both the sparse reward and intermediate reward settings.

1c|     3c|Setting 1: +10     3cSetting 2: +1000

# Episodes     Wins     Rewards     Steps     Wins     Rewards     Steps

50     64/100    11.28 $\pm$ 2.08     95.52 $\pm$ 82.58      71/100     11.12 $\pm$ 2.30     84.39 $\pm$ 79.48

150     99/100     11.2 $\pm$ 2.03     24.71 $\pm$ 18.10     100/100     11.06 $\pm$ 1.99     22.53 $\pm$ 3.56

350     100/100     11.1 $\pm$ 1.93      22.65 $\pm$ 3.40     100/100     10.14 $\pm$ 2.60      20.88 $\pm$ 4.70

750     100/100     11.18 $\pm$ 1.80     22.85 $\pm$ 3.24     100/100     9.24 $\pm$ 2.85     19.39 $\pm$ 5.54

1550     100/100     11.64 $\pm$ 1.42     23.36 $\pm$ 2.62      100/100     5.52 $\pm$ 1.10     12.95 $\pm$ 1.64

3150     100/100     12.0 $\pm$ 0.0     24.0 $\pm$ 0.0     100/100     4.46 $\pm$ 0.84      12.23 $\pm$ 0.42

4-Door (Figure <ref>) Trade-Off for Asynchronous Q-Learning. We report the number of wins out of 100 trials (100 training sessions evaluated once each), averaged total intermediate rewards, and averaged number of steps taken after different training episodes. The agent receives a terminal reward of +10 in Setting 1 +1000 in Setting 2. The agent also receives +2 for picking up a key and +2 for opening a door in both settings. The episode maxes out at 324 steps.

Deep RL: Computational Complexity. We compare the average number of steps an agent takes to reach the terminal state in the Single-Path Maze and 3-Door environments between sparse versus intermediate reward settings. If the agent does not reach the terminal state, the episode maxes out at 324 steps for 3-Door and 196 steps for Single-Path Maze. The results are averaged over 100 trials (10 training sessions evaluated 10 times each)

On the 4-Door environment, we test two intermediate reward settings where the agent is either rewarded $10$ or $1000$ points for reaching the terminal state. Additionally, the agent is rewarded $2$ points for either picking up a key or opening a door. The shortest successful path to the terminal state (12 steps) has the least number of doors to unlock, thus less intermediate rewards, whereas the longest of the three paths to the terminal state contains at least 3 doors to unlock, thus more possible intermediate rewards to collect. We compare the average steps required during evaluation for the agent to reach the terminal state between these two settings. From Section <ref>, we expect that in this OWMP setting, the agent identifies the shortest successful path with Q-learning given a well-designed discount factor and a good ratio between intermediate/terminal rewards. For a discount factor of 0.9, we observe that if the terminal reward is $1000$, the path taken by an agent trained by $\eps$-greedy Q-learning converges to the shortest path of 12 steps. On the other hand, if the terminal reward is $10$, the path taken by the agent converges to that of 24 steps and on average collects more intermediate rewards (See Table <ref>). Similarly, with a discount factor of 0.8 for DQN and 0.9 for A2C and PPO, we observe that the agent chooses the shortest successful trajectory when rewarded $1000$ points for reaching the terminal state during training, and a longer successful trajectory with more intermediate rewards when rewarded $10$ points. Our experimental findings on the trade-off between computational efficiency and the shortest path corroborate our theoretical claim in Section <ref>.

Deep RL: Trade-Off. We compare the average number of steps an agent takes to reach the terminal state in the 4-Door environment if the terminal reward is $10$ versus $1000$. The agent also receives an intermediate reward of $2$ when it picks up a key or opens a door. If the agent does not reach the terminal state, the episode maxes out at 324 steps. The results are averaged over 100 trials (10 training sessions evaluated 10 times each)

§ RELATED WORKS AND DISCUSSION

Hierarchical Reinforcement Learning and Planning. Hierarchical reinforcement learning and planning are two fundamental problems that have been studied for decades <cit.> (See <cit.> for an overview of other earlier works on hierarchical RL and Chapter 11.2 in the book <cit.> for hierarchical planning). After the success of deep learning <cit.>, recent works have revisited hierarchical RL under the deep RL framework <cit.> (see Chapter 11 in the review paper <cit.> for other hierarchical deep RL literature). Prior theoretical attempts on hierarchical RL formulated the problem as MDP decomposition problems <cit.> or solving subtasks with “bottleneck” states <cit.>. Our result is closely related to <cit.> in the following two aspects: 1) Our one-way assumption (Assumption <ref>) on the intermediate states is similar to the exit state of subMDPs (Definition 1 in <cit.>), in the sense that our one-way intermediate states can be viewed as the exit states that separate the MDP into subMDPs; 2) Our quantitative results of different MDP settings suggest that partitioning the large MDP via intermediate states and intermediate rewards generally reduce the computational complexity, which corroborates the computational efficiency of subMDPs in <cit.>. Though we come to similar theoretical conclusions that intermediate rewards lead to reduced computational complexity, in this work, we simplify down the assumptions and build a theoretical framework that is well connected to practice.

Reward Design. With the recent success of deep learning <cit.>, RL has experienced a renaissance <cit.> and has demonstrated super-human performance in various applications <cit.>. The reward design varies from task to task. For example, in Go <cit.>, the agent only receives terminal rewards at the end of the game (+1 for winning and -1 for losing); for Starcraft II <cit.>, the reward function is usually a mixture win-loss terminal rewards (+1 on a win, 0 on a draw, and -1 on a loss) and intermediate rewards based on human data; for multiplayer online battle arena (MOBA) games <cit.>, the reward functions are generally heavily handcrafted (see Table 6 of <cit.> and Table 4 of <cit.>) based on prior knowledge. Besides task-dependent reward design, other works also have studied the reward design for general RL tasks <cit.> (See <cit.> and references therein; also see other literature in Chapter 5 of the review paper <cit.>).

Connection to Reward Shaping <cit.>.
For a given MDP $\mc M$ with reward function $r$, <cit.> proposed a potential-based shaping function $F$, such that the same MDP $\mc M$ with shaped reward $F+r$ has the same optimal policy as $\mc M$ with the original reward function $r$. Part of our result is related to reward shaping <cit.> in the sense that, when certain conditions are satisfied (Assumption <ref> (a)), greedy policies under the sparse reward setting and the intermediate reward setting are the same, as they both follow the shortest path from $s_0$ to $\mc S_T$. Comparing to reward shaping, the advantage of our work is also on the practical side – since the assumptions of the potential function $F$ is generally hard to satisfy. $F$ is usually approximated via neural networks in practice, which requires extra engineering efforts. On the contrary, as we have discussed in Section <ref> and Section <ref>, our assumptions on the one-way intermediate states (Assumption <ref>) and relative magnitude between intermediate rewards $B_I$ and terminal rewards $B$
can easily be implemented in practice.

Practical Implications. The practical implication of our work is that, in order to find a successful policy that leads the agent to the terminal states, adding intermediate rewards based on prior knowledge of the practical tasks is generally more computationally efficient than using sparse terminal rewards alone. But for most practical tasks, unless the intermediate rewards are carefully designed (e.g., like the OWSP setting described in Section <ref>), greedy policies usually do not follow the shortest path to the terminal states. To prevent the agent from getting stuck at at non one-way intermediate states (e.g., like the case discussed in Example <ref>), we can assign small rewards (compared to the terminal rewards) to non one-way intermediate states. As for the the one-way intermediate states (Assumption <ref>), we can assign relatively large intermediate rewards. Our findings corroborate the reward design of Dota2 (Table 6 of <cit.>): In Table 6 of <cit.>, one can understand the “Win” (with reward +5) as terminal states; “XP Gained” (with reward +0.002), “Gold Gained” (with reward +0.006), and “Gold Spent” (with reward +0.0006) as non one-way intermediate states;“T1 Tower” (with reward +2.25), “T2 Tower” (with reward +3), “T3 Tower” (with reward +4.5), “T4 Tower” (with reward +2.25), “Shrine” (with reward +2.25), and “Barracks” (with reward +6) as one-way intermediate states.

§ ACKNOWLEDGEMENTS

YZ would like to thank Haozhi Qi from UC Berkeley for insightful discussion on the implementations of practical deep RL tasks. CB would also like to thank Siddharth Verma from UC Berkeley for helpful discussions about deep RL algorithms. JJ acknowledges NSF Grants IIS-1901252 and CCF-1909499. YM acknowledges support from ONR grant N00014-20-1-2002 and the joint Simons
Foundation-NSF DMS grant #2031899, as well as support from Berkeley FHL Vive Center
for Enhanced Reality and Berkeley Center for Augmented Cognition. YZ and YM acknowledge support from Tsinghua-Berkeley Shenzhen Institute (TBSI) Research Fund.

§ EXTRA DEFINITION AND PROOF OF SECTION <REF>

§.§ Definition of Correct and Incorrect Actions

We introduce the definition of correct and incorrect actions to facilitate the future proof.

Let $s_a$ be the subsequent state the state-action pair $(s,a)$, we define the correct action set $\mc A^+(s)$ of a state $s\in \mc S\backslash \mc S_{T}$ as

\begin{equation}
\mc A^+(s) = \{a|a\in \mc A,D(s_a,\mc S_{T})=D(s,\mc S_{T})-1\}.
\end{equation}

Conversely, we can define the incorrect action set of a state $s\in \mc S$ as

\begin{equation}
\mc A^-(s) = \{a|a\in \mc A\backslash\mc A^+(s)\}.
\end{equation}

§.§ Proof of Proposition <ref>

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with terminal states $\mc S_{T}$ and initial state $s_0$. If the reward function $r(\cdot)$ follows the sparse reward setting (Table <ref>) and the value function and Q-function are zero-initialized (<ref>), then after any $k\geq D(s_0,\mc S_{T})$  synchronous value iteration updates (<ref>), the Q-function $Q_k$ is a successful Q-function, and a greedy policy follows the shortest path from $s_0$ to $\mc S_T$.

$\forall d\leq k$, let $\mc S^{d}$ denote the set of states that is distance $d$ to the desired terminal state $\mc S_{T}$, and let $a^{d+}\in \mc A^+(s^d)$, $a^{d-}\in \mc A^-(s^d)$ denote a correct action and an incorrect action of $s^d$, respectively. From Lemma <ref>, we know that

\begin{equation*}
V_k(s^d) = \begin{cases}
\gamma^{d-1}B, & \forall k,d\in \bb N^+, d\leq k,\\
0, & \text{ otherwise}.\\
\end{cases}
\end{equation*}

Combine Lemma <ref> with the Q-function update in value iteration (<ref>):

\begin{equation*}
Q_k(s,a) = r(s,a,s_a)+\gamma V_k(s_a),\;\forall (s,a)\in \mc S\times \mc A,
\end{equation*}

we know that

\begin{align}
Q_{k}(s^d,a^{d+}) &\overset{(i)}{=}
\begin{cases}
\gamma^{d-1}B,&\text{ if }d\leq k,\\
0,&\text{ otherwise},
\end{cases}\label{eq:Qk+_induction_SR}\\
Q_{k}(s^d,a^{d-}) &\overset{(ii)}{\leq}
\begin{cases}
\gamma^{d}B,&\text{ if }d\leq k,\\
0,&\text{ otherwise},
\end{cases} \label{eq:Qk-_induction_SR}
\end{align}

where inequality $(ii)$ holds since Definition <ref> implies that $D(s_{a^{d-}}^{d},\mc S_{T})\geq D(s,\mc S_{T})$. We shall clarify equality $(i)$ for the case when $d=1$: in this case, $V_k(s) = 0$ always holds $\forall s\in \mc S_{T}$ because given a state-action pair $(s,a)$, the MDP stops once the subsequent state $s_a\in \mc S_{T}$, hence we have

\begin{equation}
Q_k(s^1,a^{1+}) = r(s^1,a^{1+},s^1_{a^{1+}})+\gamma V_k(s^1_{a^{1+}}) = B.
\end{equation}

Since $\gamma<1$, we know that

\begin{equation}
\label{eq:Qk-<Qk+_SR}
Q_{k}(s^d,a^{d-})<Q_k(s^d,a^{d+}),\;\forall k\geq d,
\end{equation}

which implies

\begin{equation}
\underset{a\in \mc A}{\arg\max}\;Q_k(s^d,a)\in \mc A^+(s^d),\;\forall k\geq d.
\end{equation}

Now consider $s_0$, let $d_m = D(s_0,\mc S_{T})$, (<ref>) implies that any greedy action is a correct action:

\begin{equation}
a_0 = \underset{a}{\arg\max}\; Q_k(s_0,a)\in \mc A^+(s_0), \;\forall k\geq d_m
\end{equation}

By Definition <ref>, the subsequent state $s_{1}$ of state-action pair $(s_0,a_0)$ has distance at most $d_m$ $(D(s_1,\mc S_{T})\in [d_m-1,d_m])$ to $\mc S_{T}$, again (<ref>) implies that

\begin{equation}
a_1 = \underset{a}{\arg\max}\; Q_k(s_1,a)\in \mc A^+(s_1).
\end{equation}

Likewise, we know that the greedy policy generates a trajectory $\{s_0,a_0,s_1,a_1,\dots\}$, such that

\begin{equation}
\label{eq:greedy_action_correct_STR}
a_i = \underset{a}{\arg\max}\; Q_k(s_i,a)\in \mc A^+(s_i),
\end{equation}

which eventually ends up with a state $s_n\in \mc S_{T}$, since Definition <ref> indicates that $s_{i+1}$ is one step closer to $\mc S_{T}$ than $s_{i}$. Hence, we conclude that $Q_k$ is a successful Q-function. When $k\geq d$, since (<ref>) shows that every action taken by the greedy policy will take the agent one step closer to $\mc S_T$, we can also conclude that the greedy policy also pursues the shortest path from $s_0$ to $\mc S_T$.

§.§ Proof of Proposition <ref>

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref> and <ref> (a). If the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>) and the value function and Q-function are zero-initialized (<ref>), then after

\begin{equation}
k\geq d_{\max}\doteq\max\{D(s_0,s_{i_1}),D(s_{i_1},s_{i_2}),\dots, D(s_{i_{N-1}},s_{i_N}), D(s_{i_N},\mc S_{T})\}
\end{equation}

synchronous value iteration updates (<ref>), the Q-function $Q_k$ is a successful Q-function, and a greedy policy follows the shortest path from $s_0$ to $\mc S_T$.

The proof of this Proposition is a direct result of Lemma <ref>. Similar to Lemma <ref>, $\forall j\in [n+1]$, let $\mc S_{[j-1,j)}$ denote the sets

\begin{equation}
\mc S_{[j-1,j)} =
\begin{cases}
\{s\in \mc S|D(s,s_{i_{1}})<\infty\}& \text{ if } j = 1,\\
\{s\in \mc S|D(s,s_{i_{j}})=\infty,D(s,s_{i_{j+1}})<\infty\}& \text{ if } j = 2,3,\dots,N,\\
\{s\in \mc S|D(s,s_{i_{n}})=\infty,D(s,\mc S_{T})<\infty\}   & \text{ if } j = N+1.
\end{cases}
\end{equation}

For a state $s^{\mb d}\in \mc S_{[j-1,j)}$, let

\begin{equation}
\mb d = [d_j,d_{j+1},\dots,d_{n+1}]^\top\in \bb R^{n+1},
\end{equation}

where $d_l = D(s,s_{i_l}), \;\forall l=j,j+1,\dots, N$ and $ d_{N+1} = D(s,\mc S_{T})$, denote a vector whose entries are the distance from $s$ to intermediate states $s_{i_j}$ (and the terminal states $\mc S_{T}$). Let $a^{\mb d+}\in \mc A^+(s^{\mb d})$, $a^{\mb d-}\in \mc A^-(s^{\mb d})$ denote a correct and an incorrect action of $s^{\mb d}$. Combine Lemma <ref> with the Q-function update in value iteration (<ref>)

\begin{equation*}
Q_k(s,a) = r(s,a,s_a)+\gamma V_k(s_a),\;\forall (s,a)\in \mc S\times \mc A,
\end{equation*}

we know that

\begin{align}
&Q_{k}(s^{\mb d},a^{\mb d+})= \sum_{l=j}^{N+1} v(k,d_l)B_l=V_k(s),\\
&Q_{k}(s^{\mb d},a^{\mb d-})\overset{(i)}{\leq} \gamma\sum_{l=j}^{N+1}v(k,d_l)B_l=\gamma V_k(s),
\end{align}

\begin{equation}
\begin{cases}
\gamma^{d_l-1}, & \forall k,d\in \bb N^+, d_l\leq k+1,\forall l\in [N+1],\\
0, & \text{ otherwise},\\
\end{cases}
\;\text{ and }\;
B_l = \begin{cases}
B_I,&\text{ if }\; l\in [N],\\
B,&\text{ if }\; l = N+1,
\end{cases}
\end{equation}

and inequality $(i)$ holds because Definition <ref> implies $D(s_{a^{\mb d-}}^{\mb d},\mc S_{T})\geq D(s^{\mb d},\mc S_{T})$ and Assumption <ref> guarantees that previous intermediate states $s_{i_1},s_{i_2},\dots,s_{i_{j-1}}$ cannot be revisited. Since $\gamma<1$, notice that when $k\geq d_j$, we have

\begin{equation}
\label{eq:Qk-<Qk+_IR_a}
Q_k(s^{\mb d},a^{\mb d+})>Q_k(s^{\mb d},a^{\mb d-}),
\end{equation}

which implies

\begin{equation}
\underset{a\in \mc A}{\arg\max}\;Q_k(s^{\mb d+},a)\in \mc A^+(s^{\mb d}).
\end{equation}

Now consider $s_0$, since we assume that $k\geq d_{\max}$, therefore (<ref>) implies that the greedy action is a correct action:

\begin{equation}
a_0 = \underset{a}{\arg\max}\; Q_k(s_0,a)\in \mc A^+(s_0).
\end{equation}

By Definition <ref> and Assumption <ref>, we consider the following two cases:

* The subsequent state $s_{1}$ of state-action pair $(s_0,a_0)$ does not reach $s_{i_1}$, $(s_1\in \mc S_{[0,1)})$, then $s_1$ has distance at most $d_1$ to states $s_{i_1}$:

\begin{equation}
\begin{split}
D(s_1,s_{i_1})\in [d_{1}-1,d_{1}].
\end{split}
\end{equation}

Since $k\geq d_{\max}\geq d_1$, (<ref>) implies that the greedy action is a correct action:

\begin{equation}
a_1 = \underset{a}{\arg\max}\; Q_k(s_1,a)\in \mc A^+(s_1).
\end{equation}

* The subsequent state $s_{1}$ of state-action pair $(s_0,a_0)$ reaches $s_{i_1}$, $(s_1\in \mc S_{[1,2)})$, then $s_1$ has distance at most $d_2$ to states $s_{i_2}$:

\begin{equation}
\begin{split}
D(s_1,s_{i_2})&\in [d_{2}-1,d_{2}].
\end{split}
\end{equation}

Since $k\geq d_{\max}\geq d_2$, (<ref>) implies that the greedy action is a correct action:

\begin{equation}
a_1 = \underset{a}{\arg\max}\; Q_k(s_1,a)\in \mc A^+(s_1).
\end{equation}

Likewise, we know that greedy execution generates a trajectory $\{s_0,a_0,s_1,a_1,\dots\}$, such that

\begin{equation}
\label{eq:greedy_action_correct_OWSP}
a_i = \underset{a}{\arg\max}\; Q_k(s_i,a)\in \mc A^+(s_i),
\end{equation}

which eventually ends up with a state $s_n\in \mc S_{T}$, since Definition <ref> indicates that $s_{i+1}$ is one step closer to $\mc S_{T}$ than $s_{i}$. Hence, we conclude that $Q_k$ is a successful Q-function. When $k\geq d_{\max}$, since (<ref>) shows that every action taken by the greedy policy will take the agent one step closer to $\mc S_T$, we can also conclude that the greedy policy also pursues the shortest path from $s_0$ to $\mc S_T$.

§.§ Proof of Theorem <ref>

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states  $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref>, <ref> (b), and <ref>, if the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>) and the value function and Q-function are zero-initialized (<ref>), then $\forall s \in \mc S\backslash\mc S_{T}$, if $\mc S_{T}$ is not directly reachable from $s$, then after

\begin{equation}
k\geq d = D(s,\mc S_{I}) \doteq \min_{j\in \mc I_d(s)}D(s,s_{i_j})
\end{equation}

synchronous value iteration update (<ref>), an agent following the greedy policy will find the closest directly reachable intermediate state $s_{i_{j^\star}}$ of $s$ ($D(s,s_{i_{j^\star}}) = D(s,\mc S_{I})$), given that $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$ when $\gamma+\gamma^h\leq 1$ or $\frac{B}{B_I}\in\paren{\frac{1}{1-\gamma^h},\frac{1-\gamma}{\gamma^{1+h}}}$ when $\gamma+\gamma^h>1$, where $h$ is the minimum distance between two intermediate states (Assumption <ref>).

Recall the definition of directly reachable intermediate states (Definition <ref>) of state $s$: $\{s_{i_j},\;\forall j\in \mc I_d(s)\}$. $\forall s^\prime\in \mc S$, such that

\begin{equation}
\label{eq:dprime>d}
d^\prime = D(s^\prime,\mc S_I) = \min_{j\in \mc I_d(s^\prime)} D(s^\prime,s_{i_j})>d
\end{equation}

is the minimum distance from $s^\prime$ to its closest directly reachable intermediate state, it suffices to show $V_k(s)>V_k(s^\prime)$, since $V_k(s)>V_k(s^\prime)$ can directly lead to $Q_k(s,a_{i+})>Q_k(s,a_{i-})$:

\begin{equation}
\begin{split}
Q_{k}(s,a_{i+}) &\overset{(i)}{=} r(s,a_{i+},s_{a_{i+}}) + \gamma V_k(s_{a_{i+}}) \overset{(ii)}{>} \gamma V_k(s_{a_{i-}})\\
&\overset{(iii)}{=} r(s,a_{i-},s_{a_{i-}}) + \gamma V_k(s_{a_{i-}}) \overset{(iv)}{=} Q_{k}(s,a_{i-}),
\end{split}
\end{equation}

where $a_{i+}\in \mc A_I^+(s)$ is an action that leads to the closest directly reachable intermediate states of state $s$ and $a_{i-}\in \mc A_I^-(s)$ is the other actions that do not. Equality $(i)$ and $(iv)$ hold by the synchronous value iteration update (<ref>), inequality $(ii)$ holds since $D(s_{a_{i-}},\mc S_I)>D(s_{a_{i+}},\mc S_I)$ and we have assumed $V_k(s)>V_k(s^\prime)$ holds $\forall s,s^\prime$ such that $D(s^\prime,\mc S_I) > D(s,\mc S_I)$, and equality $(iii)$ holds because $s_{a_{i-}}$ is not an intermediate state. Moreover, if the agent at $s$ takes an action $a_{i+}$ and moves to $s_{a_{i+}}$, we will have

\begin{equation}
k\geq d-1 = D(s_{a_{i+}},s_{i_j})
\end{equation}

if $s_{a_{i+}}$ is not an intermediate state, which implies that the action given by the greedy policy will still lead $s_{a_{i+}}$ one step forward to the closest directly reachable intermediate states. Therefore, we only need to show $V_k(s)>V_k(s^\prime),\forall s,s^\prime$ such that $D(s^\prime,\mc S_I)>D(s,\mc S_I)$, which will be our main focus in the remaining proof.

When $d<k<d+h$.
In this case, all intermediate rewards are the same (all equal to $B_I$), Lemma <ref> implies that

\begin{equation}
V_k(s) = v(k,d)B_I,\; \forall k<d+h,
\end{equation}

where $d = D(s,\mc S_I)$ and

\begin{equation}
\begin{cases}
\gamma^{d-1}, & d\leq k,\\
0, & \text{ otherwise}.\\
\end{cases}
\end{equation}

Proposition <ref> implies that the agent will find a path to the closest intermediate state $s_{i_{j^\star_0}}$:

\begin{equation}
D(s,s_{i_{j^\star_0}}) = D(s,\mc S_I),
\end{equation}

\begin{equation}
V_k(s) = \gamma^{d-1}B_I > \gamma^dB_I \geq V_k(s^\prime).
\end{equation}

When $k\geq d + h$.
To complete this theorem, we need to show that, when $k\geq d+h$, $V_k(s)>V_k(s^\prime)$ still holds. Let $\pi$ be any deterministic policy and suppose under policy $\pi$, the agent starting from $s^\prime$ will visit the sequence of intermediate states before reaching $\mc S_{T}$:

\begin{equation}
\{s_{i_{j^\star_0}},s_{i_{j^\star_1}},\dots,s_{i_{j^\star_{u^\pi}}},s_{i_{j^\star_{u^\pi+1}}}\},
\end{equation}

where we slightly abuse the notation by assuming $s_{i_{j^\star_{u^\pi+1}}}\in \mc S_{T}$. Hence, the discounted reward $V_k^\pi(s^\prime)$ starting from state $s^\prime$ following policy $\pi$ satisfies

\begin{equation}
\begin{split}
\label{eq:discounted_value_upperbound}
V_k^\pi(s^\prime) \leq \underbrace{\gamma^{d^\prime-1}B_I + \brac{ \sum_{l=1}^{u^\pi}\gamma^{d_l-1} }B_I+\gamma^{d_{u^\pi + 1}-1}B}_{\Gamma(\pi)},
\end{split}
\end{equation}

\begin{equation}
\label{eq:dist_bound}
d_l = D(s^\prime,s_{i_{j^\star_0}})+\sum_{m=0}^{l-1}D(s_{i_{j^\star_m}},s_{i_{j^\star_{m+1}}})\overset{(i)}{\geq}d^\prime+lh,\;\forall l = 1,2,\dots, u^\pi+1,
\end{equation}

where inequality $(i)$ hold because of Assumption <ref>. Hence, we know that

\begin{equation}
\Gamma(\pi) = \gamma^{d^\prime-1}B_I + \brac{ \sum_{l=1}^{u^\pi}\gamma^{d_{l}-1} }B_I+\gamma^{d_{u^\pi + 1}-1}B\overset{(ii)}{\leq}\underbrace{\gamma^{d^\prime-1}\brac{\sum_{l=0}^{u^\pi}\gamma^{l h}}B_I+\gamma^{d^\prime+(u^\pi + 1) h-1}B}_{f(u^\pi)},
\end{equation}

where inequality $(ii)$ holds because of (<ref>) and $\gamma<1$. By the synchronous value iteration update (<ref>), and (<ref>) the value function of any state $s,s^\prime$ satisfy:

\begin{equation}
\label{eq:discounted_value_approx}
\gamma^{d-1}B_I\leq V_k(s),\; V_k(s^\prime) = \max_\pi V_k^\pi(s^\prime)\leq \max_\pi f(u^\pi),
\end{equation}

Next we will show $\gamma^{d-1}B_I>f(u^\pi)$ holds $\forall \pi$, (which directly leads to $V_k(s)>V_k(s^\prime)$, for any policy from (<ref>), after taking the max over all policy $\pi$) under these two following conditions: 1) $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$ when $\gamma+\gamma^h\leq 1$; 2) $\frac{B}{B_I}\in\paren{\frac{1}{1-\gamma^h},\frac{1-\gamma}{\gamma^{1+h}}}$ when $\gamma+\gamma^h>1$.

* When $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$ and $\gamma+\gamma^h\leq 1$.

Since $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$, we know that $B_I-(1-\gamma^h)B>0$, hence

\begin{equation}
\begin{split}
f(u^\pi) & < f(u^\pi) + \gamma^{d^\prime+(u^\pi + 1) h-1}\brac{B_I-(1-\gamma^h)B} \\
& = \gamma^{d^\prime-1}\brac{\sum_{l=0}^{u^\pi}\gamma^{l h}}B_I+\gamma^{d^\prime+(u^\pi + 1) h-1}B+\gamma^{d^\prime+(u^\pi + 1) h-1}\brac{B_I-(1-\gamma^h)B}\\
& = \gamma^{d^\prime-1}\brac{\sum_{l=0}^{u^\pi + 1}\gamma^{l h}}B_I+\gamma^{d^\prime+(u^\pi+2)h-1}B = f(u^\pi+1) <\dots < f(\infty) \\
& = \gamma^{d^\prime-1}\brac{\sum_{l=0}^\infty\gamma^{l h}}B_I = \frac{\gamma^{d^\prime-1}}{1-\gamma^h}B_I\overset{(i)}{\leq}\frac{\gamma^{d}}{1-\gamma^h}B_I\overset{(ii)}{\leq}\gamma^{d-1}B_I,
\end{split}
\end{equation}

where inequality $(i)$ holds because (<ref>) implies $d^\prime \geq d+1$, and inequality $(ii)$ holds because $\gamma+\gamma^h\leq 1$ implies that $\frac{\gamma}{1-\gamma^h}\leq 1$.

* When $\frac{B}{B_I}\in\left[\frac{1}{1-\gamma^h},\frac{1-\gamma}{\gamma^{1+h}}\right)$ and $\gamma+\gamma^h>1$.

When $\gamma+\gamma^h>1$, we know that the interval $\paren{\frac{1}{1-\gamma^h},\frac{1-\gamma}{\gamma^{1+h}}}$ is well defined as $\gamma+\gamma^h>1$ implies $\frac{1}{1-\gamma^h}<\frac{1-\gamma}{\gamma^{1+h}}$. Since $\frac{B}{B_I}>\frac{1}{1-\gamma^h}$, we know that $(1-\gamma^h)B-B_I>0$, hence

\begin{equation}
\begin{split}
f(u^\pi) & < f(u^\pi) + \gamma^{d^\prime+u^\pi h-1}\brac{(1-\gamma^h)B-B_I}\\
& = \gamma^{d^\prime-1}\brac{\sum_{l=0}^{u^\pi}\gamma^{l h}}B_I+\gamma^{d^\prime+(u^\pi + 1) h-1}B+\gamma^{d^\prime+u^\pi h-1} \brac{(1-\gamma^h)B-B_I}\\
&=\gamma^{d^\prime-1}\brac{\sum_{l=0}^{u^\pi-1}\gamma^{l h}}B_I+\gamma^{d^\prime+u^\pi h-1}B=f(u^\pi-1)<\dots<f(0)\\
&=\gamma^{d^\prime-1}B_I+\gamma^{d^\prime+h-1}B\overset{(i)}{\leq}\gamma^{d}B_I+\gamma^{d+h}B\overset{(ii)}{\leq}\gamma^{d-1} B_I.
\end{split}
\end{equation}

where inequality $(i)$ holds because (<ref>) implies $d^\prime \geq d+1$, and inequality $(ii)$ holds because $\frac{B}{B_I}\leq\frac{1-\gamma}{\gamma^{1+h}}$ implies that $\gamma B_I+\gamma^{1+h}B\leq B_I$.

Hence, we conclude that $f(u^\pi)<\gamma^{d-1}B_I,\forall \pi$, which leads to the result that $V_k(s)>V_k(s^\prime)$, $\forall k\geq d+h$ and $\forall s,s^\prime\in \mc S$ satisfying
(<ref>). This result indicates that we still have $V_k(s)>V_k(s^\prime)$ in the future update of synchronous value iteration. Therefore, we conclude that $V_k(s)>V_k(s^\prime),\forall s,s^\prime \in \mc S$ satisfying $D(s^\prime,\mc S_I)> D(s,\mc S_I)$, which completes the proof.

§.§ Proof of Theorem <ref>

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states  $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref>, <ref> (b), and <ref>, the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>), and the value function, Q-function are zero-initialized (<ref>). $\forall s \in \mc S\backslash\mc S_{T}$, suppose $\mc S_{T}$ is directly reachable from $s$, and let

\begin{equation}
d = D(s,\mc S_{T})\; \text{ and }\; d_I = D(s,\mc S_{I}) \doteq \min_{j\in \mc I_d(s)} D(s,s_{i_j}).
\end{equation}

If $d$ and $d_I$ satisfies:

\begin{equation}
\label{eq:d_cond_find_ST}
d_I+\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}},&\text{ if }\;\frac{B}{B_I}<\frac{1}{1-\gamma^h},\\
d_I+\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}},&\text{ if }\;\frac{B}{B_I}\geq \frac{1}{1-\gamma^h},
\end{cases}
\;\text{ and }\; d<d_I+h-1,
\end{equation}

where $h$ is the minimum distance between two intermediate states (Assumption <ref>), then after $k\geq d$ synchronous value iteration updates (<ref>), an agent following the greedy policy will pursue the shortest path to $\mc S_{T}$.

By the update of Q-function in the synchronous value iteration update (<ref>), it suffices to show

\begin{equation}
\label{eq:qk(s,a+)>qk(s,a-)ToST}
Q_k(s,a^+) = r(s,a^+,s_{a^+})+\gamma V_k(s_{a^+})>r(s,a^-,s_{a^-})+\gamma V_k(s_{a^-})=Q_k(s,a^-),
\end{equation}

when condition (<ref>) is satisfied. Lemma <ref> implies that when $k<d_I+h$, we have

\begin{equation}
V_k(s) = \max\{v(k,d_I)B_I,v(k,d)B\},
\end{equation}

\begin{equation}
\begin{cases}
\gamma^{d-1}, & \forall k,d\in \bb N^+, d\leq k,\\
0, & \text{ otherwise}.\\
\end{cases}
\end{equation}

Hence we will focus on proving (<ref>) in the remaining proof.

When $d\leq k<d_I+h-1$.
In this case, the conditions in (<ref>) first guarantee it exists a $k$ such that $d\leq k<d_I+h-1$. First, we will show both conditions

\begin{equation*}
d<d_I+\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}}\; \text{ and }\; d<d_I+\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}},
\end{equation*}

indicate that

\begin{equation}
\label{eq:v(k,d_I)B_I<v(k,d)B}
\gamma^{d_I}B_I<\gamma^dB.
\end{equation}

* For $d<d_I+\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}}$, we have

\begin{equation}
\begin{split}
&d-d_I<\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}} \iff\paren{\frac{1}{\gamma}}^{d-d_I}<(1-\gamma^h)\frac{B}{B_I}\\
\iff &\gamma^{d_I} B_I<(1-\gamma^h)\gamma^dB\implies\gamma^{d_I} B_I<\gamma^dB.
\end{split}
\end{equation}

* For $d<d_I+\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}}$, we have

\begin{equation}
\begin{split}
&d-d_I<\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}}\iff \paren{\frac{1}{\gamma}}^{d-d_I}<\frac{B}{B_I+\gamma^h B}\\
\iff& \gamma^{d_I}(B_I+\gamma^hB)<\gamma^dB\implies \gamma^{d_I} B_I<\gamma^dB.
\end{split}
\end{equation}

Now consider a correct action $a^+\in \mc A^+(s)$ and an incorrect action $a^-\in \mc A^-(s)$, we will next show

\begin{equation}
\label{eq:Qk(s,a+)_value_Q_k(s,a-)_upper_bound}
Q_k(s,a^+)=v(k,d)B,\; \text{ and }\; Q_k(s,a^-)\leq \max\{\gamma v(k,d_I-1)B_I,\gamma v(k,d)B\}.
\end{equation}

* For $Q_k(s,a^+)$, when $d=1$, we have

\begin{equation}
Q_k(s,a^+) = r(s,a,s_{a^+}) + \gamma V_k(s_{a^+}) \overset{(i)}{=} B = v(k,1)B,
\end{equation}

where equality $(i)$ holds because $s_{a^+}\in \mc S_{T}$, hence $r(s,a,s_{a^+}) = B$ and $V_k(s_{a^+}) = 0$.

When $d>1$, we have

\begin{equation}
Q_k(s,a^+) = r(s,a,s_{a^+}) + \gamma V_k(s_{a^+}) \overset{(ii)}{=} \gamma v(k,d-1)B \overset{(iii)}{=} v(k,d)B.
\end{equation}

Equality $(ii)$ holds because $r(s,a,s_{a^+}) = 0$ and Lemma <ref> implies $V_k(s_{a^+}) = v(k,d-1)B$. Equality $(iii)$ holds because when $k\geq d$, $\gamma v(k,d-1) = \gamma^{d-1}=v(k,d)$. Hence, we conclude that $Q_k(s,a^+) = v(k,d)B$.

* For $Q_k(s,a^-)$, consider these two following subsets of $\mc A^-(s)$: $a_{i+}^-\in \mc A^+_I(s)\cap\mc A^-(s)$ and $a_{i-}^-\in \mc A\backslash(\mc A^+_I(s)\cup\mc A^+(s))$, where $\mc A^+_I(s)$ is the set of actions that take state $s$ one step closer to $\mc S_I$:

\begin{equation}
% \label{eq:defAI+}
\mc A^+_I(s) \doteq \{a|a\in \mc A,D(s_a,\mc S_{I})=D(s,\mc S_{I})-1\},
\end{equation}

and $D(s,\mc S_{I})$ is defined as

\begin{equation}
D(s,\mc S_{I}) \doteq \min_{j\in \mc I_d(s)} D(s,s_{i_j}) = d_I.
\end{equation}

We will next show that

\begin{equation}
\label{eq:Qk(s,a-)_upper_bound}
\begin{split}
Q_k(s,a_{i+}^-)&\leq  \max\{\gamma v(k,d_I-1)B_I,\gamma v(k,d)B\},\;\forall a_{i+}^-\in \mc A_I^+(s)\cup \mc A^-(s),\\
Q_k(s,a_{i-}^-)&\leq \max\{\gamma v(k,d_I)B_I,\gamma v(k,d)B\},\;\forall a_{i-}^-\in \mc A\backslash(\mc A^+_I(s)\cup\mc A^+(s)).
\end{split}
\end{equation}

When $d_I=1$, we know that $s_{a_{i+}^-}\in \mc S_I$, hence $r(s,a_{i+}^-,s_{a_{i+}^-}) = B_I$. Moreover, when $k<d_I+h$, we have $V_k(s_{a_{i+}^-}) = 0$, this is because $V_0(s_{a_{i+}^-})$ is initialized as $0$ and it takes at least $h$ update of synchronous value iteration for $V_k(s_{a_{i+}^-})$ to be positive but $k<d_I+h-1 = h$. Hence, we know that

\begin{equation}
Q_k(s,a_{i+}^-) = B_I = \gamma v(k,0)B_I\leq \max\{\gamma v(k,0)B_I,\gamma v(k,d)B\}.
\end{equation}

As for $Q_k(s,a_{i-}^-)$, we have $r(s,a_{i-}^-,s_{a_{i-}^-}) = 0$ and $V_k(s_{a_{i-}^-})=\max\{v(k,d^\prime_I)B_I,v(k,d^\prime)B\}$, where

\begin{equation}
d^\prime_I = D(s_{a_{i-}^-},\mc S_I) \geq d_I,\;d^\prime = D(s_{a_{i-}^-},\mc S_{T}) \geq d.
\end{equation}

Hence, we have

\begin{equation}
\begin{split}
&Q_k(s,a_{i-}^-) = r(s,a_{i-}^-,s_{a_{i-}^-})+\gamma V_{k}(s_{a_{i-}^-})\\
\overset{(i)}{=}&\gamma\max\{v(k,d_I^\prime)B_I,v(k,d^\prime)B\}\leq\max\{\gamma v(k,1)B_I,\gamma v(k,d)B\},
\end{split}
\end{equation}

where equality $(i)$ holds by Lemma <ref>. Therefore, we conclude that (<ref>) holds when $d_I = 1$.

When $d_I>1$, we have $r(s,a_{i+}^-,s_{a_{i+}^-}) = 0$ and $r(s,a_{i-}^-,s_{a_{i-}^-}) = 0$. In this case, let $d^\prime = D(s_{a_{i-}^-},\mc S_{T})$, then

\begin{equation}
\begin{split}
&Q_k(s,a_{i+}^-) = r(s,a_{i+}^-,s_{a_{i+}^-})+\gamma V_k(s_{a_{i+}^-})\\
\overset{(i)}{=} &\gamma \max\{v(k,d_I-1)B_I,v(k,d^\prime)B\}\leq\max\{\gamma v(k,d_I-1)B_I,v(k,d)B\},
\end{split}
\end{equation}

where equality $(i)$ holds by Lemma <ref>. For $Q_k(s,a_{i-}^-)$, we have $r(s,a_{i-}^-,s_{a_{i-}^-}) = 0$ and $V_k(s_{a_{i-}^-})=\max\{v(k,d^{\prime}_I)B_I,v(k,d^{\prime\prime})B\}$, where

\begin{equation}
d^\prime_I = D(s_{a_{i-}^-},\mc S_I) \geq d_I,\;d^{\prime\prime} = D(s_{a_{i-}^-},\mc S_{T}) \geq d.
\end{equation}

Hence, we have

\begin{equation}
\begin{split}
&Q_k(s,a_{i-}^-) = r(s,a_{i-}^-,s_{a_{i-}^-})+\gamma V_{k}(s_{a_{i-}^-})\\
\overset{(i)}{=}&\gamma\max\{v(k,d_I^\prime)B_I,v(k,d^{\prime\prime})B\}\leq\max\{\gamma v(k,d_I)B_I,\gamma v(k,d)B\},
\end{split}
\end{equation}

where equality $(i)$ holds by Lemma <ref>. Therefore, we conclude that (<ref>) holds when $d_I > 1$.

A direct implication of (<ref>) is that

\begin{equation}
\begin{split}
\leq&\max\{\max\{\gamma v(k,d_I-1)B_I,\gamma v(k,d)B\},\max\{\gamma v(k,d_I)B_I,\gamma v(k,d)B\}\}\\
= &\max\{\gamma v(k,d_I-1)B_I,\gamma v(k,d)B\}.
\end{split}
\end{equation}

Therefore, we have shown (<ref>) for $d\leq k<d_I+h-1$. Hence, combine (<ref>) and (<ref>), we have

\begin{equation}
\begin{split}
Q_k(s,a^-)\overset{(i)}{\leq} & \max\{\gamma v(k,d_I-1)B_I,\gamma v(k,d)B\} \leq \max\{\gamma^{d_I-1}B_I,\gamma^dB\}\\
\leq&\max\{\gamma^{d_I-1}B_I,\gamma^{d-1}B\} \overset{(ii)}{=} \gamma^{d-1}B = v(k,d) = Q_k(s,a^+),
\end{split}
\end{equation}

where inequality $(i)$ follows (<ref>) and equality $(ii)$ holds due to (<ref>). Hence, know that a greedy action will select $a^+\in \mc A^+(s)$. If we let $d^\prime,d_I^\prime$ denote the distance between $s_{a^+}$ to $\mc S_{T}$ and $\mc S_{I}$, respectively, we have

\begin{equation}
d^\prime = D(s_{a^+}, \mc S_{T}) = d-1,\;d^\prime_I = D(s_{a^+}, \mc S_{I})\geq d_I-1,
\end{equation}

which implies $d^\prime$ and $d^\prime_I$ still satisfy (<ref>). Recursively applying the above argument, we conclude that a greedy policy will find the shortest path to $\mc S_{T}$, when $d\leq k<d_I+h-1$.

When $k\geq d_I+h-1$. To complete the theorem, we need to show when $k\geq d_I+h-1$, $Q_k(s,a^+)>Q_k(s,a^-)$ still holds. We have already shown that

\begin{equation*}
Q_k(s,a^+) = v(k,d)B = \gamma^{d-1}B,
\end{equation*}

when $d\leq k<d_I+h-1$, and the Q-function from the synchronous value iteration (<ref>) update is non-decreasing, hence when $k\geq d_I+h-1$, we know that $Q_k(s,a^+)\geq v(k,d) = \gamma^{d-1}B$ and it suffices to show that
$\gamma^{d-1}B\geq Q_k(s,a^-)$. Let $\pi$ be a deterministic policy and suppose the agent starting from $s$ will visit the following sequences of intermediate states before reaching $\mc S_{T}$ under policy $\pi$:

\begin{equation}
\label{eq:IS_sequence}
\{s_{i_{j^\star_0}},s_{i_{j^\star_1}},\dots,s_{i_{j^\star_{u^\pi}}},s_{i_{j^\star_{u^\pi+1}}}\},
\end{equation}

where we slightly abuse the notation by assuming $s_{i_{j^\star_{u^\pi+1}}}\in \mc S_{T}$. By the synchronous value iteration update (<ref>), the Q-function of state action pair $(s,a^-)$ under policy $\pi$ satisfies

\begin{equation}
\label{eq:discounted_Q_func}
Q^\pi_k(s,a^-) \leq \underbrace{\gamma^{d_I-1}B_I + \brac{ \sum_{l=1}^{u^\pi-1}\gamma^{d_l-1} }B_I+\gamma^{d_{u^\pi}-1}B}_{\Gamma(\pi)},
\end{equation}

\begin{equation}
\label{eq:dist_bound_for_Q}
\begin{split}
d_l &= D(s,s_{i_{j^\star_0}})+\sum_{m=0}^{l-1}D(s_{i_{j^\star_m}},s_{i_{j^\star_{m+1}}})\overset{(i)}{\geq}d_I+lh,\;\forall l = 1,2,\dots, u^\pi+1,
\end{split}
\end{equation}

where inequality $(i)$ holds because of Assumption <ref>. Hence, we know that

\begin{equation}
\Gamma(\pi) = \gamma^{d_I-1}B_I + \brac{ \sum_{l=1}^{u^\pi-1}\gamma^{d_{l}-1} }B_I+\gamma^{d_{u^\pi}-1}B\overset{(ii)}{\leq}\underbrace{\gamma^{d_I-1}\brac{\sum_{l=0}^{u^\pi-1}\gamma^{l h}}B_I+\gamma^{d_I+u^\pi h-1}B}_{f(u^\pi)},
\end{equation}

where inequality $(ii)$ holds because of (<ref>) and $\gamma<1$. By the synchronous value iteration update (<ref>), the Q-function of state action pair $(s,a^+)$ when $k\geq d_I+h-1$ satisfies $Q_k(s,a^+)\geq \gamma^{d-1}B$, and the Q-function of state action pair $(s,a^-)$ satisfies

\begin{equation}
Q_k(s,a^-) = \max_\pi Q_k^\pi(s,a^-)\leq \max_\pi f(u^\pi).
\end{equation}

Next we will show $\gamma^{d-1}B>f(u^\pi)$ holds $\forall \pi$ (which directly leads to $Q_k(s,a^+)>Q_k(s,a^-)$) in these following two conditions: 1) $d<d_I+\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}}$ when $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$; 2) $ d<d_I+\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}}$ when $\frac{B}{B_I}\geq \frac{1}{1-\gamma^h}$.

* When $d<d_I+\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}}$ and $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$.

Since $\frac{B}{B_I}\in \paren{0,\frac{1}{1-\gamma^h}}$, we know that $B_I-(1-\gamma^h)B>0$, hence

\begin{equation}
\begin{split}
f(u^\pi) & < f(u^\pi) + \gamma^{d_I+u^\pi h-1}\brac{B_I-(1-\gamma^h)B} \\
& = \gamma^{d_I-1}\brac{\sum_{l=0}^{u^\pi-1}\gamma^{l h}}B_I+\gamma^{d_I+u^\pi h-1}B+\gamma^{d_I+u^\pi h-1}\brac{B_I-(1-\gamma^h)B}\\
& = \gamma^{d_I-1}\brac{\sum_{l=0}^{u^\pi}\gamma^{l h}}B_I+\gamma^{d_I+(u^\pi+1)h-1}B = f(u^\pi+1) <\dots < f(\infty) \\
& = \gamma^{d_I-1}\brac{\sum_{l=0}^\infty\gamma^{l h}}B_I = \frac{\gamma^{d_I-1}}{1-\gamma^h}B_I\overset{(i)}{<}\gamma^{d-1}B,
\end{split}
\end{equation}

where the last inequality holds because $d<d_I+\log_{\frac{1}{\gamma}}\brac{(1-\gamma^h)\frac{B}{B_I}}$.

* When $ d<d_I+\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}}$ and $\frac{B}{B_I}\geq \frac{1}{1-\gamma^h}$.

When $\frac{B}{B_I}>\frac{1}{1-\gamma^h}$, we know that $(1-\gamma^h)B-B_I\geq0$, hence

\begin{equation}
\begin{split}
f(u^\pi) & < f(u^\pi) + \gamma^{d_I+(u^\pi-1)h-1}\brac{(1-\gamma^h)B-B_I}\\
& = \gamma^{d_I-1}\brac{\sum_{l=0}^{u^\pi-1}\gamma^{l h}}B_I+\gamma^{d_I+u^\pi h-1}B+\gamma^{d_I+(u^\pi-1)h-1} \brac{(1-\gamma^h)B-B_I}\\
&=\gamma^{d_I-1}\brac{\sum_{l=0}^{u^\pi-2}\gamma^{l h}}B_I+\gamma^{d_I+(u^\pi-1)h-1}B=f(u^\pi-1)<\dots<f(1)\\
&=\gamma^{d_I-1}B_I+\gamma^{d_I+h-1}B\overset{(i)}{\leq}\gamma^{d-1} B.
\end{split}
\end{equation}

where the last inequality holds because $ d<d_I+\log_{\frac{1}{\gamma}}\paren{\frac{B}{B_I+\gamma^hB}}$.

Hence, we conclude that $\gamma^{d-1}B>f(u^\pi),\forall \pi$. This result implies that a greedy action will select $a^+\in \mc A^+(s)$. If we let $d^\prime,d_I^\prime$ denote the distance between $s_{a^+}$ to $\mc S_{T}$ and $\mc S_{I}$, respectively, we will have

\begin{equation}
d^\prime = D(s_{a^+}, \mc S_{T}) = d-1,\;d^\prime_I = D(s_{a^+}, \mc S_{I})\geq d_I-1,
\end{equation}

which indicates that $d^\prime$ and $d^\prime_I$ still satisfy (<ref>). Recursively applying the above argument, we conclude that a greedy policy will find the shortest path to $\mc S_{T}$, when $k\geq d_I+h-1$. Combine this result with the case where $d\leq k<d_I+h-1$, we have shown that the greedy policy finds the shortest path to $\mc S_{T}$, after $k(k>d)$ synchronous value iteration update.

§ AUXILIARY LEMMAS

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with desired terminal states $\mc S_{T}$ and initial state $s_0$. If the reward function $r(\cdot)$ satisfies the sparse reward setting (Table <ref>) and the Q-function is zero-initialized (<ref>), $\forall d \in \bb N^+$, let $\mc S^{d}$ denote the set of states whose distance to the terminal state $\mc S_{T}$ is $d$:

\begin{equation*}
\mc S^{d} = \{s\in\mc S|D(s,\mc S_{T})=d\}.
\end{equation*}

Then $\forall k\in \bb N^+,\forall s^d\in \mc S^d$, $V_k(s^d)$ satisfies:

\begin{equation}
\label{eq:Value_it_induction_SR}
V_k(s^d) = \begin{cases}
\gamma^{d-1}B, & \forall k,d\in \bb N^+, d\leq k,\\
0, & \text{ otherwise}.\\
\end{cases}
\end{equation}

We will use induction to prove the results. Recall the synchronous value iteration update (<ref>):

\begin{equation*}
V_{k+1}(s)=\max_{a\in \mc A}\left\{r(s,a,s_a)+\gamma V_k(s_a)\right\},\;\forall s\in \mc S.
\end{equation*}

We first check the induction condition (<ref>) for the initial case $k=1$.

Initial Condition for $k=1$.
Since the agent only receives reward $r(s,a,s_a) = B$ when $s_a \in\mc S_{T}$, by the value iteration update, we have:

\begin{equation}
V_{1}(s) =
\begin{cases}
B, & \text{ if } s \in \mc S^1,\\
0, &\text{ otherwise},
\end{cases}
\end{equation}

hence, the initial condition is verified.

Next, suppose the condition (<ref>) holds for $1,2,\dots,k$, we will show it also holds for $k+1$. In this case, we only need to verify $V_{k+1}(s^{d})=\gamma^{k}B$ for $d = k+1$, because the induction assumption already implies

\begin{equation*}
V_{k+1}(s^d) = \begin{cases}
\gamma^{d-1}B, & \forall k,d\in \bb N^+, d\leq k,\\
0, & \text{ otherwise}.\\
\end{cases}
\end{equation*}

Note that when $d = k+1>1$, we have

\begin{equation}
r(s^{k+1},a,s^{k+1}_a) = 0,\;\forall a\in\mc A,\; \text{ and }\;V_{k}(s^{k+1}_a) \overset{(i)}{\leq} V_k(s^k) = \gamma^{k-1} B,
\end{equation}

where $s^{k+1}_{a}$ is the subsequent state of state-action pair $(s^{k+1},a)$, and inequality $(i)$ becomes equality if only if $a$ is a correct action $a\in \mc A^+(s)$ (see Definition <ref>). Hence, we know that

\begin{equation}
V_{k+1}(s^{k+1})=\max_{a\in \mc A}\left\{r(s^{k+1},a,s_a)+\gamma V_k(s^{k+1}_a)\right\}=\gamma^{k}B.
\end{equation}

As a result, we conclude that

\begin{equation*}
V_{k+1}(s^d) = \begin{cases}
\gamma^{d-1}B, & \forall k,d\in \bb N^+, d\leq k+1,\\
0, & \text{ otherwise},\\
\end{cases}
\end{equation*}

which completes the proof.

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref>, and <ref> (a), if the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>) and the Q-function is zero-initialized (<ref>), $\forall j \in [N+1]$, let $\mc S_{[j-1,j)}$ denote the set of states such that

\begin{equation}
\mc S_{[j-1,j)} =
\begin{cases}
\{s\in \mc S|D(s,s_{i_{1}})<\infty\}& \text{ if } j = 1,\\
\{s\in \mc S|D(s,s_{i_{j}})=\infty,D(s,s_{i_{j+1}})<\infty\}& \text{ if } j = 2,3,\dots,N,\\
\{s\in \mc S|D(s,s_{i_{N}})=\infty,D(s,\mc S_{T})<\infty\}   & \text{ if } j = N+1.
\end{cases}
\end{equation}

Given a state $s^{\mb d}\in \mc S^{\mb d}_{[j-1,j)}$, where $\mb d = [d_j,d_{j+1},\dots,d_N,d_{N+1}]^\top\in \bb R^{n-j+2}$ is a vector, such that $d_j<d_{j+1}<\dots<d_n<d_{N+1}$ denote the distance from $s^{\mb d}$ to $s_{i_j},s_{i_{j+1}},\dots,s_{i_N},\mc S_{T}$, respectively:

\begin{equation}
d_l = D(s^{\mb d},s_{i_l}),\;\forall l=j,j+1,\dots,n, \;\text{ and }\;d_{N+1} = D(s^{\mb d},\mc S_{T}).
\end{equation}

Then $\forall k\in \bb N^+,\forall s^{\mb d}\in \mc S^{\mb d}$, $V_k(s^{\mb d})$ satisfies the following conditions:

\begin{equation}
\label{eq:Value_it_induction_IR_a}
V_k(s^{\mb d}) = \sum_{l=j}^{N+1} v(k,d_l)B_l,
\end{equation}

\begin{equation}
\label{eq:Value_it_induction_IR_a_v(k,d)}
\begin{cases}
\gamma^{d_l-1}, & \forall k,d\in \bb N^+, d_l\leq k,\forall l\in [N+1],\\
0, & \text{ otherwise},\\
\end{cases}
\;\text{ and }\;
B_l = \begin{cases}
B_I,&\text{ if }\; l\in [N],\\
B,&\text{ if }\; l = N+1.
\end{cases}
\end{equation}

We will use induction to prove the results. Recall the synchronous value iteration update (<ref>):

\begin{equation*}
\begin{split}
V_{k+1}(s)&=\max_{a\in \mc A}\left\{r(s,a,s_a)+\gamma V_k(s_a)\right\},\;\forall s\in \mc S.\\
\end{split}
\end{equation*}

We first check the induction condition (<ref>) for the initial case $k=1$.

Initial Condition for $k=1$.
When $k=1$, the value function of states $s$ before reaching $s_{i_j}$ will not be affected by the rewards from $s_{i_{j+1}},s_{i_{j+2}},\dots,s_{i_{N}},\mc S_{T}$ and will only be updated using the intermediate reward from $s_{i_j}$. As similarly proven for the sparse reward case (Lemma <ref>), we have

\begin{equation}
V_{1}(s) =
\begin{cases}
B_{I_l}, & \text{ if }\;D(s, s_{i_l}) = 1,\forall l\in [N+1],\\
0, &\text{ otherwise},
\end{cases}
\end{equation}

which implies $V_1(s^{\mb d}) = \sum_{l=j}^{N+1} v(1,d_l)B_l$,
hence, the initial condition is verified.

Next, suppose the conditions (<ref>) hold for $1,2,\dots,k$, we will show they also hold for $k+1$. By the induction assumption, we know that

\begin{equation*}
V_k(s^{\mb d}) = \sum_{l=j}^{N+1} v(k,d_l)B_l,
\end{equation*}

holds for $1,2,\dots,k$, therefore we only need to show the induction condition (<ref>) holds when it exists $l^\prime\in \{j,j+1,\dots,N+1\}$, such that $d_{l^\prime}=k+1$, because $v(k,d_{l^\prime})$ remains the same, $\forall d_{l^\prime}\neq k+1$ when we change $k$ to $k+1$. Suppose $s^{\mb d}\in \mc S_{[j-1,j)}$ satisfies $D(s^{\mb d},s_{i_{l^\prime}}) = k+1$, since $d_{j}<d_{j+1}<\dots<d_{l^\prime} = k+1$, we will discuss these following cases.

* When $j < N+1$ and $l^\prime < N+1$. For a correct action $a^+\in \mc A^+(s^{\mb d})$, we have

\begin{equation}
\begin{split}
&r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+})\\
\begin{cases}
B_I+\gamma V_k(s^{\mb d}_{a^+})=B_I+\gamma\sum_{l=j+1}^{l^\prime-1}\gamma^{d_l-2}B_I+\gamma\cdot\gamma^{k-1}B,&\text{ if }\;d_j=1,\\
\gamma V_k(s_{a^+}^d) = \gamma \sum_{l=j}^{l^\prime -1}\gamma^{d_l-2}B_I+\gamma\cdot \gamma^{k-1}B,&\text{ if }\;d_j>1.
\end{cases}\\
=&\sum_{l=j}^{l^\prime-1}\gamma^{d_l-1}B_I+\gamma^k B_I= \sum_{l=j}^{l^\prime}v(k+1,d_l)B_I = \sum_{l=j}^{N+1}v(k+1,d_l)B_l,
\end{split}
\end{equation}

where the last equality holds because of (<ref>). For an incorrect action $a^{-}\in \mc A^-(s^{\mb d})$ we have

\begin{equation}
\begin{split}
r(s^{\mb d},a^-,s^{\mb d}_{a^-})+\gamma V_k(s^{\mb d}_{a^-}) \overset{(i)}{=} \gamma V_k(s^{\mb d}_{a^-})\overset{(ii)}{\leq} \sum_{l=j}^{l^\prime-1}\gamma^{d_l}B_I,
\end{split}
\end{equation}

where equality $(i)$ holds because $r(s^{\mb d},a^-,s_{a-}^{\mb d}) = 0$ and inequality $(ii)$ holds because of $\gamma<1$. Since $k+1>1$, we know that $r(s^{\mb d},a,s^{\mb d}_a) = 0$ and hence

\begin{equation}
r(s^{\mb d},a^-,s^{\mb d}_{a^-})+\gamma V_k(s^{\mb d}_{a^-}) < r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+}).
\end{equation}

By the value iteration update (<ref>), we know that

\begin{equation}
\begin{split}
V_{k+1}(s)&=\max_{a\in \mc A}\left\{r(s,a,s_a)+\gamma V_k(s_a)\right\}\\
&=r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+}) = \sum_{l=j}^{N+1}v(k+1,d_l)B_l,
\end{split}
\end{equation}

which completes the induction for this case.

* When $j < N+1$ and $l^\prime = N+1$. For a correct action $a^+\in \mc A^+(s^{\mb d})$, we have

\begin{equation}
\begin{split}
&r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+})\\
\begin{cases}
B_I+\gamma V_k(s^{\mb d}_{a^+})=B_I+\gamma\sum_{l=j+1}^{N}\gamma^{d_l-2}B_I+\gamma\cdot\gamma^{k-1}B,&\text{ if }\;d_j=1,\\
\gamma V_k(s_{a^+}^d) = \gamma \sum_{l=j}^{N}\gamma^{d_l-2}B_I+\gamma\cdot \gamma^{k-1}B,&\text{ if }\;d_j>1.
\end{cases}\\
=&\sum_{l=j}^{N}\gamma^{d_l-1}B_I+\gamma^k B= \sum_{l=j}^{N+1}v(k+1,d_l)B_l.
\end{split}
\end{equation}

For an incorrect action $a^{-}\in \mc A^-(s^{\mb d})$ we have

\begin{equation}
\begin{split}
r(s^{\mb d},a^-,s^{\mb d}_{a^-})+\gamma V_k(s^{\mb d}_{a^-}) = \gamma V_k(s^{\mb d}_{a^-})\leq \sum_{l=j}^{N}\gamma^{d_l}B_I.
\end{split}
\end{equation}

Since $k+1>1$, we know that $r(s^{\mb d},a,s^{\mb d}_a) = 0$ and hence

\begin{equation}
r(s^{\mb d},a^-,s^{\mb d}_{a^-})+\gamma V_k(s^{\mb d}_{a^-}) < r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+}).
\end{equation}

By the value iteration update (<ref>), we know that

\begin{equation}
\begin{split}
V_{k+1}(s)&=\max_{a\in \mc A}\left\{r(s,a,s_a)+\gamma V_k(s_a)\right\}\\
&=r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+}) = \sum_{l=j}^{N+1}v(k+1,d_l)B_l,
\end{split}
\end{equation}

which completes the induction for this case.

* When $j = N+1$ and $l^\prime = N+1$. For a correct action $a^+\in \mc A^+(s^{\mb d})$, we have

\begin{equation}
\begin{split}
&r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+}) = \gamma^k B= v(k+1,d_l)B_l.
\end{split}
\end{equation}

For an incorrect action $a^{-}\in \mc A^-(s^{\mb d})$ we have

\begin{equation}
\begin{split}
r(s^{\mb d},a^-,s^{\mb d}_{a^-})+\gamma V_k(s^{\mb d}_{a^-}) \overset{(i)}{=} 0,
\end{split}
\end{equation}

where equality $(i)$ holds because Definition <ref> implies that $D(s^{\mb d}_{a^-},\mc S_{T})\geq D(s^{\mb d},\mc S_{T})= k+1$. Since $k+1>1$, we know that $r(s^{\mb d},a,s^{\mb d}_a) = 0$ and hence

\begin{equation}
r(s^{\mb d},a^-,s^{\mb d}_{a^-})+\gamma V_k(s^{\mb d}_{a^-}) < r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+}).
\end{equation}

By the value iteration update (<ref>), we know that

\begin{equation}
\begin{split}
V_{k+1}(s)&=\max_{a\in \mc A}\left\{r(s,a,s_a)+\gamma V_k(s_a)\right\}\\
&=r(s^{\mb d},a^+,s^{\mb d}_{a^+})+\gamma V_k(s^{\mb d}_{a^+}) = v(k+1,d_{N+1})B,
\end{split}
\end{equation}

which completes the induction for this case.

Hence, we know the induction condition (<ref>) holds for $k+1$, which completes the proof.

Let $\mc M = (\mc S,\mc A, P, r, \gamma)$ be a deterministic MDP with initial state $s_0$, intermediate states $\mc S_{I} = \{s_{i_1},s_{i_2},\dots,s_{i_N}\}$, and terminal states $\mc S_{T}$. Suppose $\mc M$ satisfies Assumption <ref>, <ref> (b), and <ref>, if the reward function $r(\cdot)$ follows the intermediate reward setting (Table <ref>) and the value function and Q-function are zero-initialized (<ref>), $\forall s \in \mc S\backslash\mc S_{T}$, if $\mc S_{T}$ is directly reachable from $s$ and suppose

\begin{equation}
d = D(s,\mc S_{T})\; \text{ and }\; d_I = D(s,\mc S_{I}) \doteq \min_{j\in \mc I_d(s)} D(s,s_{i_j}),
\end{equation}

then after $k\leq d_I+h$ synchronous value iteration updates (<ref>), the value function $V_k(s)$ satisfies

\begin{equation}
\label{eq:Vk(s)_ST+_directly_reachable}
V_k(s) = \max\{v(k,d_I)B_I,v(k,d)B\},
\end{equation}

\begin{equation}
\label{eq:v(k,d)_def}
\begin{cases}
\gamma^{d-1}, & \forall k,d\in \bb N, d\leq k,\\
0, & \text{ otherwise}.\\
\end{cases}
\end{equation}

Similar to the definition of $\mc A^+(s)$, let $\mc A_I^+(s)$ denotes the set of actions that lead $s$ one step closer to $\mc S_I$:

\begin{equation}
\label{eq:defAI+}
\mc A^+_I(s) = \{a|a\in \mc A,D(s_a,\mc S_{I})=D(s,\mc S_{I})-1\}.
\end{equation}

We will use induction to prove the results. Recall the synchronous value iteration update (<ref>):

\begin{equation*}
\begin{split}
V_{k+1}(s)&=\max_{a\in \mc A}\left\{r(s,a,s_a)+\gamma V_k(s_a)\right\},\;\forall s\in \mc S.\\
\end{split}
\end{equation*}

We first check the induction condition (<ref>) for the initial case $k=1$.

Initial Condition for $k=1$.
When $k=1$, we know that

\begin{equation}
\begin{split}
V_1(s) &= \max_a\{r(s,a,s_a)+\gamma V_k(s_a)\}\\
\max\{B_I,B\},&\;\text{if }d_I=d=1,\\
B_I,&\;\text{if }d_I=1,d>1,\\
B,&\;\text{if }d=1,d_I>1,\\
0,&\;\text{otherwise }
\end{cases}\\
\end{split}
\end{equation}

which verifies the initial condition (<ref>).

We will discuss these following cases: (a) $d_I\leq k+1,d=1$, (b) $d_I\leq k+1,d>1$, and (c) $d_I>k+1$.

(a) When $d_I\leq k+1,d=1$.
In this case, we consider these following actions:

\begin{equation}
a^+\in \mc A^+(s),\; a_{i+}^-\in \mc A_I^+(s)\backslash \mc A^+(s),\; a_{i-}^-\in \mc A(s)\backslash(A_I^+(s)\cup\mc A^+(s)).
\end{equation}

* For any $a^+\in \mc A^+(s)$. In this case, $d=1$ implies that $s_{a^+}\in \mc S_{T}$. Hence we have

\begin{equation}
\label{eq:dI=k+1_d=1_a+}
r(s,a^+,s_{a^+})= B,\;V_k(s_{a^+}) = 0\implies r(s,a^+,s_{a^+})+\gamma V_k(s_{a^+}) = B,
\end{equation}

* For any $a^-_{i+}\in \mc A_I^+(s)\backslash\mc A^+(s)$. In this case, let

\begin{equation}
d^\prime = D(s_{a_{i+}^-},\mc S_{T}),
\end{equation}

by the definition of $\mc A_I^+(s)$ (<ref>), we know that

\begin{equation}
d^\prime = D(s_{a^-_{i+}},\mc S_{T})\geq d = 1,\; D(s_{a^-_{i+}},\mc S_{I}) = D(s,\mc S_{I}) - 1 = d_I-1 \leq k.
\end{equation}

Hence, the induction condition (<ref>) implies that

\begin{equation}
V_k(s_{a_{i+}^-}) = \max\{v(k,d_I-1)B_I,v(k,d^\prime)B\}.
\end{equation}

If $d_I >1$, we know that $r(s,a,s_{a_{i+}^-})=0$, and hence

\begin{equation}
\label{eq:dI=k+1_d=1_a-i+;dI>1}
r(s,a_{i+}^-,s_{a_{i+}^-})+\gamma V_k(s_{a^-_{i+}}) = \gamma\max\{v(k,d_I-1)B_I,v(k,d^\prime)B\} \overset{(i)}{=} \max\{v(k+1,d_I)B_I,\gamma v(k,d^\prime)B\},
\end{equation}

where equality $(i)$ holds because $\gamma v(k,d_I - 1) = \gamma v(k,k) = \gamma^k = v(k+1,k+1) = v(k+1,d_I)$. When $d_I=1$, we have

\begin{equation}
\label{eq:dI=k+1_d=1_a-i+;dI=1}
r(s,a_{i+}^-,s_{a_{i+}^-})+\gamma V_k(s_{a^-_{i+}}) = B_I.
\end{equation}

* For any $a^-_{i-}\in \mc A\backslash(\mc A_I^+(s)\cup\mc A^+(s))$. In this case, let

\begin{equation}
d^{\prime\prime} = D(s_{a_{i+}^-},\mc S_{T})\geq d = 1,\;d_I^{\prime} = D(s_{a_{i+}^-},\mc S_{I})\geq d_I=k+1,
\end{equation}

the induction condition (<ref>) implies that

\begin{equation}
V_k(s_{a_{i+}^-}) = \max\{v(k,d_I^\prime)B_I,v(k,d^{\prime\prime})B\}.
\end{equation}

Similar to the previous case for $a_{i+}^-$, we also have $r(s,a,s_{a_{i+}^-})=0$, and hence

\begin{equation}
\label{eq:dI=k+1_d=1_a-i-}
r(s,a_{i-}^-,s_{a_{i-}^-})+\gamma V_k(s_{a^-_{i-}}) = \max\{\gamma v(k,d_I^\prime)B_I,\gamma v(k,d^{\prime\prime})B\}.
\end{equation}

Combine (<ref>), (<ref>), (<ref>), and the synchronous value iteration update (<ref>), when $d_I>1$ we have

\begin{equation}
\begin{split}
V_{k+1}(s) &= \max_{a\in \mc A}\{r(s,a,s_a)+\gamma V_{k}(s_a)\}\\
&=\max\left\{B,\max\{v(k+1,d_I)B_I,\gamma v(k,d^\prime)B\},\max\{\gamma v(k,d_I^\prime)B_I,\gamma v(k,d^{\prime\prime})B\}\right\}\\
&\overset{(i)}{=}\max\{v(k+1,d_I)B_I,B\} = \max\{v(k+1,d_I)B_I,v(k+1,1)B\},
\end{split}
\end{equation}

where equality $(i)$ holds because $d^\prime,d^{\prime\prime}\geq1$ implies that $\gamma v(k,d^\prime)B,\gamma v(k,d^{\prime\prime})B\leq \gamma B<B$.

Similarly, using (<ref>), (<ref>), (<ref>) when $d_I=1$, we have

\begin{equation}
\begin{split}
V_{k+1}(s) &= \max_{a\in \mc A}\{r(s,a,s_a)+\gamma V_{k}(s_a)\}\\
&=\max\left\{B,B_I,\max\{\gamma v(k,d_I^\prime)B_I,\gamma v(k,d^{\prime\prime})B\}\right\}\\
&\overset{(ii)}{=}\max\{B_I,B\} = \max\{v(k+1,1)B_I,v(k+1,1)B\},
\end{split}
\end{equation}

where equality $(ii)$ holds because $d_I^\prime,d^{\prime\prime}>1$.
Hence, we have verified the induction condition (<ref>) for $d_I\leq k+1,d=1$.

(b) When $d_I\leq k+1,d>1$.

In this case, we also consider these following actions:

\begin{equation}
a^+\in \mc A^+(s),\; a_{i+}^-\in \mc A_I^+(s)\backslash \mc A^+(s),\; a_{i-}^-\in \mc A(s)\backslash(A_I^+(s)\cup\mc A^+(s)).
\end{equation}

* For any $a^+\in \mc A^+(s)$. Similarly, let

\begin{equation}
d_I^\prime = D(s_{a^+},\mc S_{T}),
\end{equation}

hence we know that

\begin{equation}
D(s_{a^+},\mc S_{T})= d - 1\geq1,\; d_I^\prime = D(s_{a^+},\mc S_{I}) \geq D(s,\mc S_{I}) - 1 \leq k.
\end{equation}

The induction condition (<ref>) implies that

\begin{equation}
V_k(s_{a^+}) = \max\{v(k,d_I^\prime)B_I,v(k,d-1)B\}.
\end{equation}

Notice that $d>1$ implies that $r(s,a^+,s_{a^+})=0$, hence

\begin{equation}
\label{eq:dI=k+1_d>1_a+}
r(s,a^+,s_{a^+})+\gamma V_k(s_{a^+}) = \max\{\gamma v(k,d_I^\prime)B_I, \gamma v(k,d-1)B\}.
\end{equation}

* For any $a^-_{i+}\in \mc A_I^+(s)\backslash\mc A^+(s)$. In this case, let

\begin{equation}
d^\prime = D(s_{a_{i+}^-},\mc S_{T}),
\end{equation}

by the definition of $\mc A_I^+(s)$ (<ref>), we know that

\begin{equation}
d^\prime = D(s_{a^-_{i+}},\mc S_{T})\geq d > 1,\; D(s_{a^-_{i+}},\mc S_{I}) = D(s,\mc S_{I}) - 1 = k.
\end{equation}

Hence, the induction condition (<ref>) implies that

\begin{equation}
V_k(s_{a_{i+}^-}) = \max\{v(k,d_I-1)B_I,v(k,d^\prime)B\}.
\end{equation}

If $d_I >1$, so $r(s,a,s_{a_{i+}^-})=0$, and hence

\begin{equation}
\label{eq:dI=k+1_d>1_a-i+;dI>1}
r(s,a_{i+}^-,s_{a_{i+}^-})+\gamma V_k(s_{a^-_{i+}}) = \gamma\max\{v(k,d_I-1)B_I,v(k,d^\prime)B\} = \max\{v(k+1,d_I)B_I,\gamma v(k,d^\prime)B\},
\end{equation}

the last equality holds for the same reason described in the previous case for $d_I>1,d>1$. When $d_I=1$, we have

\begin{equation}
\label{eq:dI=k+1_d>1_a-i+;dI=1}
r(s,a_{i+}^-,s_{a_{i+}^-})+\gamma V_k(s_{a^-_{i+}}) = B_I.
\end{equation}

* For any $a^-_{i-}\in \mc A\backslash(\mc A_I^+(s)\cup\mc A^+(s))$. Similar to the case where $d_I=k+1,d=1$, let

\begin{equation}
d^{\prime\prime} = D(s_{a_{i+}^-},\mc S_{T})\geq d > 1,\;d_I^{\prime} = D(s_{a_{i+}^-},\mc S_{I})\geq d_I=k+1,
\end{equation}

the induction condition (<ref>) implies that

\begin{equation}
V_k(s_{a_{i+}^-}) = \max\{v(k,d_I^\prime)B_I,v(k,d^{\prime\prime})B\}.
\end{equation}

Similar to the previous case for $a_{i+}^-$, we also have $r(s,a,s_{a_{i+}^-})=0$, and hence

\begin{equation}
\label{eq:dI=k+1_d>1_a-i-}
r(s,a_{i-}^-,s_{a_{i-}^-})+\gamma V_k(s_{a^-_{i-}}) = \max\{\gamma v(k,d_I^\prime)B_I,\gamma v(k,d^{\prime\prime})B\}.
\end{equation}

Combine (<ref>), (<ref>), (<ref>), and the synchronous value iteration update (<ref>), when $d_I>1$ we have

\begin{equation}
\begin{split}
&V_{k+1}(s)=\; \max_{a\in \mc A}\{r(s,a,s_a)+\gamma V_{k}(s_a)\}\\
=&\;\max\left\{\max\{\gamma v(k,d_I^\prime)B_I, \gamma v(k,d-1)B\},\max\{v(k+1,d_I)B_I,\gamma v(k,d^\prime)B\},\max\{\gamma v(k,d_I^{\prime\prime})B_I,\gamma v(k,d^{\prime\prime})B\}\right\}\\
\overset{(i)}{=}&\;\max\{v(k+1,d_I)B_I,\gamma v(k,d-1)B\} \overset{(ii)}{=} \max\{v(k+1,d_I)B_I,v(k+1,d)B\},
\end{split}
\end{equation}

where equality $(i)$ holds because $d^\prime_I,d^{\prime\prime}_I\geq d_I$ implies that $\gamma v(k,d_I^\prime),\gamma v(k,d_I^{\prime\prime})\leq \gamma^{d_I}=v(k+1,d_I)$
and $d^\prime,d^{\prime\prime}>d$ implies that $v(k,d^\prime),v(k,d^{\prime\prime}) \leq  v(k,d-1)$. Equality $(ii)$ holds because when $d_I = k+1$, $v(k+1,d_I) = \gamma^{d_I}>0$, then if $\gamma v(k,d-1)B>v(k+1,d_I)B_I$, we know that $\gamma v(k,d-1)B>0$, which implies $k\geq d-1$ (or equivalently $k+1\geq d$) hence $v(k+1,d) = \gamma^{d-1} = \gamma v(k,d-1)$.

Similarly, when $d_I=1$, (<ref>), (<ref>), (<ref>), we have

\begin{equation}
\begin{split}
&V_{k+1}(s)=\; \max_{a\in \mc A}\{r(s,a,s_a)+\gamma V_{k}(s_a)\}\\
=&\;\max\left\{\max\{\gamma v(k,d_I^\prime)B_I, \gamma v(k,d-1)B\},B_I,\max\{\gamma v(k,d_I^{\prime\prime})B_I,\gamma v(k,d^{\prime\prime})B\}\right\}\\
\overset{(iii)}{=}&\;\max\{B_I,\gamma v(k,d-1)B\} = \max\{v(k+1,1)B_I,v(k+1,d)B\},
\end{split}
\end{equation}

where equality $(iii)$ holds because $d^\prime_I,d_I^{\prime\prime}\geq 1,$
Hence, we have verified the induction condition (<ref>) for $d_I\leq k+1,d>1$.