  Optimal policies in standard MDPs can be obtained using either value
iteration or policy iteration. However, in the case of zero-sum Markov games,
there is no efficient policy iteration algorithm; e.g., it has been shown that
one has to solve Omega(1/(1-alpha)) MDPs, where alpha is the discount factor,
to implement the only known convergent version of policy iteration. Another
algorithm, called naive policy iteration, is easy to implement but is only
provably convergent under very restrictive assumptions. Prior attempts to fix
naive policy iteration algorithm have several limitations. Here, we show that a
simple variant of naive policy iteration for games converges exponentially
fast. The only addition we propose to naive policy iteration is the use of
lookahead policies, which are anyway used in practical algorithms. We further
show that lookahead can be implemented efficiently in the function
approximation setting of linear Markov games, which are the counterpart of the
much-studied linear MDPs. We illustrate the application of our algorithm by
providing bounds for policy-based RL (reinforcement learning) algorithms. We
extend the results to the function approximation setting.
