A learning rule almost too simple to be true: keep a running tally of how much better each other move would have done, and next round pick a move with probability proportional to that regret. No model of the opponent, no equilibrium solving — pure hindsight. Yet Hart and Mas-Colell proved the time-average of such play converges to the correlated-equilibrium set. Down the center the terms go in, the players learn, and the joint distribution comes out. Blue builds and defends it; red tries to break it.
source S. Hart & A. Mas-Colell, A Simple Adaptive Procedure Leading to Correlated Equilibrium, Econometrica 68(5), 2000, pp. 1127–1150 — doi:10.1111/1468-0262.00153. Rendered, not quoted.
Each player keeps, for every ordered pair of its own actions j→k, the average regret: how much more it would have scored, per period, had it swapped every past play of j for k (opponent held fixed).
Let R(j,k)⁺ be the positive part of that average. If the player just played j, next action is drawn:
p(k) = R(j,k)⁺ / μ · p(j) = 1 − Σₖ p(k)
μ is a fixed normaliser (here ·) large enough that this is always a genuine distribution — the leftover mass keeps you where you are. Live regrets for the current run:
| player | own act | max R⁺ |
|---|
the-bandit's no-regret idea — do not converge to the best arm, just never regret your average against any fixed arm — placed inside a game, where the "arm" payoffs are set by other learners moving at the same time.
Run it on both sides and the empirical joint play lands in a-the-correlated-equilibrium: local, myopic, per-player learning whose long-run average is a global object no one computed. This is the engine — as counterfactual regret (CFR) — behind superhuman poker bots. Each sphere is the next one's premise.
The blue team's live check: re-run the learner to a fixed horizon and confirm the max average positive regret has fallen below the no-regret bound. If red flips the sign, this badge is where it shows.
Two players, three actions each (A B C), repeated. The payoff bimatrix is Shapley's game (1964) — the classic where naïve best-response chasing never settles, so any convergence must come from the averaging, not the play.
| u₁ / u₂ | A | B | C |
|---|---|---|---|
| A | 1 / 0 | 0 / 0 | 0 / 1 |
| B | 0 / 1 | 1 / 0 | 0 / 0 |
| C | 0 / 0 | 0 / 1 | 1 / 1 |
Row = player 1's action, column = player 2's. Best responses chase each other around a cycle — no pure equilibrium, and fictitious play orbits forever. That cycle is exactly what you feed the panel below.
Matching on positive regret — the honest rule. Regret shrinks, play averages into the correlated-equilibrium set.
| 1↓ 2→ | A | B | C |
|---|
Every number is computed live from the fixed-seed run — the regret gauge and the joint table are the actual simulation, never looked up.
What the machine produces, proven: the maximum average positive regret falls toward 0 as T grows (no-regret), and the empirical joint distribution's correlated-equilibrium incentive violations shrink with it — no player, looking back, wishes it had swapped any action for another. At T=200 max regret is ≈ 0.27; by T=20 000 it is ≈ 0.03, and it keeps falling.
The blue team's witness (left) confirms the bound live; the red team (right) flips the sign to make it fail.
It also needs the counterfactual payoff of every unplayed action each round — full observation of the opponent's move. Take that away and you are in bandit territory, where convergence is slower and the internal-regret version needs more machinery. Rate is roughly 1/√T: honest, but not fast.
"Regret matching converges to a Nash equilibrium." Cut. It converges to the correlated-equilibrium set — strictly weaker, and generally not a product of independent mixed strategies.
"The players' strategies converge." Cut. The empirical distribution converges; the round-to-round mixed strategies need not settle at all.
"This is the exact poker-bot algorithm." Kept, corrected. Poker uses counterfactual regret minimisation (CFR) — the same no-regret spine, lifted to per-information-set regret in an extensive-form tree.
The red team's move: flip the rule to match on negative regret — chase the actions that did worst in hindsight. The blue team's witness (window 7) is watching.
Chase the worst move and the average regret stops falling — it locks near its maximum, the empirical play collapses out of the equilibrium set, and the witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.