  Monte-Carlo counterfactual regret minimization (MCCFR) is the
state-of-the-art algorithm for solving sequential games that are too large for
full tree traversals. It works by using gradient estimates that can be computed
via sampling. However, stochastic methods for sequential games have not been
investigated extensively beyond MCCFR. In this paper we develop a new framework
for developing stochastic regret minimization methods. This framework allows us
to use any regret-minimization algorithm, coupled with any gradient estimator.
The MCCFR algorithm can be analyzed as a special case of our framework, and
this analysis leads to significantly-stronger theoretical on convergence, while
simultaneously yielding a simplified proof. Our framework allows us to
instantiate several new stochastic methods for solving sequential games. We
show extensive experiments on three games, where some variants of our methods
outperform MCCFR.
