Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents
Authors: Nika Haghtalab
Chara Podimata
Kunhe Yang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: calibration
Stackelberg games
learning in repeated games
strategic agents
best response
strategic classification
Stackelberg Security Games
TL;DR: We introduce and study learning in a new class of games called "Calibrated Stackelberg Games" (CSGs) where the agents can only form calibrated forecasts about the principal's strategies (as opposed to having full knowledge of them).

Abstract: In this paper, we introduce a generalization of the standard Stackelberg Games (SGs) framework: _Calibrated Stackelberg Games_. In CSGs, a principal repeatedly interacts with an agent who (contrary to standard SGs) does not have direct access to the principal's action but instead best responds to _calibrated forecasts_ about it. CSG is a powerful modeling tool that goes beyond assuming that agents use ad hoc and highly specified algorithms for interacting in strategic settings to infer the principal's actions  and thus more robustly addresses real-life applications that SGs were originally intended to capture. Along with CSGs, we also introduce a stronger notion of calibration, termed _adaptive calibration_, that provides fine-grained any-time calibration guarantees against adversarial sequences. We give a general approach for obtaining adaptive calibration algorithms and specialize them for finite CSGs. In our main technical result, we show that in CSGs, the principal can achieve utility that converges to the optimum Stackelberg value of the game both in _finite_ and _continuous_ settings and that no higher utility is achievable. Two prominent and immediate applications of our results are the settings of learning in Stackelberg Security Games and strategic classification, both against _calibrated_ agents.

Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents
Nika Haghtalab', Chara Podimata', and Kunhe Yang'
University of California, Berkeley, (nika, htthr/annggbbreeeeeeeereee MIT & Archimedes, podimata@mit.edd
Abstract
In this paper, introduce generalization of the standard Stackelberg Games (SGs) framework: Calibrated Stackelberg Games (CSGs). In CSGs, principal repeatedly interacts with agent who (contrary standard SGs) does not have di- rect access to the principal's s action but instead best-responds to calibrated forecasts about it. CSG is powerful modeling tool that goes beyond assuming that agents use ad hoc and highly specified algorithms for interacting in strategic settings and thus more robustly addresses real-life applications that SGs were originally intended to capture. Along with CSGs, we also introduce a stronger notion of calibration, termed adaptive calibration, that provides fine-grained any-time cali- bration guarantees against adversarial sequences. We give general approach for obtaining adaptive calibration algorithms and specialize them for finite CSGs. In our main technical result, we show that in CSGs, the principal can achieve utility that converges to the optimum Stackelberg value of the game both in finite and continuous settings, and that no higher utilityy is achievable. Two prominent and immediate applications of our results are the settings of learning in Stackelberg Security Games and strategic classification, both against calibrated agents.
Introduction
Stackelberg games (SGs) are canonical model for strategic principal-agent interactions, considering principal (or "leader") that commits strategy h and agent (or "follower") who observes this strategy and best respond by taking action BR(h) These games are inspired by real-world applications such economic policy design (where tax policymaker establishes rules for triggering audits before taxes are filed), defense (where a principal allocates security resources to high-risk targets before vulnerabilities
exploited) and many more, see e.g., [7, 22, 49, 35, 21, 15, 17]. By anticipating the agent's 's best-response, principal who knows the agent's 's payoff function can calculate the optimal Stackelberg strategy guaranteeing her utility V** In recent years, repeated SGs have gained popularity in addressing settings where the agent's payoff function is unknown to the principal. In this setting, the principal, who can only observe the agents' actions, aims to deploy sequence of strategies h1,..., hy over 7 rounds whose average payoff is at least as good as V i.e., the value of her optimal strategy had she known the agent's 's payoff's in advance.
Despite the original intent, repeated SGs are often studied under strict assumptions on the agent's knowledge and algorithmic behavior. Examples include requiring the agent best respond per round using BR(h,) [7, 21], necessitating the agent to precisely know the principal's strategy at all times (e.g., the attacker must anticipate the exact probabilistic allocation of the defender's security resources), or employing one of many online optimization algorithms whose every detail (down to the learning step size) can significantly impact the principal's ''s utility [51].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, instead of working with such restrictive and often unrealistic assumptions on the agent's s knowledge and behavior, we build on foundational decision theoretic concepts, such as forecasts and calibrution [19, 29, 30]. In practice, while agents may not observe the principal's true strategies h they can form calibrated forecasts - notion of consistency in beliefs about h, - to which they then best respond. Indeed, such a decision-theoreti perspective on converging to correlated and Nash equilibria in simultaneous multi-player games [29, 38]. Our work brings the perspective of calibrated forecasts to principal- games. We introduce Calibrated Stackelberg Games (CSG)-a class that is more general than standard SGs- and ask:
game dynamics led to seminal results
Q1. What characterizes principal's 's optimal utility in CSGs?
Q2 Are there natural forecasting algorithms for the agent that satisfy calibration?
Our Contributions. We answer both questions completely. For Q1, we show that the principal's optimal utility converges exactly to V For Q2, we give general approach for obtaining fine- grained any-time notion of calibration of independent interest and further specializing
games.
Before we delve into the details of our contributions, we highlight two key aspects of our results. First, calibration a common property of forecasting procedures shared by many algorithms, not any one particular algorithm defining the agent's 's behavior. Despite not constraining the agent to any particular algorithm, our answer to Q1 shows that the principal can meaningfully converge to V*, which is the value she could have achieved in single-shot game had she known the agent's s utility. Second, our definition and results immediately apply to two important Stackelberg settings; Stackelberg Security Games [49, 7, 33] and strategic classification [21]. As such, we obtain the first results for learning against calibrated agents in these settings too.
Our work contributes two concepts of independent interest (Section 2): first, CSGs that directly generalize the standard model of repeated SGs, and second, notion of calibration, termed adaptive calibration. This notion which draws inspiration from adaptive regret bounds in online learning, provides fine-graine -raiied calibration guarantees for adversarial sequences.
Beyond the introduction of these models, we address an important property of CSGs in our answer to QL. We show that the principal's ' optimal utility in CSGs converges to V*, nothing more less, in games with finit (Section 3) or continuous (Section 5) actions spaces. Note that V is a benchmark that gives both players more power: the principal knows the agent's utility and the agent observes the principal's 's strategy. We find it somewhat surprising then that the optimal achievable principal utility in CSGs, in which both players work with significantly less knowledge, converges to V exactly.
As for our newly introduced notion of adaptive calibration (Section 4), we provide an answer to Q2 by giving a general approach for creating adaptively calibrated forecasting algorithms. This shows that adaptive calibration is not just an abstract notion, rather, it is a natural property with deep roots in the theory of online learning. Indeed, to obtain these results we draw inspirations from recent advances in the multicalibration literature [34] regarding simulating no-regret and best-response dynamics and the sleeping experts problem setting which has been a staple of the online learning literature [8, 31]. Furthermore, we specialize our approach for strategic settings by showing how standard calibration concepts (such the "binning function"") can be adapted to account for the agent's 's best-responses.
1.1 Related work
Repeated Stackelberg games. Learning optimal Stackelberg strategies has been studied in the offline [17] and the online setting, where only instantaneous best-responses are observable (i.e., no access to best-response oracle). Key applications include Stackelberg Security Games (e.g..
[12, 7, 47, 50D and strategic classification (c.g.. [21, 15, 3, 4J). Another line of work treats repeated games an extensive form game and studies optimal strategies for infinite [52] or finite [16] horizons. Other works consider learning in the presence of non-myopic agents that best respond by maximizing discounted utilities [5, 33, 2]. The main distinction our work is that in our setting, the agents have only calibrated forecasts regarding the principal's 's strategies (rather than full knowledge of them).
Stackelberg games beyond best responses. Recent works have studied variants of repeated Stack- elberg games with different agent strategic behaviors beyond best responding. One example is no-regret learning, in which previous works have extensively investigated the relationship between the principal's 's cumulative utility and the single-shot Stackelberg value against agents that use mean- based learning algorithms [13], gradient descent [24, 25], no-external regret algorithms [13, 20, 51],

---

no vo-internal/swap regret algorithms [20, 45], and no-couuterfactual internal regret algorithms [14]. Another research direction assumes agents approximately best respond due uncertainty in the prin- cipal's 's strategy [11, 6, 46] or their own [43, 39, 40] and study robust Stackelberg equilibria [48, 32]. Most of the works here assume that the principal knows the agent's 's utility function with the exception of [51]. Core differences to our framework are that (1) we work in an online learning setting where the principal has to learn the agent's 's utility function from their responses; (2) we do not assume a specific agent algorithm but focus properties of agent belief's that are shared by many algorithms.
Calibration and application in games. The study of calibration, introduced by Dawid [19], dates back to seminal work by Foster and Vohra [30] and Hart [36] that showed the existence of asymptotic online calibration against any adversarial sequence. Applying calibration to game dynamics, Foster and Vohra [29] introduced the concept of calibrated learning, which refers to player best responding to calibrated forecasts of others' actions. They demonstrated that the game dynamics of all players performing calibrated learning converge to the set of correlated equilibria. This is complemented by the results of [38, 27, 28] that show smooth and continuous variants of calibrated learning dynamics converge to Nash equilibrium. Our work differs from the above by studying game dynamics that converge to a Stackelberg equilibrium, where only the follower (agent) performs calibrated learning.
Adaptivity and sleeping experts. The notion of adaptive calibration introduced in Section 2 is related the study of adaptivity of regret bounds in online learning [44, 18, 37]. Our design of adaptively calibrated forecasting algorithms builds on the multi-objectivv learning perspective of online monliii)calbbaationn [41. 34] and the powerful tool of sleeping experts [8, 31, 44] which has proven useful in various applications such as fairness [9].
2 Model & preliminaries
We begin this section with some basic definitions about forecasts, calibration, and games, and then introduce the class of games that we study; Calibrated Stackelberg Games (CSGs).
Adaptively Calibrated Forecasts. We use denote the space of outcomes and C 2 A to denote the space of forecasts. A (stochastic) forecasting procedure a is an online procedure that takes any adversarial sequence of outcomes h, A for & [T], and on round outputs (possibly random) forecast Pa E C solely based on outcomes and forecasts h, Pr, for T E [t - 1). To define calibrated forecasts, let us first introduce the notion of binning functions.
Definition 2.1 (Binning [28]). We call set 11 = {w; (ie)i a binning function, ifeach w; : C + [0, maps forecasts to real values in [0, 1). and for all C. we have Σie(n) wa w:(p) 1.
With the above binning functions, we define the adaptive calibration error with respect to IT as follows. At a high level, conditioned on any bin, the calibration error measures the difference between the expected forecasts that fall in that bin and the corresponding expected outcome.
Definition 2.2 (TI-Adaptive Calibration Error). For any time interval [s, t). let P.t be the sequence forecasts and heg be the sequence of outcomes. For given binning II {wi)se(n) with size n, and Vi E [n]], define the ll-adaptive calibration error
(1) t-s
CalErr, (heat: Psa))
[IP(a.]()) -
where during interval [s, 4J, (ie. 2 Dt wi(p is the effective number of times that the forecast belongs to bin (i.e., bin i is activated), Pis.0 (1) 2 Σt= (:(p.)
(3 -Dr is the expected forecast that activates bin h (1) 2 Et= (xx(pr) h is the expected outcomes corresponding to bin i. (e)
We say that a forecasting procedure is adaptively calibrated it achieves vanishing calibration error on any adversarial sequence of outcomes and any sub-interval of time steps.
Definition 2.3 ((=, -ddppiivv Calibrated Forecasts). A forecasting procedure a is s-adaptively calibrated to binning II = (ws (een) with rate ra(-) E o(1), for all adversarial sequences of actions 1 hi,... hr,, where h. E A, oulputs forecasis Pt E C for I E (T) such that with probability at least 6, we have that Vs, such that 1 S < < ST and Vi E [m]]
CalErr; (hest. Paa) S r 8) +
3

---

We remark that without adaptivity (i.e., for 1 and t = T), Definition 2.2 is weaker than the standard definition of calibration (e.g., [30], listed for completeness in Appendix A) in two ways: (1) standard calibration takes each prediction E C' as an independent bin, thus having infinitely many binning functions: (p(.)) (.). Instead, we only require calibration with respect to the predefined binning II which only contains finite number of binning functions; (2) standard calibration cares about the summation over calibration error across bins, but we only consider the maximum error.
Stackelberg Games. A Stackelberg game is defined as the tuple (Ap, Up, UA), where Ap and AA are the principal and the agent action spaces respectively. and Up : AA x AA + R+ and UA Ap x AA + R, are the principal and the agent utility functions respectively. For ease of exposition, we work with finite Stackelberg games (i.e.. |Apl = m and |AA| k) and generalize our results to continuous games in Section 5. When the principal plays action z E Ap and the agent plays action y E AA, then the principal and the agent receive utilities (p( y) and UA(x, y) respectively. We also define the principal's 's strategy space as the simplex over actions: Hp APP) For strategy Hr, we oftentimes abuse notation slightly and write (r y) == EE E (Ur(,, v)).
Repeated Stackelberg games capture the repeated interaction between a principal and an agent over T rounds. What distinguishes Stackelberg games from other types of games is the inter-temporal relationship between the principal's 's action/strategy and the agent's response; specifically, the principal first commits to a strategy h, E H.p and the agent subsequently best- respondsss to it with y AA- Let P, E Fp H.p be the agent's 's belief regarding the principal's 's strategy at round t. In standard Stackelberg games: P. h, i.c.. the agent has full knowledge of the principal's 's strategy. In this paper, we consider games where the agent does not in general know h, when playing, but they only best-respond according to their belief pt. The agent's best-response to belief Pt according to her underlying utility function UA is action Y/ E AA such that
ye E BR(P.)
where BR(P:) argmax E ())
DEAr z-pp
We often overload notation and write UA v) Eg-pp [U (x) Note that from Equation (2), the best-responses to p. form a set. If this set is not a singleton, we use either a deterministic or a randomized tie-breaking rule. For the deterministic tie-breaking rule, the agent breaks ties according to predefined preference rule > over the set of actions AA. For the randomized tie-breaking rule, the agent chooses y/ by sampling from the set BR(P:) uniformly at random, i.e., y/- Unif (BR())).
The Stackelberg value of the game is the principal's 's optimal utility when the agent best responds:
V
max max (p ,y").
h h' y EBR('")
In the above definition h" is referred to as the principal's 's optimal strategy.
For an agent's ' action y E AA, we define the corresponding best-response polytope Pd, as the set of all of the agent's beliefs that induce y the agent's best-response, i.e., Py = {p E Fp y BR(P)). We make the following standard assumption, which intuitively means that there are sufficiently many strategies that induce y" the agent's 's best-response.
Assumption 2.4 (Regularity). The principal's 's optimal strategy h* E (AAp) and the agent's 's optimal action y" BR(h') satisfy regularity condition: py. contains an &g ball of radius 17 > O.
Interaction Protocol for Calibrated Stackelberg Games (CSGs)
(1) The principal plays strategy h, Hr.
(2) The agent without observing h, forms a calibrated prediction (Def. 2.5) about h,
(3) The agent best responds to Pe by playing y: BR((:)) (+ breakkn...
(4) The principal observes y: and experiences utility Ur(he,y.).
(5) The agent observes h, action sampled from h.
Figure I: Principal-Agent Interaction Protocol a Round of a CSG
Calibrated Stackelberg Games. In CSGs (see Figure for the principal-agent interaction protocol the agent forms (s, II) adaptively calibrated forecasts their beliefs p, regarding h,
If the agent observes action 2; ~ h, instead of the mixed strategy h. then they can still calibrate to the sequence of he with an additional (vanishing) error term that comes from concentration inequalities.

---

We first define binning functions that are especially appropriate for forecasts in games. In CSGs, we define II based on whether a best-response the input calibrated forecast, i.e., Vp E Fp:
wi (p) = 1 E BR(D), > j #
(for the deterministic tie-breaking)
to (P) = 1 E BR(P))
(for the randomized tie-breaking)
[BR(p)]
Note that both binning functions meet the conditions of Definition 2.1. Applying Definition 2.3 for calibrated agent forecasts in CSGs we have the following:
Definition 2.5 (8- C--Aaptiielyy Calibrated Agent for CSGs). The agent is called s-adaptively calibrated with rate ra(+) E o(1), for any sequence of principal strategies hy,... hy Hp the agent takes a sequence of actions y1,.... yr that satisfy the following requirements: 1) there is a sequence of forecasts Pt & Fp for E [T], such that Vt E BR():), and 2) forecasts P1.---:PP PT are e-calibrated for binning 1l with rate r-(.) with respect to the principal's 's strategies h1, ,,r
We next review the fundamental constructs from Equation (1) and their intuitive meaning in this setting. ([s,e)
(t) _ Ere[s,s] (s(p,) is now the expected number of times that the forecast has induced action
i from the agent as their best response during interval [s, t). P(s..) - Er((s,)] (P+)) pr/n(s.g] the expected forecast that induces action from the agent as their best response during interval [s. tl. and (i) A ErE(s. w; h-/m(s.r] (t) the expected principal strategy that induces action from the agent as their best response during interval [s, t). The requirement for an agent to be calibrated is quite mild, as the forecasts are binned only according to the best-response they induce.
3 Principal's learning algorithms
In this section (see Appendix C for full proofs and convergence rates), we study the relationship between the principal's Stackelberg value V and the best utility the principal can obtain from learning to play a sequence of strategies (he hE(r against calibrated agents, i.e., T Exerry Ur(h,, Vt). The relationship between V and + Exe(r) (p( Me) not priori clear. the case of calibrated forecasts, the agents do not know the exact h, when they choose their response. Instead, they base their decisions the history of the principal's strategies so far. A principal then may be able to create historical patterns that lead the agents to worse actions, thus obtaining better utility himself. Indeed, several works have shown how historical patterns can afford the principal much better utility than V* when the agents are no-regret [13, 20]. Surprisingly, we show that this is not the case when the agents calibrated; Exerr Uphh, V2) is upper bounded by TV* and term that is sublinear in T' and depends on the calibration parameters.?
Theorem 3.1. Assume that the agent is (e, ll)-as calibrated with rate r-(-) and negligible s. Then, for any sequence (hi (T( for the principal's 's strategies a CSG, with probability least 28,
the principal's utility is upper bounded as: limr + EiE(T) Up(h, y1) S V*.
Proof sketch. We sketch the proof for the deterministic tie-breaking, as the randomized one needs just an application of Azuma- Azuma-Hoeffding Hoeffding. We first rewrite EvErry Uh yr) partitioned in the principal's utility for each round- -nnd-speccfiic forecast that induces action as the best-response from the agent, for all actions i E Aa: ΣvErry Up(b, yt) = Eiea, Everry wx(Ps) UU,,, i). This equivalence holds because each Pt maps to a single best response i E AA (deterministic tie-breaking). Be- cause of the linearity of the principal's reward in the principal's strategy: EieA, EvErry ( (p()):) ip( ΣieA, ni(()= Up(hr,i) i), where ni) = (i). Adding and subtracting UP(Pr. i) from the above, we now need to bound the quantity: ΣiEAA (i) (U)(:,)), (i)()) - pr (i))). The first term is upper bounded by V*T; note that BR(P7) (and V* = maxn, max,e (h, v)) since (i) E P; and hence that should also be true for the average of (i) over rounds. The second summand is bounded by the calibration error of Defini- tion 2.3.
Li
A similar upper- upper-bound on the principal's utility was proved for no-swap regrett agents [20]. While we prove the theorem directly for calibration, an alternative proof in App. B shows that calibration implies no-swap regret.
5

---

B2
B.lx.)
S
Bg68. -3 S: B,(x. C8)
B,(S,
UB
Figure 2: Pictorial representation for notation (2(S,e) (left) and B2(S, -e) (right).
On the other hand, it may seem that because the agent's behavior is less specified when she uses calibrated forecasts (as opposed to full knowledge), the principal may only be able extract much less utility compared to V*, Again, we show that this is not the case and that there exist algorithms for the principal such that the sequence of strategies (hx hem is asymptotically approaching V*.
Theorem 3.2. There exists an algorithm for the principal in CSGs that achieves average utility: limr- 1 Everyy Ur( yc) 2 V*.
Algorithm is an explore- sxplore-then-core thwetthhemmiii algorithm; it first estimates an appropriate strategy for the principal (EXPLORE). and then repeatedly plays until the end (COMMiT). In the remainder the section, sketch the proof for Theorem 3.2 and point exact lemma statements in the Appendix. Let Ti, T- denote the set of rounds that belong in the EXPLORE and COMMIT phase respectively.
To elaborate on the objectives of the EXPLORE phase, let us first consider setting with zero calibration error, where the agent's s forecasting algorithm perfectly and adaptively calibrated, leading to V/ = BR(h;) h;) at every round. The task for the EXPLORE phase simplifies to identifying near-optimal strategy h through best response oracles that satisfies Up(h, BR(h)) V* E1 for predetermined E We formalize this property in (P1). Given that the agent is perfectly calibrated, in the COMMIT phase, the agent always plays ý = BR(h), leading to an upper bound of E1 [T2 on the Stackelberg regret. Hence, Algorithm I's regret is bounded by V [T T2|
(P1) Up(h, 2 V* for ÿ E BR(h), i.e., (h, 3) is an approximate Stackelberg equilibrium.
Moving away from the idcalized setting. we must account for possible discrepancies between ye and BR(h;) due to calibration error. This introduces: (i) An increased sample complexity [Ti] in the EXPLORE phase, given the necessity to learn near-optimal strategy from noisy responses; (ii) Potential deviations from the action ÿ BR (h) in the CоMMIT phase due miscalibrations in belief. To address the first challenge, we employ Algorithm 2, which constructs approximate best response oracle by repeatedly interacting with a calibrated agent. For the second challenge, we require our learned policy h to robust against inaccurate forecasts. This is reflected in condition (P2), which necessitates the ball of radius 62 around h to fully contained in the polytope Py. The critical insight from (P2) is: for any forecast that results in best response y BR(p.) * ÿ, there must be minimum distance of separating p. from h. We will now proceed formalize (P2), but before delving into that, it is important to introduce some additional notations.
Let (2 =) denote the ball of radius E around x, i..., B2 E) & {a' || 2'112 S =). For convex set S E T , we use B2(S, e) to denote the union of all balls of radius around the set, i.e., (2,, A Uzes B2(x, For convex set S R", we use B2(S, -e) to denote the set of all points in that are "safely" inside S (i.e., all the points in a ball radius e around them still belong in S): (S, -e) A S (2(2, C S). We call this last set, the e-conservative of S. See Figure for pictorial illustration of the notations.

---

Algorithm 1: Explore-Then-Comine
Input:
Target precision e, time horizon T. EXPLORE: Find s-optimal strategy h Hp using Algorithm 2.
COMMIT: Repeatedly play h for the rest of the rounds.
Given the above notations and for tuned E2, the pair (h, () returned by Algorithm 2 satisfies property (P1) and the additional property (P2):
(P2) h E B2 -22), i.e., h lies robustly within the best-response polytope for ÿ.
Given (P2), the regret of the COMMIT phase can be decomposed to when y/ = G. and when y/ + g:
Σ(v -Up (h.
E (v* (p((,)))) +
E (V* (V*-Up(h, Up(h, w))
(3)
1ET'
AET::
LET
When y/ - y. (P1) guarantees that - 17) S E1, so the first term is at most E (T2).
When Y/ + y. let A = AA \ {ū}. For i E A, the definition of binning function w; guarantees that the probability of playing action i on forecast Pd is exactly w; (Pt). Based this observation, the second term of Equation (3) can be further bounded as
ΣV IET: AEA
w. (p.p) - Ur(h, i)) S Σ
E
wi (P.))V*
NT,, (1) ΣnT,
iEA FETs
VEA
Using Definition 2.2 of the calibration error and properties of the lg and foo norms, we can further express nT, (i) as follows
nT, (i) CalErr, (bT,, PT.) [T2]
/m CalErr,(hn, PT.) (T2] (P2) m ra (T(())))) [22]
Pr, (1)
h 20
| (f) h112
82
where for the second inequality is: since lies in the 22 conseevvvveeve of Pg. and pr, (1) belongs
to different and non-intersecting polytope P., we know that (i) hll2 2 82. See Figure
for a geometric interpretation. Finally, bounding the sample complexity for the EXPLORE phase (Lemma C.4) and taking asymptotics gives the result.
The proof sketch above hinges being able to identify strategy for the principal h with properties (P1), (P2). We outline below how this is done through Algorithm 2.
P
Pr.(0)
At high level, Algorithm proceeds as fol- lows. It builds an initialization set I which consists of pairs (h, y) where approximately belongs to the Eg-conservative of y's best re- sponse polytope: B2 -E2). Using these points in the initialization set I, the algorithm then solves the convex optimization problem of max; Ur, yi) using membership queries to (Py y. -62) and the points of I as initial points. The final solution is obtained as the maximum of all these convex programs.
h*
2 Pg
Pr;()
2
P Br(P, y. -6)
Pj
Figure 3: Relationship between the robust policy
h and the average predictions P7; (i): Given that h is in the conservative region B3 -E2), any average prediction Pr, (i) that triggers action i # during the COMMIT phase must fall outside of Ps and thus have a distance of at least Eg from h.
There are 2 things left to be specified for Algo- rithm 2; how to build the membership oracle to B2 (Py, -22) given that U-(-) is unknown to the principal, and how to build the initialization set I contain least one point that is well
centered in py.. To build set I, Algorithm 2 samples strategies h; uniformly at random for enough
With post-processing if necessary, see Appendix C.5 for more details.
7

---

Algorithm 2: Principal's Learning Algorithm for the Optimal Commitment Originally, initialization set <- 0.
/+ build initialization set with pairs (h, where h B2(Ps, -62)
for i E (T)) [o)ume(r)) (VVouu(())))luum(()) do
Sample strategy h, E Hp uniformly random.
Query APPROXMEM (Algorithm 4) for action y/ E AA
I IU (y,, h,).
/+ optimize Up(h.y) using membership queries to Ba(Py, -E2) and set I
for (y,, h.) E I do
Solve Equation (5) using LSV [42] (initial point: h, oracle: e -approximaaee membership
oracle to B2, -E2) simulated by APPROXMEM (Algorithm 4)
max Up (h, y:), subject to (2 -E2),
(5)
h
by. < e' opttmal solution of Equation (5)
5 f- arg ma Up(big Mi) RETURN hg
number of rounds to ensure at least one sample in the 1/2-ball around the center of Pa- with high probability. To build the approximate membership oracle for the Ez-conservative best-repponse polytope for an action y. we use APPROXMEM (Algorithm in Appendix C.2). Specifically, on input h E Hp, APPROXMEM either asserts h E B2 g. E2 + E1) or h & B2 y. C E1) with probability at least 1 - E3. To do this, it samples & points in proximity to h and plays each one repeatedly for / rounds, while registering the best-response action observed for each one of these. If the most frequent best-response for all h& is y, then we can conclude with good probability that was inside By SS2). See Lemma C.2 for more details.
4 Forecasting Algorithm for Adaptive Calibration
In this section, we examine whether there exist natural forecasting procedures that satisfy our Definition 2.3 about adaptively calibrated forecasts. We answer this question positively.
Theorem 4.1. For all > 0 and all binnings II {w; R [0, 1] E [k]], there ex- ists parameter-free forecasting procedure that is addaptivyy calibrated with rate rs( O( O(Vlog (og(km))/tt. Moreover, when 11 is continuous binning (i.e., each w; is continuous), there exists a forecasting procedure that is (0, 11) addativvlly calibrated with the same rate.
To prove the theorem, we use two main tools; the first one a Schapire [44] (ADANORMALHEDGGE applied for online learning in the sleeping experts problem (see Appendix for details). Roughly speaking, the sleeping experts is standard online learning problem with T rounds and N experts, where at each round / there is only a subset of the experts being "awake" to be considered by the learner and report their predictions. Let It, the binary variable indicating whether expert i was awake at round (7,, = 1) or asleep (T,, 0). The interaction protocol between the learner and the adversary at each round is: (i) The learner observes which experts are awake, i.c., {,,, heeN.. (ii) The learner selects a probability distribution E A[[N]) supported on the set active experts A, A (i: : It, = 1}. (iii) The adversary selects a loss vector (4,))1EN))
algorithm of Luo and
(iv) The learner incurs expected loss E, EE,,, [ ADANORMALHEDGE is a parameter online learning algorithm that when applied on the sleeping experts problem (and with appropriate initialization) obtains regret (1) = O (og(N))... where T; = Ere(t] L
The second tool that we use is No-Regret vs. Best-Response dynamics (NRBR) [34]. NRBR are a form of no-regret dynamics between two players, where one of the players must also best-respond on average. Essentially, at each round / E [T', the forecasting algorithm with the calibration rate of Theorem 4.1 outputs randomized forecast p. E Fr, by simulating an interaction between two players described below. For the first player, we construct a sleeping experts problem instance, where the set of experts is G (o(a)))))) s [T] e As.J Ap, o {=1}). For each ((....()))) g
8

---

and t E [T], we define the loss, sleeping/awake indicator, and instantaneous regret respectively as: (tgianaa (.) (he, Pt) = w/ (pr) a. (lu.. Pt.j);
(6)
T (ionna))) 1 2 8);
(7)
rt.g -l.gg (lu.g - Ez).
where by hr Pt.j jt.j we denote the j-th coordinate of h, and P. respectively. We defined the losses for newly constructed sleeping experts' instance above to make sure that there is direct correspondence with the calibration error. Similar ideas for calibration (albeit not for the notion of adaptivity we consider) have been used in [41, 34]. We describe next the player interaction in NRBR.
Player 1. Runs ADANORMAL HEDGE on expert set g with a pre-specified prior To over 9 and feedback specified in Equations (6), (7). At each round Player 1 computes distribution I. A(A((G). where (9) denotes the set of active experts I(s,iii)) E 9 with L. 1.
Player Best responds to Te by selecting Qt (Fp) that satisfies:
max
E.
[(t.g]
max H
I
(hg, P:)] S..
(8)
H.EHp
gode Pr~
After simulating the game above, the algorithm outputs forecast Pt Qt. The existence of such a distribution Q, is justified by the min-max theorem ([34, Fact 4.1] or [28, Theorem 5).. In the Appendix, we also give an explicit formula for Q₁ the special case of m 2. When II, is continuous, player 2 can select a deterministic stronger property is justified by the outgoing fixed-point theorem [28, Theorem 4]. Note that this algorithm inherits its parameter-free property directly from ADANORMAL HEDGG. We are now ready to provide a proof sketch for Theorem 4.1.
that achieves Equation (8) with E 0. This
Proof sketch of Theorem 4.1. Fix instance of the NRBR game outlined above. We begin by Definition 2.2 of calibration error translated in the sleeping experts instance that we defined above:
CalErr,(hart Patt) (t s)) max max
Σ
[E rE(x.t]
We add and subtract in the above E, & to make the regret of the ADANORMALHEDGE the sleeping experts instance appear and so the aforementioned becomes:
( P.a) (t ()= Reg. (B(a).oo)))))
+ max max Ere(sa) T P...e.iii JE(1)
o(v(t=s)llg((km))
where for the regret, we have substituted the regret obtained by ADANORMALHEDGE. Note that & Egg [f.g). This, together with Equation (6) helps us translate the sleeping experts' loss to loss that depends on h,, Pr. Adding and subtracting the term Eee(s E pmaz [4g (hr.p)]:
TS Σ
mAX E awery p-Qr
[L. (h,, p)] +
Σ TE TE(s.1]
(h, P+)
E PEQ,
[To (h, p)]
(A(A))
rE(S.t]
The first term above upper bounded by e (t s) (Equation (8)) (or in the continuous setting). The second can be bound with martingale concentration inequalities.
5 Continuous Games
In this section, we generalize our results for the case of continuous Stackelberg games. The supple- mentary material can be found in Appendix E.
Continuous Stackelberg Games. We use again Ap and AA to denote the principal and the agent action spaces, respectively. Both Ap are convex, compact sets where Ap C I and AA C I The utilities of the principal and the agent are given by continuous functions Up Ap x AA + R. and UA : Ap AA + R.. In this setting, we assume that both the principal and the agent can only play deterministic strategies, i.e., Hp Ap. For x E Ap, let BR(x)) be the best-response function that is implicitly defined as V2U BR())) = O. Our continuous games satisfy Assumption 5.1: (i)-(ii) are standard assumptions used in previous works (e.g.. [24]). but (iv) cannot be derived from (i) and (ii) without further assumptions on the correlation between I, y. Nevertheless, (iv) (and the conditions under which it holds) has been justified in settings such as strategic classification [21, 51].

---

Algorithm 3: Lazy Gradient Descent without a Gradient (LAZYGDWOG)
Initialize hg 0. for epoch Φ 2 0: do
Sample St uniformly at random from the unit sphere Sm-1
Play he Xx 5ggS for M rounds.
/* avg feedback gets close to BR(h:) */
Observe agent's responses 16, M.
S,Up 1 Update action X + Proj Ba(A,, 60) Xs to 70 10
M EielM Uo.s))
Assumption 5.1.
Utility functions Up, U. and the domain Ap satisfy the following:
(i) For all x E Ap.y E AA, Up(z, y) Li-Liscchizz and concave in æ, Lg-Lipschizz in y, and bounded by Wp in l2 norm.
(ii) The best-response function BR : Ap - AA Lea Lipschitz
(iii) Regularity of the feasible set Ap = Ar =Fp
The diameter is bounded: diam(Fp) suPh,reFF || h'll2 Dp.
r(0,r) S Ap - (30, R).
(iv) The function Up (h, BR(h) is concave with respect to h, and has Lipschitz constant Ly-
The main result of this section is to show that even in continuous CSGs, we can approximate asymptotically V* for the principal's 's utility, and that no better utility is actually achieved.
Theorem 5.2. For continuous CSGs satisfying Assumption 5.1, for all Eg > O. there ex- ists finite binning Ig such that if the agent is (0, [1)* adaptively calibrated and the principal runs an appropriately parametrized instance of LAZYGDwoG (Algorithm 3) then: lim a- 4M Eeelor E EiE[Ma] Ur(ha, Vo.)) V 1--en En- Moreover, for any sequence of the princi- M- pal's s actions hurry it holds that: lim-- $ ElErT Up( ye) S V Eg.
We outline next how LAZYGDWOG works. LAZYGDWOG is variant of the gradient descent without a gradient algorithm (GDWOG) of Flaxman et al. [26]. The main new component of the algorithm is that it separates the time horizon into epochs and for each epoch it runs update of the GDWOG algorithm. During all the rounds that comprise an epoch (M in total), LAZYGDWOG presents the same (appropriately smoothed-out) strategy to the agent and observes the M different responses from the agent. The intuition behind repeating the same strategy for M rounds is that the principal wants give the opportunity the agent to recalibrate for a better forecast, i.e.. 1 lim M Hi [M] llp: hl 2 {o}|= 0. The remainder of the proof for Theorem 5.2 focuses on showing that when the calibrated forecasts converge h, then the principal's utility converges to the utility they would have gotten if the agent was perfectly best responding to h,,
6 Discussion and future directions
In this paper we introduced and studicd lcarning in CSGs, where the agents best respond to the principal's 's actions based on calibrated forecasts that they have about them. Our work opens up several exciting avenues for future research. First, although our main results prove asymptotic convergence, it is open question whether exact convergence rates can be improved both for general CSGs and for specific cases of Stackelberg games (e.g., strategic classification in more general models compared to [21], pricing [1)). Second, it is an interesting question whether definition of adaptive calibration (Def. 2.3) can actually hold for the sum over all binning functions, instead of just the maximum. Finally, to provide our asymptotic convergence results assumed that the principal has access to the agent's s calibration rate rs(.): some information regarding how p 's relate to h, is necessary to leverage the fact that agents are calibrated. But we think that in some specific settings (c.g., strategic classification) there may actually exist extra information regarding the forecasts (compared to just knowing rs(-)) that can be leveraged design learning algorithms for the principal with faster convergence rates. We discuss these directions in more detail in Appendix F.
Wee can define (0, ada-taae calibration in continuous CSGs due the continuous in Theorem 4.1.
10

---

References
[1] The value knowing a demand curve: Bounds on regret for online posted-prite price auctions. In 44th Annual IEEE Symposium Foundations of Computer Science, 2003. Proceedings., pages 594 605. JEEE, 2003.
[2] Jacob D Abernethy, Rachel Cummings, Bhuvesh Kumar, Sam Taggart, and Jamie H Morgen- stern. Learning auctions with robust incentive guarantees. Advances in Neural Information Processing Systems, 32, 2019.
[3] Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 6-25, 2021.
[4] Saba Ahmadi, Avrim Blum, and Kunhe Yang. Fundamental bounds online strategic classi- fication. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), pages 22-58, 2023.
[5] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems, volume 26, 2013.
[6] Bo An, David Kempe, Christopher Kiekintveld, Eric Shich, Satinder Singh, Milind Tambe, and Yevgeniy Vorobeychik. Security games with limited surveillance. Proceedings of the AAAI Conference Artificial Intelligence (AAAT), volume 26, pages 1241-1248, 2012.
[7] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in Stackelberg security games. In Proceedings of the 16th ACM Conference on Economics and Computation (EC), pages 61-78, 2015.
[8] Avrim Blum. Empirical support for winnow and weighted-maaorisn algorithms: Results on calendar scheduling domain. Machine Learning, 26:5-23, 1997.
[9] Avrim Blum and Thodoris Lykouris. Advancing subgroup fairness via sleeping experts. In Innovations in Theoretical Computer Science Conference (ITCS), volume 151, pages 55:1-55:24, 2020.
[10] Avrim Blum and Yishay Mansour. From external internal regret. Journal of Machine Learning Research, 8(6), 2007.
[11] Avrim Blum, Nika Haghtalab, and Ariel Procaccia. Lazy defenders are almost optimal against diligent attackers. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 28, 2014.
[12] Avrim Blum, Nika Haghtalab, and Ariel Procaccia. Learning optimal commitment to overcome insecurity. In Advances in Neural Information Processing Systems, volume 27, pages 1826-1834, 2014.
[13] Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. Selling no-regret buyer. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 523-538, 2018.
[14] Modibo K Camara, Jason D Hartline, and Aleck Johnsen. Mechanisms for no-regret agent: Beyond the common prior. In Proceedings of the 61st Annual Symposium Foundations of Computer Science (FOCS), pages 259-270. IEEE, 2020.
[15] Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-awar linear classifiers In Advances in Neural Information Processing Systems, volume 33, pages 15265-15276 2020.
[16] Natalie Collina, Eshwar Ram Arunachaleswaran, and Michael Kearns. Efficient stackelberg strategies for finitely repeated games. In Proceedings of the 2023 International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), AAMAS '23, page 643-651, 2023.
[17] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM Conference Electronic Commerce (EC), pages 82-90, 2006.
11

---

[18] Amit Daniely, Alon Gonen, and Shai Shalev-Shwarz. Strongly adaptive online learning. In International Conference on Machine Learning (ICML), pages 1405-1411. PMLR, 2015.
[19] A Philip Dawid. The well-calibrated bayesian. Journal of the American Statislical Association, 77(379):605-610, 1982.
[20] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. In Advances in Neural Information Processing Systems, volume 32, pages 1579-1587, 2019.
[21] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 55-70, 2018.
[22] Fei Fang, Thanh Nguyen, Benjamin Ford, Nicole Sintov, and Milind Tambe. Introduction to green security games. In International Joint Conference Artificial Intelligence (IJCAI), 2015.
[23] Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for max cut. Random Structures & Algorithms, 20(3):403-440, 2002.
[24] Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Convergence of learning dynamics in stackelberg games. arXiv preprint 090iv:9006.// 2019.
[25] Tanner Fiez, Benjamin Chasnov, and Lillian Ratiff. Implicit learning dynamics in Stackelberg games: Equilibria characterization, convergence analysis, and empirical study. International Conference Machine Learning (ICML), pages 3133-3144. PMLR, 2020.
[26] Abraham D. Flaxman, Adam Tauman Kalai, and H. B. McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.
[27] Dean P Foster and Sergiu Hart. Smooth calibration, leaky forecasts, finite recall, and Nash dynamics. Games and Economic Behavior, 009:271-293, 2018
[28] Dean P Foster and Sergiu Hart. Forecast hedging and calibration. Journal of Political Economy, 129(12):344733990 2021.
[29] Dean P Foster and Rakesh Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1-2):40, 1997.
[30] Dean P Foster and Rakesh V Vohra. Asymptotic calibration. Biometrika, 85(2):379 -39.099999. 1998.
[31] Yoav Freund, Robert E Schapire, Yoram Singer, and Manfred K Warmuth. Using and combining predictors that specialize. Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 334-343, 1997.
[32] Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Robust stackelberg equilibria. In Proceedings of the 24th ACM Conference Economics and Computation (EC), page 735, 2023.
[33] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. Learning in Stackelberg games with non-myopic agents. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), pages 917-918, 2022.
[34] Nika Haghtalab, Michael I Jordan, and Eric Zhao. A unifying perspective on multi-calibration: Unleashing game dynamics for multi-objective learning. arXiv preprint arX0v:2302.10863, 2023.
[35] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifi- cation. In Innovations in Theoretical Computer Science Conference (ITCS), pages 11 1-222 2016.
[36] Sergiu Hart. Calibrated forecasts: The minimax proof. arXiv preprint arXiv:2209.05880 2022.
12

---

[37] Kwang- Awang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Artificial Intelligence and Statistics (AISTATS). pages 943-951. PMLR, 2017.
[38] Sham M Kakade and Dean P Foster. Deterministic calibration and Nash equilibrium. Journal of Computer and System Sciences, 74(1):115-13)) 2008.
[39] Christopher Kiekintveld, Towhidul Islam, and Vladik Kreinovich. Security games with interval uncertainty. In Proceedings of the 2013 international conference Autonomous agents and multi-agent systems, pages 231-238, 2013.
[40] Christian Kroer, Gabriele Farina, and Tuomas Sandholm. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), volume 32, 2018.
[41] Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. Online minimax multiobjective optimization: Multicalibeating and other applications. In Advances in Neural Information Processing Systems, volume 35, pages
2022.
[42] Yin Tat Lee, Aaron Sidford, and Santosh S Vempala. Efficient convex optimization with membership oracles. In Conference on Learning Theory (COLT), pages 1292-1294. PMLR, 2018.
[43] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy commit In Algorithmic Game Theory, pages 250-262. Springer, 2009.
[44] Haipeng Luo and Robert Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory (COLT), pages 1286-1300 PMLR, 2015.
[45] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against learners in Bayesian games. In Conference on Learning Theory (COLT), pages 5221- 5252. PMLR, 2022.
[46] Vidya Muthukumar and Anant Sahai. Robust commitments and partial reputation. In Pro- ceedings of the 20th ACM Conference on Economics and Computation (EC), pages 637-638, 2019.
[47] Binghui Peng. Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), volume 33, pages 2 2149-2156. 2019.
[48] James Pita, Manish Jain, Milind Tambe, Fernando Ordónez, and Sarit Kraus. Robust solutions to Stackelberg games: Addressing bounded rationality and limited observations in human cognition. Artificial Intelligence, 174(15): 142-1111, 2010.
[49] Milind Tambe. Security and game theory: algorithms, deployed systems, lessons learned.
Cambridge university press, 2011.
[50] Haifeng Xu, Long Tran-Thanh, and Nicholas R Jennings. Playing repeated security games with no prior knowledge. In Proceedings of the 2016 International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 104-112, 2016.
[51] Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan. Who leads and who follows in strategic classification? In Advances in Neural Information Processing Systems, volume 34, pages 15257-15266 2021.
[52] Song Zuo and Pingzhong Tang. Optimal machine strategies to commit to in two-person repeated games. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 29, 2015.
13

---

A Calibrated Forecasts Standard Definition
We give below the standard definition for asymptotic calibration of Foster and Vohra [30] for sequence of binary outcomes, i.e., h2 E A = {0, 1). Vt E [7]. The forecasts Pt take values in C' [0. 1]. Let X denote the adaptive adversary generating the events' sequence (which is of infinite size), where the T first events are h,...., hr-
Definition A.I. A forecasting procedure is asymptotically calibrated if and only for any adaptive adversary X that generates the sequence h,. hr E A and the forecasting algorithm a that generates (possibly random) forecasts P1. -r E C on the same sequence, we have that the calibration score Cr(X.o) goes to
as T 00:
nr (r o)
Cr(X,0) &
E
(pr(p: pl
(9)
T
DEFP
where ur(p; - Exe(r) 1p:=pP - is the number of times that a predicts p and pr(p: h, o)
Exer (p be the fraction (empirical probability) of these times that the actual event 1.
(r(ph)
Note that in Eq. (9), while Fp contains an infinite number of distinct p's (hence an infinite number of summands), for every finite T, there is only a finite number of where nr h, o) is nonzero.
Therefore, Cr is well-defined and finite.
Equivalently, the above definition states that for the infinite binning [28] II = (p)(P)) x E C}
where W2 (p) = (p x), the calibration score can be equivalently expressed as
Cr(X,o)
Σ NoG
nT(x") T
(x) - pr(z)],,
EIT
where T2 (x) A Et= (P:) is the number of times that forecast P. falls into bin x, pr(x) & E
(P.)): P. is the average forecast that activates bin æ, which is equal to Σt= (p(p))
ny
()(
because wz (P:) nonzero if and only if p. = x, and hr(#) A Et= (.(P.)) outcome corresponding to bin z. It follows that the score Cr is a sum of the calibration errors during interval T] for all bins (with CalErr defined Definition 2.3).
wr(#) h, is the average
Cr(X,o)
Σ wLEII
CalErr, (hir P1.)).
B Calibrated Forecasts Lead to No Swap Regret
In this section, we show the connection between no-swap-regrel agents and adaptively calibrated ones. a reminder, no-swap-regret agents (translated to our setting and notation for the ease of exposition) are defined as follows.
Definition B.1 (Agent's swap regret [10]). For sequence of principal's 's strategies h,,".,, ,,, E Hpp and agent's actions y1,-.. ,YT AA, the swap regret defined as
UAAhb. (V+))
Σ UA(be,
max
AA
LETT)
KETT]
We say that an agent is a no-swap-regret agent, for the sequence of actions {ye that they are playing it holds that SwapReg(hp) Vv:T) = oT)).
We next show that calibrated forecasts lead to swap regret actions for the agent.
Lemma B.2 (Calibrated forecasts lead to swap regret). If the agent is (e, II) adaapiivvy calibrated,
then the agent's 's swap regret on the sequence hid is bounded by the calibration error as follows:
If the agent breaks ties deterministically, then with probability 2 1 8,
SwapReg(hi:r: V1.T) S 2U 2nT (rs(T) + E o(T).
14

---

If the agent breaks ties randomly, then with probability 2 1 -28
SwapReg(h (h h VvrT) S Umax (c (
2mkT (ra(T) + e(T).
where Umax= Aa maXyEAA U y) is the maximum utility the agent can obtain (without constraining the agent to play best responses).
Proof. We first present the proof for the case that the agents break ties deterministically. To simplify notation, we use (i) = "'jorr (1), Pr == Pto.T] and hr) (oo (4).
Fix a AA 7 AA. Then, with probability at least - 8, we have that:
T
T
Σ CA
Σ
UA(b, Me)
E
Σ
1s i) (Ua(he, ((i) (A()..))
(rewriting yr the exact action)
EA 1=1
T
(
(P.P)) (A, (be Ua(:))))
(10)
iEAA t=1
Σ (1) ((br - (1r UA(,,))
iEAA
E (T(1) ((r((1) pr(1) (1)) + - UA((s)) + (Pr (a()))((())))
tEAA
Σ (i) (i)(1) hr) ((0)
NEAA
20 m
Σ T Cair PIeT)
(Def. 2.3)
BEAA
20m (T)())))..
In the above equations, step (a) is due to the fact that agents best respond with a deterministic tie- breaking rule: y/: = i if and only i E BR(P:) and > J. Vjj + i, which is equivalent to wi (Pt) = 1. denote the m-dimensional vector where the jth entry is the utility (A(j.i). Step (b) is because the second term
We have also used Ua(-,i) i)
(P), UA(, (1)) UA(, i)) U (p) m()) (P(
non-positive since each P. with w; (p.) 1 belongs the best response polytope P,, so does their average: (i) E P. + E (R)..
Since the above inequality holds for any æ, it also holds after taking the maximum over all n AA AA. Therefore, we have the same bound for the agent's swap regret.
Next, we move to the case when the agent breaks ties randomly. For a fixed n, we have that at every time step f,
E (())) EiER((,)) [B((p:)
UA (h,, T(i)
wy (he,
tEAA
Therefore, by Aruma-Hoeffding's inequality, w.p. 2 1 8', have
T
(v Tlog
Une,, T (v:))
Σ w. (p:) (()
(11)
8'
TEAA
Since all actions in BR(p:) have the same utility for the agents, we also have
ElerR(p)) U (h),))
U (b, y:)
Σ
wp(p:)U' (h,
[B((p:)
15

---

Therefore, using Equations (11) and (12), we have that with probability at least 1 8'
T
T
3 (h,,, x (Vx))
Σ (h) S
Σ Σ
(p(
(Un(he (i)) Un (h);;)) i))
iEAA
(T 1 8 )
+0
(12)
We can use the same arguments above (from Equation (10) onwards) to bound the first term on the right hand side by 2km (ra(T) + E) with probability 1 ô. Finally, setting 8' = 8/M M where M = b* is the number of possible swap functions, and applying the union bound, we conclude that
with probability 2 1 26, the swap regret is bounded by
SwapReg hI.T, .1:T) Umax (0(17)
k log k log (21} ( + 2mkT (ra(T) +5)
C Supplementary Material for Section
C.1 Proof of Theorem 3.1
We first formally restate the theorem with exact convergence rates (not just asymptotically).
Theorem C.1 (Formal version of Theorem 3.1). Assume that the agent is (e, II) adaatiivv calibrated with rate ra(-) and let U = maXheHP Ma (r y). Then, for any sequence {h, her for the principal's strategies in a repeated CSG, with probability least 26, the principal's I's utility is upper bounded as:
Σ Up(he,Vi) S V-T + (Umma, m. k. T, rr, 8,8) AE(T)
where (Unmux, m, k. T, T,, 8, Unax m k. T (ra(T) + e) when the agent deterministic tie- tte-breaking and auUmax. m, k. T..T... (T.,5,,8)) 8,E) Umax m T (rs(T) + / log((1))) when the agent uses randomized tie breaking..
Proof. To simplify notation, use nT(i) (1)27(1). When the agent follows deterministic tie- beebbrekking, we have:
Up (h,, 910
Σ
Σ (P:))
iEAs
= Σ (ir)
(linaarity of Up in the principal's 's strategy)
iEAs
= Σ
(1 (Up
(1), (prr())))))) + (U - pr())))
iEAs
(+ (r(,Ur(r(().))
(0)
RT "T(V
Σ ni(i) [pT(i) hr( -IUP(,)))
iEAA
iEAA
VT U U m Σ T CalErr, P1.T)
SEAr
SV* + Umax k- 6-mm- T (Fx(T) +e)
where (a) is because (p) V* (since E BR(PT)), Höllerr's inequality, the fact
that -| < ||. 111, and (b) is because of the definition of Umax and Definition 2.3. The proof for the
randomized tie- hiebreeking setting has an extra term from Azuma- Hoemaa-iefdiig's 's inequality, similar the proof of Theorem B.2.
D
16

---

C.2 Approximate membership oracle to conservative polytopes
In this section, we formally present the algorithm (Algorithm 4 for constructing an approximate membership oracle to the conservative best response polytope for each of the agent's action. The sample complexity of the oracle will be presented Lemma C.2.
Algorithm 4: Approximate membership oracle for the conservative best response polytope (APPROXMEM)
Input:
query Hp, original polytope Pg (y E AA). approximation factor E1, conservatism factor E2, failure probability
Parameters: Number of epochs @ radius R, calibration error Ecal-
Let 7 be s.t. (t) kmm
Sei
for epoch Φ [$) do
Sample point ha such that [| h//2 R.
/* Sample point h close to h */
if ha E Hl then
RETURN FALSE
/+ No longer inside the feasible set //
else
Play strategy h& for rounds. Ve < most frequent best- rest-response action from agent during the rounds. /+ he is too close to Pso */
if + then RETURN FALSE
For membership, output Ve if all (vo boEM) agree, and N/A otherwise
RETURN TRUE
In Lemma C.2, we show that the parameters 4, Ecat. R can be tuned to achieve a wide range of parameters (E1, E3). In Proposition C.3, we provide explicit instantiations of the parameters for three special cases of (E1, E3) that will be useful in later sections.
Lemma C.2. If the agent is (s, III adaptivvll calibrated with rate r-(-) and infinitesimal e. and the parameters 4, R, Ecal satisfy:
8 + 62
R Ecal
(Condition
2
2
Ecal + E2
2 m
log
(Condition 2)
R
E3 -
Then Algorithm 4 (APPROXMEM) returns an E Ex-approximate membership oracle to P
B2 -22) with probability 1 Eg, using more than Ne1.t2.ss interactions with the agent.
O (br " ( rounds of
Specifically, with probability ex. APPROXMEM either returns TRUE which asserts that h (P y 2, +E1), or returns FALSE which asserts that h & (P 12(P--,,E8) -E1).
Proposition C.3 (Parameter settings). Assume E3 8 T-2 In the following three cases: 52 @(vm), 1, o(1), the proposed setting of parameters Ecat; R, t satisfy (Condition 1) and (Condition 2)
simultaneously.
Case
81 = =(Vm). E2
Ecal = E2
R
E1
10/m
1-
452
log(T) O0mmlog(T (T)).
2
E1
Case II. 51 1.
52
Ecal 0.15g,
R = 1.952,
① = 1.25 lTg(
Case III.
= o(1)
8q
E1
E2 + =1
(1+
E1
E2
Ecol
② 10 m
log (T".
6'
20a
11
17

---

Proof of Lemma C.2. Before we delve into the specifics of the proof, we introduce some notation. In order to make sure that he is such that | h = R. we do the following: hg h + RS where
So is sampled uniformly at random from the equator n H., where {s R ||s| 1} is the unit sphere and H = {s E I= (s, 1) = 0} is an equatorial hyperplane (1 _ (1,.... 1) E ). Note that this is because we want he to remain valid probability distribution, i.e., that (h3. 1) = and h 2 coordinate-wisst indeed, since we already have (h, 1) = 1, we need to make sure that (1) (S 1) 0, which is guaranteed by So E HH; (2) h 2 0, which is guaranteed by returning FALSE whenever hg & Hp.
For the rest of the proof, we condition on the following success event:
E - { V S [1, vi E AA, CalErr, (bet: Psa) S rr((1 - $)} 6.
Since the agent is (e, addapiiiiyy calibrated with rate rx, we have Pr(E)
Recall that Ecal = (l) denote the enror that comes from calibration error. We first show that conditioned on E, Vo [ h& E B2 Ecal). Let lye be the number of times that agent plays ye during the 1 repeats, then we have Lgo 2 1/k because yo is the most frequently played action. Then, the calibration error bound in Definition 2.3 guarantees that
1ue (Ip(vo) - lolloo CalErr,, ve (h Po.1.) S rl) +
T
|p(xs) boll2 S mm (p(()) - holloo S vmkkr(()) = Scal-
(13)
where the first inequality in equation (13) is because of the norm property |>>||| I vdl for a vector x E Rdd. Since p(y+) E Py, because the agent always best responds to forecasts, we obtain
he E B2 y
We then prove the following two claims:
(C1) I E B2 -E1), then APPROXMEM returns TRUE.
(C2) If & B2(P +81). then APPROXMEM returns FALSE with probability 2 1 1 (53 6).
Indeed, if the following two claims hold, then we have established that APPROXMEM asserts one of two cases correctly with probability 2 1 - (E3 - 5) conditioned on E. Together with the fact that Pr(E)= 1-11-- 6, proves the lemma.
Then we know that B2 S Py Be -E)) which further implies B2 E1 + 52) S Py. Therefore, the distance between and any other polytope Py (v/ o y) must be lower bounded by E1 + E2. By triangle inequality, Wh' E Py where s/ + y. we have
Proof of (C1). Suppose E S2 -1). --1).
Vo E [Ø].
l|ا - 12ll2 2 h - h2 - |h -holl2 2 E1 + E2 - R 2 Ecals
where the last step follows from (Condition 1).
Since this holds for all h' E Py it implies h& & B2 Seal) whenever y/ # y. Together with the
fact that h& E B2 i Ecal), we must have yo = y for all epochs @ E [Ø]. Therefore, APPROXMEM always returns TRUE.
Proof of (C2). Suppose h & B2 +21). We first analyze the probability of returning FALSE for fixed epoch @ [Ø). Let as be the boundary of convex set S, then by triangle inequality, we have (Pyr. y. Ecal)) < d(h,aP,) + aB, Ecal))
d(h, 0B
For the first term, we have d(h, )P,) < E2 since
E B2 +&1 = h & p = B2(Py: -62) = d(h, Pa) S 82.
For the second term, we have
d(OPy, BB ccm)) S Ecal,
because Py is a convex set. Combining the two bounds, we know that d(h, aB2 eca)) S Eal +22 Since he is uniformly sampled from the sphere of radius R around h, by convexity of B2 Ecal) and the rotation invariance property of unit sphere, we have
Pr(hş & B2(P,r Ecat)] > Pr((RS,, v) Ecal + E2] = Pr (S e1) > eattes/))
18

---

where v unit vector pointing in the direction of (one of) the projection from h to @B2 Ecal), and e₁ (1, 11.,,...,, ,0) R According to [23, Lemma 9], we can further lower bound the probability by
!
Ecal + E2 11-
Pr(ha $ gg Eca)) 2 2/m
R
Finally, the probability that no epoch returns FALSE (failure of APPROXMEM) is most
Ecal + S2 R
(1 - (1 S E3 - 6, where 8'
2/m -
Since
1, the above inequality holds as long as
E3 - 4/m (1-
(1-(ca)) Eccll + E2
2 7
1
log
log
R
E3
which follows from (Condition 2). Therefore, h & ep +81), then APPROXMEM returns FALSE with probability 2 (Ea 8).
C.3 Complexity of the explore algorithm
Lemma C.4 (Sample complexity of Algorithm 2). Using Algorithm 2, the principal can find with probability at least - (6 + Eopr + ), strategy h Hp that satisfies the two properties in Lemma C.5. We refer the reader to Theorems C.8 and C.13 for the sample complexity under two different instantiations of Algorithm
Lemma C,5 (Optimality and robustness of output policy). Under the conditions of Lemma C.4, the output of Algorithm 2 satisfies the following two properties:
(P1) (p(h, v²) 2 V* Eopt. i.e., h is an approximate Stackelberg equilibrium. (P2) h E (2 Enobur)) i.e., h lies robustly within the best- rest-response polytope for y².
We refer the reader to Theorems C.8 and C.13 for the exact values of E Eopt under two different instantiations of Algorithu 2.
Before we formally state the proof of Lemmas C.4 and C.5, we first show the sample complexity guarantee of the exploration phase of Algorithm (Lemma C.6), then state a useful lemma from prior work convex optimization from membership queries [42] (Lemma C.7).
Lemma C.6 (Initialization set Algorithm 2). Let V be the volume of an E ball of radius n in TR Suppose the principal samples uniformly from Hr for O(V-1 log T) times and calls APPROXMEM(e1 82 7/4, E3 = 5 + T22 for the membership of each of them, then with probability at least optimal target, and bo is -ceetteeed Pyr, i.e., ho E B2 2).
2
- T-1,, the initialization set I contains (ho, yo) where yo y is the
The total number of samples required for the initialization O 0V--1..25"13 " l)
phase is
Proof of Lemma C.6. By regularity assumption, there exists h E Py,, s.t. B2 Pyr. There- Moreover, since h' lies robustly inside Py,, on
fore, vh' E B2,h, 2), we have E Bz P -7). the success event of APPROXMEM(s1 = 82 = 4), APPROXMEM(h") must return membership y², otherwise we must have h' & (P,,, -
B2 )) a contradiction. Since the set of all such h' takes up nontrivial volume V in Hr, we know that O log T) uniform samples are guaranteed to one with probability
12T)
Now we upper bound the failure probability of the initialization phase. Since the agent miscalibrated with probability 8, random sampling fails to discover centered h' with probability (27)- and the
19

---

probability that one of the answers from APPROXMEM is wrong with probability (27) the total failure probability - 7 as desired.
As for the sample complexity, note that according to Lemma C.2 and proposition C.3, each call to APPROXMEM takes O (1.25mmr (x/m) log T) samples, and the initializa- tion phase calls APPROXMEM for O(V-1log log times, the total sample complexity is (V-1 1V251. " (kmmm log'T).
Lemma C.7 (LSV performance guarantee, Theorems and 15 in [42]). Let K be a convex set specified by a membership oracle, a point E R", and q >> O such that B2 7/2) S K S (wo 1). There exists a universal constant To > such that for any convex function I given by evaluation oracle and any e' 0, there is randomized algorithm that computes point 2 E (2(,, such that with probability 2 1-E',
f(z) S
min (xx + øEK
maxx f(x) ZER
min [(x))
=EK
with constant probability using O and evaluation oracle, where E₁ (s'n/a)
n² log (m/ee') calls the E -approxximate membership oracle
Note that in Lemma C.7, the required accuracy ($1) of the approximate membership oracle is orders of magnitudes smaller than the suboptimality (E) of the output solution, i.c.. E < E. Let h denote the e-optimal solution returned by LSV. Since we use APPROXMEM which is an E approxxiiet B2 y f*,e)
membership oracle to Py 5> will lie in B2(K, order to find a opar-optimal solution that lies robustly within Py. we can either simulate APPROXMEM with more epochs to guarantee E << E & E2 (see Appendix C.4 for more details), or perform
B, (Pg. -E + E). In
post-process h that pushes it further inside the polytope (see Appendix C.5 for more details).
C.4 More epochs to guarantee robustness
In this section, we show how to use more epochs in the simulation of each APPROXMEM oracle to obtain higher accuracy feedbacks. This approach directly guarantees that the output of L.S lies robustly within the polytope.
Theorem C.8. If the principal uses Algorithm 2 with parameters APPROXMEM(E; = 6 and LEV(E'), then with probability at least 1 - T E', the final solution h satisfies the following two properties:
(P1) Up(h, v²) 2 V*- -e', iee., hn is an approximate Stackelberg equilibrium. (P2) h E (2 i.e., h lies robustly within the best-response polytope for y"
The total number of samples needed is Ô (V-Im 3+m77 (17²))
(E'n))0
T8
lem 70 s/m
Proof. We first analyze the failure probability of the algorithm. Since the agent's adaptive calibration error is uniformly bounded by r-()) with probability 1-8, 8, the probability that there exists an incorrect answer from APPROXMEM is bounded by T T.T-- - T-1 conditioned on agent's 's calibration error being bounded, and the probability that LSV returns a bad solution is bounded by e', the total failure probability of the described algorithm is at most å + T E'.
Now we consider the optimization problem for the optimal polytope Pyt, with initial point ho that --centeeed in Py.. There exists such a pair (h,, y²) E I according to Lemma C.6. Let be the solution output by LSV. According to Lemma C.7, h e B2(P, ++e') B which proves (P2). For (P1), note that Lemma C.7 also guarantees
V -"-Un UU-U(h, v¹) Se' (v"- max Up(h,y') S + 2 = =3'. hep
20

---

Finally, we compute the total number of samples. By Lemma C.6, the initialization epoch
samples. According to Lemma takes 0 0 kkmm log T)
C.2 and proposi-
tion C.3, each call to the APPROXMEM oracle requires
m
(
E1 log(T)
(='1) km log samples, and Lemma C.7 suggests that there LSV makes
m
T8
O m log ((1)
oracle calls, where we run O(V-1 7) LSV instances for each initial point
the initialization set. Putting together, the total number samples is
(5'1)" To
5+
m
(nE")
To
kmn To /m
where Ô hides logarithm terms in T, m, 1/1, 1/6'.
C.5 Representation length and post-processing
In this section, we show post-processing of the output of LSV [42] under the representation length assumption.
Assumption C.9 (Utility Representation Length). Suppose the utility functions Up and UA are rational with denominator at most a, and normalized to be [0, 1). Therefore, the game's 's utility representation length L 2mn log a.
The next lemma shows that under Assumption C.9, the optimal solution h also has a finite represen- tation length.
Lemma C.10. For any AA, let h E Rh be the principal's optimal strategy in Py that achieves max EP, Up y). Suppose the utility functions Up, UA satisfy Assumption C.9. Then for all i Ap, the i-th coordinate of hy is a rational number with denominator at most 22mL.
Proof. The proof of this lemma is similar to [12, Lemma 10], which follows from well-known results in linear programming. We first note that h" is the solution of the linear programming:
max (p, y). subject h" Pa.
where Up(h,y) is linear in h and the best response polytope Py can be represented system (h : Ah 2 b). where the set of constraints are the ones that define probability simplex Hrr together with the constraints of the form Ur v) (h, v') 0. Vy' + y. Suppose A is normalized so that each entry is an integer. By Assumption C.9, each coefficient is at most 2 Since the solution the above LP is the intersection of independent constraints of A (denoted with D), we have h det( by Cramer's rule, where D, is D with the i-th column replaced by b. According to det(D)
Hardamard's s inequality,
det D)
II iE/m]
II /Elm]
d, <
II Vm2* sE(m]
2m < 2mm
We also make the following assumption on the optimal strategy h": any near-optimal strategy must lie in the neighborhood of h² Assumption C.11 (Near-optimal strategies). There exists constant s.t. for all < 2m4. 2-mf. and all strategy h such that Up(h.y") s V* -,, we have h ho I c2he.
Now we are ready to define the post-procsssing algorithm.
Lemma C.12 (Post-processing). Suppose that Assumptions C.9 and C. holds. Assume e S 2 2-4 h is E-approximate optimal strategy in Ps. and ho is a/2-centered in Ps. i.e., Bz 9/2) C Pg. then using more than O (22m7 kmmm
( ( log rounds of interactions with the agent, POSTPROCESS (Algorithm 5) outputs strategy ha that satisfies with probability 21-6 -
21

---

Algorithm 5: Post-Processing (POSTPROCESS)
Input: non-robust strategy (h, s.t. h E B2(Pg, E), robustness parameter X, intial point ho Output: robust strategy
S set of strategies h' Hp s.t. each coordinate h is rational number with denominator at most 22ml and [h. h c2
for he ESO doo
liquery + (1 (1- 22 h ho
Query APPROXMEM, (Iquery) with E 82 = -.2 2. 6 7-2 if APPROXMEM returns TRUE then
h (1 (1- 22 hquerr + 2A ho
RETURN
(i) h lies robustly inside Ps: B2(Pg.-A -A);
(ii) h is close to h: || - hill2 S mm (c2 1
Proof.
To prove the lemma, make the following claim: For all h1 Hp, if h Pg and
h2
2A 22 ho, then we have h2 E B2 -Å). In fact, for all unit vectors E R"
7 h1
we have
h + As = (1- 21
ho 7s)
h
17
Since h1 E Pg and ho + fs E B2(ho 7/2) C Pg from the assumption that ho is 9/2-centered, their convex combination must also lie in Pg because P3 is convex. Thus, we have h2 + As E Pg. Since the above holds for all unit vectors s, conclude that B2(h2, Pg. We have thus proved the claim.
With the above claim, we first show that when all oracle calls return correctly, S contains at least one point h such that APPROXMEM returns TRUE on hijuery. and the post-processed version of this strategy satisfies (i) and (ii).
Since h is an e-optimal strategy, by Assumption C.1I, we know that the true optimal hž satisfies [hh h/1so S c2 According to Lemma C010, every coordinate of hj is rational number with denominator at most 22mL, Combining the guarantees, know that S must contains the true optimal h which satisfies h E Py. Suppose this point h2. According to the above claim, we have Queery (2g. Since we simulated the APPROXMEM oracle with E1 E2 A must return TRUE on strategies that belong to B2 52 -1) = B2(P, -)), therefore, must return TRUE on hquery. This argument shows that POSTPROCESS always return valid strategies.
2'
However, it could be the case that APPROXMEM returns TRUE on strategies hi that are not hj. We argue that the guarantee of POSTPROCESS unaffected by showing that if APPROXMEM returns TRUE on any hquery. then we must have hiuecy E (2,,, +21) S Pg from the guarantee of APPROXMEM (see Lemma C.2). Applying the above claim again, we have that h E B2(P,, -A) for the returned strategy h, which proves (i).
As for (ii), note that
hh f1/l2 5/
11ll2 + llh² Inqwayyll ll2 + [|nquuery - hl/2
2A (llb²* hol2 + [Iquerry holl2)
Sym hn' 11x0 +
Sc/m2ke 42ym
Finally, we analyze the failure probability and sample complexity of POSTPROCESS. Since the agent's adaptive calibration error is uniformly bounded by ra(-) with probability 1- 6. and the
22

---

probability that there exists an incorrect answer from APPROXMEM is bounded by T T conditioned on agent's calibration error being bounded, the failure probability of POSTPROCESS is at most 8 + T-1.
2 and each h S requires simulating APPROXMEM; with O rr (kym log T) samples (see Lemma C.2 and proposition C.3), the total number of samples required is O (2 kvmm ( logT)
For the sample complexity, since |S|
Theorem C.13. Suppose the utility functions satisfy Assumptions C.9 and C.III If the principal uses Algorithm 2 with parameters El /mãz (2zmm)) ,8 ô T for the APPROXMEM oracle and e' =2-1mL-1 for LSV,, then feed the output of LSV into POSTPROCESS(A), then with probability at least - T-1 6' the final solution satisfies the following two properties:
2
(P1) Up(h, v²) VV 5md ie.. is an approximate Stackelberg equilibrium.
(P2) h E (P A), ie., h lies robustly within the best-response polytope for y".
The total number of samples needed is expressed in Equation (14).
Proof. The analysis for the failure probability the same with Theorem C.8
Now we consider the optimization problem for the optimal polytope Py-, with initial point he that is --centered in Py Let h be the solution output by LSV, and let h be the solution output by running POSTPROCESS on h. According to Lemma C.7, h satisfies h B2 " S (2 s'), and the suboptimality of h is at most Ols' + =2) S 2 2-4mL, Since ex 2-44LL by Lemma C.12, h B2 Pyy,, A)), which proves (P2).
To prove (P1), note that since ||h hill2 S vm (22te' 41) by Lemma C.12, we have
V - (r < V* Ur(h, + (Ur(h, Ur(h,,²))
41
4md
5md
< 4mb 4mb 4 C2 + n < 2
3mt
n
"
Finally, compute the total number of samples. According Lemma C.2 and propo- sition C.3, each call to the APPROXMEM oracle requires (mrr kym logT) = T) samples, and Lemma C.7 suggests that LSV makes (m)) = O m3 log (m) oracle calls, where we run OoV-llog7 T) e'n
O (Vmr km mzimr no) log o0
O m² log
LSV instances for each initial point in the initialization set. In addition, POSTPROCESS A log T)
samples (Lemma C.12), and initialization takes O (V--1.255m7 ' (x/M) l)g2r) samples (Lemma C.6). Adding them all up, the total number of samples is
takes
O 122m7-11
-1 Evm
δ 0v--1..55m k/m
V V 3.5 Lrz
1 70 )7)
+ 22 -1 )md (14)
km <224m.
where Ô hildes logarithm factors in T, m.
C.6 Proof of Theorem 3.2
In this section, we present the main theorem (Theorem 3.2) Section 3. We first formally restate the theorem with exact convergence rate.
23

---

Theorem C.14 (Formal version of Theorem 3.2). There exists an algorithm for the principal in CSGs that achieves average utility with probability o())
lim T
1
Σ ()) V*.
(15)
[E[T]
Specifically, for calibrated agents with calibration error rate rs(() ((-11/8),
(I) If the principal runs the CEERRE-THE--OMAE algorithm (Algorithm 1) where the explore phase follows the parameter settings in Theorem C.8 with e'
--1 "1
O T m CT 17
then the limit in (15) approaches V with rate
δ o(r
T
T
m-
where
C₁ V-Lm
m
34m hp 8(22
k.
7
-
70
m
+
3
+
2
(II) If the principal runs the EXPLORE- EXPLORE-THEN-EE plore phase follows the parameter settings in Theorem C.13 with À O then the limit in (15) approaches V with rate
algorithm (Algorithm where the ex-
((
[CC2 72 T 72
m2
72
T 72
C
where
C2 - 1-125miirr 3
72
Byo
+ 1.
Proof. According to Lemmas C.4 and C.5, we have that with probability 1 o(1), Algorithm 2 (with potential post-processing returns a policy within N samples, where satisfies
(P1) Up(h. y²) V* Sopt. i.c., h is an approximate Stackelberg equilibrium. (P2) ñ (P -robasst i.e., lies robustly within the best-response polytope for y²
With properties (P1)and (P2), the arguments in Section 3 give us
V Σ Up(h, We) S NNN EopiT kymTra(TI
Emhust
1E|2
Now we plug in specific instantiations of Algorithm
(I) Suppose the principal follows the parameter settings in Theorem C.8. In this case, we have Eopt 3E', Erabust E'. and
N =
maa (ME')
18 1 (s'1))
km 20 vm )mm))
m
B- to 1(200++)
1. (me') -70 (2+3))
Finally, optimizing over E gives the claimed bound.
(II) Suppose the principal follows the parameter settings in Theorem C.13. this case, we have
Copt Grohust X, and
5mn
7
0 v 1.25 1 ?
V
1
Lr kmm m24mL 1.mm1..0 k. -800)
70 )70 + 22 -
r
mm
kym
-ō (V 1.255"
(K m)
Finally, optimizing over À gives the claimed bound.
24

---

Remark C.15 (Representation length). If we assume the optimal solution h" lies in the grid of size poly(e-)) ) then in case (II) of Theorem C.14, we have 2 poly(E"") which leads to a rate of Ô (poly(s, k, m,,) (,,n) V-VV TT
where "/2 is a constant that only depends on the agent's calibration error rate B. This is the result of replacing Lemma C.10 with the finite grid assumption.
Remark C.16 (Adaptive regret versus calibration). Our primary focus lies on calibration due to its characterization of agents' beliefs and the fact that it provides both upper and lower bounds to the principal's 's utility. This is particularly useful for the learning direction, as denoted by the lower bounds in T'heorems 3.2 and C. 14. However, a different form of adaptive guarantee would suffice here: one concerning (external) regret. Nevertheless, we do not focus on regret as a characterization as it doesn't I offer the same upper bound guarantees- in fact, the principal could potentially extract more utility than V*. Additionally, aggeetbbased assumptions tend to overly emphasize the agent's s optimization techniques rather than maintaining a consistent belief about the action being executed.
D Supplementary Material for Section 4
D.1 Background on Sleeping Experts and ADANORMALHEDGE
We start the exposition of this part by introducing the sleeping experts problem [10, 31J. For each expert i [A] and round E [2']. let l,, E [0, 1] be the loss of expert and let Ie, be an indicator that takes value I,, = 1 if expert is active at round t and I,; = 0 if asleep. The interaction protocol at each round goes as follows: The indicators (ee are revealed the learner. The learner selects a probability distribution E ([AV]) that is supported only on the set of active experts A, _ {i: : Ie.- = 1}. The adversary selects a loss vector (4N))) The learner then suffers expected loss & = Es [ The regret with respect to each expert only accounts for the rounds when i is awake, which, together with the fact that Te is only supported on active experts, implies that
Regr (i) = Σ Te, (e+ (4e-ea)) le,s) = Regr max Reg (i)
(16)
EE[T]
One of the algorithms that can be used to provide sublinear regret for the sleeping experts problem is ADANORMALHEDSS [44], ADANORMALHEDGS is a powerful, parameter-free algorithm which provides regret bounds in terms of the cumulative magnitude of the instantaneous regrets, defined as:
Tr,1 = - le, for all experts E [N]. As its name suggests, ADANORMAL known algorithm HEDGE as a backbone; HEDGE maintains a probability distribution over experts at each round and draws an expert from said distribution. After the expert's loss is revealed, the probability distribution for the next round t+ is updated using multiplicative weights argument. For bandit feedback (i.e., when only the chosen expert's 's loss is revealed to the learner), the multiplicative weights update rule uses an inverse propensity scoring estimator for each expert's 's loss in place of their real loss. The new element that HDE brings to the table is a way of defining the weights at each round f; specifically, the weights are updated proportionally to the sum of instantaneous regret for each expert until round This allows the learner obtain finer control over the total regret without needing extra parameters to tune the algorithm at each round. The exact regret guarantee that ADANORMAL HEDGE obtains stated formally below.
uses the well-
Lemma D.1 (ADANORMALHEDGE) [44]). Let = L1, (Ee (le-h..) k1s) be the instantaneous regret
of any active expert i E A, at round I, and ct.; = =|resl- Then, ADANORMAI with prior q E A(NN) selects experts according to the following distribution
Tt, x we (Be-1,5 1,51 Co-1,), where
R Σ T7,6 G--1
Σ Cr TE(--1]
TE]--1]
w(R, 0) = ( (R 1,C D(R 1 1,C 1)),
max (0, R22
((R exp
3C
25

---

The regret of ADANORMALHEIGGE against any distribution over experts E [[[N] is bounded by Regr(u) S (v(u,, (u,,Cr)) Cr) (PRz(ullg) + log log T log log N))
where by Dxi(ullg) we denote the KL-divergence between distributions u and 9-
ADANORMALHEDGE can be used obtain adaptive regret bounds by creating sleeping expert (i,s) for each E [ E [T] that has the same loss as expert but is only awake after s.
Corollary D.2. Running ADANORMALHEDGE, for the sleeping expert setting with prior ((ts)) x gives regret
(ege((i,))) SO () (s) log log 7)
where T; Et- I is the lotal number of rounds in which i is active.
D.2 Formula for Computing Qt when m
To obtain the explicit formula for Qt, we first discretize the space of forecasts Fp = [0. 1] (since we focus on the case where m 2) form set FP {0, c, 2....., E, 1}. Then, we have that for each P E Fp:
E gm
[tag]
E gmatz
[Zg (he, p)]
Σ gEA((9)
Ft wi (b:-P) PP)
= (h+ - p)
Σ
w; (p)
Σ
(T.g(esit1)) - Te.((a.,111)
(17)
iEAA
SSt
2p
where we have omitted index j from the sleeping expert since because m = 2, we can focus on single action j. We assume WLOG that no forecast p E Fí falls exactly on the boundary of best response polytopes, so there no tie-breaking needed. From Equation (17), we have that:
[Gr.l] = m2 0} pMp he EP gIwiss
max
(18)
where the equation also the fact that for m 2, maxh, EH h, 1.
In the final step. we map p to the discretized grid of Fi. je, (j + 1) be two adjacent discretized points and q [0, 1] such that: 92,5 + (1 ())) Then, setting qr,e q and (t( 1 and using Equation (18) gives that
max b EH p-Q.
E [le SE.
D.3 Proof of Theorem 4.1
Proof of Theorem 4.1. We first specify how to build set of sleeping experts settings from problem definition. For that, consider the following set of experts:
(9(s.....) : [T] AA.j E Ap.O {+1}},
ie., we create different expert for each round, each principal- aggent action pair, and each (the use of which will be made clear in the next paragraph). For each expert ((s..j.(a)) G and [T]. define the loss, sleeping/awake indicator, and instantancous regret respectively as:
(1 A Lggon..., (be, Pt) = w. w.())) (be, pt,))
I 1 2 s};
Ti,g A (lag-
where by hej. Pe.j denote the j-th coordinate of the h and vectors respectively.
26

---

Running ADANORMALHEDGE on the instance with G that we specified above, with prior (sunsse)) O ot [44, Section 5.1] guarantees that Vg(s,i.j.o) G.
Reg. (M(5).5.0))
Σ TE
Tt.
5ō (V(V (1- log(kmiT)
(19)
where (()) hides lower order poly-logarithmic terms. Therefore, by simulating the NRBR dynamics, we obtain that with probability at least 2 2, Vivi [k] and S <<ts..
CalEm, gas Part) i-s jEAP (E(+1)
1
Σ Tracnssi (raacasiis max
(Definition 2.3)
1 max
E gmzt
[er.))
JEAr (E(=1)
Rege (Plosissi)))))
+ 1 max max
I In [Cr.g]
t - JEAP 0E
gatte
max max 1 max max Reg. (A(erds))) + t- JEAP (E(11) JEAP (E11)
[ (h, (hr, Pr)
(20)
gwa,
where for the first derivation we add and subtract Σ & and use that because of the NRBR dynamics: & = Pg [Lr. and for the last derivation we have used the definition of er Ly (h, Py) (Equation (6)). We next upper bound the term T as follows:
T = Σ (L, p)] + Σ 7=5 p-0+
E (L, graet
Pr)]
Σ
E (Lr p)]
==s pmlt
E g- (A(Ap)
max
[T. (,, p)] + Σ
(hr
E pEQ,
[T. (h,, p)]
gmitt
$ (tt log 101-881 s)/5)
where the first inequality is by the property of h- being the best strategy for the principal, and the last one uses the fact that max,, <A(Ap) pmg; [g (h,, p)] from the NRBR Equation (8) and martingale concentration bound on the second term
Plugging the upper bound for Q back to Equation (20) and using the regret bound for AdaNormal- Hedge (Equation (19)) we get:
CalErr; (heat Psa)) 5 (log(kmiT)) +0 (og(((>>)/0))
S rr(()
t-s
t-s
E Supplementary Material for Section 5
E.1 Proof of Theorem 5.2
Theorem 5.2 (Restated). For continuous CSGs satisfying Assumption 5. all Eo > O, there exists a finite binning Ho such that if the agent is (0, Io) adaptively calibrated and the principal an appropriately parametrized instance of LAZYGDWOG (Algorithm 3) then:
lim M
Σ 0E RE[M
Σ
Ur(h,, Vo.i) 2 V En-
FM
27

---

Moreover. for any sequence of the principal's 's actions hprry. it holds that:
lim Σ T-000
(p ve) S V* + 60-
(E[T]
E.1.1 Proof of Lower Bound
Proof. Before delving into the proof of the lower bound, we first introduce some notations. Let C(h) _ Up, BR(h)). Let Vgg - (ap. C(h) be the optimal utility restricted in the smaller strategy (2 -5). We use Ve _ EeE[M] Ié.s denote the average feedback that LAZYGDwOG uses update the strategies.
We first consider any fixed & > 0. Combining the guarantees of Lemmas E.4 and E.5, we conclude that there exists finite binning Hh and M. < oc, such that if the agent is (0, addapiivvy calibrated, then vM 2 Mg, the following two inequalities are satisfied at the same time:
sup US - -BR(hh)) S dE(+]
(by Lemma E.4)
(21)
sup
1 M
Σ #E[M]
Up(hs,yout 2 C(hs)
(by Lemma E.5)
(22)
de
Set the parameters according 7/ =oom 2 and 8Φ dom 2 x similar arguments to [51, Theorem 3.1] guarantee that
in Algorithm then
D3
2W7
V
Σ (
B[C(ba)] <
+
Vmn + LBR Dp
BR (2))
$
2
+ 6E(+)
(a)
D3.
2W3
+
Vm
Dp
2nu
where (a) is from Equation (21).
Now we upper bound the difference between V and V/ = maxnee((AP..)) C(h), then we have
V* V max min C(h") C(h') Lu max min |h h'll2 S Lvd, htEAp B)
EAP ('E
where the second inequality follows from Assumption 5.1 that C(h) is -ipsschhtt
The next step to upper bound the difference between the actual average utility and き Σ 2 [[C(hs)]. From Equation (22), we have
E(C(h$))
Σ
Σ
Up(hs, No.i) Se.
FM
6E(1)
6E(+] FE[M]
Finally, putting the above inequalities together, we obtain
V
1
Σ Σ
Up(hs: Ho.s)
ΦM
(E(2)
KE[MA]
<(V* Vi¹) +
V/a
[[C(bb) +
Σ
E[C( TM
Σ
Σ
Up Up Vois
6E(
de (E(
D3
2W3 of
<Lydomn x-
Vmb Dp te.
2%o
Taking the limit of + + oo, the above incqualities imply
lim
Σ
Σ
Up(hs, vo.)) 2 V E (LeaDP + 1).
ΦM
6 SE[M]
Since the above arguments hold for all 0, taking
LnDptI proves the theorem.
28

---

E.1.2 Proof of Upper Bound
For fixed E > 0, let De {æ1.-.. ,.)) be an e-grid of Fp under & distance, and let Hl be the
continuous binning specified by Equation (26). We have:
E
Up(h,,
Σ
Σ
(:(D:)Up(h,,BBR) BR(P:))
AE(T)
iE[T] NE(T)
Σ
Σ
wP:):)
(e(h,,BR(zz)) + La LBR ||p: 1:
ME[T AE[T]
22c
EiE(m wi (P:))
Σ w:(P:)
Up(
BR(x;)) + LLR
EIE(T wP:))
(E(T]
nr (i)UUrr (hr (1), BR(x)) 2n2
nr (Up( (R) L1 (i) hr(()]l))) + 2
EE
nr (1)
L1 Σ (1) (1) (1) (1 +2 LaaT
sEli
(A)
(B)
(23)
In the above inequalities that lead to (23), step (a) is because Up is L-z-Lipschizz in the second argument and BR(.) is Lag-Lipsshhtz, and the fact that w; (Pt) only when || x 2c. In step (b), we used Jensen's s incquality because Up in concave in the first argument. Step (c) follows from the definition ny (t) and by (i) in Definition 2.3. The last inequality (d) uses the fact that Up is L, -Liischht in the first argument to decompose Up (P)(()). BR(x:)) into calibration error (i.e., term (B)) and Up(P (1), BR(x.)) where the strategy that the agent best responds to is close to the principal's strategy (i.e., term (A)).
We can further bound (A) and (B) in Equation (23) respectively as follows:
(A) S Σ (i( (Ur(x,, BR(x;)) + Lall (1) V'T (2E)T,
xE[M]
and
(B) < LTT Σ (hir, PIT) S IrlPe w.p. 2 - 8.
*E(!]
Therefore, putting the above bounds together, we obtain that with probability 2 6,
Σ Uphh, 9e) V (Lr))))rr(()) 2(L1 + L2LBAJE.
[E(T]
Since the above derivation holds for any E 0, it suffices take such that 2(L1 + L2LEa)E = Eg. Finally, since DDl < do and rT) = o(1), taking the limit of T + oo proves the upper bound:
lim T
Σ
Up( vi) S V* E
T
[E[T]
F.2 Key lemma: asymptotically correct forecast
In this section, we state and prove the key lemma for establishing Theorem 5.2. Intuitively, this lemma states that for any strategy Ar, as long as the principal repeatedly plays h for enough rounds, the fraction of times where the agent's forecast is close h will converge to 1.
29

---

Lemma E.1. For any Eo > O, there exists finite binning 1l. such that if the principal repeatedly plays any Ap for M rounds and the agent's 's forecasts PI:M are (0, 1o)) adaptively calibrated, then:
lim 1 MI [M] Ilp. bll2 mos =0
In particular, if the calibration enror (defined in Definition 2.3) has rate r(-) E o(1) with respect to [M]:
(24)
No then
m r(M).
{s E [M] Ip.. h1l2 2 su3
(25)
E0
Proof of Lemma E.I. We first describe the construction of II. For ε teo. let Dr = (.,,'.,,,, be an E-grid of Fp under lg distance, and A(p; R) _ (R ||p x112) be the tent function with center z and radius R. Consider the following binning
11o (p)
E D3
(26)
Eje( A(p; 28)
Clearly, [1op] = 1 because the diameter of Fp bounded stated in Theorem 5.1. We can also verify that 1o satisfies Lie[r] w; (p) = for all E Fp because w;(p) is defined as the normalized tent function.
Now prove that Ho satisfies the desired property. Since the agent is adaptively calibrated to Ho. we have that Vi E [7].
72 LM (i) M
(( (2) M
(t) - h1/2 vm lim
[[PIn(() - blllo Vmm((M).
M
Now, for 30 c.. let D C De be defined as
D {az E De ||,
h 2 8).
(27)
Since | S 1D2l= < oc, taking the sum of calibration error over bins in ( we obtain
Σ
M[M (1)
(t) h
1
Σ
Σ
w. (p.) P&)
Vmlr(M). (28)
M
M
(
.E[M]
We can further lower bound (28) and get:
Σ
Σ +E[M]
wi (p.) Pa)
Σ
Σ .E[M]
w. (px) ((h 2x) + (x: Po))
M
!
(a)
Σ
Σ
w.(p.)(h- - xz)
Σ
w (p=) - -pa)
M
!
BE[M]
ME[M]
Σ
wi(pss)
||h--xi]] xill2 ||+ -ivi-palla)
M
E ( (E[M]
(c)
Σ
MIM - 22x 2 Eo
Σ
T[M (1).
M
4M
In the above inequalities, (a) and (b) are both due to triangle inequalities, and (c) is because ||h
aill2 2 8 from the definition of (d) in (27) and ||æ; Pxl12 < 2s whenever (p())) > 0 +
A(.:: 25) > Together with (28), the above set of inequalities imply
1
Σ
(1) <
Σ
Σ sE[M]
w. (p.)) P.)
< 4yml r(M). (29)
M
Eo
M
30

---

On the other hand, since De is an e-grid of Fp, if llp - h|/2 2 Eo. there must exist 24 D2 such
that ||= P=lla S E, which implies
3
| 2 > lp hl/2 ||= Pall2 2 60
_00 = 8
3i D
As for the weight that wi assigns to Ps. we also have
APs; Fi, 25)
25 - 8
wi(ps) ΣjE( Mpssaaj, 25)
1 28
21
Therefore, we have
= 21
M { E [M] -ep.-l-hi - hl| 2 mo3 $ M
Σ
Σ
(2))
Σ maas( (i) (30)
t
I.ED sE[M]
xEDD
Finally, combining inequalities (29) and (30), we conclude that
8/mB2 r(M),
M {s E [M] Ip. hll 2 fo} - (21)
Jim M
Σ E.ED!
which proves (25). The proof is complete by taking the limit of M + O. which guarantees r(M) and immediately implies the convergence result in (24).
L
Note that the rate in Equation (25) does not depend on strategy h. Therefore, in the context of running LAZYGDwoG (Algorithm 3), we can turn Lemma E.1 into the following uniform convergence result across epochs:
Proposition E.2. For any Eo > O, there exists a finite binning Hg such that 4T > O, if the principal runs LAZYGDwOG for o epochs where each epoch has length M, and the agent's forecasts (Ps.)) [M are adaptively calibrated with respect to Hg, then we have the following uniform convergence guarantee:
lim sup M M-+000 6E(T) M
{s [M] Ilp... - -holl 2 co) =
(31)
Remark E.3. Note that the rate (25) has a polynomial dependency on [To) which, due to the construction in the proof of Lemma E.I, ends up being exponential in m because it is the size of a 5o A grid of the domain Ap. To improve on this exponential dependency, one possible approach is to design calibration, which is more common in recent literature. For example, Hart [36], Foster and Vohra 129, 30] are defined using &ı calibration error rather than loo. Another approuch is to avoid using naive conversion from Eo to & calibration error in (28), which leads to a polynomial dependency on the number of bins. These two approaches are equivalent ways of formulating the problem, and they both lead to interesting open directions.
adaptive calibration algorithm for the agent that achieves the stronger notion of E
E.3 More auxiliary lemmas: approximate best response and closeness in utility
In this section, we use the results in Appendix E.2 to show that the average feedback 1 E>e[M] Vo.s in epoch o E [ is close the best response BR(h,) (Lemma E.4), and that the principal's 's average utility in this epoch is close to (h BR&))) (Lemma E.5).
Lemma F.4. For any Eι > O, there exists finite binning Tl and Mo < such that when agent's forecasts Pist are adaptively calibrated with respect to Tlg then we have that VM 2 Mo.
1 M
sup 6E(0]
Σ .E[M]
yo.s BR(hb)
SE1
Proof. Let = 51_ and Hg be the binning that satisfies Proposition E.2 for parameter Ep- Therefore,
we know from Equation (31) in Proposition E.2 that for 82 2.Dp--L there exists Mo such that VM 2 Mo.
1
sup @
{s
[M]
|P... holl2 2 Ea} S S
(32)
M
31

---

Using Lipschitzness of the best response mapping BR(.), we have that Vo E [Φ].
1
Vo.s
BR(b,)
M
ME|M
Vou. BR(h
(Triangle inequality)
M
sE[M]
SB
| b
(BR(-) is LBx-Lipsche -ia--Lssshhtz)
M
sE[M]
<Bn
E
diam (Hp)+
Σ
Eo
M
+E[M]: 2oll2s0
sE(M))llps..-bu -a Iill
< M
(E2M Dp + M..M) .00)
(Eq. (32) & diam(Hr) Dp)
<Dp Las C2 Lar ED 2
E1
Lemma E.S. For any 61 > O, there exists finite binning Th and Mo < such that when agent's s
forecasts Pia are adaptively calibrated with respect Nlg then we have that VM 2 Mo.
sup PE(
Σ .E[M]
Up(hs Bo.s) Up BRob)) S E1.
(33)
M
Proof. The proof of this lemma is very similar to that of Lemma E.4, with a different choice of constants Eo and Eg. Note that since Up Lz-Lipcchitz in the second argument, we have
1 M
Up(hs,No.c) Up(h,, BR(})) +E[M]
Σ
1
Σ
IU [Up(ha:Vo..) Up BR(h)))llz
M
SE(M]
<
llve. - BR(b,)ll2
M
.E[M]
The rest of the proof follows from Lemma E.4 by choosing Eo = 2LaLm and E2 2-Dp-LmLi
Future Directions
Adaptive Calibration Although the results in this paper all stated in terms of the calibbratio error (e.g.. maximun instead of sum over bins), a lot the existing calibration literature focuses on f1- calibration error [29, 30]. is an interesting problem whether we can get liaadppivve calibration error bounds without a polynomial dependency in the number of binning functions, where obtaining such bounds lead polynomial improvements on the dependency of (the number of agent's actions). In the case of continuous calibration, it is an open problem to obtain uniform (adaptive) calibration error bounds for parametric nonparametrie continuous binning function classes. Resolving this open problem could lead to a better rate for the learning direction of Theorem 5.2, as the current result uses naive fac -t-é, conversion of calibration error that leads linear dependency on the number of binning functions, which turns out to be exponential in the dimension of the principal's 's action space. See Remark E.3 for more details.
Convex optimization from membership oracles In the case of finite Stackelberg games, we use the results of Lee et al. [42] to solve the constrained convex optimization problem each polytope from approximate membership queries, where the key step is polynomial reduction from approximate separation oracles to approximate membership oracles. However, the precision of the constructed separation oracle is worse than the precision of the membership oracle, which naturally leads to
32

---

worse precision of the final optimization solution. To be more specific, given e-membership oracle to convex set K, Lee et al. [42] can only guarantee the returned solution to be g//10 -optimal and contained in B2 e el/10), where "No > 6 is fixed constant. An understudied open direction in the optimization community is whether variant of Lee et al. [42] can return solution in B2(K, + 6) for 5 that is any tunable parameter, with runtime depending polynomially on 1/6.
Open Problem F.1. Given an s-approximate membership oracle of a convex set C T and an eval- uation oracle of convex function J. is there an optimization algorithm that, under sufficient regularity conditions, for any unable ö, finds neur-optimal solution & such that f()) S mingeK [(x) g1/10 and & E B2(K, + 8) within poly(m) (m. 1/8, log(1/=)) calls to both oracles?
We note that resolving Open Problem F.1 will immediately lead to exponentially improved rates for Theorem C.14 for any finite Stackelberg games. To this, recall that the algorithms that achieve Theorem C. require repeated calls to the constructed APPROX MEM oracle. This oracle provides a-aaprroeemaee response, indicating whether not the query point belongs to the ez-conservative version of each best response polytope. The number of samples used in simulating each oracle call is exponential in Ea The algorithm by Lee al. [42] amplifies the inaccuracy of APPROXMEM at polynomial rate of Yo- Consequently, imposing a constraint of E1 S E2 However, resolving Open Problem F.1 removes this constraint and introduces much milder one, i..., E1 & E2 8, where is tunable parameter. This adjustment leads to exponential improvement in the final sample complexity.
E1
33


Reviews:
[{"review_id": "8Q6TqDok94", "reviewer": "Reviewer_Crqu", "summary": "The paper defines and studies a new Stackelberg games setup. Rather than making some standard assumptions --- e.g. that the principal and/or the agent exhibit specific types of play (e.g. agent playing no regret), or assuming access to the agent’s best response oracle, etc. --- this paper only assumes that the agent will be playing by best-responding to (appropriately) calibrated forecasts of the principal play. In this Calibrated Stackelberg Games setup, the authors show that: (1) The principal, by only knowing that the agent will be playing in a calibrated way, can achieve exactly (no more and no less than) the Stackelberg value of the game over a repeated interaction, by following an explore-then-commit style algorithm; (2) The agent has an efficient algorithm for producing said calibrated forecasts (in fact, strengthened by the notion of adaptivity --- meaning that calibration should hold over all subintervals of the time axis). These results are further complemented by e.g. considering both finite and continuous action spaces, as well as an adaptive calibration algorithm.", "questions": "For the substantive questions, please see my questions above on: (1) the principal needing to know the calibration rate; (2) the requirement of adaptivity of calibration; (3) some elements of Section 3 such as property (P1) etc. \n\nHere, I’ll quickly list a sampling of a few typos and notational issues:\nLine 300: bound*ed*\nLine 285: Where is the notation L_g defined?\nLine 276: Brackets around sigma in the subscript for g\nLine 222: Probably meant to say that (h hat, y) is an equilibrium rather than just h hat\nLine 201: Where is h bar_T defined?\nLine 174: The fundamental constructs from Definition 2.2 are reviewed, not from Eq 1\nLine 102: converged *to a* Stackelberg equilibrium\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "As intended by the authors, they are able to demonstrate that Calibrated Stackelberg games indeed show potential towards relaxing/moving away from various restrictive assumptions (on what the principal and the agent observe and how they play) in the literature. An important moral takeaway is that the same old Stackelberg value --- which one might have expected might in fact require the principal and the agent to (more or less) explicitly observe each other’s play --- can be achieved over time by only asking the agent to use calibrated forecasts of the principal’s play (which is a fairly mild requirement), and the principal to know and use the fact that the agent exhibits calibration. \n\nIn fact, this conclusion is carefully shown to hold (existentially and algorithmically) both for finite and continuous action spaces --- which, while to be morally expected from standard minimax reasoning, still takes work to rigorously establish and shows thoroughness on the authors’ part.\n \nIn terms of the techniques employed, the exploration process for achieving this value on the principal’s side is, in fact, not very straightforward to design both for finite and continuous action spaces; so, there is a healthy dose of sophistication involved. The adaptive calibration algorithm, on the other hand, quite straightforwardly follows from existing techniques at the intersection of no-regret dynamics and online multiobjective settings. \n", "weaknesses": "I did not spot any technical weaknesses, and the contribution of this paper to both the Stackelberg games and the calibration literatures is solid. So overall, the paper does not have any significant weaknesses. However, \n\nI would, however, like to point out that the principal needing, in certain parts of this new framework, to know the calibration rate of the agent is not to be taken lightly given that an important motivation of this paper is to relax, as much as possible, the prevalent specificity, in existing literature, of the requirements on what the principal and the agent should know. I would appreciate it if the authors could provide further elaboration of this, beyond the brief mention in the conclusion.  \n\nSecondly, while having *adaptive* calibration guarantees is nice, compared to regular marginal ones, I’m not clear on how or whether this adaptivity interacts with the proposed theory of CSG or is more or less orthogonal? In other words --- okay, using the standard sleeping experts technique for establishing adaptive online guarantees, it is possible to make the agent calibrated on every [s, t] rather than just on [1, T]; but does that really matter for e.g. being able to achieve the value V* in the process of play, or any other desirable Stackelberg properties? Since the main point of the paper is to propose a theory of calibrated Stackelberg games, it is important to be clear on whether this is an essential element of such a theory or was just added to the paper for good measure. If this is in fact an essential element, I’d like to ask the authors to clarify this.\n\nI also did find the presentation suboptimal --- the paper reads quite densely; especially, in my experience, when it comes to the proof sketch after Theorem 3.2 in Section 3. I invite the authors to revamp that part of the presentation for the rebuttal phase. Some specific things that I’d appreciate would be (1) alleviating the notational/explanatory tedium related to condition (P1) --- I am still not clear on how strong or weak it is, and where exactly things must break if it wasn’t required; (2) adding a high-level description (preferably involving more prose) of how the agent’s calibration figures into what the algorithm for the principal does. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive and insightful comments. Below we address the specific questions.\n\n**The principal needs to know the agent’s calibration rate**\n\nWe will add a more detailed discussion to our paper.\n\nOn the one hand, the principal does *not* need to know the agent's exact calibration rate. Knowing an upper bound or approximate value suffices for learning a near-optimal commitment against calibrated agents. Given that the calibration error has to be small and vanishing for our setting, we think that assuming some knowledge of an appropriate upper bound on a small calibration error provides a good tradeoff between relaxing the assumptions found in previous literature and still obtaining provable guarantees in Calibrated Stackelberg games.\n\nOn the other hand, if the principal is completely unaware of the calibration rate or the calibration error is large, several complications arise. Since the agent's beliefs might come from any forecasting algorithm, their (average) responses to the principal's strategies may be suboptimal. This uncertainty complicates the exploration phase, where the principal must decide between improving feedback accuracy by repeating the current strategy or updating the strategy based on existing feedback. Therefore, we believe that some degree of knowledge regarding calibration rate is necessary, and proving this necessity is an intriguing question for future research. Moreover, if the calibration error is large (and thus harder to justify having an approximate upper bound), the agent’s behavioral model can fit any online algorithm. It is known that in such situations, the principal’s utility is not characterized by $V^*$. For example, during a commit phase, even playing the optimal strategy $h^*$ may lead to high suboptimality if the agent doesn't best respond due to high calibration error of the forecasts. \n\n**The requirement of adaptivity**\n\nWe believe that lack of adaptive guarantees poses a technical challenge for the design of learning algorithms and likely impacts the convergence rates to $V^*$. At a high level, adaptivity ensures that each exploration step (referring to a sub-interval) is approximately correct, enabling the principal to more effectively search the space and find a final strategy that is both robust and near-optimal.\n\nMore specifically, recall that during the exploration phase of the Explore-Then-Commit algorithm, the principal first learns the optimal commitments within each robustified best response polytope, then selects the one with the highest utility. In this process, the key challenge is determining whether a strategy robustly lies within a specific best response polytope. We address this by sampling test strategies around the queried one, playing them repeatedly to find an approximate best response. This is enabled by adaptive calibration within time subintervals $[t_1,t_2]$ where each test strategy is played. Without the adaptivity property, however, ensuring an approximate best response would require a much larger $t_2$ relative to $t_1$ to make the interval $[0,t_1)$ negligible compared to $[0,t_2]$, where marginal calibration applies. This increases the repetitions for each test strategy. While this is not a proof of an algorithm-independent lower bound on the convergence rate, we wouldn’t be surprised if such a proof could be formalized that indicates that the lack of adaptivity property would result in the convergence rate becoming much worse, possibly exponentially. We believe this is an interesting question for future work.\n\n**The presentation in Section 3** \n\nWe plan to enhance the clarity and structure of Section 3.1 as follows:\n- **Elaborating on the objectives for Explore phase**: Before delving into the notations $B\\_2(S,\\varepsilon)$ and $B\\_2(S,-\\varepsilon)$, we'll overview what we aim to achieve in the Explore phase:\n  - **Idealized Setting**: Initially, we'll consider a setting with zero calibration error, where the agent's forecasting algorithm is perfectly and adaptively calibrated, leading to $y\\_t=\\text{BR}(h_t)$ at every round. Within the Explore phase, the task simplifies to identifying a near-optimal strategy through best response oracles, satisfying $U_P(\\tilde{h},\\text{BR}(\\tilde{h}))\\ge V^*-\\varepsilon\\_1$ for a predetermined $\\varepsilon\\_1$. In the Commit phase, given that the agent always plays $\\tilde{y}=\\text{BR}(\\tilde{h})$, the Stackelberg regret can be upper bounded by $\\varepsilon\\_1|T\\_2|$. Hence, the Explore-Then-Commit algorithm's regret is bounded by $V^*|T_1|+\\varepsilon_1|T_2|$.\n  - **Realistic Setting**: Moving away from the idealized setting, we must account for possible discrepancies between $y\\_t$ and $\\text{BR}(h_t)$ due to calibration error. This introduces: (1) An increased sample complexity in the Explore phase, given the necessity to learn a near-optimal strategy from noisy responses; (2) Potential deviations from the action $\\tilde{y}=\\text{BR}(\\tilde{h})$ due to miscalibrations in belief. To address the first challenge, we employ Algorithm 2 which constructs an *approximate* best response oracle by repeatedly interacting with a calibrated agent. For the second challenge, we require our learned policy $\\tilde{h}$ to be robust against inaccurate forecasts. This is reflected in condition (P1), which necessitates the ball of radius $\\varepsilon_2$ around $\\tilde{h}$ to be fully contained in the polytope $P_{\\tilde{y}}$. The critical insight from (P1) is: for any forecast $p_t$ that results in a best response $y_t\\neq\\tilde{y}$, there must be a minimum distance of $\\varepsilon\\_2$ separating $p_t$ from $\\tilde{h}$. Combined with the definition of calibration error, this relationship allows us to establish an upper bound on the number of such rounds.\n\n- **Added figure**: We'll add two figures illustrating the notations $B\\_2(S,\\pm\\varepsilon)$ and the relation between $\\tilde{h}$ and $\\bar{p}_{T_2}$. The PDF containing the figures is attached to the global response."}, {"review_id": "TOmAPgrsrc", "reviewer": "Reviewer_M2eA", "summary": "In this work, the authors consider a problem of Calibrated Stackelberg Games (CSG), which is a generalization of the Stackelberg Games. These framework differ from the standard online learning problems as in the SG framework instead of only having a single learner entity, there is a principal and an agent. The key difficulty introduced by the CSG framework is that the agent needs to respond to the action of the principal without being able to observe it. Instead, the agent have to forecast what they expect the principal's action to be and aim to best respond to that believed action from the principal. \nAs this learning objective is more challenging than classic learning problems, the authors consider the question of whether the principal can achieve optimal utility (V* being the utility of the principal's action with the highest best response) in this calibrated game. \nAn important part of the paper is dedicated to the construction of adaptively calibrated forecasts and of the CSG protocol. Then, the authors present and analyse an algorithm that can achieve optimal utility with high probability. \nThe principal's algorithm is a simple explore then commit strategy. This exploration starts with  $log T/\\eta$ uniform uniform strategies samples, for which the agent returns an associated response. Then the principal tries to find approximately optimal strategies for each of the agent's response, and ends up picking the one of these that yields the highest utility. \nThey then analyze the performance of the algorithm and show that it assumptotically reaches the optimal utility for discrete and continuous games.", "questions": "Do you think that it is possible to extend your work beyond the asymptotic guarantees that you provide? \n\n", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper studies a generalization of the Stackelberg games, which are challenging in the online learning framework, and show that it is possible to reach optimal utility for the principal even if the agent doesn't have access to the strategy picked by the principal ahead of time. \nThese results are novel, and the analysis of the algorithm builds upon standard online learning algorithms. The authors took particular care in connecting the CSG framework with other online learning problems such as sleeping experts.\n\nThis work provides some good preliminary baselines for the SCG problem, and should provide a strong foundation for future works to build upon it. ", "weaknesses": "The main weakness of the paper is that the results provided, meaning that the algorithm presented can find the optimal utility, only holds asymptotically, making it difficult to appear useful in practice, when we only have a limited time-horizon. \nIt would be useful to discuss extensions of this work that could achieve stronger guarantees in finite time horizons.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of our work.\n\n**On whether Nonasymptotic guarantees are possible**\n\nYes, absolutely! While we state our results in asymptotic forms in the main body, we have already provided non-asymptotic guarantees for finite time horizon in the appendix. Specifically, please refer to Thm C.14 in Appendix C.6 for a more formal version of Thm 3.2. We opted to defer these detailed rates to the appendix due to their complexity and the potential difficulty in interpretation for general games, but we are happy to instantiate them for specific settings like security games and present them as corollaries in the main body.\n"}, {"review_id": "n3OWoPQysX", "reviewer": "Reviewer_j8Y8", "summary": "This manuscript introduces the concept of calibrated forecasts in repeated Stackelberg games (SG) and proposes two concepts: the calibrated Stackelberg games (CSG) that generalizes the standard SGs and the adaptive calibrated forecast. The technical contribution is as follows: First, a principal's learning algorithm against adaptively calibrated agents is proposed where the average utility of the principal converges to the Stackelberg value, which is the best possible average utility under this setting. Second, a forecasting algorithm that meets the concept of calibrated forecast is proposed, which means that the agents can actually perform calibrated forecasts for the principal's action. Third, even for continuous Stackelberg games where the action sets of principal and agent are continuous, there will be principal's learning algorithm against certainly adaptively calibrated agents where the average utility of the principal converges to the Stackelberg value, the best possible one.", "questions": "P.3, l.128: \"Definition 2.2 is weaker than the standard definition of calibration...\" What does \"weaker\" mean? As far as I understand, introducing a binning function \\Pi is a generalization compared to the standard definition but it does not strengthen or weaken the assumption.", "limitations": "The authors describe some limitations (and thus future directions) of this work in the conclusion section and in Appendix F.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The notion of calibrated forecast, on which the paper is entirely based, seems much reasonable; compared to the original definition, it is generalized by introducing a binning function, enabling us to represent some rules for choosing the best response of agents (deterministic/randomized tie-breaking rule in the manuscript). Although its assumption seems much stronger and unrealistic, this work succeeded in proposing forecasting algorithms that meets the conditions of adaptive calibration by combining online algorithms with the study on novel game dynamics; its technical contribution seems far non-trivial. For the principal, this work succeed in proposing learning algorithms that achieves the best possible average utility asymptotically, meaning that the proposed learning algorithm is asymptotically the best one under this setting.", "weaknesses": "The connection between the proposed concepts (calibrated Stackelberg games and adaptive calibrated forecast) and the applications the manuscript claims (Stackelberg security games and strategic classification) is unclear from the manuscript although it is claimed that the results \"immediately apply\". Thus, it looks like that this work addresses an artificial setting in Stackelberg games. To avoid this, the authors should carefully review the connection between the proposed concepts and the applications at least in the Appendix.\n\nMinor comment:\nIn Theorem 5.2, unlike Theorem 3.1, the binning \\Pi_0 is fixed as Eq. (25), but it is described only in the Appendix. As far as I read the main part, I'm afraid that the binning is irresponsible and not related to the agent's policy. For the sake of completeness, please consider describing the actual formula for the binning and its meaning in the main article.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive feedback on our paper. We’re happy to see that the reviewer recognizes the importance of addressing Stackelberg games through calibration, moving beyond traditional assumptions. We address the specific questions in the subsequent paragraphs:\n\n**Stackelberg security games and strategic classification as applications of CSG**\n\nThank you for the suggestion. We'll add the following paragraph to the revised version of our paper to explain how security games and strategic classification falls under the framework of CSGs:\n- **Stackelberg security games (SSG)** are a prominent example of finite Stackelberg games that captures the strategic interactions between an attacker (or agent) and a defender (or principal). In an SSG, the defender commits to a probabilistic distribution of security resources across $k$ targets, and the attacker best responds to it by attacking the target that maximizes its utility. Specifically, the defender's action space $\\mathcal{A}_P$ includes the finite set of schedules, where each schedule is the subset of targets that can be simultaneously defended by one security resource. The attacker's action space $\\mathcal{A}_A$ is the finite set of targets $[k]$ that the agent can attack. Transitioning this into our Calibrated Stackelberg Game (CSG) model, we depart from the traditional assumption that the attacker has perfect knowledge of the defender's strategy. Instead, we consider realistic attackers that base their decisions on calibrated forecasts of defender's strategies.\n- **Strategic classification** is an application of continuous SGs where the principal aims to learn classifiers that remain robust when agents strategically manipulate their features to receive positive classifications. We use the model of [Dong et al, EC 2018] to illustrate how it falls under the framework of continuous SGs. In this model, during every round of interaction, the principal commits to a linear classifier $\\mathbf{h}_t\\in\\mathbb{R}^d$, then the agent with initial feature $\\theta_t\\in\\mathbb{R}^d$ best responds to the classifier $\\mathbf{h}_t$ by modifying its feature to $\\tilde{\\theta}_t=\\theta_t+w_t\\in\\mathbb{R}^d$ that maximizes the dot product of $\\langle \\tilde{\\theta}_t,\\mathbf{h}_t\\rangle$ minus the cost of movement $c_t(w_t)$. The principal's utility is the negative logistic loss or hinge loss. In the above model, the agent has full knowledge of the classifier $\\mathbf{h}_t$ before manipulating its features, which might be unrealistic for applications like college admissions where the classification rules are opaque to the agent. Our CSG framework relaxes this assumption by allowing agents to best respond to beliefs about the classifier $\\mathbf{h}_t$ generated by any calibrated forecasting algorithm. Our results applied to this setting show that when agents’ features are drawn from a stochastic distribution, the principal's optimal average utility is captured by the same Stackelberg value obtained when agents have direct knowledge of $\\mathbf{h}_t$.\n\n**Binning function in the continuous setting**\n\nWhile the continuous setting’s binning may appear less intuitive, it is still related to the agent’s policy. In the discrete setting, the grouping of the principal's strategies into bins is based on whether they induce the same best response from the agent. When extending this to a continuous setting, the concept remains grounded in the agent's best response, but with some adjustments to accommodate the continuous action space. Specifically, we define the binning function based on whether the induced best responses are in close proximity rather than being identical. This is achieved by first creating an $\\varepsilon$-net of the strategy space, followed by smoothing the discontinuous net into continuous $\\Lambda$ functions that serve as the bins after normalization. Intuitively, the $\\Lambda$ functions, defined as $\\Lambda(p)=(R-\\\\|p-x\\\\|_2)\\_+$ for all $x$ in the net, resemble the shape of \"tents\". These functions peak at $x$ and smoothly decrease to 0 as $p$ moves away from $x$. Consequently, strategies sharing a nonzero $\\Lambda$ function (or equivalently nonzero binning function) must be close in $l_2$ distance. This, in turn, implies that their best responses must also be close, given the assumption that the BR function is Lipschitz. In this manner, the cover still respects the distance metric regarding the agent's response, ensuring that the binning is not irresponsible or unrelated to the agent's policy, but rather a nuanced adaptation to the continuous setting. We will further clarify this in the final version of the paper.\n\n\n**Binning as a weakening of the standard calibration assumptions**\n\nWhile the introduction of binning is indeed a generalization of the standard calibration definition, it's a definition that can only weaken the assumption, because binnings serve as a coarsening of the representation of functions on which the agent wants to achieve vanishing calibration error.\n\nIn fact, the finest-grain bin, which corresponds to the indicator function $w_{\\mathbf{p}}(x)=\\mathbf{1}\\\\{x=\\mathbf{p}\\\\}$ for every possible strategy $\\mathbf{p}$, would lead to the standard definition of calibration as it inspects the calibration error for every strategy independently; and calibration wrt this binning immediately imply calibration wrt all other normalized binnings. Given our approach of defining the binning based on the agent's best response function, our generalized calibration assumption is weaker than the finest-grained binning and forms a realistic assumption that the agents can easily achieve.\n"}]

Author rebuttal:
Please refer to the attached PDF for the added figures.

Meta-review: This paper introduces a new framework---Calibrated Stackelberg Games, which is a generalization of the standard Stackelberg Games (SGs) framework. Rather than standard strong assumptions on the behaviors of principle and agents, this new framework only assumes that the agent will be playing by best-responding to calibrated forecasts of the principal play. This paper further consider a stronger notion of calibration---adaptive calibration, and show that the principal can achieve utility that converges to the optimum Stackelberg value of the game.

The setting is novel which addresses certain drawbacks of prior framework, and the results make solid contribution to the community. The author feedback effectively addressed the concerns of reviewers. We thus recommend acceptance.
Decision: Accept (spotlight)