Bounds for Approximate Regret-Matching Algorithms
  A dominant approach to solving large imperfect-information games is
Counterfactural Regret Minimization (CFR). In CFR, many regret minimization
problems are combined to solve the game. For very large games, abstraction is
typically needed to render CFR tractable. Abstractions are often manually
tuned, possibly removing important strategic differences in the full game and
harming performance. Function approximation provides a natural solution to
finding good abstractions to approximate the full game. A common approach to
incorporating function approximation is to learn the inputs needed for a regret
minimizing algorithm, allowing for generalization across many regret
minimization problems. This paper gives regret bounds when a regret minimizing
algorithm uses estimates instead of true values. This form of analysis is the
first to generalize to a larger class of $(\Phi, f)$-regret matching
algorithms, and includes different forms of regret such as swap, internal, and
external regret. We demonstrate how these results give a slightly tighter bound
for Regression Regret-Matching (RRM), and present a novel bound for combining
regression with Hedge.
