Is Learning in Games Good for the Learners?

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.

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. There 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.

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. 2. 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. 3. 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?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No

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). In 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? Towards 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. To 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. Towards 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. Finally, 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.

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.

Questions

In Section 3, why is Nash equilibrium the "right" solution concept for the metagame?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

The authors have adequately addressed the limitations of their work.

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.

Strengths

- Theoretical analysis is solid and convincing. - The problem studied is interesting. Although running no-regret dynamics leads to CCE, no work attempts to doubt "running no-regret" this thing itself.

Weaknesses

I think some realistic running examples can be supplemented for better illustration.

Questions

See in Weaknesses

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See in Weaknesses

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.

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.

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.

Questions

NA

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

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. The 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.

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. The complexity results at the end are a nice touch as well.

Weaknesses

I have no major complaints about the paper. Here are some minor comments/issues: - 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). - p.6: "Further, each equilibrium set can be optimized over via a linear program.": I'm not sure what this means. - 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 - 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. [Barman & Ligett 2015]: "Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard"

Questions

none

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

n/a