Is Learning in Games Good for the Learners?
Authors: William Brown
Jon Schneider
Kiran Vodrahalli
Venue: NeurIPS 2023 spotlight (2023)
Keywords: learning in games
correlated equilibria
Stackelberg equilibria
swap regret
dynamic regret
TL;DR: Tradeoffs between reward and regret for learning in 2-player games: deviating to higher regret is often better for reward

Abstract: We consider a number of questions related to tradeoffs between reward and regret in repeated gameplay between two agents. To facilitate this,  we introduce a notion of generalized equilibrium which allows for asymmetric regret constraints, and yields polytopes of feasible values for each agent and pair of regret constraints, where we show that any such equilibrium is reachable by a pair of algorithms which maintain their regret guarantees against arbitrary opponents. As a central example, we highlight the case one agent is no-swap and the other's regret is unconstrained. We show that this captures an extension of Stackelberg equilibria with a matching optimal value, and that there exists a wide class of games where a player can significantly increase their utility by deviating from a no-swap-regret algorithm against a no-swap learner (in fact, almost any game without pure Nash equilibria is of this form). Additionally, we make use of generalized equilibria to consider tradeoffs in terms of the opponent's algorithm choice. We give a tight characterization for the maximal reward obtainable against some no-regret learner, yet we also show a class of games in which this is bounded away from the value obtainable against the class of common "mean-based" no-regret algorithms. Finally, we consider the question of learning reward-optimal strategies via repeated play with a no-regret agent when the game is initially unknown. Again we show tradeoffs depending on the opponent's learning algorithm: the Stackelberg strategy is learnable in exponential time with any no-regret agent (and in polynomial time with any no-adaptive-regret agent) for any game where it is learnable via queries, and there are games where it is learnable in polynomial time against any no-swap-regret agent but requires exponential time against a mean-based no-regret agent.

Is Learning in Games Good for the Learners?
William Brown Columbia University w. brovm@columbaa.ede edu
Jon Schneider Google Research jachnei jachnei@google com
Kiran Vodrahalli Google Research kirannv@google. com
Abstract
We consider a number of questions related to tradeoffs between reward and regret in repeated gameplay between two agents. To facilitate this, we introduce notion of generalized equilibrium which allows for asymmetric regret constraints, and yields polytopes of feasible values for each agent and pair of regret constraints, where we show that any such equilibrium is reachable by a pair of algorithms which maintain their regret guarantees against arbitrary opponents. As central example, we highlight the case one agent is no-swap and the other's 's regret is unconstrained. We show that this captures an extension of Stackelberg equilibria with a matching optimal value, and that there exists a wide class of games where a player can significantly increase their utility by deviating from no-swap-regre, algorithm against a no-swap learner (in fact, almost any game without pure Nash equilibria of this form). Additionally, we make use of generalized equilibria to consider tradeoffs in terms of the opponent's 's algorithm choice. We give a tight characterization for the maximal reward obtainable against some no-regret learner, yet we also show class of games in which this is bounded away from the value obtainable against the class of common "mean-based no-regret algorithms. Finally, we consider the question of learning reward-optimal strategies via repeated play with a no-regret agent when the game is initially unknown. Again we show tradeoffs depending is learnable in exponential time with any no-regret agent (and polynomial time with any no-adaptive reegeet agent) for any game where it is learnable via queries, and there are games where it is learnable in polynomial time against any no-swap- regret agent but requires exponential time against mean-based no-regret agent.
the opponent's 's learning algorithm: the Stackelberg strategy
Introduction
How should two rational agents play a repeated, possibly unknown, game against one another? One natural answer barring any knowledge of the game, or the capacity to compute potentially computationally intractible equilibria is that they should employ some sort of learning algorithm to learn how to play over time. Indeed, there is vast literature which studies what happens when all the players in repeated game run (some specific type of) learning algorithms to select their actions. For example, when all players a game simultaneously run (o-(swa))-regree learning algorithms, is known that the average strategy profile of the learners converges to (coarse) correlated equilibrium (23; 11; 16). More recent works have studied how design algorithms that converge to these equilibria faster rates (7; 1; 8), performance guarantees of such equilibria compared to the optimal possible welfare (4: 17), and the specific dynamics of such learning algorithms (9; 20; 22).
In contrast, relatively little attention has been devoted to whether it is actually in the interest of these agents run these specific learning algorithms. For example. in setting where all agents are running swap-regret learning algorithms, when can an agent significantly benefit by deviating and running a different type of algorithm? And if they can, what algorithm should the agent deviate to?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1
Our results
We explore the following questions (and others) in the case where two agents repeatedly play a normal-form, general-sum game for T rounds.
When does reward trade off with regret? While maximizing reward is often viewed as the objective of regret minimization against arbitrary adversaries, tensions may emerge when playing against another learning agent, as one's s choice of actions has a causal effect on future loss functions as determined by the opponent's 's algorithm. In such cases, as we discuss further below, it turms out that demanding a stronger regret guarantee (e.g. asking for no-swap-regre instead of to-ext)rma-rreret) may ultimately result in lower reward for an agent. To analyze these tradeoffs. in Section we introduce a notion of generalized ( A, @ -equiliibrr,m where A and @B are the sets of "deviation strategies" over which players A and B minimize regret (e.g. fixed actions or swap functions), presented as an asymmetric extension of the linear Φ-equilibria considered by (13). Each pair of strategy sets (Q,, &B) generates polytope of (Ø A. & B) -equilibb,,, where any point then yields reward value for each player. We show that all such points are feasible: for any game and any ($ A, (P)--quilibriuu
yp, there is a pair of algorithms which converge to s while maintaining their respective 4 r-erett and gerrreret guarantees against arbitrary opponents. Further, deviating to strategy with fewer constraints & A can often result in strictly improved reward for player A. As a concrete application, we consider the question of deviating from simultancous no-swap-regret play.
When is no-swap-regret play a stable equilibrium? What should you do if you know that your opponent in repeated game is running no-swap-regre algorithm to select their actions? In (10), the authors show that one utilit--ptimizing response (up to additive o(T) factors) is to play static (mixed) strategy (your Stackelberg strategy) and obtain the Stackelberg value of the game. However, determining your Stackelberg strategy requires some knowledge of the game, and acquiring this knowledge from repeated play may be difficult (we address the latter issue in Section 5). In comparison, it is relatively straightforward to also run no-swap-regret learning algorithm. This begs the question: are there games where you obtain significantly less utility (i.e., at least (2(")) less utility) by running no-swap-regret learning algorithm instead of playing your Stackelberg strategy?
We show that the answer is yes, such games exist and are relatively common. In fact, we provide an efficient algorithmic characterization of the games G for which both players playing a no-swap-regre learning algorithm an
Nash equilibrium of the entire repeated "meta- "meta-game", The exact characterization is presented in Section 3 and is somewhat subtle, e.g., there are slightly different characterizations depending on whether we insist all pairs of no-swap-regret algorithms lead to approximate equilibria or only one specific pair, corresponding to best-case and worst-case values in the generalized equilibrium polytope. One consequence of both characterizations, however, is that for almost all games (in treasure-theoretie sense, considering arbitrarily small perturbations), in order for to be an approximate equilibrium for both players to play a low-swap regret strategy, the game G must possess a pure Nash equilibrium. That is, in any game without pure Nash equilibrium, it is possible for at least one of the parties to do significantly better by switching from no-swap-regret learning to playing their Stackelberg strategy.
Finally, we additionally show there are some games where playing a no-(external)-ree regret algorithm against another no-swap-regret learner weakly dominates playing no-swap-regret algorithm, regard- less of the specific choice of algorithms. This counters the intuition that stronger regret guarantees protect a player from worse outcomes.
Optimizing reward against no-regret learners. What if our opponent is not running a no-swap- regret algorithm, but simply a (o-ee algorithm? In this case, it still possible obtain at least the Stackelberg value of the game by playing our Stackelberg strategy (no-regret algorithms are also guaranteed eventually learn and play the best response to this strategy). However, unlike in the no-swap-regret setting, there exist specific games and no-regret algorithms where it is possible to obtain significantly (S2(T)) more than the Stackelberg value by playing a specific dynamic strategy. This phenomenon was first observed in (10), where a specific game is given for which it is possible to obtain Q(T)) more than Stackelberg when playing against any no-regret algorithm in the family of mean-based learning algorithms (including algorithms such as multiplicative weights and EXP3). However, many questions remain unanswered, such as understanding in which games it is possible to outperform playing one's 's Stackelberg strategy, and by how much.

---

In Section 4 we present some answers to these questions for the case of generic no no-regret algorithms. Specifically, we first show that if player B is running (any) no-regret algorithm. the utility of player A (regardless of what strategy they employ) is upper bounded by Val (6, E) T + o(T), where (equilibrium) value of the game for player
Val (0, E) is what we call the the uncomstrained--exeene A, which is given by the solution to linear program. We then show that this upper bound is asymptotically tight: there exists a no-regret algorithm C such that if player B is playing according to L. then the player A can obtain utility at least Val (0, T - o(T") by playing an appropriate strategy in response.
Note that this characterization does not completely resolve the question of (10) it requires the construction of a fairly specific no-regret algorithm L, and it is still open what possible against specific (classes of) no-regret algorithms (c.g., multiplicative weights or mean-based algorithms). In fact, we show a property of games which, when satisfied, implies that is impossible to obtain the unconstrained-exteni value against a mean-based learner.
Learning the Stackelberg strategy through repeated play. Finally, we address the question of how hard it is to actually identify the Stackelberg strategy in a game against learning opponent. Given full knowledge of the game G, finding an agent's Stackelberg strategy is simply a computational problem which turns the game (in particular, the opponent's 's reward matrix) is unknown, an agent must learn the Stackelberg strategy over time. Existing work on learning Stackelherg strategies (e.g.. (19; 24)) generally assumes access to a best-response oracle for the game (i.e., for specific mixed strategy, how will an opponent best-respond?). In contrast, if our opponent is playing a specific no-regret learning algorithm, they may not immediately best respond to the strategies we play! This raises the following two questions. First, when it possible learn the Stackelberg equilibrium of a game while playing against a learning opponent? Second, is it easier to learn this equilibrium when playing against certain classes of learning algorithms?
be efficiently solvable by solving several small LPs (see (6)). However, if
In Section 5 we begin by showing that it is indeed possible to convert any best-response query algorithm for finding Stackelberg equilibria via best-response queries to an adaptive strategy that learns Stackelberg equilibria via repeated play against a generic no-regret learner, albeit potentially at the cost of an exponential blow-up in the number of rounds, e.g. for query algorithm which makes Q best-response queries, simulating it against a no-regret learner may require T = exp(() (Q) rounds of play. For the special case of opponents with no-adaptive-regret algorithms (such as online gradient descent), we show that only T = poly(Q) rounds are required in the worst case. However, in general we show that exponential runtime can be necessary. In particular, we give an example of game with M actions where it is possible to learn the Stackelberg equilibrium in (Ml rounds when playing against any no-swap-regret learning algorithm, but where it requires at least exp (M) rounds to learn this equilibrium when playing a mean-based no-regret algorithms.
1.2 Related work
The broader literature on no-regret learning in repeated games is substantial, covering many equilib- rium convergence results varying assumptions. A recent line of work (5; 10; 21) considers problems related to optimizing onc's 's reward when competing against a no-regret learner in a game. We extend these questions to consider the relationship and regret for an optimizer, properties of the game are initially unknown, and give a series of separation results in terms of various notions of equilibrium. Also relevant is the literature on analysis of no-regret trajectory dynamics, and in particular (20) which shows a game in which no-regret dynamics outperform the reward of the Nash equilibrium. Additionally, there is also prior work considering regret minimization problems involving either best-responding or otherwise strategic agents (see e.g. (3; 18)), as well as work considering alternate regret notions or behavior models for repeated Stackelberg games (e.g. (12; 15)).
well as to settings where
1.3 Notation and preliminaries
Throughout, we consider two-player bimatrix games G = BA, where player A ("the optimizer") has action set A {ai,..., and player ("the learner") has action set B = (bi,...,bn ). When the optimizer plays action o; and the learner plays action by. the players receive rewards A (as; by) and u (a;, by), respectively. We assume that the magnitude of each utility is bounded by constant. The sets of mixed strategies for each player are denoted by A(A) and A respectively;
3

---

when the optimizer plays mixed strategy a E (A)) and the learner plays 8 E A the expected au by), with up (a, () defined reward for the optimizer is given by us(a, B) Σ i=1 وj=1
M
analogously. An action b E B is best response to strategy ((A) if E argmaN ug (a, b)). We let (R(a) (a) be the set of all such actions for player B, and likewise (R(3) for player A.
2 Generalized equilibria and no-E-regret learning
Here we introduce the notions of #-regret and generalized equilibria, which we use to analyze the regret and reward of players in repeated bimatrix games under varying assumptions regarding the choice of regret benchmarks, the algorithms used, and the structure of the game.
Originally introduced in (14) and extended to general convex settings in (13), we consider the formulation of linear Ø-regret as it relates to bimatrix games. Given sequence of action pairs (o,, bb ...., (ir for I" >> 0 and some set of functions 4, where each f E & maps actions A to action profiles in (AA), we say that the P-regrer for the optimizer (and analogously for the learner) is
Reg, (T) = max fE
u uA(s(a;)))))) -a:--uusaaa (as bj.)-
Definition 1 (No-p-regret learning). We say learning algorithm L is no- r-regret algorithm if. for some constant c < 1, we have that Reg (C, T) = O(T)), where (e, is the D-regret corresponding to the action sequence played by L.
Some notable sets of regret comparator functions & are the constant maps & (corresponding to external regret), where all input actions are mapped to the same output action, and the "swap functions" I (corresponding to internal regret') ), which contain all single swap maps fú; [M] + [M] where f(i and f(²) i' for i' + i. Imposing these constraints on players in a game results in a (coarse) correlated equilibrium, which are instances of our notion of generalized equilibrium.
(4A, & -equilibrium vp E A x B) in a two-player game is joint distribution over action profiles (a.b) such that player A cannot increase their expected reward by deviating with some strategy in t A and player B cannot benefil by deviating with some strategy in BB.
Definition 2 (Generalized
In contrast to the -e-quilia considered by (14; 13), here we allow constraints to be asymmetric between players. While many equilibrium notions for two-player games impose symmetric regret constraints on each player (c.g. Nash, correlated, and coarse correlated equilibria), this need not always be the case. In Section we highlight Stackelberg equilibria as a motivating example for considering more general notions of asymmetric equilibria from the perspective of 4-regret, to determine when one should deviate from simultaneous no-swap play, and in Section 4 we characterize the maximum reward attainable against no-regret learners in terms of asymmetric equilibria.
We say that the value of a game G' for player A of certain equilibrium class (L,,, Dn), denoted Vala A ( A, pn)) is the maximum reward obtainable by player A at some (ΦA, $ Jequiiibiir (with Valn ( A; &D)) defined symmetrically for player B). Likewise, we say that the min-value of game for a player and an equilibrium class, denoted by e.g. MinVal (T A. h for player A, is the minimum reward for player over all (4 A. 4 - equilibria
game. These capture the range of feasible average rewards under repeated play via (4 4 B)) reereettt dynamics.
Proposition 1. For a repeated game over T rounds where player A uses a no- A A-rgret algorithm and player B uses no- 10 -regrrtt algorithm, the average rewards obtained by each player are upper bounded by Val (2 A, 2b) + o(1) 1) and Valg (1 A. 4B) + o(1), respectively, and lower bounded by M ( p o11 and MinVal (D 4B) o(1)
We consider an e-approximate A$A, T ( to be a joint profile distribution where each constraint is satisfied up additive error e, connecting Definitions and follows.
Proposition 2 (Convergence of no- rerrert dynamics to generalized equilibrium). Suppose after T rounds of a game where player plays no- n A-regret algorithm and player plays a no Beeggret algorithm, player A has average A < E and player B has average 4 D--regret E. Let
We refer internal and swap regret interchangeably, focus is primarily on rates with respect to T.

---

o² p'A P'B denote the joint distribution over both players' actions at time and 9 : + E o denote the time-averaged history over joint player action distributions. Then, ip is an E-approximate (DA, @ -equilibbrr where
[ua (a, b)] 2
E
[U (f^(a), - E, and
(a.6)aup
(a.b)mup
E LB (a, b]] 2
E
lu (a, fb(())]
(a.b)mup
(a.b)ru
for every possible deviation FA fA. -g- Likewise, if players A and B repeatedly play strategies corresponding to an AR DB eqquilibruu, then player A is no- A A-regret and player B is no- pregret.
A general construction for no-f-regret algorithms is given in (13), which immediately implies feasibility of dynamics which converge to some instance of any class of (+) A. & ( in a game, possibly requiring agents use differing algorithms if constraints are asymmetric. We show that a much stronger claim is true: such a pair of algorithms cxists for any (ΦA. 2 -equuiiiib y in game. These algorithms also satisfy y when played together, yet simultancously maintain their corresponding regret guarantees against arbitrary adversaries.
property, in that they converge to
Theorem 1. Consider any game G. Suppose there exists a no- A-regret learning algorithm LA and no- n- n-regret learning algorithm LB- For any particular (D,, -e)-eiiibirr V in a game G, there exists pair of learning algorithms (f'A ( (ib(()))))))) such that:
* The empirical sequence of play when Player A uses (V) and Player B uses (V) converges to
(VV) and (D) are no-$--regret and no-Dg-regret, respectively, against arbitrary adversaries.
Our approach is for the algorithms to initially implement a schedule of strategies which converges V. Yet, these algorithms also detect when their opponent disobeys the schedule by tracking their 2-regret with respect to V and after o(T') violations can deviate indefinitely to playing a standalone no- no-P--algorihmm for all remaining rounds. Several of our results throughout make use of Theorem 1. Here we state notable immediate implication for equilibrium selection.
Corollary 1.1. For any equilibrium scoring function r A(A B) R. with unique optimum computable in finite time, there exists a pair of learning algorithms (L',, (z)) such that:
The empirical distribution when player A uses LA) and player B uses C converges to argmax I'
L" and Ln are A-regret and no- no-o-----eeeee grrggret, respectively, against arbitrary adversaries.
Proof. First optimize I' over v in finite time to find the unique optimum; then apply Theorem to the resulting desired equilibrium.
Corollary 1.1 allows for optimizing for objectives such as total welfare or min-max utility for both players, and imposing conditions on generalized equilibria beyond d-regret constraints (e.g. product constraints for Nash equilibria) by assigning arbitrarily low scores to invalid strategy profiles.
In subsequent sections, we will primarily focus the function classes E and I corresponding to external and internal regret as mentioned above, as the well empty set () corresponding to unconstrained regret, and we additionally will consider the case when the game G is initially unknown. Before continuing, we note that each player's values for any ( A. $B) -qquilibrium class can be expressed via linear program, whose size is polynomial in the game dimensions for these function classes of interest.
Proposition 3. For any game G and constraints A4, BB) both Val A (4,,, A, 2B) and Valg (# 4b) are computable via linear programs with MN variables and poly( M, N, | 4 constraints. When A and & belong to {0,E,1 E), the number of constraints poly (M,
In general, these values for a player may differ under distinct notions generalized equilibria; we give several examples of such concrete value separations in Appendix A (in Theorem 8). Our results Section illustrate a particularly stark separation of this form, in which can often be dominant to deviate to strategy where &-regret constraints are violated.
5

---

3 Stability of no-swap-regret play
Here we address the following question: when is it the case that for two players game, is an approximate (Nash) equilibrium for both players to play no-swap-regret strategies? More specifically, imagine a "metagame" where at the beginning of this repeated game, both players simultaneously announce and commit to specific adaptive (and possibly randomized) algorithm they intend to run to select actions to play in the repeated game for the next T rounds. this metagame, for which games G' is it an of -approxmmtt Nash equilibrium for both players to play no-swap-regret learning algorithm?
Of course, the answer to this question might depend on which specific no-swap-regret learning algorithm the agents declare. We therefore attempt to understand the following two questions:
Necessity: For which games G is it the case that there exists some pair of no-swap-regret al- gorithms which form a aapprrxxiit Nash equilibrium? (Equivalently, when is it never the case that playing no-swap-regret algorithms forms an approximate Nash equilibrium?)
Sufficiency: For which games G is it the case that all pairs of no-swap regret algorithms form -apprxiimte Nash equilibria?
central element our analysis will be to consider the Stackelberg equilibria of a game.
Definition (Stackelberg Equilibria). The Stackelberg equilibrium of a game G for player the pair of strategies (a, b) given by argmax bEBR(a) u (ax, b), and the resulting expected utility for player A is the Stackelberg value of the game, denoted Stack Stack is defined symmetrically.
We can relate Stackelberg equilibria to our notions of generalized equilibria.
Proposition 4. For any game G, we have that Stack = Val (0, Z).
Here, any joint distribution over action profiles where player B has zero swap regret constitutes a (0, -)-quiiiirr for game, and the optimal value for such an equilibrium for player A coincides with the Stackelberg value. Further, each equilibrium set can be optimized over via linear program.
Note that each value definition allows for tiebreaking in favor of player A. In general, simply playing the Stackelberg strategy a may not suffice to obtain Stack A if the best response for Player B is not unique. However, there are a number of mild conditions which are each sufficient to ensure the existence of an approximate Stackelberg strategy a' which yields a unique best response for player B and obtains Stack -E for any > 0. Here we consider minimal such condition (essentially, no action is weakly dominated without also being strictly dominated).
Assumption 1. In game G. for each b, either BR(a) {b) for some a, or & BR(a) for all a. Likewise, for each a, either BR(3) = {a} for some 3, or & BR(3) for all 3.
We provide an efficient algorithmic procedure to answer both questions of necessity and sufficiency for specific game G satisfying Assumption 1. To do this, recall that when two players both employ no-swap regret strategies, they asymptotically (time-average) converge to some correlated equilibrium (here, corresponding to an (I, -eqquiuliibr) On the other hand, by defecting from playing no-swap regret strategy (while the other player continues playing their no-swap regret strategy), player can guarantee their Stackelberg value for the game. Moreover, the optimal (up to o(T) additive factors) best response to an opponent running a no-swap regret strategy. It thus suffices to understand how the utility a player might receive under correlated equilibrium compares to the utility they receive under their Stackelberg strategy. For a fixed game G, let Stack,, 1 Val (6, I) be the Stackelberg value for the first player, and Stack Val (I, be the Stackelberg value for the second player. We have the following theorem.
shown by (10), this is
Theorem 2. Fix a game G satisfying Assumption 1. The following two statements hold:
1. There exists some pair of no-swap-regret algorithms that form an of -approaoote Nash equilibrium in the metagame iff there exists correlated equilibrium up in G such that u (pp) Stack a and up({p) Stack
2. Any pair of no-swap-regrel algorithms form an oap))appeo Nash equilibrium the metagame iff for all correlated equilibria up in G. Uy())) Stack and uz({p) = Stack

---

Moreover, given game G, it is possible to efficiently (in polynomial time in the size of G) check whether each of the above cases holds.
We obtain both claims by leveraging the construction in Theorem I: best-case and worst-case correlated equilibria are feasible by some pair of no-swap-regret algorithms, and both players must simultancously achieve close to their Stackelberg value for deviating to not be preferable. The characterization in Theorem is algorithmically useful, but sheds little direct light on in which games or how often we would expect playing no-swap-regret to be an approximate equilibrium. It turns out that for many games, playing no-swap-regret is not an equilibrium; below we will show that for almost all games, if G does not have pure Nash equilibrium, at least one player has an incentive to deviate to their Stackelberg strategy.
Definition 4. A property P of a game holds for almost all games if, given any game G. property P holds with probability for the game G" formed by starting with G and perturbing each of the entries u. uA(a;, b5) and ug(a; (as, by) by independent uniform random variables in the range [-e,a] (for any choice of E). In other words, the property holds for almost all choices of the 2M utility values that define a game (with respect to the standard measure on this space).
Theorem 3. For almost all games G, if G does not have a pure Nush equilibrium, then there does not exist a pair of no-swap-regre algorithms which form a -apprppxxii Nash equilibrium in the metagame for G.
Sketch. We can show that if correlated equilibrium has the same utility for a player as their Stackelberg value (a consequence of Theorem 2), then the correlated equilibrium must be a convex combination of valid Stackelberg equilibria. In almost all games, both players have unique Stackelberg equilibria (and Assumption 1 holds), which implies that this correlated equilibrium must actually be the Stackelberg strategy for both players simultaneously. This implies that it is a pure Nash equilibrium (since one action in a generic Stackelberg equilibrium is always pure).
Note that although Theorem holds for almost all games, there are some important classes of games (most notably, zero-sum games) in the measure zero subset omitted by this theorem statement that both a) do not have pure Nash equilibria and b) have the property that playing no-swap-regret algorithms is an approximate equilibrium in the metagame (in particular, for zero-sum games, the Stackelberg value collapses to the value of the unique Nash equilibrium). Still, Theorem shows that there are very wide classes of games for which playing no-swap-regret algorithms is not stable from the perspective of the agents.
Finally Theorem 3 requires that we deviate to our Stackelberg strategy, which may be hard to compute. One can ask whether there are games where efficient deviations - e.g., to algorithms with weaker regret guarantees- - lead to strictly more utility for the deviating player. In Appendix B we show this is true in the following sense: there are games where (E, > MinVal = (I. That is, in such game player A can possibly strictly increase their utility by switching to low- external-regret strategy, and such a switch will never decrease their utility.
4 Optimal rewards against no-regret learners
Here, we characterize the feasibility of optimizing one's reward against no-(extermal)-regre learners in terms of generalized equilibria. In contrast to the case of no-swap-regret learners, as shown by (10) there are games in which one can obtain 12(T) more than the Stackelberg value over T rounds against certain no-regret algorithms by playing an appropriate adaptive strategy. A major remaining open question from this line of work is determining the best feasible reward and corresponding optimal strategy against no-regret agents in arbitrary games. We resolve this question when considering the maximum over all possible no-regret algorithms: for any game, we can compute an upper bound on the feasible reward against any no-regret algorithm, and we show that there exists a specific no-regret algorithm against which we can obtain this reward via an efficiently implementable strategy.
Theorem 4. For any game G, there exists a no-regret algorithm C and a strategy for player A such that the total reward of player A converges to Val (9, E) T + o(T") when player B uses L.
Here we again make use of the construction from Theorem 1. Note that by Proposition 1, this is optimal over all no-extermal-reere algorithms, any adaptive strategy constitutes a no-O-regret
7

---

algorithm. By Proposition 3 we can identify the optimal (0, eqquilibriu in poly(M,N) time, which is sufficient to implement the algorithm L as well as our own strategy efficiently.
However, we additionally show that this bound is often unattainable against many standard no- external-regret algorithms. A property of many such algorithms (including Multiplicative Weights, Follow the Perturbed Leader, and Exp-3) is that they are mean-based as formulated by (5).
Definition 5 (Mean-based learning). Let Ti, be the cumulative reward resulting from playing action i for the first rounds. An algorithm C is t-mean-basel if. whenever Tie S jjt - -T,, the probability that the algorithm selects action in round 1 1 is al most 7, for some 7 ((1)
These algorithms resemble "smoothed" variants of Follow the Leader; they only play actions with probability higher than o(1) if their cumulative reward thus far is not too far from optimal, and hence never play dominated strategies. However, in general, (9, -''uuibiii may contain dominated strategies, is also the case for coarse correlated equilibria. This allows us to show the following.
Theorem 5. Against any mean-bused no-regret algorithm for player B, there are games where a T-round reward of A (0, I) + +a) ' cannol be reached by any alaptive strategy for player for any E > 0. However, for this same game, Val > (0.
In the appendix, we introduce a notion of "dominated-swappin external regret" which we use to characterize class of games for which this holds, and we give concrete example of such a game.
5 Learning Stackelberg equilibria in unknown games
Our results thus far have highlighted the primacy of the Stackelberg reward as an objective for repeated play against a learner: it is optimal against a no-swap learner and can sometimes be optimal against a mean-based learner, and it is almost always attainable against any learner. However, until now our strategies have assumed knowledge of the entire game, which may be unrealistic in many settings for which learning in games is relevant, particularly terms of our opponent's rewards.
Here, we consider the challenge of learning the Stackelberg strategy via repeated play against a no-regret learner when only own rewards are known, which is unaddressed in the literature to knowledge; much of the prior work on learning Stackelberg equilibria assumes a query model, where one can observe the best response BR(a) played by an opponent for any queried mixed strategy a. While here we cannot immediately observe the best response of an opponent, as their actions are selected by learning algorithm which may be slow to adapt changes in our behavior, we give reduction from query algorithms of this form to strategies for choosing our actions which enable us to simulate queries BR(a) against learner, and we analyze the efficiency of this approach (in terms of rounds required for learning) under differing assumptions on the learner's 's algorithm.
For comparison of behavior across time horizons of varying lengths, it will be convenient for us to consider the notion of an anytime regret bound, which can be obtained from any base no-regret algorithm via doubling methods, well often via learning rate decay.
Definition 6 (Anytime regret algorithms). An algorithm is an anytime no- no-P-regret algorithm if satisfies Reg., (I) = ((1) over the first rounds, for some c and any 1 T.
We also recall the notion of adaptive regret; many no-external-regret algorithms such as Online Gradient Descent satisfy no-adaptive-regre bounds (see e.g. (25)).
Definition 7 (Adaptive regret algorithms). An algorithm for player
sendapptive--regree algorithu if suP] Reg (C, ()) < O(T"), for some < 1, where Reg, (C, s)) = un up(a,, (a,, b,.)
fax Li ((b,))
key distinction between adaptive-regret algorithms like OGD and mean-based algorithms like FTPL is in in their "forgetfulness". and hence their ability to quickly adapt when rewards change. This has stark implications for the efficiency of learning Stackelberg equilibria, which we show can take exponentially longer against mean-based algorithms. As shown by (25), adaptive regret is closely connected with dynamic regret; we note that our results for adaptive-regret learners can also be extended to dynamic-regret learners.
8

---

5.1 Simulating query algorithms
Our approach will be to compute an e-approximate Stackelberg strategy by simulating best response queries against learner, after which point we can obtain an average reward upproaching Stack in each subsequent round, calibrating E in terms of T as desired. The query complexity for such algorithms can depend on the geometry of the best response regions of the game, and unfortunately, as shown by (24), there are "hard" game instances which require exponentially many queries. This issue arises when the best response regions may be quite small but non-empty, even finding point therrtticalyy difficult. We restrict our attention to games in which this
in each region is does not occur, and fortunately efficient query do algorithms exist for this case.
Assumption 2. For game G and any action by, have that
Pr a--Unf((A(M)
[b. E BR(a)) E (0) U [1/ poly(e 1],
i.e. the volume of each BR region is either 0 or inverse polynomially large.
Proposition 5 ((19; 24)). For a game G satisfying Assumption 2. there is an algorithm which finds an E-approximate Stackelberg strategy for player A with Q poly(M, 1/s/ queries to BR(a).
We note that while such algorithms indeed obtain tighter approximation guarantees in terms of (e.g. (llo((/E))) the query complexity is still inverse polynomially related to the best response region volumes; we consider only e-approximate equilibria due challenges which are inherent to the no-regret learning setting, as the precision with which we can simulate a query is constrained by our time horizon. The key our approach is to play according the relevant window of the learner's history, which induces them to play a best response. Against no-adaptive-regret learners, best response will be induced quickly, their regret is bounded even over small windows. However, for arbitrary no-regret learners, we have no promises other than the cumulative regret bound, which may require saturating the entire history for each query.
mixed strategy until it saturates
Theorem 6. Suppose & C 4. For a game satisfying Assumption there is an algorithm which finds an s-approximate Stackelberg strategy in p rounds against any anytime-no-Pe no-e-regrett learner, and in poly(Q/e) rounds against any no-adaptive -eriptivvv----egeeer calibrated for T ( (Q/e)), where Q = poly( M, 1/E).
5.2 Efficiency separations for mean-based and no-swap algorithms
We show here that the exponential dependence for mean- baaed algorithms is necessary: there exist games where learning the Stackelberg strategy requires exponentially many rounds against a particular mean-based algorithm. However, for the games we construct, we show that it is still possible to efficiently learn the Stackelberg strategy against a no-swap-regret learner.
Theorem 7. There is distribution over games 'D such that for a sumpled game G:
For any no-swap-regne learner used by the opponent, there is a strategy for the leader which yields an average reward of Stack -E in T (oly(M// rounds.
There is mean- beean- no-regret algorithun such thut, when used by the opponent, there is no strutegy for the leader which yields an average reward of Stack - over T rounds unless T exp(Ω(M))
Our construction includes a set of actions for player which are best responses to pure actions from player A. and one such pure strategy pair will necessarily constitute the Stackelberg equilibrium; identifying each best response suffices for player A to identify the Stackelberg strategy. The game also includes a number of safety actions for player B, which yield no reward for player A with any strategy, yet allow player B to "hedge" between multiple actions of player A. This poses a barrier to optimizing against a mean-bast based learner: the history must be heavily concentrated on a single action to observe the best response, and as such the history length must grow by constant factor for each observation. However, against a no-swap-regret learner, it suffices for the optimizer to only play each action for a polynomially long window in order to identify the learner's 's best response; we track the accumulation of "swap-regret buffer" for any other action and show that it cannot be too large, limiting the number of rounds it can be played when it is not a current best response.

---

References
[1] loannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 736-749, 2022.
[2] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(6):121-164, 2012.
[3] Maria-Florina Balean, Avrim Blum, Nika Haghtalab, and Ariel Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC 15, page 61-78, New York, NY, USA, 2015. Association for Computing Machinery.
[4] Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimiza- tion and the price of total anarchy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 373-382, 2008.
[5] Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg, Selling to no-regret buyer. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 523-538, 2018.
[6] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce, EC '06, page 82-90, New York, NY, USA, 2006. Association for Computing Machinery.
[7] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235-254. SIAM, 2011.
[8] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances Neural Information Processing Systems, 34:27604-
27616, 2021.
[9] Constantinos Daskalakis, Rafael M Frongillo, Christos H Papadimitriou, George Pierrakos, and Gregory Valiant. On learning algorithms for nash equilibria. In SAGT, pages 114-125. Springer, 2010.
[10] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. Advances Neural Information Processing Systems, 32, 2019.
[11] Dean P Foster and Rakesh V Vohra. Asymptotic calibration. Biometrika, 85(2):379-390 1998.
[12] Denizalp Goktas, Jiayi Zhao, and Amy Greenwald. Robust no-regret learning in min-max stackelberg games, 2022.
[13) Geoffrey J. Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th International Conference on Machine Learning, ICML. '08, page 360-367, New York, NY, USA, 2008. Association for Computing Machinery.
[14] Amy Greenwald and Amir Jafari. general class of no-regret learning algorithms and game- theoretic equilibria. In Bernhard Schölkopf and Manfred K. Warmuth, editors, Learning Theory and Kernel Machines, pages 12, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
[15] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alex Wei. Learning in stackelberg games with mon-myopic agents, 2022.
[16] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilib- rium. Econometrica, 68(5):1127-113 2000.
[17] Jason Hartline, Vasilis Syrgkanis, and Eva Tardos. No-regret learning in bayesian games. Advances in Neural Information Processing Systems, 28, 2015.
10

---

[18] Zhiyi Huang, Jinyan Liu, and Xiangning Wang. Learning optimal reserve price against non- myopic bidders. CoRR. abs/1804. 1060, 2018.
[19] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory, 2009.
[20] Katrina Ligett and Georgios Piliouras. Beating the best nash without regret. SIGecom Exchanges, 10(1))23-26, 2011.
[21] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against learners in bayesian games. In Conference on Learning Theory, pages 5221-5252. PMLR, 2022.
[22] Panayotis Mertikopoulos. Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 2703-2717. SIAM, 2018.
[23] Hervé Moulin and J P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7:201-221, 1978.
[24] Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In Proceedings of the Thirly-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovalive Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, 1ААГ11/AАT 19/EAA119. AAAI Press, 2019.
[25] Lijun Zhang, Tianbao Yang. Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In International Conference on Machine Learning, 2017.

---

A Properties and separations for generalized equilibria
A.1 Proof of Proposition
Proof. The set of (Ø) A. & L includes all strategy profile distributions in which both con- straints are satisfied. If player receives substantially more or less than the corresponding value, this would imply violation of the regret constraints for at least one of the players' learning algo- rithms.
A.2 Proof of Proposition 2
Proof.
The statement follows by observing that
[UAAB) (a, b)]
[MLABBy (a,
(a.b)aup
T
(a.b)mupt
E
[u (S^(a),b)
[ua (Ja(a),
T
(a.h)mup
(a.b)~ut
[uB (a, fn(())
E (a.b)=p!
luB (a, fB (b))
T
(a,b)-up
which in turn are equivalent the time-averaged utility of the play of players A and B, the time- averaged utility for player A under deviation fA. and the time-averaged utility for player B under deviation fB. Applying the definition of average d-regret and applying the given bounds on the verrerett yields the conclusion of the first direction. The reverse direction follows by reversing the steps.
A.3 Proof of Proposition 4
Proof. Observe that under any strategy (a, b) where b BR(a), player B cannot have any swap- regret, and so any Stackelberg equilibrium is also -qqul)iqqil Further, the marginal distributions over the optimal (0. -qquiliiuiii for player A over each b; cannot have distinet expected value for player A, as otherwise this would contradict optimality, and so an optimal (0, ()- equilibrium is either single Stackelberg equilibrium mixture of Stackelberg equilibria with equal value.
A.4 Proof of Proposition 3
Proof. By definition, the set of A 4 B yo is a sub-polytope of A(A B) defined via the following linear constraints:
For each fA A have that
ΣΣ
Σ
Pig (((,
Σ
Σ
Pig ualaooo)))))))
iE[M JE[N]
ME[M] JE[M]
For each fa LB. have that
Σ Σ Pij up (B) SE[M] JEIN]
Σ Σ Pig uB(ar(),b))
JE
The value Val A
A, 2B) corresponds to the element of this polytope that maximizes EiE[M] ΣjEM Pi uA (a,, b;). Optimizing this linear function over the above polytope can be done in time poly(M, N, & & l l) via any linear program solver. Computing Val ( A, @n) can be likewise done efficiently.
12

---

For player A, the regret comparator function sets 0, &. and I contain O. M. and M² elements respectively. In all three of these cases 4 poly(M); likewise, in all three of these cases Φ = (oly(N) (and thus we can efficiently compute these values when A DB E { T)). nI
A.5
Reward separations
We show that with respect to optimal values, these equilibrium classes are often distinct, and there exist games where values do not collapse. The separations we show here consider the equilibrium cases either where both players have identical regret constraints, or where player A is unconstrained. We note that while inspecting other cases, identified similar examples for several other generalized equilibrium pairs, and we expect that strict separations exist between any distinct pair of generalized equilibria for the three regret notions we consider, any direction not immediately precluded by the regret constraints. We are mostly interested in cases where B is constrained, and A may be constrained or unconstrained.
Theorem For each of the following, there exists a 4 game G with rewards {0, 1, where:
1. Vala (0, 8) Val (0, V (E, Val. (I,I)
2. Vala (0, 8) V (E, Val (0,I) Val (I,I)
Proof. We prove both results by exhibiting game with the desired chain of inequalities, which we found by searching random examples of 4 x games with values constrained {0, 1, and computing the various values of the games with a linear programming library. The numerical values are easy to check with computation. The game G₁ = (MA, MM, satisfics the conditions for the first chain of inequalities, and the game G2 (Ma,, MB.) satisfies the conditions for the second chain inequalities. First we instantiate the game G1:
1
0
0
07
0
2
0
0
0
0
1
1
0
MA.
MB,
0
2
0
2
0
0
0
0
0
The corresponding values for game Gj are simple to check:
1. Vala (0, E) = 8/5.
2. Vala (0,Z) = 4/3.
3. Vala EE 1.
4. Vala (I,Z) 0.
Then we instantiate the game G2:
2
1
2
1
1
0
0
1
2
0
M4a =
MB, =
1
2
2
0
2
0
2
1
0
2
1
1
The corresponding values for game G2 simple to check:
Val. (0, E) = 13/7.
2. Vala EE, = 12/7.
3. Vala ( = 5/3.
4. Val (I,I) = 4/3.
13

---

B Deviation to weaker regret classes
In Section 3, we show that if two players are playing no-swap-regret strategies against one another, is often in the interest of each player to switch to playing their Stackelberg strategy (in particular, this is true whenever the game does not have pure Nash equilibrium). However, as we later argue, learning ones Stackelberg strategy in such game can be difficult. It is therefore natural to ask whether there are beneficial deviations to computationally efficient strategies. In particular, it ever in player's s interest to weaken their regret benchmark, and e.g. switch from playing no-swap-regret strategy to no-external regrett strategy?
We give example showing this is true in fairly strong sense: we exhibit a game G where if player switches from playing a no-swap-regret algorithm to any no-external-regret algorithm, their asymptotic utility never decreases and sometimes strictly increases - i.e., there is no downside to switching to an external regret algorithm (and potentially a high upside). We have the following theorem.
Theorem 9. There exists game G where M 2 ValA(I, and Vala(E, 2 V (I,T).
Proof. Consider the game G specified by the two payoff matrices
0 0 27
2 1 17
MA =
MB ==
2 1
0
1
0
0 2
The corresponding values for this game are simple compute:
1. VII MinVal (I, 0.
2. (E, 0.
3. (E,, 1.
C Proof of Theorem
Proof. Let yp be the joint distribution over action pairs corresponding V. Let T denote the total number of steps we run the algorithm for; we will use t < T as changing step size. Suppose both player A and player B know p². We will define C and (V) in two phases: in the first phase, A and B trust their opponent and play according to deterministic sequences corresponding to approximations of yp. If either player violates the other's trust o(T) times, then the player defects to playing Ca or LB respectively forever after.
First elaborate upon the trusting phase. Both players consider windows of length Length(t) which is monotonically increasing in / and also which grows sub-linearly in t. For concreteness, we pick a sub-linear monotonic increasing growth rate of ((VE) and describe how to implement the schedule of window lengths. We can keep track of real-valued variable Z, with Z1 M N, and after each window completes, update it by 7 = Z, + 2v7 where is the step at the end of the window. To get an integral window length, define Length(t) = [Z.]. Thus in this case, the Ltn grows O(VI), satisfying both conditions. Both players then compute weighting instantiated with pairs of pure strategies by assigning & := Length(t) - example pairs (each of weight 1/ Length(t)) to pure strategy pair i [M Nj. This weighted distribution approximates given Length(!) samples. Note that the rounding approximation is feasible given only Length(() samples since Σ EM-N C; Length(t). These pure strategy pair samples then lexicographically
x can be communicated from Player A to Player B during burn-in phase of length > M-N .V, the dimension of the discrete joint distribution pure player strategy pairs.
14

---

ordered. Then, both players act according to the pure strategies in order, thereby (over the window) achieving an (M / Len approximation (p:
M-N
C2
M-N
Length
P.l Le)
M N Le)
P1
(t)
P2
S
This process repeats for every window.
The distrustful phase occurs if one of the players does not follow the agreed-upon instructions Tastrust times, where Tassuss is taken to be o(T). After this many violations, Player A defaults to playing LA and likewise Player B defaults to playing LB ever after.
We now show that this algorithm satisfies both conditions in the theorem statement. First, if both players use (V) and Cg (VV), the play converges to y., the joint distribution of play corresponding to V. This point is immediate to observe since (M /)/ Length(t) + 0 as t + oo as Length(t) is monotone increasing in
Now we prove that both players are no-D-regret with respect to any adversary. First we show no-Ø- regret for both players in the case where Player A plays [ (V) and Player B plays L Let G be the approximation to ip implemented over the window corresponding to final step t, and suppose that ||40 -x Ez. Recalling the proof of Theorem 1, for Player A (and analogously for Player B) we can bound
[uA (a, (a.b)~p
E
E (a.b)~u.
[ua (a, (a.b)]
(0 (p.)" UA
- 1 -.ll2 1IMAlll E. C. V N,
where here we interpret y0, Pe: U.A, un E R M as vectors over the space of all action pairs. Thus for this particular window, the overall gap from the expected reward for is Ex C /M N. Then similarly upper bound (a,,), [MA (fa(a), I (a.0i=p [uA (fa(a), b)] +& C. M / N for any choice of fA E 4
(x)
E (a.b)aup
[UA (fa(a),b)]
E (a,b)aup
[UA (fa()))) 60]
M N
M
(k,(k,) (k(k)))) Σ fa(as)) ((la))-u(..b)))
< 1p Pelli [fA(a)) (.)(,b))) ... fa(ar)) Talan))aa((,b)) [u((;bb)]] ll2
S ...VM N max (lfa(ax)]2 |1aa(;b;))l1z
R.
S VM N 1. C
E. M C.
Then recall that by
<
M-N Len
Thus, overall, the average regret using due to the window is bounded
Reg (p., S Le)
Reg (p. + C2 (t)
Ltngth(t)
where C2 is another constant depending on C, M, N and where we use the shorthand Reg (- t) to denote the d-regret over the window ending in step t. Now call P the strategy where the joint distribution & as previously defined gets played in each window Now we can bound the total 0-regret for & by the sum of the r-regrets for each window (maximizing fA E & over the steps in each window makes more competitive than optimizing only one fA over the whole length T sequence). Thus for total f-regret, we have:
Reg, (+,T) <
Reg (4, T) + NumWindows(T) C2
<
Reg, (p, + (T),
15

---

where
NumWindowss(1) Ei=1 (en
min k.
The last step follows since NumWindows(T) S (T"), because (T") - (T)).
Since already know that the strategy yp is no- no-reregret and (T) is o(T), we have proven that playing 0 is no- D-regret in the case where Player A plays ( and Player B plays L (V).
The second case where the opposing player does not cooperate is easier: after at most o(T) steps, the player switches to an algorithm La or LB respectively which no-Ø-regret and incurrs only ((T) additional regret. Thus the theorem statement holds.
D Proof of Theorem 2
Proof. We begin with the first claim. To prove the forward direction, there exists such so, then
choose a pair of low-swap-regret algorithms (La, LB) such that the time-averaged trajectory over T rounds is guaranteed to asymptotically converge to y (this is possible by either the results of (11), or our Theorem 1). That is, if the two players play strategy St at round t [T'] then = + Pt satisfies ||@ |lse- = o(1). It follows that 2. (9))) 2 T ua(()) - o(T) T Stack -o(T) and therefore player A has at most an o(T)) incentive deviate (by (10), they can obtain at most Stack T + o()) against Lg). Symmetric logic holds for player B.
To prove the reverse direction, assume LA and L3 no-swap-regret algorithms such that (CA, LB) an -aproxxmte Nash equilibrium in the metagame. Since they are no-swap-regret, the time-averaged play of these two algorithms for T rounds must converge correlated equilibrium f moreover, since (L..L)) is an -pproxiiie Nash equilibrium, Ør must have the property that u ( 2 Stack -0( and (B())) 2 Stack -o(1). Taking the limit as T + oo and selecting a convergent subsequence of the GT. this shows there must exist a correlated equilibrium ip with the desired properties.
apprrxxmaae
Likewise, similar logic proves the second claim with the following modifications. In the forward direc- tion. we can choose any pair of low-swap-regne algorithms LB), and any correlated equi- librium yp they asymptotically converge to is guaranteed to have the property that u ( = Stack, A and u ({p) Stack In the reverse direction, since any correlated equilibrium is implementable by some pair of low-regret algorithms (again, by Theorem 1), the same logic shows that all correlated equilibria & must satisfy (yp) Stack and un (Tp) Stack
Finally, to see that these two conditions are efficiently checkable, note that: the two values Stack A and Stack are efficiently computable given the game G. and ii the set of correlated equilibria go form a convex polytope defined by a small poly(N, .)) number of linear constraints (see Proposition ( 3). In particular, since u (yp) and ug (ip) are simply linear functions of for a given game G, we can efficiently check whether there exists any point in this polytope where u ( = Stack and (pp))) Stack
E Proof of Theorem 3
Proof. We will show that (for almost all games G) if there is a correlated equilibrium yo such that "x(s)) Stack, a and un (g)) Stack then there exists simultaneous unique Stackelberg cquilibrium for both players in G, which must pure Nash equilibrium. Combined with Thcorem 2, this implies the theorem statement.
We will rely on the following fact: in almost all games G, both players have unique Stackelberg strategy. To see this, consider the following method for computing A's Stackelberg strategy. For each pure strategy by for player B, consider the convex set A, S ((A) containing the mixed strategies for player A which induce b, as a best response (i.e., A₁ = fa E A(A) by BR(a))). Then, for each j E [N], compute the strategy (ky A, which maximizes u (ay; b;). The Stackelberg value Stack, is then given by max, u (az. bj). In order for this to stem from unique Stackelberg equilibrium, is enough that: 1. the maximum utility not attained by more than one j. and for each j, the optimizer ay E A, is unique.
16

---

These two properties are guaranteed to hold in almost all games. To see this, first note that the convex sets A, are determined entirely by the utilities ug, so we will treat these as fixed. Now, given any convex set Aj. the extremal point in randomly perturbed direction will be unique with probability - but since (x simply the extremal point of A, in the direction specified by "A(:,;) (which is randomly perturbed direction), so aj is unique in almost all games. Finally, if we perturb the magnitude of each of the utilities ua(:;b;) (keeping the direction the same), the maximizer max; u (a b;) will also be unique almost surely.
Let (a. bA) be the Stackelberg equilibrium for player and let (ag. be the Stackelberg equilibrium for player B. Now, consider the aforementioned correlated equilibrium sp E A x B). We will begin by decomposing it into its marginals based on its first coordinate; that is, we will
write o = Ei=1 A,(a,, for some mixed strategies 33 E A (B) and weights X, (with E; X = 1). By the definition of correlated equilibria, note that each a; belongs to (R(3.). But this means that u Ma(a, (a,, B,) I Stacks. with equality holding iff (a;, 3²) = (ag, BB) (due to uniqueness of Stackelberg). Therefore, in order for up({)) Stack we must have that yp (ag, Bg). By symmetry, we must also have that = (a.A, ba). If both these are true, then yp is a pure strategy correlated equilibrium of the game, and is hence a pure strategy Nash equilibrium (and moreover, is also the Stackelberg equilibrium for both A and B).
F Proof of Theorem 4
Proof. By Theorem 1, there is a pair of 0-regret and E-regret algorithms LA and Li which converge to (0, -qquiliuuii for which player A obtains (0,, E). By Proposition 1, this is optimal over all no-external-regret algorithms, as any adaptive strategy constitutes a no-0-regret algorithm. By Proposition 3 we can identify the optimal (0, E) -qquuiibbriu in poly(M, (ll N) time, which is sufficient to implement the algorithms L and C efficiently for any desired T.
G Dominated-swapping external regret bounds for mean-based algorithms
For the following proof (of Theorem 10), we introduce the following notion of dominated external regret, a tighter upper bound on the behavior of mean-based algorithms than the standard no-external-regret guarantee.
Definition 8 (Dominated-swapping external regret). For game G. let D(G) be the set of dominated strategies for player B, i.e. b, E D(G) b, & BR(a) for all a E A(M). For j. je E [N] define (b,) as:
(ba()e) = {{ [bx b, D(G)
[b, by $ D(G)
i.e. 95k (b:) swaps b, to by. bf is dominated and plays bj otherwise. Let ED(G) {9g. : l e [N]} be the set of dominated-swapping external regret comparators.
This definition leads to the following tighter upper bound on what is achievable against mean-based no-regret algorithm.
Theorem 10. For any game G and any mean- mean-based based no-regret algorithm used by player B, there no strategy for which the average reward of player A converges to Val (0, ED()) + s, for any 8 O.
Proof. First, we observe that mean- mean-based algorithms will never play dominated strategy by E D(G) in more than o(T) rounds. As b, is dominated, there is some 8 > 0 such that for every E ((M). there some by where ug (a, by) 2 uB b,) + 6. Let o denote the empirical distribution of player A's actions up to time f. After some window of O(7T) o(T) rounds we will have the cumulative rewards .s and T,t satisfy os < round, and so b; will never be played in more than (T)) rounds.
öt < dj.t --y TT under any a for some by in each subsequent
We can also see that any such no-E-regret algorithm is no-Epray-regret algorithm. Suppose such an algorithm had Enggr-regret eT, for 0; then, there is some 9yk for which (oor,,9 (3r)) 2 Up Up(or, 3r) + By the E-regret guarantee this cannot occur if j k, as any such function 9/s
17

---

equivalent to the fixed deviation rule for by. However, if this occurs for j * k. such an algorithm must have played dominated strategies in a total (eTT". This contradicts our assumption that no dominated strategy b; is played in more than o()) rounds, and so any mean-based no-E no-E-regret algorithm is also a no-ED(Cy-regre algorithm, against which player A cannot obtain average reward which converges to any amount higher than V (0, ED(C)) + +1)).
H Proof of Theorem
bj
by
bg
Q1
1,
0,
3.0
02
0,0
1,1
0,0
Figure 1: Game where Vala (0, Vala (Q, MBRewA
Proof. Let MBRew, A denote the maximal reward obtainable by player A when player B uses a mean-based algorithm. Observe that by is dominated for player B, and thus cannot be included in any (0, -equiilibbii (by Theorem 10). Further, it will never played by a mean-based learner for more than o(T") rounds, for any distribution over a1 and d2 the best response is either bı or b2- As such, both Val A (0. I) and MBRew A are at most 1 + o{1); a reward of - o(1) is obtainable by committing to either á or dg for each round. However, p for player A includes positive mass on (a1, by). and yields an average reward of Val (0, E) = for player A. Let p1 be the probability on (a1, b2). ), let pa be the probability on (az, by), let ps be the probability on (a1, by). and let pu be the remaining probability. The reward for player A is given by:
can see that the optimal (0, -equilibrrim
Rew (p) P1 + P2 + 3p3
and p defines a (0, E) equilibrium if
Rew (p) > Rew + bi)
for each b,, which holds if:
Pi + P2 2 P1 + Ps:
P1 + p2 2 P2:
Pi + P2 2 0.
Only the first is non-trivial, and so the optimal (0, -equiliibri for player A occurs by maximizing Pi + P2 + 3p3 subject to p2 2 Ps. which yields a probability of 0.5 for both and p3 (and 0 for pı and po), well an average reward of 2. As such, player A cannot obtain a reward approaching Val (0, E), as their per-round reward is at most 1 + o(1)
I Proof of Theorem 6
Proof. We recall that the SU algorithm from (19) finds initial points (b:b) in each best response region via random sampling, which takes takes 1/ po) queries in expectation. Then, upon calibrating for (loo(1/E)) bits of precision SU makes (oly(M, N. (og(///) queries, each of which can be taken to be a point some grid of spacing 1/ po] within the simplex by the precision condition. The computed approximate Stackelberg strategy is then the optimal such point on the grid.
We first describe our strategy for simulating each query against an arbitrary anytime-no-regre learner; as & C d, we can restrict to considering only no-external-regne regrett learners, these regret constraints will always be satisfied. To implement a query greedily play the action whose historical frequency of play is the furthest below its target frequency in g. After (ppoly(1/e)) rounds, the historical distribution will be within 1/ poloy(s-") of q. and continuing the greedy selection strategy indefinitely 1/ poly(e-1) ball around q. Let ty be the time at which this
will ensure that the history remains occurs. After maintaining the greedy strategy for q for an additional w(t)) rounds, the anytime regret bound ensures that most frequently played item must indeed be the best response response to some point in the ball around g, provided that this ball is contained entirely inside some best response region Ry. For the sampling step, a taking sufficiently small grid (but still 1/ poly(s-1)) ensures that random sampling still suffices to find a point point in each best response region even if our
18

---

queries may be adversarially perturbed to neighboring points on the grid, as each region is convex and has volume at least 1/ poly(= To address the issue for the line search steps, it suffices to take an additional step along each search conducted by SU before termination, where we then take each hyperplane boundary estimate be one step inward along the grid from where our search terminates, maintaining buffer between each hyperplane estimate in which all our points of uncertainty must lie. This adds at most a constant factor to our query complexity, and impacts our approximation by 1/ poly(=-)), "), which then yields us runtime of poly(1/e) 9 rounds.
For the case of a mudaptive-regree learner, suppose such an algorithm is calibrated for T O (2); then, over any window of length W its regret is at most O ((Q (1/E)
Taking W w(((C: (1)=)(())) yields per-round regret of at most o(1) over the window, and so an algorithm must play a best response in W - o(W) of the rounds. For sufficiently large C₁ and C2. each W is large enough to yield the same precision we required for the anytime case, where now we greedily play the action whose frequency furthest below its target since our previous query terminated, which allows to again simulate the (() queries in poly(Q/e) rounds (accounting for the robustness checks) while yielding (WWQ)= = oTT).
J Proof of Theorem? 7
Proof. Our game consists of M actions A for the optimizer, and N 2M + learner, which are divided into M primary actions B, M secondary actions S, and M V.
( actions for the
safety actions
If we restrict the learner to only playing primary actions, the game somewhat resembles a coordination game, where each pure strategy pair (g,,by) is Nash equilibrium. However, the set B is comprised of both undominated actions By and dominated actions DD. which are unknown to the optimizer, and where each bj E Ba weakly dominated by the secondary action 8y. The optimizer receives reward 0 whenever the learner plays secondary action, and so the challenge for the optimizer is to identify the pair ba) which maximizes u.A (aj. by), for by E D.. which will be the Stackelberg equilibrium. Further, the safety actions Yij essentially allow the learner to hedge between two actions; this does not pose substantial difficulty for the optimizer when the learner is no-swap-regret, yet creates an insurmountable barrier for learning the Stackelberg equilibrium in sub-exponential time against a mean- based learner.
An instance of a game G' E G is specified by the partition of B into By and Bp. There is an action 8j S for each J. and for each pair (i.j) with < j there is an action Yij e V. The rewards for game G are as follows. For any strategy pair, the optimizer's 's utility is given by:
uA(aj, b,) = j/M for bj B:
ua(a;, b,) = for bj E B and with i + j:
ua(ai, 85) = O for any 8j E S;
ua(ai, Uyt) 0 for any Bik E V;
and the learner's utility is given by:
For by E By:
ub(az, bj) 1; - up(a;, bb) = 0 for i # j:
For by E BD:
- -ug(a, bū) = 0 for any i;
For 83 S:
- un((aj 83) 1 if bj E Bp:
uulay, 83) 0 if by By:
19

---

uz(as, 8y) = 0 for i J;
. For Vij E y:
ug(aa, Vij) u (aj, Mij) - unnaus Mhi) = for i, +
2/3:
We assume that By is non-empty, and so there is some optimal pure Nash equilibrium (a7, b() which yields a reward of i/M; it simple to check that this also the Stackelberg equilibrium.
Optimizing against no-swap learners. First, we give a method for matching the Stackelberg value against an arbitrary no-swap-regret learerr which corresponds to the pair (aj. by) for the largest value j such that by E By. Consider a no-swap-regrel learner which obtains regret bound of 7 = (TT) over T rounds. Let SR,(h, b') for any learner actions b and V'' denote the l-round cumulative swap regret between and V/, i.e. the total change reward which would have occurred y' was played instead for each of the first / rounds in which b was played. To model the behavior of an arbitrary no-swap-regret learner, we disallow the learner from taking any action which would increase SR, (b. ()) above given the loss function for the current round, and otherwise allow the action to be chosen adversarially. While our model is deterministic for simplicity, it is straightforward to extend to the analysis algorithms whose regret bounds hold in only expectation, e.g. by considering a distribution over values of r in accordance with Markov's inequality (as no algorithm can have negative expected regret against arbitrary adversaries) and considering our expected regret to the Stackelberg value.
Our strategy for the optimizer is:
For each e [MM), play a until either 6y or s; is observed at least t r times;
Return og for the largest i such that b, is observed (" times.
We show that this takes at most O(T a) rounds. Once of is identified. we can commit to playing it indefinitely, at which point the learner must play by in all but most O poly(M)) rounds, and so with T = Oppol (Mf))) rounds we can increase the total fraction of rounds in which (at, bt) is played to 1 - E, which yields the desired average reward bound.
The key to analyzing the runtime of our strategy is to consider the "bufferr in regret between any pair of actions before the threshold of 7 is reached, which enables us the bound the number of rounds in which instantaneously suboptimal actions are played. Note that prior the start of window i (where a; is played), both 6; and s; obtain reward 0 in each round, and as such cannot decrease their expected regret relative to any other action, as all rewards in the game are non-negative. Further, for any previous window j. both b; and s incur regret of 1 with respect to either by or 8j. as well as between the suboptimal and optimal action in window i, and thus cannot be observed more than times in the window. As such, observing i; least '" times window i indicates that b; E By (and likewise observing b; at least 1" times indicates that by E BD)-
Any action b + BR(a;) will incur positive swap regret with respect to BR(,,), and cannot be played in window once (b, BR(a))) 2 т. Each action begins with SR, (b. BR(a,)) = O at time = 1; for each of the learner's actions, we consider the rate at which its buffer decays, as well instances in which swap regret can decrease:
Previously optimal b E BUS' BR(a:): actions in BUS can only accumulate negative swap regret with respect to BR(a.) during rounds in which they were previously optimal; any previous optimum b = BR (a) for j < i was played most 1. times during window j. and so we have that (b, BR(a;)) 2 -t"
All b E BUS \ BR(a,): ignoring any previously accumulated regret buffer, each of these 2M actions can be played at most r rounds during window i before exhausting their initial buffer. Accounting for possible previous optima with SR, (b. BR(a)) < 0. the number of rounds during window in which some E BUS BR(a) (a:) is played is at most Mt + (2M L)T.
20

---

Safety actions Vik E V: Suppose neither aj have been played yet by the optimizer. including in the current window. As was the case for other actions which have never yielded positive instantaneous reward, Ujk can be played at most times before (yj&, (R()))) > т. j i, i.e. this the first window which У/Д obtains positive instantaneous reward, the per-round regret is 1/3, and so at it can be played for most 37 rounds. Further, Vyk a obtains a regret of -2/3 with respect to BR If k and the window for aj has already been completed, M/j can be played for at most 9T rounds, as initially we have that (yja,, (R))) 2 2T,, which again increases by 1/3 per round. We then have that the total amount of rounds with safety actions played during window i is at most (12M + M as there are fewer than M total safery actions, and fewer than M in each of the latter cases.
This yields a per-window runtime across all actions of most Mt + (M2 + 10M 1)T, which is O(T Mº) across all windows, and so we obtain the desired result for optimizing against arbitrary no-swap-regret learners.
Optimizing against mean-based learners. Here, we show that there are mean- based no-regret algorithms for which exponentially many rounds are required for an optimizer to approximate the Stackelberg value against learner. When considering horizons which are superpolynomial in parameters of the game, it is most natural to consider algorithms with regret bounds which are non-trivial for smaller horizons, as well as an anytime variant of the mean-baser property. We define an extension of the classical Multiplicative Weight Updates algorithm (MWU; see (2) for survey), called Rounded Mean-Base Doubling, which inherits both properties in the anytime setting.
Algorithm 1 Rounded Mean-Based Doubling (RMBD)
Initialize and run MWU for Zi 2 rounds and actions. Let T2 == 27; and i := 2. while T, < T do
Initialize MWU for T; rounds and n actions.
Simulate rumning MWU for T;-1 rounds, using the average of the first T,-1 rewards each round.
For T rounds, MWU with action probabilities rounded multiples of 4 ÖCT,"" 1/2).
Let 7;-1 = 27; and i == i+1. end while
Lemma 6. When running RMBD for T rounds, the following hold at any round S T:
RMBD has cumulative regret (nn/t);
If action j has the highest cumulative reward and os. S Oj - Ö(V)), then action is played with probability O at round I.
Proof. Let CVi bound the regret of MWU over rounds (where C= =(vlooggn) and let D
V2C (n). We can bound the regret of RMBD over T; rounds by DV/,, via induction (which holds trivially at T.). Suppose it holds for some T,. Let R(T;) be the true reward obtained by RMBD over T; rounds, which at least .T. DVT,, where .T is the cumulative reward of the best action over T, rounds. Consider our simulation of MWU over T, rounds using the average reward function. As the reward function is identical each round, and the cumulative reward for each action j is equivalent under averaging, the measured reward R(T,)) from the simulated run is at most dy+,r; after T; rounds. Upon continuing to run this instance of MWU for an additional T; rounds, the regret bound ensures that the total measured reward R(T;+1) is at least 0,- 22; CV/2T, Rounding probabilities contributes at most an additional 2nryT; to the regret; suffices to implement rounding by reallocating probability mass from any Pi,t < 2y onto other actions arbitrarily. to avoid renormalization. The total reward of RMBD over 27: T++1 1 given by cumulative reward at T, as well as the additional reward obtained by the MWU instance over the next T; rounds, and
21

---

have that
R(T++1) = R(T;) + R((i+1)) R(T:))
2 TT - -
2 TT- - DVTi+t,
which yields the bound for every T: We can extend this to any t [T,, T with most a factor increase to cumulative regret.
To bound the selection frequency of actions with suboptimal cumulative reward, recall the mean- based analysis of MWU given in Theorem D.I from (5), which shows that the selection frequency
Pk,r for action & at time is most 7 2log(v log ni if Th, S Jj YI' for the action j with V2'log
highest cumulative reward. As such, any action whose cumulative reward o S Jj.t Ö(vt) will be played with probability 0.
Suppose a learner plays the action with highest cumulative reward at each round for foum = (MM rounds, then plays RMBD thereafter for total T rounds. Note that this maintains the both properties of RMBD for all t. We show that at least T = exp (xp())(MM) rounds are required to identify the Stackelberg strategy. The optimizer must check the learner's pure best response to each a; for identification with certainty, and it is straightforward to construct distribution in which any strategy which does not observe BR(a,) for all j will have linear regret to Stack,, 4 in expectation (e.g. where By contains one action chosen uniformly at random). The difficulty in exploration of the best responses comes from the safety actions, as a, must have been played more frequently than any other action in order not be dominated by some safety action. Let fJ.a denote the number of rounds which the optimizer has played a, out of the first t. Observe that by construction of the game and the properties of RMBD, primary secondary action b, or 8j in BR(a)) will only be played with positive probability when:
2 Pjt 2 [P3. Pk.)) Ö(VEt)
= 2px, - Ō((V))
for all k. which necessitates that Pj.t 2 2t Ö(VI). Taking /hunn sufficiently large, have that
N8
P5,t 2 PK, for any 2 foum and all For any subsequent observation BR(ag) at t', we must have that Pk,t' 2 Pj.e, and so the number of rounds required to play an action before observing its best response grow at a rate of at least (3/2)M, which completes the proof.
22


Reviews:
[{"review_id": "UENV4wPomY", "reviewer": "Reviewer_o15k", "summary": "This paper considers equilibria between agents that have arbitrary regret benchmarks (corresponding to different equilibrium concepts), and the relation between those equilibria and the interactions of no-regret learning agents.  It is known in the literature that an agent who knows that the other is playing a no-external-regret algorithm can guarantee themself the Stackelberg leader value (i.e., $Val_A(\\emptyset,\\mathcal{E})$ in the terminology of this paper).  This paper extends that results by showing that in fact it can be better to play a no-external-regret learning strategy against a no-swap-regret learner (i.e., a learning algorithm with a weaker regret guarantee can get higher utility, all else being equal).  A further result is that any generalized equilibrium is reachable by a pair of regret-minimizing learning strategies.\n\nThe paper also considers the complexity of learning Stackelberg strategies; it turns out to be easier to learn a Stackelberg leader strategy against a learning algorithm with a stronger regret guarantee, because it reacts more quickly to best-respond to changes in the other player's behavior. \n\n\n", "questions": "none", "limitations": "n/a", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is an extremely strong paper.  The question of when minimizing regret benchmarks also lead to good performance (the thing that we actually care about, in general) is really important, and this paper provides rigorous, compelling, and general answers.  The generalized equilibrium framework and the connections between learning and equilibrium are very clear and likely to have a significant impact on the learning in games literature.  I strongly expect to refer to this paper in the future.\n\nThe complexity results at the end are a nice touch as well.\n\n\n", "weaknesses": "I have no major complaints about the paper.  Here are some minor comments/issues:\n\n- I was initially very surprised by Theorem 1; a little more hand-holding about why this doesn't contradict Barman & Ligett [2015] might have helped.  (Basically, the result doesn't require the algorithm pair to _find_ an optimal equilibrium, instead it will converge without regret to an exogenously _specified_ equilibrium).\n- p.6: \"Further, each equilibrium set can be optimized over via a linear program.\": I'm not sure what this means.\n- p.8: \"Let $\\sigma_{i,t}$ be the cumulative reward resulting from playing action $i$ for the first $t$ rounds\": It would be clearer to avoid the notational collision with strategies by using a different letter\n- p.8: A few more details in the proof sketch for Theorem 5 would be helpful; it took me a while to convince myself even that the statement made sense.\n\n\n[Barman & Ligett 2015]: \"Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard\"\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! \n\nYou are correct that Theorem 1 applies to exogenously specified equilibria, and does not require “learning” the target equilibrium on the fly. However, our focus is on two-player games, for which it is also possible to efficiently optimize over each of the equilibrium sets we consider via linear programming (as we show in Proposition 3). Even for multiplayer games, one can always compute an “optimal” (e.g. in welfare, or for any player) (C)CE via a linear program which is polynomial in the size of the game, with variables for the probability of each action profile and linear constraints for each player-action(-action) pair which enforce regret constraints. The size of this LP is polynomial in {# actions} but exponential in {# players}, as the normal-form representation of a many-player game has exponentially many {# players}. In contrast, the results of [BK15] apply to “succinct” games with structured rewards (e.g. routing games, see [PR08] for many other examples) in which rewards are fully determined by a representation which is polynomial in {# players, # actions}, and as such are not in contradiction with the LP approach which uses a normal-form representation.\n\nWe will clarify this in the paper, and will also fix the notation overload (thanks for catching this!) as well as further clarify the intuition behind Theorem 5; the key idea there is showing that mean-based algorithms are strictly stronger than “worst-case” no-regret algorithms, and thus are harder to exploit.\n\n[PR08] Computing correlated equilibria in multi-player games - Papadimitriou & Roughgarden"}, {"review_id": "RtSG2lnPlP", "reviewer": "Reviewer_TzAU", "summary": "This paper addresses several interesting questions regarding the tradeoff between reward and regret in repeated gameplay between two agents. Three problems are sequentially investigated. 1. The paper provides a characterization of the setting when running a no-swap-regret learning algorithm is preferred over playing the Stackelberg strategy; it further showed that such a setting has measure zero and almost does not happen. 2. This paper shows that if the opponent is running any no-regret algorithm, the utility of the player is upper bounded by the unconstrained-external value of the game; such an upper bound is achievable for a particular no-regret algorithm of the opponent. 3. The paper shows that it is possible to convert any best-response query algorithm for finding Stackelberg equilibria via best-response queries to an adaptive strategy that learns Stackelberg equilibria via repeated play against a generic no-regret learner, albeit potentially at the cost of an exponential blow-up in the number of rounds. \n", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The several questions addressed in this paper are very interesting. In algorithmic game theory, many existing work focus on algorithms for finding an equilibrium via repeated gameplay. However, in repeated gameplay, the agent’s interest is often maximizing reward and has the motivation to deviate from the regret minimization algorithm. This paper studies when deviating from the regret minimization algorithm is beneficial and when it is not. \n", "weaknesses": "There are still many unsolved open questions. For example, for specific no-regret algorithm classes, it is not clear how much one can exploit. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review! Indeed there are several remaining open questions that we think would be interesting to explore in future work. \n"}, {"review_id": "W84fZQG0R4", "reviewer": "Reviewer_hPuK", "summary": "The paper explores tradeoffs between reward and regret in repeated gameplay between two agents. It introduces a concept of generalized equilibrium that allows for different regret constraints, resulting in feasible values for each agent. The paper shows that such equilibria can be reached by algorithms maintaining regret guarantees against any opponent. The paper also examines tradeoffs in terms of the opponent's algorithm choice and characterizes the maximal reward achievable against a no-regret learner. It demonstrates that different classes of no-regret algorithms can lead to varying rewards.", "questions": "See in Weaknesses", "limitations": "See in Weaknesses", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Theoretical analysis is solid and convincing.\n- The problem studied is interesting. Although running no-regret dynamics leads to CCE, no work attempts to doubt \"running no-regret\" this thing itself.\n", "weaknesses": "I think some realistic running examples can be supplemented for better illustration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments! While our focus for the paper is intended to be primarily theoretical, in the appendix we give examples of games where we show explicit separations between feasible equilibrium values, and we are happy to explore simulating algorithms on these games.\n"}, {"review_id": "ByGbOphJWw", "reviewer": "Reviewer_vLcT", "summary": "This submission studies questions surrounding playing against a no-regret learner in a repeated game setting. These questions are motivated by previous observations that while it is known that when all players play no-regret strategies the empirical frequency of play approaches an equilibria, a player can sometimes do better by deviating to a different strategy/algorithm (that is not no-regret). \n\nIn particular, the authors focus on four questions: (1) When does reward trade off with regret? (2) Under what game settings is playing a no-swap-regret algorithm a stable equilibrium? (3) How to play against a no-regret learner? (4) How can one learn the Stackelberg strategy through repeated play against a no-regret learner?\n\nTowards answering question (1), the authors consider a generalized notation of equilibrium, (Phi-A, Phi-B)-equilibrium, where player A is restricted to playing no-Phi-A-regret strategies and player B is restricted to playing no-Phi-B-regret strategies. Each choice of (Phi-A, Phi-B) induces a polytope of (Phi-A, Phi-B)-equilibria. They show that for any equilibria in this polytope, there exists a pair of no-regret algorithms in (Phi-A, Phi-B) which converge to it. \n\nTo assist in answering question (2), the authors consider a \"metagame\", in which at the beginning of a repeated game, both players simultaneously announce and commit to an algorithm to use during the game. The authors main result towards answering (2) are a set of sufficient and necessary conditions for (a) some pair of no-swap-regret algorithms to form a Nash equilibrium in the metagame and (b) all pairs of no-swap regret algorithms to form a Nash equilibrium in the metagame. In an effort to characterize which types of games playing no-swap-regret algorithms is \"optimal\", the authors show that if a game G does not contain a pure Nash equilibria, then there does not exist a pair of no-swap-regret algorithms which form a Nash equilibrium in the metagame, when player utility functions in G are randomly perturbed. \n\nTowards answering (3), the authors show that there exists a no-(external)-regret algorithm for player B and a strategy for player A such that the average reward for player A converges to their best possible feasible reward. However, the authors show that against any mean-based no-regret learner (a popular subset of no-external-regret algorithms), there does not exist a strategy for player A which can get \"close to\" the best possible feasible reward. \n\nFinally, the authors answer (4) by showing how to learn the Stackelberg strategy by simulating best-response queries against the no-regret learner. While they show that in general this may require exponentially-many queries, polynomially-many queries are sufficient if the no-regret learner is playing a no-adaptive-regret algorithm. ", "questions": "In Section 3, why is Nash equilibrium the \"right\" solution concept for the metagame?", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "While the authors are not the first to consider the general problem of playing a repeated game against a no-regret learner, this paper both introduces and addresses a (very) wide range of important and well-motivated questions surrounding the topic. The results contained in this submission provide valuable insights into this highly nuanced problem. While no one result stands out in particular, the sheer breadth of the results obtained by the authors in this submission is very impressive and the submission as a whole presents the clearest picture to-date of \"the right thing to do\" when playing against a no-regret learner. ", "weaknesses": "With that being said, the breadth of the results obtained by the authors makes it unclear what the main takeaway of the submission should be. At times, the submission reads like a laundry list of results about playing against a no-regret learner. Additionally, a longer discussion on related works in the main body (particularly (10) and (22)) would help someone who is not as familiar with the area better understand the main contributions of the authors. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! Indeed, we view our results as indicating that the answer to the question of “what should you do when playing against a no-regret learner?” is very much “it depends”, and we aim to explore several branches of this decision tree (is their algorithm known? is the game known? etc.). A second-order takeaway is perhaps that the Stackelberg value is often a “reasonable” benchmark to target. We will certainly use the additional provided page in the camera-ready version to further clarify the relevant background and the narrative thread of our results.\n\nAs for the meta-game, the question of alternate possible solution concepts is definitely an interesting one. We focused on Nash equilibria because the meta-game is essentially a “one-round game” where players act independently (by committing to an algorithm/strategy), and here Nash equilibria exactly capture whether players have an incentive to deviate up-front from committing to a specific learning algorithm."}, {"review_id": "yAttnAa5TM", "reviewer": "Reviewer_VEjN", "summary": "The paper studies several trade-offs that existed in learning in games. The first is the tradeoff between regret and rewards, for which a generalized notion of equilibria is introduced. It is then investigated whether running a no-swap regret learning algorithm is efficient. It is shown that this depends on the form of the games, in some games running a no-swap regret learning algorithm can be more efficient than employing the Stackelberg strategy. The same question is investigated for learning in game against a no-external regret learning algorithm. ", "questions": "1. Could the authors elaborate on why exponential weights, FTPL etc algorithms are mean-based? Also, Theorem 4 seems to be stated with respect to average reward, while Theorem 5 seems to be saying that a mean-based algorithm cannot attain the total rewards (which seems to be not surprising?), I wonder how these two Theorems should be interpreted together. \n\n2. It is mentioned that Proposition 5 can be improved, though the query complexity is still inversely proportional to the best response region volume. But from Theorem 6, it seems that through stimulating the best response queries, the complexity is independent of the best response region volume.\n\n3. It seems to be that mean-based algorithms often have no external-regret. I wonder if they can be also no swap regret? If so, how should one interpretate Theorem 7?  ", "limitations": "No", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the paper is really well-written and well-organized. The problem investigated and the results presented are interesting. The generalized notion of equilibria seems to be useful for other analyses of learning in games. It is also important to study the performance of different types of algorithms in games, (such as mean-based no-regret learning algorithms), these results can lead to further insights into algorithm designs for learning in games. ", "weaknesses": "Overall the paper is pretty solid, a rather minor weakness is that the presentation of the paper can still be improved. \nThere are quite a number of results presented in the paper. As a result, section 1.1 is a really lengthy section. It seems like the authors are trying to summarize the question investigated, related works, and the obtained results in this section. This can lead to some confusion as some of the notions are yet to be introduced in the paper and this is still at the very beginning of the paper. I would suggest making the section more concise and putting some of the discussion in the later parts of the paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! We will certainly take another pass on clarifying the narrative in the introduction, and can move some of the discussion of results to later in the paper. \n\nIn terms of mean-based algorithms, all of these algorithms resemble approximate/smoothed versions of Follow the Leader, in that actions are almost never chosen unless they are close to historically optimal (see Appendix D of [BMSW17] for a more thorough analysis).\n\nWe apologize for the confusion regarding Theorems 4 and 5; both of these theorems can be interpreted either in terms of total or average reward (by multiplying/dividing by $T$), and we will change the Theorem 5 statement for consistency. The takeaway for Theorem 5 is that all mean-based algorithms are strictly stronger than “worst-case” no-regret algorithms for certain games, and thus are harder to exploit (and an average reward of $\\text{Val}_A (\\emptyset, \\mathcal{E})$ cannot be approached).\n \nAs for Proposition 5, the exact BR query complexity for Stackelberg equilibria depends on a number of different parameters related to the structure of the game, and there are some technical intricacies we avoid discussing in the body for simplicity; to summarize, all algorithms which obtain accuracy $\\epsilon$ with $\\text{poly}(1/\\epsilon)$ queries require that the best response regions have volume at least $1/\\text{poly}(1/\\epsilon)$. However, in the query model the accuracy of these algorithms can be boosted to e.g. $\\log(1/\\epsilon)$ (by binary searching), yet the relationship between query complexity and volume is still fixed (finding initial feasible points is the bottleneck). We are unable to take advantage of this accuracy boost in our setting due to the imprecision inherent in the learning setting. As such, we make use of the weaker bound so as to align with the error terms resulting from learning. Once the query complexity is established to be $\\text{poly}(1/\\epsilon)$, Theorem 6 only requires that the volume is at least $1/\\text{exp}(1/\\epsilon)$, but we still need Assumption 2 nonetheless to establish the query complexity. We will clarify this discussion in the paper.\n\n\nFinally, while many mean-based algorithms are no-(external)-regret, results from [DSS19] imply that no mean-based algorithms can be no-swap-regret (or no-internal-regret) when there are more than two actions (via an example of a 3-action game where the maximum reward against any no-swap learner is strictly below that obtainable against any mean-based learner). Note that the definitions of external and internal regret coincide for only 2 actions.\n\n\n[BMSW17] Selling to a No-Regret Buyer - Braverman, Mao, Schneider, Weinberg\n[DSS19] Strategizing against No-regret Learners - Deng, Schneider, Subramanian\n"}]

Author rebuttal:

Meta-review: This paper lools at the interplay of no-regret learning and convergence in games.

All the reviewers, and myself, enjoyed it  and is therefore strongly recommend for acceptance.
Decision: Accept (spotlight)