PaperlayerView exact revision on arXiv

Source-linked AI summary

Policy Regret in Repeated Games

Raman Arora, Michael Dinitz, Teodor V. Marinov, Mehryar Mohri

arXiv:1811.04127v2cs.LGcs.GTstat.ML

TL;DR

External regret does not account for how an adaptive adversary would react to a different action, motivating the study of policy regret. The paper shows that the measures can be incompatible in adversarial settings, but relates them in strategic games and introduces policy equilibrium. No-policy-regret play converges to policy equilibrium, and coarse correlated equilibria are a strict subset of that set.

  • Problem

    Against adaptive adversaries, external regret does not account for how the adversary would react if the player chose another action.

    Source: §1 · p. 2

  • Method

    The paper compares the two regret notions in adversarial and self-interested game settings, and introduces policy equilibrium to characterize no-policy-regret play.

    Source: §1 · pp. 2–3

  • Results

    Policy and external regret can be incompatible under some adversaries, while no-policy-regret play converges to policy equilibrium, which strictly contains coarse correlated equilibria.

    Source: §1 · p. 3, §3 · p. 4

  • Takeaways & Limitations

    In self-interested strategic settings, a large class of stable algorithms with sublinear external regret also achieves sublinear policy regret.

    Source: §1 · pp. 2–3

    The equilibrium notion requires constant m, and the authors leave extensions to more than two players and richer deviations open.

    Source: §5 · p. 9

Abstract

from arXiv · show

The notion of \emph{policy regret} in online learning is a well defined? performance measure for the common scenario of adaptive adversaries, which more traditional quantities such as external regret do not take into account. We revisit the notion of policy regret and first show that there are online learning settings in which policy regret and external regret are incompatible: any sequence of play that achieves a favorable regret with respect to one definition must do poorly with respect to the other. We then focus on the game-theoretic setting where the adversary is a self-interested agent. In that setting, we show that external regret and policy regret are not in conflict and, in fact, that a wide class of algorithms can ensure a favorable regret with respect to both definitions, so long as the adversary is also using such an algorithm. We also show that the sequence of play of no-policy regret algorithms converges to a \emph{policy equilibrium}, a new notion of equilibrium that we introduce. Relating this back to external regret, we show that coarse correlated equilibria, which no-external regret players converge to, are a strict subset of policy equilibria. Thus, in game-theoretic settings, every sequence of play with no external regret also admits no policy regret, but the converse does not hold.

1 Introduction

The introduction frames online learning against adaptive adversaries, where external regret misses how an opponent might react to a different action. It presents the paper’s results on regret incompatibility, strategic settings, and policy equilibrium.

1 Introduction

  • External regret benchmarks the best fixed action in hindsight, but against an adaptive adversary that benchmark does not account for how the adversary would react to another action.Source: §1 · p. 2
  • In general adversarial settings, sequences with sublinear external regret can have linear policy regret, while sequences with sublinear policy regret can have linear external regret.The introduction contrasts this incompatibility with the relationship between the measures in strategic games.Source: §1 · p. 2
  • In self-interested strategic settings, a large class of stable algorithms with sublinear external regret also achieve sublinear policy regret.The paper considers settings where the opponent seeks to maximize its own utility rather than the player’s regret.Source: §1 · pp. 2–3
  • No-policy-regret play in repeated games converges to a policy equilibrium, a new equilibrium notion that accounts for how other players may react to a deviation.Policy equilibrium is defined using functions rather than actions to capture these counterfactual responses.Source: §1 · p. 3
  • Coarse correlated equilibria form a strict subset of policy equilibria, so no-policy-regret play need not converge to a coarse correlated equilibrium.Source: §1 · p. 3

2 Related work

The related-work section reviews research on policy regret against reactive adversaries and on the link between no-regret learning and game equilibria.

2 Related work

  • Merhav et al. (2002) studied full-observation learning against m-memory-bounded utility functions and gave regret bounds in O(T^2/3).Source: §2 · p. 3
  • Later work treated reactive bandits, memory-bounded adversaries, switching-cost lower bounds, and bandits whose losses evolve with repeated arm pulls.The cited works include Farias and Megiddo (2006), Arora et al. (2012b), Dekel et al. (2014), Koren et al. (2017a, 2017b), and Heidari et al. (2016).Source: §2 · p. 3
  • Prior work connected no-external-regret dynamics to correlated equilibria and extended equilibrium results to stronger regret notions and broader strategy settings.The section cites Foster and Vohra (1997), Fudenberg and Levine (1999), Hart and Mas-Colell (2000), Blum and Mansour (2007), and later extensions.Source: §2 · pp. 3–4

3 Policy regret in reactive versus strategic environments

This section establishes that external and policy regret can conflict against reactive adversaries, then shows how stability in strategic games relates the two measures. It extends the policy-regret framework and states conditions under which no-external-regret players also have bounded policy regret.

3 Policy regret in reactive versus strategic environments

  • The paper extends policy regret to model influence from the entire past, allowing more distant actions to have less significance than recent ones.The section describes the m-memory assumption as somewhat stringent and motivates this extension with decaying influence over time.Source: §3 · p. 4
  • For any constant m ≥ 2, there are m-memory-bounded utilities where every sublinear-policy-regret sequence has linear external regret and every sublinear-external-regret sequence has linear policy regret.Source: §3 · p. 4
  • In the 2-memory example, repeating one action maximizes utility and minimizes policy regret but incurs linear external regret.The passage also states that every sublinear-external-regret strategy in this example has linear policy regret.Source: §3 · p. 4
  • In two-player games, when both players use stable no-external-regret algorithms, the theorem gives bounded policy regret for each player.The result is stated for algorithms with average (m, S(T)) stability and applies against fixed actions.Source: §3 · pp. 4–5
  • The authors report Exp3 and multiplicative weights as examples of algorithms satisfying average stability in the stated setting.Source: §3 · p. 5

4 Policy equilibrium

Policy equilibrium extends equilibrium reasoning to account for how opponents may react when a player deviates. When both players use no-policy-regret algorithms, their empirical play and deviation distributions converge to this equilibrium set, which strictly contains the coarse correlated equilibria.

4 Policy equilibrium

  • Policy equilibrium accounts for opponent reactions by representing play as distributions over functions and comparing stationary play with distributions induced by fixed-action deviations.The definition requires a stationary distribution of the induced Markov chain under which neither player benefits from switching to a fixed action.Source: §4 · pp. 6–7

4.1 Convergence to the set of policy equilibria

  • No-policy-regret play converges to the set of policy equilibria, and the empirical distributions converge there almost surely.The guarantee applies when both players’ algorithms produce sublinear policy regret; MWU and Exp3 are examples given in the text.Source: §4.1 · p. 8

4.2 Sketch of proof of the main result

  • The convergence proof constructs empirical Markov chains and shows that their limits induce a policy equilibrium satisfying the equilibrium inequalities.The proof uses empirical distributions that satisfy those inequalities up to an o(1) additive factor.Source: §4.2 · p. 8
  • Convergence does not require unique stationary distributions, and the sequence need not have a unique limit; the guarantee is convergence to the set S.Any limit point satisfies the policy-equilibrium conditions.Source: §4.2 · p. 8

4.3 Relation of policy equlibria to CCEs

  • Coarse correlated equilibria form a strict subset of policy equilibria: every CCE has a corresponding policy equilibrium, but some policy-equilibrium play is not a CCE.The paper gives a two-player game whose policy-equilibrium play is not a CCE.Source: §4.3 · p. 8

5 Discussion

The discussion identifies open questions about extending policy equilibrium analysis and connecting it to established game-theoretic guarantees. It also notes boundaries involving player count, memory, deviation classes, and stability notions.

5 Discussion

  • Whether smooth-game price-of-anarchy guarantees extend to policy equilibria remains an open question.The discussion frames policy equilibrium as a first step and points to price-of-anarchy and price-of-stability analyses as future directions.Source: §5 · p. 9
  • The equilibrium framework assumes constant memory; extensions to more than two players, superconstant memory, and richer deviations remain open.The text notes that no-policy-regret algorithms do not exist for superconstant memory and that the Markov-chain-based equilibrium notion requires constant memory.Source: §5 · p. 9
  • On-average stability and m-memory boundedness are distinct notions; a unified stability definition for guarantees outside games remains an open question.Source: §5 · p. 9

A Proofs of results from Section 3

The proofs establish an incompatibility between external and policy regret in one setting, then show how stability lets no-external-regret algorithms also achieve no-policy regret. They establish that MWU and Exp3 satisfy the stability property used for that result.

Proof of Theorem 3.2

  • For fixed memory size, a sequence with sublinear policy regret must have utility at least T/2 − o(T), which the proof uses to construct its external-regret comparison.The argument isolates rounds following deviations and compares their utilities to establish linear external regret.Source: A Proofs of results from Section 3 · p. 11
  • A sequence with sublinear policy regret can have linear external regret, and every sequence with sublinear external regret can have linear policy regret.The proof constructs a sequence with sublinear policy regret and linear external regret, then establishes the converse direction.Source: A Proofs of results from Section 3 · p. 11

Proof of Theorem 3.4

  • When both players use no-regret algorithms that are average-stable, each player's policy-regret bound is controlled by the other's utility-matrix norm, stability, and regret.The bound combines the stability term with the player's external-regret term.Source: A Proofs of results from Section 3 · pp. 11–12

Stability proofs for MWU and Exp3

B Proofs of results from Section 4

The proof constructs a stationary distribution for a Markov chain induced by fixing one player's action. Its expected utility matches the corresponding utility under a distribution over function pairs.

Theorem B.1

  • For any distribution over function pairs, the proof establishes a stationary distribution of the fixed-action Markov chain with matching expected utility for player 1.The equality relates utility under the function-pair distribution to utility under the stationary action-pair distribution.Source: B Proofs of results from Section 4 · p. 13

Proof of Theorem 4.4

  • The constructed stationary distribution assigns probability only to states where player 1 plays the fixed action.Its probability on the other player's action is obtained by summing over function pairs that map the fixed action to that action.Source: B Proofs of results from Section 4 · p. 13
  • The construction verifies stationarity by showing that the proposed distribution is unchanged by the fixed-action Markov chain.The transition rule uses the function-pair distribution to determine the next action of player 2.Source: B Proofs of results from Section 4 · p. 13

B.1 Sketch of proof of the main result

The proof sketch represents empirical play and fixed-action deviations with Markov chains, then links their limits to policy-equilibrium inequalities. It concludes that the relevant product distributions converge weakly to the policy-equilibrium set, including for observed play almost surely.

Empirical Markov chains

  • The empirical distributions of algorithm outputs are stationary distributions of empirical Markov chains, and the observed-play distributions approach them almost surely.The same stationary-distribution relation applies to the distributions corresponding to fixed-action deviations.Source: §B.1 · p. 14

Function-pair distributions

  • The proof constructs empirical distributions over function pairs that induce the empirical Markov chains, including chains for fixed-action deviations.The limiting function-pair distribution induces the limiting chains used in the final equilibrium argument.Source: §B.1 · pp. 15–16

Convergence to policy equilibria

  • The product distributions of empirical play and fixed-action deviations converge weakly to the set S when both players' algorithms generate sublinear policy regret sequences.The proof also states that the empirical distributions of observed play converge to S almost surely.Source: §B.1 · pp. 16, 18

Policy-equilibrium limit

  • Limit points of the empirical play and deviation distributions satisfy the policy-equilibrium inequalities, yielding the convergence conclusion.The proof obtains a contradiction if a limit distribution is not a policy equilibrium.Source: §B.1 · p. 18

B.2 Proof that CCEs are a subset of policy equilibria

The section shows how no-external-regret algorithms can converge to a coarse correlated equilibrium while also achieving no policy regret. It then establishes that policy equilibria include distributions that are not coarse correlated equilibria.

B.2 Proof that CCEs are a subset of policy equilibria

  • For any CCE, there are stable no-external-regret algorithms whose empirical play converges to that CCE.The proof uses mini-batches, checks whether empirical play remains close to the target distribution, and switches to Exp3 if the check fails.Source: §B.2 · p. 18
  • With high probability, the algorithm's empirical play converges to the target CCE; a doubling trick extends the result to any time horizon.The proof bounds failure probabilities across epochs and concludes almost-sure convergence.Source: §B.2 · p. 19
  • Every coarse correlated equilibrium of a two-player game is induced as the stationary distribution of a policy equilibrium, and some policy equilibria are not coarse correlated equilibria.The construction uses no-external-regret algorithms that converge to a CCE and also admit no policy regret.Source: §B.2 · p. 20
  • A constructed two-player game has a policy-equilibrium play sequence with linear external regret, so its limiting distribution is not a CCE.This establishes that the inclusion of CCEs in policy equilibria is strict.Source: §B.2 · p. 20

B.3 Auxiliary results.

These auxiliary results bound how changes in distributions affect expected utility and stationary distributions. They also establish convergence of empirical play under the stated conditions.

B.3 Auxiliary results.

  • If two distributions differ by at most ε in L1 distance, their expected values under a utility function bounded by 1 differ by at most ε.The same lemma is used to compare utilities under perturbed distributions.Source: §B.3 · p. 20
  • If two row-stochastic matrices differ by at most ε, each stationary distribution of one has a stationary distribution of the other within 4d^2ε in L1 distance.The bound is stated for matrices in d dimensions.Source: §B.3 · p. 20
  • The empirical distributions of play under the described fixed-action deviations converge almost surely to the set P.The passage identifies the empirical distributions associated with deviations by either player.Source: §B.3 · p. 21

B.4 Concentration of ˜M

The appendix establishes concentration and convergence results for empirical processes, then extends the framework to arbitrary player memories and discusses the difficulty of extending no-policy-regret algorithms to multiple players.

B.4 Concentration of ˜M

  • The empirical transition matrix and its stationary distribution converge almost surely to their averaged counterparts, while the resulting no-external-regret bound is O(T^7/8).The concentration result bounds the number of transition-matrix observations by O(T^7/8).Source: §B.4 · p. 22

C Extending the framework to arbitrary memories

  • With arbitrary player memories, the framework represents play as a memory-bounded Markov process and defines utility using its stationary distribution.The stationary distribution's marginal over the current action pair is used to express expected utility.Source: C Extending the framework to arbitrary… · p. 23

D Extending the framework to arbitrary number of players

  • For multiple players, other players' memories affect a player's utility, complicating its interpretation as a memory-bounded function and the construction of no-policy-regret algorithms.One proposed approach treats the utility as memory-bounded using the maximum memory of the other players.Source: D Extending the framework to arbitrary… · p. 24

E Simple example of a policy equilibrium

A two-player example exhibits a policy equilibrium that is not a CCE and gives both players asymptotically maximum utility over repeated play. The row player's no-policy-regret strategy earns 3/4, whereas switching to action b yields 0.

E Simple example of a policy equilibrium

  • The example constructs a policy equilibrium that is not a CCE and gives both players asymptotically maximum utility over repeated play.The column player has equal payoffs across actions and plays a function mapping the row player's action to its response.Source: E Simple example of a policy equilibrium · pp. 24–25
  • The row player's resulting utility is 0, compared with 3/4 from playing according to π; under policy-regret play, empirical play converges to δ(a,c).Source: E Simple example of a policy equilibrium · p. 25

Related papers

Loading 1811.04127v2…