Understanding Model Selection for Learning in Strategic Environments
Authors: Tinashe Handina
Eric Mazumdar
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine Learning
Game Theory
Nash Equilibrium
Stackelberg games
Model Selection
Primary area: learning_theory

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.

Understanding Model Selection for Learning in Strategic Environments
Tinashe Handina
Eric Mazumdar
Computing + Mathematical Sciences
Computing Mathematical Sciences California Institute of Technology
California Institute of Technology
Pasadena, CA 91125 thandina@caltech.. edu
Pasadena, CA 91125 mazudarr@caltechh edu
Abstract
The deployment of ever-larger machine learning models reflects growing consen- sus 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 envi- ronments. this work, we consider the natural question of how the interplay models and strategic interactions affects the relationship between performance 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 Braess' paradox-like phenomenon in which optimizing over less expressive model classes allows one achieve strictly better equilibrium outcomes. Motivated by these examples, we then propose new paradigm for model selection in games wherein an agent seeks choose amongst different model classes use as their action set in a game.
Introduction
Machine learning-and deep learning in particular- has already demonstrated enormous potential enable new services across wide spectrum of everyday life. Examples range from chatbots M 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 Despite signs of diminishing returns, this consensus has broadly held true. Machine learning algorithms tend to follow monotonic scaling law: with more compute and data, one can train more expressive models and eke out performance gains.
4 6
As algorithms are deployed into real-world scenarios, however, they will inevitably come into contact with some form of strategic decision-making making--hether 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 bearning-powerd platforms 8 or more broadly individuals whose goals
are misaligned with those of the algorithm
Reflecting this reality, recent years have of strategic decision-making on learning algorithms. Two sub-fields in particular include strategic classification [10] in which one seeks learn classifier predictor in the presence of agents
surge in research seeking understand the effects
"Conresoondence Tinashe Handina
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

who strategically manipulate data and multi-agen reinforcement learning [1] in which agents attempt learn optimal decision- makiing 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, 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) [ and seemingly innocuous design decisions like stepsize choices and gradient estimators have been shown to give rise to qualitatively different outcomes in strategic classifica- tion [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 non-trivial relationship between model class expressivity and equilibrium performance. In particular, we show now-even in highly structured regimes in which one has full access to the underlying data distribution- paradox-like phenomenon: the larger and more expressive the model class a learner optimizes over, the lower their performance at equilibrium.
interactions result in Braess'
To understand why this is possible, we make links with the literature 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 unilateral restriction of one's 's action set over which one could have played and had 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 strategic environment- the choice of model class should be treated as a strategic action. Following up on this observation, we formulate a problem of molel-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 proof-of-concept, we provide an algorithm to identify the best set in a class of structured games.
1.1 Related work
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 sufficiently expressive class of models to optimize over a given dataset [13]. non-monotynicity of scaling laws emerged classically due to overfitting [14]-in 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 [5].
Deep learning upended this way of thinking with the development of a theory for generalization beyond what is called the threshold of interpolation 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 [7]. 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 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 growing body of literature on the difficulties of learning in game theoretic environments.
Learning in strategic environments: Recent years have seen 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 [T8] adversarial machine learning 77. and multi-agent reinforcement learning [I]] 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 [1]], strategic regression (20), and participation dynamies [21 [2] all analyze
games in which a learner deploys learning algorithms in hame-theeretie environments. Similarly, work on MARL naturally builds upon the foundation of Markov games
23 24
which has seen a resurgence in the machine learning literature in recent years due these connections [2]] 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
One can view all of these problems as an instance of learning in games 25
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- gradient-based learning [29], small design choices like stepsizes and gradient estimators leading different equilibria [2] 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 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 [2). The paper considers 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 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 orthogonal track, which is to ask whether 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 335 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, 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, 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.
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 Q.
Definition 2.1. A set of model classes = N ordered if for all θ 9, AA, if < <jit
implies that θ C O
3

---

The set & may be set of nested policy classes in MARL or 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 model class 6, E A over which to optimize. In some instances, we refer to model classes as action spaces, and we use these two terms inlerchangeably. The selection of 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 fi S2 x & - R which they seek to minimize that also depends on the action of the environment. Similarly, the environment will have a loss function fc f2 x & - R. Here ft is the learner's 's action space whilst is the environment' 's action space.
To model different strategic interactions, we make different assumptions 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 single action, Stackelberg Environments where the Learner leads, Stackelberg Environments where the learner follows, and General Nash Environments. We provide concrete description of each of these environments in Appendix A.I
In the next section, we analyze General Nash environments and show that payoff's do not necessarily monotonically increase in expressivity. In Appendix [A.2] we provide 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 leamner follows.
3 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 way for a player to restrict their model class, resulting in game with a Nash equilibrium that has 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
relaxed, this phenomenon still exhibits itself.
To prove our main result, we assume the two-player game strongly monotone on the space Q x & c R". Definition 3.1. A two-player game is y-strongly monotone if the generalized gradient operator F: x & + R" given by:
e) where: = e), ee)
F(x)
satisfies:
(F(x) - F(x'), x²) 2 uli x' 112 Va, x' E 3XE
strongly monotone game is a convex game 28 Implicitly, it assumes that the two players' losses are yu strongly convex in their own action and makes further assumption on the interaction between players' actions (27] The assumption of strong monotonicity ensures that there 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 seauvorr-thougee 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 well assumption that their interaction is not trivially zero at Nash.
Assumption 3.2. Assume the game defined on fe and fi is strongly monotone on Q x E. Further assume that

---

0
53
0=0.85
Nash
20
%
S
Sn
3.9
b
increasing 14
60
0.6
expressive
(a.) A visual description of 2-player Markov game in which the learner can unilaterally increase their payoff by restricting the expressivity of their policy class. (b.) the payoff of the learner at Nash in 50-state version of this Markov game as their policy class is restricted to take the form (i(s) = [p, - p] in all states s for p E [] - p. p. for different discount factors (assumed to be the same for both players). In all cases, we see the learners' payoff broadly increase Nash they optimize over smaller policy classes.
Figure 1:
1. ft and fe are jointly convex in and e.
2. The gradient mappings, Vi and Ve exist and well defined for all (0, (). Furthermore, the gradient mappings are T--Lipschitz continuous the joint action space.
3. The Nash equilibrium E on the interior of O with V VoBR. + 0.
To show how the restriction of model class yields 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 (0, e) E x E Pareto-optimal, if there does not exist (0, é) such that f1(0, é) < fi(0,e) e) and fe (0, s fe
Given these assumptions, we prove the following theorem. For of exposition, we defer the proof to Appendix B.I
Theorem 3.4. For two-player monotone game G on θ x & which satisfies Assumption 3.2 if the unique Nash equilibrium in θ x E, (8", e²) is not Pareto optimal then there exists a restriction of the learner's model class (i.e., a set O' Q) such that the restricted game G' O' E &admits Nash equilibrium (0',e)) e') with: fi e') < fi(0".e") ee).
This theorem highlights the fact that the momeooononiccty of scaling laws is, in fact, something 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, remark that it does not say anything about the with which one find this restricted space. While the proof is constructive, 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-monee con-monotonicity can play out complex ways.
Example 1: Multi-Agent Reinforcement Learning We first demonstrate extreme form of the reverse scaling predicted by Theorem 3.4 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 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 two-player game with states. In each state 8;, with i 21,2.... n). both players have two actions available to them {0, 1} with 0 corresponding to the top
'Our definition makes the assumption of strict improvement only on the learner's 's loss that is what is important for future theorems.
5

---

row or left column. In each state, the environment is allowed to choose policy that is unrestricted, meaning that ne = pp. 1--p pl for any p [0. 1]. The learner can choose from policies such that: (s(s)) fp. 1 - p] for all p E [1 P: pi] for some E [0.5, 1.. Varying p generates model classes of varying expressivity. For example, when p = 1, then they are allowed choose any policy, and for p 0.5, they are constrained to only playing uniform policies.
Given actions a, 6 from the learner and environment, respectively we define the transition probabilities
as:
p(0 8i, a = 0, 1) - p(5 51, = 1, 1) p( 82, a 0, 0) - p( si, = 1, 0)
Thus, 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 reward
Us (T ne) = Emgi. Σ rt Re as, be)
where E {e, and Ye: " the player's 's discount factors. We construct the payoffs for the learner such that they have dominant strategy of (s) = pp. 1 al-pp in all states, and their expected cumulative payoff increases the players end up further along the chain of states (as seen in Figure IT.
We construct the payoffs of the environment player such that they trigger a switch to the next state and only if the probability that the learner puts action 0 is below some threshold p (s().. We do so for a sequence of thresholds p for 1.... n such that p. > P > 0.5. With this construction, for Pi+1 the construction of the payoff matrices are left to Appendix E and a plot of the equilibrium rewards
< P < P the game will result in the players staying in state s; for all time. More details on
for the learner function of p is shown in Figure 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-m con-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 y = 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 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., can sometimes have a higher payoff than the unrestricted Nash equilibrium.
Example 2: Participation dynamics Our second example is similar problems considered in the literature on performative prediction 18] though the setup we consider also fits the literature on understanding participation dynamies [32 and algorithmic collective action [
In this model, there is a base distribution Po over the input-output space X' 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 X' + V. The environment, on the other hand, takes the form of population of agents that selects a distribution on P on the input-output space (i.e., P E (XX))) to maximize their own utility which depends on the choice of the learner.
The least restrictive class of models the learner has access Q is the set of all functions g: X' <>>> V. We also consider a restricted function class which is the class of all functions 9r : X" - 3 where X' X' is the result of some feature mapping X X". Thus, θ is the space of all functions of the form gr (.)))) Clearly θ C Ω
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 Po with a manipulated data distribution Pe such that the distribution seen by the learner is given by P = aP. (1 a)Po for some a E 0, 1]. The parameter a relates to the strength of the response distribution within the
We switch from losses utilities to emphasize the fact that players would like maximize their reward.

---

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 9 or Ør is the Bayes-Optimal classifier on X' and X' respectively are: 9 (a:) arg max Pvy(=) & (x) arg max P(y]ó(x)).
Thus, the learner's loss at equilibrium is given by:
fi'g": P) (z) f( P) = Pr(g (z) + 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 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 set of features o' X + X' that are more informative than some o" X + x X C 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:
(P),,.)) Pr(g(z) # g(0 (z))) > 0 (P, Po) otherwise.
fg P)
where U is the uniform distribution on X' x y and TV represents the TV distance between distribu- tions.
As we will show, for sufficiently large a, the learner 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 [V| Assume that the Bayes optimal classifier X' for Po denoted gf = arg maxzey (()) satisfies:
Po) Pt) = y)
This leads the following result for this game.
Proposition 3.6. Under Assumption 3.5 consider two functions classes over which the learner can optimize, Qt and θ which the set of all functions from 9r : Xx" - where X' o" (X) such that
o" dz(x) for x E X Consider the corresponding games denoted G and G respectively. Then the Nash equilibrium in G is (g" P*) where P (1 a)P + aU and the Nash equilibrium in G is given by (g,, Po). Furthermore, there exists range of E (0, 1) such that:
, PT) fi
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.
4 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, formulate problem of learning in games in which the learner seeks to find the best model class across a set candidate model classes as well as the best strategy. We frame this a problem of model selection for games.
We remark that model-selection an area of recent interest online learning the best of our knowledge- the paradigm has not been applied to games yet. Most similar to
though to
7

---

Algorithm Stochastic gradient descent to find Nash equilibrium in a strongly monotone game
1: procedure PSGD(O, Fu, T)
2: for t e to T do
3: 1)t p(t-1)
4: Tx+1 llexe (xt 1/t (x+))
5: end for
6: fT return Σ T(T+1)/2
7:
end procedure
this problem is line of work on meta-learning in games, which seeks to find good strategies that generalize across environments [4].
We describe an algorithm for how the learner can select model classes to identify which model class we assume that all players use stochastic gradient descent and adopt
to use. As a proof-of-coneee the structure a problem we analyzed in the Nash environment regime. In particular, we assume the learner has access sets of subsets of J Rd and that their loss and the environment's loss satisfy following generalization of Assumption 3.2 For simplicity, we let the tuple of a particular model and the environment action be denoted by (i.c., (8,c) = r.). We note here that F is the generalized gradient mapping as described in Definition 3.1
Assumption 4.1. Assume the game defined L-Lipschitz continuous on Ω x Further, assume that the players have access to stochastic gradient estimators such that the estimated monotone mapping F satisfies, Vo E Ω E:
and fi is strongly monotone and that they
B[F(=)] F(x) and [[]] F())
Given this assumption and under the simplifying assumption that all players decreasing stepsizes, we assume that for given model class G the players engage in projected stochastic gradient descent of the form:
T++1 To,xe xE (32 17e ((re))
where denotes the Euclidean projection onto O; x E. The pseudocode for this is described in Algorithm| We show that the rumning average of the iterates resulting from running this algorithm in an environment satisfying Assumption [41 concentrates quickly around the payoff at the Nash equilibrium. The proof of this proposition
be found in Appendix C
Proposition 4.2. Let θ correspond to a particular model class which results in an instance of contin- uous action μ ststrongly monotone game with a unique Nash Equilibrium x². Under Assumption 4.1 and the assumption that all players use stepsize schedule ne = p(t+1} for any 8 (0, 1) Algorithm yields estimate îo such that:
2
L2 log( 13
f(=)))
2.2T
with probability at least 1 1- 8.
To derive this bound, generalize existing result from convex optimization 45
Given these confidence bounds, we now propose a successive climination algorithm for identifying the best model class in 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 The specific form of successive elimination is described in Algorithm
stochastic mirror descent 46
As 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. identification and defer the proof to Appendix C
We show the results with respect to
Proposition 4.3. Under the assumptions of Proposition 4.2 let A= 1 With probability at least 1 - 8, Algorithm identifies the model class whose Nash equilibrium yields the highest payoff after:
n 1 log ( ))++ 133)
112 A
8

---

Algorithm 2 Successive Elimination for Best Design action Identification
procedure SICCISINVELLMIATTOO(())...
2:
S - [0:
3:
T=1
4:
while |S| > do
5:
a
6:
8' < 2n
7:
for all θ 5
8:
Z.p <- Algorithm 1 with (0,, 7)
9:
end for S 5 S 10 E S: 30; such that:
10:
fx +
L log( + ( ++*
s(x+)
L log ( +
1
11:
12: end while
13: return
14: end procedure
interactions with the environment, where A is the minimum suboptimality gap of the Nash equilib- rium of function class compared 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 is possible to be no regret, not just within a model class, but across a set model classes well.
5
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 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 efficiently learn the best model class to optimize over without sacrificing performance in terms of regret.
Altogether, results 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.

---

References
[1] Eleni Adamopoulou and Lefteris Moussiades. Chatbots: History, technology, and applications.
Machine Learning with Applications, 2020.
[2] Dana Pessach, Gonen Singer, Dan Avrahami, Hila Chalutz Ben-Gal, Erez Shmueli, and Irad Ben-Gal Employees recruitment: prescriptive analyties approach via machine learning and mathematical programming. Decision Support Systems, 134: 13290, 2020.
[3] Robert Gorwa, Reuben Binns, and Christian Katzenbach. Algorithmic content moderation: Technical and political challenges in the automation of platform governance. Big Data & Society, 7(1), 2020.
[4] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020.
[5] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws, 2021.
[6] Utkarsh Sharma and Jared Kaplan. Scaling Laws from the Data Manifold Dimension. Journal of Machine Learning Research, 23(9):1-34, 2022.
[7] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR, 2018.
[8] Jamie Woodcock and Mark Graham. The gig economy: critical introduction. 2020.
[9] Moritz Hardt, Eric Mazumdar, Celestine Mendler- Dünner, and Tijana Zrnie. Algorithmic collective action machine learning. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[10] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifi- cation. In Innovations in Theoretical Computer Science, page 111-122, 2016.
[11] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-Agent Reinforcement Learning: A Se- lective Overview of Theories and Algorithms, pages 321-384. Springer International Publishing. Cham, 2021.
[12] Tijana Zmnc, Eric Mazumdar, Shankar Sastry, and Michael Jordan. Who leads and who follows in strategic classification? In Advances in Neural Information Processing Systems, 2021.
[13] Vladimir N. Vapnik. The nature of statistical learning theory. Springer- Springer-Verlag New York, Inc., 1995.
[14] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. In Computational Learning Theory, pages 224 240. Springer Berlin Heidelberg, 2001.
[15] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-280, 1971.
[16] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt, December 2019, arXiv:1912.02292 [cs, stat].
[17] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training Compute-Optimal Large Language Models, March 2022.
10

---

[18] Juan Perdomo. Tijana Zmic, Celestine Mendler-Diing and Moritz Hardt. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning, pages 7599-7609, 2020.
[19] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, 2018.
[20] Omer Ben-Porat and Moshe Tennenholtz. Best Response Regression. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[21] Sarah Dean, Mihaela Curmei, Lillian J. Ratliff, Jamie Morgenstern, and Maryam Fazel. Emer- gent segmentation from participation dynamics and multi-learner retraining. 2023.
[22] Lauren E Conger, Franca Hoffman, Eric Mazumdar, and Lillian J Ratliff. Strategic distribution shift of interacting agents via coupled gradient flows. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[23] Lloyd Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):1095-1100 1953.
[24] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[25] D. Fudenberg and D. K. Levine. The theory of learning in games. MIT Press, Cambridge, MA., 1998.
[26] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 173(1):465-507, 2019.
[27] Eric Mazumdar, Lillian J. Ratliff, and S. Shankar Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science 2(1):103-131, 2020.
[28] B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica, 1965.
[29] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in Adversarial Regularized Learning, pages 2703-2717. 2018.
[30] Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani, Gaming helps! learning from strategic interactions natural dynamics. In Proceedings of The 24th International Conference on Artificial Intelligence and Statisties, pages 1234-1242. 2021.
[31] Oren Neumann and Claudius Gros. Scaling laws for multi-agent reinforcement learning model. In The Eleventh International Conference on Learning Representations, 2023.
[32] Meena Jagadeesan, Michael Jordan, Jacob Steinhardt, and Nika Haghtalab. Improved bayes risk can yield reduced social welfare under competition. In Thirty-seventl Conference on Neural Information Processing Systems, 2023.
[33] D. Braess. Über ein Paradoxon der Verkehrsplanung. Untermehmmensforscchnng Operations Research Recherche Opérationnelle, 12(1):258-22 268, December 1968.
[34] Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Informational Braess' Paradox: The Effect of Information on Traffic Congestion. Operations Research. 66(4):893-91 917, August 2018.
[35] Tamer Basar and Yu-Chi Ho. Informational properties of the nash solutions of two stochastic nonzero-sum games. Journal of Economic Theory, 7(4):370-33 387, 1974.
[36] T. Basar and G. J. Olsder. Dynamic noncooperative game theory: second edition. SIAM, 1999.
[37] Donald M. Topkis. Supermodularity and Complementarity, Princeton University Press, 1998.

---

[38] Susan Athey. Monotone Comparative Staties under Uncertainty. The Quarterly Journal of Economics, 117(1):187-223, 2002. Publisher: Oxford University Press.
[39] Pradeep Dubey, Inefficiency of nash equilibria. Mathematics of Operations Research, 11(1):1-8. 1986.
[40] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation emror in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning, pages 1587-1596, 2018.
[41] Jacob K. Goeree, Charles. Holt, and Thomas Palfrey. Quantal Response Equilibrium: Stochastic Theory of Games. Princeton University Press, 2016.
[42] Aldo Pacchiano, My Phan, Yasin Abbasi- Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaha Szepesvári. Model selection contextual stochastic bandit problems. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[43] Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. 2019.
[44] Keegan Harris, loannis Anagnostides, Gabriele Farina, Mikhail Khodak, Zhiwei Steven Wu, and Tuomas Sandholm. Meta-learning in games. 2023.
[45] Nicholas J. A. Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high- probability bounds for strongly-convex stochastic gradient descent, September 2019.
[46] Tor Lattimore and Csaba Szepesvari. Bandit algorithms. 2017.
[47] M. Jagielski, A. Oprea, B. Biggio, C. Liu, C. Nita-Rotaru, and B. Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. 2018 IEEE Symposium Security and Privacy (SP). IEEE Computer Society, 2018.
[48] Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, 1991.
[49] Kevin Jamieson, William Agnew, and Tomer Kaftan. Lecture 4: Stochastic Multi-Armed Bandits, Pure Exploration.
[50] Junling Hu and Michael P. Wellman. Nash q-learning for general-sun sum stochastic games. J. Mach. Learn, Res., 4(null):1339-100 dec 2003.
12

---

A Learner-Environment Interactions
A.1 Description learner environment settings
We begin by providing a concrete description of each of the learner-environee eevirromment settings we explore:
Stationary Environments: The environment has only one action (i.e., = {e)) and the problem reduces to that of classical ML. The resulting equilibrium is simply the minimum the learner's loss given and the model class θ,
0- arg min fi(0, e). A
2. Stackelberg Environments Learner Leads:
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 [TO]. The equilibrium is a joint strategy (0", e*) such that:
0 arg min fi(0, (O), 0E
and (R. = arg min, fe fa( e).
3. Stackelberg Environments Learner Follows: 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 [ against the learner. Here the equilibrium is joint strategy (0", .E*) such that:
e" arg min (BR.
AEE
and 8" (R) arg mingge c0()
4. General Nash Environments: Which allows us model the general case when the interaction results in a Nash equilibrium. This is, for example, the desired solution in MARL || and participation and regression games [2]. In this setting, the equilibrium outcome is joint strategy (0, e) such that:
fe(0, e¹) 2 fe(0,e) e) VE'E,, fi(O', e) 2 f((0,e) 4 e e
We remark that in this last case, the assumption of a two-player game made for simplicity, and our results would go through in n-player games.
A.2 Stationary environments and Stackelberg games with the learner leading
We investigate the two cases in which performance monotonically increases as a function of complex- ity: 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 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, O; Oj E A i j. If (0s, ei) and (0,,e,) ) are equilibrium outcomes in stationary environments or Stackelberg environments in which the learner leads with the instantiated model classes being O and θ respectively, then f((,,, e,) 2 fi
Proof. For stationary game, the proposition above follows naturally. We know that Ej which we denote e* Since 0 E O S Oj. the equilibrium (0,, e*) necessarily must be such that ci()).c") < e),, otherwise (l,, e²) ) is not an equilibrium point.
For a Stackelberg game where learner leads, the proposition follows the same argument. According to Stackelberg dynamics, we know that B BR(O,) the case that (0,) & [i(O,, es) otherwise simply selecting 0, when optimizing θ would be profitable deviation.
and B B((0)) ej. We can see that it must be
13

---

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 77. In these games, if the Nash equilibrium exists, it coincides with the Stackelberg equilibria via simple min-max theorems
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 which the learner leads.
A.3 Stackelberg games where the learner follows
We also consider the case in which the environment results in 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-aa as happens in settings such as collective action and non-adversarial backdoor attacks in machine learning- the use of more features can actually hurt.
f(BRRC))
moddl
Stackebbrrg acullruum Stockitting COuIIVIU
Magnilude environmnnt's action
Figure 2: The loss for the learner at their best response in regression game as the magnitude of the environment's perturbation vector varies with the payoffss achieved at equilibrium as derived in Proposition A.2
Example 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 (x 0f x or (x) 0T x + 02 exp(-[[==|] as the function use for the regression task. The classifier's goal to learn 0 so as to minimize the expected squared error. In this framework, the environment can add deviation e to the dataset. This would mean that the input to the regressor model would be x + e.
Consider the model classes @ (ar) O (a) derived from (2), (x() respectively. We show that despite θ (x) C Oz)(z)) at a Stackelberg equilibrium, the learner has higher payoff when they learn from θ (z)) as opposed to ④ dg((2) 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 O. More coneretely:
Proposition A.2. Consider dataset where each data point Rd is drawn from distribution D. A learner has the option to select one of two model classes:
θ ()(=)) [z)(x) 0 IR where: ob(x) = 0"'x}
(z(()) (0](x)) 01, 02 E RRdd TR.
where: dz(x) 0f x + 02 exp exp(-1|x112)
Assume that each data point can perturbed by an error vector C Rdd, resulting in the learner observing x + instead of x. For some compact convex C, distribution D and dimension d, the Stackelberg equilibrium attained by optimizing over θ Ozt(z) results in a strictly lower loss than that attained by optimizing over (x))
The calculations for this proposition are the Appendix D Figure 2 highlights the non-monotonicity
of performance between different equilibria in the two spaces. We see that at the Stackelberg
14

---

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 point-wise sense.
B Additional proof'
B.1 Proof of Theorem 3,4
We begin by revisiting the main assumptions of this proof:
Assumption B.1 (Restatement of Assumption 3.2). Assume the game defined on fe and fi is strongly monotone Ω E. Further assume that
1. ft and fe are jointly convex in and c.
2. The gradient mappings. V fi and fe exist and are well defined for all (0, e). Furthermore, the gradient mappings are L--Lipschitz continuous in the joint action space.
3. The Nash equilibrium H" E θ is on the interior of @ with Vo +
Theorem B.2 (Restatement of Theorem 3.4). For a two-player monotone game G on θ x E which satisfies Assumption 3.2 if the unique Nash equilibrium in θ x & is not Pareto optimal then there exists a restriction of the learner's 's model class (i.e., a set @' C )) such that the restricted game G' on O' x & admits a Nash equilibrium (6', .e") with: fi ee) < fi(6",e")
Proof of Theorem 3.4
Note the following: because we can achieve strictly lower loss for the jointly convex loss function ft. we know that V fi(0", e²) #
Consider the following the function (0) fi (R)())). Here (R) is the best response of the other player to the action 0, i.e., ( == arg minces fe(0,e) e).
Relying on this function definition, we describe a particular restriction on the model class O and then find a Nash equilibrium for this model class, which is different from (0", ee") and whose loss for the O e-player is lower in this new equilibrium.
Vafi(0", (0') Vo lar, we note that V Ve.R,((*) V fi (f*)) * 0 since if it were, it would mean that either VaBR, (8*) ) or Ve BR, were equal to zero which is not the case. V (e BR, (0*)) = 0, would mean that both Vefi(0', (R)) and fe BR. (0*)) = 0 implying a global mini- mum which would contradict the existence of a Pareto improving point. R. # 0 follows from the Assumption 3.2
Realize that V fi(00)
(O)) + O. In partieu-
Noting the fact that fi(")) + 0 allows us pick direction with respect to the inner product with (8*)), ), let v be any vector Re such that (v, (f()))) >> O. Consider 0' = 6 de for some > O. Let e' = (O').. We will now define O' c θ such that the game on the model class O' E Nash equilibrium
has (0', ,e')
(VoJi(0', BR. 0'- 0) S 0}. Notice how the first step removes (0*, ee") from the construction. The second step makes such that BRa(e')= = 0' for all 0 E O'. Since e' is the best response to 0' we get that the point (0', e') a Nash equilibrium.
Let Ô = {0 0 (0-0', v) S 03. We then go on to define O'
What is left to show is that we can create such restriction with the characteristic that the O-player's loss function is lowered at the new equilibrium. To do this, we rely on the choice of the 8 parameter.
Claim B.3. There exists value of d > 0 such that fi ,e) < fi(O",
To see this, consider the Taylor expansion of Je((') at 0
fi(0') f:(0)) + (Vi100)) -0) + (0' 0T) ( Ho 0*)
L
S f((00) + (,"))) 0*) + 2
10 0-1
= -((00) - ((V +
2 |0|
15

---

In the first line d E (Vii(0)), e) > O. Furthermore, we realize that the term d(Vii v) E ( and that 8² |ull 2 (6))). This means we can select value of 6 such that the term (VV - d | With this,
E [0, 1]}. We note that by our construction
l is positive.
then deduce that fi(0)) fi((") which then completes the proof.
B.2 Other proofs in Section
We begin with proving the proposition on Strategic classification, Here we restate the assumptions again:
Assumption B.4 (Restatement of Assumption 3.5 1. Let | n. Assume that the Bayes optimal
classifier on X for Pu denoted 9² (a) arg maxyey P(y x (x)) satisfies:
fi Po) = (x) =)
Proposition B.5 (Restatement of Proposition 3.6 Under Assumption 3.5 consider two functions classes over which the learner can optimize, Ω2 and θ which is the set of all functions from g- :X - Y where X* = 6² (X) such that of (x)) x for E X². Consider the corresponding games denoted G and G respectively. Then the Nash equilibrium G is (g", Pp) where P (1 xx) and the Nash equilibrium in G is given by (gr, Po). Furthermore, there exists range of (0, 1) such that:
P Pu + al
fi P*) f(
Proof of Proposition 3.6 To prove the first part of this proposition, we note that (g", PP) is a Nash equilibrium in that player has any incentive to unilaterally deviate given their action sets. Indeed, g" is the Bayes-optima classifier on P in S2 then Pr(g(z) * g( (x)) > O and consequently the environment's best-response perturbation is P. U. Similarly, 9r, Po is the Bayes-optimal classifier on X and satisfies Pr(g(z) = g (x)) = 0 by definition. As such, the environment's best response is given by Pe Po.
To prove the second part of the proof we note that:
a a n
, 2 (1 - ar) min [e( Po)
gei
n
Now, note that for 2 2 nfi Po). we have that:
Si(g" pT) Si Po)
C Further results on Online Learning for Model Selection in Games
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 fa and fi is strongly monotone on Z E. Further, assume that
1. The functions fi and fe are L-Lipschitz continuous on Ω x
2. The players have access to stochastic gradient estimators such that the estimated monotone mapping F satisfies, Vo E Ω x
[[F())) F(x) and ([] =
Proposition C.2 (Restatement of Proposition 4.2p. Let θ correspond to a particular model class which results in an instance of continuous action μ strotoogly monotone game with a unique Nash Equilibrium (x*) Under Assumption 4.1 and the assumption that all players use stepsize schedule "tt n(4IT for any E (0, 1) Algorihhm yields an estimate ior such that:
[M(()) fi(x=) 5 (
[12 log( (3) + L3 12T
with probability at least 1 1-6 8.
16

---

Proof of Proposition 4.2
Let 22 = (z1,...,,En) for fixed number of players. We then define
Viuj (xt)
2u (T4)
F(x1)
Let F(x)) F(xx) - E(x)), where [[E(2;)] = 0 and [() ll S 1 a.s..
V (x
From the description of Algorithm 2, we can see that 21+1 = llaxe (r, F (xx)) The proof of this
proposition closely mirrors [55]
Let T be the output of Algorithm We can see that:
|10411 - x=1 = Ilexe (+t - T1: (xx)) - x²1²
S 1 M1 F((1) - x²1
= 11 =¹11 - 2n/ (F(x)), x2) + nř (x:))
|| x²112 - -n (F( - 2np ( (F (xre), - x²) 2m (F(x)) 2t -x))+ +n?1 (xx))
| x² + 21x (F(x)) F(x)), x²) 2n. 2F. + +1)+)((((=))
Rearranging terms we get:
(F(rs)) - x²) S 1| - x=1 - |,0+11 - xx x²11² + 2m (F(t)) - F(x,), Uz - x²) +
(F(x;),
x1 - -x')= |1,, x²112
|| - 112
+ (É(x)) 24 - x²) + 1t F (xx)12
217
2
1 x x011 112
||,141 -x -x=112
1
2 (F(x:), - xx")
(F(x)), It
- - x¹) + ( (x+) 21 - x²)
| (xx))
217e
2
2
(F(x)), x3)
1x xx*
||0241
xx11
2 || x² 12 + (((x)) xe - x²) + 11
(xx))1
217
((F(x)), x²) < 2t
|,,,
x²1
112
|| - x=11
H
||
x 112 + (B(Iz), 21 21 x²) + 7t
F ((x))1? 1|
2112
2
2
2
t
1
1.
1|08 - ===11²
|| - 101 11 + 1(B())) x²) + t 1)t F (xx:))1
2m
2
2m/
= 2
P
(t(t
1)1|23 - x=122 t(t + 1) 211 + t {(((x)), - -x1)) +
[f(x)))
4
p(t + 1)
(L + 1)2
2 2
(t(t
(1)l=1)]l=+ - x x01 - t(t + 1) x²1 + t (L)()) ,, 22 - -x")
4
We then sum over all t and noting that the right-hand side has portion with a telescoping sum, we that:
T (( 2.
T
(k(m)) 24 + T 7-(++1 1)2
Σ
Σ
t(F(1z), 24 - -x") -
4
Σ (((x)) 24 -x) T F- 1)2
T
T(T 1)/2
T(T +1
1=1
17

---

By monotonicity we get note that: 2 - x²112 11-1= - (F(r)), - -x") and thus:
4
3F - x²) + T +
21 x. x²1 112 S
T(T + 1)/2
T(T +1)
1
t=1
1
4
(B(())) xx0) T -L 1)2
1|127 x0122
T(T + 1)/2
IT +1)
11
T ELLL+ 1)2
St. x" x011²
(B(a)),
T(T + 1)/2
UT + +1
14
Σ xe +
T- (L 1)²
[ - x0112
μT 1)
1
T ((E(z)), Ie x2) x²)+ T (L 1)2
(f(()) - f((x))
4L CT 1)
Σ
Fr
To complete the proof, we rely on high probability bound on Er which makes use of specialized form of the Generalized Freedman's 's Inequality.
T Σ t(((z)) x²), Then for any 8 E (0, we have
Lemma C.3 45 Lemma 4.1). Let Ex
that Er < L Tlog(}))
plugging in the bound on Ey 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 = (.)): With probability at least 1 6, Algorithm 2 identifies the model class whose Nash
equilibrium yields the highest payoff after:
[n[L2log] log(())) + L3)
1.2A*
interactions with the environment, where A is the minimum suboptimality gap of the Nash equilib- rium of 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
[(xt)) where xor +- Algorithm where x the Nash equilibrium point for O, then have that:
X
1 vo, T) and
X
f(x)
1a logl 222 4 X;12
}}) 5
X
Proof. Here we rely on the union bound to note that:
L log 2 T"n + 3
L log(
2
)
1
X X112
5
P
X - -;1
8
2T
2T
T=1
1=
T 1=1
8
1
2n
T2
1=1
< 8
18

---

Lemma C.6. With probability greater than or equal to 1 8, the best model class Or is retained in the active S until the end of Algorithm 2
Proof. Let D be the event Ü {
X - -X1
1oR(2 ( 2
}}
We know that DC occurs
p²
TT=11
with probability at least 1- 1- Let (T, L log(2 r2n )+ 1,27
Obe is dropped if there exists j. such that X5,r - (T, 6) > XR.T + UTT a). We consider the scenario where the event DD occurs. In this scenario we have that X; UT, 6) 2 X,,r and that XR, 2 X - -T, 6) for all T. Plugging these two inequalities into the first expression gives us that X3 2 X which is a contradiction.
Therefore, with probability greater than or equal to 8 have the best model class O remaining in S.
Lemma C.7. Given that the best model class O₃ is identified by Algorithm 2 it will terminate after n(T (oT 1og(3))) ) samples
Proof. Let A; = x; Let = min, A. Let O₂ be the action that corresponds the highest payoff at the Nash equilibrium point.
We note that one of the conditions which leads to action O, being removed from the consideration set S is
XE. - U(T,) 2 X + UTT
Assuming that the event DC holds, for each model class θ we have that, Xx.T > Xx 8t and that Xi, S X + (L,,, 8). Substituting these expressions into what we have by we get that
X X; 2 (T, 8) + (T
A 2 (T,
Now we consider the case where A A to find a bound for T.
2 (T,
4(2² log( 2T ) L2)
HTT
2² SI2 log T
1 log( (g) + 1,3) A
A
4(L² log( 222 + L²
pT N
L log ( + L3
T T2
1
La log ( + 1 n²
From here we proceed to find the which corresponds
O 1.2 logt 2 1+13 2=
steps which simply
o (logt
found by taking the log. We then note that
Σ
2 O
1.2 [og( 1)
Summing
A
over n decision actions we get O n1. log( 8
samples which completes the proof.
A
D Additional calculations for Linear Regression Example
Consider the following setup. The decision-maker would like to solve regression problem and has the choice of two different regression models. For a distribution input data D, and a datapoint æ, they can either compute:
(x)x) 0T (xx
19

---

Or:
which in 00(x) =
exp(- exp(-1lx+e11))
For the rest of the calculation we take the distribution of the input data to be (0 1). Suppose the true relationship between features and outcomes y is linear and is by y 3 x. However, the training data is reported by 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. Equivalenty, this can be seen as the input data being misreported and generated from distribution A (e, (e,
Suppose the population of strategic agents knows that the learner will solve regression problem. Then, they would like to choose e to maximize their expected prediction given. Concretely:
e" = arg max E Bi (x + +e]
Given the fact that 0" arg ming El(y- ( + e) For this example, the set (e E Rd T[lll for E [-10, 10)}. We select this direction because, at high level, the best deviation for environment can be shown for many model classes to be in the direction of B.. As for the magnitude boundaries, the equilibrium points 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 Id already lies in C. As such, this calculation does not make use of the structure of C.
To begin, we compute the the optimal A for given when Φ0(x)) = 00x e)):
Vafi(e,0) vo )
VoB[(B"' x - 0" (x + e))
23 20 2ee To
Setting this equal to 0, we find that:
ee
8 (e)
3
||||
plugging this into the problem for the strategic agents, we find that:
e" arg max E[ (x +e)]
arg max 8 (
e
eTB
arg max
1 ||||
This results in the optimal choice for the population of strategic agents being er T turn results in the regression accuracy of the decision maker being:
1 fi(e", fi(e",00(e")) (e"))) = - 113112
Case 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 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 Rd For the second case, let us first expand the loss for the decision-makee maker as:
fi(e, E[(3" 2- (2 (3) of +0x
el|3)]
We first evaluate 22, F(xppp/x (3 - of (x + e))} Note that E(xpE -1|x +
(BTx) 0f (x + e))] -20 Elexp(-11z Blepplll )x
Elexp( + el 2|(3)a]
20

---

(//e//eeepp[1 |æ + eel
1
1
Elexp(-||zz ||= + e|13xx] =
(
rexp(-1xx+ + e
-
|x:1²)
dr
2x
2
Rd
1
exp(p
x zexp(-
||01| 2x e) dx
2
2n
1
exp(
1
1
[1ee13)
/ Texp(
3
||:0
ell?)
dx
2m
Rd
[
1
exp
(lell1)
1
I. C-N(
_
2
c,
1
1]
dx
3
Rd
3
3
1
1
1
2
1
exp(
[1ll3)
x. C.N((
c,
T)dc
dr
3
3
3
3
1
1
exp(
[lell3)
3
3
3
2(
exp(
3
3
Additionally we consider B[exp(-11: + e((²)e]
Ejexp(-1|xr 1|x + e =e(2)e] =
(
1
1
E ccxp(-11x++0 + (xp())xp())) [|x01(2 2xxp(~21e01p) dx
2
Rd
2
1
1
Texp(-1lee)
eexp(
3
]|(0|1² -2x e) dx
2T
2
Rd
1
1
/
2
8
exp(
-
[|el
eexp(
+
el(
dx
2x
3
Rd
2
3
1
1
3
exp(
3
[1el3)
e.Ni
3 3
e,
l)
de
1
1
2
1
3
exp(
3
1eel1))
e.N(
g 3
1)
dz
Rd
1
5
exp(
3
1ell)))
exp(
3 [1ee13)e
Putting everything together, we get the following:
-20gEfexpp || + +e
0f (x))))
=-20,,3 EE [exp(-1|== + < )z] + 20 E(exp((- || + e||3aa] + 2 || + c||
-0200 20230 ) 1 exp( 1
3 |||| ()) ee + 20 (-21
1 1
exp( exp(-5 _ 20 (1
1 3 exp( eeepp= exp(-z]le(()o)) {eee
3
-4033T( 1 ++ expl - [|e|1) 1200((]]) 1 + exp( 1 [lel1 + 20207 (()) expl - 3 [ee)
(()))))
= 202((5) ++ exp expl 13 +23"e)) e))
We then go on to evaluate (5EEeex((211: + e| using the same calculation method as above, and find that (exp -2| + e| = ( exp( - [l]())))
Putting everything together we find that the loss of the model is:
file, 0) =
To, 0 ee
(
exp( -ell- (oFe3300 +2(()) expl (eel))
We take the derivative with respect to 02 and we find that the loss' derivative is:
2,8 0-++0 20, + 2ec 0, + 292(( 1 1 +1 exp( |ell2)e
21

---

Solving for 01 after equating the derivative to zero, we find that 81 is
ee" - (1 1 |||| (B
) -
exp(
1 ((e)))
Similarly, we take the derivative with respect to 02 and we find it to be:
2(1)) 8 exp( 3pp0-]ee3)000 2,9 e)) + 28o(()] _ exp(= 2
[lel)))
5
setting the derivative to zero and solving for 82 we find that 82 is:
0₂ - -1)) exp( 3 |el|| (0f 2
(1) exp( ||(|3)
From this point on we make the assumption that is the direction of B (i.e., = KTē for some k E R. As such, note that ||e]| = k. For simplification and ease of computation, we make the following notational substitutions:
1 + exp( - 1 k2)
( exp(
kT²) =
Re-writing the expressions of 02 and 0g we get:
ce
1 2 exp(
01 = (I
(B 02((g]
- [el))))
1 + |el|
3
3
e
(T 1 ||e||2
(B - B2me)
mm6T e + 2.
0₂
We go on to simplify the expressions for 0, and 02:
ce
01 = (I
(B 02me)
1 ||ll
eeT
m(fT e +
2,3T 2,TTe)
(I
)
me)
+ |ell
ee
m² 2,3T c)
(1
(
+ |
EET
m² 10fffee + 233
e
01 (I
(I
+ |||| )3
+ ||e|/
y
eet
m 0f
ee
T
2m g
0 - (1
1 |el
E
(1
1 + |elle
)3 + (1
1 +
|e|
0
1
em em2
20T
c
(1
ee
)8 +
2em 2 1T
|el
1 + |ellz
|
2
We let 2 = (111
1
m² and realize that:
14
T
2em2.re
(I + zee )01 = =(I 1+ |
)3 +
1
||e|
y
T
) + 2 m²
CET
(I 2ee zee T)0] = -(I 1 ||e||2
+
||e| 1
eeT
m
ee
(1 zee T 001 =
B +
2
1
|elp
1
|e
22

---

We make use of the substitution e e= =
|1,311
k-2
m
k22
(T + zee" )01 =
3 + 2
1 + h.2 3
1 1 k
y
(1 + zee" )01 3
m
k22)
1+ k2
We invert the left side using the Sherman Morrison formula:
zee"
(1 + 2 m2
01 = (1 1 =||e||2
)
k22)
122 1
y
zee"
1
(1 + 2 m 1.2)
0, (T 1 =||e|12 )(((
1 1:2
y
1
2 m22
01 B(
)1
k2)
zk?²
1 k2
We simplify this by letting ( (14 1 (1 2 h²2 c and thus 01 = Sc. We now substitute this expression back find the expression of 02:
02 -m(ff 2BTT. e)
y
mlcf3 e 2,8² e)
02
y
0
m
(c8 e 23T e)
m (3Te) (2 +
02
m 1||311(2+
0
y
We simplify the expression for 0g as well by noting that 02 = p|1 where p == + c) We now
calculate the loss of the strategic agent:
fe(0, e) = El0 (x + e) + 02 exp( - || + el|3)]
1 )² exp( (|e|13)
oF O2(
off + 023(
1 +1 exp( 3 |lll
3
oTe 9.3m
<eBTe + 3mpp|
c||| 3mpl ||1
= [|k] + 3mp)
We then now re-evaluate the loss of the model player in terms of the simplified expressions we have found.
3- + 0T, + 07 ee 00,
28 (x((()))==c((((llele + 23t e)) + {B(( exp( exp(->]1e11))
8 - 118-2300, of 20, 24 B11) + 03
11811- 20
2p
(x)) +
-1.8112 20 + 1 c² 1|1 + 2pmck |/|2 + |pm + p
(1 2c 2 2122 2pmck + 4pmnk + 31
23

---

We 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 incentivized to use the value of k 1, which corresponds || This then gives the model loss of ] [|]3 However, in the 2
larger model case, the agent is incentivized to give a value of & of 3.4. This results a higher model loss of z 0.78|| Figure 2 shows the learner plots.
E Further details the Multi-Agent RL Example
Our procedure for constructing the Markov follows from a couple of foundational principles. Given that we are in a two-player game with players and B, we make payoff matrices that make one action for player A the dominant strategy across all states (c.g., our example in 3 We choose the action 0). is important to note that though particular strategy 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 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.
24

---

NeurIPS Paper Checklist
1. Claims
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.
Guidelines:
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 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 long is clear that these goals are not attained by the paper.
2. Limitations
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 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification:
We provide a set of assumptions and complete proofs for each theoretical
result
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the information needed to reproduce the simulations detailed in this work.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our contributions 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.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
y /nips. /nips.cc//ppp httpss/ccccclcgguideeee////////e wwaccc//uuiss//ee
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/ettails
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary 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 the core the paper to 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We focus on theoretical contributions. All of the compute is not sophisticated and is not intense.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///aerrrppp.cc///lll//eeca
Answer: [Yes]
Justification:
The research does conform in every respect with NeurlPS' Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper does discuss the societal impacts of the work being performed. Our work 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 environ- ments. Having a better understanding of the interplay between machine learning systems and strategic environments allows for more principled understanding of the impact and
28

---

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), faimesss 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 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 unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: Paper poses no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 require this, but we encourage authors to take this into account and make best faith effort.
Licenses 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 used and, possible, include URL.
29

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.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 palasets.papersstt paperssi thcode. com con/dataset package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of 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 available online, the authors are encouraged to reach out to the asset's s creators.
13. 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 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. 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 involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS 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.
15. 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 crowdsoureing nor research with human subjects.
30

---

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


Reviews:
[{"review_id": "bQRI41O4qV", "reviewer": "Reviewer_yWQz", "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.\n\nThe 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.", "questions": "See weaknesses section.", "limitations": "The authors have addressed any potential negative impacts.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper's study of the impact of model selection on equilibrium performance is to the best of my knowledge novel; usually commitment is studied in the context of commiting to a single action rather than a set-valued commitment more remiscient of meta-games. Though it is intuitive that set-valued commitment should improve one's equilibrium outcome from the perspective of equilibrium selection, the technical result of the paper (Theorem 3.4) studies when equilibrium is unique and thus commitment has the effect of entirely changing the equilibrium set rather than effecting favorable equilibrium selection, which seems less obvious. It seems that such a result should not be possible when model selection coincides with usual commitment where model selection is only of singleton classes, though it would be helpful for the authors to clarify whether this is the case. Generally, the writing of the paper is polished and accessible.", "weaknesses": "* Restricting one's model class seems to be equivalent to a form of set-valued commitment. From that perspective, it does not seem particularly surprising that gaining commitment power improves one's equilibrium outcome. If this intuition is not correct and there's subtlety, the authors should clarify so in the paper, which currently does not really discuss model selection as commitment.\n\n* 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?\n\n* 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n\n**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**\n\nYou 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. \n\nAs 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]\n\n**The appendix proofs could be written more clearly. In the Theorem 3.4 proof, how is the possibility that ∇θBRe(θ∗)=−1 being ruled out?**\n\nThank you for your feedback on the appendix, we will work to improve clarity in this section. \nFor Theorem 3.4., This is another regularity assumption on the game for this negative result. For a more concrete discussion, please see general comment. \n\n**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?**\n\nPlease see general comment for discussion\n\n[1] Basar, T., & Olsder, GJ. (1999). Dynamic noncooperative game theory. 2nd ed", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pa5EZR4ATA", "reviewer": "Reviewer_QRet", "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.    \n\nOverall, the main ideas presented in this paper are:\n- The choice of model class should be treated as a strategic action when deploying models in strategic environments.\n- There's a need to rethink scaling laws before deploying increasingly complex models in real-world strategic settings.", "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? \n\n2. 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": "Yes, the authors describe the limitations of this approach and potential directions for future work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper challenges the conventional wisdom about scaling laws in machine learning, and draws attention to how strategic interactions between the learner and its environment can affect equilibrium performance. This is an important and relevant topic towards making machine learning models robust for real world applications. \n\n2. The paper clearly outlines the assumptions made in the different settings for which theoretical guarantees  have been provided, along with illustrative examples in related domains to better understand the applicability of its insights.", "weaknesses": "1. Some of the theoretical results presented in the paper rely on strong assumptions, eg. strong monotonicity ensuring existence of a unique Nash equilibrium, or assuming the availability of SGD estimators with decreasing step sizes for all players, which may not always hold in practice. This paper does not focus on empirical evaluations to validate its claims. \n\n2. 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. \n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n**Weaknesses**\n\n**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.**\n\n**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.**\n\n**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$**\n\nFor the main theorem (Theorem 3.4.) and the work on the identification of a model class please see the general comment.\n\nWe 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.\n\n**Questions**\n\n**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?**\n\nYes, you are correct. Thank you for pointing this out. We will edit this in the final version. \n\n**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?**\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9vY84r0coE", "reviewer": "Reviewer_RwJQ", "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.\n\nThey 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.\nFurthermore, 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.", "questions": "Assumption 4.1, what is F?\n\nThm 3.4. define \\delta^* and e^*.\n\nLine 149: define \\Omega and \\calE.", "limitations": "same as above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think overall the results are interesting.", "weaknesses": "Overall, I found the results interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Questions**\n\nThank you for pointing out places where we could further describe the mathematical notation we used. \n\n**Assumption 4.1, what is F?**\n\nHere F is the gradient operator (i.e., F(x) is the gradient evaluated at point x).\n\n**Thm 3.4.**\n\nHere $\\theta^*, e^*$ is the unique Nash equilibrium in $\\Theta \\times \\mathcal{E}$.\n\n**Line 149: define $\\Omega$ and $\\mathcal{E}$.**\n\nHere $\\Omega$ is the space of all model classes and $\\mathcal{E}$ is the space of all actions the environment can select.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "57JY9xcd79", "reviewer": "Reviewer_8iV5", "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.", "questions": "(also including detailed comments)\n\nLine 50: extra space after \"--\"\n\nQuick 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).\n\nAround 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.\n\nAfter 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...\n\nLine 304: extra space\n\nSec 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": "No concerns.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The authors identify an interesting (and to some extent, realistic) phenomenon and establish formal claims about it.  The paper is well written and polished.  The message might be interesting to practitioners.", "weaknesses": "My main complaints are (1) the model is a bit unusual and idealized (e.g., assuming uniqueness of equilibrium) for strategic machine learning, and (2) the results don't appear proportionally strong.  See detailed comments below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n**Punctuations and editorial concerns**\n\nThank you for the comments on punctuation edits. We will correct these in the final version. \n\n**...I also wouldn't view these papers as about learning in games.**\n\nWe 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.\n\n\n**The model is a bit unusual and idealized (e.g., assuming uniqueness of equilibrium) for strategic machine learning**\n\nAs 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). \n\n**It sounds like you are treating strategic machine learning as a simultanous-move game, rather than a Stackelberg game**\n\nOur 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:\n\n1. 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.\n2. 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\n\n**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?**\n\nThe 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. \n\nWe 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. \n\n**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?**\n\nPlease refer to the general comment.\n\n**References**\n\n[1] Meena Jagadeesan, Michael Jordan, Jacob Steinhardt, and Nika Haghtalab. Improved bayes risk can yield reduced social welfare under competition\n\n[2]Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. “Performative prediction.”", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their input to our paper as well as their comments. We appreciate the broad consensus and recognition of the importance of this research avenue within the Machine Learning community, particularly its salience in ensuring the development of robust models for real world applications. We believe that the issue that we highlight is important to characterize and study since it can give us insights into the performance of ML algorithms in real-world environments. Below are some comments to help with any lingering issues:

**On the assumptions made:**

For Theorem 3.4. we would like to note that this result is a negative result which is an existence proof. In particular, we show that even under strong assumptions on the game (e.g., strong monotonicity), we are able to observe non-monotonicity. Through our examples, we show how when these assumptions are relaxed in games without some of the nice properties of the theorem this phenomenon still presents itself. The multi-agent reinforcement learning example we provide, for instance, illustrates this as we have a Nash game where strong monotonicity does not hold, yet we find that performance does not scale monotonically with respect to the expressivity of the policy class. What we sought to show through the theorem was the pervasiveness of this phenomenon even in games with very strong assumptions on their structure. 

**On Online learning for Model Selection in Games:**

Section 4 follows from the non-convexity of the loss as well as the realization that one cannot know what model class to commit to without knowing the objective of the environment. Learning this objective can only be done through repeated interaction with the environment—i.e., a form of online learning. This section provides a framework and first algorithm for thinking about the optimization problem that a learner has to solve. We look forward to future work that looks more expansively at this domain. As posed, with no assumption on the structure of the equilibrium payoff’s relationships between model classes, the learner inevitably has to try out all model classes and thus the dependence on $n$. We leave for future work the question of whether it possible to be no-regret within and across model classes. Furthermore work that is able to better characterize and take advantage of the structure of the non-monotonic landscape could aide in going beyond the dependence on $n$.

We would like to reiterate our appreciation of the general positive reception of the work. We look forward to engaging further to improve the work and clear up any concerns.

Meta-review: The results in this paper are not as strong as one might like. However, it is a solid piece of work.
Decision: Accept (poster)