Learning to Steer Learners in Games
Authors: Yizhou Zhang
Yian Ma
Eric Mazumdar
Venue: ICML 2025 poster (2025)
Keywords: Learning in games
steering
Primary area: theory->game_theory
TL;DR: We consider the problem of learning to exploit learning algorithms through repeated interactions in games.

Abstract: We consider the problem of learning to exploit learning algorithms through repeated interactions in games. Specifically, we focus on the case of repeated two player, finite-action games, in which an optimizer aims to steer a no-regret learner to a Stackelberg equilibrium without knowledge of its payoffs. We first show that this is impossible if the optimizer only knows that the learner is using an algorithm from the general class of no-regret algorithms. This suggests that the optimizer requires more information about the learner's objectives or algorithm to successfully exploit them. Building on this intuition, we reduce the problem for the optimizer to that of recovering the learner's payoff structure. We demonstrate the effectiveness of this approach if the learner’s algorithm is drawn from a smaller class by analyzing two examples: one where the learner uses an ascent algorithm, and another where the learner uses stochastic mirror ascent with known regularizer and step sizes.

Learning to Steer Learners in Games
Yizhou Zhang'
Yian Ma
Eric Mazumdar'
Abstract
opponents' objectives), and on the other, they must reason strategically about the game-theoretic implications of its actions to maximize utility. Thus, the problem becomes trading off between exploration and competition.
We consider the problem of learning to exploit learning algorithms through repeated interactions in games. Specifically, we focus on the case of repeated two player, finite-action games, in which optimizer aims to steer no-regret learner to a Stackelberg equilibrium without knowledge of its payoffs. We first show that this is impossible if the optimizer only knows that the learner is using an algorithm from the general class of no-regret algo- rithms. This suggests that the optimizer requires more information about the learner's objectives or algorithm successfully exploit them. Building this intuition, reduce the problem for the optimizer to that of recovering the learner's 's pay- off structure. We demonstrate the effectiveness of this approach if the learner's s algorithm is drawn from a smaller class by analyzing two examples: one where the learner uses an ascent algorithm, and another where the learner uses stochastic mir- ror ascent with known regularizer and step sizes.
To address this problem, the dominant approach to learning in games has been formulating as an adversarial online learning problem. In this framing, with unknown objectives and learning rules, each player assumes they are faced with an arbitrary (and potentially adversarial) sequence of payoff's and seeks to find an algo- rithm that maximizes their own utility. Given this setup, a natural class of algorithms to choose from is the class of no-regret algorithms, which guarantees asymptotically optimal performance compared the best fixed action in hindsight (Cesa-Bianchi & Lugosi, 2006). all players use no-regret algorithms, it is well known that the average action of the players over the entire time horizon converges to (coarse) correlated equilibrium (Foster & Vohra, 1998; Hart & Mas-Colle MoleC,,,ll, 2000). However, since the opponents are also learners rather than adversaries, adopting a no-regret algorithm may not be optimal.
handle opponents
In this paper, we seek to understand how one player should deviate from choosing a no-regret learning algo- rithm in games. We focus on simplified abstraction of this problem-the repeated two player games with finite actions, in which each player only knows their own utility function (i.c., their payoff matrix), but not their opponent's.
1. Introduction
Learning algorithms and Al agents are increasingly being deployed into enviromments where they interact with other learning agents-be they people or other algorithms. This is already a reality in wide-ranging application areas such as ad auctions, self-driving, automated trading, and cybersecurity. In each of these problem areas, the presence of other agents with potentially misaligned objectives renders the problem game- theorretc in nature. Algorithms deployed in such environments are therefore faced with a generalization of the classic exploration-exploottaioo trade-off in online learning: On one hand, they must take actions to learn the underlying structure of the game (i.c., its payoff and potentially its
This problem has been well studied in recent though primarily in the where the payoff matrix, and thus the objective of the opponent player, is known. Under such assumptions, it was shown in (Deng et al., 2019) that if one player (the optimizer) deviates from using a no-regret algorithm, it can (under mild assumptions about the game instance) guarantee an asymptotic average payoff that is arbitrarily close to the Stackelberg value of the game by steering the no-regret player (the learner) the Stackel- berg equilibrium of the underlying matrix game. This is the highest attainable value if the optimizer plays one fixed mixed strategy. Further studies have focused on analyzing the steerability of smaller classes of algorithms, such as no-swap-regret (Brown et al., 2023) or mean-based algo- rithms (Arunachaleswaran al., 2024). providing more insights into steering no-regret learners. Crucially, all
DDeparmeent of Computing & Mathematical Sciences, Califor- nia Institute of Technology. Pasadena, CA 91 125, USA HHllecoolu Data Science Institute, University of California San Diego, La Jolla, CA 92093, USA. Correspondence to: Yizhou Zhang syzhang&@caltec..ddu
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning to Steer Learners in Games
these works assume knowledge of the learner's objectives- knowledge that the optimizer itself may not even have.
no more than (T) steps, the optimizer is able steer the learner the Stackelberg equilibrium and conse- quently (asymptotically) achieve its Stackelberg value by using an applore-tenn-comii style algorithm.
In real-world applications, instead of knowing the entire game (i.e.. knowledge of both payoff matrices). it is often the case that each player only knows their own payoff matrix. Despite this, few works have studied the setting where the payoff structure of the learner initially unknown (or only partially known) to the optimizer. Thus, in this work we focus on answering this question:
Building on the previous result, we show by two con- crete examples that, when some information about the learner's 's update rule is known, it is possible to learn the learner's 's payoff structure and thus to steer them to the Stackelberg equilibrium. One example assumes the learner only has two pure strategies and is using any ascent algorithm where its payoff increases at cach step and the other assumes that the learner is using stochas- tic mirror ascent with known step sizes and regularizer. We note that most existing no-regret algorithms share similar dynamics with these two cases.
Without full knowledge of the game, can an optimizer learn to steer no-regret learner to an (approximate) Stackelberg equlilibrium?
As will show, crucial question that emerges from study- ing this problem is the learnability of the learner's 's objective through repeated interaction. Giving rise to the second main question that we answer:
2. Related Works
What information does the optimizer need in order to achieve this goal?
Before presenting our results, we discuss relevant related works.
1.1. Our Contributions
Steering no-regret learners. The problem of steering a no-regret learner in a repeated game has been the focus of several recent works, though often under strong assump- tions on what information is available to the optimizer. As- suming known learner payoff's Braverman et al. (2018) first introduced the problem of steering a learner in an auc- tion setting. Subsequently, Deng et al. (2019) showed that the optimizer can guarantee at least the Stackelberg value against the learner in bimatrix games and Assos et al. (2024) studied the problem of utility maximization under the ad- ditional assumptions on the learner's s algorithm. Brown et al. (2023) also focused on smaller classes of no-regret algorithms such as no-swap-regret, anytime no-regret and no- no-aaaptivv-regret algorithms. While sharing a similar goal with our work, all of these works use the known learner payoff to design steering algorithms, which is not available in our setting. Without the knowledge of learner payoff, Brânzei et al. (2024) showed the steerability of the learner in a cake-cutting model, which can be viewed as a 2D spe- cial case of our problem. Lin & Chen (2024) proposed principal-agen framework and studied the optimal average utility that can be obtained by the optimizer assuming ei- ther no-regret or no-swap-regret algorithm under known learner payoff. There is also a broader line of works regard- ing more general properties of interacting with no-regret learners, including (Zhang et al., 2024) that considered the stecring problem through direct payments to the learner and (Anumachaleswaran et al., 2024) that studied the problem of pareto-optimality in the space of learning algorithms.
We answer both questions in the setting of a repeated two player bimatrix game over a fixed (but assumed large) time horizon T. Our results can be summarized as follows:
We provide a negative answer to the first question. More specifically, we show that when the learner's pay- off matrix is unknown, no matter what algorithm the op- timizer uses, there exists a no-regret algorithm for the learner that prevents the optimizer from achieving its approximate Stackelberg value. This happens because the optimizer cannot accurately learn the learner's pay- off. This result suggests that we cannot hope to design an algorithm that asymptotically achieves the same performance as the Stackelberg equilibrium against all no-regret algorithms and all payoff matrices of the learner. This highlights a fundamental difference from the case where the learner's 's payoff is known-wherr the asymptotic Stackelherg value is attainable-dur to the lack of information.
Given the impossibility result above, we shift our fo- cus to what information is needed to steer the learner. We show that in order to achieve asymptotic Stackel- berg value, instead of exactly recovering the learner's payoff structure, it suffices for the optimizer first obtain reasonably accurate estimation of the payoff matrix (or equivalently, the best-response structure) through some learning method and then incorporate the idea of pessimism to steer the learner to the Stack- elberg equilibrium by leveraging its no-regret nature. We show that as long as the estimation process takes
Learning in Stackelberg games. The problem of steering is closely related to the problem of learning to play a Stack-
2

---

Learning to Steer Learners in Games
elberg equilibrium through repeated interactions. Thus, a particularly related line of work involves learning in un- known repeated Stackelberg games, where the decisions are made sequentially in each round. This problem has been well-studied in its own right but often under simplify- ing assumptions on the games or the responses of the fol- lower (the learner in our framing of the problem). Letchford et al. (2009) and Peng al. (2019) proposed algorithms for learning through interaction with a myopic responinngn agent, and Haghtalab et al. (2022) extended this framework to non-myopic agents with discounted utilities over time a different setup from the one we consider. Other works have analyzed similar problems under different assumptions on the underlying game. In the control literature, Lauffer et al. (2023) studied the problem of learning in dynamic Stackelberg games and showed that one could learn the Stackelberg equilibrium. Maheshwari et al. (2024) stud- ied a similar problem of learning Stackelberg equilibria in the context of continuous games; Goktas et al. (2022) stud- ied the behavior of no-regret learning in a smaller class of zero-sum Stackelberg games, and the problem of steer- ing learning agents has also emerged in the literature on strategic classification (Zrnic et al., 2021). In each of these problems, the additional structure introduced into the games simplifies the task of learning the Stackelberg equilibrium through e.g., convexity or smoothness of the underlying optimization problem. Unfortunately, in bimatrix games, the Stackelberg optimization problem is both highly non- convex and discontinuous, vastly complicating the task of learning Stackelberg equilibria. Learning in Stackelberg games has also been studied in various application areas including security (Blum et al., 2014; Balcan et al., 2015), calibration (Haghtalab et al.. 2023) and learning with side information (Harris et al., 2024). Most results proposed in these works assume the follower uses (nearly) myopic best response dynamics, which does not fit into our setting.
siders (and leverages) the learning behavior of other agents to achieve higher payoff and more stable learning process (Foerster et al., 2018; Lu et al., 2022).
3. Notations and Preliminaries
Throughout this paper, we use Am to denote the probability simplex in R We use [m] to denote the set {1. .................... ..m.. and (24))-_ to denote the set { 22..:2...... ......................... TT),
We use e, to denote the i-th one-hot vector, whose j-th element is 1i = j). We use || ||a, || ol to denote the In and T norm of a matrix/vector, and || Ilmax to denote the max norm of a matrix, which is given by the maximum absolute value among all entries. We use 02 and In to denote the all-zero and all-one vectors in R respectively. For two vectors a, b E R", a S b indicates a; S b,, Vi E [m]. For matrix M. Mc, (and abbreviation M,) denotes the i-th row of M and M.j denotes the j-th column of a matrix. As an extension, we use Mz,: (and abbreviation Mz) and Ma,5 to denote the matrix obtained by combining the rows in an index set I (columns in an index set J) respectively, and MI.J similarly denote the matrix obtained by choosing rows in I and columns in J. For index set I, let IA denote the i-th element in I.
3.1. Problem Setup
We consider a repeated general-sum bimatrix game G with two players, referred to as P1 (the optimizer) and P2 (the learner). There are T rounds of repeated interaction, in each round f, P1 and P3 play mixed actions I2 E Am and Y/ E A, simultaneously. We use A, B E RmX*n to denote the payoff matrices of P1 and P2 respectively, thus their utility in round could be written as x!. Aye and x! By,-
Within the interaction process, players use algorithms to decide the action they play. An algorithm takes the interac- tion sequence {x7, Vr 1t1 as input, and outputs the actions 2, (for Pi) or y (for Pz). We allow the algorithm of each player to be randomized, and the goal of each player is to obtain a higher expected total utility across all time steps, which can be written as:
Other related works. Several other relevant works do not directly fit into either 'steering' or 'learning'. Conitzer & Sandholm (2006) first proposed an efficient algorithm of computing Stackelberg equilibria when the game is known through solving and combining several small linear pro- grams, motivating our steering approach based on payoff matrix recovery. Gan et al. (2023) studied the notion of robust Stackelberg equilibrium allowing the follower to respond with any 5-optimal response. Despite being formu- lated differently, this shares the same high-level idea with our approach of inducing pessimism to steer learners. Col- lina et al. (2024) considered the setting of finitely repeated Stackelberg games where the leader commitments and fol- lower actions are adaptive to the gameplay history and pro- posed an efficient algorithm for approximating Stackelberg equílibria in the space of adaptive game playing algorithms. There are also works from an empirical perspective that con-
U(P)) - E ET
of Av U(()) = E :
[ of Byb
3.2. Regret and No-regret Algorithms
Given a fixed sequence of actions {#x)T= played by PI. a natural metric of the performance of Ps is the regret, which compares to the best action in hindsight. We define three forms of regret, one regret associated with trajectory, one incurred by an algorithm, and one incurred in a game.
Definition 3.1. Given an interaction history {at, y1 1T
3

---

Learning to Steer Learners in Games
the learner regret of P2 on the trajectory is defined as:
If the optimizer simply commits to fixed action and the learner best-responds, the choice that maximizes its utility should yield Stackelberg equilibrium:
T
T
Regz((zz; M1 )1 = max yEAR
Jt
By
Jt Byt. (1)
Definition 3.4. An action pair (a*, is a Stackelberg equilibrium if it is a solution to the following optimization problem:
Given a sequence of optimizer actions {xe )T the learner regret of P2 under the learner algorithm A2 is defined as:
maximize
AyAy
(4)
T
T
subject to y E BR(B,B),, E Am.
(e2 (xx))m))
max VE
T Lt
By-BBye
A2
T By It
The Stackelberg value for P1 is defined the optimal value of (4), denoted by B),
Given the optimizer algorithm A1 and the learner algorithm A2, the learner regret of P2 is the expected learner regret under A2:
Notice that in general, the set BR(B,z) contain more than one element. This would yield potentially different Stackelberg values among the best-response set. We use the rule of optimistic tie-breaking to adopt the one with the highest optimizer payoff among all best responses to define the Stackelberg equilibrium. However, we do not impose the assumption that the learner will also use optimistic tie- breaking when deciding between indifferent actions.
(e, = B( Reg2 (1 Me F1=1)
The learner would like to choose an algorithm that achieves a low regret on different possible optimizer trajectories {z.)²=z. while being flexible to prevent the optimizer from efficiently learning its payoff matrix. Faced with such trade- off, the learner may set a regret budget f. and aim to act against possible optimizer exploration strategies while keep- ing its regret under this budget. To better characterize these circumstances, we make the following definition of fine- grained no-regret algorithms:
Since the Stackelberg value is the highest possible average- reward it can get through fixing action among all time steps, we use Stackelberg regret to measure its performance:
Definition 3.5. Given an interaction history { Yr ) the Stackelberg regret of P1 is:
Definition 3.2. Given some function f N - IR such that S(T) = oT') and an optimizer action sequence { an interaction sequence {st, 31 )= is f-no-regret for the learner (with constant C) if
T Σ
Stack (er. Be = T. V(A,
x
A
Given the optimizer algorithm Ag and the learner algorithm A2, the Stackelberg regret of P1 is the expected Stackelherg regret under A1,
Rega(f F,, Ve VT C f(T)
(2)
for some constant C, a learner algorithm A2 is f-no-regret
(with constant C) on {x=)T=_1 if
StackReg (AI,AA)
(5)
:= B (ar.e Ai. Stack D
Reg2(A2, fz 1T CC-
(3)
for some constant C as T + co. An algorithm is f-no- regret if it is f-no-regret on all possible optimizer action sequences. An algorithm is no-regret if it is f-oo-regret for some (T) = (T)).
In the following sections we build upon these preliminaries to study the problem of steering the learner to the Stackel- berg equilibrium. For brevity and ease of exposition, we defer all proofs the Appendices.
3.3. Stackelberg Equilibrium and Stackelberg Regret
4. Impossibility of Learning to Steer Agents Who Use General No-regret Algorithms
Consider a simple optimizer strategy that plays a fixed action x at each time step, if the learner wants to be no-regret on the resulting trajectory, its action sequence {yx {y=) will converge to a best response to x, defined as:
When the learner payoff matrix B is known to the optimizer, Deng al. (2019) proved that under mild assumptions, there exists an optimizer algorithm Ad that guarantees a Stack- elberg regret of at most Stack A2) S <T + o(T) for an arbitrarily small constant e. However, if the optimizer doesn't 't have full knowledge of B, extracting Stackelberg value becomes harder. It is natural to wonder if we do not impose any extra assumptions (other than being no-regret)
Definition 3.3. For an action x of Pt, the best response of
Ps given its payoff matrix B is the set of actions maximizing its payoff:
BR B, x) = {u An .Tyy 2 T By Vy' E An).
4

---

Learning to Steer Learners in Games
on P2. is it still possible for P1 to learn the payoff structure of P2 through the interaction process and thereby extract the Stackelberg value for all possible game instances? The following result shows that this is impossible in general:
5.1. Facets and Equivalence Classes of Payoff Matrices
From the optimizer's perspective, the matrix B does not di- rectly show up its payoff. The only way that B influences the Stackelberg equilibrium and the value is through the in- duced best response set B BR(B,a) Therefore, intuitively all the information that the optimizer needs to characterize the response dynamics is encoded in the best response for each æ E Am. We characterize each point x in the opti- mizer's simplex Am by which best response it could induce, as indicated in the following definition:
Theorem 4.1. There exists a pair of game instances G1 = Bi) and G2 (A. B2) B2) with the same opti- mizer payoff matrix A, such that for all optimizer algo- rithms A, there exists a no-regret algorithm A2 for the learner satisfying: StackRegi (A: = o(T) on G1 and Stock Regi A2) = cI for some constant on Gz.
Definition 5.1. For any possible payoff matrix B of the learner, the facet E, S Am corresponding to the i-th learner action e; is defined as the set of optimizer actions E Am such that is a best response to 2:
The proof of Theorem 4. 1 is deferred to Appendix A.
Theorem 4.1 suggests that even if the optimizer knows that the learner payoff is one of the two different candidates B1 or B2, whatever algorithm A₁ they try to come up with, there exists a no-regret algorithm A2 for the learner that can induce an ((T') Stackelberg regret to the optimizer in one of the two game instances. The proof of Theorem 4.1 relies on first designing a game instance such that G2 and G2 has different Stackelberg equilibrium, and use a simple algorithm A/2 against which the optimizer is not able to distinguish whether the realized learner payoff matrix is B1 or B2, before finally modifying it to be no-regret. The idea of constructing pair of game instances that have different equilibrium but the same payoff function for one player is also used in the proof of Theorem 3 in (Bajaj et al., 2024), in which they showed that in a repeated two-player game where the opponent strategy is not known, no algorithm can achieve bounded competitive ratio against itself (used by the opponent) for all such game instances.
E, == fx E Am : e, E B))B,
(6)
We sometimes use BB) to explicitly indicate that Eg induced by B.
Intuitively, the boundary of a facet specifies the critical hyperplane in the space of mixed strategies Am. of the op- timizer, where the learner is indifferent between two (or more) pure strategies. In general, Stackelberg equilibrium strategy x* stays at an extreme point of one facet, and there- fore, in order to extract Stackelberg from the learner, the optimizer must be able to (or potentially implicitly) recon- struct the facet boundaries around the equilibrium point. We illustrate the definition of facets by the following example:
and consider the learner payoff matrix B I, with the optimizer action æ (I1, I2) the facets E,, E2 and Eg are visualized in Figure 1:
Example 5.2. Let m =
This suggests that we cannot hope to design a no- Stacke algorithm for the optimizer that works simultaneously well on all game instances without any addi- tional assumption on the learner besides it being no-regret. Interestingly, Theorem 6 in (Brown al., 2023) suggests that the optimizer is able to learn and steer no-adaptive- regret learner, indicating the fundamental difference of learn- ing to steer learners with different algorithm classes.
E1
E2
Ea
X2
5. Steering through Facets and Payoff Matrix Recovery
Given Theorem 4.1, natural question that emerges is what information the optimizer needs to acquire to be able steer no-regret learners to Stackelberg equilibrium. In this sec- tion we present two alternative sufficient conditions under which the optimizer can steer the learner the Stackelberg equilibrium and achieve (T) Stackelberg regret by simply fixing one action at different time steps. The first sufficient condition is the approximate pessimistic recovery of facets- the best response regions for each pure learner strategy, and the second sufficient condition is an approximation of the learner's ' payoff matrix, up to an equivalence class.
X1
Figure I. The facets Es, Ee and Eg for payoff matrix B 1. While similar definitions are made in (Letchford et al., 2009; Peng et al., 2019; Lattimore & Szepesvári, 2019), we use the word facer because each E, induced by any matrix B is indeed a polytope that is a subset of An and their union Use(n) E, Am-
5

---

Learning to Steer Learners in Games
Following (Conitzer & Sandholm, 2006), once we have identified the facets for all i E [n). we can compute the Stackelberg equilibrium in the following way: First solve the linear program:
Theorem 5.5. If P1 has a set of di-pessimistic facets
Fyy Vi E [n] such that Vi & j. inf ZEE, 2' ||x x' || z d2, as long as P2 is using an f-no-regret algorithm Az. P can guarantee a Stackelberg regret of
=
(7)
BlackReg((AI,AA = ( 112 d2 + dd))
(13)
(E
for each i E [n]. Since P2 plays pure strategy at equilib- rium, the Stackelberg value is then given by:
by sticking to the corresponding x obtained from (9) and (10). Here we keep d1 and d2 inside the (()) notation to allow their choice to be dependent on T.
((A, B)= max (A) B)
(8)
sEim]
A refined version of Theorem 5.5 that expands the big O()) notation as well as its proof can be found in Appendix B.2. Here can see if we take di = d2 VJ(T)/T, we obtain an optimizer Stackelberg regret of O (VTTT).. which is o(T).
with the corresponding solution (x", i*) being the Stackel- berg equilibrium.
At Stackelberg equilibrium the learner is usually indif- ferent between multiple pure strategies, which means that switching from the equilibrium pure strategy y² to another indifferent pure strategy y does not incur additional regret to the learner, while potentially vastly degrading the opti- mizer's payoff. Therefore, instead of simply selecting the equilibrium point, the optimizer must choose pessimistic equilibrium point that sacrifices some utility from Stackel- berg value to guarantee the learner responds with y". We define pessimistic facets as:
In Theorem 5.5 we require a condition of inf infzen, simistic facets are disjoint (and at least de distance away) from other facets, and once the optimizer selects a point within E,_ , the learner has a unique best response i and deviating from i incurs a regret proportional to d2 at cach step.
ZERT , I| - I'Ilı 2 d2, ensuring the pes-
Definition 5.3. Given a facet Eg C Am. a pessimistic facet ET is subset of E,. We say E, is d-pessimistic if it is non-empty and dh (E,, E, I d, where d=(...) is the Hausdorff distance with respect to the L1 norm.
While a proper estimation of pessimistic facets suffices to steer the learner, under some specific cases, it may be easier for the optimizer to reconstruct the learner's payoff matrices, and it suffices to restrict our attention to those matrices which could induce different best response sets, leading to the following definition of equivalent payoff matrix classes: Definition 5.6. For any two m matrices B and B', if there exists some E R+ . E R such that
If the optimizer plays a 'safe' version of Stackelberg equi- librium by modifying (7) to:
max
(A,
=
(9)
EEF
B = cB' u1
(14)
and obtains a pessimistic value with respect to (8) as:
we say that B and B' are equivalent.
V (A, B) max V,- (A, B); =E(n]
(10)
It's not hard to see that if two matrices B and B' are equiva- lent, the induced best response set BR B, x) = B BR( B)) for all x E Am. Indeed, we show in Appendix B.3 that for all equivalent matrix pairs (B1, Bz), if learner algorithm is f-no-regret on one, there exists a corresponding algorithm that is f-no-regret on the other, which indicates that the optimizer is in general not able to distinguish between these two matrices without knowing A2. Therefore, restricting our attention from payoff matrices to equivalence classes won't 't affect the optimizer's ability to steer learners.
the obtained value V- B) will be close to V(A, B) if d small, stated formally follows:
Proposition 5.4. Consider the optimization problem (9). If
the facet ET is d-pessimistic, the pessimistic Stackelberg value V,- (A, B) satisfies
V1(A, B) :l S V,, & Vi B),
(11)
and therefore if FT. is d-pessimistic for all i E [n].
((A B) - [|]AA|lmax VV-AA, V(A. (12)
To describe an equivalence class B. observe that for all matrices B in B, the matrix B, (n-1( defined by (B : = (B.,+ some K A i in each column will be the same for any fixed in- dex i E [m] with the convention that 0/0- = 0, so we can use Bi to represent the entire equivalence class. Based on this, we can also define the difference between two equivalence classes:
The proof is deferred to Appendix B.1. As shown in Propo- sition 5.4, as long as the optimizer knows a complete set of d-pessimistic facets for each i E [n)), it is able to compute an approximate Stackelberg equilibrium up to an error at the scale of d. We now extend this result to its ability to extract Stackelherg value against no-regret learners:
B,,)/ max,, J2 [|B..h B lloo for
6

---

Learning to Steer Learners in Games
Definition 5.7. For two equivalence classes B1 and B2, their difference index i is defined as d3 .2) Bi 2-
We provide the following example:
Example 5.10. Following Example 5.2, consider B
-0.05 1.05
1.05 0.05
0 For facet E1 and the corresponding B, B3, 0.95
0
5.2. Steering with Payoff Class Estimation
0.05
we have that ||d (1, |mlax = 0.1. We show E (B, d) and the boundaries of E (B), E (B) as follows in Figure 2:
If Pt has an estimation B that perfectly recovers the under-
lying payoff matrix class of B, we could rewrite (7) as:
max FEAm
A.
s.t.: (B:)² x S - (15)
(B
for each E [n]. Again, each linear program solves for the best action when e; is the best response to action x played by P1. Consequently (8) becomes (AA, B3 = max; (1 B)) and the Stackelberg equilibrium point would be the corre- sponding solution.
E (8, d)
X2
With an estimation B that has some enror within margin d, we can define an optimistic version of (15):
V,+ (A. = TT A. s.t: (B:)* S d1, (16)
max # Am
and a set of pessimistic version:
max (T A. s.t: (B,) -d1. (17)
X1
=.
Figure 2. We can see that although Ej (B) & E, by construc- tion we have ET (B, d) C (B)
The optimistic (ef. pessimistic) problem relaxes (cf. tight- ens) the condition by a margin d. Notice that the feasible set of each optimization problem characterized by (15), (16) and (17) are also variants of the aforementioned concept of facets, we overload the notation:
Proposition 5.9 suggests that given an estimation B and a proper margin d, if P1 plays according to the solution to (17) (assuming E; (B, d) is not empty), the corresponding learner best response in the underlying game would be e,, However, a pessimistic facet may not be feasible when the original facet is fcasible. If E; (B, d) is empty, we cannot deduce that E, (B) is also empty. Instead, to certify the emptiness of (B),, we need E (B. d) to be empty as well. We use the following version of the definition given by (Gan et al., 2023) to capture the emptiness of E and ET
Definition 5.8. Given a payoff matrix class B, the facet E, corresponding to the i-th action e, of P2 is defined as:
(B) = {x E Am: (B,) x S 0n-13.
(18)
Similarly, given an estimation of payoff matrix class i and an error margin d, the optimistic facet F and the pes- simistic facet ETTT corresponding to the i-th action e; of P2 is defined respectively as:
Definition 5.11 (GGan et al., 2023), Definition 3). Given a payoff matrix class B of Pa, define the inducibility gap C. with respect the i-th action e, of P2 to be:
E. (B,d) d) == f Em Am (B:)Tx= x S d
(19)
G == min max, xJ (B))).-
(22)
E, (B, (BB,d) d) = { am xB:)²x5 - -dIn11
(20)
We can see from Definition 5.11 I that C. < 0 if and only if (15) is feasible. We show in Appendix C.2 that if C, > O. (15) is infeasible and there exists gap where it can be relaxed while still being infeasible. If C. = 0, however, Definition 5.11 indicates that Va, max, x" B (e, ( e,) 2 0, and 3x Am.j E [n] such that x" Be e4) 0. Under this case, the facet (B) has zero volume and as long as the estimation 1 is not precise, the facet E, (B, d) could always be empty. Also, even if the optimizer knows the real underlying B, since e; is weakly dominated, the learner is not steerable if e; happens to be the Stackelberg equilibrium since the learner is indifferent between e, and e,. To avoid this special case (which occurs with probability 0
The definition of pessimistic facets in Definition 5.8 en- forces strict dominance of the corresponding action by at least some margin d. We show in Proposition 5.9 that when the error margin d is larger than the scale of the difference in equivalence classes, the optimistic (cf. pessimistic) prob- lems are indeed relaxations (cf. tightenings) of (15). Proposition 5.9. If the error margin d satisfies
d 1 (I,
(21)
then: ET (B,d) d) C (B) S EJ (B, d). Further, since (15), (16) and (17) maximize the same objective, if ET (B, d) is
non-empty then: V. (A, B) S Vi(A, B3 S V, B).
7

---

Learning to Steer Learners in Games
for uniformly randomly generated B matrices (Von Stengel & Zamir, 2010)), we make the following assumption, as is standard (see e.g., (Gan et al., 2023; Deng et al., 2019; Brown et al., 2023)):
Lemma 5.16 suggests that once P1 has small estimation error of the payoff matrix class B of P2, the value and the corresponding action obtained by solving (17) will guar- antee a bounded suboptimality proportional to the error scale. Based on this, if P1 has an estimatiion B, that is accurate enough, P1 can commit to a fixed strategy given by the solution to the pessimistic optimization problem and could obtain a sublinear Stackelberg regret in the long run as T -> 00. We state this result as follows:
Assumption 5.12. The learner payoff matrix class B satis- fies C2 * 0 for all é E [n].
Remark 5.13. Our construction of game instances when proving Theorem 4.1 both satisfy this assumption. That is saying, if the optimizer knows B1 and B3, it is able to steer the learner to Stackelberg equilibrium, indicating that the impossibility lies in 'leamiig'' instead of "steering'.
Theorem 5.17. Under Assumption 5.12, Pr has an estima- tor B of B such that [[d; B²] I c c= ((g(T) Vi for some g(T) = o(T), then if P2 is using a f-no-regret algorithm A2, there exists an algorithm A1 satisfying:
With Assumption 5.12 we ready show that if the esti- mation 8 is accurate enough, all the facets are identifiable: Proposition 5.14, Given an estimation B satisfying (21):
Stack (A) Ol O(VTT((T))))))) + g(T)). (24)
Similarly, the refined version of Theorem 5.17 with explicit Stackelberg regret bound and its proof can be found in Appendix C.5.
1. (B) 0 and d S C, 1' then E (B. d) 0;
2. (B) + 0 and d S Co then E, (B, d) + 0.
5.3. Lower Bound on Stackelberg Regret
Proposition 5.14 shows that under Assumption 5.12, when the estimation error is small enough, either both E and E, are empty, or none of them is empty. Therefore, given B that is accurate enough, the optimizer will finally be able to decide whether E, (B) is empty or not.
To illustrate the tightness of our result, we provide the lower bound on the Stackelberg regret of the optimizer in Ap- pendix D, which shows that our rate (T)(TT essentially optimal against f-no-regret learners.
Since Proposition 5.9 suggests V;T (A, S V) S
V (A, if the optimizer chooses the solution to (17), its
6. Learning to Steer Classes of Learners
suboptimality can be bounded by V.+ (A, V,- (4, .8) To bound this difference term, we make the following defi-
We have shown in Section 5 that if P: can recover the set of pessimistic facets or approximate payoff matrix class, it would be able to steer the learner to a Stackelberg equilib- rium. Therefore it is natural for the optimizer to adopt an explore- explore-then-cone then-commit style algorithm that first learns either the facets or the approximate payoff matrix, and then com- mits to a pessimistic Stackelberg equilibrium. In this section we show in two concrete examples that when some infor- mation about the update rule of the learner's 's algorithm is known, P2 leaks information about its payoff which allows Pi learn the desired payoff structure and thus steer the learner to Stackelberg equilibrium.
nition to capture the sensitivity of this problem:
Definition 5.15. Given a matrix M E IR (n=-i)xm, define the sensitivity constant Sen(M) as:
M c1 m
Sen(M)= == minezo maxp,0
(23)
P.Q
where the maximization is over all P and Q that satisfies
M
P C [m], Q C [m], [P] = (2),
invertible.
c P,O
We provide numerical experiments to illustrate the effective- ness of the algorithms in Appendix F.
In Definition 5.15, we take the maximum over all invertible square submatrices, if we take M =(::)T, we can inter- pret P as choosing active constraints within the columns of B3 and Q can be interpreted as choosing nonzero entries of Based on Definition 5.15, we obtain Lemma 5.16:
6.1. Learning to Steer Ascending Learners with = 2
In this section we assume that the learner is using an ascent algorithm. where the learner's 's action greedily improves its payoff based on the last round's optimizer action:
Lemma 5.16. Suppose both the optimistic and pessimistic problems are feasible, then the difference between the op- timal solution V (A, B) to (16) and the optimal solution V, (A, 13 to (17) can be upper bounded by:
Definition 6.1. A learner algorithm A is an ascent algo- rithm if x! By: x. Byt+1 0 for all t, and x! By: of Byt+1 0 if and only if y1 E BR(B..))
V (A, V (A, B) S Ad Sen )B:) as long as (B, loc S d S 25em([B8yT)
For simplicity we restrict our attention to the case where m = n = 2, where we can see that the direction that
8

---

Learning to Steer Learners in Games
Vc+1 moves from y, directly reflects the best response to Ty-- Based on this observation, we propose Algorithm 1 as shown in Appendix E.I. The idea behind the algorithm is that the optimizer first performs a binary serach across its simplex [0, 1] and then apply pessimism to get an estimated E and En before finally committing to the solution obtained through (9) and (10). We show in the following theorem that the algorithm obtains a sublinear Stackelberg regret:
it can get some information of the i-th row B, of B. By uniformly exploring all such rows, it is able fully recover the entire matrix class B. Interestingly, since the update rule includes projection onto the simplex An. the information of one dimension is lost, so the optimizer cannot fully recover the exact matrix B, but luckily the projection preserve all information needed to recover B up to the equivalence class, which suffices to steer the learner to Stackelberg. Based on the intuition above, we propose Algorithm 4 as shown in Appendix E.2 with the following regret bound.
2 and the payoff matrix B does not contain identical columns. For some chosen parameter d, if either one facet is empty, or each facet has diameter at least d and P/2 uses an ascent algorithm A that is f-no-regret, Algorithm with accuracy margin d achieves a Stackelberg regret of at most O ((T) d' long as = ((T))(-f(T)).
Theorem 6.2. Suppose
Theorem 6.3. If the learner payoff matrix B statisfies the assumptions needed in Theorem 5.17, P2 follows update rule (25), and each entry E1.5 is i.i.d.
+ dT -log d) as
then with probability at least 1 -5,, 6, P1 using Algorithm 4 with k (T/g(T))² 2R² log(2ann/0). incurs Stackelberg regret of al most Stack Regk (A1, O(TTJ((T +
A more detailed version of Theorem 6.2 with its proof can be found in Appendix E. As an ample, here if F(T) = 7 and we take d = VS(T)TT we achieve bound on the optimizer Stackelberg regret of O 0 (VTJ(T)) - log VS(T)T)) = + log +
g(T)
+ [(TT)
The detailed version of Theorem 6.3 and its proof can be found in Appendix E.2. Here since for all no-regret algorithms Ag we have f(T) = ((VT), if we take T o(g(T)) and we have
0
0 T=
g(T) VT((T)
T(T)
Stack =()
For the more general case where n = 2 and m is an arbitrary constant, we can use a similar approach that does m(m- 1)/2 binary searches on all pairs of (es, e,). # j to find set of approximate indifferent points on each segment {ar E Am. : x; + 2j = 1} and then use them to reconstruct the facets E and Ez. the reconstruction is possible under mild assumptions since the real facets E` and Eg are separated by the hyperplane x² (Be - Be2)= = 0. We leave as a open problem whether similar approach will work for n > 2 case. There an alternative view of Algorithm based on payoff matrix reconstruction, see discussion also in Appendix E.I.
7. Conclusion
We studied the problem of learning to steer no-regret learn- ers to Stackelberg equilibrium through repeated interactions. While we showed this to be impossible against a general no-regret learner, we provided sufficient conditions under which the learner can be exploited and designed algorithms that learns to steer the learner under further assumptions on their algorithm. Our work provides several future directions for learning in strategic environments, including but not limited to finding a more precise characterization on learn- able and steerable learner algorithm classes, and learning in environments where neither payoff matrices are known.
6.2. Learning to Steer Mirror Ascent Learners
We now present an estimation algorithm that estimates the payoff matrix class B of P2 given that P2 is using stochastic mirror ascent with known regularizer. More specifically, we assume that the follower is using the following update rule:
Acknowledgements
EM acknowledges support from NSF Award 22401 10. YM is supported by: NSF Award CCF-2112665 (TILOS), DARPA AIE program, the U.S. Department of Energy, Of- fice of Science, and CDC-RFA-FTT-3-006 from the CDC's Center for Forecasting and Outbreak Analytics.
Vt+1 arg min ((vluu))))) - (o) B + <P))) yEA.
(25)
where & E RT is some noise that is either innate in the problem or injected by Pa to prevent from information leak-
age. We assume that f/ and the Bregman divergence reg- ularizer D(-II-) are both known to P1 and the regularizer satisfies D(y(+a [1ya) - oo if there exists [r]] such that 1,+ 0.
Impact Statement
Our work focus on learning within strategic unknown envi- ronments, providing theoretical insights that can guide the design of more robust and intelligent multi-agent systems. Since our society inherently fits into such environments, our work coud serve as the guideline for designing algorithms
At each time step f, through the update rule (which the optimzer knows by knowing the regularizer and step size), the relationship between 1/+1 and yt only depends on the term x!! B + <." therefore the optimizer selects x, = C,,

---

Learning to Steer Learners in Games
that interacts with people.
cake cutting. Advances in Neural Information Processing Systems, 37:97699 97765, 2024.
For instance, in self-driving fleets, vehicles must not only learn how to navigate but also anticipate the diverse, evolv- ing behaviors of other drivers, either human or algorithms. better understanding of how to "steer" or align these vehi- cles' learning processes could reduce collisions, congestion, and erratic maneuvers. Similarly, in automated trading plat- forms where billions of dollars change hands every day, being able to steer and exploit rival strategies strategies-expeciallly when the rival's objectives are unknown, can prevent desta- bilizing market manipulations or cascading losses. Beyond commercial applications, cybersecurity systems stand to benefit as well: more nuanced models adversarial be- havior under uncertain objectives can better protect critical infrastructure from sophisticated attacks.
Braverman, M., Mao, J., Schneider, J., and Weinberg, M. Selling to no-regret buyer. In Proceedings of the 2018 ACM Conference Economics and Computation, pp. 523- 223-538, 2018.
Brown, W., Schneider, J., and Vodrahalli, K. Is learning in games good for the learners? Advances in Neural Information Processing Systems, 36:54228-54249 2023.
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Collina, N., Arunachaleswaran, E. R., and Kearns, M. Efficient stackelberg strategies for finitely repeated games, 2024. URL
Ultimately, our findings encourage organizations and pol- icymakers to invest in adaptive mechanisms that account for varying degrees of information accessibility. By doing so, we can foster more stable, cooperative, and beneficial outcomes in multi-agent settings, ensuring that AI systems operating under unknown strategic environments are both robust and societally accountable.
2207.04192.
Conitzer, V. and Sandholm, T. Computing the opti- mal strategy to commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce, EC '06, pp. 82-90, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595932364. doi: 10. 1145/113470..11477777 URL https://doi.ors 10.
References
Deng. Y., Schneider, J., and Sivan, B. Strategizing against no-regret learners. Advances in neural information pro- cessing systems, 32, 2019.
Arunachaleswaran, E. R., Collina, N., and Schneider, Pareto-optimal algorithms for learning in games. In Pro- ceedings of the 25th ACM Conference on Economics and Computation, pp. 490-510, 2024.
Foerster, J., Chen, R. Y., Al-Shedivat, M., Whiteson, S., Abbeel, P., and Mordatch, I. Learning with opponent- learning awareness. In Proceedings of the 17th Interna- tional Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18 pp. 122-130, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
Assos, A., Dagan, Y., and Daskalakis, C. Maximizing utility in multi-agent environments by anticipating the behavior of other learners, 2024. URL pattps://arxtaa org/ abs/ 240./240..02 04889.
Bajaj, S., Das, P., Vorobeychik, Y., and Gupta, V. Rationality of learning algorithms in repeated normal-form games. IEEE Control Systems Letters, 22209-2444 2024. doi: 10.1109/LCSYS 202..3366....2
Foster, D. P. and Vohra, R. V. Asymptotic calibration. Biometrika, 85(2):379-393 1998.
Gan, J., Han, M., Wu, J., and Xu, H. Robust stackel- berg equilibria. Proceedings of the 24th ACM Con- ference on Economics and Computation, EC '23, pp. 735, New York, NY, USA, 2023, Association for Com- puting Machinery. ISBN 9798400701047. doi: 10. 1445/558050733597680 URL https://doi.com 10.
Balcan, M.-F., Blum, A., Haghtalab, N., and Procaccia, A. D. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the six- teenth ACM conference on economics and computation, pp. 61-78, 2015.
Bertsimas, D. and Tsitsiklis, N. Introduction to linear optimization, volume 6. 1997.
Goktas, D., Zhao, J., and Greenwald, A. Robust no-regret
learning in min-max stackelberg games, 2022. URL
Blum, A., Haghtalab, N., and Procaccia, A. D. Learning optimal commitment to overcome insecurity. Advances in Neural Information Processing Systems, 27, 2014.
https: arwia. http:/axxvvv...//aaaa wttp://///..b....////.. httpb////2222.11.
Haghtalab, N., Lykouris, T., Nietert, S., and Wei, A. Learn- ing in stackelberg games with non-myopic agents. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 917-918, 2022.
Brânzei, S., Hajiaghayi, M., Phillips, R., Shin, S., and Wang, K. Dueling over dessert, mastering the art of repeated
10

---

Learning to Steer Learners in Games
Haghtalab, N., Podimata, C., and Yang, K. Calibrated stack- elberg games: Learning optimal commitments against calibrated agents, Advances in Neural Information Pro- cessing Systems, 36:61645-6166 2023.
Zrnic, T., Mazumdar, E., Sastry, S., and Jordan, M. Who leads and who follows in strategic classification? In Ad- vances in Neural Information Processing Systems, 2021.
Harris, K., Wu, S. Z., and Balcan, M.-F. F. Regret min- imization in stackelberg games with side information. Advances in Neural Information Processing Systems, 37: 12944-12976, 2024.
Hart, S. and Mas-Colell, A. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 1127-1150, 2000.
Lattimore, T. and Szepesvári, C. informmtiionthhorettii approach to minimax regret in partial monitoring. In Conference Learning Theory, pp. 2111-2139. PMLR, 2019.
Lauffer, N., Ghasemi, M., Hashemi, A., Savas, Y., and Topcu, U. No-regret learning in dynamic stackelberg games. IEEE Transactions on Automatic Control, 69(3): 1418-1431, 2023.
Letchford, J., Conitzer, V., and Munagala, K. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory: Second International Sympo- sium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009. Proceedings pp. 250-262. Springer, 2009.
Lin, T. and Chen, Generalized principal-agent problem with learning agent, arXiv preprint arXiv:2402.09721, 2024.
Lu, C., Willi, T., De Witt, C. A. S., and Foerster, J. Model- free opponent shaping. In International Conference Machine Learning, pp. 14398 14411. PMLR, 2022.
Maheshwari, C., Cheng, J., Sastry, S. S., Ratliff, L., and Mazumdar, E. Convergent first-order methods for bi-level optimization and stackelberg games. In 2024 IEEE 63th Conference on Decision and Control (CDC), 2024.
Peng. B., Shen, W. Tang, P., and Zuo, S. Learn- ing optimal strategies to commit to. Proceedings of the AAAI Conference on Artificial Intelligence, (01):2149-2156 Jul. 2019, doi: 00.1609/aai.vv3:00 33012149. URL TtRLhtts::/// aaai. org. index. hhtp/AAl/artiile//vveeee
Von Stengel, B. and Zamir, S. Leadership games with convex strategy sets. Games and Economic Behavior, 69 (2):446 457,2010 2010.
Zhang, B. H., Farina, G., Anagnostides, I., Cacciamani, F., McAleer, S. M.. Haupt, A. A., Celli, A., Gatti, N., Conitzer, V., and Sandholm, T. Steering no-regret learners to desired equilibrium, 2024. URL https: /arxiv. org/ abs/ 2306 05221.

---

Learning to Steer Learners in Games
A. Proof of Theorem 4.1
Consider the game instances G = (A, Bi) and G2 = (A, B2) where:
0 0 1 c
0 c
1 0 0 1
B1
B2
(26)
0
1
with (0, 1/2) being small positive constant. Fix an optimizer algorithm A1 and suppose is no-Stackelberg-reeret on G1. We first show that there exists learner algorithm A₂ (that may not be no-regret algorithm itself) that achieves Rege (A1, A2) o(T) both 11 and G2, and then modify this A₂ make it no-regret algorithm itself. In this proof section we use Stackregı (-, G+) and Regz(-, G;) to denote the corresponding regret notions evaluated on G,-
For the first step, we show that a simple algorithm A2 that takes = (0, 1)2 satisfies the conditions above for both G1 and G2. Notice that the unique Stackelberg equilibrium for G is:
x = =0 (),,1),, . = (0,1)²
(27)
with the corresponding Stackelberg value V(A, B1) = c. In order to achieve sublinear Stackelherg regret, the selections Te by A₁ must satisfy
StackRegi (A) [Ba.)
Te Σ a Aye yr
vi, Vt
o(T),
(28)
which simplifies to:
T Σ
! c
E
1]
-
o(T).
(29)
That is, the average of {-+)²= must be asymptotically close to (0, 1)" in expectation. Also notice that y is a strictly dominant strategy for the learner, we have Reg, G1) 0.
Now consider G2, the unique Stackelberg equilibrium for G2 is:
1 ST. 32 = (1,0)² 2.'
2. =
(30)
yielding a Stackelberg value of V(A, B2) = 1/2. Since Ai only takes the {u ) sequence as input, it must behave identically as in G1, with expected average (xt) asymptotically close to (0, 1)" as well. That is,
1
-R mii
T
Σ
T Afj
vi. 1i
2
1=1
1 T -E mi
27 T
Aye
Wt vi. 14
(31)
2
T (ET - oT))
2
= 7 - e)T + oTT).
Therefore, as long as A, no-Staacellher-regree on G against A2, it incurs linear Stackelberg regret on G2 against the
12

---

Learning to Steer Learners in Games
same A2. Also, since (29) still holds under Gg, we have the following upper bound on the learner regret:
Regg(A1, G2)
T
=T - B ( mn
T B28h = Vi. Vt
-T - E [1 ~
(xt [0 11)² Bry 1/ vi, Vt
E Ba 17 me
Σ
0 1
B2 yt
vi, vt
r
=T B (n)) A1
Σ (10 1] -xx) B2tl V/2 vī. Vt
T
(32)
T
=E (m)) Ai
Σ ([0 _|=1
1] x²)² B2ys = yi.
T
(10 1] - xz)²²² [1]
=E
1=1
1] - =f 0
E
Σ [0
=T())
which completes the first part of the proof.
We now modify A2 into no-regret algorithm. Notice that although A2 constructed above obtains sublinear regret against A on both G₃ and Gg, it is not no-regret G2 since it may incur linear regret on some { sequence, e.g. 2 (1, Vt. Since Ai is fixed, we can use a function g(T) = o(T) to characterize its Stackelberg regret, namely we select g(T) such that
T StockRegh (A1, A2; G1) = EE Te
Σ
L Ayr Dr = vi Vi Og((T))
(33)
Our idea is to let the learner keep track of the cumulated regret upon the current time step to identify whether the trajectory {z, bor) is generated by A₁ or not. Consider the modified algorithm Âg as follows:
1. When the interaction process starts, stick (0, 1)::
2. At each time step I, calculate the running Stackelberg regret S ( )==1) = (1- (1-1)e-Errl
Er=l xf Ay::
3. If (.SS((2r.))))))) 2 VTg(T). switch and stick to online mirror ascent, otherwise keep playing (0, 1)".
Notice that here aim prove the existence of such algorithm as Az. To complete the proof of Theorem 4.1, notice that game instance G1 no matter what trajectory (x-)<=1 it faces, since (0, 1)" is dominant learner action, A will play (0, 1)" for all time steps, and therefore have Stackelberg regret. It suffices to prove that on the game instance G2, A is no-regret and Ag still incurs (TT) Stackelberg regret to the optimizer against A1. To simplify calculation we use notations x (#1 x2)) and y = (2) here.
the knowledge of g(T), which serves the Stackelberg regret bound of A₁ because we only
To show that Ag no-regret, notice that before switching mirror ascent, the learner regret has the following form:
G2) = max
1r,1
2
Σ
xr.2 = max Σ (1 2x, 2),0) 0}.
(34)
7=1
Also, A sticks to (0, 1)", and therefore,
SR((Er. ((=1)) = (1 1)e
Σ Fr
(35)
r=1
13

---

Learning to Steer Learners in Games
Let Tg denote the time step which A switches, or T if the algorithm doesn't switch until the end, have:
Rege( (2,, (1)11 G2)
T,
=max - Σ
Tt,2, 0}
Im/
SR (1t, Yt 1t 13--1 ).03 0(1)
=max((T,- - -2(TT
=max|2 SR(( )
(36)
T +,++100++01
SR((I 1T,-1)
22
+11)
=O(VTg(T)
=o(T),
and therefore,
Regz(( ye 3eTr=11 G2)
T
T
T By Σ
T Byt
max Y.A.
It.
Dt.
t=1
t=l
To
T
Ft. T By
Σ
3it
T Byt +
Σ
ot By
Σ
By:
(37)
yEAn
yEAn
t=T+11
t=
=Rega (I 81 Mi G2) + (ta
=o(T) +O(VT)
=T(
Since this holds for arbitrary {=+)==1 sequence, we deduce that Ag is no-regret algorithm.
To show that Ag incurs ( Stackelberg regret the optimizer against A₁, consider the event
ε = (SR((Er.Vi) G1) VTg(T), for some /. E (T)}
(38)
= [SR(( V (T{)))
that captures the case where the Stackelberg regret of Ar exceeds VTg(T) under G1 given the learner fixes yi, since A₁ no-Stackelberg-reereet on G1, the probability of & should be small:
E [[ BrIT=ri =O(V 9(T), T
Pr(E) S
(39)
(Tg(T)
Conditioned on & doesn't happen, Ag will not switch to online mirror descent, the Stackelberg regret under G2 satisfies:
[Stack (fx,, :
121.0e 17_ dr Ar.
1 [
T
Σ A
2
(40)
1
=
(ET - -E 1
[SR([I) (0, 1r
2
=
c) + +((TTg(T))
2
14

---

Learning to Steer Learners in Games
Since An should respond identically G2 write the Stackelberg regret of A1 as:
Stack (A1, A2; G2)
=B ( Stock Regi (( Be)=n::
=B (ae.Ve) 3T A
Stackkeeckkaaaattt (a B (m. (.. (ta. /tw.aa/eeeeeaaaaaaaaaaaaaaaaaaaa Pr(E))
9(T)
=O(T
+ E (
Pr(E))
T
9(T))
( - (-)TT+((TT((T) (1
g(T)
20(T
+
T
2dT
(41)
for some constant c, where we have used (40) in (i). As a result, A incurs ( Stackelberg regret against A,, which completes the proof of Theorem 4.1.
15

---

Learning to Steer Learners in Games
B. Proofs for Section 5.1
B.1. Proof Proposition 5.4
Fix some i. Since d-pessimism implies E and Eg are non-emply, let x; denote the optimal solution to (9) and x" be the optimal solution (7), since E S Eg have:
(x") A. VV(A A.. 5 -(7)
(42)
Also, (E, BT7 S d implies there exists & E satisfying 1 x*111 111 S d. and thus:
Vi (A, -xx))
20" A.s
=(x" + =x")² 22/AA A.,i
(43)
2(x") a, A,
=Vi(A, B) d) A.
where the first inequality holds due to the optimality of z; solution to (9) and in the second inequality Hölder's inequality that gives la bl < ||a|]a [bbloo, which completes the proof.
B.2. Refined Statement and Proof of Theorem 5.5
We first provide refined statement of Theorem 5.5 that expands the big O(-) notation in the original statement.
Theorem B.1. If P1 has set of d1 de-pessimistic facets E, Vi E [n]] such that vi + j. inf æ''E,, ||> 2'111 2 d2, as long as P2 is using an f-no-regret algorithm A2 with constant C, P1 can guarantee a Stackelberg regret of
ReackRegi A2) = (di + 2CT(T)
||A]max
(44)
ed2
by sticking the corresponding x- obtained from (9) and (10). Here is constant that depends only the learner's payoff matrix B.
(A,A Proof. Let u.. denote the optimal solution (9) and arg max, V, (A, B) be the index of the best response under x
so that x -x._ Since the pessimistic facet E satisfies inf iufze,, wEE, ||z x' 1 d2 for all j * i'. e, is unique best response have
(x-)² Te, - (x- Bej 2 ed2, vj [m].s #i
(45)
16

---

Learning to Steer Learners in Games
for some constant e. Since the learner regret has the following expression:
(( -31)(=1)
=(x> )d
Ci - y1)
=(x ) B
(ci- Σ B(,cez)
1=1
jE(n]
T
=B
(1- Dt, )ei
Σ
yeses
jeinlaiti
(46)
=(x (
Σ ye
Σ
yenes
jE(n
JE(M)
E
Σ Uhs ((xT)T Beg - ((e))
jE(n],jzi
Σ
seds,
jC(n]Jitii 1=1
where we have used the fact that Yt. = Eje(n] izt Biy for all ye E An the fourth equation. Since A2 used by the learner is f-oo-regret, assume the regret constant C, have:
(er
9t)ll
T
(e
Σ
,r,se,)l1
1=1
JE(n]
y1.3-)
Ut.i
jEin),A
(47)
2
Vh.i
t=1
vEln)
2Reg2((x
11e IT
ed2
2CI(T)
cd2
where the second equality follows from ye.s [0, Voe E An, [n]] and the third equality follows from the same
17

---

Learning to Steer Learners in Games
argument above. Let i* denote arg max, VI(A, B), the Stackelberg regret of P1 satisfies:
Stack RlackRegi (2) -T.V
(x )d Ay,
T
-T. (V,((A Σ (x )" Ae Σ
(x )d A(ee=- - -1t))
=T. (V(A - (A, +
(x (T=)T ((A((== 31)
1=1
T
ST. (V(A, B) - ()( + +1|ATx |10
Σ
(e- - yt)l
1=1
ST. <T. (V(AB (A, + +11A x [6 Σ (er- vill
(48)
=T (V. - V,- (A, + +1IAa x 1lo0 Σ (e:- - y:)l
T
(8)
Tdl | max + 11A x 1lael
Σ
(cr-
y/)l11
1=1
T
(1)
Tdd || max + max
Σ
(es - 9))ll
1=1
Cf(T)
RTd max + A|| max
6d2
where we have used Hölder's inequality in (i), the maximizing argument of (10) in (ii), Proposition 5.4 in (iii), Hölder's inequality in (iv) and (47) in (v). This completes the proof of Theorem 5.5.
B.3. Regret Invariance Properties of Equivalent Payoff Matrices
We now state and prove Proposition B.2, which shows that the same trajectory yields the same asymptotic learner regret for all learner payoff matrices within the same equivalence class.
Proposition B.2. Consider an interaction history (It, Bo that is f-no-regret for the learner on matrix B1, then for all matrices B2 being equivalent to By, the same interaction history is also f-no-regret. result, for all f-no-regret learner algorithm A2 on Br, there exists another learner algorithm A'2 on B2 that simulates AQ on By which is also f-no-regret on B2.
Proof. We use the notation Rega(:; B) to denote the learner regret on its payoff matrix B. Since B₁ and Bg are in the same equivalence class, by definition have B3 cBi + pl1 for some RR p E m," The interaction history {2+, ) being f-no-regret B₁ implies for some constant C:
T
Rega (1t, 3 Bi)
maxx A,
Jt Byy I Σ t=1
B. SC-(())
(49)
t=
18

---

Learning to Steer Learners in Games
Therefore, have the following bound the learner regret on By:
T
Reg2((2,,,.) B2)
max yeAn
B2y
Σ
1 Bay
T
T
T
max
nd (cB1 + k1
Σ
rt
(cB1 + )1
yEA, t=l
T
T
T
T
max
Lt
T B1y
Σ
Dtt
T Biye
+ max yEAn t=1
Ft p
T
n
T
It p1
T
yEAn,
(50)
t=1
t=1
t=1
T Si. Biy
Σ
T BLye
Σ
T
Σ
T
zt.
Ftc 1
J p
yEΑn
yEA.. t=1
(=1
t=1
max yEAn,
2t Biy
Σ zt.
Biyt
<TC
where the fourth equation holds because 1. = Di=1 = 1 for all y E An. This shows that (2x, We ) is also f-no-regret on B2.
19

---

Learning to Steer Learners in Games
C. Proofs for Section 5.2
Within the proofs in this section we will make extensive use of the following property that for all a Am:
(B, max S (B; B;) S [Id maxmmmxx (
(51)
This property be obtained by bounding each of the column vector (Bi -B;) BB) with the fact that each entry of in [0, 1].
C.1. Proof of Proposition 5.9
Suppose we have d 2 [[d; mmll
To prove that F. (B,d) S (B), notice that if F. (B, d) = 0 the inclusion naturally holds. Otherwise for all E F (B,d). d),
it holds that
(B,)"= (B; BB) (B;)*x*
i) S (B; BB?T= d1
(52)
(B)d,(B, || - d))n=1
50,
where (i) holds by definition of E, (B, d) and (ii) holds due to (51), so that E EB(B).
Similarly to prove (B) S E (B, d), we only need to consider the case where (B) * 0 for all æ E (B), we have:
(8:) x -B; -B,) (B;)
$ (B:: -B,)²Z
(53)
< <B, B3) mmx I-
<dln-1
where again (i) holds by definition of (B) and (ii) uses (51). Therefore x E E (B, d).
C.2. Relaxed Empty Facet Condition under Positive Inducibility Gap
Proposition C.1. C >> 0 is equivalent to E, = 0, both imply the the following:
{o E Am: (B))² S C₁ 1n-1) = 0.
(54)
2
Proof. We first prove that C + F, 0. Notice that
C > 0 +V E Am mm,maxx maxx (B.) >
*Vx E Am. s.t x² (B)).., >
(55)
< Am, S.t (B?)
E
We now prove the second part by proving that if there exists To Am satisfying
C In
(B;) 3o 5
(56)
2
have C 5 0. This is because
C.
1
(B.)TTr To
n
2
min max (B,) In- wEam 3
(57)
20

---

Learning to Steer Learners in Games
implies
1 (B)) 20 I max 2o (B:).,s in
(58)
2 5
which means that for j* attaining the maximum,
o (Bi) :r - " (B))..
(59)
which is equivalent
1/ (B9))..) 5.
(60)
This means that
C, = min max x (BP).. aeAm. 3
S <max To T (BP).s
(61)
=n (B))
<0,
which completes the proof.
C.3. Proof of Proposition 5.14
Proof of part
By Proposition C.1, E, implies
C2 tor E (B,) x < 1n-1} = 0.
(62)
Therefore,
fo Am (B;) (B B3) x
- Ln 1 = 0.
C₁
(63)
2
Combining (51) and (21) we obtain
C
(8) Bi) - -1,,
max 1n 2 -d1,-1 2 la-1-
(64)
Based on the two equations above, we further have
Ci 1, 1 =
{or E Am (8:) S
(65)
and since d < G. it holds that E (8, d) = -0.
Proof of part 2: Let arg minlyEA.. max, x (B))... if Ex(B) + 0, by definition we have
(B:) zo S C1In-1-
(66)
That is,
(B:)²² zu <(8; BB.YB zo + CzIn-1
[1, |l In- C,la-1
(67)
< (C. + d)1n-1
mm) < - -dd--1
where we have used (51) in (i), the condition (21) in (ii) and the assumption d < -C,/2 in (ii). This means that To E Fij (B, d) and hence F, (B,d) d) # 0.
21

---

Learning to Steer Learners in Games
C.4. Proof of Lemma 5.16
To bound the difference term:
(A, -V,
(68)
notice that (16) can be written
maximize
V (A, = x² A.
(B:)27
dl
1
(69)
subject to
-17
I S
1
Im
and similarly for (17):
maximize
VI (A, = T A.i
(B: T
dl
1
(70)
subject to
-17"
2
Im
1T
251
For notational simplicity, we use M to denote the matrix
1
and we only need to bound the term M71
0m-
over
mm
all linearly independent index sets I such that [ and k: 1] is the number of rows in Mz corresponding
those in (B:)² We begin with presenting some auxiliary lemmas:
Lemma C.2. Consider linear optimization problem in the following form:
maximize subject to
== c²
(71)
Ax S b,
and its perturbed problem:
maximize subject to Ar b 6
V(0) = CTa
(72)
where x E R and A E Rmxx for some m 2 (notice that in the context of this lemma the matrix A and its dimensions m, n are in general not those considered in the broader setting of the game). Assume both problems are feasible and the constraint sets are bounded, recall that Ay denote the matrix constructed by selecting rows of A from some index set C [m], we have that
V(8) - V S max T
A 8z,
(73)
ZES
where S denotes the set of all index sets corresponding to rows any basic solution to (71), or equivalently, the maximization over all linearly independent row combinations of size n.
Proof. See Appendix G.I.
Lemma C.3. For arbitrary Bi and the corresponding M described above, have:
2d1 0m- k
max
M₁¹
2d))n((3:))))
(74)
ZES
where S denotes the of all index containing linearly independent of M with size and ie |[n 1] n]
Proof. See Appendix G.2.
22

---

Learning to Steer Learners in Games
Lemma C.4. For invertible matrix B and small perturbation matrix 8B, let || norm, B ||8|B|||| B 6B is also invertible and its inverse is bounded by: ||
be any sub-mulippicative matrix
|B B |1]
((B+8B)
(75)
Proof. See Appendix G.3.
Proof of Lemma 5.16. Compare equations (69) and (70) we obtain the following through Lemma C.3:
201
(A, - V. (A -|1Aiil max
M
I
0m-k
(76)
s2d A bx Sen
(1:92T 1
[B 1
Since for all invertible submatrices
and
such that [d, B))[Se((((BB))) < 2.2 the following
P.Q
P.0
inequality
(B:) 7
(B: 7
(B:)
<1
(77)
1
1
P.Q
m
P.Q
P.Q
is satisfied, and for every possible combinations of P and Q Lemma C.4 implies:
[ -1
(B:
T m P.Q
(B:)
1/2
P.
(78)
(B:) -1
(B:) 7
(B 77
1T
1s
1
P.Q
m
P.Q
P.Q
Sen((B))7)
(8 (B,
We have that
(en(
(en((B;)))
(79)
dSen (B:)TT
which leads to the final result:
Vi+ B)) - V, (A,
2d || A -o Sen (B:9T)
2d A., 0o. Sen (B:)²)
(80)
1 dSen( (B89T)
<4d|| Sen (BB))
where the last inequality holds because dSen((B))²)) 2 1
C.5. Refined Statement and Proof of Theorem 5.17
We first expand the big O(-) notation in the statement of Theorem 5.17 and obtain the following theorem:
Theorem C.5. Under Assumption 5.12, if Pı has an estimator B of B such that [B, B) S O(g(T)/T) vi for
some g(T) o(T), then if Pz is using a f-no-regret algorithm A2 with constant C, there exists an algorithm A satisfying:
( (VT+VT((T) Sen (L) +
CVTS(T)
StackRegi (A,,
|
max [| -x)
(81)
=0 (VTJ(T) + t
23

---

Learning to Steer Learners in Games
Proof. Consider the algorithm A₁ that commits to the solution (a ;--) to:
maximizes,
(A, = x²" 1."AA,, A.
subject (B:))² - - f(T)/T))n-1.
(82)
x E Am, [n].
where f(T) is some function satisfying f(T) oT) and f(T) o(f(T)) Since + f(T)/T 2 [|d, Bl Proposition 5.9 guarantees that e;- best response to x under B.
Let (x), denote the Stackelberg equilibrium of the game. We have that E, (B) * 0 and since = (TT)T) + /TT)/T goes to zero as T + xo, Assumption 5.12 and Proposition 5.14 guarantees that V₁- (A, B) is well-defined (and therefore so is V (A, B)) for large enough T.
Since A is f-no-regret, it holds that
x " B(er - (n) SC.f(T)
EA,
Σ
(83)
1=1
for some constant C. We have that
T
BA
Σ
T Ayt
= A2
)T AyA
(84)
AA
(x (m Ae,-
+ E AAnAA
[ Am
A(y - c-)
For the first term, notice that for large enough T, + f(T)/T
[Be.( and get:
EA
Σ x )
-TV,- (A,
(85)
2TV (A,
TV, (A, B) - (TV+ - (V, (A,
TV () - 4(ET + [(T)) llx. Sen
where (i) holds since we are taking maximum in (82), and (ii) holds by Proposition 5.9 and Lemma 5.16.
for the second term, since x satisfies
S (8: T - J())))
(86)
we have
(B)-) x -BB--) Jx + +BB -B:-)Ta-
<(-(e+ + j(T)/T) + || (B, 11x)))))
(87)
i(T)
1n-1-
where (i) holds by definition of d.)..) and (51), and (ii) holds by the assumption that [|d, ()l Se.
24

---

Learning to Steer Learners in Games
Thus 6j- is the unique best response x- and Hölder's inequality yields
(x (x
BE
BEA Aa
Σ le-
vc)
2
J(T) T
max [
ex]lloo
BA2 Σ Ut cx-
(88)
3.b
Therefore,
Cf(T)T
AA
yt et-)
(89)
f(T) max;. [[e, - cx)l
1=1
Thus we have:
Σ 1m/l
(x (x=)T A(y - -e--)
A1
T
||(x |"x Alloo
EAA2
Σ (yr -(vc-et-))
(90)
(
Cf(TYT
||||| max f(T) max;,e [Bee, ex)ll00
where we apply Hölder again in (i) and use the fact that x- E Am in (ii).
Combining (84), (85) and (90) we obtain as
oc: 00:
T
AA
Σ
ot Ay
1=1
2VV(A 4(ET + F(T))]IA,, Sen((B)))
CJ(T)T
|||| max j(T) max,, [ - l20
(91)
2 2TV(A, 4(g(T) + ((T))) llo Sen((())))
Cf(T)T
||AA|l max j(T) maxjæ [B(e; 200
taking i(T) TT) have:
StackRegi(A
<4 ET vTf(T) ||A,, Sen ((B%))²) + || max CVTf(T)
maxj,a B(ee, ex)llo
(92)
4 ((eT VT((T) Sen (BB))T) + maxx,k [ - -x))llo
CVTf((T)
||Al
- -
This completes the proof of Theorem 5.17.
25

---

Learning to Steer Learners in Games
D. Lower Bound on Stackelberg Regret against General f-no-regret Learners
In this section we provide Theorem D.I, which shows that even if the optimizer knows B, the learner still has a no-regret algorithm with regret budget f that can lead a (T) Stackelberg regret of Pt. indicating that our Stackelberg regret bound Theorem 5.17 essentially optimal.
Theorem D.1. Consider given function f(T) o() which serves as the regret budget of Pz. there exists a game instance ==(A, (A, B) that satisfies Assumption 5.12 and an f-no-regret learner algorithm A that can be used by P2 such that for all mixed strategy x E Ams the non-adaptive algorithm A1 that plays Ią = x: at all time steps has Stackelberg regret at least ((TT((T))
Proof. Consider the game instance (A, B) where:
0
0
1
0
A
B
(93)
3
1
0
whose unique Stackelberg equilibrium is:
2 1 2 = (1,0)*
(94)
with Stackelberg value V(A, B) = 3.8 For algorithm Ai that outputs fixed optimizer action = (21, and given sequence 1e of learner actions, the learner regret can be expressed as:
T
Rega(1ær xr, 11) = 7 max (21, 02)
x
yt-
(95)
1=1
Consider the learner algorithm A2 to be:
1. If If 21, play (0, T::
2. Otherwise, play (0, 1)" for T-202 rounds, and (1, for the remaining T' f(7)
f(T) rounds.
T-2mm
The learner regret of A if 2g 2 x1 is:
Rege(A2, fxz = =x]T_) )- = Tr T22 = 0,
(96)
and if 22 < Fi, we have:
(T) (T
S(T) )x1
Rege {r, = x)}=1) =Tx;
- 2x²
1 2x12
=T(1 x22) x2 (T)
S(T) )1 222)
(T
20²
2x²
(97)
(1 f2) (T)
2x²
2x2
=f(T),
and therefore Ag is f-f fnoorregret.
If the optimizer wants to achieve sublinear Stackelberg regret, x must satisfy 22 < æ1. otherwise Ag will stick to 1),
and incur a O(T) Stackelberg regret, now we calculate the Stackelherg regret of the optimizer when D2 < Z1
3
f(T)
f(T))
StackRegi (fx, xx, (.)
- - (3(T - 2x²
222
1 2r²
(98)
2x²
-
-3x2) + 2x² S(T).
The minimum Stackelberg regret 22 [0, 1) can be achieved by taking
1
f(T)
I2 = 2
(99)
6T
where Stack ((x; =x, ( 0 ((T))))) so in general the Stackelberg regret 2( ((VT)(T))
26

---

Learning to Steer Learners in Games
E. Algorithms and Proofs for Section 6
Before we start presenting the algorithms and proofs, we first prove an auxiliary lemma which suggests that in an explore- then-commit style algorithm, any interaction history that has length o(T) before committing will have no impact on the asymptotic learner regret, stated formally as follows:
Lemma E.1. Consider an optimizer action ā E Am if the optimizer action sequence { Pi satisfies on -. VI >> T for some = (T)) then the interaction sequence {xr, Ve Yl=1 is f-no-regret if and only if
Regz( Rega((=s.. v1) C S(T)
(100)
for some constant C, and consequently, A2 is f-no-regret on {mm) 1 and only if
BEA
Σ (ū V1)
SC.
(101)
for some constant C.
Proof. Let ÿ E (R(B, be best response f.. For the "if" direction, observing that:
Regz( (,2,,18 31
max yEAn
21 By
3
T
By
T Σ
< max yEAn
T By
I1 Byg + max
Jt
By
Σ
It By
yEAm
(102)
t=1
t=++1
1=
= Rege Ve (1s
Regz f (1 ya 12=
S T Iumax +C ((T)
< C² f(T)
for some constant C' where we have used the fact that (T)())) and therefore {z,, Ve is f-no-regret. For the "only if" direction, notice that
T
T
Regz((2; (22,, ye VTmi = max
T By
Σ
xt
T
By
yEAn
t=1
1=1
T BiO -1t
(103)
T o B(ÿ vv) + x" B
Σ (ū (リ-w) v1)
2 - B max + Regz ( (Tt, Ve 1T++1)-
If we want Rega((0s. s C. ((T) for some constant C, must have:
Regz((wa, v S C ((T) + +||B]| max S C')
(104)
for some constant C², which completes the proof. The proof of (101) follows directly by taking expectation over all (9:)7 trajectories generated by Az.
E. Algorithm 1, Detailed Version and Proof of Theorem 6.2 and Discussion
We present the pseudocode for Algorithm follows:
Here test(-) (-) is a procedure that compares the learner's response at two consecutive time steps to determine the underlying
best response to some optimizer action = (p, 1 1--1- p). as shown in Algorithm 2, and B na rySea research(,,. d) is procedure that approximates the optimizer action x² at which the learner is indifferent to an error margin d, as shown in Algorithm 3.
We also provide the detailed version of Theorem 6.2 as follows:
27

---

Learning to Steer Learners in Games
Algorithm 1 Playing Against Ascending Learner
Input: Accuracy margin
Run (R(0) (0) and BR(1) t (1).
if test(() (1) then
Let (e) (1)
Compute 7 f arg ma x² Av".
else
PL - 1 (BR = (1,0)). + (B)( = (0, !)]-
Pi.PR + BinarySearch/p..Ptt
if pi P then
E 0, max - d, d,03];
Ez [min(1, PI - d7.1] 1|.
else
_ + [0, max - d, 0}};
E +
miim(1,77 P2 + d), 11.
end if
Compute through (9) and (10).
end if'
Stick ã for all remaining time steps.
Algorithm 2 test
Input: Action parameter E [0, 1]
Use t to denote the current timestep.
Play z, (p, p)" and observe Yt = (4; 9T) Play an arbitrary æz-1 and observe yc+1 (9t+1, 9411)²
if (++1 Ge then
return (1,
else
return 10
end
Theorem E.2. Suppose m = n = 2 and the payolf matrix B does not contain identical columns. For some chosen parameter d, if either one facet is empty, or each facet has diameter at least d and P2 uses an ascent algorithm Ag that f-no-regret, Algorithm with accuracy margin d achieves a Stackelberg regret of most
(++ (4+5 61
| max
(105)
if the learner has a strictly dominated action, where 61 minzea,, TT BT 62). and
2CJ(T) e2d
(2logg 6 2Td+
||Alluass
(106)
otherwise, where 6g is constunt that depends only on B. Under either case, C is constant that depends only on the learner regret constant and payoff matrix. This indicates that the Stackelberg regret is at most O ((T) + dl log d) as long d ((cx)(-((T)).
Proof. If one of the facet is empty, would have te = test(1). In this case, despite the first interaction steps used by 2 test calls, Algorithm will output the Stackelberg equilibrium strategy for all subsequent actions.
Now we analyze the Stackelberg regret against an f-oo-regret algorithm A2. W.L.o.g suppose eq is the strictly dominated action, since 62 is strictly dominated, we would have IT Bej - xT Beg > 0 for all x E Am. there exists a constant c that depends only on B (but not d), such that:
TT TTe J Bez 2
(107)
28

---

Learning to Steer Learners in Games
Algorithm 3 BinarySearch
Input: Interval endpoints PL,PR PR. accuracy margin d.
if PL - -PRl S then
return PR,
end if'
BR t test R2)
if BR = (1.0) then
return BinarySearch PeLR pn, d)
else
return Binaaryeaaaar.. PLA
end if'
Therefore, by Lemma E. the sequence should satisfy:
Reg2 (f (1))) ===
(e v1) S C f(T)
(108)
1=5
for some constant C, therefore, have:
T Σ (cl vi S S(T).
C
(109)
t=
This would lead to an upper bound on the Stackelberg regret:
StackReg:(A,,4)
4V AVV(AA
Σ
2 Ay TT
(e v1)
t=1
t=5
S ||| max || A|
(el
3/ 00
(110)
< 4||A|lmax + ||A||max f(T).
If neither facets empty, the binary search phase shrinks the interval length from 1 to d, which requires at most log d + 1 calls of the BinarySearch function. Each Binary search calls the procedure test for at most one time, which corresponds to at most two interaction time steps. Therefore, the total number of time steps in the binary search phase is at most -2 log d + 6, leading to a Stackelberg regret of at most (-2 log d + A|] which is O({(T).
Since each facet has length at least d, the pessimistic facets computed by ET and En satisfies du (E,, ET) I 2d and inf se F. s,en, || x'll2 for 1,2. Therefore, combining Lemma E. and Theorem 5.5 we obtain:
[-2 d+6] Σ
SlackRegi A2) < 1 1-2logd+
T 1f
Ay, + of A
Σ
(el y/)
t= log d+6|+1
< (-2 log 6)]|
All
Σ
(01 110
(III)
t= log d+6]+1
2CJ(T)
< (-2 d 6)]l
(2Td+ ed
|| Imax
Discussion matrix reconstruction view. Observe that by Definition 5.6 multiplication by a positive constant and shifting an all-one vector in a row preserves the equivalence class, there are only three possible forms of payoff matrices B:
0 A
0 X
0 A
100
(112)
1
0
-1
29

---

Learning to Steer Learners in Games
In the third case (and the instances where À Assumption 5.12 is satisfied, indicating that this instance is learnable. So we foeus on the first cases where À # 0.
For the first case where
0 A
B
(113)
0 1
for dz (p: p) know that if X then 1f
(0, 1) is dominant action, and when À S 0 we have:
(0, 1) is the best response;
all actions are equivalent;
(114)
p
(1,0) is the best response.
Similarly for the second case where
0
A
B
(115)
0
-1
À then (1, is dominant action and when À 2 0 have:
p (1, 0) is the best response;
= I+X all actions are equivalent;
(116)
p 1+X (0, 1) the best response.
Now we have reduced the problem to identifying the matrix type and finding À (or equivalently, p" where all actions are equivalent to the learner).
E.2. Algorithm 4, Detailed Version and Proof of Theorem 6.3
We present the pseudocode for Algorithm 4 as follows, where the ExploreRow procedure shown in Algorithm 5.
Algorithm Playing Against Mirror Descent
Input: Per-row exploration step k.
for i = 1,2,...,m. do
B, f ExploreRow(e, k)
end for
Construct estimation B [B, B₂
Bml"
Compute the equivalence class B and commit to å through (82) with J(T) VTF(T).
Algorithm Expl oreRow
Input: Action x E Am. exploration step k.
for r = 1,,, k + do
Play x, observe the follower action yr in this time step.
end for return B, = - V
The detailed version of Theorem 6.3 is presented follows:
Theorem E.3. If the learner payoff matrix B statisfies the assumptions needed in Theorem 5.17, P2 follows update rule (25), and each entry Et, is i...d. R-sub- Sabb-Gaussian. then with probability at least 1 5, P1 using Algorithm 4 with (T/g(T))² 2R² log(2mn/6)) incurs Stackelberg regret of at most
m (1 + +4
maxj,k [[ c00 + (TS(T)) Sen((B?))7)+ max;ą B - -x)
STg(T)
C CVT)(T)
|| (117)
where C a constant that depends only on the learner regret constant and payoff matrix.
30

---

Learning to Steer Learners in Games
Proof. The Lagrangian of this problem can be written
L(y, >. nhe D(yllu)) (o) B 1 + pl M yi 1).
(118)
Since 1 is the optimal solution to (25), the KKT condition yields:
I) (VeeyDD(e++lll))) B" 54 - X + 1 E. = 0:
(119)
y/+1, X 0, Vi E [n]]
Since the Bregman divergence regularizer satisfies Vy (yv+++illun - 0c if there exists i E [n]] such that Ut+1,5 -> 0, we can deduce that À = O, and the condition becomes:
B² 24 pl f1 0. Ti V (yo++ill l1v))
(120)
Let h, denote ha := Tue D( we know that
BT x h4 + p4l - E.
(121)
here used Je instead of y indicate the different Lagrange multipliers different time steps. If 24 6j obtain:
B: = h4 + p4 - Ee,
(122)
where B7 is the i-th row of B, so if we fix F2 ez for t = 1 to k; we have the following estimation of B₁:
B h
(123)
with error term:
B. B
&
(124)
The first term doesn't affect the equivalence class of B, and the second term diminishes over time. Hence we can obtain an estimation with arbitrarily small error using uniform exploration. Assuming that each entry & is i.i.d. R-sub-Gaussian, we obtain through Chernoff bound:
ke
Pr
Σ & lo sc)
2n exp exp
(125)
2R²
If we take h:
2R² x log 8
it holds with probability least 1 8/m that
[BB B
eel 1oll S..
(126)
Combining this with Theorem 5.17, we take ( IT), the number of steps to explore one row of B would be:
T ((T)
2mn 2R log 8
k
(127)
When 9(T) R(VT) would have o(T), indicating that the exploration cost would also be sublinear in T. The length of the exploration phase consists of at most m(lk + 1) steps and achieves estimation / in the equivalence class B. We first give an upper bound on ||d B)|| for all i. Notice that:
max B. - B.izllo max [B.... - Brizlloc
J1
31.12
< max
[ - -B -1BB,s, B.szllook
J1
max [I(B -B)(en -102)
J..2
(128)
max (BT -B3 )ej, 032))
Ji.Ja
max max ET(E), e3,)
Ji.Ja
31

---

Learning to Steer Learners in Games
where ş 1 E3 & for all / in this Expl oreRow function call. To make notation simpler, in this proof mildly overload the notation to let:
B, [B,1 B B, B
B.n B..]
B. = [B., B
B,
B.
B B
have:
B,
B:
(B,
m [B,, bl maxj,k |B..j
B. loc
[|Br.h B..zel maxji |B.rj B2 Doo Bi
ma
|B B. 1100 max j1 .22 ||Bris B 1l00
(mmxx,,,.) 12 |B -Ba 1loc max,, |Brrs B, 100)
(129)
[Bas BB 1o00 X maxji ./2 |B:rs Br 1000
max
ma B..i Biii oo (B; B.)
ma | -B llee X max BB B.
2 E B,
B, B. max [B. B.
ja | B. 0o x ja [Bar
Bo
211E11
Since our exploration round & for all ExploreRow function calls, ||E|| I
T ((T))
2R log 2mn we obtain through union bound that with probability least
g(T) which goes to zero as T + for large enough T we have:
xo (max,, Jz .2 |B.j Bi 12o0)
4||5| ||15|10c |
Bi
B) Billoc
|1, [) S
+
max
[B..j
Bo,
4ni|E/1
4n|| b0
max
B B. 1oc
max BB.j B.jz 1oo0
8n||Elloc
(130)
maX
[B... B.,izla
8n
g(T)
maxji.52
|| [B.j
B. loc
T
(TT)
0
T
Therefore, combining Lemma E.1 and Theorem 5.17 we obtain:
StackRegi(AIn A2)
maxx, [B(e; - =xx VT((T) Sen (BB))²) + CVTf(TT
(T)
S <m(k + B), +
||
max,, [ =x)]l
STg(T)
CVTT(TT
mm(k 1)]lA||mma Imax +
VT((TT) Sen ((B%)T)+ + max,, [Bee, - -ex)llo0
||
m BB(e, - =x
o ((T)
+ O( (OVTT((T)))))) + (()))
T 2
0 ((VT((T) + (T +
((T))
(131)
which completes the proof.
32

---

Learning to Steer Learners in Games
F. Numerical Experiments
F.1 Empirical Simulations for Section 6.1
For all experiments this section, we assume the learner is using Online Gradient descent (OGD) with step size
d VE
T
(132)
For the purpose of properly displaying the interaction and learning process, we choose different 700 for different game instances. For each game instance, we compare the performance and learning dynamics for optimizer algorithm being either OGD Binary Search explore-then-comme (BS, Algorithm 1). For Binary Search, set the accuracy margin 0.01. For each game instance, plot both the payoff and the strategy (indicated by its 0-th entry) of each player at different time steps. We assume optimizer is the row player and learner is the column player.
Matching pennies.
We first test repeated matching pennies, where the payoff matrices are given by:
B [
A
(133)
Both the unique Nash equilibrium and the Stackelberg equilibria all have
x = 2
(134)
We obtain the curve shown in Figure 3.
Payoff History
1.00
0.75
0.50
0.25
Payort
0.25
0..50
-0.75
Optimizer, OptAlg BB
-1.00
Learner, Opthii=BS
100
Optimizer, OptAlg-OGD
Strategy History
Learner, Opthig=OGD
Exploration Phase
Optimizer, Stackeiberg
0.0
0.6
20
80
100
Round
Figure 3. Learning dynamics optimizer algorithms OGD and BS for matching pennies.
Here the blue curves represent the learning dynamics when the optimizer uses binary search (Algorithm 1) with the exploration phase shaded in red. The orange curves represent the dynamics when the optimizer uses OGD. In both optimizer
33

---

Learning to Steer Learners in Games
algorithms, the solid lines are eurves for the optimizer and the dashed lines curves for the learner. We plot the optimizer Stackelherg strategy and payoff in black dotted lines.
We can see that when both players are using OGD, the trajectory keeps oscillating and does not converge to the Nash equilibrium. In comparison, when the optimizer uses BS, it quickly learns its real underlying Stackelberg equilibrium (which also the Nash) and commits to it, yielding a stable learning dynamics.
Constructed game instance the following game instance:
Below we show that BS indeed yields a smaller Stackelberg regret than OGD. We construct
5
B
(135)
3
-3
The unique Stackelberg equilibrium action for the optimizer is:
3 2 5' 5
3r
(136)
with Stackelberg value 3. We obtain the curve shown in Figure 4. In Figure all curves drawn with the same line
Optimizer: Steering with BS
Optimizer: OGD
Payoff History
Payoff History
Parolf
1
Optimizer; avgpoyoff
Optimizer, avgpayoff
Optimizer, OptAlg=BS
Leamnrr, OptAlg-BS
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Exploration Phase
Str arateg History
Strategy History
Optimizer, Stackeiberg
Optimizer, Opt
Leamnrr OptAig-OGD
Optimizer, Stackelberg
Stratepf0)
Stratoodo)
0.2
0.2
0.0
0.0
25
100
125
150
175
25
100 Round
125
150
175
200
Figure 4. Learning dynamics for optimizer algorithms OGD and BS for game instance 1.
style as in Figure 3, in addition blue and orange dotted lines to plot the average optimizer payoff for BS and OGD respectively.
We notice again that when the optimizer is using OGD, the algorithm fails to converge. In addition, after the optimizer commits to the pessimistic Stackelberg solution, the learner slowly converges to the best response induced by the Stackelberg equilibrium and steers the optimizer payoff close to the Stackelberg value, which is higher on average than the payoff using SGD.
34

---

Learning to Steer Learners in Games
Constructed game instance One may argue that OGD fails because it doesn't 't converge, however it is not the case. Below construct a game instance that has unique Nash equilibrium which OGD converges, and unique Stackelherg equilibrium with higher optimizer utility than that of Nash. The game instance is follows:
2
0
1
0
A
B
(137)
3
The unique Nash equilibrium is
y= (0.1)²;
(138)
while the unique Stackelberg equilibrium
1/3), .y (1, (1.
(139)
The optimizer payoff Nash is I, while its Stackelberg value The simulation result is shown in Figure 5.
Payoff Histery
2.5
Payolf
1.5
0.5
Optimizer, OptAlg=BS
Leamnrr OptAlg-BS
50
100
150
200
250
300
Optimizer, OpE
Strategy History
Learner, OptAig-OGD
Optimizer. Stackelberg
Straeghi
0.4
0.2
150
Round
Figure 5. Learning dynamics for optimizer algorithms OGD and BS for game instance 2.
The plot above shows that even if both converges, BS and OGD converge completely different equilibria, while BS always yields higher payoff and therefore a lower Stackelberg regret.
E22 Empirical Simulations for Section 6.2
In this section show the effectiveness of Algorithm 4. and illustrate the necessity of pessimism. Here assume the optimizer is using Algorithm 4, but with different pessimism levels d E {0.01, 0.02, 0.05). We assume that the learner is using Stochastic Mirror descent with KI regularizer. For each pure strategy of the optimizer, we set the number of steps for exploration to be & = 50. We consider the following game instance:
0
2
2
A =
B
(140)
0
3
3
35

---

Learning to Steer Learners in Games
The unique Stackelberg equilibrium of this game is
3 2
5
(141)
with optimizer payoff 2. We plot the payoff's and strategies of both player at each time step with different d in Figure
Payoft History
Payolf
Optimizer, d=0.00
dw0.01
Optimizer d-0.02
1000
2000
d=0.02
Strategy History
Optimizer, d=0.05
Leamner, dm0 05
1.0
Exploration Phase
Optimizer, Stackeiberg
Strategyio)
0.0
250
500
750
1000
1250
1500
1750
2000
Figure Learning dynamics of payoff estimation for different pessimism levels d.
In Figure 6, different line colors indicate the learning dynamics of different pessimism levels. The solid lines optimizer curves while the dashed lines being learner curves. The shaded region indicates the exploration phase and the black dotted line represents the optimizer Stackelberg payoff and strategy.
We can see that for larger d, the optimizer being more pessimistic and chooses an action that is farther away from the Stackelberg equilibrium. This leads to a lower optimizer payoff after the learner converges to the unique best response induced by the action. However, for less pessimistic choices of d, since the committed optimizer strategy ă too close the Stackelberg equilibrium where the learner is indifferent from all mixed strategies, the gradients of the learner payoff with respect ă will be extremely small and thus takes lot longer converge. Once it hasn't t converged the optimizer payoff of committing to Z will be smaller, illustrating the effectiveness of being pessimistic.
36

---

Learning to Steer Learners in Games
G. Proof of Auxiliary Lemmas
G.I. Proof of Lemma C.2
The dual problem (71) can written as:
minimize
b" y/
subject to
A y/
(142)
V 2 0,
and that of (72) is:
minimize
(6 + 8)
subject to
A y C,
(143)
2 0.
We can now follow the approach in Section 5.4 and Section 5.5 in (Bertsimas & Tsitsiklis, 1997) to obtain the result: Since both (71) and (72) are feasible and have bounded constraint sets, they have finite optimal value and a corresponding optimal solution, do their dual problems. Therefore for each dual problem there exists optimal solution that is basic feasible solution (which are the same for both dual problems), denoted by U1, U2..... That is,
V = min b" yi
(144)
1=122...
and
V(6) = min
(b + 8) yi.
(145)
i= 11,......!
Therefore we have:
V V = min
(b + o)
min 67 y/
1=1
(146)
< max d'y..
Since for each == 1,2,..., a linearly independent set of columns I of A of size n captures the basic feasible solution (which an independent set rows of A) and y, specified by yi = (Az)² in entries within and elsewhere, we can rewrite 8 y as
8t v 8 cT Azōr.
(147)
which completes the proof.
G.2. Proof of Lemma C.3
Consider an index set I containing linearly independent rows of M that satisfies [Z] = m.
(B
Since all m x m submatrices contain & rows in
1
and m k rows in -Im for some 0 < k S m. Thus My has the
1
form:
MT.
R-1
Mz
(148)
C
12 m-
[B3
where I, denotes the j-th index in I and Mz contains the first & rows selected from
1
Now we show some
1
properties of Mr11 First, since Vi {k +1, 2, ... m) and Vj E [m]] it holds that
i = o = Tij @ (Mz)7 (M Do. G T
(M7
-
=-MM )1,-))),----)
(149)
n
37

---

Learning to Steer Learners in Games
where comes from the definition of Mi' and (ii) holds due (148), have that:
(MT -n- = -
(150)
Second, consider the product for arbitrary A R²
A
M
Σ
(MT "M Do
(151)
O 0m-k
j=l
whose i-th row can be written as:
O k 1)
A
M
Σ
(MF Ag.
(152)
j=1
Let 3 = (Ix+1 - n - 1, I+1 -1
Im n - 11, we can see from (150) that if E E,
a ) O.
Mr
Om 0m-
(153)
Also, consider the product of (M. (Mzz.. for i,j E {m,',E, we have:
15 (7. (T.
(,(2))) +
(M1 (M2
(154)
Σ (MT))a((Mz).))
where (MT = because
(Mz)1.) 0, [k 1,..., E [m]]EE
(155)
as shown in (148). Similarly, for the product of (Mz)s. )is for for E [k], we have:
Ii -M>)),
= Σ (MM)a)(MT)))) )1s + Σ (M
LE|m](E
330
(156)
Σ (ME)),(MM)))n) )n
1E[m]iE
where (M)((M)) = 0 due to
= = [ [k]
(157)
as indicated by (150).
The two equations (154) and (156) above show that if we consider the submatrix of (Mz) (Ml))... consisting of its first rows and columns in {m,),E, its inverse is equal to the corresponding entries of the inverse of M7. More specifically,
(M (mR = (MT)
(158)
Now that we have:
A
M-¹
= -I(M5 ),,p Alloo (MM))) mi Aloo (M,
(159)
0m-k
38

---

Learning to Steer Learners in Games
where again (i) holds due (157). Since the selection of Z is arbitrary, & can also be constructed arbitrarily, so the upper
bound for MI O
would be
(B:)
max Z,8
max P,0
1
A
(160)
P.
20
where the maximization is over all P, Q that satisfies:
(B: T
P |n], Q 1
invertible.
(161)
P.Ω
Also, because the entries corresponding to = and are perturbed, we can multiply those constraints by arbitrary nonzero and still get the same result, which completes the proof.
G.3. Proof of Lemma C.4
Given that |- 1, we can expand the series (I B-) -1 convergent Neumann series:
(I + B-B (-B
(162)
km0
So that (I (-B)-B well-defined. As result,
(B (B+ (B(T + BB (T B 88) B-
(163)
also well-defined, and further
5B)
+|[[+ B- B- -||
=||-+1|||
Σ 8BB
k=0
B
|| (- B 1
(164)
k=0
B
| 1
|8811
k=0
|B-1
1
B |
88
which completes the proof.
39


Reviews:
[{"review_id": "hpbK6gotGH", "reviewer": "Reviewer_r9Wp", "summary": "The authors propose a new method to steer no-regret learners to a stackelberg equilibrium in repeated two player bimatrix games. There are two main contributions, The first is an impossibility result that there exists a no-regret learner that prevents an optimizer from achieving the stackelberg equilibrium when the learner's payoff matrix is unknown. However, with information about thel earner's  payoff matrix, the authors show that it is indeed possible to for the optimizer to steer the learner to the Stackelberg equilibrium.\n\nUsing the above two sufficient conditions, the paper argues that if we know that the learner is using an ascent algorithm, the optimiser can attain a sublinear regret by using a Binary Search algorithm (appendix E.1) to search through the simplex to estimate the pessimistic facets of the learner. Similarly, if the learner is known to use a mirror ascent algorithm with a known regulariser, it is possible to estimate the payoff matrix up to the equivalence class.\n\n## update after rebuttal\nAfter the inclusion of the experiments, I increase my score to a 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Before addressing the concerns, we would like to thank the reviewer for carefully reading the paper, providing insightful feedbacks and pointing out related empirical fields, all being really helpful for improving our work. Pleas find our response listed section-wise below:\n\n### Methods and Evaluation Criteria:\n> *\"There doesn't seem to be much comparison to other methods...\"*\n\nTo the best of our knowledge, our work is among the earliest to consider the problem of steering a no-regret learner to Stackelberg equilibrium *without* knowing its payoff structure. The only work close to this setting is [Brown et al., 2023](https://arxiv.org/pdf/2305.19496) but their method is only able to learn an approximate Stackelberg equilibrium efficiently when the learner is no-adaptive-regret, i.e. the learner regret between arbitrary time intervals should be bounded. Since we are considering a more general setting, establishing a fair comparison between our method and other methods can be challenging.\n### Experimental Designs Or Analyses:\n> *\"There is no empirical evaluation (which I think is a major weakness). It also seems unusual to have knowledge of the regularizer...\"*\n\nWe focus on the theoretical perspective of this problem and our main contribution is both the impossability result and---in light of this--- a few sufficient conditions under which no-Stackelberg regret is possible with provable upper bounds. We are happy to include empirical evaluation to illustrate the effectiveness of our result in the revision. Preliminary results seem to be in keeping with our theory. For the assumption of knowing the regularizer, please refer to **Question For Authors** part.\n\n### Relation To Broader Scientific Literature:\n> *\"... it would strengthen the paper to include more big-picture results beyond m = n = 2.\"*\n\nIndeed similar result holds for arbitrary $m$ as long as $n=2$. The idea is to separately treat each edge of the simplex as a special instance of the $2\\times 2$ case. See Page 8, Line 428-439 and Appendix E.1 for more discussion. Please also refer to **Other Strengths And Weaknesses** section of our reply to reviewer abnn for the hardness when $n>2$.\n\n### Essential References Not Discussed:\n> *\"I would have expected some references to the machine learning communities work on opponent shaping...\"*\n\nThank you for pointing out these references. This is a relavant set of ideas that is related, though focuses on a different goal/situation.\n\nFor the reference *\"Foerster, Jakob N., et al. (2017).\"*, they studied 2-player stochastic games with one learner provides conventional policy gradient while the other iterates in a one-step lookahead manner. The reference focus on *convergence* to equilibria, and assumes the learner has knowledge of the update rule, value functions and gradients of *both* agents *at the current time step*, while our work focus on *steering* the learner to *Stackelberg Equilibria* only assuming the optimizer knows the regularizer of the learner. \n\nFor the reference *\"Lu, Christopher, et al. 2022.\"*, which considered learning to play against other learning agents strategically, they formulated the meta games of partially observable stochastic games and designed a model-free algorithm that does meta-learning on the constructed MDP. Their work requires resetting the underlying POSG environment, while in our work we assume an online learning process where the optimizer minimizes its Stackelberg regret based on one single gameplay trajectory.\n\n### Questions For Authors:\n\n> *\"...whether knowing the opponent's regularizer is a reasonable assumption, or if this can be relaxed...\"*\n\nThis is a very interesting question and something we thought about but were unable to circumvent. Our results give sufficient conditions when steering a learning agent is possible (which in view of our impossibility result is a hard problem in general). To do so we decided to focus on classes of algorithms for the follower that were commonly analyzed and used for learning in matrix games. Towards this we identified that most common algorithms for matrix games are based around the idea of multiplicative weights (or Hedge/exponentiated gradients) which is the result of using the negative entropy as a regularizer. The second other common class is projected gradient descent which results from the use of the $L_2$ Euclidean norm. Against both of these algorithms we showed that efficient steering is indeed possible. \n\nThe requirement of knowing the geometry in which the follower optimizes is strong but seems to be crucial for efficiently learning to steer them, since it allows the leader to glean information about $B$ from observation of their consecutive actions (and not have to wait for the follower to converge as in other papers). We believe it is a very interesting open problem whether the follower using mirror descent with arbitrary regularizers inadvertently reveals information about their payoff B in such a fine grained manner.", "claims_and_evidence": "The claim for the impossibility result is convincing. The main result focuses on the idea of discovering the learner's payoff matrix by characterizing the learner's best response through facets of the learner's action polytope. The authors do take care to consider the pessimistic case, where if the learner is indifferent, it chooses the action that would be worse for the leader. The proofs appear to be rigorous and generally well-written. I couldn't find any obvious errors.", "methods_and_evaluation_criteria": "There doesn't seem to be much comparison to other methods. There are no experiments to showcase the power of this algorithm vs other benchmarks, even on simple games. While the theoretical results are thorough, it would help if there was more discussion on how these theoretical results compare to existing literature, or why other methods might not work in these cases.", "theoretical_claims": "The theoretical claims appear to be valid. The impossibility result is proved with a counter-example. The requirement for disjoint pessimism seems reasonable (it maybe helpful to connect this to the non-existence of weak Stackelberg equilibria), and the extension to equivalences classes also seems correct.", "experimental_designs_or_analyses": "There is no empirical evaluation (which I think is a major weakness).  It also seems unusual to have knowledge of the regularizer. Maybe the authors could comment more on this assumption.", "relation_to_broader_scientific_literature": "I think the paper did a good job of discussing related work. It is interesting to explore shaping, especially as AI systems become more ubiquitous. I would say, that while the theoretical results appear strong, it would strengthen the paper to include more big-picture results beyond _m = n = 2.", "essential_references_not_discussed": "I would have expected some references to the machine learning communities work on opponent shaping\n\nLu, Christopher, et al. \"Model-free opponent shaping.\" International Conference on Machine Learning. PMLR, 2022.\n\nFoerster, Jakob N., et al. \"Learning with opponent-learning awareness.\" arXiv preprint arXiv:1709.04326 (2017).", "other_strengths_and_weaknesses": "n/a", "other_comments_or_suggestions": "n/a", "questions_for_authors": "I would be interested in the authors' comments on whether knowing the opponent's regularizer is a reasonable assumption, or if this can be relaxed. Maybe it is enough to know that they _are_ regularized, but not the exact quantity?", "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": "mNWPlKQ8i4", "reviewer": "Reviewer_DWLF", "summary": "This paper studies the problem of learning the Stackelberg equilibrium against an unknown follower who plays against the leader with some no-regret learning algorithm. They first show a negative result, which shows that this is impossible if no information about the follower is known by the leader. Then they propose sufficient conditions under which the follower can be exploited and design an algorithm that achieves tight sublinear Stackelberg regret. Finally, they provide two specific examples about the update rule of follower’s algorithm which allows the leader to steer to the Stackelberg equilibrium.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would first like to thank the reviewer for thoughtful review and recognition of the novelty in the research topic we proposed. Please find our response listed section-wise below:\n\n### Other Strengths And Weaknesses:\n\n> *\"...I find the contribution of Section 6 unclear, where learning to steer to the Stackelberg equilibrium with non-sublinear regret... \"*\n> *\"... One could apply an efficient learning algorithm from the literature to infer the follower’s type and then leverage the strategy outlined by Deng et al. (2019) to address the problem... This alternative approach would likely achieve similar performance and theoretical properties...\"*\n\n\nThere may be some confusion in how we presented our results and we are happy to clarify/simplify the presentation in the revision. We show in Section 6 that the Stackelberg regret is vanishing in both cases. In Theorem 6.2, $d$ is a tunable parameter in our algorithm, indicating the binary search accuracy level. Choosing $d=\\sqrt{f(T)/T}$ would yeild a $\\sqrt{Tf(T)}$ regret overall. In Theorem 6.3, $g(T)=o(T)$ and thus the regret vanishes asymptotically there as well. We tried to keep our results general but can clarify/instantiate these quantities in the revision to highlight our results.\n\nThe goal of section 6 was to give sufficient conditions under which steering a learning agent to a Stackelberg equilibrium is possible (in the sense that the Stackelberg regret is vanishing in time). Our impossibility results hints that this is a hard goal against arbitrary no-regret learers, and so we wanted to understand what further restrictions we could make on the follower for the leader to succeed. To that end, we identified two sub-classes of no-regret algorithms in which our problem can be efficiently addressed: (1). ascending learners  in games with two actions, and (2). general mirror descent learners (with known regularizers) in general games. While the class in (1). is quite broad, we could only prove that efficient steering is possible in a limited case. For the class of follower algorithms in (2). we based the case on the observation that by far the most common no-regret algorithm for games in Hedge or multiplicative weights which is an instantiation of mirror descent with a negative entropy regularizer. Our results in this section are positive in the sense that it is possible to exploit learning agents in games under some (often realistic) assuption on their algorithm. \n\nUnfortunately in both of these cases the approach of learning the type and then using results from [Deng et al., 2019](https://arxiv.org/abs/1909.13861) is not straighforward. The follower's type is actually their payoff matrix, and learning the follower's mayoff matrix through interaction is  highly non-trivial--especially if one would like to do this efficiently and not wait for the follower to converge. Our solution is to make further assumptions on the type of algorithm the follower is using, and then use the strucure to help us learn the payoff matrix. Even this is nontrivial as can be seen in our results in Section 6. Furthermore, even if the optimizer has an approximation of the learner payoff matrix, since the method proposed in [Deng et al., 2019](https://arxiv.org/abs/1909.13861) is pessimistic by a unadjustable constant $\\alpha$, as long as the learner's payoff structure is not recovered in an absolutely accurate way, directly applying the method in [Deng et al., 2019](https://arxiv.org/abs/1909.13861) would either be not pessimistic enough, such that the regret budget of the learner allows it to deviate from the Stackelberg equilibrium far enough to incur a huge Stackelberg regret, or be overly pessimistic, such that the pessimism itself brings a linear Stackelberg regret to the optimizer.\n\n\n### Questions For Authors:\n\n> *\"Can you elaborate on the contribution of non-sublinear Stackelberg regret in Section 6?\"*\n\n\nThank you for raising this question. We would like to emphasize that we are still assuming the learner to be no-regret in both parts in Section 6. More specifically, in Section 6.1, while Definition 6.1 does not imply an ascent algorithm being no-regret itself, we still need the no-regret property for the learner to drive it to an approximate best-response after having learned its paryoff structure. Meanwhile, many online ascent algorithms, e.g. online gradient ascent with proper step size, are themselves no-regret. In Section 6.2, stochastic mirror ascent with proper step size is no-regret as long as its regularizer is strongly convex. We will make a clear statement regarding this in our revision.", "claims_and_evidence": "yes.", "methods_and_evaluation_criteria": "yes.", "theoretical_claims": "I did not check the correctness of proofs.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "This paper is related to the literature of learning in Stackelberg games and strategizing against no-regret learners.", "essential_references_not_discussed": "I did not notice any essential reference not being discussed", "other_strengths_and_weaknesses": "On the positive side, this paper considers a learning approach to learning the Stackelberg equilibrium against no-regret followers with unknown type information. I found the problem presented by the paper interesting, and relevant. In general, this paper proposed an innovative research topic.\n\nOn the other hand, I find the contribution of Section 6 unclear, where learning to steer to the Stackelberg equilibrium with non-sublinear regret. This suggests that the regret does not vanish asymptotically, which raises concerns about the effectiveness of the proposed learning approach. One could apply an efficient learning algorithm from the literature to infer the follower’s type and then leverage the strategy outlined by Deng et al. (2019) to address the problem of strategizing against no-regret learners when the follower’s type is known. This alternative approach would likely achieve similar performance and theoretical properties, making it unclear what additional value the proposed method in Section 6 provides.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "Can you elaborate on the contribution of non-sublinear Stackelberg regret in Section 6?", "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": "APD4qRZhJx", "reviewer": "Reviewer_abnn", "summary": "This paper studies repeated two-player Stackelberg games where the follower (learner) uses a no-regret algorithm to choose responding actions and the leader (optimizer) aims to play against the learner.  Unlike most previous works (e.g., [Deng et al, 2019]) that assume that the optimizer knows the learner's utility matrix, this work drops this assumption and aims to study under what conditions the optimizer can achieve the Stackelberg equilibrium value: \n\n(Result 1) First, the authors show a negative result: if the learner's utility matrix is unknown and its algorithm can be any no-regret algorithm, then the optimizer cannot achieve the Stackelberg value. \n\n(Result 2) Second, the authors show that, if the optimizer knows the learner's utility matrix or best-response functions up to some small error, then it can almost achieve the Stackelberg value (using the idea of pessimism to deal with the error). \n\n(Result 3) Finally, the authors show that, if the learner's utility matrix is unknown but its algorithm is either any ascent algorithm or a stochastic mirror ascent with known step sizes and regularizer, then the optimizer can learn the learner's utility matrix (approximately) and then achieve the Stackelberg value.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the great amount of time and thought the reviewer has invested in evaluating our manuscript. We are grateful for the precise recognition of our contribution and novelty, and the insightful feedbacks allowing us to refine and improve our work. We address each concern section-wise below:\n\n### Essential References Not Discussed:\n\n> *\"(Minor weakness 1)...\"*\n\nThank you for mentioning the related works and your interpretation. While both mentioned works considered potential suboptimal learner responses, neither considers unknown (or up to a small error) learner utility. We would especially like to highlight the difference between our work and [Gan et al., 2023](https://arxiv.org/abs/2304.14990), which also considered a region of $\\delta$-optimal response, where the learner's action is with suboptimality at most $\\delta$. Although being in a similar to the definition of pessimistic facet in Definition 5.7, their definition relies on the real underlying payoff matrix $B$ when defining the region, compared to our definition that uses the *estimated* payoff matrix. This is saying, that the boundary of their $\\delta$-optimal region would be parallel to the real underlying $0$-optimal response region, making their bound easier and more straightforward compared to that in our work. The mismatch in boundary direction in our work requires us to come up with a novel proof of Lemma 5.14 in Appendix C.4, which links the optimistic/pessimistic value difference to the real underlying learner payoff through Definition 5.13, which in our opinion is both a conceptual and technical contribution of our work. We will cite these works and provide further discussion in the revision.\n\n### Other Strengths And Weaknesses:\n\n> *\"(Minor weakness 2) ...\"*\n\nWe impose the assumption $n=2$ because only in this case can we apply binary search on facet estimation. For $n>2$ case, our method wouldn't directly apply because there could be infinitely many ascent direction for $n>2$, and thus the difference between $y_{t+1}$ and $y_t$ no longer fits the binary search algorithm. This is the main reason why we neede more structure in the follower's algorithm as in the section on Mirror Descent. For the assumption of knowing the regularizer, please refer to **Questions for Authors** part of our reply to Reviewer r9Wp for details.\n\n### Other Comments Or Suggestions:\n\n> *\"(Comment 1) ...\"*\n\nThank you for raising this point. First, we would like to specify that $\\epsilon>0$ is encoded within the condition $\\inf_{x\\in E_{i}^-,x'\\in E_j} \\Vert x-x'\\Vert_1 \\geq d_2$, which essnetially suggests that each point in $E_i^-$ is at least $d_2$ away from other facets. More specifically, this means in line 795, $x^-$ is not in $E_j$ for all $j\\neq i^-$, and by definition of $E_j$, $\\exists j'$, s.t. $(x^-)^TBe_j<(x^-)^TBe_{j'}$. Since such existence of $j'$ holds for all $j\\neq i^-$, we can deduce that $(x^-)^TB e_{i^-}-(x^-)^T B e_j>0, \\forall j\\neq i^-$. For those $j$ where $E_j=\\emptyset$, since here $d_2$ satisfies $d_2\\leq 2$, we can take $\\epsilon_1=\\frac{1}{2}\\min_{x\\in\\Delta_m,j\\neq i^-}\\{x^TB e_{i^-}-x^T B e_j\\}$ such that equation (44) holds, which is indeed similar to the inducibility gap defined in Definition 5.9 but we are only taking minimum over those $j$ with empty $E_j$, automatically satisfying $\\epsilon_1>0$. For other $j$ since $x^-$ is at least $d_2$ away from $E_j$, there must be a constant $\\epsilon_2> 0$ such that $(x^-)^TB e_{i^-}-(x^-)^T B e_j\\geq \\epsilon_2 d_2$. We proceed the proof by taking $\\epsilon=\\min \\{\\epsilon_1,\\epsilon_2\\}$.\n\n> *\"(Comment 2) ...\"*\n> *\"Regarding both comments...\"*\n\nThe purpose of allowing a constant scale is that we want to:\n\n1). Focus on the asymptotic behaviour of the learner's algorithm;\n\n2). Highlight the *rate* at which the regret is growing in the bound;\n\n3). Keep the $f$-no-regret property invariant when dealing with the same interaction sequence in the same equivalence class.\n\nOur purpose 2) requires the definition of $f$-no-regret itself does not contain any asymptotic notation, and our purpose 1) requires  any optimizer's exploration phase that is of length $O(f(T))$ won't affect the overall $f$-no-regret property of the learner (see Lemma E.1), which is essential to our proofs of Theorems 6.2 and 6.3. Even if we modify the definition to $Reg_2\\leq f(T)$ without the constant, the exploration phase would still induce another constant $C'>C$ which will appear in the final bounds in Section 6 since we have to use Lemma E.1.\n\n> *\"(Typo)(Small issue 1)(Small issue 2)\"*\n\nThanks for pointing out the typo and these issues. We will fix them in the revision.\n\n### Questions For Authors\n\n> *\"(Q1) Can you clarify what important constants are hidden in the big $O(\\cdot)$ notation in Theorem 5.4, Theorem 5.15, Theorem 6.2, and Theorem 6.3?\"*\n\nPlease refer to our reply in **Other Strengths And Weaknesses** section to reviewer 2TDF for a more detailed bound without the big $O(\\cdot)$ notation.", "claims_and_evidence": "Yes, the claims are supported by clear and convincing theoretical arguments.", "methods_and_evaluation_criteria": "The techniques used to prove the three main results all make sense to me.  On the positive side:\n\n(Strength 1) The technique for Result (1) includes a non-trivial construction of two utility matrices and learner's no-regret algorithms that prevent the optimizer from achieving the Stackelberg value.  This is an interesting technical contribution. \n\n(Strength 2) The technique for Result (3) shows how to make use of the specific properties of popular no-regret algorithms (gradient ascent algorithm and stochastic mirror ascent algorithm), combined with binary search, to estimate the utility matrix of the learner.  This idea is interesting and might inspire some follow-up works.", "theoretical_claims": "Yes, I checked most of the proofs and didn't find any major issues, except for some minor notational unclarity (which I described in Other Comments and Suggestions) that does not affect my judgment for the correctness.", "experimental_designs_or_analyses": "No experiments.  This is fine to me given the theoretical nature of this work.", "relation_to_broader_scientific_literature": "(Strength 3) The authors did a great job of discussing the relationship with previous works.\n\nThere are previous works about playing against no-regret learners in Stackelberg games (mentioned in the \"Steering no-regret learners\" paragraph) assuming known utility.  There are also previous works (mentioned in the \"Learning in stackelberg games\" paragraph) about learning the agent's utility matrix for a myopically best-responding agent.  This work simultaneously fills the gaps of these two strands of literature by considering learning unknown utility of a no-regret learning agent.  This is a significant conceptual contribution to both strands of literature.  More interestingly, this work gives a negative result -- learning the unknown utility of a no-regret learning agent is impossible in general.  This negative result can be a good reference for future works that explore conditions for positive results.", "essential_references_not_discussed": "(Minor weakness 1) Result (2) says that the optimizer can approximately achieve Stackelberg value if he knows the learner's utility matrix up to some small error.  This idea has been known in the literature, e.g., [Gan et al, 2023](https://arxiv.org/abs/2304.14990) (which is cited) and [Lin & Chen, 2024](https://arxiv.org/abs/2402.09721) (which is not cited).  Nevertheless, I am not too worried about this weakness, because Result (2) is more of a building block for Result (3), instead of the main conceptual contribution.", "other_strengths_and_weaknesses": "(Minor weakness 2) The positive Result (3) for special no-regret learning algorithms seems weak.  For example, the result for any ascent algorithm (Theorem 6.2) is restricted to $n=2$ (number of optimizer's actions), which is not very complete.  The result for stochastic mirror ascent (Theorem 6.3) requires the optimizer to know the regularizer and step size) of the learner, which seems to be a strong assumption.\n\nBut I think the major contribution of this work is the negative Result (1), and Result (3) is more of a \"proof of concept\" that some positive results can be obtained for special no-regret learning algorithms.  So, I am not very worried about this weakness.", "other_comments_or_suggestions": "(Comment 1) The $O(\\cdot)$ notation in Theorem 5.4 hides a quantity that depends on the learner's payoff matrix.  According to the proof of Theorem 5.4 in Appendix B.2, the $O(\\frac{f(T)}{d_2})$ term is actually $\\frac{2f(T)}{\\epsilon d_2}$ where $\\epsilon$ is a quantity that depends on the matrix B.  I think this quantity is related to the inducibility gap defined in [Gan et al, 2023], and the assumption that $\\epsilon > 0$ is required.  Some clarification regarding this hidden quantity would be appreciated. \n\n(Comment 2) In the definition of equivalent classes of utility matrices (Definition 5.5), you allow scaling both $cB'$  and shifting $+\\mu 1_n^T$.  Although scaling by $c$ does not change the best-response set $BR(B, x)$, it does change the learner's regret by the same scaling factor $c$.  This scaling factor will then affect the optimizer's Stackelberg regret -- it is another quantity hidden inside the big $O(\\cdot)$ notation in Theorem 5.4.\n\nRegarding both comments, hiding quantities (that are not necessarily constants) in big $O(\\cdot)$ notation is not a good practice because it might cause analytical errors.  I would suggest the authors to not hide any important quantities in the big $O(\\cdot)$ notation.  Relatedly, in the definition of $f$-no-regret (Definition 3.2), instead of defining $Reg_2 \\le C\\cdot f(T)$ for some constant $C$, directly define $Reg_2 \\le f(T)$ without any constant.  In that case, if a learner algorithm is $f$-no-regret on $B$, then it is $cf$-no-regret on the scaled matrix $cB$, and the optimizer's Stackelberg regret will have a term like  $\\frac{cf(T)}{c\\epsilon d_2} = \\frac{f(T)}{\\epsilon d_2}$, I think. \n\n(Typo) Page 5, Line 268: capitalize \"while\". \n\n(Small issue 1): Page 5, \"At a Stackelberg equilibrium the learner must be indifferent between multiple pure strategies\". I would say \"the learner is usually indifferent between multiple pure strategies\" instead.  There are some degenerate cases where the learner needs not be indifferent. \n\n(Small issue 2): Page 6, line 324 - 325: maybe mention \"$k\\ne i$\" and clarify that $B_i^\\circ$ has $n-1$ columns, with the $i$-column excluded.", "questions_for_authors": "(Q1) Can you clarify what important constants are hidden in the big $O(\\cdot)$ notation in Theorem 5.4, Theorem  5.15, Theorem 6.2, and Theorem 6.3?", "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": "Vhuzr4ANn6", "reviewer": "Reviewer_2TDF", "summary": "The work extends the work by Deng et al, 2019, in showing that one of the key elements of steering is the knowledge of $B$ (Section 4). The authors give some results for steering under (pessimistic) approximations of the 'best response regions' (Def. 5.1) (Section 5) and show upper and lower bounds (Section 5.3 and 6) on the Stackelberg regret (Def 3.5). This is done under the assumption that the learner uses a specific kind of no-regret algorithm and the optimizer uses a 'explore then commit' strategy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful assessment and constructive critiques, which is essential for us to further improve our work. We give section-wise responses and clarifications to the mentioned issues.\n\n### Essential References Not Discussed:\n\n> *\"The authors might also consider referring to 'AN INFORMATION-THEORETIC APPROACH TO MINIMAX REGRET IN PARTIAL MONITORING', Lattimor, Szepesvári, 2019 after Definition 5.1. The idea and analytic purpose of $C_a$ in the reference and of E_i are very similar (identical in definition).\"*\n\nThank you for pointing out the references. The definition of $C_a$ is indeed conveying the same information of characterizing the region of point against which a specific action is a best response, and their discussions on the intuition behind $C_a$ and the illustrations in the appendix also work for our definition of facets. We will add this work into citation in our revised version.\n\n### Other Strengths And Weaknesses:\n\n> *\"... I find the use of asymptotic notation and early switch to this in the proofs a bit dangerous. There are some steps I can not see/verify from the proofs due to early hiding of the constants or since some dependencies are not shown explicitly. (Please, see question to the authors). I am happy to revise my evaluation if my concerns are addressed.\"*\n\nHere we present the exact bounds for the following theorems, in Theorems 5.4 and 5.15 the learner regret bound is indicated by $Cf(T)$:\n\nTheorem 5.4: $\\epsilon>0$ is a constant that depends on $B$, please see our reply to (Comment 1) in **Other Comments Or Suggestions** section to Reviewer abnn for details.\n\n$$\n\\left(Td_1+\\frac{2Cf(T)}{\\epsilon d_2}\\right)\\|A\\|_{\\max};\n$$\n\nTheorem 5.15:\n\n$$\n\\left(4(\\|d _i(\\mathcal{B},\\hat{\\mathcal{B}})\\| _{\\infty} T+\\sqrt{Tf(T)}) Sen((\\mathcal{B} _{i^*}^\\circ)^T) +\\frac{C\\sqrt{Tf(T)}}{\\max _{j,k} \\|B(e_j-e_k)\\| _\\infty}\\right)\\|A\\| _{\\max};\n$$\n\nFor the two theorems below, we assume the adjusted learner regret rate after the exploration phase is indicated by $Cf(T)$, see response to Reviewer abnn and Lemma E.1 for details.\n\nTheorem 6.2: If there exists a strictly dominated action, let $\\epsilon_1=\\min_{x\\in\\Delta_m} x^T B(e_1-e_2)$,\n\n$$\n\\left(4+\\frac{C}{\\epsilon_1}f(T)\\right) \\|A\\|_{\\max};\n$$\n\nOtherwise, $\\epsilon_2>0$ is a constant that depends on $B$ (as a result of Theorem 5.4) and $d$ is a tunable parameter of the algorithm (see **Questions For Authors** section):\n\n$$\n\\left(-2\\log d+5+Td+\\frac{2Cf(T)}{\\epsilon_2 d}\\right)\\|A\\|_{\\max};\n$$\n\nTheorem 6.3: Here $k=\\left(T/g(T)\\right)^2 2R^2\\log(2mn/\\delta)$, $g(T)=o(T)$ is a tunable parameter of the algorithm deciding the length of exploration rounds, \n\n$$\n\\left(m\\left(1+k\\right)+4(g(T)+\\sqrt{Tf(T)})Sen((\\mathcal{B} _{i^*}^\\circ)^T)+\\frac{C\\sqrt{Tf(T)}}{\\max _{j,k} \\|B(e_j-e_k)\\| _\\infty}\\right)\\|A\\| _{\\max}.\n$$\n\nWe will include a version of our theorems in the detailed format with exact bounds in our revision. For the usage of asymptotic notations, please also refer to our reply to (Comment 2) in **Other Comments Or Suggestions** section to Reviewer abnn for details.\n\n\n### Other Comments Or Suggestions:\n\n> *\"In Appendix E, equation (104) and following, it should be $T$ not $\\infty$ ?\"*\n\nThank you for pointing out, this is a typo and we will correct this in the revision.\n\n### Questions For Authors:\n\n> *\"How is $d$ related to $\\epsilon$ in the proof of Theorem 6.2? In particular, how is it ensured that $\\epsilon$ is a constant, although $\\epsilon$ depends on $d$ and $d$ depends on $T$? ...\"*\n\nWe apologize for causing the confusion. Here $d$ is an accuracy margin that is used as an adjustable input to Algorithm 1 which we didn't mention in the main body. The idea is that we do binary search until we have identified the boundary of the facets by an accuracy level of at most $d$. We then stick to the pessimistic Stackelberg equilibrium for the remaining time steps, paying a total cumulative regret of $dT$. The statement between Lines 1412 and 1414 is indeed confusing, and from which \"... the assumption that each facet has length at least $d$ indicates that ...\" should be deleted from this sentence. What we are trying to say is that since $e_2$ is strictly dominated, we would have $x^TBe_1-x^TBe_2>0,\\forall x\\in\\Delta_m$, so that such constant $\\epsilon$ exists and is only dependent on $B$ instead of $d$.\n\nThe reason why we leave $d$ in the big $O(\\cdot)$ notation is that we want to leave some freedom for choosing $d$ as a function of $T$ for different $f(T)$. For example if we choose $d=\\sqrt{f(T)/T}$ the regret bound would be $O(2\\sqrt{Tf(T)}+\\frac{1}{2}\\log\\left(\\frac{T}{f(T)}\\right))$. Here we omit the result $O(f(T))$ obtained in the case where one facet is empty because $O(\\frac{f(T)}{d}+dT-\\log d)$ is always $\\Omega(f(T))$ as long as $f(T)$ is $O(T)$ no matter what $d$ is chosen.\n\nThank you for recognizing and pointing this out. We will make the above point clear in the revision.", "claims_and_evidence": "All claims are supported by proofs. However, some of them I could not verify.", "methods_and_evaluation_criteria": "This is theoretical work, thus, evaluation with benchmark datasets or similar empirical methods is not relevant.", "theoretical_claims": "I checked some proofs, (Appendix A and E)", "experimental_designs_or_analyses": "This is theoretical work, so no experiments are provided.", "relation_to_broader_scientific_literature": "The work complements the work by Deng et al, 2019 and falls within the brought literature of steering no-regret learners in a game.", "essential_references_not_discussed": "The authors might also consider referring to \n'AN INFORMATION-THEORETIC APPROACH TO MINIMAX REGRET IN PARTIAL MONITORING', Lattimor, Szepesvári, 2019 \nafter Definition 5.1. The idea and analytic purpose of $C_a$ in the reference and of E_i are very similar (identical in definition).", "other_strengths_and_weaknesses": "The paper is mostly well written. I am leaning towards 'accept', however, a few things should be clarified. Especially, I find the use of asymptotic notation and early switch to this in the proofs a bit dangerous. There are some steps I can not see/verify from the proofs due to early hiding of the constants or since some dependencies are not shown explicitly. (Please, see question to the authors).\nI am happy to revise my evaluation if my concerns are addressed.", "other_comments_or_suggestions": "small:\n- In Appendix E, equation (104) and following, it should be $T$ not $\\infty$?", "questions_for_authors": "How is $d$ related to $\\epsilon$ in the proof of Theorem 6.2? In particular, how is it ensured that $\\epsilon$ is a constant, although $\\epsilon$ depends (?) on $d$ and $d$ depends on $T$? (this would be needed for the last step in (106) to the best of my understanding)", "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": {"ethical_review_concerns": "None."}}]

Author rebuttal:

Meta-review: After somewhat extensive discussion with the authors, all reviewers agree the paper should be accepted.  I'd encourage the authors to consider the various feedback and discussions as they create the final version of the paper.
Decision: Accept (poster)