Understanding Model Selection for Learning in Strategic Environments

Firstly, we would like to thank the reviewer for the time and effort spent looking through our work. We are delighted to see how the reviewer recognizes this research direction as interesting and points to it as a realistic phenomenon that has potential interest to practitioners. Additionally, we appreciate the comment on the paper's writing. Please find below our expansion on some of the comments and questions raised:

Punctuations and editorial concerns

Thank you for the comments on punctuation edits. We will correct these in the final version.

...I also wouldn't view these papers as about learning in games.

We concede that not all papers referenced take the lens of learning in games; however, they are all about deploying learning algorithms/classifiers in game-theoretic environments. In our work, we show that model complexity in these environments is a non-trivial matter over and beyond simply generalization error considerations.

The model is a bit unusual and idealized (e.g., assuming uniqueness of equilibrium) for strategic machine learning

As a comment, our general model does not make assumptions on uniqueness of equilibrium. We do make assumptions for the proof of a negative result (please see general comment for more information on assumptions).

It sounds like you are treating strategic machine learning as a simultanous-move game, rather than a Stackelberg game

Our model also does indeed capture cases where the interaction between the learner and environment is a Stackelberg game as well. We describe our findings in the preliminaries section and point to the Appendix to the full set of results including illustrations for Stackelberg environments. Concretely: in the paper, we look at how performance at equilibrium scales as a function of model class expressivity across 4 types of strategic environments and find that:

1. In Stationary, and Stackelberg environments where the learner leads, performance at equilibrium scales monotonically as a function of model class expressivity. This is in line with the view of traditional machine learning where performance does scale monotonically as a function of the model class’ expressivity.
2. In Stackelberg environments where the learner follows as well as in Nash environments, performance at equilibrium does NOT scale monotonically as a function of model class expressivity. This is in stark contrast to the growing consensus that, the larger and more expressive the model, the better performance

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?

The problem that the learner faces is that of first selecting a class of models (which can be thought of as an action space) and the from that, when engaging in a game with the environment selecting a particular model (or action) for the game. The learner thus has “commitment power” in that they are first able to select a class of models or space over which to play. This work shows that this first task of selecting a class of models over which to play, depending on the type of game, is non-trivial. In particular, for Nash games and Stackelberg games where they are the follower, it very well may be the case that increasing the size of your model class may lead to equilibria that yield worse payoffs for the learner. This is in direct contradiction to conventional wisdom in machine learning which seems to suggest that adding models / actions to a set which you are optimizing over will lead to performance that is at least as good as when optimizing over a strict subset.

We consider performance at equilibrium positions in each of the sub-game archetypes as these are stationary points. Considering performance at equilibrium is a common benchmark in strategic interactions’ analyses e.g., [1][2]. in a Nash game, therefore, a Stackelberg equilibrium may not be a Nash equilibrium and therefore would not be a stable point for that particular game archetype.

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?

Please refer to the general comment.

References

[1] Meena Jagadeesan, Michael Jordan, Jacob Steinhardt, and Nika Haghtalab. Improved bayes risk can yield reduced social welfare under competition

[2]Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. “Performative prediction.”

We would like to thank the reviewer for the time and effort spent reviewing our work. We are delighted to see that the reviewer recognizes the importance of the findings discussed. Please find below our response to your questions and concerns.

Questions

Thank you for pointing out places where we could further describe the mathematical notation we used.

Assumption 4.1, what is F?

Here F is the gradient operator (i.e., F(x) is the gradient evaluated at point x).

Thm 3.4.

Here $\theta^*, e^*$ is the unique Nash equilibrium in $\Theta \times \mathcal{E}$.

Line 149: define $\Omega$ and $\mathcal{E}$.

Here $\Omega$ is the space of all model classes and $\mathcal{E}$ is the space of all actions the environment can select.

We firstly would like to thank the reviewer for the time and effort spent in looking through our work. We are delighted to see how the reviewer recognizes how this work challenges conventional wisdom with respect to model selection in machine learning. Additionally, we appreciate the comment on the relevance of this line of work in building robust machine learning models for real world applications. Please find below our expansion on some of the comments and questions you raised:

Weaknesses

1. Some of the theoretical results presented in the paper rely on strong assumptions, e.g., strong monotonicity ensuring the 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 illustrative examples focus on simplified policy classes, which may not be representative of practical applications. The effect of different model architectures or generalization to larger team sizes is not considered.

3.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$

For the main theorem (Theorem 3.4.) and the work on the identification of a model class please see the general comment.

We are also excited by the prospect of future work showing this phenomenon clearly through real-world large scale controlled experiments and deployments which we did not have the capacity to do. Our examples were selected to illustrate the range of scenarios one can expect to observe non-monotonicity of performance degradation–not an empirical evaluation.

Questions

Line 221: "... for some p¯∈[0,1]" - should this be p¯>=0.5 since "p∈[1−p¯,p¯]" does not seem to make sense otherwise?

Yes, you are correct. Thank you for pointing this out. We will edit this in the final version.

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?

We believe that we would be able to see the same phenomenon present itself in more complicated regimes, such as repeated game settings with complicated strategies or time-adaptive policy classes. We anticipate some of the analyses would need to be adjusted to take into account additional complexity, and we look forward to future work that dives more deeply into the nuances of more complicated games and strategies.

Firstly, we would like to thank the reviewer for the time and effort spent looking through our work. We are delighted to see how the reviewer recognizes the novelty of the paper’s study as well as the unintuitive, surprising, yet impactful consequences of the notions investigated. Additionally, we appreciate the comment on the paper's writing. Please find below our expansion on some of the comments and questions you raised:

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

You are correct in identifying commitment as a crucial factor in giving rise to this phenomenon. However, the non-monotonicity of performance we illustrate does not arise from gaining or losing commitment power (in our model, model class selection occurs at the beginning regardless of the type of game). Non-monotonicity arises from the difficulty in selecting a commitment in the presence of strategic environments.

As to the question of why it is we observe this complexity in the model class expressivity to equilibrium-payoff function, we make links to work that has explored this unintuitive landscape. Most prominently, Braess’ paradox made the observation of how adding a road to a road network can slow down traffic flow through the network. One can view our results as an instantiation of this Braess paradox-like phenomenon within the realm of machine learning. Other works include results on the non-convexity of Stackelberg losses [1]

The appendix proofs could be written more clearly. In the Theorem 3.4 proof, how is the possibility that ∇θBRe(θ∗)=−1 being ruled out?

Thank you for your feedback on the appendix, we will work to improve clarity in this section. For Theorem 3.4., This is another regularity assumption on the game for this negative result. For a more concrete discussion, please see general comment.

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?

Please see general comment for discussion

[1] Basar, T., & Olsder, GJ. (1999). Dynamic noncooperative game theory. 2nd ed