Regret Testing: A Simple Payoff-Based Procedure for Learning Nash Equilibrium

A learning rule is uncoupled if a player does not condition his strategy on the opponent's payoffs. It is radically uncoupled if the player does not condition his strategy on the opponent's actions or payoffs. We demonstrate a simple class of radically uncoupled learning rules, patterned after aspiration learning models, whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game.