Damped Anderson Mixing for Deep Reinforcement Learning: Acceleration, Convergence, and Stabilization

Abstract:
Anderson mixing has been heuristically applied to reinforcement learning (RL) algorithms for accelerating convergence and improving the sampling efficiency of deep RL. Despite its heuristic improvement of convergence, a rigorous mathematical justification for the benefits of Anderson mixing in RL has not yet been put forward. In this paper, we provide deeper insights into a class of acceleration schemes built on Anderson mixing that improve the convergence of deep RL algorithms. Our main results establish a connection between Anderson mixing and quasi-Newton methods and prove that Anderson mixing increases the convergence radius of policy iteration schemes by an extra contraction factor. The key focus of the analysis roots in the fixed-point iteration nature of RL. We further propose a stabilization strategy by introducing a stable regularization term in Anderson mixing and a differentiable, non-expansive MellowMax operator that can allow both faster convergence and more stable behavior. Extensive experiments demonstrate that our proposed method enhances the convergence, stability, and performance of RL algorithms.

heading: 1 Introduction
text: In reinforcement learning (RL) [28], an agent seeks an optimal policy in a sequential decisionmaking process. Deep RL has recently achieved significant improvements in a variety of challenging tasks, including game playing [20, 26, 18] and robust navigation [19]. A flurry of state-of-theart algorithms have been proposed, including Deep Q-Learning (DQN) [20] and variants such as Double-DQN [13], Dueling-DQN [31], Deep Deterministic Policy Gradient (DDPG) [16], Soft Actor-Critic [12] and distributional RL algorithms [5, 17, 33], all of which have successfully solved end-to-end decision-making problems such as playing Atari games. However, the slow convergence and sample inefficiency of RL algorithms still hinders the progress of RL research, particularly in high-dimensional state spaces where deep neural network are used as function approximators, making learning in real physical worlds impractical.
To address these issues, various acceleration strategies have been proposed, including the classical Gauss-Seidel Value Iteration [23] and Jacobi Value Iteration [24]. Another popular branch of techniques accelerates RL by leveraging historical data. Interpolation methods such as Average-DQN [2] ∗Equal contributions in alphabetical order †Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
have been widely used in first-order optimization problems [6] and have been proven to converge faster than vanilla gradient methods. As an effective multi-step interpolation method, Anderson mixing [30, 9], also known as Anderson acceleration, has attracted great attention from RL researchers. The insight underpinning of Anderson acceleration is that RL [28] is intrinsically linked to fixed-point iterations: the optimal value function is the fixed point of the Bellman optimality operator. These fixed-points are computed recursively by repeatedly applying an operator of interest [11]. Anderson mixing is a general method to accelerate fixed-point iterations [30] and has been successfully applied to fields, such as the computational chemistry [22] or electronic structure computation [1]. In particular, Anderson acceleration leverages the m previous estimates in order to find a better estimate in a fixed-point iteration. To compute the mixing coefficients in Anderson iteration, it searches for a point with a minimal residual within the subspace spanned by these estimates. It is thus natural to explore the efficacy of Anderson acceleration in RL settings.
Several works [15, 25] have attempted to apply Anderson acceleration to reinforcement learning. Anderson mixing was first applied to value iteration in [11, 15] and resulted in significant convergence improvements. Regularized Anderson acceleration [25] was recently proposed to further accelerate convergence and enhance the final performance of state-of-the-art RL algorithms in various experiments. However, previous applications of Anderson acceleration were typically heuristic: consequently, these empirical improvements in convergence have so far lacked a rigorous mathematical justification.
In this paper, we provide deeper insights into Anderson acceleration in reinforcement learning by establishing its connection with quasi-Newton methods for policy iteration and improved convergence guarantees under the assumptions that the Bellman operator is differential and non-expansive. MellowMax operator is adopted to replace the max operator in policy iteration to simultaneously guarantee faster convergence of value function and reduce the estimated gradient variance to yield stabilization. In addition, we analyze the stability properties of Anderson acceleration in policy iteration and propose a stable regularization to further enhance the stability. These key two factors, i.e., the stable regularization and the theoretically-inspired MellowMax operator, are the basis for our Stable Anderson Acceleration (Stable AA) method. Finally, our experimental results on various Atari games demonstrate that our Stable AA method enjoys faster convergence and achieves better performance relative to existing Anderson acceleration baselines. Our work provides a unified analytic framework that illuminates Anderson acceleration for reinforcement learning algorithms from the perspectives of acceleration, convergence, and stabilization.

heading: 2 Acceleration and Convergence Analysis of Anderson Acceleration on RL
text: We first present the notion of Anderson acceleration in the reinforcement learning and then provide deeper insights into the acceleration if affords by establishing a connection with quasi-Newton methods. Finally, a theoretical convergence analysis is provided to demonstrate that Anderson acceleration can increase the convergence radius of policy iteration by an extra contraction factor.
Background Consider a Markov decision process (MDP) specified by the tuple (S,A, R, p, γ), where S is a set of the states and A is a set of actions. The functions R : S × A → R and p : S × A × S → [0, 1] are the reward function, with Rt = R(s, a), and transition dynamics function, respectively for the MDP. The discount rate is denoted by γ ∈ [0, 1) and determines the relative importance of immediate rewards relative to rewards received in the future. The Qvalue function evaluates the expected return starting from a given state-action pair (s, a), that is, Qπ(s, a) = E [ ∑∞ t=0 γ
tRt+1 | s0 = s, a0 = a]. A policy π(a|s) is a distribution mapping the state space S to the action space A.

heading: 2.1 Anderson Acceleration in Policy Iteration
text: We focus on the tabular case to enable the theoretical analysis of Anderson acceleration in value (policy) iteration, which can be naturally applied to function approximation. Both the value iteration (V -notation) and the policy iteration (Q-notation) can have Anderson acceleration applied to them to improve convergence. However, theoretical analysis has shown that value iteration enjoys a γ-linear convergence rate, i.e., ‖V (t) − V ∗‖∞ ≤ γ‖V (t−1) − V ∗‖∞, where V (t) is the value function in the iteration step t and V ∗ is the optimal value function, while policy iteration converges
faster. This is due to the fact that policy iteration more fully evaluates the current policy than does value iteration. Additionally, policy iteration is more fundamental and scales more readily to deep reinforcement learning. For this reason, we analyze our method in the policy iteration setting under Q-notation as value iteration is a special case of policy iteration. Thus, our analysis also applies under value iteration.
We first focus on the control setting where the optimal value of state-action pair Q∗(s, a) is defined recursively as a function of the optimal value of the other state-action pair:
Q∗(s, a) = R(s, a) + γ ∑ s′∈S p (s′ | s, a) ·max a′ Q∗ (s′, a′) . (1)
Combining policy evaluation and policy improvement, the resulting policy iteration algorithm is equivalent to solving for the fixed point of the Bellman optimality operator T : R|S×A| → R|S×A| with T Q(s, a) = R(s, a) + γ ∑ s′∈S p (s
′|s, a) ·maxa′ Q (s′, a′) . As a general technique to speed up fixed-point iteration [30], Anderson acceleration has been successfully yet heuristically applied to reinforcement learning algorithms [25, 11, 15]. Specifically, Anderson acceleration linearly combines the m previous estimates to yield a better iteration target in the fixed point iteration. Geometrically, Anderson acceleration applies the operator to a point that has a minimal residual within the subspace spanned by these estimates. In policy iteration, Anderson acceleration maintains a memory of the previous Q function values and updates the iterate as a linear combination of these values with dynamic weights α(k) in the kth iteration step. Specifically,
Q(k+1)(s, a) = (1− βk) m∑ i=0 α (k) i Q (k−m+i)(s, a) + βk m∑ i=0 α (k) i T Q (k−m+i)(s, a), (2)
where 0 ≤ βk ≤ 1 is the damping parameter. All of the coefficients α(k)i in the coefficient vector α(k) are computed following
α(k) = argmin α∈Rm+1 ∥∥∥∥∥ m∑ i=0 αi ( T Q(k−m+i) −Q(k−m+i) )∥∥∥∥∥ 2 = argmin α∈Rm+1 ∥∥∥∆′kT · α∥∥∥ 2 , s.t. m∑ i=0 αi = 1,
(3) where ∆′k T = [ek−m, · · · , ek] ∈ R|S×A|×(m+1) and ek = T Q(k) −Q(k) ∈ R|S×A| is the Bellman residuals matrix. By the Karush-Kuhn-Tucker conditions, the analytic solution of optimal coefficient vector αk is
α(k) =
( ∆′k∆ ′ k T )−1 1
1T ( ∆′k∆ ′ k T )−1 1 , (4)
where 1 denotes the vector with all components equal to one.

heading: 2.2 Connection Between Damped Anderson Acceleration and Quasi-Newton Methods
text: We know that the optimization problem is closely linked with solving a fixed-point iteration problem by directly solving its first-order condition. Inspired by [8], we show that Anderson acceleration in policy iteration attempts to perform a special form of quasi-Newton iteration from its optimization problem behind.
To illuminate this connection, we firstly show that the original constrained optimization to obtain the optimal α(k) in Eq.(3) can be equivalent to the unconstrained one
τ (k) = argminτ∈Rm ‖ek −Hkτ‖ 2 , (5)
where we let n = |S| × |A|, and then Hk = [ek − ek−1, · · · , ek−m+1 − ek−m] ∈ Rn×m. τ (k) = [ τ (k) 0 , τ (k) 1 , · · · , τ (k) m−1 ]T ∈ Rm with τ (k)i = ∑m−i−1 j=0 α (k) j . Let δk = Q
(k) − Q(k−1), ∆k = [δk, δk−1, · · · , δk−m+1] ∈ Rn×m. We show that the updating rule of Q(s, a) in Anderson acceleration can be expressed as a quasi-Newton form in Proposition 1.
Proposition 1. By conducting the damped Anderson acceleration (Eq.(2) and (3)) on the policy iteration, the updating of Q(k+1) can be reformulated as
Q(k+1) := Q(k) −Gkek (6) whereGk = (∆k + βkHk) ( HTk Hk )−1 HTk −βkI can serve as an approximation of inverse Jacobian matrix of ek = TQ(k) −Q(k), and I is an identity matrix.
Proposition 1 points out that Anderson acceleration on policy iteration additionally leverages more information about the fixed-point residual ek = TQ(k) −Q(k) to update the Q function. Particularly, the first part (∆k + βkHk)(HTk Hk)
−1HTk in Gk contains partial structure matrix information about the real inverse of Jacobian matrix, which has the huge potential to speed up the convergence of the fixed-point iteration. More importantly, the results established in [30] and [9] can been seen as special cases of Proposition 1 with βk = 1. If we directly get rid of the first part in Gk and set βk = 1, the updating rule exactly degenerates to the Q-value function iteration without Anderson acceleration.

heading: 2.3 Convergence Rate Analysis of Anderson Acceleration on RL
text: The success of the Anderson acceleration to reduce the residual is coupled in the algorithm iteration at each stage. Let eαk = ∑m j=0 α (k) j (TQ
(j)−Q(j)). The stage-k gain θk can be defined by ‖eαk‖∞ = θk‖ek‖∞. As α(k)k = 1, α (k) j = 0, j 6= k, i.e., m = 0, is an admissible solution to the optimization problem in Eq. (3), it immediately follows that 0 ≤ θk ≤ 1. The key to rigorously show that Anderson acceleration can speed up the convergence of policy iteration by taking a linear combination of history steps is connecting the gain θk to the differences of consecutive iterates Q(k) and residual terms ek. As discussed in the following part, the improvement of the convergence rate of the policy iteration by using the acceleration technique is characterized by θk. We first consider the following assumption about the operator T used to guarantee the first and second order derivatives of T are bounded, as in [7]. Assumption 1. Assume the Bellman operator T acting on state-action value function Q has a fixed point Q∗, and there are positive constants c1 and c2 such that
1. T ∈ C2(R|S×A|). 2. The first derivative of T is bounded by c1. 3. The second derivative of T is bounded by c2. Theorem 1. Under Assumption 1, if the coefficients α(k)i remain bounded and away from zero, the following bound holds for the fixed point residual ek from Eq. (2) and (3) with depth m ‖ek‖∞ ≤ θk {((1− βk−1) + c1βk−1) ‖ek−1‖∞}+ c2 · (‖δk‖∞ + ‖δk−1‖∞)|τ1|‖δk−1‖∞
+ c2 · m∑ i=2 ( ‖δk‖∞ + ‖δk−i‖∞ + 2 i−1∑ l=1 ‖δk−i‖∞ ) |τi| ||δk−i‖∞.
(7)
Note that the first term of RHS in Eq. (7) characterizes an increased convergence radius by an extra contraction factor θk. Therefore, if the error terms ‖δk−i‖∞ are small enough, and the operator T is differentiable and has bounded first and second derivatives, the faster convergence result characterized by θk can be derived for the Q-value function iteration with Anderson acceleration.
Unfortunately, the commonly used max operator in T does not satisfy Assumption 1 as it is not a differentiable operator. Moreover, the “hard” max operator in T always commits to the maximum action-value function according to current estimation for updating the value estimator, lacking the ability to consider other potential action-values. A natural alternative is the Boltzmann Softmax operator, but this operator is prone to misbehave [3] as it is not a non-expansive operator. MellowMax operator [3], which can help strike a balance between exploration and exploitation, is considered in this paper. More importantly, the more meaningful convergence result of Anderson acceleration in policy iteration under Assumption 2 can be established due to the contraction properties of the Bellman operator under MellowMax operator. The results are given in Theorem 2. Assumption 2. Assume the Bellman operator T acting on state-action value function Q is a γcontraction operator, i.e., ‖T Q−T Q′‖∞ ≤ γ‖Q−Q′‖∞ for each state-action function pair Q and Q′.
Theorem 2. If both Assumption 1 and 2 hold, the coefficients α(k)i remain bounded and away from zero. The following bound holds for the residual ek with depth m
‖ek‖∞ ≤ θk[(1− βk−1) + c1βk−1]‖ek−1‖∞ +O( m∑ j=1 ‖ek−j‖2∞). (8)
From Theorem 2, we find that there is a theoretical advantage to consider Anderson acceleration for policy iteration with depth m due to the gain θk even with the higher-order accumulating terms. Fortunately, the Bellman operator with MellowMax operator is a γ-contraction operator, satisfying Assumption 2. Specifically, the resulting Bellman operator Tmm under the MellowMax operator is defined as
TmmQ(s, a) = R(s, a) + γ ∑ s′∈S p (s′ | s, a)mmω (Q (s′, ·)) , (9)
where mmω is the MellowMax operator and mmωQ (s′, ·) = log( 1|A| ∑ a′ exp[ωQ(s
′, a′)])/ω. Rigorously, we show that MellowMax can simultaneously satisfy Assumption 1 and 2 in Appendix B. As such, the faster convergence result presented in Theorem 2 can be derived. In other words, the faster convergence of policy iteration under MellowMax operator can be established by applying Anderson acceleration. Based on this theoretical principle, we apply MelloxMax operator in the Bellman operator to design our method in Section 3, where a detailed discussion is also provided.
Finally, the Q-value estimate Q(k) can be obtained by iteratively applying the MellowMax operator by starting from some initial value Q(0):
Q(k+1) ← (1− βk) m∑ i=0 α (k) i Q (k−m+i) + βk m∑ i=0 α (k) i TmmQ (k−m+i), ∀(s, a) ∈ (S,A). (10)

heading: 3 Stabilization Analysis and Our Method
text: In this section, a stable regularization is firstly introduced and its stability analysis is provided as well. We then briefly analyze the role that MellowMax operator plays when conducting Anderson acceleration on deep reinforcement learning. These two factors eventually inspire our algorithm, which we call Stable Anderson Acceleration (Stable AA).

heading: 3.1 Stable Regularization
text: Inspired by recent stable results of Anderson acceleration [9], we introduce the stable regularization term on the aforementioned unconstrained optimization problem Eq. (5) to obtain mixing coefficients τk. Particularly, we add `2 regularization of τk scaled by the Frobenius norm of ∆k and Hk to improve the stability. This yields the new optimization problem
τk = argmin τ∈Rm
‖ek −Hkτ‖2 + η ( ‖∆k‖2F + ‖Hk‖ 2 F ) ‖τ‖2, (11)
where η is a positive tunning parameter representing the scale of regularization. The solution is τk = (HTk Hk + η(‖∆k‖2F + ‖Hk‖2F )I)−1HTk ek. We introduce this stable regularization under the unconstrained variables τk, which facilitates the optimization. Intuitively, if the algorithm converges, we have limk→∞ ‖∆k‖F = limk→∞ ‖Hk‖F = 0. Therefore, the coefficient on the regularization term vanishes as the algorithm converges, degenerating to Anderson acceleration method without the stable regularization. In this sense, the stability owing to our stable regularization plays a more important role in the early phase of training, which we demonstrate in Section 4. Based on the solved stable regularization τk and the relationship between τk and α(k), we derive the updating of Q(k+1) in the policy iteration as follows
Q(k+1) = Q(k) − G̃kek, (12)
where G̃k = −βkI + (∆k + βkHk) ( HTk Hk + η(‖∆k‖2F + ‖Hk‖2F )I )−1 HTk .
Moreover, the following Theorem characterizes the stability ensured by regularization in Eq (11). Please refer to the proof in Appendix C.
Theorem 3. The matrix G̃k satisfy ‖G̃k‖2 ≤ |2/η − βk| , ‖G̃−1k Gk‖2 < 1.
Theorem 3 derives the upper bound of ‖G̃k‖2, which is determined by η and βk. Intuitively, a larger strength of regularization η and a proper magnitude of βk can yield more stability. In addition, ‖G̃−1k Gk‖2 is strictly less than 1, revealing a smaller violation in Q(k) iteration compared with non-regularized form.
To quantify the effect of regularization on the coefficient α(k), we provide some analytical results regarding the obtained mixing coefficients α(k) in Proposition 2. The proof is provided in Appendix C.
Proposition 2. Let α(k)non and α(k)reg be the mixing coefficient vectors obtained by vanilla unconstrained and our stable regularized Anderson acceleration, respectively. Define the transformation matrix as A, satisfying α(k) = A · τ̃k with τ̃ (k) = (1, τk)T (detailed structure of A is in the Appendix C). Let cond2(A) be the conditional number of A, i.e., cond2(A) = ‖A‖2‖A−1‖2. Then we have the following inequalities
‖α(k)reg ‖22 ≤ 4(1 + ‖ek‖2
η2 ), ‖α(k)reg − α(k)non‖22 ≤ (cond2(A))2 · ∥∥∥α(k)non∥∥∥2 2 − 2m+ 1 m+ 1 . (13)
From the first inequality, we observe that the `2-norm of the derived coefficients α (k) reg is controlled by the regularization parameter η. An overly large η tends to reduce the bound for the norm of α(k)reg , implying a stable solution of the mixing coefficients α(k)reg . Besides, we can conclude from the second inequality that there is an inevitable gap between α(k)non and α (k) reg .

heading: 3.2 Stability Effects of MellowMax
text: The adopted MellowMax operator bridges the Anderson acceleration and reinforcement learning algorithms and it has two-sided stability effects. Firstly, based on the convergence analysis in Section 2, MellowMax operator satisfies the differential and non-expansive properties, which allows the faster convergence of Anderson acceleration in policy iteration. In contrast, the commonly used max and Boltzmann Softmax operator [4, 28] violate one of the theoretical assumptions respectively, and thus the (faster) convergence of Anderson acceleration under them may not be guaranteed. This is likely to yield instability while the training of algorithms.
Secondly, it is well-known that the “hard” max updating scheme in the popular off-policy methods, such as Q-learning [32], may lead to misbehavior due to the overestimation issue in the noisy environment [29, 13, 21]. By contrast, it has been demonstrated that MellowMax and Softmax operators are capable of reducing the overestimation biases, therefore reducing the gradient noises to stabilize the optimization of neural networks [3, 27]. The stable gradient estimation based on MellowMax operator leads to the enhancement of final performance for algorithms.

heading: 3.3 Algorithm: Stable AA
text: The introduced stable regularization approach combined with the MellowMax operator finally form our Stable AA method. In our algorithm, we focus on exploring the impact of Stable AA on DuelingDQN [31]. In particular, under the procedure of off-policy learning in DQN, we firstly formulate the general damped Anderson acceleration form with the function approximator Qθ as follows
Qθ (st, at) = βt m∑ i=1 α̂iQθi (st, at) + (1− βt)Est+1,rt
[ rt + γ
m∑ i=1 α̂i max at+1 Qθi (st+1, at+1)
] ,
(14) where θi are parameters of target network before the i-th update step. α̂i can be computed either by vanilla Anderson acceleration [11], or Regularized Anderson acceleration [25]. Then the obtained Qθ (st, at) serves as the target in the updating of Q-networks. In our Stable AA method, we firstly solve the optimization problem in Eq. (11) to compute τk. Next we obtain α̃(k) by making use of the quantitative relationship between τk and α(k). More importantly, we substitute max with MellowMax operator mmω. The resulting target value function Q̃θ in our Stable AA algorithm is
Algorithm 1 Stable AA Dueling-DQN Algorithm 1: Initialize a Q value network Qθ and m target networks with parameters θi (i = 1, ...,m). Set the
total training steps K and updating step M . 2: while k ≤ K do 3: Observe the initial state s0; 4: for t = 1 to T do 5: Select at = arg maxaQθ(st, a) with probability 1− and a random action with probability . 6: Perform the action at, obtain rt and st+1. Store the transition (st, at, rt, st+1) in the replay buffer. 7: Sample the batch of transitions (s, a, r, s′) from the replay buffer. 8: / * Step 1: compute α̃(k) * / 9: Compute ∆k and Hk, and then solve the optimization problem with stable regularization in
Eq. (11) to obtain τk. 10: Obtain the optimal coefficient vectors α̃(k) via α̃(k) = A · τ̃k, where the transformation matrix A is defined in Proposition 2. 11: / * Step 2: compute the target Q̃θ by Anderson Mixing * / 12: Compute the value after the MellowMax operator for each target network Qθi , i.e., mmω(Qθi(st+1, ·)) 13: Evaluate the target value function Q̃θ (st, at) via Eq. (15) under the Melloxmax operator. 14: / * Step 3: update the Q value networks * / 15: Update the Q value network θ by minimizing the loss in Eq.(16) with the target yt from Step 2. 16: Update m target networks every M steps, i.e., θi ← θi+1(i = 1, ...,m) and θm ← θ. 17: Set k = k + 1. 18: end for 19: end while
reformulated as
Q̃θ (st, at) = βt m∑ i=1 α̃iQθi (st, at) + (1− βt)Est+1,rt
[ rt + γ
m∑ i=1 α̃i ·mmω(Qθi (st+1, ·))
] ,
(15) where mmω(Q(s, ·)) is the MellowMax operator. Finally, the updating is performed by minimizing the least squared errors of Bellman equation between the current Q value estimate Qθ(st, at) and the target value function yt obtained from Eq. (15),
L(θ) = E(st,at)∈D [ (yt −Qθ (st, at))2 ] , (16)
where D is the distribution of previously sampled transitions. In summary, the key of Stable AA method in policy iteration lies in two factors: the stable regularization in Eq. (11) in computing coefficient α(k), and the MellowMax operator enabling the faster convergence in updating Q(k), both of which improve the convergence and sample efficiency. Moreover, we provide a detailed description of Stable AA on Dueling-DQN algorithm in Algorithm 1. Similar to the strategy in [25], the incorporation of Stable AA into policy gradient based algorithms, including actor critic [28] and twin delayed DDPG (TD3) [10] can be directly implemented in their critics part. It can be viewed as a straightforward extension, and we leave this exploration as future works.

heading: 4 Experiment
text: Our theoretical results about Anderson acceleration mainly apply to the case of a tabular value function representation, but our derived Stable AA algorithms can be naturally applied into the function approximation setting. The goal of our experiments is to show that our Stable AA method can still be useful in practice by improving the performance of Dueling-DQN algorithms. Our experimental results demonstrate that such an improvement is attributed to the joint benefits of the proposed stable regularization and the MelloMax operator.
Experimental Settings We perform our Stable AA Dueling-DQN algorithm on a variety of Atari games, and mainly focus on reporting four representatiave games, i.e., SpaceInvaders, Enduro, Breakout, and CrazyClimber. Results of other games are similar, which we provide in Appendix D. We compare our approach with Dueling-DQN [31] and Regularized Anderson Acceleration (RAA)[25]. In addition, we also provide an ablative analysis about our Stable AA algorithm to illuminate the separate and joint impacts of stable regularization and MellowMax operator. In the following experiments, we report results statistics by running three independent random seeds. We set βt in Eq. (15) as 0.1 for convenience.
Implementation of MellowMax Operator The MellowMax operator mmω satisfies the desirable differential and non-expansive properties, enabling the faster convergence in policy iteration with Anderson acceleration. Nevertheless, we need to perform an additional root-finding algorithm [3] to compute the optimal ω in each state in order to maintain these properties and help the MellowMax operator to identify a probability distribution. Unfortunately, this root-finding algorithm is computationally expensive to be applied. Following the strategy in [27], we tune the inverse parameter ω from {1, 5, 10} and then report the best score.

heading: 4.1 Performance of Our Stable AA
text: We select DuelingDQN and DuelingDQN-RAA as baselines for the evaluation on the four Atari games. These two algorithms and our approach DuelingDQN-Stable AA are trained under the same random seeds and evaluated every 10,000 environment steps, where each evaluation reports the average returns with standard deviations. Our implementation is adapted from RAA [25]. After the grid search, we set ω in MelloxMax of Stable AA as 5.0 and η in stable regularization as 0.1 across 4 Atari games.
From Figure 1, we note that our DuelingDQN-StableAA (red line) significantly outperforms Regularized AA (blue line) and baseline (black line) across all four games. Overall, Dueling-RAA enables to accelerate DuelingDQN to improve the sample efficiency and enhance the final performance, but our approach can lead to further benefits. Remarkably, our DuelingDQN-StableAA (red line) is superior to RAA to a large margin, especially on Breakout where our approach achieves around 250 average return while RAA only achieves 150 return. In summary, we conclude that the joint impact of both stable regularization and theoretically-principled MellowMax further accelerate the convergence and improve the sample efficiency of the popular off-policy DuelingDQN algorithm.

heading: 4.2 Ablation Analysis
text: We further examine the separate impact of the proposed stable regularization (shown in Eq. (11)) and the theoretically-principled MelloxMax operator via the rigorous ablation study. Starting from DuelingDQN, we firstly add stable regularization with different scales η while comparing with our resulting Stable AA method. Meanwhile, we separately replace Max operator in DuelingDQN with MellowMax operators with various inverse parameters ω to explore their impacts.
Impact of Stable Regularization From diagrams in the first row of Figure 2, we can observe that the benefit margin of stable regularization on Anderson acceleration differs from game to game. Concretely, naively applying stable regularization on DuelingDQN regardless of the MellowMax to guarantee the faster convergence of Anderson acceleration can still significantly accelerate the convergence in Spaceinvaders. In contrast, the stable regularization is able to boost the sample efficiency mildly on Enduro. For example, when η = 1.0 (green line), “+StableReg1.0” is more sample efficient (higher than yellow and orange lines) in the early phase of training. However, the benefit of stable regularization vanishes as the training proceeds, achieving comparable performance with DuelingDQN. Interestingly, if we further add the additional MellowMax operator (red line), the resulting Stable AA approach can accomplish the improvement of performance to a large margin.
Impact of MellowMax Operator As exhibited in diagrams in the last row of Figure 2, the benefit of MellomMax operator still depends on the game. Particularly, the improvement of MellowMax operator on SpaceInvaders is negligible, where the lines representing “+MelloxMax” overlap subtly with DuelingDQN. Nevertheless, our Stable AA additionally incorporates the stable regularization, achieving remarkable improvement of sample efficiency. In addition, due to the fact that it is hard to compute the optimal inverse temperature ω in MellowMax, we tune the parameter ω and report the corresponding results in Figure 2. It manifests from the diagram on Enduro game that MellowMax under ω = 5.0, 10.0 (green and yellow lines) can substantially enhance the final performance. More importantly, under the joint benefits of both the stable regularization and the theoretically-principled MellowMax operator, our Stable AA DuelingDQN algorithm can simultaneously accelerate the convergence and improve the final performance.

heading: 5 Discussion and Conclusion
text: Apart from MellowMax, other variants of Softmax operator can also be combined with Anderson acceleration, although their theoretical principles have not been studied. For instance, the competitive
performance of the Boltzmann Softmax operator suggests that it is still preferable in certain domains, despite its non-contraction property. We leave the exploration towards more desirable operators as future works. Additionally, the study of our approach on a wider variety of Atari games, and implement on more state-of-the art algorithms are expected in the future.
In this paper, we firstly provide deeper insights into the mechanism of Anderson acceleration on the reinforcement learning setting by connecting damped Anderson acceleration with quasi-Newton method and providing the faster convergence results. These theoretical principles about the faster convergence of Anderson acceleration inspire the leverage of MellowMax operator. Combing with a stable regulation, the resulting Stable AA strategy is applied in DuelingDQN, which has been further demonstrated to significantly accelerate the convergence and enhance the final performance.

heading: Acknowledgement
text: We would like to thank the anonymous reviewers for great feedback on the paper. Yingnan Zhao and Ke Sun were supported by the State Scholarship Fund from China Scholarship Council (No:202006120405 and No:202006010082). Dr. Jiang and and Dr. Kong were supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). Dr. Kong was also supported by the University of Alberta/Huawei Joint Innovation Collaboration, Huawei Technologies Canada Co., Ltd., and Canada Research Chair in Statistical Learning.

Review summaries:
The paper provides a mathematical justification for the benefits of Anderson Accelerating in RL by connecting Anderson mixing and quasi-newton method. The paper also propose a stable Anderson Accelerating (stable AA )algorithm with a stable regularization term and a MellowMax operator and evaluate the performance with Dueling DQN on a variety of Atari games environments. Experimental results show that the proposed algorithm improves convergence, stability and final performance compared to vanilla Dueling DQN and Dueling DQN with previous RAA method.

Anderson mixing is a heuristic applied to RL to improve sample-efficiency and convergence. This paper delves into the theoretical side of the Anderson mixing that improves the convergence of deep RL algorithms, showing that the Anderson mixing adds an extra contraction. This paper also shows the connection between Anderson mixing and Mellowmax operator, showing more stable performance and fast convergence. 

This paper looks to characterise the use of Anderson acceleration in Deep Q learning.  Theoretical convergence results are given in tabular settings. A novel algorithm is developed to satisfy the assumptions made in the theory. The algorithm outperforms reasonable baselines and ablation studies.