Equivalence Analysis between Counterfactual Regret Minimization and
  Online Mirror Descent
  Follow-the-Regularized-Lead (FTRL) and Online Mirror Descent (OMD) are regret
minimization algorithms for Online Convex Optimization (OCO), they are
mathematically elegant but less practical in solving Extensive-Form Games
(EFGs). Counterfactual Regret Minimization (CFR) is a technique for
approximating Nash equilibria in EFGs. CFR and its variants have a fast
convergence rate in practice, but their theoretical results are not
satisfactory. In recent years, researchers have been trying to link CFRs with
OCO algorithms, which may provide new theoretical results and inspire new
algorithms. However, existing analysis is restricted to local decision points.
In this paper, we show that CFRs with Regret Matching and Regret Matching+ are
equivalent to special cases of FTRL and OMD, respectively. According to these
equivalences, a new FTRL and a new OMD algorithm, which can be considered as
extensions of vanilla CFR and CFR+, are derived. The experimental results show
that the two variants converge faster than conventional FTRL and OMD, even
faster than vanilla CFR and CFR+ in some EFGs.
