Regret testing: learning to play Nash equilibrium without knowing you have an opponent

Foster, Dean P.; Young, H. Peyton Article Regret testing: learning to play Nash equilibrium without knowing you have an opponent Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Foster, Dean P.; Young, H. Peyton (2006) : Regret testing: learning to play Nash equilibrium without knowing you have an opponent, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New York, NY, Vol. 1, Iss. 3, pp. 341-367 This Version is available at: https://hdl.handle.net/10419/150083 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/2.5 Theoretical Economics 1 (2006), 341–367 1555-7561/20060341 Regret testing: learning to play Nash equilibrium without knowing you have an opponent DEAN P. FOSTER Department of Statistics, Wharton School, University of Pennsylvania H. PEYTON YOUNG Department of Economics, Johns Hopkins University, and Department of Economics, University of Oxford A learning rule is uncoupled if a player does not condition his strategy on the opponent’s payoffs. It is radically uncoupled if a player does not condition his strategy on the opponent’s actions or payoffs. We demonstrate a family of simple, radically uncoupled learning rules whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game. KEYWORDS. Learning, Nash equilibrium, regret, bounded rationality. JEL CLASSIFICATION. C72, D83. 1. LEARNING EQUILIBRIUM Although Nash equilibrium is the central solution concept in game theory, it has proved difficult to find adaptive learning rules that invariably lead to Nash equilibrium from out-of-equilibrium conditions. Of course, there exist particular rules, such as fictitious play, that work for particular classes of games, such as zero-sum games and potential games. And there exist sophisticated Bayesian updating procedures that lead to Nash equilibrium in any game provided that players’ strategies and beliefs are sufficiently aligned at the outset.1The issue we consider here is whether there exist simple adaptive procedures that solve the “learning to play Nash” problem for general games without making large demands on the players’ computational capacities and without imposing special initial conditions. Dean P. Foster: [email protected] H. Peyton Young: [email protected] The authors thank Andrew Felton, Sham Kakade, Ben Klemens, Thomas Norman, Kislaya Prasad, and several anonymous referees for constructive comments. An earlier version of this paper appeared as Sante Fe Institute Working Paper 04-12-034 with the title “Regret Testing: A Simple Payoff-Based Procedure for Learning Nash Equilibrium.” 1In a Bayesian framework, convergence to Nash equilibrium occurs with probability one provided that players’ repeated-game strategies are optimal given their beliefs, and their beliefs put positive probability on all events that have positive probability under their strategies (Kalai and Lehrer 1993). Unfortunately it is difficult to satisfy the latter absolute continuity condition when players do not know their opponents’ payoff functions (Jordan 1991,1993,Foster and Young 2001,Nachbar 1997,2005). Copyright c2006 Dean P. Foster and H. Peyton Young. Licensed under the Creative Commons AttributionNonCommercial License 2.5. Available at http://econtheory.org. 342 Foster and Young Theoretical Economics 1 (2006) To date, the main results on this problem have been negative. Consider, for example, the following criteria: i) a player’s response rule may depend on the history of the game, but it should not depend on ex ante knowledge of the opponent’s payoff function; ii) the rule should not depend on state variables of arbitrarily high dimensionality; iii) when all players use the rule, their period-by-period behaviors should converge (or at least come close) to Nash equilibrium behavior of the stage game or the repeated game. A rule with the first property is said to be uncoupled. This is a reasonable requirement when the payoff structure of the game is not known precisely, which is often the case in practice. (Moreover, if coupled learning rules were allowed, one could simply “tailor” the learning rule to each payoff situation, and the program would amount to little more than a theory of equilibrium selection.) The second property expresses the idea that a rule should be simple to implement. One formulation of “simplicity”—admittedly rather restrictive—is that a player’s behavioral response should depend only on histories of bounded length, or alternatively on a summary statistic of the whole history, such as the realized empirical frequency distribution (as in fictitious play). Such a rule is said to be stationary with respect to the state variable in question. The third property says that period-by-period behaviors should come close to Nash equilibrium; it is not enough that the cumulative empirical frequency of play come close. (The latter is the sense in which fictitious play converges in zero-sum games for example.) A recent paper of Hart and Mas-Colell (2005) establishes the following impossibility theorem: when the relevant states are taken to be histories of bounded length, and convergence is defined as almost sure convergence of the period-by-period behavioral probabilities to an "-equilibrium of the stage game, then for all sufficiently small " > 0 there is no rule satisfying the above three properties on the set of finite two-person games.2 This impossibility result hinges crucially on a particular choice of state variable and a demanding notion of convergence. In an earlier paper, for example, we demonstrated a class of statistical learning procedures that are simple, uncoupled, and cause players’ behaviors to converge in probability to the set of Nash equilibria in any finite game (Foster and Young 2003). In the simplest version of this approach, each player’s state variable has three components: i) the empirical frequency distribution of the opponent’s play over the past speriods, where sis finite; ii) a “hypothesis” about what frequency distribution the opponent is using during these periods, which is assumed to be unconditional on history; iii) a counting variable that tells whether the player is currently in “hypothesis testing” mode and how long he has been so. Once the count reaches s, a player conducts a hypothesis test, that is, he compares his current hypothesis with the observed behavior of the opponent over the last speriods. If the hypothesis is not too improbable given the data, he keeps the same hypothesis and eventually starts testing again. Otherwise he rejects his current hypothesis and chooses a new one at random from the finite-dimensional space of frequency distributions that the opponent could 2A related impossibility result states that if the state variable is the joint frequency distribution of play, there exists no uncoupled, deterministic, continuously differentiable adjustment dynamic such that the empirical frequency distribution converges to a stage-game Nash equilibrium in any finite two-person game (Hart and Mas-Colell 2003). Theoretical Economics 1 (2006) Regret testing 343 be using. Players are assumed to be boundedly rational in the sense that they choose smoothed best responses given their current hypotheses about the opponent. By annealing the parameters, it can be shown that, given any finite game, the players’ behaviors converge in probability to the set of Nash equilibria of the stage game. In this paper we introduce a new type of learning rule, called regret testing, that solves the “learning to play Nash” problem in an even simpler way. Unlike fictitious play, hypothesis testing, Kalai–Lehrer updating, and a host of other learning rules, regret testing does not depend on observation of the opponent’s pattern of play or even on knowledge of the opponent’s existence; it depends only on summary statistics of a player’s own realized payoffs. In this sense it is similar in spirit to reinforcement and aspiration learning.3Response rules that depend only on a player’s received payoffs are said to be radically uncoupled. In the next section we define regret testing in detail; here we briefly outline how it works and why it avoids the impossibility theorems mentioned earlier. In each period a player has an intended strategy, that is, a probability mixture over actions that he plans to use in that period. With a small exogenous probability—independent among periods and players—a given player becomes distracted and uses an alternative strategy instead of his intended strategy. For simplicity assume that the alternative strategy involves choosing each action with equal probability. Periodically the player evaluates how his intended strategy is doing. He does this by comparing the average payoff he received when using his intended strategy with the average payoffs he received when distracted. If the latter payoffs are not markedly larger than the former, he continues as before. Otherwise he switches to a new (intended) strategy, where the choice of new strategy has a random component that assures that no region of his strategy space is completely excluded from consideration. The random aspect of strategy switching is crucial because it allows for undirected search of the strategy space, and prevents the learning process from getting bogged down in disequilibrium mutual-adjustment cycles. It also side-steps the impossibility theorem of Hart and Mas-Colell mentioned at the outset: since behavior at a given point in time depends on the outcome of prior random variables (strategy switches), the learning process is not stationary with respect to any of the usual state variables such as history of play, history of payoffs, and so forth. Nevertheless, it is very simple and intuitive, and under an appropriate choice of the learning parameters, causes period-byperiod behaviors to converge in probability to the set of stage-game Nash equilibria in any finite two-person game. The method can be extended to handle generic n-person games with finite action spaces (Germano and Lugosi 2004), but whether it works for all finite n-person games (n≥3) remains an open problem. 2. REGRET TESTING Consider an individual who lives alone. He has mpossible actions, the names of which are written on “tickets” stored in “hats.” Each hat contains h≥mtickets. Since a given 3Standard examples of reinforcement learning are given in Bush and Mosteller (1955) and Erev and Roth (1998). For models of aspiration learning see Karandikar et al. (1998), Börgers and Sarin (2000), Bendor et al. (2001), and Cho and Matsui (2005). 344 Foster and Young Theoretical Economics 1 (2006) action can be written on multiple tickets, a hat is a device for generating probability distributions over actions. Every probability distribution that is expressible in integer multiples of 1/his represented by exactly one hat. The larger is h, the more closely can any given distribution be approximated by one of these hats. Step 1. A day consists of speriods, where sis large. Once each period, the player reaches into his current hat, draws a ticket, and takes the action prescribed. He then returns the ticket to the hat. Step 2. At random times this routine is interrupted by telephone calls. During a call he absent-mindedly chooses an action uniformly at random instead of reaching into the hat. Step 3. Every time he takes an action he receives a payoff. At the end of day t, he tallies the average payoff, b αt, he received over the course of the day whenever he was not on the phone. For each action j, he compares b αtwith the average payoff, b αj,t, he received when he chose jand was on the phone. Step 4. If at least one of the differences b rj,t=b αj,t−b αtis greater than his tolerance level τ > 0 he chooses a new hat, where each hat has a positive probability of being chosen. Otherwise he keeps his current hat and the process is repeated on day t+1. Any procedure of this form is called a regret testing rule. The reason is that b αj,t amounts to a statistical estimate of the payoff on day tthat the player would have received from playing action jall day long, hence the difference b rj,t=b αj,t−b αtis the estimated regret from not having done so.4(Recall that the regrets cannot be evaluated directly because the opponent’s actions are not observed.) The logic is simple: if one of the payoff-averages b αj,tduring the experimental periods is significantly larger than the average payoff in the non-experimental periods, the player becomes dissatisfied and chooses a new strategy, i.e., a new hat from the shelf. Otherwise, out of inertia, he sticks with his current strategy. The revision process (Step 4) allows for many possibilities. The simplest is to choose each hat with equal probability, but this lacks behavioral plausibility. Instead, the player could exploit the information contained in the current payoffs, say by favoring strategies (hats) that put high probability on actions with high realized payoff b αj,t. Consider, for example, the following revision rule: with probability 1 −"adopt the pure strategy that puts probability one on the action jthat maximizes b αj,t; and with probability "choose a strategy at random. This is a trembled form of best response strategy revision, where the tremble is not in the implementation of the strategy but in the choice of strategy. In particular, a strategy that is far from being a best response strategy can be chosen by mistake, but the probability of such a mistake is small. While the use of recent payoff information may be sensible, however, we do not insist on it. The reason is that the process will eventually approximate Nash equilibrium behavior irrespective of the revision rule, as long as every hat is chosen with a probability that is uniformly bounded away from zero at all revision opportunities. This allows for a great deal of latitude in the specification of the learning process. 4A similar estimation device is used by Foster and Vohra (1993) and Hart and Mas-Colell (2000,2001, 2005). Theoretical Economics 1 (2006) Regret testing 345 We hasten to say that this rule is intended to be a contribution to learning theory, and should not be interpreted literally as an empirical model of behavior, any more than fictitious play should be. Nevertheless it is composed of plausible elements that are found in other learning rules. One key element of regret testing is inertia: if there is no particular reason to change, play continues as before. In fact, inertia is built into the rule at two levels: there is no change of strategy while data is being collected over the course of a day, and change is implemented only if a significant improvement is possible—in other words, the alternative payoffs must exceed the current average payoff by more than some positive amount τ. Inertia is an important aspect of aspiration learning as well as several other learning rules in the literature, including hypothesis testing (Foster and Young 2003) and regret matching (Hart and Mas-Colell 2000,2001). In the latter procedure, a player continues to choose a given action with high probability from one period to the next. When change occurs, the probability of switching to each new action is proportional to its conditional regret relative to the current action.5Hart and Mas-Colell show that under this procedure the cumulative empirical frequencies converge almost surely to the set of correlated equilibria. (Note that this is quite different from saying that the period-by-period behaviors converge.) A second key element of regret testing is that, when a change in strategy occurs, the choice of new strategy has a random component that allows for wide-area search. Except for hypothesis testing, this feature is not typical of other learning rules in the literature. For example, under regret matching, a player’s strategy at any given time is either almost pure or involves switching probabilistically from one almost-pure strategy to another. Similarly, under aspiration learning, a player switches from one pure strategy to an alternative pure strategy when the former fails to deliver payoffs that meet a given aspiration level. In both of these situations there are probabilistic changes among particular classes of strategies, but not a wide-area search among strategies. These two elements—inertia and search—play a key role in the learning process. Inertia stabilizes the players’ behavior for long enough intervals that the players have a chance to learn something about their opponent’s behavior. Search prevents the process from becoming trapped in adjustment cycles, such as the best response cycles that bedevil fictitious play in some settings. Intuitively, the way the process operates is that it discovers a (near) equilibrium through random search, then stays near equilibrium for a long time due to inertia. While it may seem obvious that this ought to work, it is a different matter to show that it actually does work. One difficulty is that the players’ search episodes are not independent. Searches are linked via the history of play, so there is no guarantee that the joint strategy space will be searched systematically. A second difficulty is that, even when a search is successful and an equilibrium (or near equilibrium) has been found, the players do not know it. This is because they are ignorant of the opponent’s payoff function, hence they cannot tell when a equilibrium is in hand, and may 5The conditional regret of action krelative to action jis the increase in average per-period payoff that would have resulted if khad been played whenever jactually was played. (The conditional regret is set equal to zero if kwould have resulted in a lower average payoff than j.) 346 Foster and Young Theoretical Economics 1 (2006) move away again. The essence of the proof is to show that, nevertheless, the expected time it takes to get close to equilibrium is much shorter than the expected time it takes to move away again. 3. FORMAL DEFINITIONS AND MAIN RESULT Let Gbe a two-person game with finite action spaces X1and X2for players 1 and 2 respectively. Let |Xi|=miand let ui:X1×X2→Rbe i’s utility function. In what follows, we assume (for computational convenience) that the von Neumann Morgenstern utility functions uiare normalized so that all payoffs lie between zero and one: min x∈X1×X2 ui(x)≥0 and max x∈X1×X2 ui(x)≤1. (1) Let ∆idenote the set of probability mixtures over the miactions of player i. Let hi be the uniform size of i’s hats (a positive integer). The set of distributions in ∆ithat are representable as integer multiples of 1/hiis denoted by Pi. Note that every strategy in ∆ican be closely approximated by some strategy in Piwhen hiis sufficiently large. Let τi>0 denote i’s tolerance level, let λi∈(0,1)be the probability that a call is received by a player iduring any given play of the game, and let sbe the number of plays per day. The state space is Z=P1×P2, which we sometimes refer to as the probability grid. The state of the learning process at the start of a given day tis zt= (pt,qt)∈P1×P2. For each action jof player i, let b αi j,t=b αi j,t(zt)be the average payoff on day tin those periods when iplayed action jand was on the phone. Let b αi t=b αi t(zt)be i’s average payoff on day twhen not on the phone, and let b θi t= (b αi t,b αi 1,t,...,b αi mi,t). Note that b θi t contains enough information to implement a wide variety of updating rules, including trembled best response behavior and trembled better response behavior. Finally, let b ri t(zt) = max 1≤j≤mib αi j,t(zt)−b αi t(zt). Aregret-testing rule for player 1 has the following form: there is a number γ1>0 such that for every tand every state zt= (pt,qt), b r1 t(zt)≤τ1⇒pt+1=pt(2) b r1 t(zt)> τ1⇒P(pt+1=p|pt,b θ1 t)≥γ1for all p∈P1. The analogous definition holds for player 2. Note that we must have γi≤1/|Pi|because the conditional probabilities in (2) sum to unity. The case γi=1/|Pi|corresponds to the uniform distribution, that is, all strategies in Piare chosen with equal probability when a revision occurs. The class of regret testing rules is more general, however, because it allows for any conditional revision probabilities as long as they are uniformly bounded below by some positive constant. A pair (p,q)∈∆1×∆2is an "-equilibrium of Gif neither player can increase his payoff by more than "through a unilateral change of strategy. Theoretical Economics 1 (2006) Regret testing 347 THEOREM 1. Let G be a finite two-person game played by regret testers and let " > 0. There are upper bounds on the tolerances τiand exploration rates λi, and lower bounds on the hat sizes hiand frequency of play s, such that, at all sufficiently large times t , the players’ joint behavior at t constitutes an "-equilibrium of G with probability at least 1−". Explicit bounds on the parameters are given in Section 5 below. REMARK 1. It is not necessary to assume that the players revise their strategies simultaneously, that is, at the end of each day. For example, we could assume instead that if player i’s measured regrets exceed his tolerance τi, he revises his strategy with probability θi∈(0,1)and with probability 1 −θihe continues to play his current strategy on the following day. We could also assume that the players use different amounts of information. Suppose, for example, that player ilooks at the last kidays of payoffs (ki integer), and revises with probability 0 < θi<1 whenever the estimated regrets exceed τi. With fixed values of kiand θithis does not change the conclusion of Theorem 1 or the structure of the argument in any significant way. REMARK 2. It is not necessary to assume that, when on the phone, a player chooses each of his actions with equal probability. Any fixed probability distribution that assigns positive probability to every action can be employed, but in this case the sample size may need to be larger than in the uniform case for the theorem to hold. REMARK 3. Theorem 1 does not assert that the learning process converges to an "- equilibrium of G; rather, it says that the players’ period-by-period behaviors are close to equilibrium with high probability when tis large. By annealing the learning parameters at a suitable rate, one can achieve convergence in probability to the set of Nash equilibria, as we show in the concluding section. Moreover, with some further refinements of the approach one can actually achieve almost sure convergence, as shown by Germano and Lugosi (2004). Although these are probabilistic forms of convergence, the results are quite strong because they hold for the players’ period-by-period behaviors. Regret matching, by contrast, only guarantees that the players’ time-average behaviors converge, and then only to the set of correlated equilibria.6 Before giving the proof of Theorem 1 in detail, we give an overview of some of the technical issues that need to be dealt with. Regret testing defines one-step transition probabilities P(z→z0)that lead from any given state zon day tto some other state z0 on day t+1. Since these transition probabilities do not depend on t, they define a stationary Markov process Pon the finite state space Z. A given state z= (p,q)induces a Nash equilibrium in behaviors if and only if the expected regrets in that state are nonpositive. Similarly, (p,q)induces an "-equilibrium in behaviors if and only if the expected regrets are "or smaller. Note that this is not the same as saying that (p,q)itself is an 6Other rules whose long run average behavior converges to the correlated equilibrium set are discussed by Fudenberg and Levine (1995,1998), Foster and Vohra (1999), and Cahn (2004). See Young (2004) for a general discussion of the convergence properties of learning rules. 348 Foster and Young Theoretical Economics 1 (2006) "-equilibrium, because the players’ behaviors include experimentation, which distorts the probabilities slightly. If a given state zdoes not induce an "-equilibrium, the realized regrets b ri j,tare larger than "with fairly high probability for at least one of the players. This player then revises his strategy. Since no strategy on his grid is excluded when he revises, there is a positive probability he hits upon a strategy that is close to being a best response to the opponent’s current strategy. This is not good enough, however, because the new strategy pair does not necessarily induce an "-equilibrium. What must be shown is that the players arrive simultaneously at strategies that induce an "-equilibrium, a point that is not immediately obvious. For example, one player may revise while the second stays put, then the second may revise while the first stays put, and so forth. Even if they do eventually arrive at an "-equilibrium simultaneously, they must do so in a reasonably short period of time compared to the length of time they stay at the "-equilibrium once they get there. Again this is not obvious. One difficulty is that the players do not know when they have arrived—they cannot see the opponent’s strategy, or even his action, so they cannot determine when an "-equilibrium is in hand. In particular, the realized regrets may be large (due to a series of bad draws) even though the state is close to equilibrium (or even at an equilibrium), in which case the players will mistakenly move away again. A second difficulty is that revisions by the two players are uncoupled, that is, they cannot coordinate the search process. In reality, however, their searches are linked because the regrets are generated by their joint actions. Thus, the fact that each player conducts a search of his own strategy space whenever he revises need not imply that the joint strategy space is searched systematically. 4. ENTRY AND EXIT PROBABILITIES The first step in proving Theorem 1 is to compare the probability of entering the set of "-equilibrium states with the probability of leaving them. As a preliminary, we need to refine the concept of "-equilibrium as follows. Given a pair of nonnegative real numbers ("1,"2), say that a pair of strategies (p,q)∈∆1×∆2is an ("1,"2)-equilibrium if ∀p0∈∆1, u1(p0,q)−u1(p,q)≤"1 ∀q0∈∆2, u2(p,q0)−u2(p,q)≤"2. When "1="2=", we use the terms "-equilibrium and ("1,"2)-equilibrium interchangeably. For any two real numbers x,ylet x∧y=min{x,y}and x∨y=max{x,y}. Let us also recall that midenotes the number of actions available to player i. LEMMA 1. Let m =m1∨m2,τ=τ1∧τ2, and λ=λ1∧λ2, and suppose that 0< λi≤τ/8≤ 1 8for i =1,2. There exist positive constants a, b, and c such that, for all t , (i) If state zt= (pt,qt)is a (τ1/2,τ2/2)-equilibrium, a revision occurs at the end of period t with probability at most a e −bs for all s. (ii) If ztis not a (2τ1,2τ2)-equilibrium and if s ≥c, then at least one player revises at the end of period t with probability greater than 1 2; moreover if each player i is out Theoretical Economics 1 (2006) Regret testing 355 There are at most 1/γ2states in Zaltogether, so X w/∈E∗ πw≤16ae−bs /γ5. The right-hand side is at most "/2 if ae−bs ≤γ5"/32, that is, if s≥(1/b)ln(32a/γ5"). By Lemma 1, we can take a=12mand b=λτ2/256m. Thus it suffices that s≥256m λτ2ln(384m/γ5"), which is implied by the stronger bound in (11). This concludes the proof of Case 1. CASE 2. d(G) = 0; some player has a 0-dominant strategy. Fix a probability 0 < β < 1 2that is much smaller than γand much larger than a e −bs ; later we specify βand smore exactly. Define the following subset of states: Zβ={z= (p,q):∀t,∀q0∈P2,P(pt+16=p|zt= (p,q0)) ≤β}. In words, Zβis the set of states such that the first player changes strategy with probability at most βno matter what strategy the second player is using on his grid. Without loss of generality assume that player 1 has a 0-dominant strategy. Then he has a pure 0-dominant strategy, say p∗, which is in P1. We fix p∗for the remainder of the proof. Let Z∗be the set of states whose first coordinate is p∗. Then player 1 rejects with probability at most ae −bs (see Remark 4), that is, P(zt+1∈Z∗|zt∈Z∗)≥1−ae−bs . Hence Z∗⊆Zβprovided that a e −bs ≤β, which holds whenever sis sufficiently large (we assume henceforth that this is the case). Let w∈Z−E∗. There are two possibilities: w/∈Zβand w∈Zβ. CASE 2A.w/∈E∗and w/∈Zβ. Since w= (p,q)/∈E∗,wis not an "/2-equilibrium, and hence is not a (2τ1,2τ2)- equilibrium. By Lemma 1 the probability is at least 1 2that there will be a revision next period by at least one of the players. If player 1 revises, a transition of form (p,q)→ (p∗,·)∈Z∗occurs with probability at least γ. After that, (p∗,·)stays in Z∗for one more period with probability at least 1 −ae−bs , which is at least 1 2because ae−bs < β < 1 2. Hence in this case P2(w→Z∗)≥γ/4. If player 1 does not revise but player 2 does, then with probability at least γwe have a transition of form (p,q)→(p,q0), where q0∈P2is a strategy for player 2 that makes 356 Foster and Young Theoretical Economics 1 (2006) player 1 revise with probability greater than β. (There is such a q0because of our assumption that w/∈Zβ.) In the following period the transition (p,q0)→(p∗,·)occurs with probability greater than βγ. Hence in this case P2(w→Z∗)≥βγ2/2. Therefore, in either case, P2(w→Z∗)≥(βγ2/2∧γ/4)≥βγ2/4. Now apply Lemma 2 with Z0=Z∗,θ=ae−bs , and ρ=βγ2/4. Since w/∈Z∗we conclude that πw≤2ae−bs /(βγ2/4) = 8ae−bs /βγ2. (19) CASE 2B.w/∈E∗and w∈Zβ. By definition ofZβ, player 1 revises with probability at most β, which by assumption is less than 1 2. Since w= (p,q)/∈E∗, some player ican increase his payoff by at least "/2, and hence by more than 2τi. This player will revise with probability greater than 1 2(see Remark 4), hence icannot be player 1 (who revises with probability less than 1 2). Therefore imust be player 2. By (9), there exists q00 on player 2’s grid that is within τ2/8 of a best response to p. The probability is at least γthat 2 chooses q00 when he revises. Putting all of this together, we conclude that P((p,q)→(p,q00)) ≥γ/4. (20) By construction, state (p,q00)is a (·,τ2/8)-equilibrium, hence player 2 revises with probability at most ae−bs (see the remark after Lemma 1). By assumption, (p,q)∈Zβ, so player 1 revises with probability at most βagainst any strategy of player 2, including q00. Hence (p,q00)is also in Zβ, and P((p,q00)→(p,q00)) ≥(1−β)(1−ae−bs )≥(1−β)2>1−2β. From this and (20) we have P2((p,q)→(p,q00)) ≥(γ/4)(1−β)2> γ/16, the latter since β < 1 2. Now apply Lemma 2 with Z0={(p,q00)},ρ=γ/16, and θ=2β. It follows that for every stationary distribution πof P, πw≤2(2β)/(γ/16) = 64β/γ. (21) Combining (19) and (21), it follows that in both Case 2a and Case 2b, ∀w/∈E∗,πw≤64β/γ ∨8ae−bs /βγ2. (22) Theoretical Economics 1 (2006) Regret testing 357 The size of the state space is at least 1/γ2. Summing (22) over all w/∈E∗it follows that π(Z−E∗)≤(1/γ2)(64β/γ∨8a e −bs /βγ2). We wish to show that this is at most "/2. This will follow if we choose βand sso that 64β/γ3="/4 and 8ae−bs /βγ4≤"/4. Specifically, it suffices that β="γ3/256 and s≥(1/b)ln(8192a/"2γ7). By Lemma 1 we may choose a=12mand b=λτ2/256m, hence it suffices that s≥(256m/λτ2)ln(98,304m/"2γ7). This certainly holds under (11), which states that s≥(103m2/λτ2)ln(105m/"2γ7). This concludes the proof of the theorem.  6. CONVERGENCE IN PROBABILITY Theorem 1 says that, for a given game G, regret testing induces an "-equilibrium with high probability provided that the learning parameters satisfy the bounds given in (6)- (11). But it does not imply that, for a given set of parameters, an "-equilibrium occurs with high probability for all games G. The difficulty is condition (7), which in effect requires that d(G)not fall into the interval (0,p48(τ1∨τ2)). If we think of Gas a vector of 2m1m2payoffs in Euclidean space, the excluded set is small relative to Lebesgue measure whenever the τiare small. Thus, if we tighten τ1,τ2and the other parameters in tandem, the learning process eventually captures all games in the “net,” that is, there are no excluded cases. In this section we show even more, namely, that by tightening the parameters sufficiently slowly, the players’ period-by-period behavioral strategies converge in probability to the set of Nash equilibria of G. Fix an m1×m2action space X=X1×X2and consider all games Gon Xwith payoffs normalized to lie between zero and one. As before, let m1∨m2,λ=λ1∧λ2,γ=γ1∧γ2, and τ=τ1∧τ2. For each " > 0, we choose particular values of these parameters that satisfy all the bounds except (7), namely, τi(") = "2/48 (23) λi(") = τ(")/16 (24) hi(") = 8pm/τ(")£(25) γi(") = 1/|Pi(hi("))|(26) s(") = (103m2/λ(")τ2(")ln(105m/"2γ7(")£. (27) Recall that |Pi(hi("))|is the number of distributions on i’s grid when his hat size is hi("). Hence the players’ grids become increasingly fine as "becomes small. Note also 358 Foster and Young Theoretical Economics 1 (2006) that (26) implies that each player chooses a new hat with uniform probability whenever a revision is called for. This proves to be analytically convenient in what follows, although more general assumptions could be made. Let PG(")denote the finite-state Markov process determined by Gand the parameters (τ1("),...,s(")). Let EG(")be the finite subset of states that induce an "-equilibrium of G. DEFINITION 1. Let Pbe an acyclic, finite Markov process and Aa subset of states. For each " > 0, let T(P,A,")be the first time (if any) such that, for all t≥T(P,A,")and all initial states, the probability is at least 1−"that the process is in Aat time t. It follows from Theorem 1 that T(PG("),EG("),")is finite for all games Gsuch that d(G)/∈(0,p48(τ1∨τ2)). By assumption (23), this holds whenever d(G)/∈(0,"). In this case, for all t≥T(PG("),EG("),"), the probability is at least 1 −"that the behavioral strategies constitute an "-equilibrium of Gat time t. The time T(PG("),EG("),")may depend on the payoffs, because these affect the details of the transition probabilities and the states that correspond to "-equilibria of G. We claim, however, that for every " > 0 there is a time T(")such that T(")≥ T(PG("),EG("),")for all Gsuch that d(G)/∈(0,"). To see why this is so, consider the realization of plays on any given day. A realization is a sequence of s(")action-outcome pairs, where an “outcome” is 0 or 1 depending on whether the action was taken by that player while on the phone or not. Hence there are (4m1m2)s(")possible realizations. We may partition them into four disjoint classes: sequences that cause both the players to reject (because the estimated regrets exceed their tolerances), sequences that are rejected by player 1 but not player 2; sequences that are rejected by player 2 but not player 1, and sequences that are accepted by both. Notice that this partition does not depend on the day tor on the strategies (pt,qt)in force during that day, but it does depend on the game G. Moreover, a player’s response given a rejection does not depend on other details of the sequence, because we are assuming that each player chooses a new strategy with uniform probability over all distributions on his grid. The number of length-s(")realizations is finite, and there are finitely many ways of partitioning them into four classes. Further, the probability that each sequence is realized on a given day tis determined by the state (pt,qt), and there are finitely many states. Hence, over all G, there can be only a finite number of Markov transition matrices PG("). Further, finitely many subsets of states can be used to define EG("). Let us enumerate all possible pairs (PG("),EG(")) as follows: (P1,E1),...,(Pk,Ek). Now define T(") = max1≤j≤kT(Pj,Ej,"). Then T(")has the property that, for all Gsuch that d(G)6∈(0,"), and for all t≥T("), the behavioral strategies constitute an "-equilibrium at time twith probability at least 1−". DEFINITION 2 (annealed regret testing). Consider any positive sequence "1> "2> "3> ··· decreasing to zero. The annealed regret testing procedure at stage kis the regret testing procedure with parameters τ1("k),τ2("k),λ1("k),λ2("k),h1("k),h2("k),γ1("k), Theoretical Economics 1 (2006) Regret testing 359 γ2("k), and s("k)as in (23)–(27). Each day that the process is in stage k, the probability of moving to stage k+1 on the following day is pk≡"2 k+1 2k2T("k+1). THEOREM 2. Fix an m1×m2action space X =X1×X2. Annealed regret testing has the property that, for every game G on X, the behavioral strategies converge in probability to the set of Nash equilibria of G . Although annealed regret testing seems to require that each player has an arbitrarily long memory, the process is actually of much lower dimension. To see why, let us fix a particular player i. Create one “payoff register” and one “counting register” for each of i’s actions, plus one general payoff register and one general counting register for all of his actions together. Let kbe a state variable that is common to all the players and indicates what stage the process is in (i.e., what parameters are currently in force). At each time t,i’s general payoff register contains the running total of the payoffs he received when not on the phone, and the general counting register contains the number of times he was not on the phone. Similarly, each action-specific register contains the running total of the payoffs he received when he was on the phone and played that action, and the number of times the action was played while on the phone. When the sum over all counting registers reaches s("k), player iconducts a test using the kth set of parameters, revises his strategy if this is called for, and empties all the registers. The process is then repeated. Thus player ineeds to keep track of only 2mi+3 numbers—two for each of his actions, two in the general registers, and the current stage k. Thus the learning process requires very little memory or computational sophistication. PROOF OF THEOREM 2. Given G, it suffices to show that, for every " > 0, there is a finite time T"(possibly depending on G) such that for all t≥T", the probability is at least 1−"that the behavioral strategies (e pt,e qt)constitute an "-equilibrium of G. Indeed, for every δ > 0 there exists 0 < "δ≤δsuch that every "δ-equilibrium lies within δof the compact set NGof Nash equilibria of G. Hence, for all t≥T"δ, the probability is at least 1−"δ≥1−δthat (e pt,e qt)lies within δof NG. Thus, the behavioral strategies converge in probability to the set of Nash equilibria of G. To facilitate the proof we define three integer-valued random variables Nt,Tk, and Wkthat describe the process as it transitions through stages. Let Ntbe the stage that the process is in on day t. In other words, on day tthe process is using the parameters (τ1("Nt),τ2("Nt),λ1("Nt),λ2("Nt),h1("Nt),h2("Nt),γ1("Nt),γ2("Nt),s("Nt)). The distribution of the realizations of Ntdepends on the transition probabilities as follows: N1=1 Nt+1=(Ntwith probability 1−pNt Nt+1 with probability pNt. 360 Foster and Young Theoretical Economics 1 (2006) The first time that the system uses the kth set of parameters is denoted by Tk, that is, Tk≡ inft{t:Nt≥k}. Now define Wt≡t−TNtto be the length of time since the parameters were last changed. In essence, the proof consists of establishing two facts about Wt. First we show that if Wtis “large” for a given t, the behavioral strategies are nearly a Nash equilibrium with high probability at time t. This follows by applying Theorem 1 to this setting. Second, we show that the probability that Wtis “large” converges to one as t converges to infinity. This follows from our assumption that the transition probabilities pkare small. We now establish these points in detail. For any game Gon X, if d(G)>0 then d(G)≥"kfor all sufficiently large k, because the sequence {"k}decreases to zero. The least such kis called the critical index of G, and denoted by kG. In case d(G) = 0, we take kG=1. Fix " > 0. Define k∗ G=kG∨mink{k| "k≤"/4}. It follows that if Nt≥k∗ Gthen "Nt≤"/4 and d(G)≥"Nt. Since Nt→∞almost surely as t→∞, there is a time T∗such that, for all t≥T∗, the probability is at least 1−"/4 that Nt≥k∗ G. From now on we consider only t≥T∗. Given t≥T∗, consider two cases: Wt≥T("Nt)and Wt<T("Nt). In the first case, the process is an "Nt-equilibrium with probability at least 1 −"Nt. Since t≥T∗,Nt≥k∗ G with probability at least 1 −"/4, in which case "Nt≤"/4. It follows that at time tthe process is in an "/4-equilibrium, and hence an "-equilibrium, with probability at least (1−"/4)(1−"/4)≥1−"/2. To complete the proof, it therefore suffices to show that, for all sufficiently large t, the second case occurs with probability at most "/2, that is, there exists T∗∗ such that ∀t≥T∗∗,P(Wt<T("Nt)) ≤"/2. (28) To establish (28) we proceed as follows. Recall that in the kt h stage of the process, the parameter values are (τ1("k),...,s("k)). By choice of pk, the kt h stage lasts for 2k2T("k+1)/"2 k+1periods in expectation. Say that the kt h stage is short if it lasts for at most T("k+1)/"2 k+1periods, which is 1/2k2times the expected number. This event has probability at most 1/k2. Hence, given any positive integer k0, the probability that a short stage occurs at some time after the kt h 0stage is at most X k>k0 1/k2≤Z∞ k0 d x/x2=1/k0. If we let k∗∗ G=k∗ G∨16/", it follows that the probability is at most "/16 that a short stage ever occurs after stage k ∗∗ G. Now there exists a time T∗∗ such that ∀t≥T∗∗,P(Nt≥k∗∗ G+2)≥1−"/16. We show that (28) holds for this value of T∗∗. For each time t≥T∗∗, define the event Atto be the set of all realizations such that there is at most one stage change between t −T("Nt)/"2 Ntand t , that is, Nt≤1+Nt−T("Nt)/"2 Nt. Theoretical Economics 1 (2006) Regret testing 361 Let Ac tdenote the complement of At. Since t≥T∗∗, the probability is at least 1 −"/16 that the process is at stage k∗∗ G+2 or higher at time t. Denote this event by Bt. If Btand Ac tboth hold, then there were at least two stage changes between t−T("Nt)/"2 Ntand t, hence the previous stage change (before the current stage) was short. But we already know that the probability of a short stage at any time beyond stage k∗∗ Gis at most "/16. Hence P(Ac t|Bt)≤"/16 and P(Bc t)≤"/16. Therefore ∀t≥T∗∗,P(Ac t)≤P(Ac t|Bt) + P(Bc t)≤2("/16) = "/8. We now compute the probability that Wt<T("Nt). By the preceding we know that P(Wt<T("Nt)) ≤P(Wt<T("Nt)|At) + P(Ac t) ≤P(Wt<T("Nt)|At) + "/8. Hence to establish (28) it suffices to show that P(Wt<T("Nt)|At)≤3"/8. Clearly, P(Wt<T("Nt)|At) = X k P(Wt<T("Nt)|Nt=k,At)P(Nt=k|At) ≤max kP(Wt<T("Nt)|Nt=k,At). Let Nt=k. The event Atis the disjoint union of the event A0 tin which no stage change occurs between t−T("k)/"2 kand t, and the event A1 tin which exactly one stage change occurs. When A0 toccurs, Wt≥T("k)/"2 k>T("k), hence P(Wt<T("k)|A0 t) = 0. It remains only to show that P(Wt<T("k)|A1 t)≤3"/8. The conditional distribution of Wtis f(w)≡P(Wt=w|Nt=k,A1 t) = ck(1−pk)T("k)/"2 k−wpk(1−pk+1)w−1, (29) where ckis a positive constant and 1 ≤w≤T("k)/"2 k. This follows because under A1 t a single stage change occurs during the interval, and it occurs exactly Wt=wperiods before period t. We may rewrite (29) in the form f(w) = c0 k1−pk+1 1−pkw for some c0 k>0. Since pk>pk+1,f(w)≤f(w+1). Hence for every Tand win the interval 1 ≤T,w≤T("k)/"2 k, X w<T f(w)≤T f (T)and X w≥T f(w)≥(T("k)/"2 k−T)f(T). 362 Foster and Young Theoretical Economics 1 (2006) In particular for T=T("k)we have P(Wt<T("k)) = X w<T("k) f(w) =1 1+P w≥T("k) f(w)P w<T("k) f(w)≤1 1+T("k)/"2 k−T("k)/T("k)="2 k. Since t≥T∗∗,"Nt="k≤"/4 with probability at least 1−"/4. Hence P(Wt<T("k)) ≤("/4)2(1−"/4) + "/4<3"/8. This establishes (28) and completes the proof of Theorem 2. APPENDIX Here we prove Lemma 1, which is restated for easy reference. LEMMA 1.Let m =m1∨m2,τ=τ1∧τ2, and λ=λ1∧λ2, and suppose that 0< λi≤τ/8≤ 1 8for i =1,2. There exist positive constants a, b, and c such that, for all t , (i) If state zt= (pt,qt)is a (τ1/2,τ2/2)-equilibrium, a revision occurs at the end of period t with probability at most a e −bs for all s. (ii) If ztis not a (2τ1,2τ2)-equilibrium and if s ≥c, then at least one player revises at the end of period t with probability greater than 1 2; moreover if each player i is out of equilibrium by at least 2τi, both revise at the end of period t with probability greater than 1 4. It suffices that a =12m, b =λτ2/256m, and c =103m2/λτ2. PROOF. The player’s strategy revisions are triggered by the size of their realized regrets b ri t. Hence we need to estimate the distribution of b ri tconditional on the state at time t, namely, zt= (pt,qt). Recalling the definitions of b αi j,tand b αi tfrom Step 3 of regret testing, let αi j,t≡E(b αi j,t|(pt,qt)) and αi t≡E(b αi t|(pt,qt)). Recall that player 2 draws from his hat with probability 1 −λ2, and plays an action uniformly at random with probability λ2. (The uniform distribution over actions when experimenting contrasts with the possibly non-uniform distribution over hats when a rejection occurs.) Hence when player 1 chooses action jat time t, his expected payoff is α1 j,t=X k ((1−λ2)(qt)k+λ2/m2)u1 j,k. Similarly, 1’s expected payoff at time tis α1 t=X j,k (pt)j((1−λ2)(qt)k+λ2/m2)u1 j,k. Theoretical Economics 1 (2006) Regret testing 363 Similar expressions hold for α2 j,tand α2 t. Define ri t≡max jαi j,t−αi t. Since E(b αi j,t|(pt,qt)) = αi j,tand E(b αi t|(pt,qt)) = αi twe can think of the difference, b ri t=max jb αi j,t−b αi t, as being an estimator of ri t. Define the estimation error in state (pt,qt)to be |b ri t−ri t|. Next we estimate the distribution of the realized regret estimates b ri t. CLAIM.If λi≤1 3, then for all δ≤1/p2mi, and for all times t, P|b ri t−ri t|> δ≤6mie−sλiδ2/16mi. (A1) PROOF. Fix a player iand let (pt,qt)be the state on day t. Let Ni j,tbe the number of times action jis played on day twhile player iis on the telephone. The average payoff during these times, b αi j,t, is an average of Ni j,titems, each of which is bounded between zero and one. By Azuma’s inequality (Azuma 1967), P(|b αi j,t−αi j,t|> δ |(pt,qt),Ni j,t)≤2e−Ni j,tδ2/2. (A2) Let Ni t=PjNi j,t. The number of times iwas not on the phone on day tis s−Ni t, hence again by Azuma’s inequality P(|b αi t−αi t|> δ |(pt,qt),Ni t)≤2e−(s−Ni t)δ2/2. (A3) Since for any two events Aand B,P(A ∪B)≤P(A) + P(B), it follows from (A2) and (A3) that P(|b ri t−ri t|>2δ|(pt,qt),Ni 1,t,Ni 2,t,...,Ni mi,t)≤2 mi X j=1 e−Ni j,tδ2/2+2e−(s−Ni t)δ2/2. (A4) The next step is to estimate the size of the tail of the random variable Ni j,t, which is binomially distributed B(λi/mi,s). We claim that PNi j,t−sλi mi≥sλi 2mi≤2e−sλi/20mi. (A5) This can be derived from Bennett’s inequality (Bennett 1962). Consider a collection of nindependent random variables U1,...,Unwith sup|Ui| ≤ M,E Ui=0, and PiE U2 i=1. Then for every τ > 0, PX i Ui≥τ≤expτ M−τ M+1 M2ln(1+Mτ). (A6) 364 Foster and Young Theoretical Economics 1 (2006) We apply this to the case of ni.i.d. random variables X1,...,Xn, with Var(Xi) = σ2and |Xi|≤1. Let Ui= (1/σpn)(Xi−E X). Then |Ui|<1/σpn,EUi=0, and Pn i=1EU2 i=1. Letting τ= (γ/σ)pn,M=1/σpn, and X=PXi/n, it follows from (A6) that P(X−EX ≥γ)≤expnγ−n(γ+σ2)ln(1+γ/σ2). If we take γ=σ2/2 and use the fact that ln(3/2)≥.4, P(X−EX ≥σ2/2)≤exp(−nσ2/10). When the Xi’s are binomial (p,n)with 0 <p<.5, this implies P(X−p≥p/2)≤e−np/20 and hence P(|X−p|≥p/2)≤2e−np/20, from which (A5) follows immediately. Consider the event Bin which all of the Ni j,tlie within their expected value λis/mi plus or minus half their expected value: B ≡\j{|Ni j,t−λis/mi|≤λis/2mi}. From (A5) it follows that the probability of the complementary event Bcsatisfies P(Bc)≤2mie−sλi/20mi. (A7) Let Abe the event |b ri t−ri t)|>2δ. From (A4) we have P(A |B)≤2mie−λisδ2/4+2e−(s−Ni t)δ2/2. But if Bholds, then s−Ni t≥s−3λis/2= (1−3λi/2)s. By hypothesis λi≤1 3, hence s−Ni t>s/2 and P(A |B)≤2mie−λisδ2/4+2e−sδ2/4. (A8) Since P(A)≤P(A |B) + P(Bc), it follows from (A7) and (A8) that P(A) = P(|b ri t−ri t|)>2δ)≤2mie−sλiδ2/4+2e−sδ2/4+2mie−sλi/20mi ≤2(mi+1)e−sλiδ2/4+2mie−sλi/20mi. Changing from δto δ/2 we obtain P(|b ri t−ri t|> δ)≤2(mi+1)e−sλiδ2/16 +2mie−sλi/20mi. (A9) By assumption, δ≤1p2mi; so 1/20mi≥δ2/16 ≥δ2/16mi. It follows that e−sλiδ2/16mi≥ e−sλiδ2/16 ≥e−sλi/20mi, hence (A9) implies P(|b ri t−ri t|> δ)≤(4mi+2)e−sλiδ2/16mi≤6mie−sλiδ2/16mi. This establishes (A1) as claimed. 