Maxmin Q-learning: Controlling the Estimation Bias of Q-learning
Authors: Qingfeng Lan
Yangchen Pan
Alona Fyshe
Martha White
Venue:  (2020)
Keywords: reinforcement learning
bias and variance reduction

Abstract: Q-learning suffers from overestimation bias, because it approximates the maximum action value using the maximum estimated action value. Algorithms have been proposed to reduce overestimation bias, but we lack an understanding of how bias interacts with performance, and the extent to which existing algorithms mitigate bias. In this paper, we 1) highlight that the effect of overestimation bias on learning efficiency is environment-dependent; 2) propose a generalization of Q-learning, called \emph{Maxmin Q-learning}, which provides a parameter to flexibly control bias; 3) show theoretically that there exists a parameter choice for Maxmin Q-learning that leads to unbiased estimation with a lower approximation variance than Q-learning; and 4) prove the convergence of our algorithm in the tabular case, as well as convergence of several previous Q-learning variants, using a novel Generalized Q-learning framework. We empirically verify that our algorithm better controls estimation bias in toy environments, and that it achieves superior performance on several benchmark problems. 

Published as a conference paper at ICLR 2020
MAXMIN Q-LEARNING: CONTROLLING ESTIMATION BIAS OF --LEARNING
THE
Qingfeng Lan, Yangchen Pan, Alona Fyshe, Martha White Department of Computing Science University of Alberta
Edmonton, Alberta, Canada (qlan3, pan6, alona, whi whitem) @ua berta.ca
ABSTRACT
Q-learning suffers from overestimation bias, because it approximates the maximum action value using the maximum estimated action value. Algorithms have been proposed to reduce overestimation bias, but we lack an understanding of how bias interacts with performance, and the extent to which existing algorithms mitigate bias. In this paper, 1) highlight that the effect of overestimation bias on learning efficiency Q-learning, called Maxmin Q-learning, which provides parameter flexibly control bias; 3) show theoretically that there exists parameter choice for Maxmin Q-learning that leads to unbiased estimation with lower approximation variance than Q-learning; and 4) prove the convergence of our algorithm in the tabular case, well as convergence of several previous Q-learning variants, using novel Generalized Q-learning framework. We empirically verify that our algorithm better controls estimation bias toy environments, and that achieves superior performance on several benchmark problems.
2) propose a generalization
INTRODUCTION
Q-learning (Watkins 1989 is one of the most popular reinforcement learning algorithms. One of the reasons for this widespread adoption is the simplicity of the update. On each step, the agent updates its action value estimates towards the observed reward and the estimated value of the maximal action in the next state. This target represents the highest value the agent thinks it could obtain from the current state and action, given the observed reward.
Unfortunately, this simple update rule has been shown to suffer from overestimation bias (Thrun & Schwartz 1993 yan Hasselt, 2010). The agent updates with the maximum over action values might be large because action's value actually is high, it can be misleadingly high simply because of the stochasticity or errors in the estimator. With many actions, there is a higher probability that one of the estimates is large simply due stochasticity and the agent will overestimate the value. This issue is particularly problematic under function approximation, and can significant impede the quality of the learned policy (Thrun & Schwartz) 1993, Szita & Lörinez 2008 Strehl et al.) 2009) or even lead to failures of Q-learning (Thrun & Schwartz 1993). More recently, experiments across several domains suggest that this overestimation problem common (Hado van Hasselt al. 2016).
Double Q-learning (van Hasselt, 2010 is introduced to instead ensure underestimation bias. The idea is to maintain two unbiased independent estimators of the action values. The expected action value of estimator one is selected for the maximal action from estimator two, which is guaranteed not to overestimate the true maximum action value. Double DQN (Hado van Hasselt et al. 2016), the extension of this idea to Q-learning with neural networks, has been shown to significantly improve performance over Q-learning. However, this is not a complete answer to this problem, because trading overestimation bias for underestimation bias is not always desirable, as show in our experiments.
Cooee available at otu.bbeiiitttpesesst/mooo//////p

---

Published as a conference paper at ICLR 2020
Several other methods have been introduced to reduce overestimation bias, without fully moving towards underestimation. Weighted Double Q-learning (Zhang et al., 2017) uses a weighted combination of the Double Q-learning estimate, which likely has underestimation bias, and the Q-learning estimate, which likely has overestimation bias. Bias-corrected Q-Learning (Lee et al. 2013) reduces the overestimation bias through bias correction term. Ensemble Q-learning and Averaged Q-learning (Anschel et al., (017) take averages of multiple action values, to both reduce the overestimation bias and the estimation variance. However, with finite number of action- value functions, the average operation in these two algorithms will never completely remove the overestimation bias, as the average of several overestimation biases is always positive. Further, these strategies do not guide how strongly we should correct for overestimation bias, nor how to determine- control-the level bias.
The overestimation bias also appears in the actor-critic setting (Fujimoto et al. 2018 Haarnoja al. 2018). For example, Fujimoto et al. (2018) propose the Twin Delayed Deep Deterministic policy gradient algorithm (TD3) which reduces the overestimation bias by taking the minimum value between two critics. However, they do not provide a rigorous theoretical analysis for the effect of applying the minimum operator. There is also theoretical guide for choosing the number of estimators such that the overestimation bias can be reduced to O.
In this paper, we study the effects of overestimation and underestimation bias learning performance, and use them to motivate a generalization of Q-learning called Maxmin Q-learning. Maxmin Q-learning directly mitigates the overestimation bias by using minimization over multiple action-value estimates. Moreover, it is able to control the estimation bias varying from positive to negative which helps improve learning efficiency as we will show in next sections. We prove that, theoretically, with an appropriate number of action-value estimators, we are able to acquire an unbiased estimator with lower approximation variance than Q-learning. We empirically verify our claims on several benchmarks. We study the convergence properties of our algorithm within a novel Generalized Q-learning framework, which suitable for studying several of the recently proposed Q-learning variants. We also combine deep neural networks with Maxmin Q-learning (Maxmin DQN) and demonstrate its effectiveness in several benchmark domains.
PROBLEM SETTING
We formalize the problem as Markov Decision Process (MDP), (S,A,,, where S is the state space, A the action space, P : A -+ [0, 1] the transition probabilities, r Axxx5 TR is the reward mapping, and 7 E [0, 1] is the discount factor. At each time step t, the agent observes a state S, E S and takes an action A₁ A and then transitions to a new state S S according to the transition probabilities P and receives scalar reward Re+1 r(S,, At, St+1) E R. The goal of the agent is to find a policy x : S x A [0, 1] that maximizes the expected return starting from some initial state.
Q-learning is an off-policy algorithm which attempts to learn the state-action values Q S - for the optimal policy. It tries solve for
Q* a) = Ret1 max (S St 5 = A, s, = d'EAA
The optimal policy is to act greedily with respect to these action values: from each s select from arg max (8, a). The update rule for an approximation Q for a sampled transition 8t, Ge, Tet St41 is:
Q(sr, a.) + Q( a.) + a(Y? Qss, a:)) for Y r2+1 + max Q(5(41,a)) (I) d'EA
where a is the step-size. The transition can be generated off-policy, from any behaviour that sufficiently covers the state space. This algorithm is known to converge in the tabular setting (Tsitsiklis 1994), with some limited results for the function approximation setting (Melo) & Ribeiro 2007).
3 UNDERSTANDING WHEN OVERESTIMATION BIAS HELPS AND HURTS
In this section, we briefly discuss the estimation bias issue, and empirically show that both overestimation and underestimation bias may improve learning performance, depending the
2

---

Published as a conference paper at ICLR 2020
environment. This motivates our Maxmin Q-learning algorithm described in the next section, which allows us to flexibly control the estimation bias and reduce the estimation variance.
The overestimation bias occurs since the target ma Q(s++1, d') is used in the Q-learning update. Because Q is an approximation, it is probable that the approximation is higher than the true value for one or more of the actions. The maximum over these estimators, then, is likely to be skewed towards an overestimate. For example, even unbiased estimates Q a') for all a', will vary due stochasticity. Q(54+1, 1, a') = Q* ($1+1, a') + Ca', and for some actions, ear will be positive. As result, E E| Q (8 a')] 2 maxa'ed (++(1++1:: a')] = maxa EAA Q* ("
This overestimation bias, however, may always be detrimental. And, further, in some cases, erring towards an underestimation bias can be harmful. Overestimation bias can help encourage exploration for overestimated actions, whereas underestimation bias might discourage exploration. In particular, we expect more overestimation bias in highly stochastic areas of the world; if those highly stochastic areas correspond to high-valus value regions, then encouraging exploration there might be beneficial. An underestimation bias might actually prevent agent from learning that region is high-value. Alternatively, if highly stochastic areas also have low values, overestimation bias might cause an agent to over-explore a low-value region.
We show this effect in the simple MDP, shown in Figure [ The MDP for state A has only two actions: Left and Right. It has deterministic neutral reward for both the Left action and the Right action. The Left action transitions to state В where there are eight actions transitions to terminate state with highly stochastic reward. The mean of this stochastic reward is μ.. By selecting l > O, the stochastic region becomes high-value, and we expect overestimation bias to help and underestimation bias to hurt. By selecting μ O, the stochastic region becomes low-value, and we expect overestimation bias to hurt and underestimation bias to help.
r~ + 1.1
0 Right
B
A
Left
Figure I: A simple episodic MDP, adapted from Figure 6.5 in Sutton & Barto 2018) which used to highlight the difference between Double Q-learning and Q-learning. This MDP has two non- terminal states and B. Every episode starts from A which has two actions: Left and Right. The Right action transitions to terminal state with reward O. The Left action transitions to state B with reward 0. From state B, there are actions that all transition to terminal state with reward + &, where & is drawn from a uniform distribution 1). When μ > O, the optimal action in state A Left; when μ < 0, is Right.
We test Q-learning, Double Q-learning and our new algorithm Maxmin Q-learning in this environment. Maxmin Q-Jearning (described fully in the next section) uses estimates of the action values in the targets. For N = 1, it corresponds to Q-learning; otherwise, it progresses from overestimation bias N towards underestimation bias with increasing N. In the experiment, we used discount factor 7 = 1; a replay buffer with size 100; an c-greedy behaviour with = 0.1; tabular values- initialized with Gaussian distribution (0, 0.01); and a step-size of 0.01 for all algorithms.
The results Figure our hypotheses for when overestimation and underestimation bias help suboptimal
and hurt. Double Q-learning underestimates too much for +1, and converges policy. Q-lcarning learns the optimal policy the fastest, though for all values of N = 2, 4, 6, 8, Maxmin Q-learnigg does progress towards the optimal policy. All methods get to the optimal policy for μ = -1, but now Double Q-learning reaches the optimal policy the fastest, and followed by Maxmin Q-learning with larger N.
MAXMIN Q-LEARNING
In this section, we develop Maxmin Q-learning, a simple generalization of Q-learning designed to control the estimation bias, as well reduce the estimation variance of action values. The idea is
3

---

Published as a conference paper at ICLR 2020
1.2
0.8
O-leaming
Q-leaming
1.0
Double Quicarnin
Doubic Q-loaming
Maxmin Q-learnin (N=2)
0.6
Maxmin Q-eaarinn (N=2)
Distance training policy to optimal
Maxmin Q-learning (Ne4)
Distance training policy to optimal policy
Maxmin Qllaarning (N=4)
Maxmin Q-eeaning (N-6)
Maxmin Q-eerning (N-6)
Maxmin Q-larning (N-B)
Maxmin Q-eaaniing (N-B)
0.6
poliny
0.4
0.2
0.0
0.0
0
2000
4000
0
2000
4000
Episodes
Episodes
(a) μ +0.1 (overestimation helps)
(b) μ -0.1 (underestimation helps)
Figure 2: Comparison of three algorithms using the simple MDP in Figure I with different values of μ., and thus different expected rewards. For μ = +0.1, shown in (a), the optimal e-greedy policy is to take the Left action with 95% probability. For μ4 -0.1, shown in in (b), the optimal policy is to take the Left action with 5% probability. The reported distance is the absolute difference between the probability of taking the Left action under the learned policy compared to the optimal e-greedy policy, All results were averaged over 5, 000 runs.
to maintain N estimates of the action values, Q', and use the minimum of these estimates in the Q-learning target: max,' (1... .N) (s', For N = 1, the update is simply Q-learning, and so likely has overestimation bias. As N increase, the overestimation decreases; for some N 1, this maxmin estimator switches from overestimate, in expectation, to underestimate. We characterize the relationship between N and the expected estimation bias below in Theorem [ Note that Maxmin Q-learning uses different mechanism reduce overestimation bias than Double Q- learning; Maxmin Q-learning with N = 2 is not Double Q-learning.
The full algorithm is summarized in Algorithm I and is simple modification of Q-learning with experience replay. We use random subsamples of the observed data for each of the N estimators, to make them nearly independent. To do this training online, we keep replay buffer. On each step, random estimator is chosen and updated using a mini-batch from the buffer. Multiple such updates can be performed on each step, just like in experience replay, meaning multiple estimators can be updated per step using different random mini-batches, In our experiments, to better match DQN, we simply do one update per step. Finally, it is also straightforward to incorporate target networks to get Maxmin DQN, by maintaining target network for each estimator.
We now characterize the relation between the number of action-value functions used in Maxmin Qelarnning and the estimation bias of action values. For compactness, we write Qi instead of Q' (8, a). Each Q has random approximation error e'
D'a Qr + E
We assume that et, is uniform random variable T- for some T 0. The uniform random assumption was used by Thrun & Schwartz (1993) to demonstrate bias in Q-learning, and reflects that non-negligible positive and negative ey are possible. Notice that for N estimators with n samples, the r will be proportional to some function of nea/N because the data will be shared amongst the N estimators. For the general theorem, we use generic т, and in the following corollary provide a specific form for T in terms of N and nl.a.
Recall that M is the number of actions applicable at state s'. Define the estimation bias Zur for transition s' to be
ZMN del
(r + max Qmin) (r + max Dwrar)
o²
(max mmin
max Q'aa.)
d'
d'
4

---

Published as a conference paper at ICLR 2020
Algorithm 1: Maxmin Q-learning
step-size a, exploration parameter number of action-value functions N Initialize N action-value functions Initialize empty replay buffer
Input:
......Q) randomly
Observe initial state
while Agent is interacting with the Environment do
Qmin (s. t (I....) (s,, a), Va A
Choose action by e-greedy based on Qmin
Take action observe T,
Store transition (s, a, r; s') in D
Select subset S from {I....,N) N} (e.g., randomly select one to update)
for i E do
Sample random mini-bated of transitions (sD, aD, rD. s'p) from D
Get update target: YMQ <- -D max Qmin (8 a')
Update action-value Q': Q'(sD,aD) t Q' a (yMQ (((spaa))
end
end
where
Qmin def
D = Qsa + min (E......))
min
ie iE......))
We now show how the expected estimation bias M and the variance Qmin are related to the number of action-value functions N in Maxmin Q-learning.
Theorem Under the conditions stated above,
(i) the expected estimation bias is
M(M 1). 1)...1
F[ZMN]] =-r[1- -2
where IMN
(M + N ) - 1 }) -.(1+
E Zun] decreases as increases: (i)
ElZM,N=Il = YT YT ++1 and E -00)
4
Var
(N + 1)2 + 2)
V VarlQ
[ decreases as N increases: V Var[Quin) = for N=1 and V cr[QQuin 0 N - cc.
Theorem T is generalization of the first lemma in Thrun & Schwartz 1993); provide the proof in Appendix A as well as a visualization the expected bias for varying M and N. This theorem shows that the average estimation bias E[ZMN], ]. decreases as N increases. Thus, can control the bias by changing the number of estimators in Maxmin Q-learning. Specifically, the average estimation bias can be reduced from positive negative N increases. Notice that F[ when MN = 7. This suggests that by choosing N such that tMN R 2. we can reduce the bias to near 0.
Furthermore, Var[Qmin] decreases as N increases. This indicates that we can control the estimation variance of target action value through N. We show just this in the following Corollary. The subtlety is that with increasing N, each estimator will receive less data. The fair comparison is to compare the variance of a single estimator that uses all of the data, as compared which shares the samples across N estimators. We show that there is an N such that the variance is lower, which arises largely due to the fact that the variance of each estimator decreases linearly n, but the parameter for each estimator only decreases square root rate in the number of samples.
the maxmin estimator
Corollary Assuming the na samples are evenly allocated amongst the N estimators, then 2 N/nga where o² is the variance of samples for (8, a) and, for Qsa the estimator that uses all
5

---

Published as a conference paper at ICLR 2020
500
1000
Q-learning
Q-leamiin
450
Double Q-learning
Double Q-learring
400
Averaged Q-eearning (N=2)
800
Averaged Q-leamiin (N-2)
Maxmin Q-learning (N-2)
Maxmin Q-leaming (N-2)
350
Steps
Steps 620
300
250
400-
200
150
200
0
10
20
30
40
50
200
400
600
800
1000
Reward variance (o²)
Episodes
(a) Robustness under increasing reward variance
(b) Reward ~ N0),,
Figure 3: Comparison of four algorithms on Mountain Car under different reward variances. The
lines in (a) show the average number of steps taken in the last episode with one standard error. The lines in (b) show the number of steps to reach the goal position during training when the reward
variance o² 10. All results were averaged across 100 runs, with standard errors. Additional experiments with further elevated x² can be found in Appendix C22
Us samples for single estimate,
12
Var Var(Qua mim Quiinn
[ar(Qua).
(N 1)? +
Under this uniform random noise assumption, for N 2 VarlQma) < V Var sQa)-
EXPERIMENTS
In this section, we first investigate robustness to reward variance, in a simple environment (Mountain Car) in which can perform more exhaustive experiments. Then, we investigate performance in seven benchmark environments.
Robustness under increasing reward variance Mountain Car Mountain Car (Sutton & Barto 2018) is classic testbed in Reinforcement Learning, where the agent receives reward of per step with ? = 1, until the car reaches the goal position and the episode ends. In our experiment, modify the rewards to be stochastic with the same mean value: the reward signal is sampled from a Gaussian distribution. ((-1,o0)) on each time step. An agent should learn to reach the goal position in few steps as possible.
The experimental setup as follows. We trained each algorithm with 1, 000 episodes. The number of steps reach the goal position in the last training episode was used as the performance measure. The fewer steps, the better performance. All experimental results were averaged over 100 runs. The key algorithm settings included the function approximator, step-sizes, exploration parameter and replay buffer size. All algorithm used e-greedy with e = 0.1 and buffer size of 100. For each algorithm. the best step-size was chosen from {0.005, 0.01, 0.02, 0.04, 0.08}. separately for each reward setting. Tile-coding was used to approximate the action-value function, where we used tilings with each tile covering 1/8th of the bounded distance in each dimension. For Maxmin Q-learning, we randomly chose one action-value function to update at each step.
As shown in Figure 3 when the reward variance is small, the performance of Q-learning, Double Q- learning, Averaged Q-learning, and Maxmin Q-learning are comparable. However, the variance increases, Q-learning, Double Q-learning. and Averaged Q-learning became much less stable than Maxmin Q-learning In fact, when the variance learning and Averaged Q-learning failed to reach the goal position in 5, 000 steps, and Double Q- learning produced runs > 400 steps, even after many episodes.
very high (o 50, see Appendix C.2 Q-

---

Published as a conference paper at ICLR 2020
Results Benchmark Environments To evaluate Maxmin DQN, choose seven games from Gym (Brockman et al. 2016). PyGame Learning Environment (PLE) (Tasti 2016). and MinAtar (Young & Tian 2019): Lunarlander, Catcher, Pixelcopter, Asterix, Seaquest, Breakout, and Space Invaders. For games in MinAtar (i.e. Asterix, Seaquest, Breakout, and Space Invaders), reused the aaper-parametent and settings of neural networks in (Young & Tian 2019). And the step-size was chosen from [3*t 10-3, 10-300000000 10 100 + 10 For Lunarlander, Catcher, and Pixelcopter, the neural network was multi-layer perceptron with hidden layers fixed [64, 64]. The discount factor was 0.99. The size of the replay buffer was 10, 000. The weights of neural networks were optimized by RMSprop with gradient clip 5. The batch size was 32. The target network was updated every 200 frames. e-greedy was applied as the exploration strategy with decreasing linearly from 1.0 to 0.01 1, 000 steps. After 1, 000 steps, 6 was fixed to 0.01. For Lunarlander, the best step-size was chosen from [3 10-3 10-3,0000000 3 10-1 10.00.1.3 10-1-1011.3
10-3). For
Catcher and Pixelcopter, the best step-size was chosen from [10 3 3,3 10
10 +,3 10 - 1010 91.
For both Maxmin DQN and Averaged DQN, the number of target networks N was chosen from [2,3, 4, 5, 6, 7, 8, 9]. And we randomly chose one action-value function to update at each step. We first trained each algorithm in a game for certain number of steps. After that, each algorithm was tested by running 100 test episodes with c-greedy where e = 0.01. Results were averaged over 20 runs for each algorithm, with learning curves shown for the best hyper-parameter setting (see Appendix C.3 for the parameter sensitivity curves).
We see from Figure that Maxmin DQN performs as well better than other algorithms. In environments where final performance is noticeably better--Pixelopper, Lunarlander and Asterix-the initial learning slower. A possible explanation for this is that the Maxmin agent more extensively explored early on, promoting better final performance. We additionally show on Pixelcopter and Asterix that for smaller N, Maxmin DQN learns faster but reaches suboptimal performance beriavin more like Q-learning and for larger N learns more slowly but reaches better final performance.
CONVERGENCE ANALYSIS OF MAXMIN Q-LEARNING
In this section, we show Maxmin Q-learning is convergent in the tabular setting. We do by providing a more general result for what we call Generalized Q-learning: Q-learning where the bootstrap target uses function G of N action values. The main condition on that it maintains relative maximum values, as stated in Assumption [ We use this more general result to prove Maxmin Q-learning is convergent, and then discuss how provides convergence results for Q- learning, Ensemble Q-learning Averaged Q-learning and Historical Best Q-learning as special cases.
Many variants of Q-learning have been proposed, including Double Q-learning (van Hasselt 2010
Weighted Double Q-learning ŞZhang et al., 2017), Ensemble Q-lcarning (Anschel et al. 2017 Averaged Q-learning (Anschel et al. 2017), and Historical Best Q-learning (Yu et al. (018)) These algorithms differ in their estimate of the one-step bootstrap target. To encompass all variants, the target action-value value of Generalized Q-learning you is defined based action-value estimates from both dimensions:
yQQ =000000000
where L is the current time step and the action-value function QC?(1) is function of Q! K)...., - I)...., Q (1 K),..., Q. (L 1):
Q. K) Q² - K)
(t(-1))
@
Q (t)
QN K)
(1-1)
For simplicity, the vector (Q) is denoted as Q0Q (t), same for Q'( The corresponding update rule is
Quea (t) + Q (t 1) at GQ - Q (t 1))
(4)
For different G functions, Generalized Q-learning reduces to different variants of Q-learning, including Q-learning itself. For example, Generalized Q-learning be reduced to Q-learning
7

---

Published as a conference paper at ICLR 2020
200
Retum
Retum
Roturn
DDN
DQN
DON
DDO%
DDON
DOON
0-
Avaraged DON
Averaged DON
Averaged DON
-10
Maxmin
-20
Meamin DON
Moxein
0.0
IxLO")
Stope 9.10")
Stops (x10f)
(a) Catcher
(b) Lunarlander
(c) Space Invaders
60-
Avaroge
Avcrags
Average
10-
DON
10
Averaged
Averaged
DON
0.0
1.5
2.5
3.0
4.0
55
0.0
0.5
3.0
1/5
2.0
5.5
1.0
2.0
4.
5.0
Staps bco0%)
Steps 6:107)
Steps (x10f)
(d) Breakout
(c) Pixelcopter
(f) Asterix
N
N-dd
15-
30
Ratum
Katum
Retum
20-
DON
DDON
Nod
10
Averaged DON
Masmin DON
N-B
1.5
7.5
2,0
Stose bxio
Steps 0120")
(x10")
(g) Seaquest
(h) Pixelcopter with varying N
(i) Asterix with varying N
Figure& 4: Learning curves on the seven benchmark environments. The depicted return is averaged over the last 100 episodes, and the curves are smoothed using an exponential average, to match previous reported results (Young & Tian 2019). The results were averaged over 20 runs, with the shaded area representing DQN on Pixelcopter and Asterix, with different N, highlighting that larger N seems to result in slower early learning but better final performance in both environments.
standard error. Plots (h) and (i) show the performance of Maxmin
8

---

Published as a conference paper at ICLR 2020
simply by setting K = 1, N with ((Q.) maX Q.a- Double Q-leaming can be specified with = 1, N = 2, and G(Q,, Q2) Q- s.arg max_'eA P'p""
We first introduce Assumption for function G in Generalized Q-learning, and then state the theorem. The proof can be found in Appendix B
Assumption (Conditions on G) Let G RONK R and G(Q) q where Q (Q RaNK, E A and |A| = n. i (1,...,NN.jj {O....,KK K. - and q E R.
(i) If Qai Vi, k. Vj and Va, then q max, QH
(i)) AQ, Q' RANK, G(Q) G(Q") IS max.,i. Qy Q'
We can verify that Assumption | holds for Maxmin Q-learning. Set = and set N to be a positive integer. Let Q, (Q...... ) and define GMQ easy to check that part (i) of Assumption
max,e A min (I....N) Q It satisfied. Part (ii) is also satisfied because
- G(Q') |S| max min Q - max min D IS max Q Q'a -
0,
Assumption (Conditions the siep-sizes) There exists some (deterministic) constant C such that for every (s, a) E S x A,i (I....,NN,, 0 S (t) I 1, and with probability 1,
Σ (1), SC t=0
Σ 1=0
Theorem Assume finite MDP (S, value functions in Generalized Q Q-learning, using the tabular update Equation 3). will converge to the optimal action-value function with probability 1, in either of the following cases: (i) < 1, or (ii) 7 1, Va Q' (t A, 0) 0 where $1 is an absorbing state and all policies are proper.
and that Assumption 1 [and 2onnddhoodd.d Then the action-
As shown above, because the function G for Maxmin Q-learning satisfies Assumption D then by Theorem it converges. Next, we apply Theorem 2 to Q-learning and its variants, proving the convergence of these algorithms in the tabular case. For Q-learning, set K and N 1. Let (Q.) = max.eA aea It is straightforward to check that Assumption I holds for function 6 For Ensemble Q-learning,
-
.......,... )) 1 Σm= Q'.-. Easy to check that Assumption is satisfied. For Averaged Q-learning, the proof is similar to Ensemble Q-learning except that N and K is positive integer. For Historical Best Q-learning, set N = and K to be a positive integer. We assume that all auxiliary action-value functions selected from action-value functions most K updates ago. Define BBQQ be the largest action-value among Q .)... Qua K) for state s. Assumption the convergence is guaranteed.
K 1 and N to be positive integer. Let
m N
satisfied and
CONCLUSION
Overestimation bias is a byproduct of Q-learning, stemming from the selection of maximal value to estimate the expected maximal value. In practice, overestimation bias leads to poor performance in a variety of settings. Though multiple Q-learning variants have been proposed, Maxmin Q- learning is the first solution that allows for a flexible control of bias, allowing for overestimation underestimation determined by the choice of N and the environment. We showed theoretically that we can decrease the estimation bias and the estimation variance by choosing an appropriate number N of action-value functions. We empirically showed that advantages of Maxmin Q-learning, both on toy problems where we investigated the effect of reward noise and several benchmark environments. Finally, we introduced a new Generalized Q-learning framework which we used to prove the convergence of Maxmin Q-learning as well as several other Q-leaming variants that use N action-value estimates.
ACKNOWLEDGMENTS
We would like thank Huizhen Yu and Yi Wan for their valuable feedback and helpful discussion.

---

Published as a conference paper at ICLR 2020
REFERENCES
Oron Anschel, Nir Baram, and Nahum Shimkin. Stabilization for Deep Reinforcement Learning. Learning, pp. 176-185, 2017.
Averaged-DQN: Variance Reduction and In International Conference Machine
Dimitri P Bertsekas and John N Tsitsiklis. Parallel and Distributed Computation: Numerical Methods, volume 23. Prentice hall Englewood Cliffs, NJ, 1989.
Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic Programming, volume 5. Athena
Scientific Belmont, MA, 1996.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv preprint 1606.060060014000 2016.
Herbert Aron David and Haikady Navada Nagaraja. Order Statisties. Encyclopedia of Statistical Sciences, 2004.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference Machine Learning, pp. 1587-1596, 2018
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pp. 1861-1870, 2018.
Hado Hado van Hasselt, Arthur Guez, and David Silver. Deep Reinforcement Learning with Double Q-learning. In AAAI Conference Artificial Intelligence, 2016.
Donghun Lee, Boris Defourny, and Warren B. Powell. Bias-corrected Q-learning to Control Max- operator Bias in Q-learning. In JEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, pp. 93-99, 2013.
Francisco S Melo and M Isabel Ribeiro. Q-learning with Linear Function Approximation. In International Conference Computational Learning Theory, pp. 308-322, 2007.
Alexander L. Strehl, Lihong Li, and Michael L. Littman. Reinforcement Learning in Finite MDPs:
PAC Analysis. Journal of Machine Learning Research,
2009.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press,
second edition, 2018
István Szita and András Lörinez. The Many Faces of Optimism: Unifying Approach. In International Conference Machine learning, pp. 1048-1055. ACM, 2008.
Norman Tasfi. Pygame learning environment.
https://github.coo http://ttth...ommmssts.t.
PyGame Learning Environment 2016.
Sebastian Thrun and Anton Schwartz. Issues in Using Function Approximation for Reinforcement Learning. Fourth Connectionist Models Summer School, 1993.
John N Tsitsiklis. Asynchronous Stochastic Approximation and Q-leaming. Machine learning, 1994.
Hado van Hasselt. Double Q-learning. In Advances Neural Information Processing Systems, pp- 2613-2621, 2010.
Chris Watkins. Learning from Delayed Rewards. PhD thesis, King's 's College, Cambridge, 1989.
Kenny Young and Tian Tian. MinAtar: An Atari-inspired Testbed for More Efficient Reinforcement Learning Experiments. arXiv preprint arXiv: /903.0377 2019.
Wenwu Yu, Rui Wang, Ruiying Li, Jing Gao, and Xiaohui Hu. Historical Best Q-Networks for Deep Reinforcement Learning. In International Conference Tools with Artificial Intelligence, pp. 6-11, 2018.
Zongzhang Zhang, Zhiyuan Pan, and Mykel Kochenderfer. Weighted Double Q-learning. In International Joint Conference Artificial Intelligence, pp. 3455-3461, 2017.
10

---

Published as a conference paper at ICLR 2020
A THE PROOF OF THEOREM 1
We first present Lemma 1 here as a tool to prove Theorem [ Note that the first three properties in this lemma are well-known results of order statistics (David & Nagaraja 2004).
Lemma Let X1...., XN be N i.i.d random variables from an absolutely continuous distribution with probability density function(PDF) f(z) and cumulative distribution function (CDF) F(r). (1...N and XN:N def
Denote μ del =[x,] and o² del [Xr[X.] < +o0. Set XI:N del
(I...( Denote the PDF and CDF of Xy,N as fI,(()) and (z), respectively, Similarly, denote the PDF and CDF of XNN (NN(()) and FN.N(w), respectively. We then have
(i) H (N-1)6
V2n-I S E| S and (
(ii) (FN((E) = - -1 ((--Ra)--nnM)-NNNOO------
(iii) FN-N(E) = (F(x))) [NNN())= N(O1F())))))))
(iv) XI...... XN U(-T,T). we have Var(XI:N) (N+1P(N+2) and Var(X1:441) < Var(Xua) S Var(Xia) = o² for any positive integer N.
4N
Proof.
(i) By the definition of XI,Ns we have X S XI.N Thus E[X < E[Xi,N]. Since E[Xia] E[Xi] E[X < E[Xia] μ.. The proof of [N-1)a
v2N-I < E E[XI:)]
can be found in (David & Nagaraja 2004 Chapter 4 Section 4.2).
(ii) We first consider the edf of XI.N. F1: (x) == P(XIN < x) = =1- > x)
1 P(X, > I,...,XM > x) 1- > x) ... P(N 11= F(x))
Then the pdf of X1.N is fI,(()) dF Nf(xx(1 - N-x)
(iii) Similar to (ii), we first consider edf of XN.N. FN) == P(NN.N S 2) P(X1 S
F....,, XN x) P(X, I x) ..... x) (F(x)) Then the pdf of X fN-N(x) = dFxxx = ((()) dx
(iv) Since X1,..., XN Uniform(- (oommm(T,700 -T,T), have F(x)
and f(x)
V Var(Xu.) = E[XIN2 - E[XiN] 47 (N44NNN4 (N=+T=) = (N+1)
4n72
It is easy to check that Var(XIN41) < Var(X1.N) S Var(X1a) = o² for any positive integer N.
Next, we prove Theorem 1
Proof. Let (x) and F(x)) be the edf and pdf of esa- respectively. Similarly, Let fx(2) and (x be the edf and pdf of min;e e Since e.a is sampled from Uniform((7,,7) is easy to
get (xx and F(x) 2 + 2. By Lemma 1, we have [N(x) Nf(=) N-x)
11

---

Published as a conference paper at ICLR 2020
N (2 -- and (x) = 1 - (1 - -0--)))===----- -1-
= =1- -
The expectation of ZMN is
E|ZMN] - 7 Qr
max D''c.l
a'
=mammax min earl ()
(N))) dx
MN
N-
[1
(
1 AMj dx
2T
2
2T
2
2T
rd(1
(2
1
T
N/M
27
yT -Y -" [1 - (
N jM dr
2T
=77(1 /// (1- y dyl
(y
def
2T
Let twN = (1 ) dy. so that E[ZMN] =TT11 - 2MMN]. Substitute by where = 3// then
tMN = N / x - - 1)adat
B( 1
N M +1
T(M + +)
N T(M +1)
I(M 1)r(1 + ))
T(M +1)
M(M - 1).
(M + )M - ..... (1+ }
Each term the denominator decreases as N increases, because 1/N gets smaller. Therefore, tM M+I and + = 1. Using this, conclude that [[ decreases as N increases and E[ZM,N=1] = 7T M+1 and FlZ = -r.
By Lemma the variance of Qmin is
7
VarlQuan sq
(N (N - 2)
VarlQ (mmm) decreases N increases. In particular, VarlQuir = for N and VarlQuan
0 for N xo.
The bias-variance trade-off Maxmin Q-learning is illustrated by the empirical results in Figure 5 which support Theorem [ For each M, N can be selected such that the absolute value of the expected estimation bias is close according to Theorem I As M increases, we can adjust N to reduce both the estimation variance and the estimation bias.
Finally, we prove the result of the Corollary.
Corollary [ Assuming the ne samples are evenly allocated amongst the N estimators, then T 2 N/ngo where x² is the variance of samples for (s, a) and, for Q.a the estimator that uses all Usa samples for single estimate,
12N2
Var Q
(N + IN +2) Var(Q.a).
Under this uniform random noise assumption, for N 2 8, Var(Qmén) Var(Q.a).
12

---

Published as a conference paper at ICLR 2020
The expected estimationn blas (ElZvv]
Variance Q-learlin
0.9
100%
Variance ratio (VarlQ:""\\ar((Q)
Number actions (M)
0.8
16
0.3
32
0.0
40%
64
128
20%
-0.8
256
8
Number of action-value functions (N)
Number action-valus functions (N)
(a) Bias control
(b) Variance reduction
Figure 5: Empirical results of Theorem [| M is the number of available actions for some state s. N the number of action-valle functions in Maxmin Q-learning. In Figure (a), (a), show heat map of bias control in Maxmin Q-laaning. In Figure (b), we show how the variance ratio Qman and Qsa (i.e. VarlQm /V Var (Q. sa)) reduces as N increases, For better comparison, set yr 1.
Proof. Because Q is sample mean, its variance is o where o² is the variance of samples for (s, a) and mean Qia (because it is an unbiased sample average). Consequently, esn has mean zero and variance σ² N//nna Because esa is uniform random variable which has variance 7 we know that 3 Non2N/naa Plugging this value into the variance formula in Theorem 1 we get that
4N
V Varle Qureii
(N + 1)2(N2 2)
1 0² /
(N + 1)2(N +
12N2
Var [aa]
(N + 1) 2)
because VarlQ.a] = /2/naa for the sample average Q.n that uses all the samples for one estimator. Easy to verify that for N 8, VarlQuur
< Var Var(Qua)
B THE CONVERGENCE PROOF OF GENERALIZED Q-LEARNING
The convergence proof of Generalized Q-Jearning is based on Tsitsiklis (1944). The key steps to use this result for Generalized Q-learning include showing that the operator is contraction and verifying the noise conditions. first show these two steps in Lemma and Lemma We then use these lemmas to make the standard argument for convergence.
B. PROBLEM SETTING FOR GENERALIZED Q-LEARNING
Consider Markov decision problem defined on finite state space S. For every state E S, there is a finite set of possible actions for state and a of non-negative scalars Pss' (a), a E A. s' S, such that E5e (a) = for all E .A. The scalar Par (a) is interpreted as the probability of transition to s', given that the current state is and action is applied. Furthermore, for every state s and action a, there is a random variable Tsa which represents the reward if action a is applied at state We assume that the variance of sa is finite for every and A.
13

---

Published as a conference paper at ICLR 2020
A stationary policy is function и defined on S such that (s)) E A for all E S. Given stationary policy, we obtain a discrete-tine time Markov chain (t) with transition probabilities
Pt( = s'I = s) = Pas (T()))
(5)
Let [0, be a discount factor. For any stationary policy and initial state s, the state value V is defined by
V = lim E T-
(6)
==
The optimal state value function V is defined by
sup V 8 E
(7)
The Markov decision problem is to evaluate the function V*. Once this is done, an optimal policy easily determined.
Markov decision problems are easiest when the discount y is strictly smaller than 1. For undiscounted case (y 1), will assume throughout that there is reward wreerd-free state, say state 1, which is absorbing; that is, Pı1 (a) = and riu = 0 for all a E A. The objective then to reach that state maximum expected reward. We say that stationary policy is proper if the probability of being at the absorbing state converges to as time converges to infinity; otherwise, we say that the policy is improper.
We define the dynamic programming operator T RRS + RISI, with components Tú, by letting
(V)V) = mmx
El +7
El
Σ Pes Per (a)Va/
(8)
aEA
s'ES
It is well known that if y 1, then T is contraction with respect to the norm unique fixed point.
ll and V is its
For Generalized Q-learning algorithm, assume that there N estimators of action-values Q'.....Q' Q.. Let m be the cardinality of S and n be the cardinality of A. We use discrete index variable t order count iterations. Denote (t) Q'(t + j). After t iterations, we have a vector (t) E R= and w mnN K, with components (t). (s, E S x A, i {l...., N),
and j E {O.... K 1). By definition, for j E (1...., K 1}, we have
(t 1)= -
(9)
For O, we have Q = D And we update according to the formula
Q'aa (t 1) Q' (t) a'., (2) (aa(())) (t)
(10)
where
yoQ (t) + 7Q GQ f(s.a) (t).
(11)
Here, each ai (f) is nonnegative step-size coefficient which is set to zero for those (s. E S x A and (1,..., N) for which Q is not to be updated at the current iteration. Furthermore, Tse is random sample of the immediate reward if action a is applied at state s. f(s, a) is random successor state which is equal to s' with probability Pas' (a). Finally, QCQ(t) defined as
QCQ(t) (t))
(12)
where G a mapping from BaNK to R. It is understood that all random samples that are drawn in the course of the algorithm are drawn independently.
Since for j E (1...., - 1}. we just preserve current available action-values, we only focus on the case that j the sequel. Let F' be the mapping from ggnn into gunN with components Fr defined by
Ft (Q) Elr.al + ZEQQC f(.
(13)
14

---

Published as a conference paper at ICLR 2020
and note that
Σ e'ES
Past (a) Q2)
(14)
If Pi (Q(1) = Q(1)
do K more updates such that Q( Q(1.. vi, e (1....,,N) N).
Vj, (O...., - 1}. and va E A.
In view of Equation Equation [0 be written
Qsa (1 + Q(a + us (t) (Q(1) Q'a (1) (1))
(15)
where
who (t) = Tea - Elraal + (0 CQ f(.,a) (t) EIQ (t)
(16)
f(a.a)
and F(t) represents the history of the algorithm during the first t iterations. The expectation in the expression E (ts.a is with respect to f(s,a).
B.2 KEY LEMMAS AND THE PROOFS
Lemma 2 Assume Assumption 7 holds for function G in Generalized Q-learning. Then we have
E[w (1) < Var(rsa) (E(l...,N) Tst (s.))SxxA
max max max 1Q (0aa(T))
Proof. Under Assumption the conditional variance of Cio above by the largest possible value that this random variable could take, which is (1..g(
H(sa given F(t), is bounded
aa) 1Q -) We then take the conditional
variance of both sides of Equation 16 to obtain
max Fl (1)) Var(rsa)+ + (E.....,N) TSt (sa)ESxA
(T)
(17)
We have assumed here that rea is independent from f(s, a). not, the right-hand side in the last inequality must be multiplied by but the conclusion does not change.
Lemma a contraction mapping, in each of the following cases:
(i) 7 1.
(ii) 7 = 1 and Va E A, ai 0) = where 8 is an absorbing state. All policies are proper.
Proof. For discounted problems (y < 1), Equation 13
casily yields VQ, Q',
FFt (Q) - F (Q') S 7 max
QQ - Q2 G9
(18)
sES
In particular, F is a contraction mapping, with respect to the maximum norm |loc-
For undiscounted problems (y 1), our assumptions on the absorbing state $1 imply that the update equation for Q' degenerates to Q (++1) Q (t), for t. We will be assuming in the sequel, that Q initialized at zero. This leads to an equivalent description of the algorithm which the mappings Fi, of Equation
13 are replaced by mappings Fi satisfying Fi Fi, if s & $1 and Fy (Q) = 0 for all A. {1,...,N) NJ and Q R..
Let us consider the special case where every policy proper. By Proposition 2.2 in the work of (Bertsckas & Tsitsiklis) 1996), there exists vector 0 such that T' is contraction with respect to the norm I In fact, close examination of the proof of this Proposition 2.2 shows that this proof is easily extended to show that the mapping (with components F is contraction with respect to the norm ||. ||., where = vs for every E A and E (I....,N)
15

---

Published as a conference paper at ICLR 2020
B.3 MODELS AND ASSUMPTIONS
In this section, we describe the algorithmic model to be employed and state some assumptions that will be imposed.
The algorithm consists of noisy updates of a vector E R", for the purpose of solving system of equations of the form F(x) = z. Here F assumed to be mapping from R into
itself. Let F1. Fi...., Fx: R" + R be the corresponding component mappings; that is, F(z) (Fi
for all IR..
Let N be the set of non-negative integers. We employ discrete "time" variable t, taking values in .. This variable need not have any relation with real time; rather, it is used to index successive updates. Let s()) be the value of the vector x: at time i and let (4) denote its ith component. Let T" be an infinite subset of indicating the set of times at which an update of z, is performed. We assume that
(t + 1) x1((), t T
(19)
Regarding the times that z; is updated, we postulate update equation of the form
2t (t) + (1) x,(()) w;))),, t E
(20)
Here, at(() is step-size parameter belonging [0, 1]. (() is noise term, and (1,(1) is vector of possibly outdated components of r. In particular, we assume that
z' (t) = (.,(tt))...,,(((((()) E
(21)
where each (t) is an integer satisfying 0 S r)(()= S t. If no information is outdated, we have (t) and x' (t) .r(t) for all t; the reader may wish think primarily of this case. For an interpretation of the general case, see (Bertsekas & Tsitsiklis, 1989). In order to bring Eqs. 19 and
into a unified form, it is convenient assume that o; (4), (C), and ()) are defined for every j. and f, but that (t) = 0 and (1) = for T
We will now continue with our assumptions. (a((),=)()) at,(,, (t) are viewed as random variables defined on a probability space F,, and the assumptions deal primarily with the dependencies between these random variables. Our assumptions also involve an increasing sequence {F(t)] of subfields of F. Intuitively, F(t) is meant represent the history of the algorithm up to, and including the point which the step-sizes (t(t) for the ith iteration are selected, but just before the noise term (t) is generated. Also, the measure- theorrtic terminology that "a random variable Z is meassuraal" has the intuitive meaning that Z is completely determined by the history represented by F()).
All variables introduced so far
The first assumption, which is the same the total asynchronism assumption of Bertsekas & Tsitsiklis (1989), guarantees that even though information can be outdated, any old information eventually discarded.
Assumption For any and j, lim; (t) = oo, with probability
Our next assumption refers to the statistics of the random variables involved in the algorithm.
Assumption 4 Let ( be an increasing sequence of subfields of F.
(i) z(0) is F(0) measurabbe.
(ii) For every and t, wx(t) is F(t + memasuura..
(ii) For every i, and I, ass() and r)(1) are F(I) meessarul..
(iv) For every and I, we have Flwx(()F(()) =
(v) There exist (deterministic) constants A and B such that
((w((() < A B max max (2)( Vi,t
(22)
16

---

Published as a conference paper at ICLR 2020
Assumption 4 allows for the possibility of deciding whether to update particular component z; time t. based on the past history of the process. this case, the step-size a, (t(t) becomes a random variable. However, part (tiz) of the assumption requires that the choice of the components to be updated must be made without anticipatory knowledge the noise variables vi that have not yet been realized.
Finally, we introduce a few alternative assumptions on the structure the iteration mapping F. We first need some notation: xr y IR" the inequality y be interpreted x; S yi for all Furthermore, for any positive vector (Vi,..., Un), we define a norm lle on I by letting
ma U/
| max
IR"
(33)
Notice that in the special case where all components of v are equal to 1, lll is the same as the maximum norm ||
lloo.
Assumption 5 Lef F R
R
(i) The mapping F is monotone; that is, if S y, then F(x) S Fly).
(ii) The mapping F is continuous.
(iii) The mapping F has a unique fixed point x²
(iv) e E RR is the vector with all components equal to 1, and r is a positive scalar, then
F(x) - re S F(x - rre) S F(x + re) < F(x) + re
(24)
Assumption There exists vector x² E R2" positive vector v, and scalar 3 [0, 1), such that
[F(x) - x"1lo I B||= x= llus
Vx E R
(25)
Assumption There exists positive vector scalar 8 E (0, and scalar D such that [F(x)]lo B||= +
Vx e R"
(26)
Assumption There exists least one proper stationary policy. Every improper stationary policy yields infinite expected cost for at least one initial state.
Theorem Let Assumptions 1.
7 Then the sequence x(() is bounded with probability
Theorem 4 Let Assumptions 3 and hold. Furthermore, suppose that xxf) is bounded with probability Then ætt) converges to x² with probability 1.
Theorem Let Assumptions
3 4
and hold. Then ætt) converges to x² with probability 1.
Detailed proofs of Theorems and can be found in the work of Bertsekas & Tsitsiklis (1989)
B.4 PROOF OF THEOREM 2
We first state Theorem 2 here again and then show the proof.
Theorem 2 Assume a finite MDP (S, A, P, R) and that Assumption [ and 2 hold. Then the action-value functions in Generalized Q-learning, using tabular update in Equation ( will converge to the optimal action-valus function with probability 1, in each of the following cases:
(i 7 1.
(ii 7 = 1 and Va E A, Qt = 0) = where 8₁ is an absorbing state. All policies are proper.
17

---

Published as a conference paper at ICLR 2020
Proof. We first check Assumptions Theorem to Generalized Q-learming.
3 and i Section B.3 are satisfied. Then we simply apply
Assumption is satisfied in the special case where (t) t, which is what was implicitly assumed in Equation To but can be also satisfied even if we allow for outdated information.
then automatically valid. Part (idi) is quite natural: in particular, assumes that the required samples are generated after we decide which components to update during the current iteration. Part (iv) is automatic from Equation 16 Part (v) is satisfied by Lemma
Regarding Assumption 4 parts (t) and (it) of the assumption
Assumption 2 needs be imposed the step-sizes employed by the Generalized Q-learning algorithm. This assumption is standard for stochastic approximation algorithms. In particular, requires that every state-action pair (s, a) simulated an infinite number of times.
By Lemma 3 F is a contraction mapping. Assumption 6 is satisfied.
All assumptions required by Theorem 5 are verified, convergence then follows from Theorem
C ADDITIONAL EMPIRICAL RESULTS
C.I MDP RESULTS
Comparison of three algorithms using the simple MDP in Figure [ with different values of p is shown in Figure For μl = +0.1, the learning curves of action value (A,, are shown in (a). Here, the true action value Q(A, Left) is +0.1. For μ 0011, the learning curves of action value Q(A, Left) are shown in (b). The true action value Q(A, Left) is -0.1. All results were averaged over 5, 000 runs.
0.20
0.1
Qlsamming
0.15
Double Q-leaming
Mexmin Q-leannin (N-2)
0.0
0.10
Maxmin Q-iaarinng (N=4)
Maxmin Q-eeaning (N-6)
Q(A.LETT)
G-lesming
Q(A.EEF T)
0.05
Maxmin Q-earning (N-8)
-0.1-
Double Q-learing
Maxmin Q-lcaming (N=2)
0.00
True value
Q-learingg (N-4)
-02
Maxmin Q-terning (N-6)
Maxmin Q-lcaring (N=B)
-0.10
value
-0.3
-0.15
0
2000
4000
0
2000
4000
Episodes
Episodes
(a) / +0.11
(b) / 0.1
Figure 6: MDP results
C.2 MOUNTAIN CAR RESULTS
Comparison of four algorithms on Mountain Car under different reward settings is shown in Figure 7 All experimental results were averaged over 100 runs. Note that for reward variance o² = 50, both Q-learning and Averaged Q-learning fail to reach the goal position in 5, 000 steps so there are no learning curves shown in Figure 7 (d) for these two algorithms.
C.3 BENCHMARK ENVIRONMENT RESULTS
The sensitivity analysis results of seven benchmark environment are shown in Figure
18

---

Published as a conference paper at ICLR 2020
500
500
Q-learning
Q-leaaming
Double Q-learning
Double Q-learning
400
Averaged leamming (N-2)
400
Averaged Q-learnin (N-2)
Maxmin Q-learning (N-2)
Mexmin Q-lsaming (N-2)
350
350
Steps
Steps
300
300
250
250
200
200
150
150
200
400
800
800
1000
200
400
600
800
1000
Episodes
Episodes
(a) Reward ~ N\-1,0)
(b) Reward 1(-1,1)
1000
1000
G-learning
Q-teaming
Double Q-learnng
Double Q-learing
800
Averaged Q-learning (N-2)
800
Averaged Qelearning (N-2)
Maxmin Q learning (N-2)
Maxmin leammigg (N-2)
Steps 600
Steps 600
400
400
200
200
200
400
600
800
1000
250
500
750
1000
Episodes
Episodes
(c) Reward ~
(d) Reward ~ NN11,
Figure 7: Mountain Car results
19

---

Published as a conference paper at ICLR 2020
80
DGN
50
Averaged
40
Maxmin DGN
Average Retum
Average Return
DON
Averaged
Maxmin DGN
-4.0
-3.5
-3.0
-5.0
-4.5
-4.0
-3.5
+3.0
logio
log
Catcher
(b) Pixelcopter
DGN
200
20
DDON
Averaged
Maxmin DON
0-
15
Average
Average Return
Retum
-200
10
DON
100
DOON
Maxmin DON
-600
-.5
-4.0
-3.5 logt.
-3.0
-25
-4.5
-4,0
-3.5
-3.0
-25
log
(c) Lunarlander
(d) Asterix
12
50-
10-
Average
Average Return
Retur
DOON
DOON
Averaged
DON
DON
-.5
-4.0
-355
-3.0
-2.5
-4.5
-4,0
-3.5
-3.0
-25
logio
log
(c) Space Invaders
(f) Breakout
15.0
12.5
Average10.0
2.5
DDON
Averaged DQN
-45
-4.0
-3.5
-3.0
-25
logo
(g) Seaquest
Figure 8: Sensitivity analysis
20


Reviews:
[{"review_id": "rygrmXsCtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 proposes a novel variant of Q-learning, called Maxmin Q-learning, to address the issue of overestimation bias Q-learning suffers from (variance of the reward of best action leading to overestimated reward). \nThe idea is to keep a number of estimators each estimated using a different sub-sample, and taking the minimum of the (maximum) reward value of each. \nThe paper gives theoretical analyses, in terms of the reduction in the overestimation bias, as well as the convergence of a class of generalized Q-learning methods including Maxmin Q-learning. \nThe experiment section presents a thorough evaluation of the proposed method, including how the obtained rewards vary as a function of the variance of the reward function and as a function of learning steps, as compared to a number of existing methods such as the Double Q-learning method and its variants. \nThe experimental results are quite convincing, and the theoretical analyses seem solid. \nOverall this is a well balanced paper which proposes a reasonable new idea, simple but effective, backed by sound theoretical analysis and well executed experimental evaluation. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgA2mRnYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 proposes a new Q learning algorithm framework: maxmin Q-learning, to address the overestimation bias issue of Q learning. The main contributions of this paper are three folds: 1) It provides an inspiring example on overestimation/underestimation of Q learning. 2) Generalize Q learning by a new maxmin Q-learning by maintaining independent Q estimator and interact them in a max-min way for the update. 3) Provide both theoretical and empirical analyses of their algorithm.\n\nI have two main concerns for this paper:\n1) When is your algorithm useful? What's your criterion of picking the hyper-parameters (e.g. number of Q functions you want to learn).\n2) Comparison to more intriguing way for jointly update of multiple Q functions, like soft Q learning.\n\nFor the first concern, the paper has shown an interesting example in Figure 2. However, it seems that we cannot decide whether overestimation or underestimation will help the exploration, since the reward function is often unknown in real world. And in both cases, maxmin Q learning is not the best algorithm than either Q learning and double q learning. On the other hand, if we use a softmax policy for Q function, e.g. $\\pi(a|s) \\propto \\exp(\\alpha Q(s,a))$, a drift for Q learning(e.g. Q(s,a) = Q*(s,a) + c) has no effect on our policy. I believe in this case we should more focusing on the inner difference between different value of Q function, rather than comparing our estimate Q function with the true Q*.\n\nFor the second concern, we can view the framework of maxmin q learning as a joint update scheme for different Q function. In experimental part, the comparison is not fair since the paper use multiple Q function to compare with single or double Q function. One reasonable baseline is to update N different Q function, and take the minimum of the final Q function as our decision policy, compare with maxmin Q learning with N different Q function. Another baseline the paper should consider is soft Q learning, where it maintain multiple Q function and jointly update Q different function to maximize the entropy while moving towards an improvement Q.\n\nOverall, I believe the idea of the paper is novel and interesting, but further improvements should be added in order to improve the score the paper.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgkW77MYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "The paper tackles the problem of bias in target Q-values when performing Q-learning.  The paper proposes a technique for computing target Q-values, by first taking the min over an ensemble of learned Q-values and then taking the max over actions.  The paper provides some theoretical properties of this technique: (1) the bias of the estimator can be somewhat controlled by the size of the ensemble; (2) performing Q-learning with these target values is convergent. Experimental results show that the proposed technique can provide performance improvement on a number of tasks.\n\nOverall, this paper is a modest contribution to the field, since variants of this technique are known and the theoretical arguments are derivatives of known arguments, which places it roughly borderline for an ICLR conference paper.\n\nMy comments:\n-- The paper is very well-written. Thank you for putting the effort to provide clear writing.\n-- The idea of computing a target value as the minimum of an ensemble is well-known in continuous control.  See https://arxiv.org/abs/1802.09477 as well as a number of works which follow it.\n-- The method is motivated as a way to control over/under-estimation.  However, the theoretical arguments show that this depends on N, M, and tau (unknown). Are there any ways to choose N other than hyperparameter tuning?", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose the use of an ensembling scheme to remove over-estimation bias in Q-Learning. The idea is simple but well-founded on theory and backed by experimental evidence. The authors also extensively clarified distinctions between their idea and similar ideas in the reinforcement learning literature in response to reviewer concerns.
Decision: Accept (Poster)