Understanding Model Selection for Learning in Strategic Environments

Authors: tinashe  handina
eric  mazumdar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 01:14:48

Abstract: The deployment of ever-larger machine learning models reflects a growing consensus that the more expressive the model class one optimizes over—and the more data one has access to—the more one can improve performance. As models get deployed in a variety of real-world scenarios, they inevitably face strategic environments. In this work, we consider the natural question of how the interplay of models and strategic interactions affects the relationship between performance at equilibrium and the expressivity of model classes. We find that strategic interactions can break the conventional view—meaning that performance does not necessarily monotonically improve as model classes get larger or more expressive (even with infinite data).  We show the implications of this result in several contexts including strategic regression, strategic classification, and multi-agent reinforcement learning. In particular, we show that each of these settings admits a Braess' paradox-like phenomenon in which optimizing over less expressive model classes allows one to achieve strictly better equilibrium outcomes. Motivated by these examples, we then propose a new paradigm for model selection in games wherein an agent seeks to choose amongst different model classes to use as their action set in a game.

Main paper: 
 introduction: 
 Machine learning-and deep learning in particular-has already demonstrated enormous potential to enable new services across a wide spectrum of everyday life. Examples range from chatbots [1] , to hiring [2] , and content moderation [3] . Driving this proliferation is the fact that the increasing availability of compute resources coupled with the abundance of data provided by internet-scale datasets allows one to train larger and larger models while monotonically improving performance [4, 5, 6] . Despite signs of diminishing returns, this consensus has broadly held true. Machine learning algorithms tend to follow a monotonic scaling law: with more compute and data, one can train more expressive models and eke out performance gains.As algorithms are deployed into real-world scenarios, however, they will inevitably come into contact with some form of strategic decision-making-whether that be in the form of adversarial agents attempting to manipulate the output of the algorithm [7] , gig-workers taking actions to enforce better working conditions from learning-powered platforms [8] , or more broadly individuals whose goals are misaligned with those of the algorithm [9] .Reflecting this reality, recent years have seen a surge in research seeking to understand the effects of strategic decision-making on learning algorithms. Two sub-fields in particular include strategic classification [10] -in which one seeks to learn a classifier or predictor in the presence of agents who strategically manipulate data-and multi-agent reinforcement learning [11] -in which agents attempt to learn optimal decision-making policies in the presence of other learning agents. Both of these domains draw on ideas from game theory and economics to understand how to design algorithms for strategic settings.In these different regimes, a common refrain is that the presence of strategic interactions invalidates many of the foundational assumptions underlying many machine learning algorithms. For example, strategic interactions result in highly non-stationary environments for multi-agent reinforcement learning (MARL) [11] and seemingly innocuous design decisions like stepsize choices and gradient estimators have been shown to give rise to qualitatively different outcomes in strategic classification [12] . Despite these works, our understanding of model class selection in strategic settings remains underdeveloped. To that end, in this paper, we consider the following question:How do strategic interactions affect the relationship between model class expressivity and equilibrium performance?Contributions: We show through simple theoretical models, illustrative examples, and experiments that strategic interactions can yield a non-trivial relationship between model class expressivity and equilibrium performance. In particular, we show how-even in highly structured regimes in which one has full access to the underlying data distribution-strategic interactions can result in a Braess' paradox-like phenomenon: the larger and more expressive the model class a learner optimizes over, the lower their performance at equilibrium.To understand why this is possible, we make links with the literature in economics on comparative statics, which seeks to understand how the equilibria of games vary with exogenous factors. We show that even in convex games with a unique equilibrium, if the equilibrium is not Pareto optimal (i.e., there exists coordinated deviations that improve the utilities of both players), then there always exists a unilateral restriction of one's action set over which one could have played and had a better equilibrium outcome. Conversely, we show that if an equilibrium is Pareto optimal (which encompasses not only traditional optimization but also adversarial games), performance at equilibrium will tend to scale monotonically with respect to model class expressivity. To make this result concrete, we give examples of strategic regression, strategic classification, and MARL in which reverse scaling occurs.Our result suggests that-if the model will be deployed into a strategic environment-the choice of model class should be treated as a strategic action. Following up on this observation, we formulate a problem of model-selection in games. Whereas learning in games traditionally takes the action set for a player as given, we propose a new formulation in which a player has a number of action sets to choose from and must find the one that yields the best payoff. As a proof-of-concept, we provide an algorithm to identify the best set in a class of structured games.Before describing our model and results, we comment on related work in both machine learning and economics.Scaling laws in Machine Learning: Within statistical machine learning, the study of scaling laws is motivated by the task of choosing a sufficiently expressive class of models to optimize over a given dataset [13] . Non-monotonicity of scaling laws emerged classically due to overfitting [14] -in which the model is too expressive relative to the size of the data set, which can degrade performance at deployment. Such problems are fundamentally linked to understanding the behavior of the empirical risk as one optimized over larger and larger model classes [15] .Deep learning upended this way of thinking with the development of a theory for generalization beyond what is called the threshold of interpolation [16] . More recently, work has investigated how the performance of large language models scales with expressivity (measured in the number of parameters) [4, 5, 6] and the size of the dataset it is trained on [17] . In each of these works, the scaling laws increase monotonically in both the amount of data and expressivity.In our paper, we sidestep issues of sample complexity (i.e., dataset size) to isolate the interplay between expressivity and strategic interactions. While the minimum of the population risk for supervised learning monotonically decreases because optimizing over a larger space can only improve performance, we show that the population risk is non-monotonic in strategic environments. Thus, the phenomenon that we highlight holds even without consideration of sample sizes or generalization errors and adds to a growing body of literature on the difficulties of learning in game theoretic environments.Learning in strategic environments: Recent years have seen a surge of interest in understanding the effects of strategic interactions on learning algorithms. Some of the most relevant areas of interest are strategic classification [10] and performative prediction [18] , adversarial machine learning [7] , and multi-agent reinforcement learning [11] . A unifying theme across these areas is the integration of ideas from game theory into problems of machine learning, wherein one seeks to learn an optimal model given the presence of strategic agents who may themselves be learning. For example, papers on strategic classification [19] , strategic regression [20] , and participation dynamics [21, 22] all analyze games in which a learner deploys learning algorithms in game-theoretic environments. Similarly, work on MARL naturally builds upon the foundation of Markov games [23, 24] .One can view all of these problems as an instance of learning in games [25] -which has seen a resurgence in the machine learning literature in recent years due to these connections [26, 27] . In this paper, we adopt, in particular, the framework of continuous games [28] in which players' action sets can be compact convex subsets of R n .In this class of games, recent work has made clear that learning can be much more complex than in stationary environments-with non-trivial consequences including instability and convergence to cycles and chaos when using gradient-based learning [29] , small design choices like stepsizes and gradient estimators leading to different equilibria [12] , and strategic manipulations allowing for better causal discovery [30] .The question of whether our current understanding of scaling laws holds in these environments is still relatively understudied. Recent empirical work has shown that scaling laws in zero-sum MARL mirror those for deep reinforcement learning and deep learning more generally [31] . Most relevant to our work is a recent paper that studied the non-monotonicity of users' social welfare as firms deploy larger and larger models [32] . The paper considers an environment in which multiple firms compete over a set of users and analyzes the welfare of the users as all firms choose more complex models. They show through a simple model and extensive experiments that if all firms use larger models, the users' welfare can decrease. In this paper, we formulate a more general model that encompasses their interaction and more general problems of strategic classification and MARL. We take an orthogonal track, which is to ask whether it is rational for self-interested learners to unilaterally restrict the expressivity of their models in strategic settings. We show that this is indeed the case under certain conditions.Changing equilibrium outcomes in game theory: Finally, we would be remiss if we did not discuss the large body of work in economics that studies changes in equilibrium outcomes in games.A similar phenomenon to the one we highlight is the well-known Braess' paradox in strategic routing [33] in which one can add a road to a network and increase congestion. Even more related is the informational Braess' paradox [34] in which more information over the network can yield worse equilibrium outcomes for agents in routing games. Many classic works in dynamic game theory have also highlighted the unintuitive ways information and statistical estimation affect equilibrium outcomes in games [35, 36] .More generally, a large body of work in economics studies comparative statics-i.e., how equilibrium payoffs change as exogenous variables are changed [37] . The literature has mostly been concerned with deriving conditions under which payoffs change monotonically in the exogenous variables, a field known as a monotone comparative statics [38] . Our work can be seen as an attempt to understand these ideas in the context of strategic machine learning.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The claims made in the abstract and introduction do reflect the contributions and scope of the paper. 
preliminaries: 
 To understand the dependencies between strategic decision-making and model complexity, we examine different strategic environments. In our model, the learner has access to an ordered set of model classes A, which are all subsets of one large class Ω.A = {Θ k } N k=1 is ordered if for all Θ i , Θ j ∈ A, if i < j it implies that Θ i ⊆ Θ jThe set A may be a set of nested policy classes in MARL or a set of neural network architectures of increasing size for strategic classification. Importantly, the model classes have monotonically increasing expressivity when measured in classic notions of expressivity like V-C dimension [15] .Before engaging with the strategic environment, the learner chooses a model class Θ i ∈ A over which to optimize. In some instances, we refer to model classes as action spaces, and we use these two terms interchangeably. The selection of a model class fixes the optimization problem the learner will then attempt to solve through interactions with the environment. We model interactions with the environment as a two-player game and assume that players find equilibrium outcomes. We assume the learner has a loss function f l : Ω × E → R which they seek to minimize that also depends on the action of the environment. Similarly, the environment will have a loss function f e : Ω × E → R.Here Ω is the learner's action space whilst E is the environment's action space.To model different strategic interactions, we make different assumptions on the nature of the game played and the equilibrium outcomes. We focus on four types of strategic environments: Stationary Environments where the environment actor only has a single action, Stackelberg Environments where the Learner leads, Stackelberg Environments where the learner follows, and General Nash Environments. We provide a concrete description of each of these environments in Appendix A.1.In the next section, we analyze General Nash environments and show that payoffs do not necessarily monotonically increase in expressivity. In Appendix A.2, we provide a set of theoretical results that show how equilibrium payoffs are monotonically increasing in expressivity in Stationary and Stackelberg environments where the learner leads. We then show in Appendix A.3 how payoffs also do not necessarily monotonically increase in expressivity in Stackelberg environments where the learner follows.The equilibrium outcome is the Stackelberg equilibrium of the two-player game under the assumption that the learner leads. This is, for example, the setup adopted in strategic classification [10] . The equilibrium is a joint strategy (θ * , e * ) such that:θ * = arg min θ∈Θi f l (θ, BR e (θ)),and e * = BR e (θ * ) = arg min e∈E f e (θ * , e).Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We do provide a description of the limitations of the work and avenues for further exploration.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
non-monotonic scaling of performance in nash settings: 
 In this section, we present our investigation of the relationship between model class expressivity and equilibrium performance in Nash setting. We show how even under strong assumptions on the regularity of the game, there always exists a way for a player to restrict their model class, resulting in a game with a Nash equilibrium that has a lower loss if the original Nash equilibrium is not Pareto optimal (i.e., the game is not zero-sum or strategically zero-sum). We note that this is a negative result which is an existence proof. To concretely establish this phenomenon, we illustrate through examples in multi-agent reinforcement learning and strategic classification how in settings where these assumptions are relaxed, this phenomenon still exhibits itself.To prove our main result, we assume the two-player game is strongly monotone on the space Ω × E ⊂ R n . Definition 3.1. A two-player game is µ-strongly monotone if the generalized gradient operator F : Ω × E → R n given by:F (x) = ∇ θ f l (θ, e)∇ e f e (θ, e) where: x = (θ, e), satisfies:⟨F (x) -F (x ′ ), x -x ′ ⟩ ≥ µ∥x -x ′ ∥ 2 ∀ x, x ′ ∈ Ω × EA strongly monotone game is a convex game [28] . Implicitly, it assumes that the two players' losses are µ strongly convex in their own action and makes a further assumption on the interaction between players' actions [27] . The assumption of strong monotonicity ensures that there is always a unique Nash equilibrium and that issues of multiple equilibria do not arise.This assumption is once again made to isolate the phenomenon of interest. In the case with multiple Nash equilibria we believe that it is possible to have different equilibrium outcomes exhibiting different scaling behavior-though we leave such analyses for future work. We remark that we make these assumptions for illustrative purposes and that many of our numerical experiments show the same result under milder game structures.On top of the assumption of strong monotonicity we require several smoothness conditions on the players' objectives as well as an assumption that their interaction is not trivially zero at Nash. Assumption 3.2. Assume the game defined on f e and f l is strongly monotone on Ω × E. Further assume that . In all cases, we see the learners' payoff broadly increase at Nash as they optimize over smaller policy classes.1. f l and f e are jointly convex in θ and e.2. The gradient mappings, ∇f l and ∇f e exist and are well defined for all (θ, e). Furthermore, the gradient mappings are L-Lipschitz continuous in the joint action space.3. The Nash equilibrium θ * ∈ Θ is on the interior of Θ with ∇ θ BR e (θ * ) ̸ = 0.To show how the restriction of a model class yields a decrease in loss in a large class of games, we leverage the idea that in many games, a Nash equilibrium is not necessarily a Pareto optimal point [39] . Definition 3.3. A point (θ, e) ∈ Ω × E is Pareto-optimal, if there does not exist ( θ, ê) such that f l ( θ, ê) < f l (θ, e) and f e ( θ, ê) ≤ f e (θ, e)2 Given these assumptions, we prove the following theorem. For ease of exposition, we defer the proof to Appendix B.1. Theorem 3.4. For a two-player monotone game G on Θ × E which satisfies Assumption 3.2, if the unique Nash equilibrium in Θ × E, (θ * , e * ), is not Pareto optimal then there exists a restriction of the learner's model class (i.e., a set Θ ′ ⊂ Θ) such that the restricted game G ′ on Θ ′ × E admits a Nash equilibrium (θ ′ , e ′ ) with:f l (θ ′ , e ′ ) < f l (θ * , e * ).This theorem highlights the fact that the non-monotonicity of scaling laws is, in fact, something we should expect in large classes of games. Indeed, even under mild conditions one can show that there always exists a unilateral restriction that improves payoffs.While the theorem guarantees the existence of a unilateral restriction, which improves equilibrium performance, we remark that it does not say anything about the ease with which one can find this restricted space. While the proof is constructive, it makes use of information of the environment's loss to construct the set-information that may not always be available to the learner. Furthermore, as we show in the following examples, the non-monotonicity can play out in complex ways.Example 1: Multi-Agent Reinforcement Learning We first demonstrate an extreme form of the reverse scaling predicted by Theorem 3.4 in the context of multi-agent reinforcement learning. To do so, we construct a Markov game in which the more the learner restricts their policy class, the more their expected payoff increases. Note that in keeping with the language of MARL, we consider the case when both players would like to maximize their long-run discounted rewards.The Markov game in question is a two-player game with n states. In each state s i , with i ∈ {1, 2, . . . , n}, both players have two actions available to them {0, 1} with 0 corresponding to the top row or left column. In each state, the environment is allowed to choose a policy that is unrestricted, meaning that π e (s) = [p, 1 -p] for any p ∈ [0, 1]. The learner can choose from policies such that: π l (s) = [p, 1 -p] for all p ∈ [1 -p, p] for some p ∈ [0.5, 1]. Varying p generates model classes of varying expressivity. For example, when p = 1, then they are allowed to choose any policy, and for p = 0.5, they are constrained to only playing uniform policies.Given actions a, b from the learner and environment, respectively, we define the transition probabilities as:p(s i+1 |s i , a = 0, b = 1) = p(s i+1 |s i , a = 1, b = 1) = 1 p(s i |s i , a = 0, b = 0) = p(s i |s i , a = 1, b = 0) = 1Thus, the transitions are deterministic, given the action of the environment. This results in the following utilities for the two players, which are simply their sum of discounted rewards3 :u i (π l , π e ) = E π l ,πe ∞ t=0 γ t i R i (s t , a t , b t )where i ∈ {e, l} and γ e , γ l are the player's discount factors. We construct the payoffs for the learner such that they have a dominant strategy of π l (s) = [p, 1-p] in all states, and their expected cumulative payoff increases as the players end up further along the chain of states (as seen in Figure 1 ).We construct the payoffs of the environment player such that they trigger a switch to the next state if and only if the probability that the learner puts on action 0 is below some threshold p * (s). We do so for a sequence of thresholds p * i for i = 1, ..., n such that p * i > p * i+1 > 0.5. With this construction, for p * i+1 < p < p * i the game will result in the players staying in state s i for all time. More details on the construction of the payoff matrices are left to Appendix E and a plot of the equilibrium rewards for the learner as a function of p is shown in Figure 1 for different discount factors for games having n = 50 states.We empirically observe that as p decreases (i.e., the policy class of the learner is restricted), the performance of the learner behaves in non-monotonic ways and can, in fact, be made to increase as the policy class gets closer to the uniform policy. The highly non-convex nature of the case where γ = 0.95 also highlights the difficulty in choosing a model class in general since it can be posed as a non-convex optimization problem.A key takeaway of this example is that in general-sum MARL, restrictive policy parametrizations like e.g., softmax policies or function approximation may not lead to worse performance at equilibrium like in competitive and single-agent RL [40] . Indeed our example suggests that the payoff in quantal response equilibria [41] of Markov games (i.e., equilibria in which agents constrain their strategies to a class of quantal responses-see e.g., [41] ) can sometimes have a higher payoff than the unrestricted Nash equilibrium.Example 2: Participation dynamics Our second example is similar to problems considered in the literature on performative prediction [18] though the setup we consider also fits the literature on understanding participation dynamics [32, 21] and algorithmic collective action [9] .In this model, there is a base distribution P 0 over the input-output space X × Y where X is feature space and Y is the output space. The learner is trying to perform supervised learning to learn a mapping g : X → Y. The environment, on the other hand, takes the form of a population of agents that selects a distribution on P on the input-output space (i.e., P ∈ ∆(X , Y)) to maximize their own utility which depends on the choice of the learner.The least restrictive class of models the learner has access to Ω is the set of all functions g : X → Y. We also consider a restricted function class Θ which is the class of all functions g r : X ′ → Y where X ′ ⊂ X is the result of some feature mapping ϕ : X → X ′ . Thus, Θ is the space of all functions of the form g r (ϕ(x)). Clearly Θ ⊂ Ω.We assume that the strategic manipulations of the environment take the form of manipulations to the data distribution which take place by mixing the base distribution P 0 with a manipulated data distribution P e such that the distribution seen by the learner is given by P = αP e + (1 -α)P 0 for some α ∈ [0, 1]. The parameter α relates to the strength of the response distribution within the mixture that the learner observes. It might represent the fraction of the population that engages in strategic manipulations of their data.Finally, we assume that the learner is optimizing the zero-one loss, such that for any distribution P, the best response g or g r is the Bayes-Optimal classifier on X and X ′ respectively are:g * (x) = arg max y P(y|x) & g * r (x) = arg max y P(y|ϕ(x)).Thus, the learner's loss at equilibrium is given by: f l (g * , P) = P r(g * (x) ̸ = y) f l (g * r , P) = P r(g * r (x) ̸ = y), in each case, the probability is taken with respect to P.For the population of strategic agents, we assume that they would like the learner to avoid making use of certain 'protected' features and focus on a set of restricted features ϕ * . To do so, the strategic agents' response to the learner's model depends on the set of features it makes use of. Concretely, if the learner makes use of a set of features ϕ ′ : X → X ′ that are more informative than some ϕ * : X → X * -i.e., X * ⊂ X ′ , then the strategic agents add uniform noise to the base distribution, and if not they report their true data. This can be represented by the following utility function:f e (g, P) = T V (P e , U ) : P r(g(x) ̸ = g(ϕ * (x))) > 0 T V (P e , P 0 ) otherwise,where U is the uniform distribution on X × Y and T V represents the T V distance between distributions.As we will show, for sufficiently large α, the learner is always better off optimizing over the less expressive model class at equilibrium. To do so, we assume that ϕ * preserves enough information for the Bayes optimal classifier on the space X * to be strictly better than random choice. Assumption 3.5. Let |Y| = n. Assume that the Bayes optimal classifier on X * for P 0 denoted g * r (x) = arg max y∈Y P(y|ϕ * (x)) satisfies:f l (g * r , P 0 ) = P r(g * r (x) = y) < 1 nThis leads to the following result for this game. Proposition 3.6. Under Assumption 3.5, consider two functions classes over which the learner can optimize, Ω, and Θ which is the set of all functions from g r : X * → Y, where X * = ϕ * (X ) such that ϕ * (x) = x for x ∈ X * . Consider the corresponding games denoted G and G * , respectively. Then the Nash equilibrium in G is (g * , P * ) where P * = (1 -α)P 0 + αU and the Nash equilibrium in G * is given by (g * r , P 0 ). Furthermore, there exists a range of α ∈ (0, 1) such that:f l (g * , P * ) > f l (g * r , P 0 )The proof of this proposition can be found in Appendix B.2. This proposition highlights the fact that interactions with strategic agents can make less expressive function classes yield better performance in strategic settings.The equilibrium outcome is the Stackelberg equilibrium of the two-player game under the assumption that the learner follows. This is, for example, the case that arises when agents attempt to perform data poisoning attacks [47] or engage in collective action [9] against the learner. Here the equilibrium is a joint strategy (θ * , e * ) such that: 4. General Nash Environments: Which allows us to model the general case when the interaction results in a Nash equilibrium. This is, for example, the desired solution in MARL [11] and participation and regression games [21, 32] . In this setting, the equilibrium outcome is a joint strategy (θ, e) such that:e * =f e (θ, e ′ ) ≥ f e (θ, e) ∀ e ′ ∈ E, f l (θ ′ , e) ≥ f l (θ, e) ∀ θ ′ ∈ Θ i .We remark that in this last case, the assumption of a two-player game is made for simplicity, and our results would go through in n-player games.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: Our contributions are primarily theoretical in nature. The experimental evaluations provided in this paper do not rely on private datasets and can be easily reproduced with the provided settings and parameters.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
online learning for model selection in games: 
 The previous results emphasize the importance of careful model selection in strategic environments.In this section, we consider the problem of learning the best model class to optimize in strategic environments.Due to the unknown and non-stationary nature of the environment, in game theoretic settings, the learner will have to interact repeatedly with the environment to learn which model class and, consequently, which strategy to play. Thus, we formulate a problem of learning in games in which the learner seeks to find the best model class across a set of candidate model classes as well as the best strategy. We frame this as a problem of model selection for games.We remark that model-selection is an area of recent interest in online learning [42, 43] , though-to the best of our knowledge-the paradigm has not been applied to games as yet. Most similar to Algorithm 1 Stochastic gradient descent to find Nash equilibrium in a strongly monotone game 1: procedure PSGD(Θ, x 0 , T ) 2:for t ← 1 to T do 3:η t = 2 µ(t+1)4:x t+1 ← Π Θ×E (x t -η t F (x t )) 5:end for 6:xT = return T t=1 t T (T +1)/2 x t 7: end procedure this problem is a line of work on meta-learning in games, which seeks to find good strategies that generalize across environments [44] .We describe an algorithm for how the learner can select model classes to identify which model class to use. As a proof-of-concept, we assume that all players use stochastic gradient descent and adopt the structure of a problem we analyzed in the Nash environment regime. In particular, we assume the learner has access to sets of subsets of Ω = R d and that their loss and the environment's loss satisfy the following generalization of Assumption 3.2. For simplicity, we let the tuple of a particular model and the environment action be denoted by x (i.e., (θ, e) = x). We note here that F is the generalized gradient mapping as described in Definition 3.1. Assumption 4.1. Assume the game defined on f e and f l is strongly monotone and that they are L-Lipschitz continuous on Ω × E. Further, assume that the players have access to stochastic gradient estimators such that the estimated monotone mapping F satisfies, ∀x ∈ Ω × E:E[ F (x)] = F (x) and E[∥ F (x) -F (x)∥ 2 ] ≤ σ 2 .Given this assumption and under the simplifying assumption that all players use decreasing stepsizes, we assume that for a given model class Θ i the players engage in projected stochastic gradient descent of the form:x t+1 = Π Θi×E x t -η t F (x t ) ,where Π denotes the Euclidean projection onto Θ i × E. The pseudocode for this is described in Algorithm 1. We show that the running average of the iterates resulting from running this algorithm in an environment satisfying Assumption 4.1 concentrates quickly around the payoff at the Nash equilibrium. The proof of this proposition can be found in Appendix C. Proposition 4.2. Let Θ correspond to a particular model class which results in an instance of continuous action µ-strongly monotone game with a unique Nash Equilibrium x * . Under Assumption 4.1 and the assumption that all players use stepsize schedule η t = 2 µ(t+1) , for any δ ∈ (0, 1) Algorithm 1 yields an estimate xT such that:|f l (x T ) -f l (x * )| ≤ O L 2 log( 1 δ ) + L 3 µ 2 T ,with probability at least 1 -δ.To derive this bound, we generalize an existing result from convex optimization [45] . Given these confidence bounds, we now propose a successive elimination algorithm for identifying the best model class in a game. The underlying assumption remains that the environment player is simply doing stochastic gradient descent. This should also extend to the case when the environment performs stochastic mirror descent [46] . The specific form of successive elimination is described in Algorithm 2.As we show, this algorithm has strong properties in terms of identification of the best model class due to the fast concentration of our estimator from Proposition 4.2. We show the results with respect to identification and defer the proof to Appendix C. Proposition 4.3. Under the assumptions of Proposition 4.2, let A = {Θ i } n i=1 . With probability at least 1 -δ, Algorithm 2 identifies the model class whose Nash equilibrium yields the highest payoff after:O n(L 2 log( n δ ) + L 3 ) µ 2 ∆ * Algorithm 2 Successive Elimination for Best Design action Identification 1: procedure SUCCESSIVEELIMINATION({Θ i } n i=1 , δ) 2: S ← {Θ i } n i=1 3: τ = 1 4:while |S| > 1 do 5:T = α2 τ 6: δ ′ ← δ 2nT 2 7:for all Θ i ∈ S do 8:x i T ← Algorithm 1 with (Θ i , x 0 , T ) 9:end for 10:S ← S \ {Θ i ∈ S : ∃Θ j such that:f (x i T ) + L 2 log( 1 δ ′ )+L 3 µ 2 T < f (x j T ) - L 2 log( 1 δ ′ )+L 3 µ 2 T } 11: τ = τ + 1 12:end while 13: return S 14: end procedure interactions with the environment, where ∆ * is the minimum suboptimality gap of the Nash equilibrium of a function class compared to that of the best function class.This result indicates that finding the best model class out of a set of candidate model classes may be computationally tractable in certain regimes. An interesting question that we leave for future work is whether it is possible to be no regret, not just within a model class, but across a set of model classes as well. 
conclusion: 
 This work seeks to provide a framework for understanding the complexities that arise when models are released into strategic environments. We show that the prevailing understanding of scaling laws in machine learning fails to hold in large classes of strategic environments and show its implications for MARL and strategic classification, among other areas. Lastly we highlight a possible algorithmic solution to overcoming the problem of model selection in games in which we were able to design an algorithm to efficiently learn the best model class to optimize over without sacrificing performance in terms of regret.Altogether, our results are a first step towards understanding scaling laws and hence, model selection in strategic environments. Our results suggest that we need to rethink our understanding of scaling laws before blindly deploying ever more complex models into real-world environments in which they will be faced with strategic behaviors. We leave many avenues of future work open, including questions about generalization and finite sample considerations, as well as the potential for more sophisticated algorithmic approaches to model selection. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We provide all the necessary details to understand the results.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We include the necessary information to understand the significance of the experimental procedures.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: This paper does discuss the societal impacts of the work being performed. Our work is theoretical in nature but it contributes to the growing body of research which seeks to enhance our understanding of how machine learning operates in real world environments. Having a better understanding of the interplay between machine learning systems and strategic environments allows for a more principled understanding of the impact and consequences that machine learning algorithms have on society. We outline scenarios of societal engagement in the introduction. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Paper poses no such risks Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This paper does not release new assets Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This project does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: We do not leverage crowdsourcing nor research with human subjects Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We begin by providing a concrete description of each of the learner -environment settings we explore:1. Stationary Environments: The environment has only one action (i.e., E = {e}), and the problem reduces to that of classical ML. The resulting equilibrium is simply the minimum of the learner's loss given e and the model class Θ i :θ * = arg min θ∈Θi f l (θ, e).We investigate the two cases in which performance monotonically increases as a function of complexity: stationary environments and Stackelberg interactions where the learner has commitment power (i.e., the learner "leads"). This fact follows from the elementary observation that in both of these regimes, the learner simply solves the same optimization problem over a larger space. Proposition A.1. Let A be an ordered set. Consider two model classes, Θ i , Θ j ∈ A with i < j. If (θ i , e i ) and (θ j , e j ) are equilibrium outcomes in stationary environments or Stackelberg environments in which the learner leads with the instantiated model classes being Θ i and Θ j respectively, thenf l (θ i , e i ) ≥ f l (θ j , e j )Proof. For a stationary game, the proposition above follows naturally. We know that e i = e j which we denote e * . Since θ i ∈ Θ i ⊆ Θ j , the equilibrium (θ j , e * ) necessarily must be such that f l (θ j , e * ) ≤ f l (θ i , e * ), otherwise (θ j , e * ) is not an equilibrium point.For a Stackelberg game where the learner leads, the proposition follows the same argument. According to Stackelberg dynamics, we know that BR(θ i ) = e i and BR(θ j ) = e j . We can see that it must be the case that f l (θ j , e j ) ≤ f l (θ i , e i ) otherwise simply selecting θ i when optimizing in Θ j would be a profitable deviation.While this proposition is trivial to prove, it has implications for adversarial machine learning and strategic classification. Adversarial learning can be modeled as zero-sum or min-max games [7] . In these games, if the Nash equilibrium exists, it coincides with the Stackelberg equilibria via simple min-max theorems [48] . This implies that the basic intuition of scaling laws holds true for adversarial learning. Similar takeaways hold true for strategic classification because it is commonly modeled as a Stackelberg game in which the learner leads.We also consider the case in which the environment results in a Stackelberg equilibrium where the learner follows. In lieu of a general result for this case, we construct a simple example in strategic linear regression that highlights the fact that when the learner follows in a Stackelberg game-as happens in settings such as collective action and non-adversarial backdoor attacks in machine learning-the use of more features can actually hurt.Figure 2 : The loss for the learner at their best response in a regression game as the magnitude of the environment's perturbation vector varies with the payoffs achieved at equilibrium as derived in Proposition A.2.Example 3: Strategic Linear Regression In this setup, we have a decision maker who would like to solve a regression problem and is choosing between different feature mappings they can use to fit a model. More precisely, we consider a learner deciding between whether to pick ϕ 1 θ (x) = θ T x or ϕ 2 θ (x) = θ T 1 x + θ 2 exp(-∥x∥ 2 ) as the function to use for the regression task. The classifier's goal is to learn θ so as to minimize the expected squared error. In this framework, the environment can add a deviation e to the dataset. This would mean that the input to the regressor model would be x + e.Θ ϕ 1 θ (x) , Θ ϕ 2 θ (x) derived from ϕ 1 θ (x), ϕ 2 θ (x) respectively. We show that despite Θ ϕ 1 θ (x) ⊂ Θ ϕ 2 θ (x), at a Stackelberg equilibrium, the learner has a higher payoff when they learn from Θ ϕ 1 θ (x) as opposed to Θ ϕ 2 θ (x) . This is in stark contrast to what happens in stationary environments in which adding features never hurts performance since they can just be given a weight of 0. More concretely: Proposition A.2. Consider a dataset where each data point x ∈ R d is drawn from a distribution D. A learner has the option to select one of two model classes:Θ ϕ 1 θ (x) = {ϕ 1 θ (x) : θ ∈ R d where: ϕ 1 θ (x) = θ T x} Θ ϕ 2 θ (x) = {ϕ 2 θ (x) : θ 1 , θ 2 ∈ R d × R where: ϕ 2 θ (x) = θ T 1 x + θ 2 exp(-∥x∥ 2 )}.Assume that each data point can be perturbed by an error vector e ∈ C ⊆ R d , resulting in the learner observing x + e instead of x. For some compact convex C, distribution D and dimension d, the Stackelberg equilibrium attained by optimizing over Θ ϕ 1 θ (x) results in a strictly lower loss than that attained by optimizing over Θ ϕ 2 θ (x) . The calculations for this proposition are in the Appendix D. Figure 2 highlights the non-monotonicity of performance between different equilibria in the two spaces. We see that at the Stackelberg equilibrium, the larger model class incurs a greater loss than the smaller model class despite the fact that the loss incurred by the larger model class is lower than that incurred by, the lower model class in a point-wise sense.B.1 Proof of Theorem 3.4We begin by revisiting the main assumptions of this proof: Assumption B.1 (Restatement of Assumption 3.2). Assume the game defined on f e and f l is strongly monotone on Ω × E. Further assume that 1. f l and f e are jointly convex in θ and e.2. The gradient mappings, ∇f l and ∇f e exist and are well defined for all (θ, e). Furthermore, the gradient mappings are L-Lipschitz continuous in the joint action space.3. The Nash equilibrium θ * ∈ Θ is on the interior of Θ with ∇ θ BR e (θ * ) ̸ = 0. Theorem B.2 (Restatement of Theorem 3.4). For a two-player monotone game G on Θ × E which satisfies Assumption 3.2, if the unique Nash equilibrium in Θ × E is not Pareto optimal then there exists a restriction of the learner's model class (i.e., a set Θ ′ ⊂ Θ) such that the restricted game G ′ on Θ ′ × E admits a Nash equilibrium (θ ′ , e ′ ) with: f l (θ ′ , e ′ ) < f l (θ * , e * ).Proof of Theorem 3.4. Note the following: because we can achieve strictly lower loss for the jointly convex loss function f l , we know that ∇f l (θ * , e * ) ̸ = 0 Consider the following the function fl (θ) := f l (θ, BR e (θ)). Here BR e (θ) is the best response of the other player to the action θ, i.e., BR e (θ) := arg min e∈E f e (θ, e).Relying on this function definition, we describe a particular restriction on the model class Θ and then find a Nash equilibrium for this model class, which is different from (θ * , e * ) and whose loss for the Θ-player is lower in this new equilibrium.Realize that ∇ fl (θ * ) = ∇ θ f l (θ * , BR e (θ * )) + ∇ θ BR e (θ * )∇ e f l (θ * , BR e (θ * )) ̸ = 0. In particular, we note that ∇ θ BR e (θ * ) • ∇ e f l (θ * , BR e (θ * )) ̸ = 0 since if it were, it would mean that either ∇ θ BR e (θ * ) or ∇ e f l (θ * , BR e (θ * )) were equal to zero which is not the case. ∇ e f l (θ * , BR e (θ * )) = 0, would mean that both ∇ θ f l (θ * , BR e (θ * )) and ∇ e f l (θ * , BR e (θ * )) = 0 implying a global minimum which would contradict the existence of a Pareto improving point. ∇ θ BR e (θ * ) ̸ = 0 follows from the Assumption 3.2.Noting the fact that ∇ fl (θ * ) ̸ = 0 allows us to pick a direction with respect to the inner product with ∇ fl (θ * ), let v be any vector ∈ R d θ such that ⟨v, ∇ fl (θ * )⟩ > 0. Consider θ ′ = θ * -δv for some δ > 0. Let e ′ = BR e (θ ′ ). We will now define Θ ′ ⊂ Θ such that the game on the model class Θ ′ × E has (θ ′ , e ′ ) as a Nash equilibrium Let Θ = {θ ∈ Θ : ⟨θ-θ ′ , v⟩ ≤ 0}. We then go on to define Θ ′ = {θ ∈ Θ : ⟨∇ θ f l (θ ′ , BR e (θ ′ )), θ ′ -θ⟩ ≤ 0}. Notice how the first step removes (θ * , e * ) from the construction. The second step makes it such that BR θ (e ′ ) = θ ′ for all θ ∈ Θ ′ . Since e ′ is the best response to θ ′ we get that the point (θ ′ , e ′ ) is a Nash equilibrium.What is left to show is that we can create such a restriction with the characteristic that the Θ-player's loss function is lowered at the new equilibrium. To do this, we rely on the choice of the δ parameter.δ > 0 such that f l (θ ′ , e ′ ) < f l (θ * , e * )To see this, consider the Taylor expansion of fl (θ ′ ) at θ * .fl (θ ′ ) = fl (θ * ) + ⟨∇ fl (θ * ), θ ′ -θ * ⟩ + 1 2 (θ ′ -θ * ) T H θ ( θ)(θ ′ -θ * ) ≤ fl (θ * ) + ⟨∇ fl (θ * ), θ ′ -θ * ⟩ + L 2 ∥θ ′ -θ * ∥ 2 = fl (θ * ) -δ⟨∇ fl (θ * ), v⟩ + δ 2 L 2 ∥v∥ 2In the first line θ ∈ {θ ∈ Θ : θ = λθ * + (1 -λ)θ ′ , λ ∈ [0, 1]}. We note that by our construction ⟨∇ fl (θ * ), v⟩ > 0. Furthermore, we realize that the term δ⟨∇ fl (θ * ), v⟩ ∈ O(δ) and that δ 2 L 2 ∥v∥ 2 ∈ O(δ 2 ). This means we can select a value of δ such that the term δ⟨∇ fl (θ * ), v⟩ -δ 2 L 2 ∥v∥ 2 is positive. With this, we can then deduce that fl (θ * ) > fl (θ ′ ) which then completes the proof.We begin with proving the proposition on Strategic classification. Here we restate the assumptions again: Assumption B.4 (Restatement of Assumption 3.5). Let |Y| = n. Assume that the Bayes optimal classifier on X * for P 0 denoted g * r (x) = arg max y∈Y P(y|ϕ * (x)) satisfies: Proposition 3.6) . Under Assumption 3.5, consider two functions classes over which the learner can optimize, Ω, and Θ which is the set of all functions from g r : X * → Y, where X * = ϕ * (X ) such that ϕ * (x) = x for x ∈ X * . Consider the corresponding games denoted G and G * respectively. Then the Nash equilibrium in G is (g * , P * ) where P * = (1 -α)P 0 + αU and the Nash equilibrium in G * is given by (g * r , P 0 ). Furthermore, there exists a range of α ∈ (0, 1) such that:f l (g * r , P 0 ) = P r(g * r (x) = y) < 1 n Proposition B.5 (Restatement off l (g * , P * ) > f l (g * r , P 0 )Proof of Proposition 3.6. To prove the first part of this proposition, we note that (g * , P * ) is a Nash equilibrium in that no player has any incentive to unilaterally deviate given their action sets. Indeed, if g * is the Bayes-optimal classifier on P * in Ω then P r(g(x) ̸ = g(ϕ * (x)) > 0 and consequently the environment's best-response perturbation is P e = U . Similarly, g * r , P 0 is the Bayes-optimal classifier on X * and satisfies P r(g(x) = g(ϕ * (x)) = 0 by definition. As such, the environment's best response is given by P e = P 0 .To prove the second part of the proof we note that:f l (g * , P * ) ≥ (1 -α) min g∈Ω f l (g, P 0 ) + α n > α nNow, note that for 1 ≥ α ≥ nf l (g * r , P 0 ), we have that: f l (g * , P * ) > f l (g * r , P 0 )We now present a proof for convergence for the stochastic gradient descent algorithm. We restate the main assumptions here as well: Assumption C.1 (Restatement of Assumption 4.1). Assume the game defined on f e and f l is strongly monotone on Ω × E. Further, assume that 1. The functions f l and f e are L-Lipschitz continuous on Ω × E.2. The players have access to stochastic gradient estimators such that the estimated monotone mapping F satisfies, ∀x ∈ Ω × E: Proposition 4.2) . Let Θ correspond to a particular model class which results in an instance of continuous action µ-strongly monotone game with a unique Nash Equilibrium (x * ). Under Assumption 4.1 and the assumption that all players use stepsize schedule η t = 2 µ(t+1) , for any δ ∈ (0, 1) Algorithm 2 yields an estimate xT such that:E[ F (x)] = F (x) and E[∥ F (x) -F (x)∥ 2 ] ≤ σ 2 . Proposition C.2 (Restatement of|f l (x) -f l (x * )| ≤ O L 2 log( 1 δ ) + L 3 µ 2 T ,with probability at least 1 -δ.Proof of Proposition 4.2. Let x t = (x 1 , . . . , x n ) for a fixed number of players. We then defineF (x t ) =     ∇ 1 u 1 (x t ) ∇ 2 u 2 (x t ) . . . ∇ n u n (x t )     . Let F (x t ) = F (x t ) -Ê(x t ), where E[ Ê(x t )] = 0 and ∥ Ê(x t )∥ 2 ≤ 1 a.s..From the description of Algorithm 2, we can see thatx t+1 = Π Θ×E (x t -η t F (x t ))The proof of this proposition closely mirrors [45] . Let x be the output of Algorithm 1. We can see that:∥x t+1 -x * ∥ 2 = ∥Π Θ×E (x t -η t F (x t )) -x * ∥ 2 ≤ ∥x t -η t F (x t ) -x * ∥ 2 = ∥x t -x * ∥ 2 -2η t ⟨ F (x t ), x t -x * ⟩ + η 2 t ∥ F (x t )∥ 2 = ∥x t -x * ∥ 2 -2η t ⟨ F (x t ), x t -x * ⟩ -2η t ⟨F (x t ), x t -x * ⟩ + 2η t ⟨F (x t ), x t -x * ⟩ + η 2 t ∥ F (x t )∥ 2 = ∥x t -x * ∥ 2 + 2η t ⟨F (x t ) -F (x t ), x t -x * ⟩ -2η t ⟨F (x t ), x t -x * ⟩ + η 2 t ∥ F (x t )∥ 2Rearranging terms we get:2η t ⟨F (x t ), x t -x * ⟩ ≤ ∥x t -x * ∥ 2 -∥x t+1 -x * ∥ 2 + 2η t ⟨F (x t ) -F (x t ), x t -x * ⟩ + η 2 t ∥ F (x t )∥ 2 ⟨F (x t ), x t -x * ⟩ ≤ ∥x t -x * ∥ 2 -∥x t+1 -x * ∥ 2 2η t + ⟨ Ê(x t ), x t -x * ⟩ + η t 2 ∥ F (x t )∥ 2 1 2 ⟨F (x t ), x t -x * ⟩ ≤ ∥x t -x * ∥ 2 -∥x t+1 -x * ∥ 2 2η t - 1 2 ⟨F (x t ), x t -x * ⟩ + ⟨ Ê(x t ), x t -x * ⟩ + η t 2 ∥ F (x t )∥ 2 ⟨F (x t ), x t -x * ⟩ ≤ 2 • ∥x t -x * ∥ 2 -∥x t+1 -x * ∥ 2 2η t - µ 2 ∥x t -x * ∥ 2 + ⟨ Ê(x t ), x t -x * ⟩ + η t 2 ∥ F (x t )∥ 2 t⟨F (x t ), x t -x * ⟩ ≤ 2t • ∥x t -x * ∥ 2 -∥x t+1 -x * ∥ 2 2η t - µ 2 ∥x t -x * ∥ 2 + ⟨ Ê(x t ), x t -x * ⟩ + η t 2 ∥ F (x t )∥ 2 = 2 • t 1 2η t - µ 2 ∥x t -x * ∥ 2 - t 2η t ∥x t+1 -x * ∥ 2 + t⟨ Ê(x t ), x t -x * ⟩ + t η t 2 ∥ F (x t )∥ 2 = 2 • µ 4 • t(t -1)∥x t -x * ∥ 2 -t(t + 1)∥x t+1 -x * ∥ 2 + t⟨ Ê(x t ), x t -x * ⟩ + t µ(t + 1) ∥ F (x t )∥ 2 ≤ 2 • µ 4 • t(t -1)∥x t -x * ∥ 2 -t(t + 1)∥x t+1 -x * ∥ 2 + t⟨ Ê(x t ), x t -x * ⟩ + (L + 1) 2 µWe then sum over all t and noting that the right-hand side has a portion with a telescoping sum, we see that:T t=1 t⟨F (x t ), x t -x * ⟩ ≤ 2 • T t=1 t⟨ Ê(x t ), x t -x * ⟩ + T • (L + 1) 2 µ 1 T (T + 1)/2 T t=1 t⟨F (x t ), x t -x * ⟩ ≤ 4 T (T + 1) • T t=1 t⟨ Ê(x t ), x t -x * ⟩ + T • (L + 1) 2 µBy monotonicity we get note that: µ∥x t -x * ∥ 2 ≤ ⟨F (x t ), x t -x * ⟩ and thus:µ T (T + 1)/2 T t=1 t∥x t -x * ∥ 2 ≤ 4 T (T + 1) • T t=1 t⟨ Ê(x t ), x t -x * ⟩ + T • (L + 1) 2 µ 1 T (T + 1)/2 T t=1 t∥x t -x * ∥ 2 ≤ 4 µT (T + 1) • T t=1 t⟨ Ê(x t ), x t -x * ⟩ + T • (L + 1) 2 µ ∥ T t=1 t T (T + 1)/2 x t -x * ∥ 2 ≤ 4 µT (T + 1) • T t=1 t⟨ Ê(x t ), x t -x * ⟩ + T • (L + 1) 2 µ ∥x -x * ∥ 2 ≤ 4 µT (T + 1) • T t=1 t⟨ Ê(x t ), x t -x * ⟩ + T • (L + 1) 2 µ |f i (x) -f i (x * )| ≤ 4L µT (T + 1) •       T t=1 t⟨ Ê(x t ), x t -x * ⟩ E T + T • (L + 1) 2 µ      To complete the proof, we rely on a high probability bound on E T which makes use of a specialized form of the Generalized Freedman's Inequality.Lemma C.3 ([45] Lemma 4.1). Let E T = T t=1 t⟨ Ê(x t ), x t -x * ⟩. Then for any δ ∈ (0, 1) we have that E T ≤ O L µ • T log( 1 δ )plugging in the bound on E T completes the proof.We then proceed to provide a proof of the successive elimination protocol. This proof which closely follows [49] Proposition C.4 (Restatement of Proposition 4.3). Under the assumptions of Proposition 4.2, let A = {Θ i } n i=1 . With probability at least 1 -δ, Algorithm 2 identifies the model class whose Nash equilibrium yields the highest payoff after:O n(L 2 log( n δ ) + L 3 ) µ 2 ∆ *interactions with the environment, where ∆ * is the minimum suboptimality gap of the Nash equilibrium of a function class compared to that of the best function class. Proof of 4.3. We begin by showing an "anytime" confidence interval bound.Lemma C.5. Let X i,T = f (x i T ) where x i T ← Algorithm 1(Θ i , x 0 , T ) and X * i = f (x * i )where x * i is the Nash equilibrium point for Θ i . We then have that:P n i=1 ∞ T =1 |X i,T -X * i | ≥ L 2 log( 2T 2 n δ )+L 3 µ 2 T ≤ δProof. Here we rely on the union bound to note that:P n i=1 ∞ T =1 |X i,T -X * i | ≥ L 2 log(2 T 2 n δ ) + L 3 µ 2 T ≤ n i=1 ∞ T =1 P |X i,T -X * i | ≥ L 2 log( 2T 2 n δ ) + L 3 µ 2 T ≤ n i=1 δ 2n ∞ T =1 1 T 2 ≤ δLemma C.6. With probability greater than or equal to 1 -δ, the best model class Θ k , is retained in the active set S until the end of Algorithm 2.Proof. Let D be the eventn i=1 ∞ T =1 |X i,T -X * i | ≥ L 2 log(2 T 2 n δ )+L 3 µ 2 T. We know that D C occurs with probability at least1 -δ. Let U (T, δ) = L 2 log(2 T 2 n δ )+L 3 µ 2 T, Θ k is dropped if there exists j, T such that X j,T -U (T, δ) > X k,T + U (T, δ). We consider the scenario where the event D C occurs. In this scenario we have that X * j + U (T, δ) ≥ X j,T and that X k,T ≥ X * k -U (T, δ) for all T . Plugging these two inequalities into the first expression gives us that X * j ≥ X * k which is a contradiction. Therefore, with probability greater than or equal to 1 -δ we have the best model class Θ i remaining in S.Lemma C.7. Given that the best model class Θ k is identified by Algorithm 2, it will terminate afterO n(L 2 log( n δ )+L 3 ) µ 2 ∆ * samples Proof. Let ∆ i = X * k -X * i . Let ∆ * = min i ∆ i .Let Θ k be the action that corresponds to the highest payoff at the Nash equilibrium point. We note that one of the conditions which leads to action Θ i being removed from the consideration set S isEQUATIONAssuming that the event D C holds, for each model class Θ i we have that, X k,T ≥ X * k -U (t, δ) and that X i,t ≤ X * i + U (t, δ). Substituting these expressions into what we have by 1, we get that :X * k -X * i ≥ 2U (T, δ) + 2U (T, δ) ∆ i ≥ 4U (T, δ)Now we consider the case where ∆ i = ∆ * to find a bound for T .∆ * ≥ 4U (T, δ)∆ * ≥ 4(L 2 log( 2T 2 n δ ) + L 3 ) µ 2 T µ 2 T - 8L 2 log(T ) ∆ * ≥ 4(L 2 log( 2n δ ) + L 3 ) ∆ * µ 2 T ≥ 4(L 2 log( 2n δ ) + L 3 ) ∆ * T ≥ O L 2 log( n δ ) + L 3 µ 2 ∆ *From here we proceed to find the τ which corresponds to OL 2 log( n δ )+L 3 µ 2 ∆ *steps which is simply found by taking the log. We then note thatO log( L 2 log( n δ )+L 3 µ 2 ∆ * ) τ =1 2 τ = O L 2 log( n δ )+L 3 µ 2 ∆ * . Summing over n -1 decision actions we get O n(L 2 log( n δ )+L 3 ) µ 2 ∆ *samples which completes the proof.Consider the following setup. The decision-maker would like to solve a regression problem and has the choice of two different regression models. For a distribution of input data D, and a datapoint x, they can either compute:ϕ 1 θ (x) = θ T (x + e)Or:ϕ 2 θ (x) = θ T 1 (x + e) + θ 2 exp(-∥x + e∥ 2 )For the rest of the calculation we take the distribution of the input data to be N (0, I). Suppose the true relationship between features x and outcomes y is linear and is by y = β T x. However, the training data is reported by a population of strategic agents who commit to all manipulating their features in the same way such that the reported features are given by x ′ = x + e. Equivalently, this can be seen as the input data being misreported and generated from a distribution N (e, I).Suppose the population of strategic agents knows that the learner will solve a regression problem. Then, they would like to choose e to maximize their expected prediction given. Concretely:e * = arg max e E[ϕ i θ * (x + e)]Given the fact that θ * = arg min θ E[(y -ϕ θ (x + e)) 2 ]. For this example, the set C = {e ∈ R d : e = k β ∥β∥ for k ∈ [-10, 10]}. We select this direction because, at a high level, the best deviation for the environment can be shown for many model classes to be in the direction of β. As for the magnitude boundaries, the equilibrium points we found lie in the interior of the set, and hence, there was nothing special about the boundaries selected for this example.Case 1: Small model For this model, we do not rely explicitly on the definition of C. We find that the Stackelberg equilibrium action for the environment over R d already lies in C. As such, this calculation does not make use of the structure of C.To begin, we compute the the optimal θ for a given e when ϕ θ (x) = θ T (x + e):∇ θ f l (e, θ) = ∇ θ E[(y -ϕ θ (x)) 2 ] = ∇ θ E[(β T x -θ T (x + e)) 2 ] = 2β -2θ -2ee T θSetting this equal to 0, we find that:θ * (e) = I - ee T 1 + ∥e∥ 2 βplugging this into the problem for the strategic agents, we find that: This results in the optimal choice of e for the population of strategic agents being e * = β ∥β∥ , which in turn results in the regression accuracy of the decision-maker being:e * =f l (e * , θ * (e * )) = 1 2 ∥β∥ 2Case 2: Larger model In this case, while we make use of the structure of C, numerical experiments suggest that this point may be an equilibrium point over a far larger set than C. As this was an illustrative example, we did not venture to formally prove that the point we found was a Stackelberg equilibrium point across R d . For the second case, let us first expand the loss for the decision-maker as:EQUATION)EQUATIONEQUATION)EQUATIONEQUATION)EQUATION)d 2 +1 exp(- 1 3 ∥e∥ 2 )eAdditionally we consider E[exp(-∥xEQUATION)EQUATIONEQUATIONEQUATION)EQUATIONEQUATION)EQUATIONd 2 exp(- 1 3 ∥e∥ 2 )ePutting everything together, we get the following:EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONd 2 +1 exp(- 1 3 ∥e∥ 2 )(θ T 1 e + 2β T e))We then go on to evaluate θ 2 2 E[exp(-2∥x + e∥ 2 )] using the same calculation method as above, and find that θ2 2 E[exp(-2∥x + e∥ 2 )] = θ 2 2 (( 1 5 ) d 2 exp(-2 5 ∥e∥ 2 ))Putting everything together we find that the loss of the model is:EQUATIONEQUATION)d 2 exp(- 2 5 ∥e∥ 2 )).We take the derivative with respect to θ 1 and we find that the loss' derivative is:EQUATIONd 2 +1 exp(- 1 3 ∥e∥ 2 )eSolving for θ 1 after equating the derivative to zero, we find that θ 1 isEQUATION)d 2 +1 exp(- 1 3 ∥e∥ 2 )e)Similarly, we take the derivative with respect to θ 2 and we find it to be:EQUATION)EQUATION2 ) m 2 y and realize that:(I + zee T )θ 1 = (I - ee T 1 + ∥e∥ 2 )β + ( 1 1 + ∥e∥ 2 ) 2em 2 β T e y (I + zee T )θ 1 = (I - ee T 1 + ∥e∥ 2 )β + 2 m 2 y ee T 1 + ∥e∥ 2 β (I + zee T )θ 1 = β - ee T 1 + ∥e∥ 2 β + 2 m 2 y ee T 1 + ∥e∥ 2 βWe make use of the substitution e = k β ∥β∥EQUATION)d 2 +1 exp(- 1 3 ∥e∥ 2 ) = θ T 1 e + θ 2 3m = cβ T e + 3mp∥β∥ = ck∥β∥ + 3mp∥β∥ = ∥β∥(ck + 3mp)We then now re-evaluate the loss of the model player in terms of the simplified expressions we have found.EQUATION)EQUATION)d 2 exp(- 2 5 ∥e∥ 2 )) = β T β -2β T θ 1 + θ T 1 θ 1 + θ T 1 ee T θ 1 + 2θ 2 (m(θ T 1 e + 2k∥β∥)) + θ 2 2 y = ∥β∥ 2 -2cβ T β + c 2 β T β + c 2 β T ee T β + 2p∥β∥(m(cβ T e + 2k∥β∥)) + p 2 ∥β∥ 2 y = ∥β∥ 2 -2c∥β∥ 2 + c 2 ∥β∥ 2 + c 2 k 2 ∥β∥ 2 + 2pmck∥β∥ 2 + 4pmk∥β∥ 2 + p 2 y∥β∥ 2 = (1 -2c + c 2 + c 2 k 2 + 2pmck + 4pmk + p 2 y)∥β∥ 2We assume that d = 2 and we consider the loss for the model player with varying values of k. Optimizing over this, we see that in the small model setting, the agent is incentivized to use the value of k = 1, which corresponds to β ∥β∥ . This then gives the model a loss of 1 2 ∥β∥ 2 . However, in the larger model case, the agent is incentivized to give a value of k of ≈ 3.4. This results in a higher model loss of ≈ 0.78∥β∥ 2 . Figure 2 shows the learner plots.Our procedure for constructing the Markov follows from a couple of foundational principles. Given that we are in a two-player game with players A and B, we make payoff matrices that make one action for player A the dominant strategy across all states (e.g., our example in 3. We choose the action 0). It is important to note that though a particular strategy is dominant across states, it does not mean that player A will have the same payoff across all these states. We then make all the transitions entirely independent of this player A's actions. With this, we then design the payoff matrices for player B to be such that depending on how much weight the player A puts on action 0 (p), they are incentivized to move to another state.To do this concretely, we first instantiate a number of states and corresponding thresholds for which the player B would be incentivized to transition from one state to the next. We then use Nash Q learning [50] to find what values of player B's payoff matrix would result in behavior that is such that the Nash policy for player B below some threshold has them preferring, for example, moving to the next state but above this threshold they would prefer staying in the current state.• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Our definition makes the assumption of strict improvement only on the learner's loss as that is what is important for future theorems.We switch from losses to utilities to emphasize the fact that players would like to maximize their reward. 


Decision: The results in this paper are not as strong as one might like. However, it is a solid piece of work.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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: questions: See weaknesses section.
limitations: limitations: The authors have addressed any potential negative impacts.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Yes, the authors describe the limitations of this approach and potential directions for future work.
paper_summary: paper_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.
strength_weakness: strength_weakness: Overall, I found the results interesting.
questions: questions: Assumption 4.1, what is F?

Thm 3.4. define \delta^* and e^*.

Line 149: define \Omega and \calE.
limitations: limitations: same as above.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: No concerns.

Comments: title: Acknowledgement
Response
comment: Thank you for your question:

As a general comment on the examples we selected, these examples were selected to highlight the breadth of scenarios where the Braess-paradox-like phenomenon exhibits itself. The hope was to put together cases from different facets of ML to show the pervasiveness of this phenomenon.

Example 2, in particular, was interesting to us both in its connection to previous work done (e.g., performative prediction) as well as in the implications it has for practitioners. For us, the connection that privacy-preserving / fairness-inducing techniques could be argued for from a utility maximization lens for the learner was an interesting takeaway that we thought ought to be highlighted and added nuance to the development of robust real-world machine learning tools. We will make sure to highlight this connection and emphasize the salience of this example better in a future version. 

As a side note, we also see in Example 3 (in the appendix due to space considerations) that this phenomenon not only shows up when the learner uses new, different sets of features but also when they consider more complex models that make use of the same features but with more complex functions to process the information (e.g., Neural Networks with more parameters).
Thank you for the response. I will maintain my original score, leaning towards acceptance.
Thanks for your response. 

I have one more comment regarding the technical details, I find Example 2 for showing these Braess-paradox type of results simple and not surprising. Please correct me if I am wrong here. But it just says that if there are some features that the agents don't want to be used in the prediction model, they will add noise to those features, and then the prediction model is better off not using those features. Am I missing something here?
Thanks for the clarifications---and I agree that non-monotonicity is non-obvious from the perspective of commitment. I maintain my positive review.
Thank you for your consideration and adjustment.
Thank you for your response, which is quite helpful.  To be honest, I still have some concerns, but I also realize these concerns are mostly subjective.  Given that I will increase my score to 5, leaning towards acceptance.