Understanding Model Selection For Learning In Strategic Environments

Summary

The paper studies (non-)monotonicity of equilibrium payoff in certain classes of two-player games, which has implications for strategic machine learning. Under structural assumptions, the main results are: (1) if the unique equilibrium is not Pareto-optimal, then a player can unilaterally restrict the action space and obtain a better equilibrium in the new, restricted game (similar phenomena happen in more specific example games corresponding to strategic machine learning), and (2) there's an algorithm for selecting the best "model class" (i.e., action subspace) in the same setting.

Strengths

The authors identify an interesting (and to some extent, realistic) phenomenon and establish formal claims about it. The paper is well written and polished. The message might be interesting to practitioners.

Weaknesses

My main complaints are (1) the model is a bit unusual and idealized (e.g., assuming uniqueness of equilibrium) for strategic machine learning, and (2) the results don't appear proportionally strong. See detailed comments below.

Questions

(also including detailed comments) Line 50: extra space after "--" Quick comments on contributions (before reading sec 1.1 and anything after that): it sounds like you are treating strategic machine learning as a simultanous-move game, rather than a Stackelberg game, which is a bit unusual. Is there a reason for that (for one thing, I suppose your results won't hold in the Stackelberg game formulation, where "larger models" are always no worse...)? Also it sounds like the results are really about abstract games rather than specific games induced by machine learning tasks, which makes me wonder to what extent the paper is about model selection (and not strategic interaction in general). Around line 96: well, I'm not sure "papers ... all analyze games in which a learner attempts to update their model through repeated retraining". In particular, there's a bunch of papers in strategic machine learning that study one-shot solutions of the Stackelberg game, including the seminal paper [10] which the authors cite repeatedly. I also wouldn't view these papers as about learning in games. After reading sec 3: I still feel the results are somewhat ambivalent. In particular, if the learner has the commitment power and information to "select a good model" in the simultaneous-move setting, then why can't the learner simply play a Stackelberg equilibrium? Of course this is a very vague argument, but so is the one presented in the paper... Line 304: extra space Sec 4: correct me if I'm wrong -- is the result simply saying "try every class and pick the best one"? And I imagine you can remove the doubling procedure if there's a target suboptimality that can be tolerated?

Rating

5

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

No concerns.

Summary

They study the trade-off between model expressivity and performance at equilibrium in presence of strategic interactions. They show that strategic interactions can cause non-monotone performance at equilibrium when the model gets more expressive. They show Braess'-paradox like examples where reverse scaling occurs, i.e. the larger and more expressive the model class a learner optimizes over, the lower their performance at equilibrium. Furthermore, they formulate a problem of model-selection in games. In this formulation, each player has a number of action sets to choose from and must find one that yields the best payoff. Under the assumption that both environment and the learner use SGD, they propose an algorithm for this problem where the avg payoff over iterations in their algorithm concentrates to the payoff in the Nash equilibrium.

Strengths

I think overall the results are interesting.

Weaknesses

Overall, I found the results interesting.

Questions

Assumption 4.1, what is F? Thm 3.4. define \delta^* and e^*. Line 149: define \Omega and \calE.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

same as above.

Summary

This paper studies the relationship between model class expressivity and equilibrium performance when there are strategic interactions between agents in MARL settings. In contrast with the conventional scaling laws in machine learning, where task performance typically improves with larger or more expressive model classes, this paper highlights a phenomenon similar to Braess' paradox where in certain strategic environments like 2-player games between the learner and the environment with a unique Nash equilibrium, using less expressive model classes for the learner can lead to better equilibrium outcomes. It is theoretically proved that if the Nash equilibrium is not Pareto-optimal, the learner can always restrict its model class to achieve better outcomes. This is further explained with illustrative examples for a 2-player Markov game and for strategic classification in Participation Dynamics. Finally, the authors formulate the problem of model selection in strategic environments and propose a successive elimination based algorithm for the learner to identify the best model class whose Nash equilibrium yields the highest payoff among a candidate set of model classes. Overall, the main ideas presented in this paper are: - The choice of model class should be treated as a strategic action when deploying models in strategic environments. - There's a need to rethink scaling laws before deploying increasingly complex models in real-world strategic settings.

Strengths

1. This paper challenges the conventional wisdom about scaling laws in machine learning, and draws attention to how strategic interactions between the learner and its environment can affect equilibrium performance. This is an important and relevant topic towards making machine learning models robust for real world applications. 2. The paper clearly outlines the assumptions made in the different settings for which theoretical guarantees have been provided, along with illustrative examples in related domains to better understand the applicability of its insights.

Weaknesses

1. Some of the theoretical results presented in the paper rely on strong assumptions, eg. strong monotonicity ensuring existence of a unique Nash equilibrium, or assuming the availability of SGD estimators with decreasing step sizes for all players, which may not always hold in practice. This paper does not focus on empirical evaluations to validate its claims. 2. The proposed algorithm for online model selection shows the existence of a tractable algorithm to choose between candidate model classes under certain assumptions, but the number of interactions required with the environment increases with the size of the candidate set $n$ (Proposition 4.3) which would be computationally expensive for large model classes. 3. The illustrative examples focus on simplified policy classes which may not be representative of practical applications, and the effect of different model architectures or generalization to larger team sizes is not considered.

Questions

1. Line 221: "... for some $\bar{p}\in [0,1]$" - should this be $\bar{p}>=0.5$ since "$p\in [1-\bar{p}, \bar{p}]$" does not seem to make sense otherwise? 2. Would the analysis presented in this paper also extend to repeated games where player strategies can be adaptive and the effect of model selection might be time dependent?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes, the authors describe the limitations of this approach and potential directions for future work.

Summary

The authors study a strategic learning setting formalized as a game involving a player whose action space is some function class that the player optimizes over. The paper focuses on theoretically demonstrating that, in such games, a learning agent may have an incentive to unilaterally commit to a restricted action space. The main theoretical result of the paper appears to be Theorem 3.4 which states that in unconstrained strongly monotone games with inefficient equilibria, a player can always strictly improve its utility at equilibrium by gaining commitment power in some fashion. The authors also describe the sample complexity of using successive elimination to identify a model class for which the learner's equilibrium utility is near optimal.

Strengths

The paper's study of the impact of model selection on equilibrium performance is to the best of my knowledge novel; usually commitment is studied in the context of commiting to a single action rather than a set-valued commitment more remiscient of meta-games. Though it is intuitive that set-valued commitment should improve one's equilibrium outcome from the perspective of equilibrium selection, the technical result of the paper (Theorem 3.4) studies when equilibrium is unique and thus commitment has the effect of entirely changing the equilibrium set rather than effecting favorable equilibrium selection, which seems less obvious. It seems that such a result should not be possible when model selection coincides with usual commitment where model selection is only of singleton classes, though it would be helpful for the authors to clarify whether this is the case. Generally, the writing of the paper is polished and accessible.

Weaknesses

* Restricting one's model class seems to be equivalent to a form of set-valued commitment. From that perspective, it does not seem particularly surprising that gaining commitment power improves one's equilibrium outcome. If this intuition is not correct and there's subtlety, the authors should clarify so in the paper, which currently does not really discuss model selection as commitment. * The appendix proofs could be written more clearly. In the Theorem 3.4 proof, how is the possibility that $\nabla_\theta BR_e(\theta^*) = -1$ being ruled out? * Could the authors clarify why section 4 is titled "Online learning..."---it's not obvious to me what the online learning aspect of the problem is. It seems to still consider a setting with a fixed game; perhaps the authors meant game dynamics rather than online learning?

Questions

See weaknesses section.

Rating

7

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors have addressed any potential negative impacts.

Response

Thanks for the clarifications---and I agree that non-monotonicity is non-obvious from the perspective of commitment. I maintain my positive review.

Acknowledgement

Thank you for the response. I will maintain my original score, leaning towards acceptance.