  Stochastic games generalize Markov decision processes (MDPs) to a multiagent
setting by allowing the state transitions to depend jointly on all player
actions, and having rewards determined by multiplayer matrix games at each
state. We consider the problem of computing Nash equilibria in stochastic
games, the analogue of planning in MDPs. We begin by providing a generalization
of finite-horizon value iteration that computes a Nash strategy for each player
in generalsum stochastic games. The algorithm takes an arbitrary Nash selection
function as input, which allows the translation of local choices between
multiple Nash equilibria into the selection of a single global Nash
equilibrium.
  Our main technical result is an algorithm for computing near-Nash equilibria
in large or infinite state spaces. This algorithm builds on our finite-horizon
value iteration algorithm, and adapts the sparse sampling methods of Kearns,
Mansour and Ng (1999) to stochastic games. We conclude by descrbing a
counterexample showing that infinite-horizon discounted value iteration, which
was shown by shaplely to converge in the zero-sum case (a result we give extend
slightly here), does not converge in the general-sum case.
