Title: ACCELERATED VALUE ITERATION VIA ANDERSON MIXING

Abstract: Acceleration for reinforcement learning methods is an important and challenging theme. We introduce the Anderson acceleration technique into the value iteration, developing an accelerated value iteration algorithm that we call Anderson Accelerated Value Iteration (A2VI). We further apply our method to the Deep Q-learning algorithm, resulting in the Deep Anderson Accelerated Q-learning (DA2Q) algorithm. Our approach can be viewed as an approximation of the policy evaluation by interpolating on historical data. A2VI is more efficient than the modified policy iteration, which is a classical approximate method for policy evaluation. We give theoretical analysis of our algorithm and conduct experiments on both toy problems and Atari games. Both the theoretical and empirical results show the effectiveness of our algorithm.

1. INTRODUCTION:

In reinforcement learning (Sutton & Barto, 1998) , an agent seeks for the optimal policy in a specific sequential decision problem. Several algorithms have been proposed over the course of time, including the famous Q-learning (Watkins & Dayan, 1992) , SARSA (Rummery & Niranjan, 1994; Sutton & Barto, 1998) , and policy gradient methods (Sutton et al., 2000) . In complicated decision problems where tabular representations are intractable, function approximations are usually used for estimating state-action values (Kaelbling et al., 1996; Sutton & Barto, 1998; Sutton et al., 2000) . Inspired by the success of deep learning, Deep Q-Learning (DQN) (Mnih et al., 2013) and its variants (Bellemare et al., 2017; Schaul et al., 2015; Van Hasselt et al., 2016; Wang et al., 2015) utilize a deep neural network as the value approximator, which has successfully solved end-to-end decision problems such as Atari2000.

The value iteration (VI) Bellman (1957) and policy iteration (PI) (Howard, 1964) are the most classical methods for value updating. The main difference between them is that PI evaluate the current policy accurately during the iteration while VI does not. Thanks to the accurate evaluation of the current policy, policy iteration uses significantly less policy improvement steps to converge to the optimal value. Although PI has a faster convergence rate than VI, most of the existing methods employ a rather slow value iteration procedure, because thoroughly evaluating a policy is costly or even intractable under complex environments. To retain the fast convergence property of policy iteration while reducing its computation overhead, researchers have proposed several modifications to the original policy iteration (Alla et al., 2015; Puterman, 1994) . The modified policy iteration (MPI) method (Puterman, 1994) tries to deal with this problem by approximating the solution to policy evaluation via the truncated Neumann expansion of an inverse matrix. However, this approximation requires extra iterative steps, which is still computationally inefficient for complex decision problems where sampling is costly, compared with the value iteration procedure where the policy iteration step is skipped.

Interpolation methods have been widely used in first order optimization problems (Bubeck et al., 2015; Scieur et al., 2016; 2017; Xie et al., 2018) . These methods extract information from historical data and are proven to converge faster than vanilla gradient methods. However, the interpolation method is not widely applied in reinforcement learning. The most recent work related to interpolation is the averaged-DQN (Anschel et al., 2016) , which calculates the average Q-value over the history and demonstrated that such an operation is effective for variance reduction.

Acceleration in value iteration and policy iteration has attracted researchers' great attention. Classical methods for accelerating value iteration include Gauss-Seidel value iteration (Puterman, 1994) and Jacobi value iteration (JAC) (Puterman, 1994) . More recently, Alla et al. (2015) proposed an acceleration method that switches between a coarse-mesh value iteration and a fine-mesh policy iteration during different stages. Laurini et al. (2016) performed a Jacobi-like acceleration method on dynamic programming problems. In a recent work (Laurini et al., 2017) , the value iteration procedure is accelerated by only updating a part of the values. None of the previous methods have proposed acceleration methods with an application of interpolation.

In this paper, to solve the policy evaluation problem more efficiently, we propose an alternative algorithm based on multi-step interpolation. Explicitly, the solution to the policy evaluation problem is approximately represented by a weighted combination of historical values, whose weights are adaptively updated by an optimization procedure. To reduce the computational complexity, we resort to the Anderson mixing method (Anderson, 1965; Walker & Ni, 2011; Toth & Kelley, 2015) to do the approximation with only a short length of history. Our approach fits the gap between value iteration and policy iteration, ending in an updating rule without adding much extra computational complexity to the original value iteration procedure. We also extend this approach to deep reinforcement learning problems.

The remainder of this paper is organized as follows. In Section 2, we introduce the foundations of reinforcement learning and present typical value updating algorithms. In Section 3, we derive the Anderson accelerated methods. In Section 4, we give a theoretical analysis of the convergence of our method. In Section 5, we test our method in different environments and empirically show the effectiveness of it. Finally, we conclude our work in Section 6.

2. PRELIMINARIES:

In this paper we mainly consider a finite-state and finite-action scenario in reinforcement learning. In this case, an Markov Decision Process (MDP) system is defined by a 5-tuple (S, A, P, r, γ), where S is a finite state space, A is a finite action space, P ∈ R (|S|×|A|)×|S| is the collection of state-to-state transition probabilities, r ∈ R |S|×|A| is the reward matrix, γ is the discount factor. A policy π ∈ A |S| is a vector of actions at each state. The transition matrix P π ∈ R |S|×|S| and reward vector r π ∈ R |S| under policy π are defined as P π (i, j) = P ((i, π(i)), j), r π (i) = r(i, π(i)). We further define the value v π ∈ R |S| and the Q-value q π ∈ R |S|×|A| under a given MDP and policy, where each element of v π and q π is defined as

v π (s) = E s0=s,st+1∼Pπ(st,...) ∞ t=0 γ t r π (s t ), q π (s, a) = r(s, a) + E s1∼P ((s,a),...),st+1∼Pπ(st,...) ∞ t=1 γ t r π (s t ).

We can verify that q π = r + γP v π . We define q π π ∈ R |S| by q π π (i) = q π (i, π(i)), and say a vector to be the maximum among a set if each entry of it is bigger than that of the other vectors. The values satisfy the Bellman equation:

v π = Γ π (v π ) = r π + γP π v π .

The policy π * = argmax π q π is called the optimal policy, whose value or Q-value is denoted as v * or q * . Note that v * satisfies the Bellman optimality equation

v * = Γ(v * ) = max π (r π + γP π v * ).

Therefore, finding the optimal policy is equivalent to finding the fixed point of the operator Γ(v).

2.1. FIXED POINT ITERATION METHODS:

Value iteration (VI) is the most widely used and best-understood algorithm for solving Markov decision problems. It solves the fixed point problem by iterating the following steps repeatedly,

v (t+1) = Γ(v (t) ) = max π (r π + γP π v (t) ).

An alternative solution is policy iteration (PI), which maintains both the value v (t) and the policy π (t) during each iteration. The procedure alternatively iterates the following two steps:

EQUATION

which can be directly computed by

EQUATION

• Policy improvement: Improve the current policy by

π (t+1) = argmax π (r π + γP π v (t) ).

Theoretical analysis has shown that VI enjoys a γ-linear convergence rate (i.e., v Puterman, 1994) , where K is some constant related with γ and the given MDP. Both VI and PI are model-based, because the greedy policy cannot be determined when r and P are unknown. The VI under q-notation is well-known as Q-learning (Watkins & Dayan, 1992) . We will analyze our method under v-notation, but our analysis also works under the corresponding q-notation.

(t) -v * ∞ ≤ γ v (t-1) - v * ∞ ), while PI converges much faster with v (t) -v * ∞ ≤ K v (t-1) -v * 2 ∞ (

The main difference between VI and PI is whether the current policy is fully evaluated. Though PI converges faster than VI, this advantage diminishes under several settings. In reinforcement learning, we can only access an oracle that returns the reward and next state given the current state and selected action. Under such a setting, each value iteration step can be performed by estimating Γ(v) through sampling. But the policy evaluation step based on equation (2) becomes intractable because it is quite time-consuming to compute (I -γP π (t) ) -1 . The modified policy iteration method (Puterman & Brumelle, 1978) partially solves the problem by setting v t ≈ (Γ π (t) ) mt (v (t-1) ) where m t is a (possibly large) integer related to t. However, this method requires to evaluate a series of values (Γ π (t) ) i (v (t-1) ) for i = 1, 2, . . . , m t , which is computationally inefficient.

3. ANDERSON ACCELERATED VALUE ITERATION:

Based on the observation that full policy evaluation accelerates convergence, we propose an approximate policy evaluation method. The method aims to approximately solve the policy evaluation problem, circumventing the matrix inversion and iterative procedures mentioned above.

We first utilize the linearity of equation ( 1), defining B π (v) = Γ π (v) -v and converting the problem into an equivalent form of solving the equation

B π (v) = 0. Suppose we have obtained a set of values B π (v 1 ), B π (v 2 ), . . . , B π (v k ) with respect to v 1 , v 2 , . . . , v k . Consider to find a set of weights α = (α 1 , α 2 , . . . , α k ) T , subject to k i=1 α i = 1, which satisfies that k i=1 α i B π (v i ) = 0.

Then the combination ṽ = k i=1 α i v i will satisfy the following relationship:

EQUATION

This relation implies ṽ can be viewed as an approximate solution to equation ( 1) provided the sampling estimations are accurate enough. However, this step needs to keep track of the previous values and recompute Γ π on all of them. To reduce the huge memory usage and computation, we choose v i from the recent history, i.e.,

v i = v (t-i) , i = 1, 2, . . . , k, and replace B π (t) (v (t-i) ) with the previously computed values B π (t-i) (v (t-i)

). This modification is based on the observation that the recent successive policies do not change sharply and therefore -i) ). This modification approximately solves the policy evaluation problem without model estimation or extra function evaluations.

B π (t-i) (v (t-i) ) ≈ B π (t) (v (t

Another critical issue is that we cannot guarantee the existence of α given that k is small, because the dimension of B π (v) is usually much higher than k. Inspired by the Anderson acceleration technique (Anderson, 1965; Ortega & Rheinboldt, 1970; Walker & Ni, 2011) , we instead look for a combination of

EQUATION

where

B (t) = (B π (t-1) (v (t-1) ), B π (t-2) (v (t-2) ), . . . , B π (t-k) (v (t-k) )), Ω = {α|1 T α = 1}

, Λ is an extra constraint on the values attainable by α. Typically, Λ can be chosen from the following forms:

• Total space, Λ tot = R k ; • Boxing constraint, Λ box = {α| -m1 ≤ α ≤ m1}; • Convex combination constraint, Λ cvx = {α|0 ≤ α ≤ 1}; • Extrapolation constraint, Λ exp = {α|α 1 ≥ 1, α i ≤ 0, i = 2, 3, . . . , k}.

When the 2 norm is used and Λ = Λ tot , the solution can be written explicitly as i) , the values will always locate in the subspace expanded by historical values v (t-1) , v (t-2) , . . . , v (t-k) . When the solution to equation (1) does not lie in such a subspace, there is no hope for convergence with application of such updating rule directly. To jump out of the subspace, we perform an extra value iteration step to this combination. Then we will get the updated value,

α (t) = [(B (t) ) B (t) ] -1 1/1 [(B (t) ) B (t) ] -1 1, whose derivation is placed in the appendix. Note that if we simply set v (t) = k i=1 α (t) i v (t-

v (t) = max π r π + γP π k i=1 α (t) i v (t-i) .

3.1. THE ALGORITHM:

Based on our previous discussion, we present the k-step Anderson Accelerated Value Iteration (A2VI) in Algorithm 1. In the first k steps, the value is updated according to the original VI. Otherwise, we perform an interpolation procedure, where the weights are attained from solving the problem (5). The original value iteration algorithm can be viewed as a special case of our algorithm with k = 1.

Algorithm 1 Anderson Accelerated Value Iteration (A2VI)

EQUATION

k ) by solving the optimization problem (5) 7:

v (t) = max π rπ + γPπ k i=1 α (t) i v (t-i) 8:

end if 9: end for 10:

π (T ) = argmax π (rπ + γPπv (T ) ) 11: return v (T ) , π (T )

Both Anderson Acceleration (AA) and A2VI have the same spirit of interpolating on historical data. However, A2VI does not straightforwardly apply AA to the Bellman optimality equation. Note that AA has the updating rule v t = α i B(v t-i ), while A2VI exchange the order of the operator sum and B(•) due to the motivation from equation (3). This exchange puts the nonsmooth operator max out of the affine combination, simplifying the theoretical analysis.

We present a geometric explanation on the iterative steps of VI, PI, A2VI under 1-dimensional case in Figure 1 . In value iteration, v (t) is attained by making a vertical line at (v (t-1) , 0), finding its intersection with the function line at (v (t-1) , B(v (t-1) )), then drawing a line with slope -1 through (v (t-1) , B(v (t-1) )) and finding its intersection with the horizon axis at (v (t) , 0); In policy iteration, v (t) is attained by first getting (v (t-1) , B(v (t-1) )) in the same way as value iteration, then calculating the tangent line through (v (t-1) , B(v (t-1) )) and finding its intersection with the horizon axis. In Anderson accelerated value iteration, each step is first performed in a similar style to policy iteration except that the tangent line is replaced with a secant line. Then a value iteration step is performed to get v (t) .

From the figure, we can see that VI only utilizes the current value of the Bellman residual, while PI is similar to Newton's method Puterman & Brumelle (1978) , utilizing the gradient information to achieve a faster convergence rate. Our method serves as an intermediate between them, each step of which is composed of an ordinary value iteration step and a secant step. In specific, the replacement of the tangent line to a secant line can be viewed as a quasi-Newton's method, which is shown computationally more efficient while keeping a fast convergence rate in several particular settings. Both PI and A2VI converge to the fixed point in a smaller number of steps than VI. Compared with PI, A2VI is more practical because it approximates the tangent line by a secant line, which circumvents the costly model estimation step.

3.2. EXTENSION TO MODEL-FREE LEARNING ALGORITHM:

We can rewrite our algorithm under q-notation, and get the Anderson Accelerated Q-Learning (A2Q) Algorithm shown in the appendix. Combined with the technique of deep learning, our method can be applied to end-to-end decision problems, resulting in the Deep Anderson Accelerated Q-Learning (DA2Q) Algorithm (Algorithm 2).

v * v1 v2 v3 v4 v5 v Bv r1 + ( P1 I)v r2 + ( P2 I)v r3 + ( P3 I)v

Value iteration

v1 v2 v3 v4 = v * v Bv r1 + ( P1 I)v r2 + ( P2 I)v r3 + ( P3 I)v Policy iteration v * v1 v2 v3 v4 v Bv r1 + ( P1 I)v r2 + ( P2 I)v r3 + ( P3 I)v Bv1 Bv2 Bv3

Anderson accelerated value iteration for t = 1, 2, . . . , T do 7:

With probability ε select a random action at, otherwise select at = arg maxa Q(st, a; θ) 8:

Execute action at, observe reward rt and state st+1 9:

Store transition (st, at, rt, st+1) in D 10:

Sample a random minibatch of transitions {(sj, aj, rj, s j )} b j=1 from D 11:

for j = 1, 2, . . . , b do

12: yj =        rj for terminal state rj + γ max a K k=1 α k Q(s j , a; θ -k )

for non-terminal state 13: end for 14:

L(θ) = 1 b b j=1 (yj -Q(sj, aj; θ)) 2 15: θ = θ -η ∂L ∂θ 16: s = s + 1 17: if s mod C = 0 then 18: Assign θ -k = θ -(k-1) for k = K, K -1, . . . , 2. Assign θ-1 = θ. 19: if s ≥ K(C -1) then 20:

Sample a random minibatch of transitions {(sj, aj, rj, s j )} B j=1 from D 21:

for j = 1, 2, . . . , B do 22:

for k = 1, 2, . . . , K do 23: (α1, α2, . . . , αK

d k j = rj -Q(sj, aj; θ -k ) for terminal state rj + γ max a Q(s j , a; θ -k ) -Q(sj

) = argmin (α 1 ,α 2 ,...,α K ) B j=1 ( K k=1 α k d k j ) 2 s.t. K k=1 α k = 1 28: end if 29:

end for 30: end for

4. THEORETICAL ANALYSIS:

We first analyze of the local convergence of the A2VI algorithm under boxing constraint. Our result shows that in a small neighborhood of the optimal value, our algorithm enjoys an exponential convergence rate.

Theorem 1. For any MDP with a unique optimal policy, there exists some δ > 0, such that for any initial value v (0) ∈ U δ (v * ) = {v| v -v * ∞ ≤ δ}, the A2VI algorithm under boxing constraint maintains the following properties:

(i) Γ(v (t) ) -v (t) ∞ ≤ γ Γ(v (t-1) ) -v (t-1) ∞ , ∀t = 1, 2, . . .; (ii) v (t) -v * ∞ ≤ γ t 1-γ Γ(v (0) ) -v (0) ∞ , ∀t = 1, 2, . . ..

Generally, it is difficult to obtain the global convergence rate of A2VI, since the operation max is nonsmooth.

To guarantee the convergence, we introduce a rejection step to the original algorithm. We say v is monotonic improving if Γ(v) ≥ v, and denote the set of such values as V B . We propose the A2VI algorithm with the rejection step, which only differs with Algorithm 1 at line 6. After calculating α (t) , we test whether the affine combination

k i=1 α (t) i v t-i lies in V B

. If the answer is negative, the interpolation step will be replaced with an ordinary value iteration step. We put the pseudocode of A2VI with the rejection step in Appendix. With this modification, we can have the following convergence properties. Theorem 2. For the A2VI algorithm with the rejection step with 1) , ∀t = 1, 2, . . . Theorem 3. For the A2VI algorithm with Λ = Λ exp , if v 0 ≥ 0 and v (0) ∈ V B , then we have

Λ = Λ cvx , if v (0) ∈ V B , then we have v (t) ∈ V B , Γ(v (t) ) -v (t) ≤ γ Γ(v (t-1) ) -v (t-

(a) Monotone improving values, v (t-1) ≤ v (t) ≤ v * , v (t) ∈ V B , ∀t = 1, 2, . . . (b) γ-linear convergence rate, v * -v (t) ∞ ≤ γ v * -v (t-1) ∞ .

5. EXPERIMENTS:

To validate the effectiveness of our method, we conduct several experiments.

5.1. EXPERIMENTS ON TOY MODELS:

We first test our method on three toy models. The first model is a randomly generated MDP with |S| = 100 and |A| = 50. The transition probabilities of the MDP are generated from a uniform distribution on [0, 1], and the rewards are generated from a standard normal distribution. The second model is the N -Chain problem with N = 100, where a reward of 0.1 is given at state 0 and a reward of 1 is given at state N . At each state, the agent can either choose to move forward or backward, and will move to the selected direction with probability 0.9 and to the opposite direction with probability 0.1. The last model is a 20 × 20 Gridworld model, where a reward of 1 is given at state (20, 20). At each state, the agent can choose one of the 4 directions and will move to that direction with probability 0.7, or move to one of the other directions with probability 0.1 for each. We perform the standard value iteration, policy iteration and Anderson accelerated value iteration with/without the rejection step on these models. In our experiment, each policy iteration step is approximately solved by the modified policy iteration method with 100 inner iterations. To compare our method with the averaged updating scheme (Anschel et al., 2016) , we further construct and compare our algorithm with the averaged value iteration. The value of v tv * w.r.t. step t is shown in Figure 2 , where the results are averaged from 30 independent experiments.

From the results we can see that the policy iteration converges fastest for all of the three models, however, since each of its steps includes 100 inner iterations, the actual computation cost is very high. Among value iteration methods, the Anderson accelerated value iteration converges fastest. The acceleration effect is remarkable in randomly generated MDPs, but A2VI slows down at the first few steps in the latter two experiments. However, adding a rejection step solves the problem and attains a faster convergence rate.

Another observation is that in the toy model case, the averaged value iteration cannot be used for acceleration. 

5.2. EXPERIMENTS ON ATARI GAMES WITH DEEP LEARNING BASED TECHNIQUES:

To figure out the performance of our method on complex environments, we apply our method to Atari games from Gym (Brockman et al., 2016) , which is a Python API to Arcade Learning Environment (Bellemare et al., 2013) . We compare DA2Q with DQN (Mnih et al., 2013) and Averaged-DQN (Anschel et al., 2016) . Details of the experiment settings are given in Appendix D.

As Figure 3 points out, our algorithm DA2Q obtains a significant improvement over both the original DQN algorithm and the Averaged DQN algorithm. When compared with other interpolation method such as Averaged-DQN, the overall performance of our method also tends to be stabler, always being superior than other methods among all of the three environments, while the performance of Averaged-DQN varies a lot. Compared with DQN, the extra computational cost is actually low, since the α is updated only once every C steps, which only involves an inversion on a very small-size matrix (k × k). The k target values are computed parallelly in the TensorFlow (Abadi et al., 2016) , which cost the same time as in DQN. Moreover, the extra runtime can be ignored when compared with the costly back propagations and interaction with environments.

6. CONCLUSION:

We have proposed the Anderson accelerated value iteration method, which is a novel acceleration approach for reinforcement learning. We have proved the convergence property of our method under certain conditions. Our algorithm empirically achieves a superior performance on toy models and several Atari games. Despite the success of our algorithm, several questions remain open. The convergence analysis for the general case is lacking, and we only provide convergence guarantees but do not give a theoretical analysis of the acceleration effect of A2VI, which we leave for future work.

APPENDIX:

A. A2Q

Here is the pseudocode of A2Q, which is A2VI in q-notation.

Algorithm 3 Anderson Accelerated Q-Learning (A2Q)

Input: q 0 , P, r, γ, k, T 1: for t = 1, 2, . . . , T do 2:

B π (t-1) (q t-1 ) = vec(r) + γP maxπ q t-1 π -vec(q t-1 ) 3: if t < k then 4:

vec(q t ) = vec(r) + γP maxπ q t-1 π 5: else 6:

Calculate (α1, α2, . . . , α k ) by solving the optimization problem (5) 7:

vec(q t ) = vec(r) + γP maxπ( k i=1 αiq t-i π ) 8:

end if 9: end for 10: π T = arg maxπ q T π 11: return q T , π T

B. A2VI WITH THE REJECTION STEP:

Here is the pseudocode of A2VI with the rejection step, the only difference between this algorithm with algorithm 1 is before the interpolation step, we first check whether the affine combination is in V B . If the answer is negative, then this interpolation step is replaced with an ordinary value iteration step.

Algorithm 4 Anderson Accelerated Value Iteration with the Rejection Step:

Input: v (0) , P, r, γ, k, T

EQUATION

k ) by solving the optimization problem (5)

7:

ṽ = k i=1 α (t) i v (t-i) 8:

if max π (r π + γP π ṽ) ≥ ṽ then 9:

EQUATION

i = 0 for i = 1

12:

v (t) = max π r π + γP π v (t-1)

13:

end if 14:

end if 15: end for 16: π (T ) = argmax π (r π + γP π v (T ) ) 17: return v (T ) , π (T ) C. PROOFS Lemma 1. For any MDP whose optimal policy is unique, there exists a δ > 0 and a policy π * such that for any

v ∈ U δ (v * ) = {v| v -v * ∞ ≤ δ}, Γ(v) = r π * + γP π * v

Proof Because the optimal policy is unique, for any nonoptimal policy π, for any state s such that π(s) = π * (s) we have that

[Γ π * (v * )] s > [Γ π (v * )] s , [•] s means executing operations on state s. Denote A(π) = {s|π(s) = π * (s)}.

Suppose the optimal policy is π * , then there exists ε such that

min π =π * min s∈A(π) [Γ(v * ) -Γ π (v * )] s > ε > 0,

since the optimal policy is unique and the state space and the action space are finite. We choose δ = ε 3γ , then for any policy π and any v ∈ U δ (v * ) we have

Γ π (v * ) -Γ π (v) ∞ = γP π (v * -v) ∞ ≤ γ v * -v ∞ ≤ ε 3

Then for any policy π, for any state s ∈ A(π) , we have that

[Γ π * (v) -Γ π (v)] s = [(Γ π * (v) -Γ π * (v * )) + (Γ π * (v * ) -Γ π (v * )) + (Γ π (v * ) -Γ π (v))] s ≥ ε -Γ π * (v) -Γ π * (v * ) ∞ -Γ π (v * ) -Γ π (v) ∞ ≥ ε - ε 3 - ε 3 = ε 3

which means π does not choose the optimal action in state s. Therefore, if π selects the optimal action in every state s ∈ S, then we must have π s = π * s , ∀s ∈ S, which implies π * ∈ arg max π Γ π (v), i.e., Γ(v) = r π * + γP π * v. Lemma 2. For any given MDP with optimal value v * and any value v, we always have

(1 -γ) v -v * ∞ ≤ Γ(v) -v ∞ ≤ (1 + γ) v -v * ∞ . Proof v -v * ∞ = v -Γ(v) + Γ(v) -Γ(v * ) ∞ ≤ v -Γ(v) ∞ + Γ(v) -Γ(v * ) ∞ ≤ v -Γ(v) ∞ + γ v -v * ∞ ⇒ (1 -γ) ∞ v -v * ∞ ≤ Γ(v) -v ∞ v -v * ∞ = v -Γ(v) + Γ(v) -Γ(v * ) ∞ ≥ v -Γ(v) ∞ -Γ(v) -Γ(v * ) ∞ ≥ v -Γ(v) ∞ -γ v -v * ∞ ⇒ (1 + γ) v -v * ∞ ≥ Γ(v) -v ∞

Proof of Theorem 1 From lemma 1 we know there exists a policy π and a δ > 0 such that the optimal Bellman operator is a linear function on U δ (v * ). We now set δ sufficiently small such that

km(1 + γ) 1 -γ v (0) -v * ∞ < km(1 + γ) 1 -γ δ < δ.

The result is trivial for the first k -1 steps, which are performed exactly by standard value iteration. When t > k, we prove the result by induction. Suppose the conclusion is correct for previous steps, then we have

k i=1 α (t) i v (t-i) -v * ∞ ≤ k i=1 |α (t) i | v (t-i) -v * ∞ ≤ k i=1 |α (t) i | 1 1 -γ B(v (t-i) ) ∞ ≤ k i=1 |α (t) i | 1 1 -γ B(v (0) ) ∞ ≤ km 1 -γ B(v (0) ) ∞ ≤ km(1 + γ) 1 -γ v (0) -v * ∞ < km(1 + γ) 1 -γ δ < δ It follows that v (t) -v * ∞ = Γ( k i=1 α (t) i v t-i ) -Γ(v * ) ∞ ≤ γ k i=1 α (t) i v (t-i) -v * ∞ ≤ k i=1 α (t) i v (t-i) -v * ∞ < δ Therefore, k i=1 α (t) i v (t-i) ∈ U δ (v * ), v (t) ∈ U δ (v * ), which implies Γ( k i=1 α (t) i v (t-i) ) = r π * + γP π * k i=1 α (t) i v (t-i) , Γ(v (t) ) = r π * + γP π * v (t) .

Then we can get

B(v t ) = r π * + (γP π * -I)v (t) = r π * + (γP π * -I)(r π * + γP π * k i=1 α (t) i v (t-i) ) = k i=1 α (t) i r π * + (γP π * -I)(r π * + γP π * v (t-i) ) = k i=1 α (t) i γP π * r π * + γP π * v (t-i) -v (t-i) = γP π * k i=1 α (t) i B(v (t-i) )

Taking norm on both side of the equation and utilizing the definition of α

(t) i , i = 1, 2, • • • , k, we get Γ(v (t) ) -v (t) ∞ ≤ γ P π * ∞ k i=1 α (t) i B(v (t-i) ) ∞ ≤ γ B(v (t-1) ) ∞ = γ Γ(v (t-1) ) -v (t-1) ∞ .

Therefore, we justify property (i). Property (ii) then follows directly from Lemma 2. Lemma 3. For any MDP, suppose the values u and v satisfy u ≥ v, then

Γ(u) ≥ Γ(v).

Proof As stated in section 2, u ≥ v means that u(s) ≥ v(s) for any state s. Suppose π = arg max π r π + γP π v, therefore for any s we have that

Γ(u)(s) ≥ Γ π (u)(s) ≥ Γ π (v)(s) = Γ(v)(s).

Proof of Theorem 2 On the one hand,

Γ(v (t) ) -v (t) = max π (r π + γP π v (t) ) -max π (r π + γP π k i=1 α (t) i v (t-i) ) ≤ r π (t) + γP π (t) v (t) -r π (t) -γP π (t) k i=1 α (t) i v (t-i) = γP π (t) (max π (r π + γP π k i=1 α (t) i v (t-i) ) - k i=1 α (t) i v (t-i) ) ≤ γP π (t) k i=1 α (t) i (max π (r π + γP π v (t-i) ) -v (t-i) ) = γP π (t) k i=1 α (t) i B(v (t-i) )

On the other hand, we denote π = argmax π

(r π + γP π k i=1 α (t) i v (t-i) ), then v (t) -Γ(v (t) ) = max π (r π + γP π k i=1 α (t) i v (t-i) ) -max π (r π + γP π v (t) ) ≤ r π + γP π (k) i=1 α (t) i v (t-i) -r π -γP π v (t) = γP π ( k i=1 α (t) i v (t-i) -max π (r π + γP π k i=1 α (t) i v (t-i) )) = -γP π B( k i=1 α (t) i v (t-i) )

The above two results shows

γP π B( k i=1 α (t) i v (t-i) ) ≤ B(v (t) ) ≤ γP π (t) k i=1 α (t) i B(v (t-i) ). Now, consider the rejection step. First we show that if v ∈ V B then Γ(v) ∈ V B . If v ∈ V B , then Γ(v) ≥ v. With Lemma 3, we have that Γ(Γ(v)) ≥ Γ(v), i.e. Γ(v) ∈ V B .

Next we show that if v (i) ∈ V B for i < t, then v (t) ∈ V B . According to the rejection algorithm, we have

v (t) = Γ( k i=1 α (t) i v (t-i) ). If Γ( k i=1 α (t) i v (t-i) ) ≥ k i=1 α (t) i v (t-i) , then k i=1 α (t) i v (t-i) ∈ V B and v (t) ∈ V B . If Γ( k i=1 α (t) i v (t-i) ) < k i=1 α (t) i v (t-i) , then v (t) = Γ(v (t-1) ) due to the rejection step. Since v (t-1) ∈ V B , we have that v (t) ∈ V B . Therefore, we also have that B( k i=1 α (k) i v (t-i) ) ≥ 0. We have that Γ(v (t) ) -v t = B(v (t) ) ≤ γ P π (t) k i=1 α (t) i B(v (t-i) ) ≤ γ B(v (t-1) ) = γ Γ(v (t-1) ) -v (t-1)

The second inequality is due to the definition of α (t) i , i = 1, 2, ..., k.

Proof of Theorem 3:

We prove the conclusion by induction. It is evident that the conclusion holds for the first k -1 steps. Suppose the conclusion holds for the first t -1 steps, then

v (t) = max π (r π + γP π k i=1 α (t) i v (t-i) ) ≥ r π + γP π ( k i=1 α (t) i v (t-i) ) ≥ r π + γP π v (t-1)

≥ v (t-1) , where π = arg max π r π + γP π v (t-1) . The second inequality comes from the extrapolation restriction. The Third inequality is due to that if v ∈ V B then Γ(v) ∈ V B , which is shown in Theorem 2.

As shown in Theorem 2, we have that v (t) ∈ V B and k i=1 α

(t) i v (t-i) ∈ V B . Therefore, v (t) ≤ v * . v * -v (t) = v * -max π (r π + γP π k i=1 α (t) i v (t-i) ) ≤ v * -(r π * + γP π * k i=1 α (t) i v (t-i) ) = γP π * k i=1 α (t) i (v * -v (t-i) ) ≤ γP π * (v * -v (t-1) )

Taking the infinite norm on both sides, we get

v * -v (t) ∞ ≤ γ P π * ∞ v * -v (t-1) ∞ ≤ γ v * -v (t-1)

∞ , which completes the proof.

D. EXPERIMENT DETAILS D.1 MODEL ARCHITECTURE AND HYPER-PARAMETERS:

For our experiments, we used the DQN (Mnih et al., 2013) architecture, where the Q-value network is composed of 3 convolutional layers, 1 fully connected layer, and 1 output fully connected layer. Each layer except the final layer is followed with a rectified linear activation(ReLU). The first convolutional layer use 32 8 × 8 filters with stride 4, the second has 64 4 × 4 filters with stride 2, and the third convolutional layer has 64 3 × 3 filters with stride 1. The fully connected layer consists of 512 units and the final layer outputs a single value for each action. We used the Adam optimizer with learning rate 0.0001 and = 0.0015. The discount was set to γ = 0.99. Training is done over 20M or 40M frames. We updated the target networks every 10000 steps. The size of experience replay buffer is 100000 tuples, where 32 mini batches were sampled every 4 steps to update the network. The exploration policy is ε-greedy policy with fixed ε = 0.01.

D.2 PREPROCESSING OF ENVIRONMENTS:

We preprocess the environment in the same way as the original DQN paper (Mnih et al., 2013) does. We utilize the action repeat technique, i.e., each action is repeated for the next four consecutive frames. The frames are firstly grey-scaled and then rescaled to the size of 84 × 84 pixels. Each state is represented by a concatenation of 4 consecutive frames. We fix all positive rewards to be 1 and all negative rewards to be -1, leaving 0 rewards unchanged. Transitions associated with the loss of a life are considered terminal. This problem can be directly solved with an application of Lagrange multiplier method, namely, let λ be the Lagrange multiplier, then we solve the problem max α α ( B(t) ) B(t) α + λ(1 α -1) whose solution can be written explicitly as α = -λ 2 [( B(t) ) B(t) ] -1 1. Combine this result with the constraint, we can get -λ 2 =

1 1 [( B(t) ) B(t) ] -1 1 , which implies α = [( B(t) ) B(t) ] -1 1 1 [( B(t) ) B(t) ] -1 1 .

:



Figures and Tables:

Figure 1: Geometric interpolation of VI, PI and A2VI.

Figure 2: Experiment results on several toy models.

Figure 3: Training Performance on Atari games, score is smoothed with 250 windows while the shaded area is the 0.25 standard deviation.

E. SOLVING (5) WHEN USING THE 2 NORM AND TOTAL SPACE CONSTRAINTUnder the given setting, we may rewrite the original problem in the following form, minimize α ( B(t) ) B(t) α subject to 1 α = 1.

Peer review (iclr2019):
 This is a very well-written paper which proposed a way to accelerate the value-iteration of MDP. The method is the so-called "Anderson-Mixing" method. It replaces the policy evaluation step by solving a smaller linear equation: find a linear combination of a few historical values to represent the value of the current policy. The paper also presents a very nice explanation of why such a modification of VI accelerates VI. The paper also extends the method to DQN and shows a very nice acceleration. The experiments are convincing and interesting. I only have two concerns: 1) In section 4, the convergence proof is shown but the contraction is only gamma. This is the same as the original VI. Of course, this is the worst case best bound. Is it possible to show a result that the modified-VI is always better than the original VI? 2) In section 4, the dependence on k has not been studied. But k actually critically affects the time complexity. Is it possible to obtain convergence proof depending on k?