Title: SAMPLE-EFFICIENT DEEP REINFORCEMENT LEARN-ING VIA EPISODIC BACKWARD UPDATE

Abstract: We propose Episodic Backward Update -a new algorithm to boost the performance of a deep reinforcement learning agent by fast reward propagation. In contrast to the conventional use of replay memory with uniform random sampling, our agent samples a whole episode and successively propagates the value of a state into its previous states. Our computationally efficient recursive algorithm allows sparse and delayed rewards to propagate effectively throughout the sampled episode. We evaluate our algorithm on 2D MNIST Maze Environment and 49 games of the Atari 2600 Environment and show that our agent improves sample efficiency with a competitive computational cost.

1. INTRODUCTION:

Recently, deep reinforcement learning (RL) has been very successful in many complex environments such as the Arcade Learning Environment (Bellemare et al., 2013) and Go (Silver et al., 2016) . Deep Q-Network (DQN) algorithm (Mnih et al., 2015) with the help of experience replay (Lin, 1991 (Lin, & 1992) ) enjoys more stable and sample-efficient learning process, so is able to achieve super-human performance on many tasks. Unlike simple online reinforcement learning, the use of experience replay with random sampling breaks down the strong ties between correlated transitions and also allows the transitions to be reused multiple times throughout the training process.

Although DQN has shown impressive performances, it is still impractical in terms of data efficiency. To achieve a human-level performance in the Arcade Learning Environment, DQN requires 200 million frames of experience for training, which is approximately 39 days of game play in real time. Remind that it usually takes no more than a couple of hours for a skilled human player to get used to such games. So we notice that there is still a tremendous amount of gap between the learning process of humans and that of a deep reinforcement learning agent. This problem is even more crucial in environments such as autonomous driving, where we cannot risk many trials and errors due to the high cost of samples.

One of the reasons why the DQN agent suffers from such low sample efficiency could be the sampling method over the replay memory. In many practical problems, the agent observes sparse and delayed reward signals. There are two problems when we sample one-step transitions uniformly at random from the replay memory. First, we have a very low chance of sampling the transitions with rewards for its sparsity. The transitions with rewards should always be updated, otherwise the agent cannot figure out which action maximizes its expected return in such situations. Second, there is no point in updating a one-step transition if the future transitions have not been updated yet. Without the future reward signals propagated, the sampled transition will always be trained to return a zero value.

In this work, we propose Episodic Backward Update (EBU) to come up with solutions for such problems. Our idea originates from a naive human strategy to solve such RL problems. When we observe an event, we scan through our memory and seek for another event that has led to the former one. Such episodic control method is how humans normally recognize the cause and effect relationship (Lengyel & Dayan, 2007) . We can take a similar approach to train an RL agent. We can solve the first problem above by sampling transitions in an episodic manner. Then, we can be assured that at least one transition with non-zero reward is being updated. We can solve the second problem by updating transitions in a backward way in which the transitions were made. By then, we can perform an efficient reward propagation without any meaningless updates. This method faithfully follows the principle of dynamic programing.

We evaluate our update algorithm on 2D MNIST Maze Environment and the Arcade Learning Environment. We observe that our algorithm outperforms other baselines in many of the environments with a notable amount of performance boosts.

2. RELATED WORKS:

Reinforcement learning deals with environments where an agent can make a sequence of actions and receive corresponding reward signals, such as Markov decision processes (MDPs). At time t, the agent encounters a state s t and takes an action a t ∈ A, observes the next state s t+1 and receives reward r t ∈ R. The agent's goal is to set up a policy π to take a sequence of actions so that the agent can maximize its expected return, which is the expected value of the discounted sum of rewards

E π [ t γ t r t ].

Q-learning (Watkins, 1989) is one of the most widely used methods to solve such RL tasks. The key idea of Q-learning is to estimate the state-action value function Q(s, a), generally called as the Qfunction. The state-action value function may be characterized by the Bellman optimality equation

Q * (s t , a) = E[r t + γ max a Q * (s t+1 , a )].

(1)

Given the state-action value function Q(s, a), the agent may perform the best action a * = argmax a Q(s, a) at each time step to maximize the expected return.

There are two major inefficiencies in the traditional Q-learning. First, each experience is used only once to update the Q-network. Secondly, learning from experiences in a chronologically forward order is much more inefficient than learning in a chronologically backward order. Experience replay (Lin, 1991 (Lin, & 1992) ) is proposed to overcome these inefficiencies. After observing a transition (s t , a t , r t , s t+1 ), the agent stores the transition into its replay buffer. In order to learn the Q-values, the agent samples transitions from the replay in a backward order.

In practice, the state space is extremely large, so it is impractical to tabularize Q-values of all stateaction pairs. Deep Q-Network (Mnih et al., 2015) overcomes this issue by using deep neural networks to approximate the Q-function. Deep Q-Network (DQN) takes a 2D representation of a state s t as an input. Then the information of the state s t passes through a number of convolutional neural networks (CNNs) and fully connected networks. Then it finally returns the Q-values of each action a t at state s t . DQN adopts experience replay to use each transition in multiple updates. Since DQN uses a function approximator, consecutive states output similar Q-values. So when DQN updates transitions in a chronologically backward order, often errors cumulate and degrade the performance. So DQN does not sample transitions in a backward order, but uniformly at random to train the network. This process breaks down the correlations between consecutive transitions and reduces the variance of updates.

There have been a variety of methods proposed to improve the performance of DQN in terms of stability, sample efficiency and runtime. Some methods propose new network architectures. The dueling network architecture (Wang et al., 2015) contains two streams of separate Q-networks to estimate the value functions and the advantage functions. Neural episodic control (Pritzel et al., 2017) and model free episodic control (Blundell et al., 2016) use episodic memory modules to estimate the state-action values.

Some methods tackle the uniform random sampling replay strategy of DQN. Prioritized experience replay (Schaul et al., 2016) assigns non-uniform probability to sample transitions, where greater probability is assigned for transitions with higher temporal difference error.

Inspired by Lin's backward use of replay memory, some methods try to aggregate TD values with Monte-Carlo returns. Q(λ) (Harutyunyan et al., 2016) and Retrace(λ) (Munos et al., 2016) modify the target values to allow the on-policy samples to be used interchangeably for on-policy and off-policy learning, which ensures safe and efficient reward propagation. Count-based exploration method combined with intrinsic motivation (Bellemare et al., 2016) takes a mixture of one-step return and Monte-Carlo return to set up the target value. Optimality Tightening (He et al., 2017) Q(s t , a t ) ← r t + γ max a Q(s t+1 , a ) 5: end for plies constraints on the target using the values of several neighboring transitions. Simply by adding a few penalty terms into the loss, it efficiently propagates reliable values to achieve faster convergence.

Our work lies on the same line of research. Without a single change done on the network structure of the original DQN, we only modify the target value. Instead of using a limited number of consecutive transitions, our method samples a whole episode from the replay memory and propagates values sequentially throughout the entire sampled episode in a backward way. Our novel algorithm effectively reduces the errors generated from the consecutive updates of correlated states by a temporary backward Q-table with a diffusion coefficient.

3. EPISODIC BACKWARD UPDATE:

We start with a simple motivating toy example to describe the effectiveness of episodic backward update. Then we generalize the idea into deep learning architectures and propose the full algorithm.

3.1. MOTIVATION:

Let us imagine a simple graph environment with a sparse reward (Figure 1 , left). In this example, s 1 is the initial state and s 4 is the terminal state. A reward of 1 is gained only when the agent moves to the terminal state and a reward of 0 is gained from any other transitions. To make it simple, assume that we only have one episode stored in the experience memory: (s 1 → s 2 → s 1 → s 3 → s 4 ). When sampling transitions uniformly at random as Nature DQN, the important transitions (s 1 → s 3 ) and (s 3 → s 4 ) may not be sampled for updates. Even when those transitions are sampled, there is no guarantee that the update of the transition (s 3 → s 4 ) would be done before the update of (s 1 → s 3 ). So by updating all transitions within the episode in a backward manner, we can speed up the reward propagation, and due to the recursive update, it is also computationally efficient.

We can calculate the probability of learning the optimal path (s 1 → s 3 → s 4 ) for the number of sample transitions trained. With the simple episodic backward update stated in Algorithm 1 (which is a special case of Lin's algorithm (Lin, 1991) with recency parameter λ = 0), the agent can come up with the optimal policy just after 4 updates of Q-values. However, we see that the uniform sampling method requires more than 30 transitions to learn the optimal path (Figure 1 , right).

Note that this method is different to the standard n-step Q-learning (Watkins, 1989) .

Q(s t , a t ) ← (1 -α)Q(s t , a t ) + α(r t + γr t+1 + . . . + γ n-1 r t+n-1 + max a γ n Q(s t+n , a)). (2)

In n-step Q-learning, the number of future steps for target generation is fixed as n. However, our method takes T future values in consideration, which is the length of the sampled episode. Also, n-step Q-learning takes max operator at the n-th step only, whereas we take max operator at every iterative backward steps which can propagate high values faster. To avoid exponential decay of the Q-value, we set the learning rate α = 1 within the single episode update.

3.2. EPISODIC BACKWARD UPDATE ALGORITHM:

The fundamental idea of tabular version of backward update algorithm may be applied to its deep version with just a few modifications. We use a function approximator to estimate the Q-values and generate a temporary Q-table Q of the sampled episode for the recursive backward update. The full algorithm is introduced in Algorithm 2. The algorithm is almost the same as that of Nature DQN (Mnih et al., 2015) . Our contributions are the episodic sampling method and the recursive backward With probability select a random action a t

7::

Otherwise select a t = argmax a Q (s t , a; θ)

8::

Execute action a t , observe reward r t and next state s t+1

9: Store transition (s t , a t , r t , s t+1 ) in D 10: Sample a random episode E = {S, A, R, S } from D, set T = length(E) 11: Generate temporary target Q table, Q = Q S , •; θ - 12:

Initialize target vector y = zeros(T ) 13:

y T ← R T 14: for k = T -1 to 1 do 15: Q [A k+1 , k] ← βy k+1 + (1 -β) Q [A k+1 , k] 16: y k ← R k + γ max a∈A Q [a, k] 17: end for 18:

Perform a gradient descent step on (y -Q (S, A; θ))

2 with respect to θ 19:

Every C steps reset Q = Q 20:

end for 21: end for target generation with a diffusion coefficient β (line number 10 to line number 17 of Algorithm 2), which prevents the errors from correlated states cumulating.

Our algorithm has its novelty starting from the sampling stage. Instead of sampling transitions at uniformly random, we make use of all transitions within the sampled episode E = {S, A, R, S }. Let the sampled episode start with a state S 1 and contain T transitions. Then E can be denoted as a set of 1 × n vectors, i.e.

S = {S 1 , S 2 , . . . S T }, A = {A 1 , A 2 , . . . A T }, R = {R 1 , R 2 , . . . R T } and S = {S 2 , S 3 , . . . S T +1 }. The temporary target Q-table Q, is initialized

to store all the target Q-values of S for all valid actions. Q is an |A| × T matrix which stores the target Q-values of all states S for all valid actions. Therefore the j-th column of Q is a column vector that contains Q S j+1 , a; θ -for all valid actions a from j = 1 to T .

Our goal is to estimate the target vector y and train the network to minimize the loss between each Q (S j , A j ) and y j for all j from 1 to T . After initialization of the temporary Q-table, we perform a recursive backward update. Adopting the backward update idea, one element Q [A k+1 , k] in the k-th column of the Q is replaced by the next transition's target y k+1 . Then y k is estimated using the maximum of the newly modified k-th column of Q. Repeating this procedure in a recursive manner until the start of the episode, we can successfully apply the backward update algorithm in a deep Q-network. The process is described in detail with a supplementary diagram in Appendix D.

When β = 1, the proposed algorithm is identical to the tabular backward algorithm stated in Algorithm 1. But unlike the tabular situation, now we are using a function approximator and updating correlated states in a sequence. As a result, we observe unreliable values with errors being propagated and compounded through recursive max operations. We solve this problem by introducing the diffusion coefficient β. By setting β ∈ (0, 1), we can take a weighted sum of the newly learnt value and the pre-existing value. This process stabilizes the learning process by exponentially decreasing the error terms and preventing the compounded error from propagating. Note that when β = 0, the algorithm is identical to episodic one-step DQN.

We prove that episodic backward update with a diffusion coefficient β ∈ (0, 1) defines a contraction operator and converges to optimal Q-function in finite and deterministic MDPs. Theorem 1. Given a finite, deterministic, and tabular MDP M = (S, A, P, R), the episodic backward update algorithm in Algorithm 2 converges to the optimal Q function w.p. 1 as long as

• The step size satisfies the Robbins-Monro condition;

• The sample trajectories are finite in lengths l: E[l] < ∞;

• Every (state, action) pair is visited infinitely often.

We state the proof of Theorem 1 in Appendix E.

We train the network to minimize the squared-loss between the Q-values of sampled states Q (S, A; θ) and the backward target y. In general, the length of an episode is much longer than the minibatch size. So we divide the loss vector y -Q (S, A; θ) into segments with size equal to the minibatch size. At each step, the network is trained by a single segment. A new episode is sampled only when all of the loss segments are used for training.

4. EXPERIMENTS:

Our experiments are designed to verify the following two hypotheses: 1) EBU agent can propagate reward signals fast and efficiently in environments with sparse and delayed reward signals. 2) EBU algorithm is sample-efficient in complex domains and does not suffer from stability issues despite its sequential updates of correlated states. To investigate these hypotheses, we performed experiments on 2D MNIST Maze Environment and on 49 games of the Arcade Learning Environment (Bellemare et al., 2013) . We test our algorithm in 2D maze environment with sparse and delayed rewards. Starting from the initial position, the agent has to navigate through the maze to discover the goal position. The agent has 4 valid actions: up, down, left and right. When the agent bumps into a wall, then the agent returns to its previous state. To show effectiveness in complex domains, we use the MNIST dataset (LeCun et al., 1998) for state representation (illustrated in Figure 2 ). When the agent arrives at each state, it receives the coordinates of the position in two MNIST images as the state representation.

4.1. 2D MNIST MAZE ENVIRONMENT:

We compare the performance of EBU to uniform one-step Q-learning and n-step Q-learning. For n-step Q-learning, we set the value of n as the length of the episode. We use 10 by 10 mazes with randomly placed walls. The agent starts at (0,0) and has to reach the goal position at (9,9) as soon as possible. Wall density indicates the probability of having a wall at each position. We assign a reward of 1000 for reaching the goal and a reward of -1 for bumping into a wall. For each wall density, we generate 50 random mazes with different wall locations. We train a total of 50 independent agents, one agent for one maze over 200,000 steps each. The MNIST images for state representation are randomly selected every time the agent visits each state. The relative length is defined as l rel = l agent /l oracle , which is the ratio between the length of the agent's path l agent and the length of the ground truth shortest path l oracle . Figure 3 shows the median relative lengths of 50 agents over 200,000 training steps. Since all three algorithms achieve median relative lengths of 1 at the end of training, we report the mean and the median relative lengths at 100,000 steps in Table 1 .

For this example, we set the diffusion coefficient β = 1. The details of hyperparameters and the network structure are described in Appendix C.

The result shows that EBU agent outperforms other baselines in most of the situations. Uniform sampling DQN shows the worst performance in all configurations, implying the inefficiency of uniform sampling update in environments with sparse and delayed rewards. As the wall density increases, valid paths to the goal become more complicated. In other words, the oracle length l oracle increases, so it is important for the agent to make correct decisions at bottleneck positions. N-step Q-learning shows the best performance with a low wall density, but as the wall density increases, EBU shows better performance than n-step Q. Especially when the wall density is 50%, EBU finds paths twice shorter than those of n-step Q. This performance gap originates from the difference between the target generation methods of the two algorithms. EBU performs recursive max operators at each positions, so the optimal Q-values at bottlenecks are learned faster.

4.2. ARCADE LEARNING ENVIRONMENT:

The Arcade Learning Environment (Bellemare et al., 2013) is one of the most popular RL benchmarks for its diverse set of challenging tasks. The agent receives high-dimensional raw observations from exponentially large state space. Even more, observations and objectives of the games are completely different over different games, so the strategies to achieve high score should also vary from game to game. Therefore it is very hard to create a robust agent with a single set of networks and parameters that can learn to play all games. We use the same set of 49 Atari 2600 games which was evaluated in Nature DQN paper (Mnih et al., 2015) .

We compare our algorithm to four baselines: Nature DQN, Optimality Tightening (He et al., 2017) , Prioritized Experience Replay (Schaul et al., 2016) and Retrace(λ) (Munos et al., 2016) We observe that the choice of β = 1 degrades the performance in most of the games. Instead, we use β =1 2 , which shows the best performance among { 1 3 , 1 2 , 2 3 , 3 4 , 1} that we tried. Further fine tuning of β may lead to a better result.

First, we show the improvements of EBU over Nature DQN for all 49 games in Figure 4 . To compare the performance of an agent over its baseline, we use the following measure (Wang et al., 2015) .

Score Agent -Score Baseline max{Score Human , Score Baseline } -Score Random .

(3)

This measure shows how well the agent performs the task compared to its level of difficulty. Out of the 49 games, our agent shows better performance in 32 games. Not only that, for games such as 'Atlantis', 'Breakout' and 'Video Pinball', our agent shows significant amount of improvements.

In order to compare the overall performance of an algorithm, we use Eq.( 4) to calculate the human normalized score (van Hasselt et al., 2015) .

EQUATION

)

We report the mean and median of the human normalized scores of 49 games in Table 2 . The result shows that our algorithm outperforms the baselines in both mean and median of the human normalized scores. Furthermore, our method requires only about 37% of computation time used by Optimality Tightening 1 . Since Optimality Tightening has to calculate the Q-values of neighboring states and compare them to generate the penalty term, it requires about 3 times more training time than Nature DQN. Since EBU performs iterative episodic updates using the temporary Q-table that is shared by all transitions in the episode, its computational cost is almost the same as that of Nature DQN. Scores for each game after 10 million frames of training are summarized in Appendix A.

We show the performance of EBU and the baselines for 4 games 'Assault', 'Breakout', 'Gopher' and 'Video Pinball' in performances in all 4 games, reflecting that our algorithm does not suffer from the stability issue caused by the sequential update of correlated states. Other baselines fail in some games, whereas our algorithm shows stable learning processes throughout all games. Out of 49 games, our algorithm shows the worst performance in only 6 games. Such stability leads to the best median and mean scores in total. Note that naive backward algorithm with β = 1.0 fails in most games. 

5. CONCLUSION:

We propose Episodic Backward Update, which samples transitions episode by episode and updates values recursively in a backward manner. Our algorithm achieves fast and stable learning due to the efficient value propagation. We show that our algorithm outperforms other baselines in many complex domains without much increase in computational cost. Since we did not change any network structures, hyperparameters and exploration methods, we hope that there is plenty of room left for further improvement. Up: median over 49 games. Down: mean over 49 games. We use the average of 30 no-op scores of 8 agents with different random seeds. Use of different evaluation methods and seeds may output different results.

APPENDIX A SCORES ACROSS ALL 49 GAMES:



APPENDIX D SUPPLEMENTARY FIGURE: BACKWARD UPDATE ALGORITHM:

0 … 0 0 𝑅 𝑇 𝒚 𝑄(𝑆 2 , 𝑎 (1) ) … 𝑄(𝑆 𝑇-1 , 𝑎 (1) ) 𝑄(𝑆 𝑇 , 𝑎 (1) ) 0 𝑄(𝑆 2 , 𝑎 (2) ) … 𝑄(𝑆 𝑇-1 , 𝑎 (2) ) 𝑄(𝑆 𝑇 , 𝑎 (2) ) 0 ⋮ ⋮ ⋮ ⋮ ⋮ 𝑄(𝑆 2 , 𝑎 (𝑛) ) … 𝑄(𝑆 𝑇-1 , 𝑎 (𝑛) ) 𝑄(𝑆 𝑇 , 𝑎 (𝑛) ) 0 ෩ 𝑸 𝑆 1 … 𝑆 𝑇-2 𝑆 𝑇-1 𝑆 𝑇 𝐴 1 … 𝐴 𝑇-2 𝐴 𝑇-1 𝐴 𝑇 𝑅 1 … 𝑅 𝑇-2 𝑅 𝑇-1 𝑅 𝑇 𝑆 2 … 𝑆 𝑇-1 𝑆 𝑇 𝑆 𝑇+1 𝑺 𝑨 𝑹 𝑺′ 𝑬 𝑛 𝑇 𝑄(𝑆 2 , 𝑎 (1) ) … 𝑄(𝑆 𝑇-1 , 𝑎 (1) ) 𝑄(𝑆 𝑇 , 𝑎 (1) ) 0 𝑄(𝑆 2 , 𝑎 (2) ) … 𝑄(𝑆 𝑇-1 , 𝑎 (2) ) 𝛽 𝑦 𝑇 + 1 -𝛽 𝑄(𝑆 𝑇 , 𝑎 (2) ) 0 ⋮ ⋮ ⋮ ⋮ ⋮ 𝑄(𝑆 2 , 𝑎 (𝑛) )

… 𝑄(𝑆 𝑇-1 , 𝑎 (𝑛) ) 𝑄(𝑆 𝑇 , 𝑎 (𝑛) ) 0

෩ 𝑸 0 … 0 𝑅 𝑇-1 + 𝛾 max ෩ 𝑸 [:, T-1] 𝑅 𝑇

𝒚:

Line #10 of Algorithm 2: Sample a random episode 𝑬.

Line # 11~13: Generate a temporary target Q table ෩ 𝑸 with the next state vector 𝑺′. Initialize a target vector 𝒚. Let there be 𝑛 possible actions in the environment. 𝒜 = 𝑎 (1) , 𝑎 (2) , … , 𝑎 (𝑛) . Note that 𝑄 is the target Q-value and 𝑄 𝑆 𝑇+1 , : = 0.

Line # 14~17, first iteration (k = T-1): Update ෩ 𝑸 and 𝒚. Let the T-th action in the replay memory be 𝐴 𝑇 = 𝑎 (2) .

𝑛 ① line # 15: update ෨ 𝑄 𝑨 𝑘+1 , 𝑘 = ෨ 𝑄 𝑨 𝑇 , 𝑇 -1 = ෨ 𝑄 𝑎 (2) , 𝑇 -1 ← 𝛽 𝑦 𝑇 + 1 -𝛽 𝑄(𝑆 𝑇 , 𝑎 (2) ) ② line # 16: update 𝑦 𝑘 = 𝑦 𝑇-1 ← 𝑅 𝑇-1 + 𝛾 max ෩ 𝑸 [:, T-1] T T-1 T-2 1 𝑎 (1) 𝑎 (2) 𝑎 (𝑛) … ⋮ index 𝑄(𝑆 2 , 𝑎 (1) ) … 𝛽 𝑦 𝑇-1 + 1 -𝛽 𝑄(𝑆 𝑇-1 , 𝑎 (1) ) 𝑄(𝑆 𝑇 , 𝑎 (1) ) 0 𝑄(𝑆 2 , 𝑎 (2) ) … 𝑄(𝑆 𝑇-1 , 𝑎 (2) ) 𝛽 𝑦 𝑇 + 1 -𝛽 𝑄(𝑆 𝑇 , 𝑎 (2) ) 0 ⋮ ⋮ ⋮ ⋮ ⋮ 𝑄(𝑆 2 , 𝑎 (𝑛) ) … 𝑄(𝑆 𝑇-1 , 𝑎 (𝑛) ) 𝑄(𝑆 𝑇 , 𝑎 (𝑛) ) 0 ෩ 𝑸 0 … 𝑅 𝑇-2 + 𝛾 max ෩ 𝑸 [:, T-2] 𝑅 𝑇-1 + 𝛾 max ෩ 𝑸 [:, T-1] 𝑅 𝑇 𝒚 Line # 14~17, second iteration (k = T-2): Update ෩

𝑸 and 𝒚. Let the (T-1)-th action in the replay memory be 𝐴 𝑇-1 = 𝑎 (1) .

𝑛 ① line # 15: update ෨ 𝑄 𝑨 𝑘+1 , 𝑘 = ෨ 𝑄 𝑨 𝑇-1 , 𝑇 -2 = ෨ 𝑄 𝑎 (1) , 𝑇 -2 ← 𝛽 𝑦 𝑇-1 + 1 -𝛽 𝑄(𝑆 𝑇-1 , 𝑎 (1) ) ② line # 16: update 𝑦 𝑘 = 𝑦 𝑇-2 ← 𝑅 𝑇-2 + 𝛾 max ෩ 𝑸 [:, T-2] T T-1 T-2 1 𝑎 (1)

𝑎 ( 2 

P (s |s, a) = 1 if s = g(s, a) 0 else ∀(s, a, s ) ∈ S × A × S,

In the episodic backward update algorithm, a single (state, action) pair can be updated through multiple episodes, where the evaluated targets of each episode can be different from each other. Therefore, unlike the bellman operator, episodic backward operator depends on the exploration policy for the MDP. Therefore, instead of expressing different policies in each state, we define a schedule to represent the frequency of every distinct episode (which terminates or continues indefinitely) starting from the target (state, action) pair.

Definition 2. (Schedule):

Assume a MDP M = (S, A, P, R) , where R is a bounded function. Then, for each state (s, a) ∈ S × A and j ∈ [1, ∞], we define j-length path set p s,a (j) and path set p(s, a) for (s, a) as

p s,a (j) = (s i , a i ) j i=0 |(s 0 , a 0 ) = (s, a), P (s i+1 |s i , a i ) > 0 ∀i ∈ [0, j -1], s j is terminal .

and p s,a = ∪ ∞ j=1 p s,a (j). Also, we define a schedule set λ s,a for (state action) pair (s, a) as

λ s,a = (λ i ) |ps,a| i=1 | |ps,a| i=1 λ i = 1, λ i > 0 ∀i ∈ [1, |p s,a |] .

Finally, to express the varying schedule in time at the RL scenario, we define a time schedule set λ for MDP M as

λ = {λ s,a (t)} ∞ (s,a)∈S×A,t=1 |λ s,a (t) ∈ λ s,a ∀(s, a) ∈ S × A, t ∈ [1, ∞] .

Since no element of the path can be the prefix of the others, the path set corresponds to the enumeration of all possible episodes starting from each (state, action) pair. Therefore, if we utilize multiple episodes from any given policy, we can see the empirical frequency for each path in the path set belongs to the schedule set. Finally, since the exploration policy can vary across time, we can group independent schedules into the time schedule set. Then, episodic backward operator H β t is defined as 

EQUATION

T β,Q (ps,a)i (j)   . T β,Q (ps,a)i (j) (8) = j-1 k=1 β k-1 γ k-1 βr(s ik , a ik , s i(k+1) ) + (1 -β)Q(s ik , a ik ) + β j-1 γ j-1 max a =aj Q(s ij , a ij ).

Where (p s,a ) i is the i-th path of the path set, and (s ij , a ij ) corresponds to the j-th (state, action) pair of the i-th path.

Episodic backward operator consists of two parts. First, given the path that initiates from the target (state, action) pair, function T β,Q (ps,a)i computes the maximum return of the path via backward update. Then, the return is averaged by every path in the path set. Now, if the MDP M is deterministic, we can prove that the episodic backward operator is a contraction in the sup-norm, and the fixed point of the episodic backward operator is the optimal action-value function of the MDP regardless of the time schedule. Theorem 2. (Contraction of episodic backward operator and the fixed point) Suppose M = (S, A, P, R) is a deterministic MDP. Then, for any time schedule {λ s,a (t)} ∞ t=1,(s,a)∈S×A ∈ λ, H β t is a contraction in the sup-norm for any t, i.e

EQUATION

Furthermore, for any time schedule {λ s,a (t)} ∞ t=1,(s,a)∈S×A ∈ λ, the fixed point of

H β t is the optimal Q function Q * .

Proof. First, we prove T β,Q (ps,a)i (j) is a contraction in the sup-norm for all j. Since M is a deterministic MDP, we can reduce the return as

EQUATION

Also, at the deterministic MDP, the episodic backward operator can be reduced to

EQUATION

Therefore, we can finally conclude that

EQUATION

Therefore, we proved that episodic backward operator is a contraction independent of the schedule. Finally, we prove that the distinct episodic backward operators in terms of schedule has same fixed point, Q * . A sufficient condition to prove this is given by

max 1≤j≤|(ps,a)i| T β,Q * (ps,a)i (j) = Q * (s,a)-r(s,a) γ ∀1 ≤ i ≤ |p s,a |.

We will prove this by contradiction. Assume ∃i s.

t. max 1≤j≤|(ps,a)i| T β,Q * (ps,a)i (j) = Q * (s,a)-r(s,a) γ .

First, by the definition of Q * fuction, we can bound Q * (s ik , a ik ) and Q * (s ik , :) for every k ≥ 1 as follows.

EQUATION

Note that the equality holds if and only if the path (s i , a i ) k-1 i=0 is the optimal path among the ones that start from (s 0 , a 0 ). Therefore, ∀1 ≤ j ≤ (p s,a ) i , we can bound T β,Q * (ps,a)i (j).

EQUATION

Since this occurs for any arbitrary path, the only remaining case is when

∃i s.t. max 1≤j≤|(ps,a)i| T β,Q * (ps,a)i (j) < Q * (s,a)-r(s,a) γ .

Now, let's speculate on the path s 0 , s 1 , s 2 , ...., s |(ps,a)i)| . Let's first prove the contradiction when the length of the contradictory path is finite. If Q * (s i1 , a i1 ) < γ -1 (Q * (s, a) -r(s, a)), then by the bellman equation, there exists action a = a i1 s.t Q * (s i1 , a) = γ -1 (Q * (s, a) -r(s, a)). Then, we can find that T β,Q * (ps,a)1 (1) = γ -1 (Q * (s, a) -r(s, a)) so it contradicts the assumption. Therefore, a i1 should be the optimal action in s i1 .

Repeating the procedure, we can find that a i1 , a i2 , ..., a |(ps,a)i)|-1 are optimal with respect to their corresponding states.

Finally, we can find that T β,Q * (ps,a)1 (|(p s,a ) i )|) = γ -1 (Q * (s, a) -r(s, a)) since all the actions satisfies the optimality condition of the inequality in equation 7. Therefore, it is a contradiction to the assumption.

In the case of infinite path, we will prove that for any > 0, there is no path that satisfy Q * (s,a)-r(s,a) γ -max 1≤j≤|(ps,a)i| T β,Q * (ps,a)i (j) = .

Since the reward function is bounded, we can define r max as the supremum norm of the reward function. Define q max = max s,a |Q(s, a)| and R max = max{r max , q max }. We can assume R max > 0. Then, let's set n = log γ

(1-γ) Rmax + 1. Since γ ∈ [0, 1), R max γ n 1-γ < . Therefore, by applying the procedure on the finite path case for 1 ≤ j ≤ n , we can conclude that the assumption leads to a contradiction. Since the previous n trajectories are optimal, the rest trajectories can only generate a return less than .

Finally, we proved that max 1≤j≤|(ps,a)i| T β,Q * (ps,a)i (j) = Q * (s,a)-r(s,a) γ ∀1 ≤ i ≤ |p s,a | and therefore, every episodic backward operator has Q * as the fixed point.

Finally, we will show that the online episodic backward update algorithm converges to the optimal Q function Q * . Restatement of Theorem 1. Given a finite, deterministic, and tabular MDP M = (S, A, P, R), the episodic backward update algorithm, given by the update rule Q t+1 (s t , a t ) = (1 -α t )Q t (s t , a t ) + α t r(s t , a t ) + γ |ps t ,a t | i=1 (λ (st,at) ) i (t) max 1≤j≤|(ps t ,a t )i| T β,Q (ps t ,a t )i (j) converges to the optimal Q function w.p. 1 as long as

• The step size satisfies the Robbins-Monro condition;

• The sample trajectories are finite in lengths l: E[l] < ∞;

• Every (state, action) pair is visited infinitely often.

For the proof of Theorem 1, we follow the proof of Melo, 2001 . Lemma 1. The random process ∆ t taking values in R n and defined as ∆ t+1 (x) = (1 -α t (x))∆ t (x) + α t (x)F t (x) converges to zero w.p.1 under the following assumptions:

• 0 ≤ α t ≤ 1, t α t (x) = ∞ and t α 2 t (x) < ∞; • E [F t (x)|F t ] W ≤ γ ∆ t W , with γ < 1;

• var [F t (x)|F t ] ≤ C 1 + ∆ t 2 W , for C > 0.

By Lemma 1, we can prove that the online episodic backward update algorithm converges to the optimal Q * .

Proof. First, by assumption, the first condition of Lemma 1 is satisfied. Also, we can see that by substituting ∆ t (s, a) = Q t (s, a) -Q * (s, a), and F t (s, a) = r(s, a) + γ Since the reward function is bounded, the third condition also holds as well. Finally, by Lemma 1, Q t converges to Q * .

Although the episodic backward operator can accommodate infinite paths, the operator can be practical when the maximum length of the episode is finite. This assumption holds for many RL domains, such as ALE.

:

We used NVIDIA Titan X for all experiments.

https://github.com/ShibiHe/Q-Optimality-Tightening

Figures and Tables:

Figure 1: A motivating example for episodic backward update. Left: Simple navigation domain with 4 states and a single rewarded transition. Right: The probability of learning the optimal path (s 1 → s 3 → s 4 ) after updating the Q-values with sample transitions.

Figure 2: 2D MNIST maze

Figure 3: Median relative lengths of EBU and other baseline algorithms. As the wall density increases, EBU outperforms other baselines more significantly. The filled regions indicate the standard deviation of results from 50 random mazes.

Figure 5: Scores of EBU and baselines on 4 games: 'Assault', 'Breakout', 'Gopher' and 'Video Pinball'. Moving average test scores of 40 epochs with window size 4 are plotted. The filled regions indicate the standard deviation of results from 8 random seeds.

Figure 6: Learning curves of EBU and baselines on 49 games of the Arcade Learning Environment. Up: median over 49 games. Down: mean over 49 games. We use the average of 30 no-op scores of 8 agents with different random seeds. Use of different evaluation methods and seeds may output different results.

update until k =1.

Figure 7: Target generation process from the sampled episode E

For a given time schedule and MDP, now we define the episodic backward operator. Definition 3. (Episodic backward operator) Assume a MDP M = (S, A, P, R), and time schedule {λ s,a (t)} ∞ t=1,(s,a)∈S×A ∈ λ.

E s ∈S,P (s |s,a)   r(s, a, s ) + γ |ps,a| i=1 (λ (s,a) (t)) i 1(s i1 = s ) max 1≤j≤|(ps,a)i|

|ps,a|i=1 (λ (s,a) ) i (t) max 1≤j≤|(ps,a)i| T β,Q (ps,a)i (j) -Q * (s, a). E [F t (s, a)|F t ] ∞ = (H β t Q t )(s, a) -(H β t Q * )(s, a) ∞ ≤ γ ∆ t ∞, where the inequality holds due to the contraction of the episodic backward operator.Then, var [F t (x)|F t ] = var r(s, a) + γ |ps,a| i=1 (λ (s,a) ) i (t) max 1≤j≤|(ps,a)i| T β,Q (ps,a)i (j) F t .

Algorithm 1 Simple Episodic Backward Update (single episode, tabular)1: Initialize the Q-table Q ∈ R S×A with zero matrix.Q(s, a) = 0 for all state action pairs (s, a) ∈ S × A. 2: Experience an episode E = {(s 1 , a 1 , r 1 , s 2 ), . . . , (s T , a T , r T , s T +1 )} 3: for t = T to 1 do

Table content: <table><tr><td>4:</td></tr></table>

Relative lengths (Mean & Median) on MNIST Maze after 100,000 steps of training.

Table content: <table><tr><td>Wall density</td><td>EBU (ours)</td><td>Uniform</td><td>N-step</td></tr><tr><td>20%</td><td colspan="2">5.44 2.42 14.40 9.25</td><td>3.26 2.24</td></tr><tr><td>30%</td><td colspan="3">8.14 3.03 25.63 21.03 8.88 3.32</td></tr><tr><td>40%</td><td colspan="3">8.61 2.52 25.45 22.71 8.96 3.50</td></tr><tr><td>50%</td><td colspan="3">5.51 2.27 22.36 17.90 11.32 4.93</td></tr></table>

. We train EBU and baselines agents for 10 million frames on 49 Atari games with the same network structure, hyperparameters and evaluation methods used by Nature DQN. We divide the training steps into

Table content: <table><tr><td>4335.4</td></tr><tr><td>0.3 0.7 0.7 1.3 1.3 2.0 2.7 2.8 3.1 4.0 9.6 10.0 10.3 12.4 17.2 17.3 18.2 21.2 25.3 27.2 27.4 27.7 36.0 50.2 55.2 56.5 76.3 77.2 281.9 486.4</td></tr><tr><td>-73.4 -32.0 -29.4 -19.5 -14.3 -14.3 -12.5 -11.4 -9.4 -6.1 -5.8 -4.0 -1.6 -1.4 -0.7 -0.6 -0.2 -0.1</td></tr><tr><td>Krull Robotank Up and Down Enduro Tennis Crazy Climber Asterix Name This Game Q*Bert Kung-Fu Master Kangaroo Ms. Pacman Centipede River Raid Frostbite Private Eye Amidar Montezuma's Revenge Alien Ice Hockey Venture H.E.R.O. Chopper Command Demon Attack Space Invaders Asteroids Seaquest Gravitar Freeway Battle zone Bowling Road Runner Wizard of Wor Bank heist Time Pilot Star Gunner Tutankham Fishing Derby Pong Zaxxon Beam rider Boxing Jamesbond Double Dunk Assault Gopher Atlantis Breakout Video Pinball</td></tr><tr><td>Figure 4: Relative performance (Eq.(3)) of EBU over Nature DQN in percents (%) after 10 million</td></tr><tr><td>frames of training.</td></tr></table>

Summary of training time and human normalized performance. Training time refers to the total time required to train 49 games of 10M frames each (490M frames in total).

Table content: <table><tr><td/><td>Training Time (49 games, 1 GPU)</td><td>Mean</td><td>Median</td></tr><tr><td>EBU (10M)</td><td>152 hours</td><td colspan="2">255.19% 53.65%</td></tr><tr><td>Nature DQN (10M)</td><td>138 hours</td><td colspan="2">133.95% 40.42%</td></tr><tr><td>Optimality Tightening (10M)</td><td>407 hours</td><td colspan="2">162.66% 49.42%</td></tr><tr><td>Prioritized Experience Replay (10M)</td><td>146 hours</td><td colspan="2">156.57% 40.86%</td></tr><tr><td>Retrace(λ) (10M)</td><td>154 hours</td><td>93.77%</td><td>41.99%</td></tr></table>

Summary of raw scores after 10 million frames of trainig. Mean scores from 8 random seeds are used.

Table content: <table><tr><td/><td>EBU</td><td colspan="2">Nature DQN OT</td><td colspan="2">Retrace Prioritized ER</td></tr><tr><td>Alien</td><td>708.08</td><td>690.32</td><td>1078.67</td><td colspan="2">708.29 1026.96</td></tr><tr><td>Amidar</td><td>122.07</td><td>125.42</td><td>220.00</td><td colspan="2">182.68 167.63</td></tr><tr><td>Assault</td><td>4109.18</td><td>2426.94</td><td>2499.23</td><td colspan="2">2989.05 2720.69</td></tr><tr><td>Asterix</td><td>1898.12</td><td>2936.54</td><td>2592.50</td><td colspan="2">1798.54 2218.54</td></tr><tr><td>Asteroids</td><td>1002.17</td><td>654.99</td><td>985.88</td><td colspan="2">886.92 993.50</td></tr><tr><td>Atlantis</td><td>66271.67</td><td>20666.84</td><td colspan="3">57520.00 98182.81 35665.83</td></tr><tr><td>Bank heist</td><td>359.62</td><td>234.70</td><td>407.42</td><td colspan="2">223.50 312.96</td></tr><tr><td>Battle zone</td><td>26002.44</td><td>22468.75</td><td colspan="3">20400.48 30128.36 20835.74</td></tr><tr><td>Beam rider</td><td>5628.99</td><td>3682.92</td><td>5889.54</td><td colspan="2">4093.76 4586.07</td></tr><tr><td>Bowling</td><td>78.80</td><td>65.23</td><td>53.45</td><td>42.62</td><td>42.74</td></tr><tr><td>Boxing</td><td>55.95</td><td>37.28</td><td>60.89</td><td>6.76</td><td>4.64</td></tr><tr><td>Breakout</td><td>174.76</td><td>28.36</td><td>75.00</td><td colspan="2">171.86 164.22</td></tr><tr><td>Centipede</td><td>6052.38</td><td>6207.30</td><td>5277.79</td><td colspan="2">5986.16 4385.41</td></tr><tr><td>Chopper Command</td><td>1287.08</td><td>1168.67</td><td>1615.00</td><td colspan="2">1353.76 1344.24</td></tr><tr><td>Crazy Climber</td><td>65329.63</td><td>74410.74</td><td colspan="3">92972.08 64598.21 53166.47</td></tr><tr><td>Demon Attack</td><td>7924.14</td><td>7772.39</td><td>6872.04</td><td colspan="2">6450.84 4446.03</td></tr><tr><td>Double Dunk</td><td>-16.19</td><td>-17.94</td><td>-15.92</td><td colspan="2">-15.81 -15.62</td></tr><tr><td>Enduro</td><td>415.59</td><td>516.10</td><td>615.05</td><td colspan="2">208.10 308.75</td></tr><tr><td>Fishing Derby</td><td>-39.13</td><td>-65.53</td><td>-69.66</td><td colspan="2">-75.74 -78.49</td></tr><tr><td>Freeway</td><td>19.07</td><td>16.24</td><td>14.63</td><td>15.26</td><td>9.35</td></tr><tr><td>Frostbite</td><td>437.92</td><td>466.02</td><td>2452.75</td><td colspan="2">825.00 536.00</td></tr><tr><td>Gopher</td><td>3318.50</td><td>1726.52</td><td>2869.08</td><td colspan="2">3410.75 1833.67</td></tr><tr><td>Gravitar</td><td>294.58</td><td>193.55</td><td>263.54</td><td colspan="2">272.08 319.79</td></tr><tr><td>H.E.R.O.</td><td>3089.90</td><td>2767.97</td><td colspan="3">10698.25 3079.43 3052.04</td></tr><tr><td>Ice Hockey</td><td>-4.71</td><td>-4.79</td><td>-5.79</td><td>-6.13</td><td>-7.73</td></tr><tr><td>Jamesbond</td><td>391.67</td><td>183.35</td><td>325.21</td><td colspan="2">436.25 421.46</td></tr><tr><td>Kangaroo</td><td>535.83</td><td>709.88</td><td>708.33</td><td colspan="2">538.33 782.50</td></tr><tr><td>Krull</td><td>7587.24</td><td>24109.14</td><td>7468.70</td><td colspan="2">6346.40 6642.58</td></tr><tr><td>Kung-Fu Master</td><td>20578.33</td><td>21951.72</td><td colspan="3">22211.25 18815.83 18212.89</td></tr><tr><td colspan="2">Montezuma's Revenge 1.04</td><td>3.95</td><td>0.00</td><td>0.00</td><td>0.43</td></tr><tr><td>Ms. Pacman</td><td>1249.79</td><td>1861.80</td><td>1849.00</td><td colspan="2">1310.62 1784.75</td></tr><tr><td>Name This Game</td><td>6960.46</td><td>7560.33</td><td>7358.25</td><td colspan="2">6094.08 5757.03</td></tr><tr><td>Pong</td><td>5.53</td><td>-2.68</td><td>2.60</td><td>8.65</td><td>12.83</td></tr><tr><td>Private Eye</td><td>953.58</td><td>1388.45</td><td>1277.53</td><td colspan="2">714.97 269.28</td></tr><tr><td>Q*Bert</td><td>785.00</td><td>2037.21</td><td>3955.10</td><td colspan="2">3192.08 1215.42</td></tr><tr><td>River Raid</td><td>3460.62</td><td>3636.72</td><td>4643.62</td><td colspan="2">4178.92 6005.62</td></tr><tr><td>Road Runner</td><td>10086.74</td><td>8978.17</td><td colspan="3">19081.55 9390.83 17137.92</td></tr><tr><td>Robotank</td><td>11.65</td><td>16.11</td><td>12.17</td><td>9.90</td><td>6.46</td></tr><tr><td>Seaquest</td><td>1380.67</td><td>762.10</td><td>2170.33</td><td colspan="2">2275.83 1955.67</td></tr><tr><td>Space Invaders</td><td>797.29</td><td>755.95</td><td>869.83</td><td colspan="2">783.35 762.54</td></tr><tr><td>Star Gunner</td><td>2737.08</td><td>708.66</td><td>1710.83</td><td colspan="2">2856.67 2629.17</td></tr><tr><td>Tennis</td><td>-3.41</td><td>0.00</td><td>-6.37</td><td>-2.50</td><td>-10.32</td></tr><tr><td>Time Pilot</td><td>3505.42</td><td>3076.98</td><td>4012.50</td><td colspan="2">3651.25 4434.17</td></tr><tr><td>Tutankham</td><td>204.83</td><td>165.27</td><td>247.81</td><td colspan="2">156.16 255.74</td></tr><tr><td>Up and Down</td><td>6841.83</td><td>9468.04</td><td>6706.83</td><td colspan="2">7574.53 7397.29</td></tr><tr><td>Venture</td><td>105.10</td><td>96.70</td><td>106.67</td><td>50.85</td><td>60.40</td></tr><tr><td>Video Pinball</td><td>84859.24</td><td>17803.69</td><td colspan="3">38528.58 18346.58 55646.66</td></tr><tr><td>Wizard of Wor</td><td>1249.89</td><td>529.85</td><td>1177.08</td><td colspan="2">1083.69 1175.24</td></tr><tr><td>Zaxxon</td><td>3221.67</td><td>685.84</td><td>2467.92</td><td colspan="2">596.67 3928.33</td></tr></table>

Peer review (iclr2018):
 This paper proposes a new way of sampling data for updates in deep-Q networks. The basic principle is to update Q values starting from the end of the episode in order to facility quick propagation of rewards back along the episode. The paper is interesting, but it lacks the proper comparisons to previously published techniques. The results presented by this paper shows improvement over the baseline. But the Atari results is still significantly worse than the current SOTA. In the non-tabular case, the authors have actually moved away from Q learning and defined an objective that is both on and off-policy. Some (theoretical) analysis would be nice. It is hard to judge whether the objective defined in the non-tabular defines a contraction operator at all in the tabular case. There has been a number of highly relevant papers. Prioritized replay, for example, could have a very similar effect to proposed approach in the tabular case. In the non-tabular case, the Retrace algorithm, tree backup, Watkin*s Q learning all bear significant resemblance to the proposed method. Although the proposed algorithm is different from all 3, the authors should still have compared to at least one of them as a baseline. The Retrace algorithm specifically has also been shown to help significantly in the Atari case, and it defines a convergent update rule.