Bounds for Approximate Regret-Matching Algorithms
This work addresses the problem of improving scalability and performance in large imperfect-information games like those solved with Counterfactual Regret Minimization, offering incremental theoretical advances for researchers in game theory and machine learning.
The paper provides regret bounds for approximate regret-matching algorithms when using estimated values instead of true ones, generalizing to a class of (Φ, f)-regret matching algorithms and including forms like swap, internal, and external regret, with a slightly tighter bound for Regression Regret-Matching and a novel bound for combining regression with Hedge.
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 $(Φ, 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.