# Bounds for Approximate Regret-Matching Algorithms

arXiv: https://arxiv.org/abs/1910.01706 · HTML: https://mlsanity.com/paper/1910.01706/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2019.

## Built on by (most cited first, 1 of 1)

- [CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedules](https://mlsanity.com/paper/2608.14761/) (2026)

## Abstract (arXiv)

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.