Abstract Computing a Nash equilibrium in multiplayer stochastic games is a notoriously diffificult problem. Prior algorithms have been proven to converge in extremely limited settings and have only been tested on small problems. In contrast, we recently presented an algorithm for computing approximate jam/fold equilibrium strategies in a three-player nolimit Texas hold’em tournament—a very large realworld stochastic game of imperfect information [5]. In this paper we show that it is possible for that algorithm to converge to a non-equilibrium strategy profifile. However, we develop an ex post procedure that determines exactly how much each player can gain by deviating from his strategy and confifirm that the strategies computed in that paper actually do constitute an -equilibrium for a very small  (0.5% of the tournament entry fee). Next, we develop several new algorithms for computing a Nash equilibrium in multiplayer stochastic games (with perfect or imperfect information) which can provably never converge to a non-equilibrium. Experiments show that one of these algorithms outperforms the original algorithm on the same poker tournament. In short, we present the fifirst algorithms for provably computing an -equilibrium of a large stochastic game for small . Finally, we present an effificient algorithm that minimizes external regret in both the perfect and imperfect information cases