Mixture of Step Returns in Bootstrapped DQN
Authors: PoHan Chiang
Hsuan-Kung Yang
Zhang-Wei Hong
Chun-Yi Lee
Venue:  (2021)
Keywords: Reinforcement Learning

Abstract: The concept of utilizing multi-step returns for updating value functions has been adopted in deep reinforcement learning (DRL) for a number of years. Updating value functions with different backup lengths provides advantages in different aspects, including bias and variance of value estimates, convergence speed, and exploration behavior of the agent. Conventional methods such as TD-lambda leverage these advantages by using a target value equivalent to an exponential average of different step returns. Nevertheless, integrating step returns into a single target sacrifices the diversity of the advantages offered by different step return targets. To address this issue, we propose Mixture Bootstrapped DQN (MB-DQN) built on top of bootstrapped DQN, and uses different backup lengths for different bootstrapped heads. MB-DQN enables heterogeneity of the target values that is unavailable in approaches relying only on a single target value. As a result, it is able to maintain the advantages offered by different backup lengths. In this paper, we first discuss the motivational insights through a simple maze environment. In order to validate the effectiveness of MB-DQN, we perform experiments on the Atari 2600 benchmark environments and demonstrate the performance improvement of MB-DQN over a number of baseline methods. We further provide a set of ablation studies to examine the impacts of different design configurations of MB-DQN.

Under review as a conference paper at ICLR 2021
MIXTURE OF STEP RETURNS IN BOOTSTRAPPED DQN
Anonymous authors Paper under double-blee blind review
ABSTRACT
The concept of utilizing multi-step returns for updating value functions has been adopted in deep reinforcement learning (DRL) for number of years. Updating value functions with different backup lengths provides advantages in different aspects, including bias and variance of value estimates, convergence speed, and exploration behavior of the agent. Conventional methods such as TD (A) leverage these advantages by using target value equivalent to exponential average of different step returns. Nevertheless, integrating step returns into a single target sacrifices the diversity of the advantages offered by different step return targets. To address this issue, we propose Mixture Bootstrapped DQN (MB-DQN) built on top of bootstrapped DQN, and uses different backup lengths for different bootstrapped heads. MB-DQN enables heterogeneity of the target values that is unavailable in approaches relying only on single target value. As a result, it is able maintain the advantages offered by different backup lengths. In this paper, we first discuss the motivational insights through a simple maze environment. to validate the effectiveness of MB-DQN, we perform experiments on the Atari 2600 benchmark environments, and demonstrate the performance improvement of MB-DQN over number of baseline methods. We further provide set of ablation studies to examine the impacts of different design configurations MB-DQN.
order
INTRODUCTION
In recent value-based deep reinforcement learning (DRL), a value function is usually utilized to evaluate state values, which stand for estimates of the expected long-term cumulative rewards that might be collected by an agent. In order to perform such an evaluation, deep neural network (DNN) employed by number of contemporary value-based DRL. methods (Mnih et al. 2015) Wang et al. 2016 Hasselt et al. 2016; Osband et al., 2016)] Hessel et al.) 2018) as the value function approximator, in which the network parameters are iteratively updated based on the agent's experience of interactions with environment, For many of these methods (Mnih et al. 2015 Wang et al. 2016 Hasselt et al.) 2016; Osband et al., 2016 Hessel et al. 2018), the update procedure carried out by one-step temporal-differene difference (TD) learning (Sutton & Barto 1998) (or simply "one-step TD"), which calculates the error between an estimated state value and a target differing by one timestep. One-step TD has been demonstrated effective in backing up immediate reward signals collected by an agent. Nevertheless, the long temporal horizon that the reward signals from farther states have to propagate through might lead an extended learning period of the value function approximator.
Learning from multi-step returns (Sutton & Barto 1998) is a way of propagating rewards newly observed by the agent faster earlier visited states, and has been adopted in several previous works. Asynchronous advantage actor-critic (A3C) (Mnih et al. 2016) employs multi-step returns as targets to update the value functions of its asynchronous threads. Rainbow deep Q-network (Rainbow DQN) (Hessel et al. 2018)) also utilizes multi-step returns during the backup procedure. The authors in (Barth-Maron al. (218)) also modify the target value function of deep deterministic dolicy gradient (DDPG) (Lillicrap al. (0166) to estimate TD errors using multi-step returns. Updating value functions with different backup lengths provides advantages in different aspects, including bias and variance of value estimates, convergence speed, and exploration behavior of the agent. Backing up reward signals through multi-step returns shifts the vtasinar tradeoff (Hessel et al., 2018). Therefore, backing up with different step return lengths (or simply "backup length' hereafter (Asis) (et al.) (018)) might lead to different target values in the Bellman equation, resulting in different exploration behaviors of the agent as well different achievable performance of it. The authors

---

Under review as a conference paper at ICLR 2021
in (Amiranashvili et al.) 2018) have demonstrated that the performance of the agent varies with different backup lengths, and showed that both very short and very long backup lengths could cause performance drops. These insights suggest that identifying the best backup length for environment is not straightforward. In addition, although learning based on multi-step returns enhances the immediate sensitivity to future rewards, it is at the expense of greater variance which may cause the value function approximator to require more data samples to converge to the true expectation. Moreover, relying on a single target value with any specific backup length constrains the exploration behaviors of the agent, and might limit the achievable performance of it.
Based on the above observations, there have been several research works proposed to unify different target values with different backup lengths to leverages their respective advantages. The traditional TD (A) (Sutton & Barto 1998) uses a target value equivalent to an exponential average of all n-step returns (where n. is natural number), providing faster empirical convergence by interpolating between low-variance TD returns and low-bias Monte Carlo returns. DQN (A) (Daley & Amato 2019) further proposes efficient implementation of TD (A) for DRL by modifying the replay buffer memory such that A-returns can be pre-computed. Although these methods benefit from combining multiple distinct backup lengths, they still rely on a single target value during the update procedure. Integrating step returns into a single target value, nevertheless, may sacrifice the diversity of the advantages provided by different step return targets.
As a result, in this paper, we propose Mixture Bootstrapped DQN (abbreviated as "MB-DQN") to address the above issues. MB-DON is built on top of bootstrapped DQN (Osband et al.) (0166) which contains multiple bootstrapped heads with randomly initialized weights to learn a set of value functions. MB-DQN leverages the advantages of different step return targets by assigning distinct backup length to each bootstrapped head. Each bootstrapped head maintains its own target value derived from the assigned backup length during the update procedure. Since the backup lengths of the bootstrapped heads are distinct from each other, MB-DQN provides heterogeneity in the target values as well as diversified exploration behaviors of the agent that is unavailable in approaches relying only on a single target value. To validate the proposed concept, in our experiments, we first provide motivational insights on the influence of different configurations of backup lengths in a simple maze environment. We then evaluate the proposed MB-DQN on the Atari 2600 (Bellemare et al., 2015) benchmark environments, and demonstrate its performance improvement over a number of baseline methods. We further provide a set of ablation studies analyze the impacts of different design configurations of MB-DQN. In summary, the primary contributions of this paper include: (1) introducing an approach for maintaining the advantages from different backup lengths, (2) providing heterogeneity in the target values by utilizing multiple bootstrapped heads, and (3) enabling diversified exploration behaviors of the agent.
The remainder of this paper is organized as the following. Section 2 provides the background material related to this work. Section 3 walks through the proposed MB-DQN methodology. Section reports the experimental results, and presents a set of the ablation analyses. Section 5 concludes this paper.
2 BACKGROUND
In this section, we provide the background material related to this work. We first introduce the basic concepts of the Markov Decision Process (MDP) and one-step return, followed by an explanation of the concept of multi-step returns. Next, we provide a brief overview of the Deep Q-Network (DQN).
2.1 MARKOV DECISION PROCESS AND ONE-STEP RETURN
In RL, an agent interacting with an environment & with state space S and action space A is often formulated as an MDP. At each timestep t, the agent perceives state s; E S. takes an action a E AA according to its policy [[]ss). receives reward rı ~ R(s,, dz), and transits to next state 8441 ~ p(8 8t, at), where R(s;, az) and p(s+11 (st, a:) are the reward function and transition probability function, respectively. The main objective of the agent is to learn an optimal policy
T (als) that maximizes discounted cumulative return G, >E=>> " where Y (0, 1] is the discount factor and T is the horizon. For a given policy π (a]s), the state value function V and state-action value function Q" are defined as the expected discounted cumulative return G2 starting
2

---

Under review as a conference paper at ICLR 2021
from state and a state-action pair (s. a) respectively, and can be represented as the following:
(*) |s 8, m), (x, a) E[Gr] Uz a, T..
In order maximize E[G:], conventional value-based RL methods often use one-step TD learning to iteratively update V and Q" Take Q" for example, the update rule is expressed as the following:
((5,, 0t) ((s,, az) + air (Q( G++1) ((s,,
(2)
where (0, 1] is step size parameter which controls the update speed. This update procedure only considers the immediate return Tr and (st+++1 ac-1), which is together called one-step return.
2.2 MULTII-TTEP RETURN
Multi-step return a variant of one-step return presented the previous section. Multi-step return modifies the target of one-step return through bootstrapping over longer time intervals. It replaces the single reward ry in Eq. (2) with the truncated multi-step return R, which is represented as follows:
R
re+i
/=0
where is the selected backup length. The update rule of Eq. 22 is then re-written the following:
Q(st, ax) + Q(s,, a1) a[R 7 n- + 11
Q(s,,
longer backup length n has been shown to increase the variance of the estimated (st, ar) as well decrease its bias (Jaakkola al. 1994). Despite of the high-variance and the increased computational cost, multi-step return enhances the immediate sensitivity of the value approximator to future rewards, and allows them to backup faster. As result, in certain cases, it is possible to achieve a faster learning speed for the value approximator by using an appropriate backup length n larger Hessel al. 2018 Amiranashvili al. 2018).
than one (Sutton & Barto 1998
2.3 DEEP Q-NETWORK
DQN is a DNN parameterized by for approximating the optimal Q-function. DQN is trained using samples drawn from experience replay buffer Z, and is updated based on one-step TD learning with an objective to minimize a loss function L LDQN, which is typically expressed as the following:
LDQN E....ne [(v., Q 1s,a, a, {]
(5)
where Vs,a rı + max, ( a, 0 is the one-step target value, U(Z) is uniform distribution over Z, and A is the parameters of the target network. 0 is updated by at predefined intervals.
METHODOLOGY
In this section, we first demonstrate the impacts of different backup lengths on the behaviors of an agent in a simple maze environment. Then, we walk through the details of the MB-DQN framework.
Dense Maze
Step Retum
Stop Retura
Stariin gnd Good (il reword)
Timerup 10000
Timedop - 10020
Tinestp 100000
Timestep - 10000)
Timestp 50000
"Tmostep 100000
(B)
Figure I: A visualization of the behaviors of the agents with different backup lengths. (a) presents the layout of the maze environment (denoted as Dense Maze), which contains a starting grid and goal grid. (b) and (c) illustrate the behaviors of the agents updated using I-step return and 5-step return, respectively. is observed that the agent trained with 5-step return reaches the goal through shorter diagonal trajectories, while the agent trained with 1-step return explores more grids in the early stage.
3

---

Under review as a conference paper at ICLR 2021
3.1 AGENT BEHAVIOR WITH DIFFERENT BACKUP LENGTHS IN DQN
To illustrate the impacts of different backup lengths on an agent's behavior, we first consider a toy model in two-dimensional maze environment containing starting point and goal, as depicted in Fig. (a). We use DQN as our default agent and perform our experiments on this maze environment (denoted Dense Maze) with dense rewards. In this setting, the reward of grid gradually decreases as its distance to the goal increases. We depict the states visited by the agents for 100k timesteps in the training phase in Figs. (b) and (c). is observed that the agent trained with 5-step return reaches the goal through a shorter path than that of the 1-step return case. This is because the longer backup length allows the agent to adjust its value function estimation faster. On the other hand, although the agent trained with 1 1-step return might converge slower than that of the 5-step return case, it is observed that I-step return enables the agent to visit and explore more states in the early stage. This is because the reward signal from a farther state has to propagate through longer temporal horizon. Therefore, the agent explores more extensively before learning an effective policy to reach the goal.
Mixture Bootstrapped DQN (MB-DQN)
Vanilla Bootstrapped DQN
Head
Head I Oftice Bg)
Shared Convolutional Neural Network
Hoadl 2ris.;;
Shared Convolutional Neural Network
2x (.)
K 015...8)
Q,554:
(4)
(b)
Figure 2: Overview of the proposed MB-DQN framework.
3.2 MIXTURE OF STEP RETURNS IN BOOTSTRAPPED DQN
In order to combine step returns with different backup lengths, we choose bootstrapped DQN (Osband et al. 2016) as our backbone framework. Bootstrapped DQN modifies DQN to approximate a distribution over Q-values via bootstrapping, and has demonstrated both the improved learning speed as well as the performance of the agents in various environments. At the beginning of an episode, bootstrapped DQN uniformly samples Q-value function head Q& (8, a: 0s), k E {1, "i,,...,, K} from its K bootstrapped Q-value function heads, as shown in Fig. 2 The agent then performs its control according to Qu (s, a; 0&) during the entire episode. Bootstrapped DQN re-samples a Q-value function head for each episode based the same backup length (i.e., 1-step return) to calculate the target value (i.e., Eq. (b). The framework, nevertheless, might be lack in diversity and heterogeneity among the bootstrapped heads.
As a result, we leverage the advantages of distinct Q-value function heads in bootstrapped DQN, and propose the usage of mixture backup lengths for different bootstrapped Q-value function heads in our MB-DQN framework, which is shown in Fig. 2 MB-DQN is similarly implemented as K bootstrapped heads for estimating the Q-value function. where each bootstrapped head l K correspond to its own backup lengths 72.. In each episode, MB-DQN also uniformly and randomly selects head is E (1...., K). and stores the state transition data collected by the agent using this head into a replay buffer. The replay buffer is played back periodically to update the parameters of all the bootstrapped Q-value function heads as well as the shared convolutional neural network. Each head is trained with its own target network Qu(s, 0, and its own target value =² with the truncated multi-step return defined in Eq. B3. The detailed update method is summarized in Algorithm [ while the training methodology is the same as bootstrapped DQN (Osband et al.) (0166). The truncated multi-step returns with different backup lengths thus provide diversity and heterogeneity for the K bootstrapped estimates, which balance the strengths and the weaknesses of different backup lengths.
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Update Methodology of MB-DQN
1: Initialize K Q-networks Q& (s, O2) with random weights O2
2: Let each networks Qk with its own backup length
3: for each update time
4: for each head k = 2.....KK do
5:
R, = =, 7 Re+s
6:
V5.0 R2 + 7 max. Qu(sc+mes argmax max, (setme; Ox):): 0x):0))) 0r)
7:
O2 ze arg ming, E(y.,a Qx,s, (z)))
-Mixdd-1
Sneatout
Prostbele
Enduro
20,000
1,500
300
15,000
1,000
200
2,000
10,000
Avatnge Score
1,000
500
Frcomay
Soaquest
Coayylimber
Obcot
150
30
0,000
10,000
4,000
50,000
2,000
GM
2M
Timesteps
Figure 3: Comparison of the evaluation curves of MB-DQN and the baselines in eight Atari games. [
EXPERIMENTAL RESULTS
In this section, we present the experimental results demonstrate the advantages of the mixture usage of different backup lengths. We first evaluate the proposed MB-DQN on a collection of well-known Atari 2600 (Bellemare al. 2015) games, and compare its performance to different configurations of boostrapped DQN both quantitatively and qualitatively in Section 4.1 Next, we investigate the quality of the data samples collected by MB-DQN, and demonstrate their advantages training an RL agent in Section 4.2 Then, we validate the assumption made in Section that unifying different step return targets to a single target value may not as effective as the proposed MB-DO MB-DQN approach in Section 4.3 Finally, further provide a set of ablation analyses of MB- AB-DQN on Atari games to inspect and discuss the impacts of different configurations on LBBDQQN's performance in Section 4.4
4.1 COMPARISON OF MB-DQN AND BOOTSTRAPPED DQN
Environments. To demonstrate the advantages the mixture usage of different backup lengths, we begin with collection of well-known Atari games, and plot the evaluation curves of eight common Atari games selected from the four different categories (Bellemare et al.] (016). including Breakout, Frostbite, Hero, Enduro, Qhert, Seaquest, CrazyClimber, and Freeway. We additionally provide the experimental results of the remaining games (33 Atari games considered in total) in the appendix.
Baselines. We compare the proposed MB-DQN against two baselines: bootstrapped DQN with (a) all 1-step return heads and (b) all 3-step return heads, which are denoted as Alt-/-Step (Baseline) and All-3-Step (Baseline), respectively. We use ten bootstrapped heads for both MB-DQN and the baselines. MB-DQN (denoted Mixed-I-3-Step (MB-DQN)) is implemented using five bootstrapped heads with 1-step backup length and another five bootstrapped heads with 3-step backup lengths.
Quantitative comparison. The qualitative comparison presented in Fig. 3 It is observed that longer backup lengths do not always guarantee better performances each environment may have its own favor. The All-3-Step baseline outperforms the ASle/-Step baseline six out of eight games,
For all of our experiments. the MB-DQU and the bootstrapped DQN agents are evaluated every 250k timesteps hased on the results voted by the majority of their hootstrapped heads. The evaluation curves are averaged from three random seeds, and drawn with 68% confidence interval, illustrated the shaded regions.
5

---

Under review as a conference paper at ICLR 2021
while it underperforms the All-I-Step baseline in the rest two games and suffers from consideaabl performance drop in Breakout. contrast, the proposed MB-DQN that uses a mixture of step returns outperforms the baselines in terms of its performance and convergence speed for most of the cases.
1-Step Heads
3-Step Heads
Majority Heuds
1-Step Heads
3. Step Heads
Majority Heads
10B
(a) Breakout
(b) Seaquest
Figure 4: Visualization of the agents" attention areas (rendered in red). The attention areas are derived based on (Greydanus al. 2018) and are obtained from the bootstrapped heads of MB-DQN.
Qualitative comparison via attention maps. In order to understand the rationale behind the high performance and advantages offered by MB-DQN, we further visualize the attention areas (Greydanus) et al. (018)) of the agents trained with MB-DQN for three cases: attention areas generated from (a) all of the 1-step bootstrapped heads in MB-DQN (denoted as 1-Step Heads). (b) all of the step bootstrapped heads in MB-DQN (denoted as 3-Step Heads), and (c) the composition of the bootstrapped heads which contribute to the decided actions (i.e., the majority of the bootstrapped heads that vote the resultant actions, denoted as Majority Heads). Please note that the composition in (c) may contain both the Isttep and 3-step bootstrapped heads. Fig. 4 iillustrates the attention areas (rendered in red) of these three cases for two Atari games: Breakout and Seaquest, and highlights their differences by yellow circles. In Breakout, it is observed that the 1-Step Heads case focuses more on the ball, the most important object in this game, than the 3-Step Heads case. It is also observed that when the majority of the bootstrapped heads is considered, the attention of the agent is fell on the ball well, allowing MB-DQN to play as good the All-/-Step baseline in Breakout in Fig. 3, In Seaquest, it is observed that the 1 1-Step Heads case focuses more on the scoreboard, while the 3-Step Heads case focuses more on the enemy and the submarine. The attention areas of the Majority Heads case, on the other hand, cover the areas from both the 1-Step Heads and the 3-Step Heads cases, allowing MB-DQN to outperform the two baselines in Fig. 3 These examples therefore validate that MB-DQN is able to leverage the advantages from different backup lengths, and can achieve superior performance to the two baselines by offering heterogeneity among its bootstrapped heads.
4.2 ANALYSIS OF THE DATA SAMPLE QUALITY FOR MB-DQN
As the experimental results presented in the previous section have quantitatively and qualitatively demonstrated the performance benefits offered by MB- MB-DQN, next dive further to investigate the rationale behind the advantages. We hypothesize that the performance improvements provided by MB-DQN may come from the quality of the collected data samples in the experience replay buffer. In other words, MB-DQN may have benefited from the heterogeneity in the data samples collected by bootstrapped heads with different backup lengths. To validate this hypothesis, we design an experiment containing two agents: one agent is responsible for generating state-action pairs for an experience replay buffer while updating its Q-value network with the data contained in it. The other agent only updates its Q-value network by the existing data samples contained in the replay buffer, without contributing data to it. Both of these agents are implemented with ten bootstrapped heads.
We consider three configurations for the former data generation agent: Mixed- 1-3-Step (MB-DQN) All-I-Step (Baseline), and All-3-Step (Baseline), and two configurations for the latter learning-only agent (i.e., the one without contributing data samples to the replay buffer): All-I-Step (Baseline) and All-3-Step (Baseline). The configurations are evaluated on Seaquest, and are designed such that the former and the latter agents have different configurations. The results of our experiments are plotted in Fig. (a)) where the figures on the top and bottom sides correspond to the cases that the learning-ont agents are configured to All-I-Step (Baseline) and A-tpp (Baseline), respectively. can be observed that the learning only agents trained with the data samples generated by Mixed- 1-3-Step (MB-DQN) outperform the agents trained with the data samples generated by the other

---

Under review as a conference paper at ICLR 2021
Seaquest
"Moobl 120ppp 9400010 anbde DOviarbee Etuandle
Erakest
Qbert
302
Average score
Averagee
254
1054
264
Timesteps
Timesteps
(b)
Figure 5: The evaluation curves of (a) comparison of different configurations of data generation agents and learning-only agents for validating the quality of data samples collected by MB-DQN in Section 4.2 and (b) comparison between the single X-target strategy adopted by DQN (A) (Daley & Amato 2019) and the multiple bootstrapped targets strategy adopted by MB-DQN in Section 4.3
configurations in both cases. These results thus validate our hypothesis that the data samples generated by MB-DQN are superior in quality than those generated by the other configurations, and explain why MB-DQN is able to offer benefits in performance in the environments presented in this paper.
4.3 X-TARGET VERSUS HETEROGENEOUS BOOTSTRAPPED TARGETS
In order to validate our assumption in Section T that unifying different step return targets to single target value may not be as effective as the heterogeneous bootstrapped approach adopted by MB-DQN, in this section, compare these strategies of combining step returns in several Atari environments. For the unified return target strategy, we consider a recently proposed method called DQN (A) (Daley) & Amato 2019), which implements TD (A) by pre-computing X-returns using additional cache for its replay buffer memory. On the other hand, MB-DQN employs a strategy that leverages K heterogencous bootstrapped heads, where each head & K has its own target value. For a fair comparison, we further include a variant of DQN (A), called DQN (X) Ensemble, which employs K bootstrapped heads using A-return as the target value. In our experiments, We set K 10 for MB-DQN and DON (A) Ensemble, where the settings for DQN (A) are configured as its default values (Daley & Amato 2019). The single target value used by DQN (A) is derived from multiple backup lengths ranging from one to a hundred. The evaluation curves of these strategies are plotted in 5 corresponding to the heterogeneous bootstrapped targets strategy (i.c., MB- DQN) grow faster and higher than those corresponding to the singlc-unified unified target strategy (i.c., DQN (A) and DQN (A) Ensemble). The above interesting evidence not only validates our assumption in Section T but also reveals that the advantages offered by the heterogeneity in multiple target values may outweigh the advantages offered by a single TD (A) target that aggregates returns from the long temporal horizon.
can be observed that for the four environments presented in Fig. (b), the curves
4.4 ABLATION ANALYSIS
In this section, we provide set of ablation analyses for the proposed MB-DQN on four selceted Atari games, including Breakout, Qbert, Seaquest, and Freeway, to examine the impacts of different configurations on MB-DQN's performances. We perform two sets of analyses for MB-DQN: (a) different configurations of step returns for the bootstrapped heads, and then (b) different numbers of the bootstrapped heads. Please note that additional experimental results are provided in the appendix.
4.4.1 DIFFERENT CONFIGURATIONS OF STEP RETURNS FOR THE BOOTSTRAPPED HEADS
We consider various step returns less than equal to three, and analyze four different configurations of step returns for the bootstrapped heads in MB-DQN, including Mixed- 1-2-d-----3--- 1-2-3-Step. Mixed-1-2-Step Mixed-1-3-Stepy Mixed-2-3- --e-ep and All-I-Step (Baseline). All of these configurations contain ten bootstrapped heads. The configuration Mixed-1-2 1-2-3-Step consists of three 1-step bootstrapped heads, three 2-step bootstrapped heads, and four 3-step bootstrapped heads. For the configurations Mixed-
7

---

Under review as a conference paper at ICLR 2021
Mond---3/Seep
K-2
K-10 IME DON)
Keg
Kortd (Blowkroe)
Qoart
Breakoot
114
400
124
300
10c
Average score
Seaquan
Irewway
Santuett
Freewyy
30
10c
10c
20
5-
54c
10
254
414
0.4
3M
10M
234
47
561
1M
10MM
Timesteps
[a]
(b)
Figure 6: Impacts of (a) different configurations of step returns for the bootstrapped heads, and (b) different numbers of the bootstrapped heads on the proposed MB-DQN for four different Atari games.
1-2-Step, Siixed-1-3-Step and Mixed-2 Wixedd--33-3 2-3-Step the ten bootstrapped heads are evenly distributed to different backup lengths. The results are presented in Fig. 6 (a). For all of the configurations, is observed that the agents trained with different mixtures of step returns perform similarly, and outperform those trained with the All-I-Slep baseline. These evaluation results thus suggest that the bootstrapped heads in the proposed MB-DQN is not limited to certain configurations of step returns.
4.4.2 DIFFERENT NUMBERS OF THE BOOSTRAPPED HEADS
In bootstrapped DQN (Osband et al. 2016), more bootstrapped heads lead to faster learning, while even a small number of bootstrapped heads is still able to capture most of its benefits. As MB-DQN inherits its architecture from bootstrapped DQN, we investigate the impacts of different numbers of the bootstrapped heads on MB-DQN, and examine if MB MB-DQN still maintains this property or not. We perform a set of experiments with three different configurations of the bootstrapped heads: K 2, 4, and 10. For each of the configuration, MB-DQN is set to consist of K 1-step bootstrapped heads and K/2 3-step bootstrapped heads. On the contrary, the bootstrapped DQN baseline is set as its default configuration and is implemented with K I-step bootstrapped heads.
Fig. 6 (b) illustrates the evaluation curves of the above configurations. In most cases, it is observed that for both MB-DQN and bootstrapped DQN, more bootstrapped heads lead to better performance. It is worth noticing that the proposed MB-DQN trained with two bootstrapped heads outperforms the baseline trained with ten bootstrapped heads in three of four games. This fact shows the significance and advantage of the mixture usage of multi-step returns in bootstrapped heads. On the other hand, MB-DQN's performance drops in Breakout as the number of the bootstrapped heads K become less than that of the baseline. This is caused by the fact that the 3-Step Heads perform worse than the 1- Step Heads in Breakout, as described in Section 4.1 As a result, a smaller K strengthens the negative influence caused by the 3-Step Heads, causing MB-DQN to become sensitive to the undesirable performance in certain bootstrapped heads. The above results thus suggest that an appropriate number of K has to be selected in order to maintain the advantages as well as the performance of
CONCLUSION
In this paper, we proposed MB-DQN for combining and leveraging the advantages of different step return targets using multiple bootstrapped heads. Instead of unifying different step return targets to a single target value, MB-DON assigns a distinct backup length each bootstrapped head. This allows MB-DQN to offer heterogeneity in the target values during its update procedure, and enables DRL agent to have diversified exploration behaviors. In our experiments, we first provided motivational examples to demonstrate the influence of different configurations of backup lengths in a simple maze environment. We then evaluated the proposed MB-DQN methodology on a number of Atari 2600 environments both quantitatively and gualitatively, and validated that MB-DQN is able to outperform a number of baseline methods with different configurations of backup lengths. Finally, we presented of ablation studies to examine the impacts of different design configurations for MB-DQN.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Artemij Amiranashvili, Alexey Dosovitskiy, Vladlen Koltun, and Thomas Brox. Analyzing the role of temporal differencing in deep reinforcement learning. In Proceedings of International Conference on Learning Representations (ICLR), 2018.
Kristopher De Asis, J. Fernando Sormandez-Gaacchh G. Zacharias Holland, and Richard S. Sutton. Multi-step reinforcement learning: A unifying algorithm. In Proceedings of AAAI Conference on Artificial Intelligence, pp. 2902-2909 2909, 2018.
Gabriel Barth-Maron, Matthew W. Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva TB, Alistair Muldal, Nicolas Heess, and Timothy P. Lillierap. Distributed distributional deterministic policy gradients. In Proceedings of International Conference on Learning Representations (ICLR), 2018.
Mare Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. In Proceedings of International Joint Conference on Artificial Intelligence (ICCAI, pp. 4148-4152, 2015.
Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying count-based exploration and intrinsic motivation. In Proceedings of Advances in Neural Information Processing Systems (NIPS), pp. 1471-1479, Dec. 2016.
Brett Daley and Christopher Amato. Reconciling - returns with experience replay. In Proceedings of Advances Neural Information Processing Systems (NIPS), pp. 1133-1142. 2019.
Samuel Greydanus, Anurag Koul, Jonathan Dodge, and Alan Fern. Visualizing and understanding atari agents. In Proceedings of International Conference on Machine Learning (ICML), volume 80,
pp. 1787-1796, 2018.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pp. 2094-2100 2016.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pp. 3215-3222, 2018.
Tommi S. Jaakkola, Michael Jordan, and Satinder P. Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation, 6(6):1185-1200 1994.
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proceedings of International Conference Learning Representations (ICLR), 2016.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, pp. 929-533, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of International Conference on Machine Learning (ICML), pp. 1928-1121111 1937, 2016.
Nikolay Nikolov. Rltf: Reinforcement learning in tensorflow.
https://github..
n honii ko kolov// rltf 2018.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Proceedings of Advances Neural Information Processing Systems (NIPS),
pp. 4026-4034. 2016.

---

Under review as a conference paper at ICLR 2021
Jing Peng and Ronald J. Williams. Incremental multi-step q-learning. In Proceedings of International Conference on Machine Learning (ICML), pp. 226-232, 1994.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In Proceedings of International Conference on Learning Representations (ICLR), 2016.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 1998.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Ducling network architectures for deep reinforcement learning. In Proceedings of International Conference Machine Learning (ICML), pp. 1995-2000 -995-2003, 2016.
Christopher John Comnish Hellaby Watkins. Learning from delayed rewards. In PhD thesis, King" College, Cambridge, pp. 226-232, 1989.
Appendices
A1 ADDITIONAL BACKGROUND MATERIAL
In this section, provide additional background materials related to work. We first introduce the concept of DQN (A) (Daley & Amato 2019), which is compared Section 4.3. Next, we explain the generation method of the attention maps (Greydanus al. 2018) used for the qualitative comparisons in Section 4.1 of the main manuscript.
A1.1 DQN (A)
DQN (A) DDaley & Amato 2019) incorporates the concept of X-return into DQN by modifying the replay buffer, with an aim to reduce the computation time required for deriving A-return. The replay buffer is modified to store the X-return R² at timestep along with its corresponding transition. The value of R² is computed in recursive fashion, allowing repeated computations of X-returns to be reduced when the same transitions are sampled multiple times. The recursive rule of R2 is thus expressed as follows:
R = R 7 max ((s+1,aa],
(AI)
where It] = re + max.c ((++11, a) is the one-step return target at timestep f, Q is the state-action value function, y is the discount factor, and st+1 is the next state. order to reuse outdated X- returns caused by Q-function updates, DQN (A) introduces a mechanism which periodically samples random intervals consecutive transitions from the experience replay buffer, and stores them into another cache memory. During each update, the transitions in the cache are refreshed by the current Q-function. The agent then samples batches of training data from the relatively smaller cache using a prioritized sampling mechanism similar to the one used by the prioritized replay buffer (Schaul et al.
2016) (i.c.. the larger the TD error of the transition is, the more likely would be sampled). DQN (A)
has been validated with two different X-return estimators, Peng's (A) (Peng & Williams, 1994 and
Watkin's ' Q (A) (Warkins) 1989). The difference between the two estimator is that Watkin's Q (A) terminates the calculation of A-return whenever an exploratory action is taken. In our experiments,
we adopt the configuration that uses Peng's Q (A), since it has been demonstrated in (Daley & Amato 2019) that Peng's 's Q (A) is superior Watkin's 's Q (A).
A1.2 SALIENCY MAP GENERATION METHODOLOGY OF THE ATTENTION MAPS FOR MB-DQN
In order to perform the qualitative analysis for comparing MB-DON with the bootstrapped DQN in Seciton 4.1, utilize the methodology proposed in (Greydanus et al., 2018) to construct perturbation- saliency maps to highlight what an agent actually perceives and focuses on from its observation. This information offers way to understand the learning procedure of the agent,
10

---

Under review as a conference paper at ICLR 2021
and enables to validate that bootstrapped heads with different backup lengths may concentrate on different subjects in an agent's 's observation. Given an image I, the method first generates a the perturbed image I' defined as:
(i, =1 M(i, 1)) + A(I, an) * (i, j),
(A2)
where M is the mask centered at the coordinate (i, j) of I, and A is the Gaussian blur operator with a standard deviation σд. The aim of the perturbation process is to add uncertainty, in order to cause the agent become uncertain about the area around (i. j). The salieney map S is then defined as the L2-norm difference between the estimated values of / before and after each perturbation process:
S(i, j) (IV (i, j))1?
(A3)
The L2-norm difference serves as measure to reflect the extent of attention of the agent around region (i, j). The saliency map can be added to one of the three color channels of the original image 7 to visualize the attention map of the agent. In order to construct saliency maps for MB-DQN, the methodology discussed above extended to bootstrapped version, in which all the bootstrapped heads that participate in the final decision of taken action (denoted as Quoting) are taken into consideration (i.e., the bootstrapped heads contributing to the highest votes in the majority voting procedure). The saliency measure of each bootstrapped head k E K (where K' is the total number of heads) is then defined as Sy, and the total saliency map Spootstrayped for MB-DQN is thus defined as:
K
1,
if az = Geoting 0, otherwise
Shootstraapped
SkIkk where Tk =
(A4)
A2 ADDITIONAL DETAILS OF THE EXPERIMENTAL SETUP
In this section, we provide additional training details of our experiments. The agents are evaluated based the average scores of ten test episodes every 250k timesteps. During the evaluation phase, both the proposed MB-DQN and bootstrapped DQN use a majority vote policy to decide the action to be taken. In other words, every bootstrapped head predicts its own action for each input state, while the action taken by the agent is determined by the highest vote from all of the bootstrapped heads. The experimental results presented in this paper are generated based on three different random seeds, and the evaluation curves are drawn with 68% confidence interval (i.e., one standard deviation) as the shaded areas. The detailed settings of the arpeerparameters our experiments are listed in Table Al
A2.1 THE HYPERPARAMETERS FOR TRAINING MB-DQN
Table AT summarizes the hyper- of MB-DQN, Bootstrapped DQN (Osband et al. 2016). and DQN(A) (Daley & Amato 2019), including the training parameters and their configurations, followed by the imput sizes for the agents.
A2.2 NETWORK STRUCTURE
In this section, we explain the network structure used in experiments. The shared convolutional neural network depicted in Fig. 2 of the main manuscript consists of three convolutional layers with 32, 64, and 64 filters, which is the same the configurations used in DQN (Mnih et al. 2015).. Bootstrapped DQN (Osband et al. 2016), and DQN (A) (Daley & Amato 2019). The output of the last convolutional layer then fed into K distinet heads, where each head implemented culnecco (FC) layer with 512 filters, followed by another FC layer to predict Q-value for each to ReLU.
action. The default activation function
A3 ADDITIONAL EXPERIMENTAL RESULTS
In this section, we provide and discuss additional experimental results evaluated on Atari 2600 games in Section A3.1 well as additional sets of ablation analyses of the backup lengths in Section A3.3
11

---

Under review as a conference paper at ICLR 2021
Table AI: The detailed settings of the pyyer--prameee using in our experiments.
Hyperparameter
Value
Mixture of Step Returns Bootstrapped DQN (MB-DQN)
Learning rate of the agent
2.5e-4
Discount factor (r)
0.99
Optimization for RL agent
RMSProp
Minihatch size
32
Target update period
update per 10000 timesteps
Training timesteps
10M
Replay buffer size
IM
Number of the bootstrapped heads Head return ny (Algorithm 1)
10 step heads,
3 steps 5 hcads
Bootstrapped DQN (Osband et al. 2016)
Learning rate of the agent Discount factor (r)
2.5e- 44
0.99
Optimization for RL agent
RMSProp 32
Minibatch size
Target update period
update per 10000 timesteps
Training timesteps
10M
Replay buffer size
IM
Number of the bootstrapped heads
10
Head return ni
1 step 10 heads (default),
varies for different experiments
DQN(A) (Daley Amato 2019)
Learning rate of the agent Discount (r)
le-4
0.99
Optimization agent
Adam
Minihatch size
32
Replay buffer size
1M
Cache size
80000
Block size
100
Return estimator
Peng's ' Q()) Peng Williams 1994
0.75
Input Size for the RL agents
Input size in Dense Maze
current position (x.y), where 0 S x. y<40
Input size in Atari
84484*4
A3.1 ADDITIONAL EVALUATION RESULTS ON ATARI 2600 GAMES
Following the evaluation results presented Section 4.1 of the main manuscript, in this section, we provide the the evaluation results of the Bootstrapped DQN baselines and MB-DQN 33 Atari games in Table A3 where these methods are similarly denoted as All-I-Step (Baseline), All-3- Step (Baseline), and Mixed-I-3-Step (MB-DQN), respectively. The settings of the Bootstrapped DQN baselines and MB-DQN are the same as those in Section 4.1 of the main manuscript. The scores highlighted in bold represent the best performances among these three methods. It can be observed that MB- DQQ achieves the best score in 19 out of the 33 games, while All-3-Step (Baseline) outperforms the other two 11 out the 33 games. contrast, All- Altep-Step (Baseline) only wins in the remaining three games.
A3.2 ADDITIONAL. EXAMPLES OF THE ATTENTION MAPS FROM THE MB-DQN AGENTS
Following the results presented in Section 4.1 of the main manuscript, further visualize an additional set attention maps generated by MB-DQN six Atari games, including Frostbite, Alien, BeamRider, Enduro, Riverraid, and Amidar, and present their results in Fig. (a)-(f,, respectively.
12

---

Under review as a conference paper at ICLR 2021
1-Step
3-Step
Majority
1-Step
3-Step
Majority
(a) Frosibite
(b) Alien
2012
BEST 01
(c) BeamRider
(d) Enduro
(c) Riverraid
(1) Amidar
Figure Al: Visualization of the agents" attention areas (rendered in red) for six Atari games.
From Fig. Al it is observed that in three out of the six games (i.c., Frostbite, Alien, and Amidar), the attentions of 1-Step Heady and 3-Step Heads focus different regions. On the other hand, in the remaining three games (i.e., BeamRider, Enduro, and Riverraid), the attention areas of I-Step Heads and 3-Step Heads are quite similar. Please note that even though the attention areas of them are similar in some games, the agents might still exhibit different behaviors that result in different evaluation scores, shown Table. A3 This is due the fact that the visualization approach proposed in (Greydanus et al. (018)) is only way to interpret the behaviors of the agents, and are thus unable reflect the full behaviors of them. In the following paragraphs, we provide further discussions of the three games in which the attention regions of the 1-Step Heads and the 3-Step Heads are different in MB-DQN.
Frosthite. The 1-Step Heads maintain focusing on the scoreboard, which might be a sign of overfitting. This might be the reason that causes the poor performance of 1-Step Heads in Table. A3
Alien. In order to achieve a high score in Alien, the agent has to learn to dodge the attacks from aliens, survive, and then destroy the alien eggs laid concentrate both the eggs and the monster with a similar extent of attention (i.e., the red colors of the attention regions are highlighted with similar magnitudes), which might cause the agent to be overly greedy in destroying the eggs, leading to its death and undesirable performance in Table. A3
hallways. seems that 1-Step Heads
Amidar. From Fig. AI
(f), it is observed that the 3-Step Heads seem to pay more attention on the monsters than the 1-Step Head. 3-Step Head can easily walk around the grid to get higher rewards without attacking by monsters. On the contrary, the 1-Step Heads merely concentrate
the character.
For these three games, the attention areas of the Majority Heads cover the areas from both the 1-Step Heads and the 3-Step Heads, allowing MB-DQN to outperform the two baselines All-I-Step (Baseline) and All-3-Step (Baseline) Table, A3 These examples again validate that MB-DQN can leverage the benefits from different backup lengths discussed in Section 4.1 of the main manuscript.
13

---

Under review as a conference paper at ICLR 2021
Mosed-1-----iipp
Mised-1-3-9-ep
K-2
K-4
1-10 DQN)
Mixed Stop
Ni-1 Step (Baseline)
Frosdd to
Hare
Frositele
4000
20k
28K
3000
1000
10k
2000
10K
Average score
1000
Irduro
Cran/Gimber
150K
CracyClimber
1300
1500
1000
1000
100k
500
30k
2M
4M
614
BM
10M
2M
4M
8M
10M
Timesteps
(a)
Figure A2: Curves of four more Atari games for (a) different configurations of step returns for the bootstrapped heads, and (b) different numbers of the bootstrapped heads on the proposed MB-DQN.
1-Step Mixed-113-Stees (MB-0QMF (MB-DQ))
Siived-1-3-5-Seee (MB-CQN)
Breakout
Obert
Seaquest
Freewwy
400
15k
104
30
300
25
250
200
10k
64
20
150
4k
10
2M
4M
6M
SM
10M
2M
4M
5M
BM
10M
2M
4M
6M
8M
10M
2M
4M
6M
8M
10M
Figure A3: Experimental results of different configurations of step returns in four other Atari games.
A3.3 ADDITIONAL RESULTS FOR ABLATION ANALYSES
results for Section 4.4 of the main manuscript, and consider different upper bounds of step returns for the bootstrapped heads in MB-DQN. In Fig. A2 we depict the learning curves of four more Atari games, including Frostbite, Enduro, Hero, and CrazyClimber. Fig. A2 (a) shows that the agents trained with different mixtures of step returns perform better than the All --Sep baseline. Fig. (b) illustrates the advantage of the mixture usage of multi-step returns in bootstrapped heads. These additional results lead to similar insights, as discussed Section 4.4.
In this section, present
We further inspect in detail three different configurations backup lengths for the bootstrapped heads in MB-DQN, including A-Sep- (Baseline). Mixed- frixed-/-3.. -3-SStep, and Mixed-I-3-5-Sy The learning curves of these three configurations are presented Fig. A3 can observed that the learn faster in
agents trained with a larger upper bound of backup lengths (i.e., Mixed-1-3-5-SAe three out of the four games, including Qbert, Seaquest, and Freeway. An observation from results is that the agents suffer from performance drops in Seuquest and Breakout for the Mixed-1-33 --3----- setting. This caused by the implication revealed in Fig. 3 and Section 4.1 of the main manuscript that longer backup lengths might not necessarily bring beneficial impact the learning process of the value function. The observations suggest that the optimal configuration of the bootstrapped heads and the upper bound of the backup length are still challenging issue to be investigated in the future.
A4 COMPUTING INFRASTRUCTURE
In this section, provide the configuration of our computing infrastructure in Table. A2 for reference.
14

---

Under review as a conference paper at ICLR 2021
Table A2: Specification of our computing infrastructure.
Component
Customized Machine
Processor
32 cores 64 threads (3.0GHz, up 4.2GHz)
Hard Disk Drive
6TB SATA3 7200rpm
Solid-State Disk
ITB PCIe Gen 3 NVMe
Graphics Card
NVIDIA GeForce RTX 2080Ti (two cards per instance)
Memory
16GB DDR4 2400MHz (1 (128GB in total)
A5 REPRODUCIBILITY
We implemented the proposed MB-DQN based on the RLTF framework Nikolov 2018), which is research framework that provides high-quality implementations of common RL algorithms based on the TensorFlow deveplopment platform. We modified the source codes of RLTF and added an additional option MB-DQN into its DQN family. All the conducted experiments presented in our paper re-producible with easy-following instructions. For more details about our source codes, please refer to the anonymous github repository at the following link: https//github.oom/Aooonnn
Table A3: Comparison of the evaluation results of MB-DQN and the baselines in 33 Atari games.
All-1 All-I-Step (Baseline)
All-3-Step (Baseline)
Mixed 1-3 Step (MB-DQP
Alien
1411.7
2633.7
3486.7
Amidar
344.6
544.1
639.1
Asterix
6190
6431.7
7200.0
BankHeist
812.7
977.3
1215.7
BeamRider
9832.3
13576.5
13440.6
Bowling
47.2
30.8
Boxing
81.8
90.8
91.1
Breakout
315.4
87.5
368.6
CrazyClimber
121587
49313.3
133446.7
DemonAttack
14214.8
9532
14292.0
Enduro
1077
$26.7
1365.1
Freeway
32.2
32.8
32,9
Frostbite
300
2765.7
3417.0
Gopher
8664.7
3640
4376.7
Gravitar
200.0
58.3
Hero
10039,2
13033.2
18318.0
Kangaroo
2646.7
14993.3
12520
Krull
6874.6
7861.6
9261.4
KungFuMaster
15026.7
10583,3
27930.0
MontezumaaRevenge
3.3
O
MsPacman
2264
2508.0
2469
Pong
20.7
20.9
20.9
PrivateEye
27.9
140.0
-50.8
Qbert
11065
13165.8
1 15083.8
Riverraid
11651
13102.3
14154.7
RoadRunner
49053.3
46740
38740
Scaquest
2584
4407.3
8842.0
Skiing
-3776388
19122,99
-23199,2
Solaris
807.0
327.3
-50.8
Spacelnvaders
1505.8
1279
1615.0
Venture
266.7
66.7
WizardOfWor
983.3
4600.0
2010
Zaxxon
106.7
6826.7
2963.3
15


Reviews:
[{"review_id": "vKRUVSKDbt", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes Mixture Bootstrapped DQN (MB-DQN). The new algorithm modifies bootstrapped DQN by giving different backup lengths to each head. It shows better performance in several Atari environments, compared to bootstrapped DQN. This work also attempts to analyze the source of empirical benefits in terms of attention areas of the agents, the quality of data sampling, and the way of utilizing different backup lengths. There is also an ablation analysis showing that the MB-DQN is not limited to a single configuration.\n\nReasons for score: \n\n(+): The proposed method is tested considering several different aspects, including the agent’s attention area, data quality, and the sensitivity of parameters. These experiments provide a deeper view of the MB-DQN and try to explain why this new method helps with learning. \n\n(+): The paper is well organized and easy to read. The appendix provides enough details to reproduce the main result.\n\n(-): This paper claims that while longer back-ups expedite learning, they do so at the expense of exploration: longer back-ups help in efficient assimilation of the reward information that the agent begins to exploit, as opposed to shorter TD(0)-like backups that propagate reward information relatively slowly, leading to seemingly exploratory behavior (reward information has not propagated everywhere so exploitation essentially amounts picking random actions). I find this assertion rather flawed as it suggests that inefficient learning is an avenue for better exploration. An agent tends to explore when it chooses a seemingly sub-optimal course of action to improve its knowledge, and it tends to exploit its current knowledge when it chooses the greedy action. Deliberately slowing the learning process such that even exploitation appears exploratory is a defeatist approach towards the exploration problem.\n\n(-): While there is some empirical comparison with eligibility traces in section 4.3, the fundamental advantages of using multiple heads over TD-lambda remains unclear to me. Can we see the benefits clearly in the tabular/linear function approximation setting, or make a theoretical statement about the benefits? Or is this approach only useful in the Deep-RL setting where it helps with how neural networks interact with TD? Section 4.2 suggests that MB-DQN helps by changing the data distribution in the replay buffer, can we see the same effect in the tabular/linear function approximation setting, perhaps in the domain used in Figure 1? Studying these questions empirically in simpler settings can help untangle the interaction of NN-based non-linear function approximation and the general temporal credit assignment problem that traces are designed to solve. \n\n(-): The experimental results are averaged over only 3 different random seeds. It remains unclear how these seeds were chosen. More importantly, 3 runs are not sufficient to establish the statistical significance of the results. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "si9-xMcrD5", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary of Contributions\n\nThe paper proposes the Mixture Bootstrapped DQN (MB-DQN) algorithm, an extension of bootstrapped DQN where each outputted value estimate uses a different multi-step TD target. They provide a motivating example suggesting that with shorter backups, the slower convergence results in greater exploration. They empirically show that in a variety of cases, simultaneously learning action value estimates with varying multi-step TD targets can lead to improvements over existing methods.\n\n### Review\n\nThe proposed algorithm appears novel, and the results are interesting. However, I have the following concerns:\n\n1) A high level description was provided on how actions were selected during evaluation, but none was provided as to how they were selected during training (i.e., the behavior policy). This information is important given the use of Peng's Q(λ) targets (*uncorrected* returns), as the update targets are now a mixture of on-policy sampled rewards, and off-policy bootstrapped values. Could the authors elaborate on the behavior policy used while training, and comment on its compatibility with the use of uncorrected multi-step returns? \n\n2) The motivating example compares learning with a 1-step TD target with that of a 5-step TD target. The paper suggests that due to the larger bias in a 1-step TD target (and consequently, slower convergence), the 1-step learner ends up exploring more. Especially in the 1-step case (where Peng's Q(λ) does not need corrections), the algorithm learns off-policy, making it seem like whether or not it explores more an artifact of a design choice in the behavior policy, and not something inherent about 1-step TD targets. Also of note, when looking at the heatmaps after 100,000 time steps, the 1-step learner has a very salient line taking a suboptimal path of going straight up for a bit, and then heading in a straight line toward the goal. Such a high frequency of this suboptimal path seems suggestive of the method actually *not* exploring enough. As such, I'm not sure the conclusions drawn from the example are convincing, and would appreciate if the authors could comment on the above or clarify any misunderstanding.\n\n3) In addition to the motivating maze example, the paper repeatedly emphasizes that MB-DQN provides heterogeneity in the target values. Can the authors clarify what this precisely means, and elaborate on why this is a desirable property?\n\n4) It appears a fixed learning rate was used for each algorithm. Due to the bias-variance tradeoff of multi-step TD methods, as well as the varying numbers of heads in the ablation studies, it's not clear whether a fair comparison was made between each algorithm instance. Could the authors comment on how hyper-parameters were chosen in the empirical evaluation?\n\n5) Only 3 random seeds were used in their empirical evaluation, and the paper presents one standard deviation as a 68% confidence interval. The use of 3 seems insufficient for central limit theorem arguments, but the mention of 68% suggests an assumption that the results are normally distributed. Can the authors comment on the statistical significance of their results, and whether the number of runs are sufficient for the claims being made?\n\nBased on the above, I'm recommending rejection at this time. I'm willing to raise my score should my concerns be addressed.\n\n----- Post Discussion -----\n\nI appreciate the clarifications made in the discussion regarding additional experimental details and whether the methods were fairly compared. However, given that much of the claims rely heavily on the empirical evaluation, I think further experiments with more rigorous statistical analysis is necessary. Even with the correctly plotted standard errors, the results still largely do not appear significant, suggesting that 5 seeds is just not enough. There are good recommendations by Henderson et al. (2017) and Colas et al. (2018) for the empirical evaluation, and I think it would additionally strengthen the paper to formalize the notion of heterogeneity (e.g., be able to approximately measure it, and convincingly argue that this is what's underlying any differences in performance). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "h_Qxsw8SRy-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nAs the title suggests, the paper proposes using a mixture of multi-steps in estimating the action-space value function in DRL. Multi-step RL has been around for a while now, and this work attempts to extend it further to a mixture setting by exhibiting a performance boost when the proposed technique is used with Bootstrapped DQN.\nWhy multi-steps?\nMulti-step return estimations constitute a high-variance low-bias method. Because of the “intuition” that different multi-steps would incorporate different knowledge, and the step parameter might be dependent on the environment dynamics, it would make sense to have several of them.\nWhy Bootstrapped DQN:\nProvides easy incorporation of the multi-steps since it has multiple Q heads, and the authors could assign different multi-steps to them.\n\nThe paper is easy to read and follow. The different sections have a “natural” flow to them and the reasoning is clear.\nTo prove the advantage of using the algorithm, it has been tested on 8 of the Atari games and it exhibited better performance in several of them. A qualitative comparison was also performed based on the attention map visualization for 2 Atari games and it showed that MB-DQN infers more relevant sate-space regions.\n\n“However” points:\nThe critical point is that the performance of the baseline Bootstrapped DQN is different from the one reported in the original paper. We would assume there is still some hyperparameter tuning missing for B-DQN. Yet, this does not disapprove of the power of the suggested MB-DQN since the same hyperparameters were used for both methods.\nSince MB-DQN is expected to have a higher variance, it would be interesting to test in a noisy environment (non-deterministic action-reward?).\n(Slight indentation problem in the first hyperparameters table that pushed the head return value to the first row)\n\nVerdict: \nThis is an interesting and powerful method. Well written paper. More extensive experiments would have made the proposed work more convincing. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "cEA6ofUGaMX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "###################################\n\nSummary: \n\nThis paper combines the idea of multi-step returns for value-based reinforcement learning with Bootstrapped DQN. Updating value functions with different step returns has potential benefits, and was elegantly integrated with the Bootstrapped DQN structure, where different heads have different backup lengths. This work provides empirical results on Atari game domains, and further provides ablation analysis. \n\n\n\n###################################\n\nPros: \n\n1. This paper presents a simple, but meaningful approach to combine multi-step returns in value-function based RL and Bootstrapped DQN. The strength of having different backup length in value-based RL is that multi-step returns have lower bias (despite the high variance) and sensitivity to future rewards. The power of Bootstrapped DQN comes from its exploration capabilities. Bootstrapped DQN’s multiple heads are a natural way of integrating different lengths of returns. I like the originality of this idea presented by this paper. \n\n2. This paper provides good empirical results in Atari games, showing that mixed 1-3 step MB-DQN outperforms fixed-step baselines. \n\n3. This paper also provides ablation studies, adding more comprehensive analysis of this algorithm. Separating data generation agent and learning-only agent is valid; MB-DQN is compared with DQN-lambda and DQN-ensemble and shows better performance; and more experimental results with different numbers of heads and different configurations of return lengths are compared. \n\n\n###################################\n\nCons / Questions \n\n1. The choice of (step length) n_k is limited: this paper presented main empirical results using five heads of 1-step and five heads of 3-step, and also compared with mixed 1-2-3, 1-2, 1-3, 2-3 steps. In the supplementary materials, there is a result on 1-3-5 step configurations. What about results on larger n_k steps? Could you add some experiments on 10 or 20 steps or at least add insights on how it would perform? My guess is that including very large n_k to the mixture would lead to high variances and possibly degrade the performance. \n\n2. The original strength of Bootstrapped-DQN comes from the fact that it is better for exploration. (Multiple heads lead to explorations.) However, I don’t see comprehensive analysis in the perspective of explorations. To be specific, as authors mentioned in section 3.1., shorter-step return is better at exploring wider areas in the state spaces than longer-step returns, although longer-step returns might be faster at convergence. In terms of exploration perspective, is there an evidence that mixture of shorter & longer n_k’s is better than single fixed 1-step returns? \n\n###################################\n\nReasons for Score: \n\nI gave the score of 5 (marginally below the threshold). But if the concerns that were raised above are well addressed, I am happy to change my score to a higher score after the rebuttal period. Overall, I appreciate the novelty of this paper, and I think the idea of combining two powerful methods in value-based RL: multi-step returns and bootstrapped DQN is meaningful. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "DkPgsit_NKM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper utilizes different step return targets for different heads in bootstrapped DQN, such that a more heterogeneous posterior estimation of policy value may be obtained. However, my main concern is the novelty. The step size can be viewed as a tunable hyperparameter, and the posterior computation is mainly credited to the usage of different randomized DQNs. Similarly, other tunable hyperparameters may also be diversified to introduce more heterogeneity such as learning rates, etc. \n\nRe- simulations, I appreciate the authors' efforts in conducting different experiments to understand their method, but I do have a few comments/thoughts as below:\n- what is the performance of all-2-step bootstrapped DQN? It seems more natural to me to include the comparison with this baseline, since the performance of mixed-1-3 may be more close to all-2.\n- I'm not sure if Figure 4 does do you a favor, since again we can always tune the hyperparameter of step size, and it does not need to be the same for different environments. This paper's method seems to not peak either of them.\n- the reason behind the good performance of MB-DQN explained in section 4.2 is not obvious to me. I'm not sure about the point of comparing an agent trained with its own data versus one trained with other data, since we are just learning the policy value but not the policy itself, and there is no issue like off-policy correction, etc. Actually such techniques of data-sharing have been used a lot if we have multiple agents to collect data.\n- in section 4.4, when comparing different setups of MB-DQN, it would be fairer to include more baselines used in part of the MB-DQN such as all-2, all-3.\n ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends Bootstrap DQN with multi-step TD target. The initial submission had missing details, communication problems, and results lacking rigor. The authors made a clear effort to address the reviewers concerns.

This paper's contribution is supported primarily by the empirical results which need major work. The lack of statistical significance in the key results is a major problem. The new 5 run results (originally only 3 runs) shows no clear evidence of improving over the baseline. Additionally one must either justify the use of such few runs by investigating the distributions and using the proper statistical tools (Colas et al [2]) or simply do more runs. Regardless statistical significance in the precise sense is a requirement.

In addition other adjustments to the paper would strengthen it significantly: (1) The qualitative results like state visitations can be interpreted either in favour of the method or not, this could be improved with discussion or omitted---see [1]; (2) the discussion of heterogeneity was informal; (3) discussion of the impact and sensitivity of hyper-parameters should be included---this includes addressing the concern that the performance of the baseline was as strong as it could be; (4) the current results do clearly separate if the improvement in performance (if it can be shown to be significant) is due to improvements in the rep via auxiliary task effect or the multi-step return---the reviewer has made a nice suggestion for an experiment here.

In summary, the reviewers did not find the text and examples in the paper convincing as to why the proposed method should be better than bootstrap q, and the results are not significant and need more work. 

references that may be helpful:
[1] https://openreview.net/forum?id=rkl3m1BFDB&utm_campaign=RL%20Weekly&utm_medium=email&utm_source=Revue%20newsletter
[2] https://arxiv.org/abs/1806.08295
Decision: Reject