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.
This paper introduces the "Anderson mixing" ideas from the broader literature on general fixed-point problems to the specific problem of finding the fixed-point to the Bellman optimality equations for a Markov Decision Processes. The general idea is to summarizes the history of previous iterates (value functions in this case) by finding of convex combination which also minimizes the residuals. The authors provide a solution for when an iterate is no longer representable by a convex combination of the recent history by simply bypassing the interpolation step and replacing it with a usual value iteration step. Using the intuition developed in the MDP case, they then adapt their DP algorithms to the learning case by substituting exact (tabular) value functions with deep function approximators. Experimental results are presented in 3 games from the ALE environment.
The jump from the DP formulation to the learning case is rather abrupt, and lacks sufficient motivation. The way the paper is currently structured is 50-50: 50% of the contribution is the DP view of the proposed method while the remaining half comes from the deep formulation (and experiments). I think that I would have preferred to see the entire paper being dedicated to the DP point of view, followed by a more principled Approximate DP analysis in the simpler linear case. Dedicating the remaining of the paper to the deep formulation almost feels like a missed opportunity to fully developing the theory initiated in the first section. But then of course the price to pay would be a paper which would be less aligned with the "representation learning" aspect of the conference. My main concern is that extending this technique to the deep setting mare involve some serious interference with other mechanisms already at play. It is very difficult to explain if the observed improvement come from the underlying DP basis or as a secondary effect of architectural and algorithmic considerations. 
To my knowledge, this is the first attempt at using Anderson mixing in the MDP framework. However, I would appreciate if the authors could survey previous attempts (if any) by other authors, or more generally existing results in the literature on non-linear fixed-point methods.  You may find relevant work by consulting the recent Zhang, O’Donoghue and Boyd paper (2018). 
# Detailed comments
> Puterman 2014
The 2014 edition is likely to be a re-print of the 1994 which is commonly cited. I would double-check to see if there is any difference in the content between the 2014 and 1994 edition. If not (and just a re-print) I would cite the 1994 edition which is more widely recognized. 
> Citations for VI and PI
You should cite Bellman 1957 and Howard 1961 (not Puterman). For exact references, see bibliographical remarks in Puterman. 
> Citation for Modified policy iteration
Please cite original paper(s) by Puterman and Brumelle ~1978. See bibliographical remarks in Puterman 1994 (or 2014) for the origins of MPI. 
>  via the Neumann expansion
truncated
> computationally inefficient for complex decision problems
Compared to what? More efficient than full PI for sure
> Page 2, notation for $\Gamma_\pi$ vs $\Gamma$
I suggest using a different notation for the (linear) policy evaluation operator vs the Bellman optimality one. The subscript "_\pi$ is easy to miss. 
> converges much faster with K
Define K
> In most cases, we can
In reinforcement learning, we can
> value iteration can be finished
Finished ? 
> value iteration can be finished by estimating Γ(v) through sampling.
We are no longer in the realm of DP, but more stochastic approximation methods. This isn't quite VI anymore. I would be more careful when jumping from one setting to the other.
> provided the sampling estimations are accurate enough
The approach described so far does not involve any sampling. 
> This modification is based on the observation that the recent successive policies do not
So far, the mixing equations (3) and (4) only describe the evaluation case. You haven't mentioned yet how you plan to combine this into a more general control algorithm where successive (changing) policies are generated.
> the solution can be written explicitly as
Please cite where this comes from (or provide proof inline or appendix)
> while PI is similar to Newton’s method
Cite Puterman and Brumelle for the original work on showing the connection between PI and Newton's method. 
> except that the tangent line is replaced with a secant line.
Please explain this intuition: how you obtain this geometric interpretation.
Also, the secant method being an analogue to quasi-Newton methods, and policy iteration being Newton's method, there is an opportunity to better develop and explain those parallels.