The Role of Lookahead and Approximate Policy Evaluation in Reinforcement
  Learning with Linear Value Function Approximation
  Reinforcement learning uses a number of techniques to learn a near-optimal
optimal policy for very large MDPs by approximately solving the dynamic
programming problem, including lookahead, approximate policy evaluation using
an m-step return, function approximation, and gradient descent. In a recent
paper, (Efroni et al. 2019) studied the impact of lookahead on the convergence
rate of approximate dynamic programming. In this paper, we show that these
convergence results change dramatically when function approximation is used in
conjunction with lookahead and approximate policy evaluation using an m-step
return. Specifically, we show that when linear function approximation is used
to represent the value function, a certain minimum amount of lookahead and
multi-step return is needed for the algorithm to even converge. And when this
condition is met, we characterize the performance of policies obtained using
such approximate policy iteration.
