Maximizing utility in multi-agent environments by anticipating the behavior of other learners
Authors: Angelos Assos
Yuval Dagan
Constantinos Costis Daskalakis
Venue: NeurIPS 2024 poster (2024)
Keywords: Game Theory; no regret; learning theory;
Primary area: online_learning

Abstract: Learning algorithms are often used to make decisions in sequential decision-making environments. In multi-agent settings, the decisions of each agent can affect the utilities/losses of the other agents. Therefore, if an agent is good at anticipating the behavior of the other agents, in particular how they will make decisions in each round as a function of their experience that far, it could try to judiciously make its own decisions over the rounds of the interaction so as to influence the other agents to behave in a way that ultimately benefits its own utility. In this paper, we study repeated two-player games involving two types of agents: a learner, which employs an online learning algorithm to choose its strategy in each round; and an optimizer, which knows the learner's utility function and the learner's online learning algorithm. The optimizer wants to plan ahead to maximize its own utility, while taking into account the learner's behavior. We provide two results: a positive result for repeated zero-sum games and a negative result for repeated general-sum games. Our positive result is an algorithm for the optimizer, which exactly maximizes its utility against a learner that plays the Replicator Dynamics --- the continuous-time analogue of Multiplicative Weights Update (MWU). Additionally, we use this result to provide an algorithm for the optimizer against MWU, i.e.~for the discrete-time setting, which guarantees an average utility for the optimizer that is higher than the value of the one-shot game. Our negative result shows that, unless P=NP, there is no Fully Polynomial Time Approximation Scheme (FPTAS) for maximizing the utility of an optimizer against a learner that best-responds to the history in each round. Yet, this still leaves open the question of whether there exists a polynomial-time algorithm that optimizes the utility up to $o(T)$.

Maximizing utility in multi-agent environments by anticipating the behavior of other learners
Angelos Assos MIT CSAIL Cambridge, MA assos@mit edu
Yuval Dagan UC Berkeley Berkeley, CA
yuvaldag@berkeele.ccoo edu
Constantinos Daskalakis
MIT CSAIL Cambridge, MA costis@mit.ed
Abstract
Learning algorithms are often used make decisions in sequential decision-making environments. In multi-agent settings, the decisions of each agent can affect the utilities/losses of the other agents. Therefore, if an agent is good at anticipating the behavior of the other agents, in particular how they will make decisions in each round as a function of their experience that far, it could try to judiciously make its own decisions over the rounds of the interaction way that ultimately benefits its own utility. In this paper, we
as to influence the other
agents to behave study repeated two-player games involving two types of agents: learner, which employs an online learning algorithm to choose its strategy in each round; and optimizer, which knows the learner's 's utility function and the learner's online learning algorithm. The optimizer wants to plan ahead to maximize its own utility, while taking into account the learner's 's behavior. We provide result for repeated zero-sum games and a negative result for repeated general- sum games. Our positive result is algorithm for the optimizer, which exactly maximizes its utility against learner that plays the Replicator Dynamics - the continuous- analogue of Multiplicative Weights Update (MWU). Additionally, we use this result to provide an algorithm for the optimizer against MWU, i.e. for the discrete-time setting, which guarantees an average utility for the optimizer that is higher than the value of the one-shot game. Our negative result shows that, unless P-NP, there is Fully Polynomial Time Approximation Scheme (FPTAS) for maximizing the utility of an optimizer against a learner that best-responds to the history in each round. Yet, this still leaves open the question of whether there exists a polynomial-ting algorithm that optimizes the utility up to o(T).
results: positive
Introduction
With the increased use learning algorithms as a means to optimize agents' objectives unknown or complex environments, it inevitable that they will be used multi-agent settings as well. This encompasses scenarios where multiple agents are repeatedly taking actions in the same environment, and their actions influence the payoff's of the other players. For example, participants in repeated online auctions use learning algorithms to bid, and the outcome, who gets to win and how much they Other examples arise contract design (see e.g. [3
pay, depends on all the bids (see e.g. 39 40
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Bayesian persuasion (see e.g. (19)), competing retailers that use learning algorithms to set their prices (see e.g. [5 and more.
is thus natural to contemplate the following: in a setting where multiple agents take actions repeatedly, using their past observations of the other players' actions to decide on their future actions, what is the optimal strategy for an agent? This question is rather difficult, hence players often resort to simple online learning algorithms such as mean-based learners: those algorithms select actions that approximately maximize the performance on the past, and include methods such as MWU, Best Response Dynamics, FTRL, FTPL, etc; see e.g. [6]. Yet, when an agent knows that the other agents are using mean-based learners, it can it can adjust its strategy to take advantage of this knowledge. This was shown in specific games [9] 24]: however, in general settings it not known how to best play against mean-basee learners, even if the agent knows everything about the learners, and can predict with certainty what actions they would take as a function of the history of play. This raises the following question:
Meta Question. In a multi-agent environment where agents repeatedly take actions, what is the best strategy for an agent, if knows that the other agents are using mean-based learners to select their actions? Can it plan ahead if it can predict how the other agents will react? Can such an optimal strategy be computed efficiently?
Setting. We study environments with two agents: learner who uses learning algorithm to decide on its actions, and an optimizer, that plans its actions, by trying to optimize its own reward, taking into account the learner's behavior. The setting is modeled as a repeated game: in each iteration t t= L.......7 T, the optimizer selects a strategy æ(t), which is a distribution over a finite set of pure actions A {ai.- an), i.e. axt) E ((A). At the same time, the learner selects distribution v({ over B- = (b,,.... b,), i.e y(()= E A(B). The strategies x(t) and y(!) are viewed as elements I. and RT, respectively. and the elements of A and B are identified with unit vectors. In each round, each player gains a utility, which is function of the strategies paayeed by both agents. The utilities for the optimizer and the learner equal xxt) T Ay(t) and x(t) By(()), respectively, where A, B E Raxm_ The goal of each player is to maximize their own utility, which is summed over all rounds f 1,.... T. We split our following discussion according to the study of zero-sum and general-sum games, as defined below.
Zero-sum games. Zero-sum games are those where A = B. Namely, the learner and the optimizer have opposing goals. Such games have value, which determines the best utility that the players can hope for, if they are both playing optimally. It is defined as:
Val(A)
max min TTAy min max x Ay VEA(B)
DEA(A)
The two quantities in the definition above are equal, follows from von Neumann's minmax theorem. The first of these quantities implies that the optimizer has a strategy that guarantees them a utility of Val( A) against any learner, and the second quantity implies that the learner has a strategy which guarantees that the optimizer's 's utility is at most Val(A). Such strategies, namely, those that guarantee minmax value, are termed minmax strategies.
If the learner would have used a minmax strategy in each round t, then the optimizer could have only received utility of 7 (A)( Yet, when the learner uses learning algorithm, the optimizer can receive higher utility. A standard theoretical guarantee in online learning is no-regret. When a learner uses no- no-regret algorithm to play a repeated game, it is guaranteed that the optimizer's 's reward after T rounds is at most T Val A) + o(T). Yet, T is finite, and the ((T))teem can be significant. Consequently,
pose the following question, which we study in Section 2
Question 1. In repeated zero-sum games between an optimizer and a learner, when can the optimizer capitalize on the sub-optimality of the learner's 's strategy, to obtain significantly higher utility than the value of the game? Can the optimizer's algorithm be computationally efficient?
General-sum games. Games where B o A are termed general-sum. These games are signifi- cantly more intricate: they do not posses a value or minmax strategies. In order to study such games, various notions of game equilibria have been proposed, such as the celebrated Nash Equilibrium. In the context related to the topic of our paper, the optimizer could commit on a strategy, and the other player would best respond to it, rather than using a learning algorithm, then the optimizer could
2

---

get the Stackelberg value, by playing according to the Stackelberg Equilibrium. Further, there is polynomial-time algorithm compute the optimizer's strategy this case [21 20
Against a learner that uses a no-regret learning algorithm, the optimizer could still guarantee the Stackelherg value of the game, by playing according to the Stackelberg Equilibrium. Yet, it was shown that in certain games, the optimizer can gain up to (2(T") more utility compared to the Stackelberg value when they are playing against mean-based learners 9 24
30 18). However, this often strategy which changes across time. While such a strategy could no efficient algorithm was known for general games. Deng et al. (24] devised a control problem whose solution is approximately the optimal strategy for the optimizer, against mean-based learners. Yet, they do not provide computationally--ffiiooo
37
requires playing carefully-planne be computed in polynomial-time time for specific games 9
B
23
algorithm for this control problem. Finding an optimal strategy for the that can be summarized as follows:
learner was posed as an open problem (24
Question 2. In repeated general sum games between an optimizer and mean- mean-based learner, is there a polynomial time algorithm to find an optimal strategy for the optimizer?
We study this question in Section
3
1.1 Our results
Our results are two-fold: In zero sum games, we provide positive results, and show what the optimizer's 's optimal rewards and strategies for a given game should be, in both discrete and continuous time games. Our results in that realm are the following:
For continuous time games, we provide an exact, closed form solution of the rewards of the optimizer against learner that uses the replicator dynamics, i.e. continuous MWU (Section
2. Theorem D. In the same theorem we prove that the optimizer can achieve optimal rewards by playing constant strategy throughout the game. i.e. xt)) xx; x E (AAVt [O,
We also prove range where the optimal rewards might be and provide a lower bound for when 1/7 + Do (Section 2
Proposition D.
For discrete time games, when the optimizer is up against learner that uses MWU, we first prove that the optimal rewards of the optimizer in this setting, will be lower bounded by the rewards of the optimizer in the continuous time game, if they use the same strategy x Proposition 2).
(Section 2
We then prove that the reward "gap" between continuous and discrete time games cannot be greater than 1/T/2 (Section B Proposition 10 and there games that achieve gap of at least ((rTT)) (Section 2 Proposition 3). In fact we give a class of games that can achieve that gap in rewards (Section Proposition
In general-sum games, we provide the first known computational lower bound for calculating the optimal strategy against mean based learner. We formalize the problem of optimizing rewards as decision problem, where the answer for an instance is 'YES' if the optimizer can achieve rewards more than T and 'NO' if the optimizer can receive rewards at most T 1. We prove that there is no polynomial time algorithm, assuming P * NP that distinguishes between the two cases by using a reduction from Hamiltonian Cycle. The formal theorem and sketch of the reduction construction can be found in Section 2 Theorem
1.2 Related Work
The game-theoretic modeling of multi-agent environments has long history 16 45 27
Such studies
often revolve around proving that if multiple agents use learning algorithms repeatedly play against each other, the avarege history of play converges to various notions of game equilibria [4] T6].
Recent works have shown that some learning algorithms yield fast convergence to game equilibria and fast-decaying regret, if all players are using the same algorithm [4] 22
26 42 46).
Optimizing against no regret learners. Braverman et al. 9 initiated a recent thread of works,
which studies how player can take advantage of the learning algorithms run by other agents in order to gain high utility. They showed that various repeated auctions where a seller sells an item to single buyer in each iteration t I,..., T, the seller can gain nearly the maximal utility that they
3

---

could possibly hope for, if the learner runs an EXP3 learning algorithm (i.e., the seller's utility can be arbitrarily close the total welfare). This can be Q?TT)) larger than what they can get if the buyer is strategic. Deng et al. [24] generalized the study to arbitrary normal-form games. They showed an example for a game where an optimizer that plays against any mean-based learner gets (I(T) more than the Stackelberg value, which is what they would get against strategic agents. The same paper further showed that against no-swap-regret learners, the optimizer cannot gain (T(T)) more than the Stackelberg value and Mansour et al. [37] showed that no-swap-regret learners are the only algorithms with this property. Brown et al. [ showed a polynomial time algorithm to compute the optimal strategy for the optimizer against the no-regret learner that is most favorable to the optimizer yet, such no-regret learner may be unnatural. Additional work obtained deep insights into the opümizee//earmer interactions in general games [T] [5] in Bayesian games [37] and in specific games
such as auctions 23 13 35 34). contract design (30 and Bayesian persuasion [8]
Optimizing against MWU in 2 x 2-games. Guo and Mu 29 obtain a computationalll--fficci algorithm for optimizer that is playing zero-sum game against learner that uses MWU, in games where each player holds 2 actions, and they analyze that optimal strategy.
Regret lower bounds for online learners. Regret lower bounds for learning algorithms are tightly related upper bounds for an optimizer in zero-sum games. The optimizer can be viewed as an adversary that seeks to maximize the regret of the algorithm. The main difference is that these lower bounds construct worst-case instances, yet, we seek to maximize the utility of the optimizer in any game. Regret lower bounds for MWU and generalizations of it were obtained by [17] 32 15] 28 Minmax regret lower bounds against any online learner can be found, for example, in 16
Approximating the Stackelberg value. Lastly, the problem of computing the Stackelberg equilib- rium is well studied [21 41 20). Recent works also study repeated games between an optimizer and a learner, where the optimizer does not know the utilities of the learner and its goal learn to be
nearly good as the Stackalberg strategy 66 38 36 31.
2 Optimizing utility in zero-sum games
Continuous-time games. We begin our discussion with continuous-time dynamics, where x(1) and (tt are functions of the continuous- parameter t [). The total reward for the optimizer LTT xt()T T Ay(())t, whereas the learner's utility equals the optimizer's utility multiplied by -1. We assume that the learner is playing the Replicator Dynamics with parameter 1) > O. which is the continuous-timg analogue of the Multiplicative Weights Update algorithm, which plays at every time
t
exp (n I(s)T Beids)
(1)
1,...,m. m.
Σ/ exp 17 S xss) Be,ds)
This formula gives a higher weight actions that would have obtained higher utility in the past. When v) is larger, the learner is more likely to play the actions that maximize the past utility. The value of 1) usually becomes smaller as T increases, and typically 1) 0 as T co.
The following definition will be helpful for the analysis:
Definition (Historical Rewards for the learner). The historical rewards for the learner in continuous games at time t, denoted by h(t) RT, is m dimensional vector where ha h₂(t), 1,... ...... m corresponds to the sum of rewards achieved by action a; of the learner against the history of play in the game far. We assume general setting where the learner at 0 might have non-zero historical rewards, iee. h(()) E IR". If the strategy of the optimizer is x: [0 + A(A) we get:
(tt)) = h(()) + f"B
[B" (Tt(ddttt
Suppose the game has been played for some time / and the learner has collected historical rewards h(t). The total reward that the optimizer gains from the remainder of this game can be written as

---

function of the time left for the game T t, the historical rewards of the learner at time t, h(t), and the strategy x |0, T A (A) of the optimizer for the remainder of the game.
Ei= c"(Mi(u)+) B a(()dd) e, A x(u)
Reone ]
du
(2)
Ex= c B3 J =(s)as)
For simplicity, can just transfer the time to and assume that the historical rewards of the learner are just h(0). That way we can rewrite the above definition as:
/ E (M.(()))) B So ((a())ds)) e, A xxtt) En (b.(0)))) n m(s)ds)))
Reona (z, h(0), 7, A, (,
dt
(3)
In general we are interested in finding the maximum value that the optimizer can achieve any moment of the game:
Roond (h(0), r, A, B) max (x h(0), A, B)
(4)
For finding the optimal reward for the optimizer from the beginning of the game would have find Reons (0, T, A, B), where 0 = (0, 0, 0)
The next theorem characterizes the exact optimal strategy for the optimizer, against learner that uses the Replicator Dynamics in zero sum games:
Theorem 1. In zero-sum continuous game, when the learner is using the Replicator Dynamics, the optimal rewards for the optimizer can be achieved with a constant strategy throughout the game, i.e. art)) = ((A). The optimal reward is obtained by the following formula:
In mh 1
In (Eth (m)(00)) AT
Reont
max xEA(A)
(5)
Further, x² is the maximizer in the formula above.
Proof. For zero sum games in continuous time, we have that equation 3 becomes:
Ex " (M.(())) AT 18 (())ds)) of AT x(1)
Reone M(0), T, A,- jo Em (m(((0)ee) A =()(d)
dl
(6)
Notice that
dt (e)(t:0))0TA) 13 =((()d))) = (A(100))- (())ds)
dt nhh((0) n.. -n. A
AT J x(s)ds
From Leibniz rule we have that d
2 So x(()ds =x(), thus we get:
(c0(M:(0)='''* s(()dd)) - (na(000) a(e)ds) 17 A x(t)
Given that, note that we can find a closed form solution for Reont (z, h(0), T, A, AA) as follows:
Reont (z, h(0), A, A)
1
In
Σ (R.(10)) AA a()dds))
7
In EEE (0),
In Em I (M) fg 2(s)de)
7
Suppose the optimal rewards Ro (h(0), 1,, A, A) are achieved with - Note that the final reward only depends on Jo as))ds, thus the same reward that is achieved by x (t), can be achieved by x- So znp (s)ds. Thus there exists x such that:
In (Em cnh.(0)) - In Em (bh(0)-=[AATT
R Re (h(0), -. AA)=
17
which is what we wanted.
5

---

The optimal strategy x² for the optimizer in continuous zero-sum games can be therefore obtained by finding the minimum of the convex function f(z) = In (E e" (A.(0))-)) =' We can compute the optimal strategy of the optimizer in an efficient way using techniques from convex optimization. More details can be found in the appendix at Proposition
We further analyze how larger the optimal achievable reward is, compared to the naive bound of T (A). We specifically show that always the optimal rewards the optimizer are in the range of [T (A)( T (A) + log(m)/ where is the number of actions of the learner, showing the optimizer can always get more utility than just the value of the game.
We also analyze what happens to the rewards of the optimizer as 1/T co. First, let us define for any optimizer's strategy v, the set of all best-responses.
BR(x) = arg max a BEB
Bb.
This defines set, and if there are multiple maximizers, proposition:
BR(x)) 1. We then have the following
Proposition 1 (informal). The optimal reward for an optimizer playing against a learner that uses the replicator dynamics with parameter n in an mn game, the range (T Val(A), Val(A) + log(m)/n)- Further, 1ÿT - co, this optimal utility is at least
T Val( + log(m/k)
where ks =
min
[B(())]
7)
rEA(A) minmax strategy
The proof of Proposition [ can be found Appendix B Propositions and We note that the limiting utility is obtained by playing constantly any minmax strategy that attains the minimum in the definition of & above.
Connection to optimal control and the Hamilton-Jacohi- Bellbln equation. We will present another way of achieving Theorem I using literature from control theory. One can view the problem of maximizing the optimizer's 's utilities as an optimal control problem; what control (or strategy) should the optimizer use in order to maximize their utility given that the learner has some specific dynamics that depend on the control of the optimizer? The Ramilton-Jacobi-ee Bellman equation [ gives us a partial differential equation (PDE) of R (h, t, A, B) that if we solve, we can find closed form solution of the optimal utility of the optimizer. The equation (for general sum games):
d." (h. t. A,
m DEseeM
e, A e
+ Roon th, BBxz)
max #EA(A)
dt
The intuition of the PDE is as follows; the current state of the learner can be defined given only the history h of the sum of what the optimizer played so far, and the time left in the game Given we are at state h, f, the optimal rewards for the optimizer are going to be equal to the rewards of playing action x E (AA) for time At added together with the optimal reward in the new state, namely R (h + B xAt, t + At, B). Taking the limit as At 0, gives us the above partial differential equation.
Plugging in B - A, for the of zero-sum games, get:
d.Cnnt (h, 1, A, A)
Lis1 the e, AJx
(h, t, -A)) ATx
max zEA(A)
21=1 e
If one plugs in the formula we calculated in Theorem they would find that indeed it is solution to the above PDE.
Discrete-ting games. We now move to the discrete-time setting. The learner is assumed to be playing the Multiplicative- Weithtss update algorithm, defined by:
exp 1) 1-11 (s)) Beg
(t)
i= 1,
(8)
77 Ej cxp 17 E'= TB)))
We show that if the learner constantly plays the strategy x² that is optimal for continuous-time, the obtained utility against MWU can only be higher, compared to playing against the Replicator Dynamics in continuous-time, with the same step size 77:

---

Proposition 2 (informal). Let A be a zero-sum game matrix and 1) > 0 and T E N. Let x² E A(A) be the optimal strategy against the replicator dynamics, from Theorem [ Then, the utility in the discrete time, achieved by an optimizer which plays x(t) = x² for all I. E [1...., .T) against MWU with parameter 7, is at least the utility achieved in the continuous-tine by playing x² against the replicator dynamics with the same parameters 1), T.
The proof can be found in Appendix B (Proposition
Proposition 2 implies that Proposition 1 provides lower bounds on the achievable utility of this constant discrete-tine strategy. In order to further analyze its performance, we would like to ask how much larger the discrete-time utility of the optimizer can be from the optimal continuous-time utility. We include the following statement, which follows from a standard approach:
Proposition 3. Let T E N and O. For any zero-sum game whose utilities are bounded in [-1, 1]. the best discrete-time optimizer obtains utility of at most nf' /2 more than the best continuous-tin optimizer. Further, there exists game where the best discrete- time optimizer achieves utility of tanh(n)T/2 (1) ((1))))T more than the optimal continuous time optimizer, and tanh(n) more than the discrete-time optimizer from Proposition
The proof can be found in Appendix B (Propositions and
Proposition 3 implies that in some cases, the best discrete-time optimizer can gain T VV) (T]T). We would like to understand in which games this is possible for any choice of 1j E (0, 1). We provide definition that guarantees that this would be possible:
There exists minmax strategy for the optimizer such that there exist best responses for the learner, bi, big E BR(x)), which do not coincide on support(z). Namely, there exists an action ag E support(z) such that af Ab;, # ag Ab,
Condition 1.
To motivate Condition [ notice that in order to achieve a gain of Q()TT) for any n, the discrete optimizer has to be sigmiicantly better than the continuous-time optimizer. For that to happen the learner would have to change actions frequently. Indeed, the difference between the discrete and continuous learners is that the discrete learner is slower to change actions: they only change actions at integer times, whereas the continuous learner could change actions at each real-valued time. In order change actions, they need to have at least two good actions, and this is what Assumption I guarantees. We derive the following statement:
Proposition 4, For any zero-sum game A E Raxm that satisfies Assumption 7 E (0, and T E N, there exists an optimizer, such that against learner that uses MWU with step size n, achieves a utility of at least T Val(A) + ((T(("), where the constant possibly depends on A.
The proof can be found in Appendix B (Proposition T1I.
Proposition 4 considers a strategy for the optimizer which takes the minmax strategy x from As- sumption and splits into two strategies: x²,²" E (A)), such that (x' + /2 = æ. Further, x' Ab; * "T Abiz. where bi, bi, are defined in Assumption [ It plays x' in each odd round t. and x" in each even round. It is possible to show that in each two consecutive iterations, the reward for the optimizer is 2 Val(A) + 2(7). Summing over T/2 consecutive pairs yields the final bound.
3 A computational lower bound for optimization in general-sum games
In this section, we present the first limitation optimizing against mean-based learner. Specifically, we study the algorithm which is termed Best-Responss or Fictitious Play [10 43 At each time step t 1,..., T. this algorithm selects action y(t) that maximizes the cumulative utility for rounds
vt) = arg max (EA(B)
Σ TTS) By
There is always maximizer which corresponds to a pure action by E B of the learner and we assume that if there are ties, they are broken lexicographically. In this section, we constrain the optimizer to also play pure actions.
7

---

To put this algorithm in context, we note the following connections to general mean based learners: (1) mean- mean-based learners are any algorithms which select an action yt) that approximately maximizes Eq. (9) (2) Best-Response is equivalent to MWU with v) + 0o.
We prove that there is algorithm that approximates the optimal utility of the optimizer up an approximation factor of 1 - e, whose runtime is polynomial in m, I and 1/e, as exemplified by the following (informal) Theorem:
Theorem 2 (informal). Let Alg be an algorithm that receives parameters > m. n,T N and utility matrices A, B of dimension m x n and entries in [0, 11, and outputs a control sequence r(1).... x{T) E A. Let U denote the utility attained by the learner and let U* denote the optimal possible utility. Uf 2 (1 - e\U* for any instance of the problem, and if P + NP, then Alg is not m, n, T and 1/c.
polynomial-
A sketch of the proof can be found below. and full proof can be found in the Appendix C The proof is obtained via a reduction from the Hamiltonian cycle problem. We note two limitations of this result: (1) The lower bound is for T = n/2 + 1, and it shows hardness in distinguishing between the case that the optimal reward is T and the case that the optimal reward is at most T - 1. It is still open whether could efficiently find sequence that optimizes the reward up oT)); (2) fictitious-plar a fundamental online learning algorithm. Yet, it does not possess the no-regret guarantee. It is still open whether one could obtain maximal utility against no-regret learners such as MWU with a small step size.
We continue by framing the problem of maximizing rewards against Best- Dest-Response learner decision problem, called OCDP:
Problem (Optimal Control Discrete Pure (OCDP)). An OCDP instance is defined by (A, B, m, k. T), where n. m, T E N. A e {0, 1|nxm and B [0.1] The numbers and m correspond to the actions of the optimizer and learner in a game, where the utility matrix of the optimizer and B is the utility matrix of the learner. This instance is 'YES' instance if the optimizer can achieve utility at least k after playing the game for T rounds with a learner that uses the Best Response Algorithm (Eq. (9), and 'NO' if otherwise.
We will prove that OCDP is NP-hard, using a reduction from the Hamiltonian cycle problem.
Problem 2 (Hamiltonian cycle). Given a directed graph G(V, E), find whether there exists Hamiltonian cycle, iee a cycle that starts from any vertex, visits every vertex exactly once and closes at the same vertex where it started.
is a known theorem that the Hamiltonian Cycle is an NP-complete problem, as it is one of Karp's 21 initial NP-Complete problems.
Theorem (333), Hamiltonian Cycle is NP-complete.
We conclude with the main result of this section, followed by proof sketch. The full proof appears in Section C
Theorem OCDP NP-hard. That is, if + NP, there exists no algorithm that runs in polynomial time in n. m and is which distinguishes between the case that reward of l is achievable and the case that it impossible to obtain reward more than k
Proof sketch. Consider an instance of the Hamiltonian cycle problem: лH (V,E), where V {ui,..., "n J E {ei...., )- We create an instance of OCDP as follows. First, set T = k = + 1. We will construct the instance such that the optimizer can receive reward there is a Hamiltonian cycle in the graph. Define the optimizer's 's actions to be {ai, am }. and the learner's actions to be {b) {bi,..., bn, by................ ., b', Namely, for each node d of the graph, the learner has two associated actions, b, and by. The details in the sketch differ slightly from the proof for clarity. The reduction is constructed to satisfy the following properties:
1 if and only if
The only way for the optimizer to receive maximal utility, to play a strategy as follows: the first actions should correspond to edges ei 6ig es,, that form a Hamiltonian cycle which starts and ends at the vertex W1; and the last action corresponds to e e which is outgoing edge from V1.
8

---

We define the utility matrix for the learner such that, if the optimizer is playing according to this strategy, then the learner's 's actions will correspond to the vertices of the same cycle, denoted as Ujj
1/,, V)z- This is achieved by defining the learner's s tie-breaking rule to play d1 in the first round; and defining the learner's 's utilities such that, if the optimizer 1 the edges along path U/
U/e- then the best response for the learner at time t would be to play aj., To achieve this, we define for any edge EN = (Up, vg): B faa, 6n] = -1, B (as, bel = 1 and B Blas, bj = 0 for any other action b. Consequently, after observing the edges along bn -.... - bj. the cumulative reward for the learner would be 1 for bj.- -1 for by, and 0 for any other bj. Consequently, the learner will best respond with bj. we ignore the actions b/..... by of the learner at the moment.
has played in rounds 1, ,...., L
In order to guarantee that the above optimizer's strategy yields a utiliity of n n-+1, 1, we define the optimizer's utility such that Alex; 6/l 1 if eg (Up, (g) and for all q A p Alex, b,] O. This will also force the optimizer to play edges that form a path. Indeed, if the optimizer has previously played the edges along a path Vj learner will play ba, in the next round. For the optimizer to gain a reward at the next round, they must play an edge outgoing from az.- This preserves the property that the optimizer's actions form path.
UjS- then, as we discussed, the
Next, we would like to guarantee that the optimizer's 's actions align with Hamiltonian cycle. Therefore, we need to ensure that the path played by the optimizer does not close too early, Namely, if the learner has played the edges along the path 1/ J1, .i,....7. Jr are all distinct. For this purpose, the actions v/,,- .i..... 1n are defined. We define for any edge ex (v), 2y): B[ax, 6ş] 0.85. This will prevent the optimizer from playing the same vertex twice, for any round t = I,..., n (recall that there are T = n + rounds), as argued below.
V/j and if < n,, then
Assume for the sake of contradiction that the first time the same vertex is visited is at t, where j: Jr for some r < t S n. Then, the cumulative utility of action 6/, for rounds 1....,: E is 1.7, which is larger than any other action. This implies that at the next round, the learner will play action 1/z. We define the utility for the optimizer to be zero against any action b/. Hence, any scenario where the learner plays an action B/,, prevents the optimizer from receiving a utility of 1. This happens whenever i, = in for some j < S n. Hence, optimizer that receives reward of 1 at any round must play a path that does not visit the same vertex twice, in rounds! = , ni.
Lastly, notice that we do want the optimizer to play the same vertex a1 twice, at rounds 1 and 1. This does not prevent the optimizer from receiving optimal utility. Indeed, if the optimizer would play the action a1 twice, then the learner would play bj at the next round. Yet, since there are only n + rounds, there is "next round" and no reward is lost. The details that force the learner to play bi in round n + 1 appear in the full version of the proof.
The above explanation sketches why it is possible to get n + 1 reward if and only if there is Hamiltonian cycle and this concludes the reduction.
4 Conclusion and future directions
In this paper we studied how an optimizer should play in a two-player repeated game knowing that the other agent is learner that is using known mean-based algorithm. In zero-sum games we showed how they can gain optimal utility against the Replicator Dynamics and we further analyzed the utility that they could gain against MWU. In general sum games, we showed the first computational hardness result on optimizing against a mean-based learner, by reduction from Hamiltonian Cycle.
One interesting problem that remains is the open is analyzing the optimal reward in general sum games against the Replicator Dynamics (or the MWU), which was denoted as R (0, A, B). In the fully general case with no restriction on the utility matrices A and B, we believe there is no closed form solution for the optimal utility, differently from the zero-sum case. However, it would be interesting to understand how Re (0, T, A, B) behaves as function of A and B and how the best strategy for the optimizer looks like. conjecture in this direction was given by Deng et al. (24). Perhaps it would be casier to study simpler scenarios, such as the one where rank A + B) 1.

---

which has been explored in the context of computing equilibria and the convergence of learning algorithms them (.,) B. Another direction is improving on the lower bound for general sum games. Currently, we prove that it is hard to distinguish between the case where the optimizer can achieve reward a = 7 and the case where the optimizer cannot achieve more than also hard to distinguish between reward of at least or at most /3 in cases where Are there lower bounds when the learner uses different learning algorithms, such as MWU? Other relevant open directions are extensions to multi-agent settings [13,, analyzing how the learner's utility impacted by interaction with the optimizer in general-sum games [30], which learning algorithms yield higher utilities against an optimizer, and what algorithms should be used to both learn and optimize at the same time?
T
3 Q?())
Societal impact. The work studies multi-agent environments and how agents benefit by anticipating the behavior of other agents. We believe that increasing the academic knowledge this topic can help learning agents assess their risk of being utilized by other agents and can help to build algorithms that are more resilient to manipulation. As always with new technologies, there a risk that malicious players will utilize ideas from this paper, which could cause harmful effect other agents.
10

---

References
[1] Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, and Bernhard Von Stengel. Fast algorithms for rank-1 bimatrix games. Operations Research, 69(2):113-631, 2021.
[2] Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In ACM Symposium on Theory of Computing, 2022.
[3] loannis Anagnostides, Gabriele Farina, Ioannis Panageas, and Tuomas Sandholm, Optimistic mirror descent either converges to nash or to strong coarse correlated equilibria in bimatrix games. Advances in Neural Information Processing Systems, 35: 35:16439-164555 2022.
[4] Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum sum games. In International Conference on Machine Learning. 2022.
[5] Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. Pareto-optimal algorithms for learning games. arXiv preprint arXiv:2402.0554, 2024.
[6] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 61-78, 2015.
[7] Amir Beck. First-order methods in optimization. SIAM, 2017.
[8] Richard Bellman. Dynamic programming and a new formalism in the calculus of variations. Proceedings of the national academy of sciences, 40(4):231-235 1954.
[9] Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinherg. Selling no-regret buyer. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 523-538, 2018.
[10] George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13 (1):374, 1951.
[11] William Brown, Jon Schneider, and Kiran Vodrahalli. Is learning in games good for the learners? Advances in Neural Information Processing Systems, 36, 2024.
[12] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
[13] Linda Cai, S Matthew Weinberg, Evan Wildenhain, and Shirley Zhang. Selling to multiple no-regret buyers. International Conference on Web and Internet Economics, pages 113-129. Springer, 2023.
[14] Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolo, and Sergio Pastorello. Artificial intelligence, algorithmic pricing, and collusion. American Economic Review, 110(10):326- 3297, 2020.
[15] Nicolo Cesa-Biama Bianchi. Analysis of two gradient-based algorithms for on-line regression. In Proceedings of the tenth annual conference on Computational learning theory, pages 163-170, 1997.
[16] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[17] Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert Schapire, and Manfred Warmuth. How use expert advice. Journal of the ACM (JACM). 44(3):427-485, 1997.
[18] Yiling Chen and Tao Lin. Persuading behavioral agent: Approximately best responding and learning. arXiv preprint wrX12:2302.03719 2023.
[19] Yiling Chen and Tao Lin. Persuading behavioral agent: Approximately best responding and learning, arXiv preprint arXiv:2302.03779, 2023.

---

[20] Natalie Collina. Eshwar Ram Arunachaleswaran, and Michael Kearns. Efficient stackelberg strategies for finitely repeated games. In Proceedings of the 2023 International Conference on Autonomous Agents and Mulliagent Systems, pages 643-651, 2023.
[21] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 82-90, 2006.
[22] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604- 27616, 2021.
[23] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Prior-free dynamic auctions with low regret buyers. Advances Neural Information Processing Systems, 32, 2019.
[24] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. Advances in neural information processing systems, 32, 2019.
[25] Heng Du and Tiaojun Xiao. Pricing strategies for competing adaptive retailers facing complex consumer behavior: Agent-based model. International Journal of Information Technology & Decision Making, 18066):999-1199, 2019.
[26] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. In Neural Information Processing Systems (NeurIPS), 2022.
[27] S. Freund and L. Gittins. Strategic learning and teaching in games. Econometrica, 66(3): 597-625, 1998.
[28] Nick Gravin, Yuval Peres, and Balasubramanian Sivan. Tight lower bounds for multiplicative weights algorithmic families. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss- SaetossDDagstth--eiiiiee Zentrum für Informatik, 2017.
[29] Xinxiang Guo and Yifen Mu. The optimal strategy against hedge algorithm in repeated games. arXiv preprint urXiv:2312.09477 2023.
[30] Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasiln Vasileios Vlatakis Vlatakis-Gkaragkoumt Gkaragkounis, Joshua R Wang, and Matthew Weinberg. Contracting with learning agent. arXiv preprint arXiv:2401.16199 2024.
[31] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. Learning in stackelberg games with non-myopic agents. In Proceedings of the 23rd ACM Conference Economics and Computation, pages 917-918, 2022.
[32] David Haussler, Jyrki Kivinen, and Manfred K Warmuth. Tight worst-case loss bounds for predicting with expert advice. In European Conference on Computational Learning Theory, pages 69-83. Springer, 1995.
[33] Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
[34] Yoav Kolumbus and Noam Nisan. Auctions between regret-minimizing agents. In Proceedings of the ACM Web Conference 2022, pages 100-111, 2022.
[35] Yoav Kolumbus and Noam Nisan. How and why to manipulate your own agent: On the incentives of users of learning agents. In Advances in Neural Information Processing Systems, volume 35, pages
2022.
[36] Niklas Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu. No-regret learning in dynamic stackelberg games. In arXiv preprint arXiv:2203. 17184, 2022.
[37] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against learners bayesian games. In Conference on Learning Theory, pages 5221-5252. PMLR, 2022.
12

---

[38] Janusz Marecki, Gerry Tesauro, and Richard Segal. Playing repeated stackelberg games with unknown opponents. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems Volume 2, pages 821-828, 2012.
[39] Denis Nekipelov, Vasilis Syrgkanis, and Eva Tardos. Econometrics for learning agents. In Proceedings of the sixteenth acm conference on economics and computation, pages 1-18, 2015.
[40] Gali Noti and Vasilis Syrgkanis. Bid prediction in repeated auctions with learning. In Proceed- ings of the Web Conference 2021, pages 3953-3964 2021.
[41] Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2149-2156, 2019.
[42] Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near- optimal uncoupled online learning via clairvoyant multiplicative weights update. Advances in Neural Information Processing Systems, 35:22258 25:22255-22269, 2022.
[43] Julia Robinson. An iterative method solving a game. Annals of mathematics, pages 296-301, 1951.
[44] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, volume 28, 2015.
[45] Youn. Learning algorithms in games. Journal of Game Theory, 56(2):123-1344 2004.
[46] Brian Hu Zhang, Gabriele Farina, loannis Anagnostides, Federico Cacciamani, Stephen Marcus McAleer, Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Computing optimal equilibria and mechanisms via learning in zero-sum extensive- form games. In seirth- Conference Neural Information Processing Systems, 2023.
13

---

A
Additional Definitions
We introduce the following definitions that will help us in the future proofs.
Definition (Historical Rewards for the learner). The historical rewards for the learner continuous dimensional vector that corresponds to the sum of
games at time i, denoted by h(t) IRTh is rewards achieved by each action of the learner against the history of play in the game so far. assume general setting where the learner at f = O might have non-zero historical rewards, i.e.
h(0) IR" If the strategy of the optimizer x [0,0] + (AA) we get:
h(t) h(0) [ B x(t)dt
In the discrete setting, given that the optimizer has played zo, ,t. A(A). we have for t 2 1:
k(1) = h(0) +
32
1=
Definition 3 (Value of the game). In case, where B - define the value of the game for the optimizer as Val(
Val(A) min max x Ay (EA(B) zEA(A)
Definition (Best Response Set). For a given strategy of the optimizer A(A), denote by BR(x) the set of best responses by the learner:
BR(x) = {eali E argmin [x [eAee]]
Definition 5 (Min-max strategies). Denote with MinMaxStratsana (A) the set of strategies of the optimizer that achieve the value of the game.
{ I A(4)
MinMaxStrats.pp4A) (A)
Val(A) min x Ae; xE(m)
A.1 Algorithms for the learner
For completeness, we provide pseudocode for the algorithms.
Definition 6 (MWU Algorithm). Fix the step size 0 S 2. In game where the utility matrix of the learner is B, the MWU algorithm as follows:
Algorithm MWU algorithm
1: procedure MWU(B, T m)) h(()) (0,0, 0, ...0) 0)
2:
3:
for f = 1.2, do
4:
+- De eTAAT
5: Submit
6: Observe
7:
+ 1) 1( BB
8:
end for
9:
end procedure
Definition 7 (Replicator Dynamics). Suppose 10, A(A) is strategy for the optimizer. the learner using the replicator dynamics, the strategy for the learner at time is given by:
exp (n 2(s)T Be,)
(1) Σn= exp (1 I(6)T Be,) , 11,2....,,1
(10)
14

---

Definition 8 (Best Response Algorithm). In a game where the utility matrix of the learner is B, the best response algorithm as follows, assuming we break ties lexicographically (i.e. if h;((t) (t) then by beats by if <
Algorithm 2 Best Response algorithm
1: procedure BRA(B, T)
2:
h(0) (0, 0, 0)
3: for = 0, 1...,................. T do
4:
K Dergmax.e(m) kC())
5: Submit
6: Observe 24
7: 1(t () h(t) + B
8:
end for
9:
end procedure
B Optimization in zero-sum games: missing proofs
In this section, we present some ommited proofs of lemmas mentioned in the main section.
B.1 Continuous games
First, we prove that the optimal strategy for the optimizer in continuous games can be computed efficiently. From theorem [
we know that the optimal strategy for the optimizer throughout the game, just (tt) x², where minimizes f(x):
m f(x) = In Σ
(h. ATTTAT)))
The above also known as the log-sum-exp functioo. This is a convex function, which allows us to compute its minima efficiently. We use the following two lemmas.
Lemma (Example 5.15 (7]) The log-sum-exp function f IR" + R, for which f(x) =
In (Ee i=1 e is 1-mmooth with respect the E,, foo norms and convex.
Lemma (Theorem 3.8, [22 ) For function f X R that is convex and B-smooth with respect to a norm ||-|l and where R = =uup I| - yll. the Frank- Wolfe algorithm can find xe on O(t) time
for which:
f(x.) - f(x")==+--)))))))))))) 23R
t+1
We therefore compute the approximate optimal strategy for the optimizer efficiently:
Proposition 5. For zero continuous games where the learner is using replicator dynamics, can find an e approximate optimal strategy for the optimizer in O (2) time. That is we can find x for which:
Roone (,, RRoont (x, O,T, -)
From we also know that is 1msoohth with respect to the l-p norm. Note that since the strategies are on the simplex, we have that R supz.9 22....l || yll
Proof. Consider the function g(x) In Em (o) (TTT))) (Ta))
Using lemma 2 with t 1 we can find for which
g(x) g(x")= < en. Using theorem we get:
Ro O0 - A) - Reone (x, 0,7,A,A,AA. g(x) g(x")
Se
"
as required.
Next, we bound the range of the possibilities for the utility gained by the best optimizer:
15

---

Proposition 6. In the zero-sum continuous setting, the optimizer's optimal utility is bounded as follows:
In
Val(A) TT R A -A) Val(A) T
(11)
where Val(A) is defined in 3
Proof. We have:
Σ c me? ATxT) xT) )
Reont (O,T,A, A) In (m)) -minn
m
ente] -e. (AT)ATa =3Taar=()) 1002)))
In (m))
max xEA(A) jE(.2....m)
min
In e -- A ATxT #f
In (m) min max SE
-nc A xT IT +
Σ cл(e] -c. AATTT
i=1
In (m) + max
min JE(22))
nez neeA A xT - -n Σ m -c DATATT
Note that picking out the for which e, AJA S A for all E [m]. makes enee -e])A nT S
1 for all = 1,2,..., m. On the other hand en -e] A 1 That gives In 0 s Ein eie -e, )A s Inm. We finally have:
min A xT' Inm (12)
min oj A TT' R,, A, 5 xEA(A) (1.2......
max
max
zEA(A) je (1........))
"
which is exactly what we want.
If we take the limit of the game as 7 goes infinity, we can lower bound the optimal rewards of the optimizer by considering strategy from the set MinMaxStrats((A (A) as defined in 5 that has the least number of best responses.
Proposition 7. As TT + co.
Reont (,, - AA)
2 Val(A) T [I(m) - 2 MMMMMMMxStttttt.rr
BR(("))) (1 + on)(1))
min
where (1) denotes terms that decays to O as 1)T ca, and BR(x) is the set of best responses of strategy x of the optmizer as defined in
Proof. Fix some A(A). Note that from Theorem 6 we have:
Ri (O,T,A,- -A) In (m) + e (eJATa
1 In xT
Mel -eT)A" " "T
1
1
for any j E [m]. Choose j E BR(x) (thus it minimizes e, ATx). x). Denote with d; x)) = (e, ex) A x. Note that for all [m// BR(x) we have d; 0 and for i & BR(x) we have
16

---

d,j,x) < O. We can rewrite this as:
Reone A, -A)
In (m)
+
A A oT
- In (IBR())+
1
Σ
"
1
6E/m]/ BR(x)
In (m)
1
+ 1 In (
E
LE m// BR(x) eTT.d:(i.))
+
9 A ATAT
xT
In ([B(()))
1+
17
77
BR(x)
In (m)
In 1+ E BR(a) efTidelii)) [RR(a]]
+
ej AT TT
In [R()))
1+
In(BB(xx))
17
Ia 1+ Exeimi mm/ BB())) (5
[[kk(]]]
Note that 1/7 + 00, the term this gives:
goes as d;( <
Therefore
In( BR(a))
In (m)
1
Roont (0,T,A, -A) >
+
e A.AATa
In ((BB(())((1+ o(r rT
7
Choosing MinMaxStrats. (A) that minimizes [R(x)] yields the desired result.
Below we provide example of game with multiple min-max strategies for the optimizer, however only one of them gives optimal rewards when used against MWU.
Example Consider the zero sum game where:
b1
b2
by
bn
ba+1
bn+2
b
61
n
0
Y1
02
0
0
0
03
0
71
0
Tt
A
:
:
ag
71
11
12
0.
2
0
0n+2 11
71 71 0
2
Notice that the Val(A) 1, and there are multiple strategies that achieve this result, that might have different number of best responses. For example (2 ...... 0, 0) has 1 best responses; BR(a1) {br, b2,...... bb.3)) One of the strategies that achieves the value of the game with the
least number of best responses is x² (0, 2+ 2 0) that has only best response, namely In(n+3)
BR(x") = (bn+3). For this game playing x" as TyT - oo yields Re (0, 0, A, - A) = T
B.2
Discrete Case
We can have the analogous definitions of optimal rewards for the optimizer for the discrete Given the sequence of actions of the optimizer given by x {I....,,)) T) - ((A), we can define:
mm Eisl (Me(0)))eT BJ Ei_, =(t)) e. A xx1))
Ratise (x. h(0), T, B)
(13)
Em (M((0))))) B EE_) *(+))
17

---

Again, we are interested in finding the sequence of actions that maximize the rewards:
ii (h(h(())+e
B' E. a(+)) A x((
Rasse (O),,,
max ((t))
(14)
E (he BT x
OSIST
We begin by proving that the rewards for the discrete game will always be more than the rewards for the analogous continuous game.
Proposition 8. In the zero-sum discrete game, the optimizer can receive more utility compared to the continuous game. This can be done by playing discretely the same optimal strategy x² forr the continuous game (as defined in Theorem 77. Consequently.
Beise A,
Reome AO,T,A,-A
(15)
Proof. From Theorem | we know that R (0, 0, A, -A) is achieved by constant strategy x' for the optimizer throughout the game, will prove that using that same strategy x" will yield more reward for the discrete case than the continuous case, i.e.:
11 A
e, AT
R A, A) N
E Di=l no ATx
i== no n0 ATx C.T.A AT x²
dt R (0,0, -A)
E v
A xtt
Em e n NTttiin AT=" E e noe Alass
All we need for the above to be true that the function f(t)
Emieers et is non-increasing. This is because Rdise (0, 0, A, -A) Reont (0, 0, A, -A)
ET f(t) 50' f(t)dt EtD (F(t) - f-t f())ds). so by proving is non-increasing we can
prove f(t) St f(s)ds. Therefore, all we are left with is showing that df(t) 0 for all > 0.
Notice that:
(()) - Em E e
Σ Ei e ett Gi m
)) <0 2imee e
+
(16)
D m i= e
which concludes the proof.
We continue by proving that there are instances of discrete games, that achieve reward for the yf optimizer approximately 2 more than the analogous continuous game in Theorem 9 that this difference between rewards in continuous and discrete games cannot be greater than nT Theorem IC
We also prove
2 in
Proposition 9. There is a zero game instance for which we have that
Ra (0, -A) Roont (0, T, A, -A) tanh (1) T
2
The above is achieved by taking the optimal strategy x" for the continuous game (as defined in 7 and playing it over discrete time.
Proof. Consider the matching pennies problem, where the utility matrices are:
b2
b
62
A =
a1
-1
B
=
02
02
Note that Val(A) 0, and MinMaxStrats, (A)
{(}, })), and BR
f)) 2. This gives
R (0, T, A, -A) 0. On the other hand, consider the sequence of actions of the optimizer for the discrete game to as follows:
[az. an
if t is odd otherwise
x011=
18

---

We claim that at round where t is odd, the learner will play (2. 12, while when is even, the learner will play (e"4e-m - Indeed, at = 1......... the optimizer will have played equal times the action a1 and d2, thus the rewards for actions b1 and by so far will be equal, leading the learner to play (3. 2). When t is even, action d2 has been played one more time than a1 is played. That means that at time for dj the historical reward 1, while the historical reward for b2 is -1. Thus Therefore the optimizer's
the strategy for the learner for even will indeed be o" reward will be:
T
1 -1
Rdiso (1),,,,,,
0
1
+
2940-7
-1
1
(17)
T
en
T
7/T
0
taanh (1)
(18)
2
e +
ea + -
2
Combining the two gives the desired result.
Proposition 10. In a zero-sum gume where the entries of A satisfy Aij E 11,, we have that the optimal utility the optimizer can achieve in the discrete game is not more than n/ compared the continuous game:
AA) R (0. A, - A) n/1/2.
Proof. Suppose the optimal strategy for the discrete game is Tdisc- We will construct a strategy Zcont for the continuous game, that approximates the utility of the discrete game pretty well. The strategy as follows; if (t) = Ze E (AA, then (c)nt(s) = 2t, Va E [t, + 1). Note that the historical rewards of the learner for / 0, 1, 2,,,,... ..... ,T - are the same for both the continuous and the discrete game for these specific strategies. Suppose the history at time is h(),, the strategy being played at time be v, and us = e, A x. We have:
Σ i=1
(t)) Ui == enh((())
Ry (h(t), A)
We also have:
-i=1 (t) -yaat U1
Roon (h(1), -A)
dt
(19)
i= (tht(())-must
Lis (1hg(())mmgg)))))))))
Denote by f(t)
Then,
th (0)
Risso (h(),,,, A) f(0).
whereas
R Ront (M(1), A,-) -)) = ['' S())dt
(20)
Note that:
(1(1) 7) Σ
|=1 (nh,(1)-
up
17 [ m -
m
b-1 (t)
maat
1 eak. (f))))))))
Since ut's are bounded by in [-1, 1], we get that ('(1) 2 -1. Hence f(1) 2 ʃ(0) - 17l, consequently,
Ri (h(1), 1, A, A) = { [(I)dt 2 S (S(0) nt = f(0) y/
Therefore summing up for all 1. = 1, 1
Ry (0, O, -A) R O,T,A, -A) S nT/2
We conclude with the last proposition of this section which states that in games that satisfy the following Condition, we get that the optimizer can achieve reward least 7 Val (A) + 2(77)) against MWU learner.
19

---

There exists minmax strategy z for the optimizer such that there exists two best responses for the learner, big E BR(x). which do not identify on support(z). Namely, there exists an action ag support(x) such that og Abi, + ag Ab
Condition 2.
Proposition 11. For any zerv-sum game A E [Raxx that satisfies Condition 7 7 E (0, and T E N, there exists an optimizer, such that against learner that uses MWU with step size 13, achieves utility of at least
TV)((A) + CATI,
where CA is a constant that depends only the game matrix A.
Proof. Let z, big ag be the strategies and actions guaranteed from Condition Since b and big are both best responses for 2, x Ae
Aeiz. By the Condition that there exists an action ag support(2) such that of Ae,, # C Aesg it follows that there exists two strategies r', xx" ((A) such that (a' + x²"/2
2, x' Ae,, >> x' Ae,, and z" Ae, xx Aerz. We propose the following strategy for the learner: at any odd time t. play x' and at any even time t. play r². We will prove that in iterations t and t + 1 the reward of the optimizer is at least 2 Val(A) + CAn by playing as described. Therefore, if we just sum up over all f, we will get the desired result. Now, fix some odd and we will lower bound the sum of utilities of the optimizer in iterations and t + 1:
xxt) T Ay(t) + xxt + 1) Ay(t + 1) = x' Ay(t) + x Ay(t + 1)
Denote u, = =x" Ae, and 2/2 x² Aeg, then
L Au(l) + x. T" Ay(t + 1) = Σ (1) + Σ (t 1). 1=1
Notice that
yi(l)e- np= Ab;
Ab;
nu:
(i + 1) Dラm1 (;(()e 10pa
-ppn Ab,
Σド= Vo (t(te-uuu
Therefore
Dy (t))) nm
(t) + Σ
ut + 1)=
Σ
utyi(t) +
(21)
j=1 Vs (t)e nuy
1=1
i=1
Notice that
u4 + 0.
(a' + x²))
2 Ac; = T Ae; 2 Val(A).
Hence, v²(1) 2 2 Val(A) un (1), hence the right hand side of Eq. is at least
(((t),++2al(44)
Σド= vi(t)e-me Tu Val(A)+ Σ (t)t,,
uayh (()e
e 1724
Σド= U)(t)e-nas may
1=1
The right hand side equals 2 Val(A) if O. We will differentiate it wrt 17 to get
d ( Σラ 1. (i(t)u,e
vuu -u:
(t(() nu
ET Σj Us(1)e Tui
(t) nos 2
dij
Σド=1 (t)e nus
== (D(e nHs
The right hand side equals the variance of a random variable, which we denote by Zn, such that
Pr[z, = u| = Σ
yiC 79
uGe
We obtain that the sum of utilities for the optimzer steps and / + is at least (A) S Var ddr Recall that we assumed that 1) S 1. Hence, we prove that there exists some constant C'A such that Var(Z, Zz) > CA for all r E [0, 1]. we will obtain that the sum of utilities in iterations t and 6+1 1 is at least 2 Val( (A) + C This will imply that the sum of utilities in iterations 1 through T is at least Val(A) + r/TCa/2, assuming that T even (if T odd then we can play a minmax strategy in the last round and get a similar bound). It remains to bound Var(Z,). Recall that b,, and b,2 are two best responses to z, and since Σ xii) = fz, it holds from the definition of MWU that yi, (t) and yig (t) are among the largest entries of y(t). Consequently, Vi, (t), Big (t) > 1/n. This implies that there exists some C 0 (that possibly depends on A and n.), such that for all r E (0. 1),
Pr[Z, = ). Pr(Z, ]sg] > C. Further, by Condition, ui, = xxT Abs, # x Abig Wig-
Consequently, there exists some CA > such that Var 2 CA for all r E (0, 1). This is what we wanted to prove.
O
20

---

C Computational lower bound
In this section, we present the full omitted proof of Theorem 4
Proof of theorem 4 We'll show a polynomial time reduction from OCDP to the hamiltonian ey- cle problem. Let n = [V] and m = El. Given an instance Iam = G(V, E), where V == {ui, ....... Jn J and E (ei...... em of the Hamiltonian cycle problem, stance of the OCDP problem as follows: the optimizer has m actions, denoted by A = {aI,..... am and the learner has 2n actions, denoted by B = {bI..... blyl, iim.:.................. .bn, J. The matrices A and B, which correspond to the optimizer and learner's 's utility matrices respectively are defined as follows:
create an in-
{ 1, if there exists u E V such that = (ez, u), i.c. is outgoing edge of node by
Ala;, by)
0.
otherwise
Ala;, bmyy = 0
0.1
jf 1 and Bu E V s.t. e, (U1, u), i.c. e, is an outgoing edge of node in if j # and Bu E V s.t. 6; = (ui, u). i.e. e an outgoing edge of node oy
4,
Bla,,byl
1,
if 3u E V such that e; = (u, Uy), i.c. es is an incoming edge of node vy
0,
O.W.
[0.85,
if Fu E V such that e = (uy, u). i.e. e is an outgoing edge of node ūj o.w.
Bla;, bio,
0.
Finally, we set k = T n 1, constructing the instance TOODP (A, B, m, 2n, k; T). We conclude the reduction by proving that Ham is a 'Yes instance if and only if TOCDP is a 'Yes' instance.
1. Ham = TOCDP Suppose we have a Hamiltonian cycle that visits vertices U1 = Uni Uug
Vn, Va.-1 Ua, U/. Suppose that edge Cp, connects Un, to UuL41* We will prove that the sequence of actions azy Opsr.... ap--1 , ap.. apa-1 = Ap, achieve reward exactly n++ for the optimizer. To prove that, is enough to argue that if the optimizer plays as we described above, the learner will respond with bu,, bwz:.... by.. b b Indeed, notice that Alap., 0m.] 1, Vi [n + 1]. since ép, an outgoing edge of Ung- therefore the optimizer will be getting reward 1 every round. Now, to prove that the learner best responds described, let us look the historical rewards of the learner. Suppose the rewards for each of the m = 2- | actions of the learner for rounds 1, 2, 2..... t 1 is denoted by lutt) = (hy (t), (t)()) fim (t), .... hin, (t)) R22". We will prove inductively that after rounds we will have h(t) = (t), where (t) is defined as:
0,
if [ =
H1
if < t S 0.1,
0.9,
ift = n n+ if
0,
(t,
1,
if ifl=i,i>l
3, ift
(0,
ift <
Ha., (t)
10.85, if 1 1.2.....
Notice that the cases f 1, are trivial; at = 1 everything equal to 0 since the learner has accumulated no reward yet. At time t = 2 we only update hin, + 0.85, h4 + -0.1, h + 1, thus giving us h22)) (2). Suppose that after some f rounds, where < S n rounds we have ht()) (t). After ap, is played by the optimizer, the learner has to update Din., - 0.85,,1 hy + 1
-3 and if < n we update h N -> 1 otherwise if = n we = 0.9. Either way, we get hi( + 1) = H 1). To complete the proof, note that for each I, given that the of the learner history is (I), best response for the learner is buy thus the sequence of actions app Opp...... Op.. 2 achieves reward n +
update In - -011
for the optimizer.
21

---

2. TOCDP = THam Suppose there is sequence of actions played by the optimizer that receive reward n + n + rounds, with actions Gp, apas............................ ap--1 prove that apps. sp1..... Sp. correspond to the edges of Hamiltonian Cycle starting from node V1 = i.e. edges : Cp., make a Hamiltonian Cycle, by connecting nodes vn = Mur Uugs.... Eun- We again denote the rewards of the learner for rounds 1, 1.2....,4e 1- with htt)) = (t) hn (t), Nin, (t),..., hn. (t)) E R
We will
Start by observing that the learner will play b1 at 1 as it the tie breaking rule, so the optimizer needs to play an action that achieves reward against that. Note that the way we constructed the utility matrix of the optimizer, the only actions that achieve reward against correspond to outgoing edges from vertex ei. So at t = 1, the optimizer is forced to play an action that corresponds to an outgoing edge of = 1. Suppose the first action of the optimizer is Opt. corresponding to the edge
Action
cp = (vi, Uoz).
Action at 1 = 2: The rewards of the optimizer will be updated as follows, after the
optimizer plays 4ps and the learner plays by:
0.1,
if i 1
H.(1) =
1,
if = U2
0,
0.85,
if==1
Hin (1)
0,
O.W.
We note that now new best response of the learner will be bag. Thus, the only way for the optimizer to obtain reward 1 for the second round is to play an action corresponding to an outgoing edge of node Uwz- Suppose the action the optimizer plays bp2- corresponding to an edge Ep = (Vag, ).s).
Actions at 2 < t < n: We will prove inductively that the first t < n - actions Opt...... Op. correspond to edges of the form Epi (Vwa. Pug)..... Ep. = (Vuy: Uue+i) where & Uj for 1 S i < j S. n, i.c. edges that define a simple path in the graph, starting from node v1. By playing actions in such a manner, the historical rewards of the learner will be of the form:
(Vur Vag), Epz
00
if
(t)+)= =
0.1,
i
00
ift
(t)
1,
ift= ift=i,i>]
if
(0.
if
Ho.. (1)
10.85, ift / 1.2.....:
We proved that the first actions correspond to edges of a simple path for 1 S 2. We assume for the inductive step that it is true for the first t < n actions app -.... ap of the optimizer. We will prove that the next action ap..1 by the optimizer corresponds to an edge Ey.41 that extends this simple path. Since the first t actions are corresponding to simple path, at round t + 1 the learner's 's historical rewards are going to be equal to H + 1). Note that the best response for the learner is going to be buc41 In order for the optimizer to gain reward 1 the t+ 1 I'th round, they have to be playing an action Opt+: for which cp.+1 is an outgoing edge of the node U Suppose the optimizer chooses to play ap-.1. where Ep-+: = (Vuss : Uus42), ), and 44+2 = i, for some 1 < < t + 1. At round ( + the optimizer will still have play an action that corresponds to an outgoing edge of Va,- However, after that, we will have hin., (1+3) = 1.70, which will make by, the best response. However, there is no action the optimizer can play against by, which they receive reward 1, making it impossible for the optimizer to obtain + 1 reward in n + 1 rounds. Thus the optimizer needs to play Cp++1 = (Var.. Per_a) ) and u,42 7 Wr, 1 E [t + 1). completing the inductive step. Since we also proved that the first 2 actions are forming simple path starting from vi, using the inductive step, we conclude that the first n actions have to correspond to simple path the graph starting from V1.
22

---

Actions at = n. 1: Suppose the last two actions of the optimizer are ap.. Opn--' We want to prove that Ep. (Uw,, U1), Cpn+s (U), u), where some node connected to u1. We know that the history of the learner at time i = n, as proven in the previous bullet point, as follows:
0.1,
if =1
Nu, (ni
1,
ffi=nii>
3,
0, if n 0.85, O.w.
bing, (n)
; = 1,2,.....
Note that the best response for the learner time n will be b Thus the optimizer will have to play an action dp, corresponding to an outgoing edge of vu..- Suppose Cp. = (Vi.. .). Assume * 1. Then the history updated to h - -3. 3, h1g - -2 Min.. + 0.85. Note that the best response is any action Dun; for which the optimizer cannot get reward 1 from. Thus if x o 1 it is impossible to get reward then the best response time n + will be b1 since the h1 (n + 1) = -0.1 + 1 = 0.9 > 0.85, and thus playing any action corresponding an outgoing edge of 2 will obtain reward for the learner that round.
1 every round. On the other hand, if z
I. Lastly, notice that the problem statement requests the entries of the weight matrix B to be in [0, 1]. While our construction have weights in [-4, 4], scaling and shifting all the entries by the same amount does not affect the identity of the best response.
2
5
Figure 1: Graph G
We will show an example of how we can make the reduction from Hamiltonian Cycle to OCDP. Imagine we have an instance of Hamiltonian Cycle that corresponds to the graph shown in [ and
we want to reduce to OCDP. Since we have [V] 5 vertices and E 7 edges, we instantiate
the following instance of OCDP: (A, B, n
[E), = V = 11+ 1), where
the actions sets are A [el (1,5), e2
(5, 2), e3 (1, 21,2),. e4 = (2, (2,4), (4, es = {M1, U2, V3, 044 05, Ving Vang: Ving Ving M.ng), and the utility matrices A and B shown in the tables below.
(4, 3), e7 = (3, 1)}
23

---

V1
02
V3
V/
VG
Vin
Ving
Ving
Vina
Vins
0
0
0
0
0
0
0
22
0
0
0
63
0
0
0
0
0
A
0
0
0
0
0
0
E5
0
0
C6
0
0
0
0
V1
2/2
03
24
125
Viri
Vina
Ving
Vina
Vint
C1
-1
0
0
0
0.85
0
0
0
22
0
1
-4
0.85
63
-1
0
0.85
0
0
0
B
0
-4
0
0
0
0.85
0
0
65
0
0
-4
0.85
66
-4
0
0.85
0
44
0
0
0.85
0
Notice that the only way for the optimizer to achieve reward [V] 6 following actions:
5
6 is
if he plays the
c 62, 64, c6, 67, 61
and the learner's actions the following:
Us, U4,
The following table shows the rewards history of the learner during this game:
21
122
V/
U/
Vina
V'na
U/r4
V/nas
t= 0
0
0
0
0
O
0
0
0
0
=
-0.1
0.85
0
0
8 t
-0.1
-3
0.85
0
0
0.85
r()
t
-0.1
-3
-3
0.85
0.85
0
0.85
1
-0.1
-3
0.85
0.85
0.85
0.85
1 1
0.11
-3
-3
-3
0.85
0.85
0.85
0.85
t=
0.9
-3
-3
-3
-3
0.85
0.85
0.85
0.85
0.85
0.8
-3
1.70
0.85
0.85
0.85
0.85
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? NEUR
Answer: [Yes]
Justification: The introduction and abstract accurately reflect the main scope of the paper. We have proof's for the propositions and theorems of the paper in the appendix.
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:
The assumptions made in each claim are clearly described in the statement of the claim. We discuss possible future directions section
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 sellsspeciiiationn 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: The assumptions are stated clearly in each theorem, lemma or proposition.
Full proofs what was omitted in the main section, are included in the appendix. 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 are 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not include any experiments.
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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be 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 reproducibility may be tricky in some cases, in which case authors are welcome 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 possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
26

---

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?
Question:
Answer: [NA]
Justification:
This paper does not include any experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... 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 the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/puullc//guu /otee//guudddeeeeoSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to 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 omitted from the script and why.
At submission time, 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/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
27

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. 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 are out of range (e.g. negative emrr 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: [NA]
Justification:
This paper does not include any experiments.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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 make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:////hhrrrppsccpcpeeeeeeeeee httprpp....ccpuuu........aacaaes
Answer: [Yes]
Justification:
The paper is compliant with the code of NeurIPS 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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a 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: Discussed the end of page 9.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not contain data models and therefore does not pose such risks.
Guidelines:
The answer NA means that the paper poses 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 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.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not any 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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.paaersstt paperswi thcode. cow/ datasets 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.
29

---

If this information is not 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 any existing assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
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 details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not include crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 NeurIPS Code of Ethies, 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: This paper does not include crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
30


Reviews:
[{"review_id": "tU7mBA5ZKv", "reviewer": "Reviewer_bLvs", "summary": "This paper outlines conditions under which, in repeated two-player zero-sum and general-sum games between a learner with an online learning strategy and an optimizer that knows the learner's strategy and utility function, the optimizer can learn a policy to achieve a higher average utility than the value of the one-shot game. For the two-player zero-sum game setting, assuming the learner selects actions following Replicator Dynamics in continuous time, this paper proposes an algorithm in which the optimizer can take a constant (over time) optimal strategy that provably maximizes its utility. In discrete time with the learner following a Multiplicative Weights Update (MWU) strategy, the continuous time optimal utility of the optimizer is shown to lower bound the discrete time optimal performance following the same strategy. For general-sum games, this paper proves a computational hardness result showing it is NP-hard to approximate the optimal utility for the optimizer against a Best Response learner. This is proven via a reduction from the Hamiltonian cycle problem.", "questions": "1. line 164: \"$i_1, i_2$ are defined in Proposition 4. - Should this instead be  \"$b_{i_1}, b_{i_2}$ defined in Assumption 1\" ? \n\n2. If I understand correctly, the reason why \"the learner would have to change actions frequently\" (line 153) for the optimizer to get a higher optimal utility, is so that the optimizer can exploit the gain by playing an optimal strategy at every time step? In this paper, for the discrete time dynamics, the learner's strategy is therefore assumed stochastic to ensure that the learner frequently changes actions. What would be the effect of assuming a stochastic learner in the continuous time case?", "limitations": "Yes, authors have discussed the limitations and potential future directions for their approach.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper does a good job at highlighting the motivating questions, and the main ideas of the proposed approach are in general clearly explained. The proof for the reduction from the Hamiltonian cycle was quite intuitively explained too, and I really appreciate it.  \n\n2. The theoretical contributions seem sound and relevant to the optimizer-learner setting in two-player zero-sum and general-sum games. Please note that I have not thoroughly checked the proof details in the appendix.", "weaknesses": "1. This paper primarily focuses on theoretical bounds on optimal utility and computational hardness guarantees for learning an optimal strategy for the optimizer against mean-based learners in the zero-sum and general-sum games. But there are no empirical evaluations of the proposed algorithms. In section 1.2 Related Work, authors point out prior work in contracts and auction design, which could also be broadly categorized as mechanism design. Some recent related papers (eg. [1],[2] ) have proposed experimental frameworks to analyze interactions in similar optimizer-learner frameworks, which could be referred to for similar experiment design with repeated games and bandit agents. \n\n[1] Guo, W., Agrawal, K.K., Grover, A., Muthukumar, V.K. and Pananjady, A., 2022, March. Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits. In International Conference on Artificial Intelligence and Statistics (AISTATS).\n\n[2] Banerjee, A., Phade, S.R., Ermon, S. and Zheng, S., MERMAIDE: Learning to Align Learners using Model-Based Meta-Learning. Transactions on Machine Learning Research.\n\n2. The connection to optimal control could perhaps be better motivated and explained.  \n\n3. Confusing notation that can be improved:\n- Line 255 and 256: Should it be $R_{cont}(x, h(0), T, A, -A)$ and $R^*_{cont}(h(0),T,A,-A)$?\n- Line 308: \"for each node $v_i$ of the graph, the learner has two associated actions $v_i$ and $v_i'$\" - the overloaded use of $v_i$ is confusing. \n- I might have missed it, but what is the relation between $h_i(t)$ and $h(t)$? Is it explicitly defined somewhere in the paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank  the reviewer and respond to the points raised by the review below:\n\n``In section 1.2 Related Work, authors point out prior work in contracts and auction design, which could also be broadly categorized as mechanism design. Some recent related papers (eg. [1],[2] ) have proposed experimental frameworks to analyze interactions in similar optimizer-learner frameworks, which could be referred to for similar experiment design with repeated games and bandit agents.''\n\nThank you for pointing out these papers. We will include them in the related work section in the new revision of our paper.\n\n``The connection to optimal control could perhaps be better motivated and explained.''\n\nThe optimal control paragraph is explaining how Theorem 1 can be derived using the HJB equation. The problem of strategizing against MWU can be viewed as a control problem where the system has some dynamics (in this case the dynamics of MWU), a utility function (the rewards of the optimizer), and the control which is the strategy of the optimizer. The HJB equation gives a partial differential equation that when solved gives the closed-form solution of Theorem 1. We included it because we think it might be helpful for thinking about the general sum case. The connection of optimizing against learners and control has already been discussed in prior work [24], yet from a different angle and they did not discuss the HJB equation. We will definitely include a more detailed explanation in the new revision of the paper.\n\n``Line 255 and 256: Should it be $R_{cont}(x, h(0), T, A, -A)$ and $R_{cont}^*(h(0), T, A, -A)$?''\n\nYou are right, this is a typo. We will fix it in the new revision.\n\n``Line 308: \"for each node $v_i$ of the graph, the learner has two associated actions $v_i$ and $v_i'$\" - the overloaded use of $v_i$ is confusing.''\n\nWe will use a different notation for the actions, thank you for pointing this out. \n\n``I might have missed it, but what is the relation between $h_i(t)$ and $h(t)$? Is it explicitly defined somewhere in the paper?''\n\n$h(t)$ is an $m$-dimensional vector and thus $h_i(t)$ is the $i$-th coordinate of that vector. We will make sure to include it in the definitions.\n\n``Line 164: $i_1,i_2$ are defined in Proposition 4. - Should this instead be $b_1, b_2$ defined in Assumption 1\" ?''\n\nYou are right, this is a typo. It should be \" ... where $i_1, i_2$ are defined  in Assumption 1 ...\", not in Proposition 4.\n\n``If I understand correctly, the reason why \"the learner would have to change actions frequently\" (line 153) for the optimizer to get a higher optimal utility, is so that the optimizer can exploit the gain by playing an optimal strategy at every time step? In this paper, for the discrete time dynamics, the learner's strategy is therefore assumed stochastic to ensure that the learner frequently changes actions. What would be the effect of assuming a stochastic learner in the continuous time case?''\n\nFirst of all there is a typo in that line (153). It should be \"the optimizer would have to change actions frequently\". Both in the discrete and the continuous dynamics the learner and the optimizer are allowed to play stochastically. To better understand what we mean by the optimizer having to change actions frequently take a look at Proposition 9, which exemplifies the main difference between the continuous and discrete time dynamics. It studies the game of Matching Pennies, both in  discrete and continuous-time. For the continuous-time dynamics, the best value the optimizer can get is $0$. This is a consequence of Theorem 3. However, for the discrete time dynamics, it is possible to get $\\Omega(\\eta T)$ reward for the optimizer. This is achieved when the optimizer switches actions all the time, and then it is possible to gain positive reward, as presented in the proof. Essentially, the main difference between the continuous time dynamics and the discrete time dynamics is that in the continuous case the learner changes the strategy smoothly and therefore cannot be exploited as we can exploit the discrete time dynamics. Intuitively, the learner is ``slower to respond'' in the discrete setting, hence a frequent change of actions from the optimizer could benefit the latter.", "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": "reBhd4rPLH", "reviewer": "Reviewer_dTMF", "summary": "The paper studies a control problem where an optimizer plays with a mean-based learner in a zero-sum or general-sum game. The problem follows a previous line of work that aims to understand how to play optimally with no-regret learners in repeated games. The paper shows several new results. For zero-sum games, an optimal algirithm is provided for a continuous-time setting, where the learner uses a MWU-like learning dynamic. The authors show that this algorithm, when extended to the discrete-time setting, results in an algorithm that guarantees the optimizer the value of the corresponding one-shot game. For general-sum games, the paper provides a negative result, showing that no FPTAS would exist for computing the optimizer's optimal strategy.", "questions": "- Does the reduction rely on a specific tie-breaking rule, or can the tie-breaking assumption be relaxed?\n\n- Is there any intuition why the result in Proposition 1 relies on the cardinality of BR(x)?", "limitations": "The authors addressed the limitations properly.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem studied follows a line of very well-motivated problems. Understanding how to play optimally with mean-based agents is very interesting.\n\n- The paper is overall technically sound and presents some solid results.\n\n- The zero-sum and continuous-time settings are interesting and look like reasonable choices for the problem. The paper presents non-trivial results for these settings.", "weaknesses": "- The informal statements of results in Section 1 could have been made clearer. The current presentation does not allow an easy comparison of results in different settings.\n\n- The results only apply to an MWU learner, not general mean-beased learners, and it relies on the knowledge of $\\eta$.\n\n- In the discrete-time setting, the algorithm only guarantees a lower bound. There is no matching negative result.\n\n- The negative result for the general-sum case only implies it is hard to get reward T-1, so it doesn't preclude the optimizer from obtaining sublinear regret overall. Moreover, fictitious play is a bit simplisitc as it is not no-regret. (However, I think the reduction itself is quite interesting.)\n\n---\n\nMinor:\n\n- It may be clearer to state Assumption 1 as a condition or a property. Stating it as an assumption may make it sound like your result requires additional assumption, while I think the purpose of Proposition 4 is more about showing the existence of games with a utility gap.\n\n- Line 362: closed form", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer and respond to the points raised by the review below:\n\n``The authors show that this algorithm, when extended to the discrete-time setting, results in an algorithm that guarantees the optimizer the value of the corresponding one-shot game.''\n\nThis is not exactly true. We show that for both the discrete and continuous time settings the optimizer can achieve on average more than the one-shot game. For the continuous time regime we show a closed-form solution (Theorem 3) for the rewards of the optimizer that is always more than $T \\cdot Val(A)$ (Proposition 1 / Proposition 6). Moreover, in the discrete game the optimizer can always achieve more rewards than in the analogous continuous game (Proposition 2 / Proposition 8) and we show that for a large class of games the 'gap' is $\\Omega(\\eta T)$ (Proposition 4 / Proposition 11).\n\n``The informal statements of results in Section 1 could have been made clearer. The current presentation does not allow an easy comparison of results in different settings.''\n\nWe will rewrite the statements more clearly and compare them to previous related work in the new revision.\n\n``The results only apply to an MWU learner, not general mean-beased learners, and it relies on the knowledge of $\\eta$''\n\nWe believe that our result could be extended to the case where $\\eta$ is not known in advance -- by an algorithm that learns $\\eta$ on-the-go. This was not the focus of our paper and it is left for future work. For optimizing against arbitrary mean-based learners, we do not know if there is a clean solution, and devising an optimal strategy against any mean-based learner might be a very hard research problem (as also discussed by Brown et al., ``Is Learning in Games Good for the Learners?'')\n\n``In the discrete-time setting, the algorithm only guarantees a lower bound. There is no matching negative result.''\n\nWe do provide upper and lower bounds, which are tight up to constant factors.\nProposition 4 proves that in discrete games, the optimizer cannot obtain more than $\\eta T/2$ reward compared to the continuous time analogue (Proposition 3 / Proposition 10). For the positive result, we show that there exists a game where this gain is optimal up to a multiplicative $1+o(1)$ (Proposition 3 / Proposition 9) factor. Furthermore, for a class of games satisfying a mild condition, we show that the optimizer can gain $\\Omega(\\eta T)$ more reward than the Value of the game in the discrete-time setting (Proposition 4).\n\n``The negative result for the general-sum case only implies it is hard to get reward T-1, so it doesn't preclude the optimizer from obtaining sublinear regret overall. Moreover, fictitious play is a bit simplisitc as it is not no-regret. (However, I think the reduction itself is quite interesting.)''\n\nBoth of your observations are correct; our reduction does not prove hardness of approximation of the optimal rewards, and also it is based on the assumption that the learner employs fictitious play (where $\\eta \\to \\infty$). However, we see this lower bound as a first step to possibly unlocking the mystery of the strategization against MWU, that was first introduced by [1] 5 years ago. Many other works (inclduing [2], [3]) have this left as an open problem, and we believe that this problem is computationally hard. Our hardness result is the first in this line of work and we are hopeful that in the future we will be able to prove hardness of approximation and relax the $\\eta \\to \\infty$ assumption. \n\n``It may be clearer to state Assumption 1 as a condition or a property. Stating it as an assumption may make it sound like your result requires additional assumption, while I think the purpose of Proposition 4 is more about showing the existence of games with a utility gap.''\n\nYou are right, the point is to show that a certain category of games have a utiity gap between their discrete and continuous time analogues. We will phrase the assumption as a condition instead, for the utility gap to exist.\n\n``Line 362: closed form''\n\nThanks for pointing the typo out.\n\n``Does the reduction rely on a specific tie-breaking rule, or can the tie-breaking assumption be relaxed?''\n\nYes, the reduction does rely on the specific tie breaking rule, that is only used however in the first round of the game where the historical rewards of the learner for each action is 0. We did not see a simple way to relax this tie breaking rule, and we leave relaxing this assumption for future work.\n\n``Is there any intuition why the result in Proposition 1 relies on the cardinality of BR(x)?''\n\nThe less best responses for the learner there are the longer it will take for the learner to converge from the uniform distribution to that best response. Imagine a game where every action of the learner is a best response; in that scenario the rewards for the optimizer will be exactly $T \\cdot Val(A)$. In comparison, in the case where there is only a single best response, the optimizer will gain extra utility because of the time it takes for the learner to learn that best response. The less best responses, the more time it takes to concentrate all the probability for the learner in the best responses and therefore the more utility for the optimizer.", "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": "6C7li2unwF", "reviewer": "Reviewer_jNhL", "summary": "The authors present a model where an optimizer plays with a learning agent and aims to extract better rewards from the sequential decision-making game by anticipating what the learner will do selecting a strategy that outperforms the value of a game. They study two settings: a zero-sum game, where they show a polynomial time algorithm that can extract an advantage for the optimizer, and a general-sum game, where they show the problem is NP-hard by reduction from the Hamiltonian cycle problem. They show that for a learner using Replicator Dynamics, the optimizer can get an advantage related to the time horizon by using a constant strategy.", "questions": "1. Can you justify why MWU and Replicator Dynamics are chosen as the model for the learner?\n2. Can you clearly state what the novel contribution of the paper is? My current understanding is that the hardness proof is novel, and the polynomial time algorithm for Zero-sum games is novel, and that is all.\n3. Can you clarify the undefined notation, e.g. \\Delta(A)?\n4. Why is so much exposition included in the Introduction? Is there a reason for this?", "limitations": "The authors don't specifically have a limitations section addressing the limits of the work, though they do propose future work building on the current results. The authors should address why only one model of the learner is considered, as that can be seen as a limitation.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The paper tackles the important problem of using information about other agents to maximize utility in two-player games. The authors present various theorems and proofs to show how strategies for the optimizer can be devised to gain an advantage. Further, they also show a novel hardness proof for the general-sum game by reduction from the Hamiltonian cycle problem, when playing against a mean-based learner.", "weaknesses": "My primary concern with this paper is in the organization and clarity of presentation. The authors do not contextualize and clearly state their results, or talk about the importance of their results. Further, a large portion of the theoretical information is included in the introduction, with various theorems being re-stated later on. Then, there is an awkward interlude with the related work section before continuing with the remaining theoretical analysis. This makes the paper very hard to follow, without any appropriate structure to guide the reader. I would expect a much shorter introduction, which introduces the problem setting and introduction without going into theoretical detail and summarizes the paper's contributions, following which related work or background for the problem is provided. In general, main Theorems and Propositions should not appear in the Introduction.\n\nSome important details which could be highlighted are missing from the body. For example, the authors don't clearly state the benefit that can be achieved in a zero-sum game by the optimizer, except for the informal statement of proposition 1. This seems to me one of the main contributions of the paper, other than the hardness proof.\n\nTheorems and propositions are referred to by multiple names and repeated. If possible, authors should use the same numbers for the same theorem or proposition. \n\nThe authors also focus only on the MWU and Replicator Dynamics models for the learner. However, there is no justification for why this model is chosen as opposed to any other kind of learner. The setting described is general, however all proofs rely on the learner using this model. Some discussion on why MWU and replicator dynamics are chosen will add to the concreteness of the paper.\n\nSome minor/specific comments below:\nIt would be helpful if n and m are described explicitly as the cardinality of the action spaces of the two players. As it is right now, it is easy to miss when they are first introduced, and later equations (e.g. Eq. 1) rely on the readers knowing what they stand for.\n\nWhat is \\Delta, as used in the definition of the value for zero-sum games? It seems to be used as a function, but it isn't clear from the context what it is supposed to be. This same notation is used in line 163, which suggests \\Delta(A) might be a set?\n\nLine 164: i1, i2 are not described in Proposition 4.\n\nThe replicator dynamics is defined as a continuous time analogue of the MWU algorithm, but the MWU algorithm itself is not described until later in the paper. This can be confusing for readers, if MWU is not being used, then it should not be introduced earlier. If Replicator Dynamics needs to be described as a generalization or adaptation of MWU, MWU needs to be described first.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. We answer below the main concerns, and we answer additional questions in an official comment, due to the space limitations. \n\n``My primary concern with this paper is in the organization and clarity of presentation...'':\n\nWe thank the author for their comment about the presentation. We note that in theory papers it is common to have an informal version of the theorems in the introduction, followed by a longer version in the technical sections. Yet, we will change the format in accordance to the reviewer's comments, and we agree with the reviewer that such a change can benefit the paper. Specifically, after the meta question, we will summarize in bullets the main contributions of the paper. Related work will follow. Then, we will write the preliminaries, and afterwards the results, in two sections: (1) optimizing against MWU and (2) a lower bound for optimizing against Best-Response. These will include results that currently appear both in the introduction and in sections 2 and 3.\n\n``Some important details which could be highlighted are missing from the body. For example, the authors don't clearly state the benefit that can be achieved in a zero-sum game by the optimizer, except for the informal statement of proposition 1. This seems to me one of the main contributions of the paper, other than the hardness proof.''\n\nWe state the benefit through theorem 1 and propositions 1 to 4 in the introduction. First of all, theorem 1 states that the optimal rewards for the optimizer can be achieved with a strategy that is constant over time (i.e. $x(t) = x^*, 0\\leq t \\leq T$). In proposition 1 we state exactly the range of possible rewards the optimizer can achieve and what happens when $\\eta T \\to \\infty$. In propositions 2-4 we explain what happens in the games with discrete time dynamics. First of all, the discrete time analogue of a continuous time game will always give more rewards for the optimizer (Proposition 2). This 'gap' in the rewards cannot be more than $\\eta T/2$ and there exists a game that approximately achieves this gap, namely matching pennies (Proposition 3). Lastly, we show that up to constant factors, most games also exhibit this reward gap between the continuous and discrete game analogues (proposition 4).\n\n``Can you justify why MWU and Replicator Dynamics are chosen as the model for the learner?''\n\nWe chose the MWU algorithm for the learner for several reasons. First of all, it is one of the most well-studied no-regret algorithms due to its optimal regret but also as its continuous time analogue, the replicator dynamics, is extremely well studied in the literature. MWU is also an algorithm that is widely used in online learning settings, therefore knowing how robust or manipulable it can be against strategic players in online settings is an interesting question. We also believe that our view of the problem as a continuous time problem, provides a new perspective on how to view the problem of strategizing against mean based learners (as introduced by [1]).\n    \n``Can you clearly state what the novel contribution of the paper is? My current understanding is that the hardness proof is novel, and the polynomial time algorithm for Zero-sum games is novel, and that is all.''\n\nAll of the results in our paper are novel, and are the following:\n\n(1) The first set of results concerns zero-sum games where the learner is employing Replicator dynamics (for the coninuous case) and MWU (for the discrete case), as summarized in (1a) and (1b) below:\n\n(1a) We show what is the exact best strategy for the optimizer against a replicator dynamics learner in the continuous time setting by presenting a closed form solution (Theorem 1). We show that this strategy can be efficiently computatble using optimization methods (Proposition 5) and we give a range of possible values that this optimal reward can take (Proposition 6). We also examine what happens in the limit when $\\eta T \\to \\infty$ (proposition 4 and 7).\n\n(1b) For discrete-time games, we show that the optimizer can always get more than the analogous continuous-time game (Proposition 2 / Proposition 8). This gap in the reward cannot be larger than $\\eta T/2$ (Proposition 10) and we show a game that achieves that gap almost exactly (Proposition 9). Finally we show that under a condition, there is a large class of games that exhibits this gap between the continuous and discrete time games (Proposition 3 / Proposition 11).\n\n(2) The final result we show is a first computational lower bound for computing the optimal strategy against learners and specifically, against Fictitious play.", "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": "HEzuu3EQhZ", "reviewer": "Reviewer_PJLW", "summary": "- The authors consider the problem of optimally exploiting a learning agent in zero-sum games and general-sum games.\n- For zero-sum games, they look at a specific continuous time learner, replicator dynamics, and at an analogous discrete time learner, multiplicative weights updates. They provide an explicit expression for optimal utility of the exploiter agent in the continuous case, as well as a construction for a polynomial-time algorithm that achieves that utility.\n- In the discrete case, they show that the discretized optimal strategy from the continuous case achieves at least as much utility. Moreover, they show that this utility can be exceeded, and they bound this difference between the continuous and discrete cases from below and from above.\n- In the context of general-sum games, the paper shows that determining the optimal utility of the exploiter against a Best Response Algorithm (in discrete time) is NP-hard.\n- The paper concludes by discussing open problems, in particular whether there are some learners and classes of general-sum games where one can say more about the optimal utilities for polynomial-time optimizers.", "questions": "- I wonder whether it would be possible to give a description of the constant optimal strategy in the continuous-time case, in words. How does it relate to the minimax strategy? I assume that even as $T\\rightarrow \\infty$, learners play suboptimally if the temperature $\\eta<\\infty$, and so the optimizer would deviate from the minimax strategy somewhat to exploit this. However, is it right that for $\\eta\\rightarrow \\infty$, the optimizer strategy would eventually converge to the minimax strategy?\n- Line 106: Should it say \"$\\eta\\rightarrow \\infty$ as $T\\rightarrow \\infty$\"?\n- This work relates to empirical ML work in which learners are gradient based and exploitative strategies are found via meta optimization (see e.g. model-free opponent shaping, https://arxiv.org/abs/2205.01447, and follow up work)\n- Could you say under what conditions the constant $C_A$ in Proposition 4 is small? Does this depend on the inequality in Assumption 1? (i.e., if the two best responses lead to very different utilities, this leads to more possibility of exploitation?)\n- Typo on line 350: \"The details the force the learner\"\n- In the related work section, it would be nice to better contrast the discussed related work (especially on no regret learners) to the work in this paper. E.g., MWU is also a no regret learner, but best response isn't? How exactly does this paper extend prior work on exploiting these different learners? E.g., by analyzing computational complexity, or by providing tighter bounds, etc.?", "limitations": "The authors adequately address limitations.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper makes a significant contribution by analyzing the general setting in which an optimizer is trying to exploit a mean-based learner. In my view, both the impossibility result in the general case as well as the characterization of the zero-sum case are conceptually interesting.\n- The mathematical analysis appears sound and rigorous. The paper discusses an interesting connection to optimal control. (Though I have not checked the proofs in the appendix and this is not my main area of expertise).\n- I found the paper was well written and well motivated.\n- I appreciated the discussion of societal impact. I agree with the authors that this work is relevant since it is important to study how exploitable commonly used learning algorithms are.", "weaknesses": "- The paper doesn't include any empirical simulations. It would have been interesting to see some example numerical computations of the optimal strategy in a game and resulting simulated utilities. How much better does the optimal strategy do compared to simple baselines, in some canonical games?\n- Focusing on MWU and related algorithms makes sense to make the analysis tractable, but it also limits the applicability of the results. Moreover, it would be especially interesting to have an impossibility result for a no regret algorithm.\n- While the computational hardness result is interesting, it does not appear very surprising given typical hardness results in game theory.\n- While I found that the authors generally explained their approach well, I thought it might have been interesting to give some more explanation, potentially via a concrete example (in the zero-sum case). If this takes up too much space, one could include an example in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the useful comments. We answer the main questions below, and move a few minor questions to an official comment, for space considerations.\n\n``It would have been interesting to see some example numerical computations of the optimal strategy in a game and resulting simulated utilities. How much better does the optimal strategy do compared to simple baselines, in some canonical games?''\n\nWe are happy to include examples of games and the optimal rewards and strategies of the optimizer for different time horizons $T$ in the new revision of the paper.\n\n``Focusing on MWU and related algorithms makes sense to make the analysis tractable, but it also limits the applicability of the results. Moreover, it would be especially interesting to have an impossibility result for a no regret algorithm.''\n\nEven understanding what happens against specific types of algorithms such as MWU is an elusive open problem (look at paragraph 2 of page 3 of Is learning in games good for the learners), but also understanding what the optimal strategies are against these algorithms will be helpful for the analysis against other no-regret learners. You are right, an impossibility result for no-regret learning algorithms would be extremely interesting, and we leave it open for future work.  \n\n``While the computational hardness result is interesting, it does not appear very surprising given typical hardness results in game theory.''\n\nA lot of results in game theory are impossibility results (such as for example computation of several types of equilibria in different games). However, our impossibility result is the first of its kind, as far as we know. That is, our result is the first that states that computing optimal strategies against learners with specific dynamics can be computationally hard, and none of the previous work has talked about any computational issues thus far.\n\n``I wonder whether it would be possible to give a description of the constant optimal strategy in the continuous-time case, in words. How does it relate to the minimax strategy?''\n\nAs $\\eta T \\to \\infty$ then the optimal constant strategy will approach a min-max strategy. However, for finite or small $T$ the optimal strategy might be different, depending on the game.\n\n``I assume that even as $T\\to \\infty$, learners play suboptimally if the temperature $\\eta \\to \\infty$, and so the optimizer would deviate from the minimax strategy somewhat to exploit this. However, is it right that for $\\eta \\to \\infty$, the optimizer strategy would eventually converge to the minimax strategy?''\n\nIf $\\eta \\to \\infty$ then the learner is essentially employing fictitious play (best responding to the history). When $\\eta \\to \\infty$, the optimizer is able to take advantage of that by significantly deviating from the min-max strategy. This can also be seen in the way we analyze the computational lower bound and specifically you can view it in the example we provide in the last pages of the paper (p22-23). There, optimizer constantly changes the actions they are playing. The phenomenon where the optimizer has to constantly switch actions can also be seen in the matching pennies example that we also discuss in the paper (Proposition 9). It certainly is the case for matching pennies that the average-time strategy for the optimizer in the scenario where $\\eta$ is large will converge to the min-max strategy, however, the per-round strategy is not. It is an interesting question we have not tackled whether the average-time strategy always converges to the minmax strategy.\n\n``Could you say under what conditions the constant $C_A$ in Proposition 4 is small? Does this depend on the inequality in Assumption 1? (i.e., if the two best responses lead to very different utilities, this leads to more possibility of exploitation?)''\n\nYes, this depends on the inequality in Assumption 1. If the assumption is close to being unsatisfied, then the constant is small. If the assumption is satisfied with a large gap, then the constant is larger, which implies a better lower bound on the utility gained by the optimizer.\n\n``In the related work section, it would be nice to better contrast the discussed related work (especially on no regret learners) to the work in this paper. E.g., MWU is also a no regret learner, but best response isn't? How exactly does this paper extend prior work on exploiting these different learners? E.g., by analyzing computational complexity, or by providing tighter bounds, etc.?''\n\nThanks for the question. Previous work has introduced the problem of strategizing against no-regret learners, and specifically mean based learners. It has also been shown that in zero sum games against these mean based learners, the best rewards the optimizer can achieve are $T \\cdot Val(A) + o(T)$, while in general sum games, it has been shown that the optimizer can get significantly more utility than the one shot game value (which for general sum games is called the Stackelberg value), however no efficient algorithm on how to achieve this value has been found. In our work, we show for zero-sum games what is the exact optimal rewards for the optimizer for Replicator dynamics - one of the most widely used mean base learners. We also show a first computational lower bound for computing the optimal strategy against a learner that is best responding, i.e. MWU with infinite step size. We believe that ultimately the problem of computing an optimal strategy against mean based learners in general sum games is computationally hard, and we give a first result with our lower bound towards that direction. We will add these details in the related work section.", "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:

Meta-review: The paper examines a two-player repeated game setting involving two types of players: one is an online learner, while the other is a planner who accounts for the learner's behavior when optimizing their strategy. Overall, the reviewers found the problem studied and the characterization results concerning the exploitability of a mean-based learner interesting, and the corresponding analysis sound. However, concerns were raised about the quality of the presentation. While the format is not atypical for a theoretical paper, there is room for improvement. The authors are strongly encouraged to address these concerns and revise their paper according to the suggested edits in their rebuttal.
Decision: Accept (poster)