Regret Transfer and Parameter Optimization

Noam Brown, Tuomas Sandholm

Solving massive, incomplete-information games like No-Limit Texas Hold'em is a monumental computational challenge. To make these games tractable, researchers typically employ action abstraction, which involves reducing a continuous range of choices (e.g., any bet between $1 and $1,000) into a few discrete options. However, selecting the "right" discrete actions has historically relied on human intuition or expensive trial-and-error. This paper introduces a principled method to automate this process by "warm-starting" learning algorithms and optimizing game parameters simultaneously with the equilibrium solution.

Regret Transfer: The Power of Scaling

The core innovation lies in Regret Transfer. In algorithms like Counterfactual Regret Minimization (CFR), agents learn by tracking "regret"—a measure of how much better they could have performed by choosing different actions. The authors demonstrate that when a game's payoffs change slightly (for instance, adjusting a bet size), the accumulated regrets can be transferred to the new setting.

Crucially, the authors prove that naive transfer—simply copying regrets—can actually hinder long-term convergence. Instead, they propose discounting (scaling down) the old regrets based on the magnitude of the payoff change. This provides a theoretically grounded "warm start" that maintains convergence guarantees.

Exploitability convergence comparing no transfer, naive transfer, and scaled transfer.

As shown in the figure above, "Transfer with scaling" maintains a lower total exploitability throughout the iterations compared to both "No transfer" and the "Transfer, no scaling" approach, which eventually converges slower than the baseline.

Simultaneous Parameter Optimization

Building on Regret Transfer, the researchers developed a custom gradient descent algorithm. Instead of solving a game from scratch for every parameter update, the algorithm estimates the gradient of the game's value by running a few iterations of regret matching at nearby parameter points. By transferring information from previous steps, the total complexity of finding a locally optimal parameter and an equilibrium is reduced from $\Theta(s^2)$ to $O(s\sqrt{s})$.

In some scenarios, payoffs are linear functions of parameters. By storing regrets as functions (e.g., $R(\theta) = \alpha\theta + \beta$), the algorithm can "replay" thousands of previous iterations in constant time when parameters change, further accelerating the optimization.

Key Results and Empirical Validation

The approach was tested on Leduc Hold’em and No-Limit Texas Hold’em. In Leduc Hold'em, the warm-start method provided a head start equivalent to approximately 125,000 iterations of standard CFR.

In the more complex No-Limit Texas Hold'em environment, the algorithm was tasked with optimizing the first-action raise amount. Regardless of the initial starting point (ranging from 0.5x to 2.0x the pot), all runs converged to a raise size of approximately 0.77x pot.

Bet size optimization in No-Limit Texas Hold'em, showing convergence to a consistent value.

This result was later verified via brute-force search to be the highest-payoff option, confirming the algorithm's ability to find optimal parameters in large-scale, real-world games.

Limitations and Future Directions

While powerful, the method has limitations. The gradient descent approach finds locally optimal parameters, which might not be the global optimum in non-convex landscapes. Additionally, storing regrets as functions to enable $O(1)$ replay increases memory overhead, which can be a bottleneck for massive game trees. Finally, the theory assumes payoffs are Lipschitz continuous with respect to parameters, a condition that might not hold for all game modifications. Despite these challenges, this work marks a significant shift from manual action abstraction to an automated, algorithmic process with strong theoretical foundations.

Summary updated

Abstract

Regret matching is a widely-used algorithm for learning how to act. We begin by proving that regrets on actions in one setting (game) can be transferred to warm start the regrets for solving a different setting with same structure but different payoffs that can be written as a function of parameters. We prove how this can be done by carefully discounting the prior regrets. This provides, to our knowledge, the first principled warm-starting method for no-regret learning. It also extends to warm-starting the widely-adopted counterfactual regret minimization (CFR) algorithm for large incomplete-information games; we show this experimentally as well. We then study optimizing a parameter vector for a player in a two-player zero-sum game (e.g., optimizing bet sizes to use in poker). We propose a custom gradient descent algorithm that provably finds a locally optimal parameter vector while leveraging our warm-start theory to significantly save regret-matching iterations at each step. It optimizes the parameter vector while simultaneously finding an equilibrium. We present experiments in no-limit Leduc Hold'em and nolimit Texas Hold'em to optimize bet sizing. This amounts to the first action abstraction algorithm (algorithm for selecting a small number of discrete actions to use from a continuum of actions--a key preprocessing step for solving large games using current equilibrium-finding algorithms) with convergence guarantees for extensive-form games.
BibTeX
@inproceedings{brown2014regret,
  author = {Noam Brown and Tuomas Sandholm},
  title = {{Regret Transfer and Parameter Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8832},
}
Figure