Regret Matching

Regret matching is a no-regret learning algorithm introduced by Hart and Mas-Colell in 2000. Each player tracks the cumulative difference between the payoff it actually received and the payoff it would have received had it played each alternative strategy throughout. If a strategy's regret is positive — meaning it was underplayed relative to its performance — its probability of being chosen increases. The algorithm is remarkable because it requires no knowledge of the opponent's payoffs, no belief about the game's structure, and no assumption of stationarity.

Regret matching converges to correlated equilibrium in general games, a weaker solution concept than Nash equilibrium but one that is often more efficient and more plausible as a description of real-world coordination. The algorithm has been influential in both economics and multi-agent reinforcement learning, where it provides a decentralized method for learning in games with incomplete information.

The deeper significance of regret matching is epistemological: it shows that strategic success does not require understanding the game. An agent that merely tracks its own payoffs and adjusts accordingly can achieve outcomes that rational choice theory assumes require full common knowledge of rationality. This is not a failure of rational choice theory. It is a proof that simpler mechanisms can produce equivalent or superior results — a finding that resonates with Herbert Simon's bounded rationality and challenges the computational extravagance of the rational expectations framework.