Learning to Play Multi-Follower Bayesian Stackelberg Games
Authors: Gerson Personnat
Tao Lin
Safwan Hossain
David C. Parkes
Venue: ICLR 2026 Poster (2026)
Keywords: Online Learning; Stackelberg Games; Algorithmic Game Theory
Primary area: learning theory
TL;DR: We develop online learning algorithms for multi-follower Bayesian Stackelberg games with unknown type distributions under multiple feedback models.

Abstract: In a multi-follower Bayesian Stackelberg game, a leader plays a mixed strategy over $L$ actions to which $n\ge 1$ followers, each having one of $K$ possible private types, best respond.
The leader's optimal strategy depends on the distribution of the followers' private types.
We study an online learning version of this problem: a leader interacts for $T$ rounds with $n$ followers with types sampled from an unknown distribution every round. The leader's goal is to minimize regret, defined as the difference between the cumulative utility of the optimal strategy and that of the actually chosen strategies. We design learning algorithms for the leader under different feedback settings. Under type feedback, where the leader observes the followers' types after each round, we design algorithms that achieve $O\big(\sqrt{\min(L\log(nKA T), ~ nK ) \cdot T} \big)$ regret for independent type distributions and $O\big(\sqrt{\min(L\log(nKA T), ~ K^n ) \cdot T} \big)$ regret for general type distributions.
Interestingly, those bounds do not grow with $n$ at a polynomial rate. 
Under action feedback, where the leader only observes the followers' actions, we design algorithms with $O( \min(\sqrt{ n^L K^L A^{2L} L T \log T}, ~ K^n\sqrt{ T } \log T ) )$ regret.
We also provide a lower bound of $\Omega(\sqrt{\min(L, ~ nK)T})$, almost matching the type-feedback upper bounds.

Published as a conference paper at ICLR 2026
LEARNING TO PLAY MULTI-FOLLOWER BAYESIAN STACKELBERG GAMES
Gerson Personnat, Tao Lin, Safwan Hossain, David C. Parkes John A. Paulson School of Engineering and Applied Sciences Harvard University
ABSTRACT
In multi-follower Bayesian Stackelberg game, leader plays mixed strategy over L actions to which n 2 followers, each having one of K possible private types, best respond. The leader's optimal strategy depends on the distribution of the followers' private types. We study an online learning version of this prob- lem: a leader interacts for T rounds with followers with types sampled from an unknown distribution every round. The leader's goal is to minimize regret, defined as the difference between the cumulative utility of the optimal strategy and that of the actually chosen strategies. We design learning algorithms for the leader under different feedback settings. Under type feedback, where the leader observes the followers' types after each round, we design algorithms that achieve O (/min log( K AT), nk) TT) regret for independent type distributions and K*} K=)-T) regret for general type distributions. Interest- ingly, those bounds do not grow with n at a polynomial rate. Under action feedback, where the leader only observes the followers' actions, we design algorithms with Ominn| /nnKkA'' LT log T, K" / logT") T'}) regret. We also provide a lower <Tl
bound of O (0(1miii /mimmL nK]T). almost matching the type-feedback upper bounds.
INTRODUCTION
Stackelberg games are a fundamental model of strategic interaction in multi-agen systems. Unlike normal-form games where agents simultaneously play their strategy, Stackelberg games model leader committing to their strategy; the remaining follower(s) take their actions after observing the leader's commitment (Conitzer & Sandholm, 2006 Von Stackelberg 2010). Such asymmetric interactions ubiquitous in wide range of setting, from a firm entering market dominated by an established competitor (Von Stackelberg 2010 to an online platform releasing features that influence consumers that platform (Zhao et al. 2023 Cao et al.] (2024), to security games (Balcan) et al. 2015; Sinha et al. (018)) to strategic machine learning (Hardt et al.) 2016 Hossain et al. 2025). They also form the foundation of seminal models in computational economics like Bayesian
Persuasion (Kamenica & Gentzkow 201T) or contract design (Dütting et al. 2024) that capture more structured settings with asymmetries relating to information or payouts respectively.
In these settings and beyond, there is one key question: what is the optimal strategy for the leader to commit to? Answering this question requires knowing how the follower(s) will react the leader's strategy, which typically boils down to knowing the followers' utilities. The Bayesian approach attempts to relax this complete information assumption. Pioneering works like Conitzer Sandholm (2006) assume that followers' utilities are parametrized by hidden types from a known distribution. Here, the leader aims to compute the Bayesian Stackelberg Equilibrium: the strategy maximizing the leader's 's expected utility with the followers' types drawn from the known distribution.
In many of the settings mentioned, even the Bayesian perspective may be too strong and unrealistic: the leader (c.g., online platform, dominant firm) may only know the structure of the followers' utilities but not the distribution their types (Cole & Roughgarden, 2014). While not much can be achieved in single round of such game, the leader can often interact with the followers over multiple rounds and learn about them over time. The leader must, however, balance learning with playing the optimal
correspondence Intao@cuhke edu. en or shossal n www.haarard...... edu.

---

Published as a conference paper at ICLR 2026
strategy given current information the well-known exploration-explotttioon trade-off in the online
learning literature.
This paper comprehensively studies the learning and computational problem for an online Bayesian Stackelberg game (BSG). Specifically, we consider the interaction over T rounds between a leader and followers, each realizing one of K possible private types at each round. To our knowledge, this is the first work on online learning in BSGs with multiple followers. We study two feedback models: observing realized types of the followers, or observing their best- responding actions, after each round. Our core objective is exploring how these feedback models affect the learnability of the optimal strategy. which is challenging for several reasons. First, with multiple followers, the unknown joint type space is exponentially large. Further, followers' taking best-responding actions means that the leader's utility function is discontinuous and non-convex. Lastly, even the offline single-fllower version of this problem has known computational challenges (Conitzer& & Sandholm, (0066) key technical tool used to unravel this is geometric characterization of the leader's strategy space in terms of best-response regions (presented in Section B). Section uses this and an observation about learning type distributions vis-a-vis learning utility to provide algorithms for both general type distributions and independent ones. A matching lower bound is also provided. Section [5 then studies algorithms for the action feedback case, where we leverage our geometric insights along with techniques from linear bandits. Table ( summarizes our results. Throughout, we comment on the computational complexity of our algorithms and uncover interesting trade-offs that situate our work with the broader literature on Stackelberg games.
Our Contributions:
Table 1: Regret bounds for learning the optimal leader strategy in Bayesian Stackelberg games with n followers under various settings. The (()) notation omits logarithmic factors.
Type Feedback
Action Feedback
Independent types
General types
Upp. Bound
Ö /min nKYT)
Ö(ymin(L, (L, Km]T) (mmin(V'"''>aa KTNTT
Low. Bound
R( /mint,, nKYT)
O(ymin(L nKJT)
O(ymin(L,nK)
Our work contributes to the growing literature on the computational and learning aspects of Stackelberg games (Conitzer& & Sandholm] 2006 Conitzer & Korzhyk [001]] Castiglioni
Related Works:
2020 Zhu et al. 2023). In particular, Letchford et al. Peng et al. (2019); Bacchiocchi et al.
al. (024) study online learning in non-Bayesian Stackelberg games, while Bollini et al. (2026)
consider Bayesian Stackelberg games, both with single follower. They assume that the follower myopically best responds in each round, which we also assume. However, their goal is to learn the
follower's s unknown utility function, whereas we aim to learn the unknown type distribution of the followers with known utility functions.
Balcan al. 2015 2025) design online learning algorithms with poly regrets for Bayesian Stackelberg games with single follower with unknown type distribution, while we consider mul- tiple followers. Bernasconi et al. 2023) obtain ((K /T) regret for multi-receiver Bayesian persuasion problem (which is similar ar to multi- follower Bayesian Stackelberg game) by a reduction to setting would lead to poly( K*) VT regret, which is exponential in the number of followers n (see details in Section 5) and undesirable when followers are many. Using a different approach, we design an algorithm with regret, a better result when the number of leader's ss actions L is small compared to the number of followers n. The exponential dependency on is unavoidable from a computational perspective, as [soniizzer & Sandholm (2006) show that BSGs are NP-Hard to solve with respect to L. Our algorithm combines the Upper Confidence Bound (UCB) principle and partition of the leader's strategy space into best-response regions, which is novel approach to our knowledge.
adversarial linear bandit problem. Adopting Bernasconi et al. 20233 's technique
Online Bayesian Stackelberg game can be seen as a piecewise linear stochastic bandit problem. While linear stochastic bandit problems have been well studied (Auer et al. 2002 Dani et al. 2008 Abbasi-yadde yadkori et al.] 201T), piecewise linearity brings additional challenges. Bacchiocchi et al. (2025) study single- dingee-diessionall piecewise linear stochastic bandit problem with unknown pieces; in contrast, we have known pieces but a multi-dimennional space, so the techniques and results of that work and ours are not directly comparable.
2

---

Published as a conference paper at ICLR 2026
2 MODEL
Multi-Follower Bayesian Stackelberg Game: We consider the interactions between a single leader and n 2 followers. The leader has L 2 2 actions, denoted by C [L] [I...., L}. and chooses a mixed strategy x E A(C) over them, where A(C) is the space of probability distributions over the action set. We use x(f) to denote the probability of the leader playing action E c Each follower has a finite action set A = [A]. We represent the joint action of the followers as = (a1,,.., ). Each follower i also has a private type 0; E θ [K], with the vector of follower types denoted by 0 = (0...... drawn from distribution (i.e., A ~ D), with D; denoting the marginal distribution of 0,. The properties of this joint distribution play key role in our results. We will consider two scenarios:
......... On) E @". We consider Bayesian setting where this type vector is
Independent type distributions: The followers' types are independent: D = D1 x ... x Dn-
General type distributions: The followers' types can be arbitrarily correlated.
the leader selects action E and the followers select joint action a E AAA", the leader receives utility u(E, a) E [0, 1] and each follower i receives utility v; (2,C, ai, 0;) E [0, 1J. Observe that each follower's utility depends only on their own action and type, alongside the leader's action; it does not depend the actions of other followers For leader's ' mixed strategy actions a, the leader's expected utility is denoted by u(x, a) Rezz [u(e, a)] [ (l))u(f, a). Likewise, the ith follower's ' expected utility under æ (z a,, 0.) = Et (e, a, 0)]. We assume that the leader knows each follower's utility function but not their private types.
A(C) and followers'
An instance of a multi-follower Bayesian Stackelberg game is defined by the tuple (n, L. A, K, u, v, D). In this game, the leader first commits to mixed strategy without knowledge of the followers' types. The follower types are then jointly realized from D, and each follower selects best-responding action based the leader's strategy. It is without loss of generality to consider followers choosing pure action since follower utilities are independent of one another.
Definition 2.1 (Followers' Best Response). For a mixed strategy x of the leader, the best response of a follower with realized type 0; is given by (0, x) arg maX.EA U2(2, a, 0,) The vector of (f.,((.).))) x)).
best responses is denoted by br (0,,0 x:) = (br, (01,
Let Up(x) FEoDDlul [xx br(0, x))] denote the leader's expected utility when the leader commits to mixed strategy the followers have their types drawn from DD and best respond.
Definition 2.2 (Leader's Optimal Strategy). For a joint follower type distribution D, an optimal strategy for the leader, also known as a Stackelberg Equilibrium, is given by:
x² arg arg (x) arg max Eg [u(x, br br(0,2))) WEM(C)
#EA(C)
Online Learning Model: When the leader knows the distribution D, they can compute the optimal strategy by solving the optimization problem specified in Definition 2.2 Indeed, this is the premise Conitzer & Sandholm (2006). Our work examines an online learning model where the leader does not know the type distribution D a priori; instead, the leader must learn the optimal strategy through feedback from repeated interactions with followers over T rounds.
We examine feedback models. In the type feedback setting, the leader observes the types O' of the followers after each round I, whereas in the action feedback setting, the leader only observes the actions a' of the followers. Note that type feedback strietly more informative than action feedback since the follower's 's actions can be inferred from their types by computing their best response (Definition 2.1p. We summarize the interactions at given round as follows:
1. The leader chooses a strategy x' A(C).
2. Follower types for this round are realized: 0 D.
1 'All of our results can be generalized to the setting where the leader's strategy space is an arbitrary compact convex set X' C Rd and the leader and followers' utility functions u(x, a), (2, a,, 0.) are linear (or affine)
functions of x X. We focus the probability simplex X' a(C) simplify presentation.
2This no externality assumption is common modeling a large population of agents (Dughmi & Xu 2017
Xu
2020 Castiglioni et al. 2020). We discuss this assumption more in Section 6 In of ties, we that followers break ties in favor of the leader.
3

---

Published as a conference paper at ICLR 2026
3. Followers take their best-responding actions a' br(0. x²) and the leader gets utility u(x', a').
4. Under type feedback, the leader observes the type profile 0'. Under action feedback, the leader observes only the followers' actions a'.
The leader deploys a learning algorithm (based on past feedback) to select strategy x' for every round t. We study learning algorithms that minimize the cumulative regret with respect to the optimal equilibrium strategy (Definition] 2.2). Formally defined below, minimizing this objective requires a careful balance between exploring the strategy space while not taking too many sub-optimal strategies.
Definition 2.3.
The regret of learning algorithm that selects strategy x² round E [T] is:
RTg(T)= - =
1=1 EgEND u(x", br(0", ,²")) u(æ', br(6", x'))| -
rr= (UD(z")-UD(()
Note that Reg(T) is random variable, because the selection of xf depends on the past type realizations 0-, 0t-1, We aim to minimize the expected regret [[[ee
Lastly, our model assumes followers behave myopically, selecting their best actions based only on the leader's current strategy, without considering future rounds. This is consistent with the literature on learning in Stackelberg games (see related works) and well-motivated in settings like online platforms or security games where followers maximize their immediate utility.
3 BEST RESPONSE REGIONS: A GEOMETRIC PERSPECTIVE
Since the followers' best-responding actions sensitive the leader's strategy x, the leader's expected utility function (z( is discontinuous in œ. This presents key challenge to both learning and optimizing over the leader's strategy space. To overcome this challenge, we first show that the leader's s strategy space (CC) can be partitioned into a polynomial number of non-empty best-response regions (followers have the same best-response actions within each region). While the notion of best-response regions has been proposed by prior works (Balcan et al. 2015 Peng et al., 2019 Bacchiocchi et al., 2024) Yang & Zhang 2024), those works consider single- multiple followers, we will argue that the number of such regions does not increase exponentially in the number of followers n (Lemma 3.2 a key property to be used in later sections. At a high level, the best-response region approach allows to reason about the leader strategy space in discrete sense. This is not only instructive for regret analysis (such as for Theorem 4.1) I but also facilitates leveraging algorithms like UCB (Algorithm B), which are defined for discrete settings.
cases. With
3.1 SINGLE FOLLOWER
To build intuition, first consider the leader playing against a single follower (n 1). The follower has a utility function v(E, a, 0) and a type E θ = [K] drawn from distribution D. Next, let θ A be a mapping from follower type action i.e. w()) specifies an action for type 0. For such a mapping w. let R(w) S. A(C) be the set of leader strategies under which the follower's 's best response action br(0, x²) equal w()) for every type E O. Formally:
R(w)= = x E A(C) br(0,x) = w0). 40 {
= 2 E A(E) w()), A) 2 v(z, 0), (
where we recall that for any action a, v(2, a, 0) = EeEc x())v(L, 0). The set R(w) is defined as the best-response region for mapping w. This region can also equivalently be defined as the intersection of several halfspaces (see Figure Appendix for visual). In particular, let
da = [v(1, v(1,
u(L, 0) v(L, a', 0)]² E R
denote the "advantage" of follower type 0 taking action over a' at each of the L possible leader actions. Then the halfspace H ad) = {x E A(L) (x, de,a.rr) 2 0} contains all the leader strategies under which the follower with type prefers action a over a'. Thus, the best-response region is R(w) Nece.aeA H (d) the intersection of (0] |A| K A halfspaces.
4

---

Published as a conference paper at ICLR 2026
3.2 MULTIPLE FOLLOWERS
We generalize the intuitions from the single-follower case to the multi-follower case. Let W (wi,..., Wn) denote tuple of n mappings, where each wi : θ + A is the best-response mapping for follower i. So. W is mapping from joint type space e" to joint action space AA, where (()) = (01)....... Wn (B.)) E A denotes the joint action of all followers under joint type 0 (01...., fn). Alternatively, one can think of W as matrix, W (wxx) E A where each entry Wise E AA records the best-response action for follower if he has type 0, We generalize the notion of best-response region R(w) from the singe-follower case to the multi-follower case:
Definition 3.1 (Best-Response Region). For matrix W E AnxK, the best-response region for W the set of leader strategies under which the followers' best responses are given by W:
R(W) = f br(0, =)))), VO
As in the single-follower case, R(W) can be expressed as the intersection of multiple halfspaces: R(W) (eem),,0.00...e (0.)).)
We make an important observation: the leader's expected utility function (D(2)) is linear in within each non-emply best-response region. By definition, for all 0 E @ and I E R(W), we have br(0, .² = (0). So,
UD(z) = "o(t)=Eoso.
br(O,))) = -E D(0) Σ ((())(((W(()) Eocon (( REC
where zw:e is the I-dimensional vector 2w.0 = (u(1, (()),, vl (0))). So, we conclude that the leader's expected utility is linear within each region R(W)):
Lemma 3.1. For each W, the leader's expected utility function Up(z) is linear in R(W).
Although UD(x) is linear within each best-response region, it could be non-linear and even discontin- uous across different best-response regions.
3.3 ENUMERATING BEST- RESPONE REGIONS AND COMPUTING THE OFFLINE OPTIMAL
Let = (W A R(W)= # 0} denote the set of mappings W for which the corresponding best-response region R(W) is non-empty. Although the total number of W E A is An* the number of non-empty best-response regions is significantly smaller, especially when L (number of actions of the leader) is treated as a constant. The exact characterization is given below. The proof (in Appendix A) uses a result in computational geometry regarding the number of nonempty regions obtained by dividing R. using O(nKA²) hyperplanes.
Lemma 3.2. The number of non-empty best-response regions, [W], is On A24).
For any algorithm to leverage these best response regions, it is imperative that these regions can be enumerated efficiently. The following lemma shows this is always possible. Intuitively, we construct a graph where the nodes represent non-empty best-response regions and an edge exists between W. W" W if and only if W and W" differ in exactly one entry. Traversing an edge, therefore, corresponds to moving to an adjacent best-response region by crossing single hyperplane boundary. We show that this graph is always connected and can thus be efficiently traversed using breadth-fire search. The exact algorithm and proof of Lemma 3.3 are in Appendix A
Lemma 3.3. The set of non-empty best-response regions (R(W): W E W) can be enumerated in poly(nk, KL A L. time.
We now show that the optimal strategy within each region can be efficiently computed. Recall from Definition 2.2 that, when given the followers' type distribution D, computing the leader's optimal strategy requires solving max, Eg~D [u(x, br(6, 2)]] Since the leader's 's utility linear within region R(W), the optimal solution within R(W) can be computed by the following linear program:
max RER(W)
E D(0)u(z, br(0)) max xf R(W) E D(0)u(Z, (0))
(I)
5

---

Published as a conference paper at ICLR 2026
where R(W) is given by the following set of linear constraints:
EiEc =(0) (()(, (8.),, 0.) v,ll,dd 0, vi [n], v0, + Va E A, xx(() 2 O, v4 E L, and Eeer =()=
(2)
While there are OnnK A) constraints, each involving sum over elements, the objective involves summing over K" possible type profiles. While this is exponential in n, any input to the complete information instance must provide the joint type distribution E [o, 1]K* as input. Thus, the time to compute the optimal solution within each region is polynomial in the input size.
The above results imply that, given distribution D, the optimal leader strategy in BSGs can be computed efficiently when the number L of leader's actions is small. This is because the optimal strategy within each best-response region R(W) can be computed efficiently by the linear program (I). the overall optimal strategy is the maximum over all non-empty best-response regions, and there are at most On"" A such regions by Lemma 3.2 We thus showed above that BSGs polynomial time solvable for constant L. In comparison, Theorem 7 of of & Sandholm (2006) proves that the optimal strategy is NP-hard to compute with an asymptotically increasing I..
TYPE FEEDBACK
4.1 LEARNING ALGORITHMS AND UPPER BOUNDS
General Type Distributions: We now address the core problem of learning the optimal leader strategy from online feedback. This section considers the type-feedhack setting, where the leader observes each follower's realized type 0' = (0%.... ...., 0²)) at the end of round t. We start with general distributions that is, the followers' types can be arbitrarily correlated. Observing types after each round allows directly estimate the unknown distribution DD and compute an optimal strategy accordingly. This is formalized in Algorithm
ALGORITHM 1: Type-Feedback Algorithm General Type Distributions
At round t = L. pick an arbitrary strategy x² E ACC).
for round 2 2 do
1-1 u(x, br(0*,z)) x)) - the empirically optimal strategy. Choose æf E arg max Σ'=l
Observe the followers' types 0¹ ~ D.
At first glance, one might think that this algorithm might suffer a large regret because the distribution D. which has support size [0"| K"" is difficult to estimate. Indeed, the estimation error for such distribution using t samples is at least (VV
K" even if D is product distribution (namely, the types x.
are independent) Lin 2022). This suggests that the empirically optimal strategy x² might be worse than the true optimal strategy x" by at least S2 rounds in total. As will show in Theorem a regret upper bound. The proof (in Appendix B upper bounds the single-round regret by the total variation (TV) distance between the empirical distribution D' and the true distribution D.
K"
which would cause an Q2( / /** regret in T analysis of Algorithm achieves exactly this as
While this suggests that O(vK"T) regret might be tight, this interestingly not true when n is large! That is, the intuitive lower bound that arises from the estimation error for distribution D not correct. Although the empirical type distribution can differ significantly from the true type distribution, the empirical utility of any strategy E A(C) is actually concentrated around the true expected utility z with high probability. We formalize this below:
Lemma 4.1. Given samples 0¹ o',..., 0t from distribution D, let - u(x, br ,x)) be the empirical expected utility of a strategy x E ALL) computed on the samples. Recall that Uz(z) Eg-Dlv (/ux, br(0, x)) denotes the true expected utility of x. With probability at least A))
we have: for all x E ALC), (D((x) ('(()) < o0(v
/ Llogt

---

Published as a conference paper at ICLR 2026
Proof sketch. By Lemma 3.2 the leader's strategy space A(C) can be divided into [W] O(n ) best-response regions, and the leader's utility function (a) is linear inside each region (Lemma B.T) Because the iseudo-dimension of linear functions in an L-dimensional space at most L, we have with probability at least 8', the empirical utility (xxx) on t samples
approximates the true expected utility UD(z) with accuracy o( L strategy x inside a best-response region. Taking union bound over all On K A2L) best-response regions, i.e. letting 8' 6/O(n"K* K )²".). proves the lemma. See details in Appendix B.1
/log(1/8)) for every
Note that the above concentration result holds for all strategies of for a single fixed strategy (which easily follows from Hoeffding's ' inequality). This result means that the simple Algorithm ! can achieve a regret that is of the order vT, logarithmic in n, with an additional VL. factor. This is better for large n and small L. This new regret bound, along with the earlier one (VVK"T), is formalized in Theorem 4.1 below, with the proof given in Appendix B.2 Theorem 4.1. The type-feedback Algorithm for general type distributions achieves expected regret O min { ( -log(K AT), VK*T)) and can be implemented in
A(C) simultaneously, instead
L.T) time.
Theorem 4.1 also comments on the runtime of Algorithm [ which hinges the computability of x. E max E u(æ, br(0", ,4)). Using the techniques developed in Section 3 this maximization can be solved by taking the maximum over the optimal strategies from each non-empty best-response region W E W, computed using the empirical type distribution. Using Lemmas 3.2 and 3.3 and the fact that the optimal strategy within non-empty R(W) can be solved by the following linear program, we obtain runtime that polynomial when I. is constant
Σ ((0)) subject to the constraints in R(W)
max WEW
max
Independent Type Distributions: Algorithm I and the corresponding regret bound in Theorem 4.1 hold without any assumptions on the joint type distribution D. In many settings, however, the followers' types may be independent of one another. Intuitively, one expects learning to be easier in such settings since it suffices to learn the marginals opposed to the richer joint distribution. This is we build the empirical distribution DJ for each marginal from samples
indeed correct: in Algorithm 2
o!.....e! 0 for follower i and then take the product D'
I[== D to estimate D II D..
ALGORITHM 2: Type-Feedback Algorithm Independent Type Distributions
At t L, pick an arbitrary strategy x² E A(C). for round > do
Choose x' E arg (C))) E 0 [u(2, [u(z, br(0,z)) Observe realized follower type (0i,....) 0%) for i E [n], h
E θ do
L (k) E. 1 10 k]
(0) = (( v0 e e
This algorithm achieves much improved regret, O(vnKT) formalized in Theorem empirically verified in Appendix D. The proof (in Appendix B.3
4.2 and
is similar the O(VK" regret
analysis of Theorem 4.1 which upper bounds the single-round regret by the TV distance between D' and D. But for independent distributions, we can relate the TV distance with the sum of Hellinger
distances between the marginals Dj and D;, which is bounded by O(1 aK instead of O K"
so the total regret is bounded by O(vnKT) The computational complexity, though, increases to as the empirical product distribution D' = -II DJ has support size K
(nly((nA))'*
Also note that Algorithm I does not need as input the entire utility function of the leader u(;;-), which has an exponential size T. A". The algorithm only needs the utility function for the sampled types.
7

---

Published as a conference paper at ICLR 2026
Theorem 4.2. The fype-feedback Algorithm for independent type distributions achieves expected regret O (VnKT) and can be implemented in poly A) LT L") time.
Corollary 4.1. Taking the minimum of Theorems 4. and 4.2
we obtain a rype-feedback algorithm
with expected regret O( min (VTT- -lo((n AT), V. VnKT) for independent type distributions.
4.2 LOWER BOUND
We then provide a lower bound result: no algorithm for online Bayesian Stackelberg game has better regret than [ / LL HT) When the number of followers n is large, this lower bound matches the previous upper bounds Ö(VLT). To knowledge, this work is the first to provide lower bound for the multi-follower problem and give an almost tight characterization of the factor before the classical V term. Interestingly, this OVTT.) factor does not grow with n. up to log factor.
Theorem 4.3. The expected regret of any type- opee-feedback algorithu is at least D2 /min L, nK nKYT). This holds even if the followers' lypes are independent and the leader's 's utility does not depend E.
The proof (given in Appendix B.5 involves two non-trivial reductions. First, we reduce the distribution learning problem to single-follower Bayesian Stackelberg game, obtaining an Myy m//mminfff L, K)TT lower bound. Then, reduce the single-follower game with nk types to a game with n followers each with K types. One might wish to reduce a single- follower game with K" types to an n-follower game to prove lower bound of SD( DD/miin(4 L, {") for general type distributions, but that cannot done easily due to no externality between the followers.
5 ACTION FEEDBACK
We now discuss the setting where the leader observes the followers' actions after each round. This setting is more practical yet challenging than the type-feedbace setting. We present two learning algorithms. The first algorithm achieves O(K" /T' log I') regret, using a previous technique from Bernasconi al. (2023). The second algorithm involves a novel combination of the Upper Confidence Bound principle and the concentration analysis of best-response regions from Lemma 4.1 achieving O(VnkK A22 LT Tog regret. The latter is better when the number of followers is large and the number of leader actions L is small. We empirically simulate both approaches in Appendix D
Linear-bandit based approach with VT""VTiO log T) regret: Bernasconi et al. 2023 developed
a technique to reduce the online learning problem of solving linear program with unknown objective to linear bandit instance. A spiritually similar approach can be applied here. While the optimization problem for our Bayesian Stackelberg games (Definition 2.2 is not a linear program, we show that under different formulation, this can actually be solved by single linear program (we explain the details in the proof of Theoren[.I]). We can thus leverage the techniques of Bernasconi et al. (2023) to reduce this linear bandit problem. Since [Bernasconi et al. (2023) considers adversarial online learning environment (ours is stochastic), directly applying their technique will lead to a sub-optimal OKK 5m VT) regret bound. Instead, we apply the OFUL algorithm for stochastic linear bandit (Abbasi-yadkee et al. 1) to obtain better regret bound of O(K"VT) Instead, we apply the OFUL algorithm for stochastic linear bandit (Abbasi-yadkori et al. 2011) to obtain a better regret bound of Ō(K" /T). See details in Appendix C.I
Theorem 5.1. There exists action-feedback algorithm for online Bayesian Stackelberg game with O(K" log T) regret.
Algorithm 3 with OL T.I.Tloog.. log T regret. We design a better algorithm for large n and small not using Bernasconi al. (2023) technique but using the "concentration over best-response regions" idea we developed in the previous sections. Recall from Section that the leader's 's strategy space can be partitioned into best-response regions: A(C = Uwew R(W). When the leader plays strategy in region R(W), the followers' best-response function satisfies br(0, x) W(0), so
8

---

Published as a conference paper at ICLR 2026
the leader's expected utility is D(0)u(z, ((0))(,,((0))-
Ulx, R(W)) = Σ
E u(x,a) a)
Σ D(0)= = Σ u(x, a)P(a R(W))
BEE
aEA"
@IW(0)=a
aελ"
where P(a R(W))= - D(0) denotes the probability that the followers jointly take action E AA when the leader plays E R(W). Since the distribution P(- R(W)) E A(A") does not depend on x as long as x E R(W), playing N strategies x! ,",...,.' x. within R(W) yields N observations a², ,..., a'....,a* aN ~ P(( R(W)). Using these samples, we can estimate the utility of any other strategy I E R(W) within the same region. We define the empirical utility estimate on N samples of joint actions as ÜN (z, R(W)) = 인 E==1"h u(xr, a²).
Lemma 5.1. Suppose T 2 [W]. With probability at least 1 72, we have: AW E W. AA e (1...., T) Vo E R(W), (x, R(W)) (x R(W)) ((g+1))og(37)
The proof of this lemma similar to the proof of Lemma 4.1 and given in Appendix C.2
For each region W E W, let N (W(W) = Σ [x=* e R(W) the number of times when strategies in region R(W) were played in the first - rounds. Given the result in Lemma 5.1 we define an Upper Confidence Bound (UCB) on the expected utility the optimal strategy in region R(W):
UCB
(R,))) +
1(L+1) log(33)
max #E #EW(W)
NOW))
We design the following algorithm: at each round t, select the region W E W with the highest UCB' (W), play the empirically optimal strategy in that region, and increment N*(W) by 1. Full description of the algorithm is given in Algorithm
ALGORITHM 3: Upper Confidence Bound (UCB) for Best-Response Regions Let W {W RRW) 0}.
for W E W do Choose any strategy x E R(W) and observe joint action.
for round t >> [W] do
for each W W do
Let (W) = 1 = W] be the number of times region R(W) was chosen.
Let P- R(W)) be the empirical distribution of joint actions in the rounds where region
R(W) was chosen: Paa(a R(W)) N'W E 1 [W W] 1 [a a).
Compute the empirically optimal strategy in region R(W):
kRw) = arg max E Ba-D(( [u(ar [u( a)], =ER(W)
which has empirical utility (R(W)) = E (R
lu(
Let UC) á (R( + / (((L+)))o
N'WW]
Let W E arg maxwew UCB'(W).
Play strategy xf (hr, and observe joint action a' (af (af o.))
Theorem 5.2. Algorithm has expected regret O (V KL To.
While the full proof is in Appendix C
sketch the intuition. In the classical multi-armed bandit problem, the UCB algorithm has expected regret (WmTTT To where m is the number of arms. In our setting, each best-response region corresponds an arm, and the confidence bound for each
region is O(1 L log T ). The number of arms/regions is |W|
KL by Lemma 3.2
(W))
So, the regret of Algorithm is at most O O(V(WI L- Tlog T = O n' L T log T).
Corollary 5.1. By taking the better algorithm in Theorems 5.7 and 5.2 we obtain an action-feedback
algorithm with O min K", VnLKt A KLLKL, VT) regret.

---

Published as a conference paper at ICLR 2026
Dependencies various parameters: Since action- feeion- is more limited than type-feedback, the lower bound in Theorem 4.3 immediately carries over and shows that the ((VT) regret bounds here are tight in T. There are several subtleties in achieving tighter bounds on the remaining parameters. Conitzer & Sandholm (006)) show that, even with known distributions, BSG are NP- Hard to solve with respect to L; so an exponential computational dependence on L is unavoidable, even if the regret could be made independent of L as shown in our O(K" / T)) result. Whether an online learning algorithm with poly(n, (n, K, L)vT regret exists is an open question, but such an algorithm will suffer an exponential runtime L unless P = NP.
DISCUSSION
This work designed online learning algorithms for Bayesian Stackelberg games with multiple follow- ers with unknown type distributions. Although the joint type space of n followers has an exponentially large size K", we achieved significantly smaller regrets: Ō( v /mmn(nK, L}T) when the followers' types are independent and observable, Ö(v mint K", LYT) when followers' types are correlated and observable, and (min K", Vn'K'. KL A2L LVV) when only the followers' actions are observed. These results exploit various geometric properties of the leader's strategy space. The type-feedback bounds are tight in all parameters and the action-feedback bounds are tight in T. The exponential
dependency on L unavoidable computationally (Conitzer & Sandholm 2006 Further closing the gaps between upper and lower regret bounds is an open question and will likely involve tradeoff between different parameters and tradeoff between computation and regret.
6.1 CONNECTIONS TO THE ADVERSARIAL SETTING
Our work considers stochastic follower types. Alternatively, one can consider setting where followers' types are adversarially generated. We conjecture that the main technique behind our results, "concentration over best response regions", can be generalized to adversarial settings. Importantly, the leader's 's optimization problem within each best-response region is linear. With stochastic follower types, the linear optimization problem within each best-response region can be solved by empirical optimization - this algorithm needs to be changed in the adversarial setting. In more detail:
For the fepebbee case, (e.g.. Multiplicative Weights Update) to pick a best-response region at each round. Within each best-response region, the problem becomes an adversarial online linear optimization problem with full feeback, to which we can apply algorithms such as FTRL to choose leader strategies.
adversarial full- feeeeebbback multi-armes bandit algorithm
For action-feedback, we can run an adversarial partial-feedback MAB algorithm (e.g., EXP3) to pick a best-response region at each round. Within each region, use an adversarial fertial-feedback online linear optimization algorithm to choose leader strategies.
Intuitively, best-response regions allow us (1) to tame the continuous leader action space and (2) to reduce the problem classical adversarial problems. Formally verifying this approach is left open.
6.2 INTER-FOLLOWER EXTERNALITY
Our work assumed no externality between the followers. While the learning algorithms for multiple followers without externality may not differ significantly from that of single follower, one might expect the regret bound to grow at the exponential rate of O(v TT).. However, we show that the regret bounds can be significantly lower when L is smaller than n (Theorems 4.1 5.2).
The presence of inter-follower externality leads to a leader- sarratey-induuee simultaneous game among the followers. Putting aside the computational difficulties of inter-follower Nash Equilibrium (or assuming oracle access to it), some of our results in the type-feedback setting generalize. In particular, our O ((K) result for general type distributions and O VnKT)) result for independent type distributions also apply to the setting with inter-follower externality. Our other results, which are built on best-response region characterization and depend on the independence of followers' utility functions, do not generalize to the case with externality. The introduction of inter-follont fftlo-follower externality significantly complicates the design and analysis of learning algorithms, because the action feedback now comes from equilibrium responses, instead of individual best responses leader strategy.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Yasin Abbasi-yadkort Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In J. Shawe-Taylor R. Zemel, Bartlett, Pereira, and K.Q. Wein- berger (eds.). Advances in Neural Information Processing Systems, volume 24. Curran Asso- ciates, Inc., 2011. URL o0l.77/haaaabaafff55577788555212
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Ban- dit Problem. Machine Learning, 47(2/3):235-25555 2002. ISSN 08856125, doi: 10.1023/A:
1013689704352. (tLLatt::/// /itk.iinn...../ wtt.aa/sp..ngg....o......222222. /ttp:///0000002/3111156667700000
Francesco Bacchiocchi, Matteo Bollini, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatt.. The Sample Complexity of Stackelberg Games, 2024. URL httpsss//aaaavv.ogg///a/
06977
Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond. In Proceedings of the 26th ACM Conference on Economics and Computation, pp. 1020-1020, Stanford University Stanford CA USA, July 2025. ACM.
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Commitment Without Regrets: Online Learning in Stackelberg Security Games. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp. 61-78, Portland Oregon USA, June 2015. ACM.
URL https: // acm. www.mmoog///i/o/e//eoooo 1tt.//...115//27620
2764476
Maria-Florina Balcan, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Keegan Harris, and Zhiwei Steven Wu. Nearly-optimal bandit learning in stackelberg games with side information, 2025. HRLbttpp httpaaxxivvv...... abs/ /2 50002 00204
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Pro- ceedings of Machine Learning Research, pp. 2164 2183. PMLR, July 2023. URL https //proceedings.. mlr. press www.//eeraaccoon22...
html
Matteo Bollini, Francesco Bacchiocchi, Samuel Coutts, Matteo Castiglioni, and Alberto March- esi. Learning in bayesian stackelberg games with unknown follower's types. arXiv preprint arXiv:2602.0077,, 2026.
Clément L. Canonne. A short note learning discrete distributions, 2020. URL htLthttss///ai oxq/abs/2002.11 20457
Xiaogang Cao, Jing Yuan, Hui Wen, and Cuiwei Zhang. The pricing strategies under the online platform selling mode with information sharing. Kybernetes, 181-)118111277, 2024.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online bayesian per- suasion. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 16188-16198. Curran Asso- ciates, Inc., 2020. URL UtL:ttppp:///rrceeccing. neurips...pppppppp cc ccpppper.ppppppe.eepppeeeeeee..e fi files/paper/ o20.0eeeeepaaaaacaaaaaarorrrrrr0
Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing- STOC '14, pp. 243-252, New York, New York, 2014. ACM Press. ISBN 978- 1778---4503--71-1111 doi: 1991144999999929191111 URL http://d. acm. org/ wwt.gciiiieo..oooooo..oooooooooe witttitiioooo wtt.tatt.....cooooooo.1.1111111. 25011797767799917777
Vincent Conitzer and Dmytro Korzhyk. Commitment to Correlated Strategies. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1):632 637, August 2011. ISSN 2374-3468. 2 2159-5399. doi: 10.1609aaaii 2511 URL http::ttts///tttt aaai. sxg/indexx php/
AAAT / TeATTartiile///iee

---

Published as a conference paper at ICLR 2026
Vincent Conitzer and Tuomas Sandholm. Computing the Optimal Strategy to Commit to. In Proceed- ings of the 7th ACM conference on Electronic commerce, pp. 82 82-90, Ann Arbor Michigan USA, June 2006. ACM. /tttts/////al acm. org/
1445 317 1134771
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastie Linear Optimization under Bandit Feedback. In s/ Anmual Conference on Learning Theory, pp. 355-366, 2008. Issue: 101.
Ilias Diakonikolas and Vasilis Kontonis. Sample complexity lower bounds. Available at: http: htt.eeachhnn/aa11gggereeeeeeee Lecture notes for Advanced Learning Theory, [University of Wisconsin- pdf 2019.
7/www. illilliaiis www.iiiiaiaaaaaoooo www.aaaakkkkkalaa
Shaddin Dughmi and Haifeng Xu. Algorithmic persuasion with no externalities. In Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 351-368, 2017.
Paul Dütting, Michal Feldman, Inbal Talgam-Cohen, et al. Algorithmic contract theory: A survey. Foundations and Trends@ in Theoretical Computer Science, 16(3-4)2211411) 2024.
Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora's 's problem. In Conference on Learning Theory, pp.
PMLR, 2021.
Dan Halperin and Micha Sharir. Arrangements. In Handbook of discrete and computational geometry, pp. 723-762. Chapman and Hall/CRC, 2017.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp- 111-122, 2016.
Safwan Hossain, Evi Micha, Yiling Chen, and Ariel D. Procaccia. Strategic classification with exteralittess In The Thirteenth International Conference on Learning Representations, 2025. URL https:///pennrevie.. net forum 2idoouxkEtt
Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6): 2590-2615, 2011.
Jasper Lee and Qianfan Chen. Learning discrete distributions. Available at: https://cs bttps://cs.brown brown
paf 2020. Lecture notes for
Sublinear Algorithms for Big Data, [Brown Universityl.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Proceedings of the 2nd International Symposium on Algorith- mic Game Theory, SAGT '09, pp. 250-262, Berlin, Heidelberg, 2009. Springer- Verlag. ISBN 9783642046445. doi: 10. (0.10009998833-42-066666 3-642-04645-2222 URL https: /tt::///oiiitoo http:////oooogg/////// 1007/
978 3- 642 04645-2 23
Tao Lin. How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions, 2022. URL. /0tp
06422
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning series. MIT Press, Cambridge, MA, 2012. ISBN 978-0-262-01825--8
Binghui Peng. Weiran Shen, Pingzhong Tang, and Song Zuo. Learning Optimal Strategies to Commit To. Proceedings of the AAAI Conference on Artificial Intelligence, 43011)2149-2156, July 2019, URL httth::////oj aaai. wrgg/oogg...//eee pttp/AAAt//rrriiee//iisss
Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: Looking beyond decade of success. IJCAI, 2018.
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.
Haifeng Xu. On the tractability of public persuasion with no externalities. Proceedings of the Fourteenth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 2708-2727. SIAM, 2020.
12

---

Published as a conference paper at ICLR 2026
Kunhe Yang and Hanrui Zhang. Computational Aspects of Bayesian Persuasion under Approximate Best Response. In The Thirty- Anmual Conference on Neural Information Processing Systems, 2024. URL httttp:://ppnzeviiee
net/ 1eeee//orrmmmdd00110000000 9000k333
Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. Online learning in stackelberg games with an omniscient follower. In International Conference on Machine Learning, pp. 42304-42316 PMLR, 2023.
Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design, 2023, Utthttps: http///xxv....g//b///// 05732
13

---

Published as a conference paper at ICLR 2026
A APPENDIX FOR SECTION 3
41(0,1)
de(0, 1)
Type prefers oction
Figure single-follower best- response region with K 3 types and two follower actions and three leader actions -
Type prefers actien
R(w)1o)
3. The triangle represents the probability simplex ACC). The three hyper- planes defined by di (0, 1), d2(1,0) and (1,1, 0) partition the simplex into best-response regions. For ample, in region R( 1.,.,1.1). 1. the fol- lower best-responds with action 0 for type 1, and action 1 for types and 3.
[((mus))
R(ena..)
R(w.an)
R(wes.)
1)
R(wras)
R(wuaa)
A.1 PROOF OF LEMMA 3.2
Proof. We have n followers each with K type and A actions. Each follower has K ((2) S K A advantage vectors, where each advantage vector dg corresponds to a hyperplane R that separates the leader's mixed strategy space A(C) C R into two halfspaces. total, n followers have nK A hyperplanes. Those hyperplanes divide E into at most ((nk regions (see, e.g., Halperin & Sharir (2017) Each non-empty best response region is one of such regions, so the total number is O(n A.
On K'
A.2 PROOF OF LEMMA 3.3
ALGORITHM 4: Best- Region Enumeration
Let isFeasible xz i, i,0, a) VYo' E A, Exee (() vi(l, 0)) 2
Let ennibee (W) = {a A(C) |Vi [m],0 0 E isFeasible(z, W 0) = 1}
Choose random strategy Tinst E A(C)
for i [n). 0 θ do
for a E do if isFeasible(E:mee i, 0,0,0 0,a) then L Winseli, 0 =a
Let queue = [Wanat Wiiitl mark Wina as visited
while queue + 0 do
W queue.popl) for i [m], E + do
for a E A and a + W do
Let W" W
Let [ =a
findeeeasibleWW) + 0 and W not visited then
queuc.append((W)) mark W' as visited
Proof. We construct graph G = (V, where consists of the elements W, each representing a best-response region. An edge exists between two vertices W. W E W if and only if W and W"
14

---

Published as a conference paper at ICLR 2026
differ in exactly entry. Traversing edge corresponds to moving between adjacent best-response regions by crossing a hyperplane boundary.
We claim that this graph is connected. Since cach vertex W corresponds to best-response region defined by the inequalities in (2) and the leader's strategy space is the L-dimensional probability simplex, the union of non-empty best response regions forms partition of the strategy space. Because these regions are convex polytopes sharing boundaries, the adjacent structure defined by differing in one entry corresponds crossing a shared facet. Starting from any non-empty region, we can traverse to any other by crossing shared facets through adjacent regions, so the graph is connected.
Thus, enumerate all non-empty best-response regions, can perform graph search (e.g., breadth-first search or depth- firstfitttttte search) starting from any initial vertex W to traverse all vertices in (([)) steps, which ( by Lemma 3.2 Specifically, at each vertex W, we examine all its adjacent n.K A vertices. For each adjacent vertex W we determine whether R(W") is non-empty region by solving feasibility linear program defined by the constraints in ( which runs in poly(na (n, K, A, L) time. Then, the total running time is poly(n', K", A L). We present the algorithm formally in Algorithm
B APPENDIX FOR SECTION
The following definitions will be used the proofs for this section:
Definition B.1 (Total variation distance). For two discrete distributions D and DD over support θ the total variation is half the L1 distance between the two distributions:
8(D, D) = _ 1 D 111 D Σ BEB
(D(0) -(O))-
Definition B.2 (Hellinger distance). For two discrete distributions 'D and DD over support θ, the Hellinger distance is defined
1 H(D, - VD122=
1
Σ AEG
(D(0) (D(0)-D(0))²
/2
B. PROOF OF LEMMA
We rely on several key insights about the pseudo-dimension of a family of functions, defined below: Definition B.3 (Definition 10.2 in Mohri et al. (2022)). Let G be a family of functions from input space Z to real numbers I.
A set of inputs {21...., Zm C Z is shattered by & if there exists thresholds t, t,....,t tm E IR such that for any sign vector (o),..., E (-1,+13m there exists function g satisfying sign(g(<;) 44) σi for all i 11....
The size of the largest set of imputs that be shattered by G is called the pseudo-dimension of G, denoted by (g)
Given a family of functions with finite pseudo-dimensio and samples z!...., NN drawn from distribution on the input space Z, the empirical mean of any function in the family will, with high probability, close to the true mean. Formally:
Theorem B.1 (e.g., Theorem 10.6 Mohri et al. (0122). Let 9 be a family of functions from Z to [0, 1] with pseudo-dimension Pdim(g)= d. For any distribution F over Z, with probability at least 1 over the random draw of N samples zt ....., N from F, the following holds for all g E G.
2d log 3N
log 2N
E [(()]g()))
Σ 9(29)
Consider the family of linear functions over R g {9z :2 - (x, 2) E R is known that the pseudo-dimension of this family is T.:
15

---

Published as a conference paper at ICLR 2026
Lemma B.1 (e.g.. Theorem 10.4 in Mohri al. 2012)). The family of linear functions (92 (x,2) x E R² in R has pseudo-dimensiae dimension L.
Proof of Lemma 4.7
We now have the tools to prove Lemma 4.1 For any non-empty best-response region defined by W E W, let 0' ..... 0' ~ D be i iid samples. For each sample 0', we can directly compute
2 [11,, W(O')...., uLL, W(O1)).
leader's expected utility by using strategy is (z(z) Eg (2,, ew which is the expectation of the linear function Iu (zwwe)) = (z,, zw.e). Therefore, by Theorem B.I and Lemma B.I. we have
Fix any leader strategy R(W). By Lemma 3.1
Pr Vo R(W), [lo-olo(> Σ Ie (=( S
2L log 3t
log 1 8
2 1 8'.
6
By definition, UD(x) = (ow and Ü'(x) = Ei g(zw.or). So.
2L log
log J
Pr Vx E R(W). ( 01(0) $
2 1 21-8.
t
2t
Let 8 = IWI- By the union bound, with probability at least simultaneously for all W W and R(W):
5, the following bound holds
(T(2) - (
2L l3g(3t)
log
W
=o( T.oot
L log(nK l
+
2t
where used the fact = = On KL A2L) from Lemma 3.2
B.2 PROOF OF THEOREM
Analysis of O(VK*T) Regret: Consider a Bayesian Stackelberg game with n followers each
with K types, with joint type distribution D. Let U (a, D) Eg-Dlut [u(x, br(0, x))] be the expected utility of the leader playing mixed strategy when the type distribution is D. Let x²' = arg max)cA(c) (zx D) the optimal strategy for D. At each round t, Algorithm chooses
the optimal strategy xº = arg max)e Uæx D² for the empirical distribution D t-1 samples. The total expected regret equal
over / 1
E E(Re
Σ E Ul=' DD U(x', -(('")) (D)
single-round regret r(t)
We upper bound the single-round regret r(t) by the total variation distance (Definition B.1 between
D and D
Claim B.1. r(t) = U D) U((2 D) 48(D. D'
Proof.
r(t) = U(s", D) U(x', D)
= U(x", D) U(z" D' 1-1
DD ) -U(' D D²11) "
D' U(x', D)
<U(x", D) U(x" 1-1 )+)++UUb D D² U
(4)
16

---

Published as a conference paper at ICLR 2026
where (4) follows from U (a", D ) U(x", D D' E because x' maximizes U(x, U(I,D'=1 D' We
bound the first term in Equation as follows:
Uxx" D) Ux=", D
D u(2 ((((,(()r)(0) br(0,
(0) (D) br(6.z))
(0)
#Eo
AEO
Σ
((()) D )0)( u br(0,
Σ D(0)
D' 1-1 (0) u(z, br(O,z))
006
D' (0) 1 = 25(D, 25(D, D'
(
666
By symmetrical argument, the second term in Equation (4) is also bounded by 26(D, D'
Using Claim and taking expectation, we have
E(r(t)] & 4E|0(D, D ")) )].
According to Canonne (020), for distributions with support size K KT,,, D D' " 5 (
Thus, have E(r(()) < (v
k
Using the inequality Σt= JE S 22VT, obtain
T
T
K
B[Reg(T)] = Σ
B[r(0] s O
Σ
O(2VKTT) = O(VKTT)
Analysis of ((VLV Logg(onll AT) Regret: with probability at least - 8:
Consider round 2. By Lemma 4.1 we have that
- < o(1 Llogt
Llog(nKA A) + log(?)
Va E A(C).
Suppose this event happens. Then, the regret of the algorithm at round is bounded as follows:
rtt) EgnD [u(x", [unD[u(x", br(0,xx)) u(x', br(0,x')))
= Up(x") Up(x")
= UD(x") 1--11((")) (x²) + (x²) - (x-+ (x') Un((')
Llog(1 - s (x*) - ( + +2.0
L Llog(nKA + log( (1) t-1
+
t-1
< 0+02. 10+220(1
1-1 (
L Logg(t 1)
Llog(nKA) + log(
t-1
where the last inequality follows from (x=) (--)(x*) < 0 because the algorithm selects the strategy xf that maximizes the empirical utility (x)) Then:
Reg (7) E r(1)
(1 -1- -0-00(010
(11 Llogt
Llog(nKA) + log(5) 8T
Σ
(5)
t
1=1
0
TTLlogT + v (oolog(KAA) 1og(
+ ST
(6)
< <O(VTI T log(nk A)))
(Using inequality va Vb S (((a+b)
=0 ((loKK(A))))
17

---

Published as a conference paper at ICLR 2026
Equation 5 follows from the law of total expectation and the fact that the single-round regret is
bounded by 1. Equation (6) follows from the known inequality Σ V 2VT. We set d 7
Runtime Analysis: As for the computational complexity of this algorithm, note that Lemma 3.2 states that the number of non-empty best-response regions is On K ) As shown by Equation (3). we can compute the optimal strategy within each best-response region using linear program with L variables and at most poly(n", K" A L, T)) number of constraints. Further, evaluating each constraint and the objective function can also accomplished in this time. Since each linear program can be solved in poly(rt (n K_, A4, I. T) time, and we run On (2)) linear programs at each round, with at most I' rounds, Algorithm| runs poly((n A) LT) time.
A2L)
B.3 PROOF OF THEOREM 4.7
Proof. Let D I D, denote the distribution independent types. According Claim B.1 the single-round regret r(t) = Ux D) - U(x,, D) satisfies
(t) - O(((D,D'"))
where D
ITm D is the product of the empirically computed marginal type distributions.
We will use the following properties of Hellinger Distance (Definition B.2
Guo et al. 2021 For any two distributions D and D.
H² = 6(D, D) & (D.(D.
(7)
(uo et al.
2021 both D and D are product distributions, ie. D II D, and D
[ Di then:
H² S Σ H2 (D..
(8)
Canonnne 2020) For a distribution D with support size K, the empirical distribution De over I samples from D satisfies:
K
ED, D') <
(9)
21
We now upper bound the single-round regret r(t 1) in expectation:
Bir(t 1)] < (EE(
{O(E[H(D.D))
by
<0(v
E(H
because E[X 2 (E[
0
E
H2 HD, Dj)
by 8
t=1
T.K
00
by 9
2t
Using the incquality ΣT Ji < 2vT, we obtain
T
(1
nk
E[Reg(T)] = Σ Blr(t]
< Σ 0
(17)
& O(VnKT).
111
1=1
18

---

Published as a conference paper at ICLR 2026
B.4 mLy KYT) LOWER BOUND IN THE SINGLE-FOLLONE CASE
In this section, we prove a lower bound of S / min T,, KJT) on the expected regret of any algorithm in the case of a single- (n 1), formalized in Theorem B.2
Theorem B.2. For single-follower Bayesian Stackelberg games where the follower has K types and the leader has L actions, the expected regret of any rype-feedback online learning algorithm is at least 92( mL/min,L,KK1
At high level, the proof Theorem B.2 is reduction from the distribution learning problem. Without loss of generality, assume that min { K, L} = 2c is an even number. Further assume that K L 2 The single follower has K 2c types, with type space θ {+1, +2, ..., tc). Consider a class C of distributions over & defined as follows:
Definition B.4 (Class of Distributions C). A distribution (01)...,de) E {=1}.. For each ,,...,, C,
Do E is specified by a vector
(+(+ (1t)))), Do - - - oze). 2c
(10)
2c
for some > O. Note that Do(+j) > Do(-s) if and only oj = +1. The class C consists 2 2 distributions.
In the distribution learning problem, given i. samples 01 ..... 0 from unknown distribution D E C, the goal to construct an estimator 'D specified by vector ā E {+1]e such that the expected total variation distance (Definition B.1) satisfies [E[((D, D)] S (c). It is known that solving this problem requires at least Q (223) samples.
Theorem B.3 (e.g.. (Lee & Chen 2020 Diakonikolas & Kontonis 2019). ). When D is uniformly
sampled from the class C, any algorithm that constructs estimator D using samples from D has
expected error at least E(8 D)) 2 ift s )
$If K > 2c, can let the additional types to have prohability 0. If T. > 2c, can let the additional actions of the leader have very low utility.
19

---

Published as a conference paper at ICLR 2026
Reduction from distribution learning to single-follower Bayesian Stackelberg game
Distribution learning instance: An unknown distribution D E.
Bayesian Stackelberg game instance:
single follower with type space + +2......... + and an unknown type distribution D. The follower has binary action set A (Good, Bad). The leader has action set L = ++1.+2..... tc). The utility functions of the two players are:
Follower's utility function:
if +j. f +j, Good
if 0 +j.E -j, Bad
all, a,
if O -j = -j, Good
(11)
1 if -i =iE=+j, Bad
0 otherwise.
Leader's utility function: For any action E L.
ule, Good) =, u(e, Bad) =
(12)
Note that for any mixed strategy æ, u(x, Good) and u(x, Bad)
Reduction:
Given an online learning algorithm Alg for Bayesian Stackelberg game with type feedback, we use it to construct online learning algorithm for the distribution learning problem as follows: At each round = I,...,T,
Receive the leader's mixed strategy x' from Alg.
2. Construct an estimated distribution D=r Da(z') C. based on vector (xx)) defined follows:
+1, if 2 x'(-)
a,(x*) 1 -1, if < x-()- 3. Observe sample 0¹ D and feed 0e to Alg.
(13)
20

---

Published as a conference paper at ICLR 2026
Lemma B.2 (Follower's Best Response). Given the leader's mixed strategy E A(H). for each
j E {I...., c), the best-response function of a follower with type +j or -j is:
Good,
ifx(+ s(-j),
br(+j,x)
Bad,
ifx(+)) < <<(-))
br(-j, [oood
ifx(+]) < <<(-j), ifz(+)) 2 (-(-)).
Bad,
Proof. For a follower with type +j. their utility for choosing action Good is given by
v(r, Good, +ÿ) [ Good, +-)] Σ
x(()u(e, Good, +5) x(+)).
EEC
Similarly, their utility for choosing action Bad is: v(x, Bad, +() x(-j).
Thus, by definition, the follower with type +- best responds with Good if a(+)) 2 x(-)).
Likewise, for a follower with type -j.
(xx Good, -5) = x(-j),
vxr, Bad, -j) = x(+j).
Thus, a follower with type -j best responds with Bad if ax++)) 2 xx-j), Good otherwise.
We define Uxx D) as the expected utility of the leader when using mixed strategy x under the type
distribution D. By Lemma B.2 have
(x D) Σ D(0)
u br(0,
Σ
D(+)) a (r, ( br(-
/=1
Σ
oje
1 [x(+))
1 1- ((++))2(() x(-)))
acc [x(+]) < xx--)l).
(14)
2c
Definition B.5 (Disagreement Function). The disagreement function Disagree(1; D) is the number jf E (1....,c) c) where the indicators
(x(+)) 2 xx- and 1 (D(+j) 2 D--j) differ:
Disagree (2,
1
1
x(-5)) [ 2 D P--))
Σ
2x+))) 10 = 10, +1]]
j=1
Lemma B.3. U(D,D) Uz, D) Disagree(s, D). In particular, the optimal strategy for the leader is x² = D.
Proof.
Σ j=1
1+
(1(D(+)) 2 D(-1) - ((((+)) 2 x(-i)))
2c
- ojE
(1[D(+))< < D(-)) [[((+)) < <x(-))))
For each term in the summation where D(+)) > D and x(+j) 2 x(-j) agree, the term evaluates to O). When they disagree, there are possible cases:
21

---

Published as a conference paper at ICLR 2026
1. D(+)) 2 D(-)) but x(+)) < xx-5). Since D(+j) 2 D(-)) implies o, +1, the term simplifies to
1+e -
2c 2c
2. D(+)) < D(-5) but x(t)) 2 x (--)). Here, oj = 1, so the term simplifies to
- 1 1+6
2c
2c c
Thus, we conclude that
U(D,D)-U(e Uxx = c
Disagree(z, D).
Lemma B.4. Let D2 be the estimated distribution constructed from according to Equation 13 The total variation distance between D' and D is given by
8(Da, D) Disaareeez, D).
E
c
Proof. By definition.
DD.. = - Σ (
-(-i))
x and 'D agree at (+j) and (-j), the corresponding term in the total variation sum is 0. Conse- quently, only need to consider the case when a disagreement occurs.
1. x(+s) < <x(-j) while D(+)) 2 D(-j). In this case,
Dz(+5)= = 1-c
1
D(+j)= = 1+6
1 1-6
Dx(-i) =
D(-j)
2c
2c
2c
2c
Hence,
[D(())) D(+j)) (000))/((D(-))) |D.(t))-P((-)|((AAA------ -P(ii)
2e
c
2. x(+j) 2 xx-j) while D(+5) < DD--).. Similarly, we have
1+6 Da(-s) 1-r
1 1
1
D+(+5)= 2c
D(+j)
D(-1)=
2c
2c
2c
Again, we have
[Da(+)) - D(+i)) -(.()))
- D(-i) -((()) = + 2
Thus, it follows that
8(D,, D) - -Disagree(r;; D).
From Lemma B.3 and Lemma B.4
D(D,D)-U(z,
Disagroo(z, D) 8(D,, D).
(15)
Consider the regret of the online learning algorithm Alg for the Bayesian Stackelberg game, where the algorithm outputs of round By Equation 115) and Theorem B.3 the expected regret at round t < ((3) is at least
E(U(D,D) U(x', D) ElS(D.,, D)] 2 s(c)-
22

---

Published as a conference paper at ICLR 2026
Thus, the expected regret over T rounds is at least:
(DU(D,)) - U( z min {T. o (( } S2(c)
E E(Reg(()) = Σ
2 (VV2(T) o1 Olymin min K, LTT)
where we choose E
2c
T
mi nkY YT) LOWER BOUND FOR THE MULTI-FOLLOWER CASE: PROOF OF B.5
THEOREM 4.3
We now prove lower bound of S?( m/mm nK YT') on the expected regret of any online learning algorithms for Bayesian Stackelberg games with multiple followers. Without loss of generality, assume that n/K is even integer, and assume that the number of leader actions L 2 nK. We do reduction from the fingle-follower problem the multi-follower problem.
Single-Follower Bayesian Stackelberg Game instance: Consider the single-follower Bayesian Stackelberg game instance defined in Appendix [o.bendixB.B]00 [.4] but instead of single follower with K types, we change the instance that the single follower has n types, indexed by θ = {{ i E [n].j E [K]}. Suppose the single follower's type distribution D belongs to the class in Definition B.4 with support size 2c nK (instead of 2c K). Note that for such a D E C,
K D(i.))
Dii,))= =1 and Wi [n],
= -
=1
The follower's utility function is given by except that we now 0 (i.j) to represent type and & = (i.j) to represent a leader's action. The leader's action set is L = O, with utility function u given by [2)..
Multi-Follower Bayesian Stackelberg Game instance: We reduce the single-follower game to an n-follower game defined below. Consider a Bayesian Stackelberg game with n followers each with K + 1 types. The type distribution and the followers and leader's 's actions and utilities are defined below: (To distinguish the notations from the single-follwee game, we use tilde notations :)
Type distribution: The followers' types are independently distributed according distribution D IT D. where the probability that follower E [n] has type is:
if j = 0, if j = 1, 1,.., K.
D.0) =
TO0M D(1.j)
100
Followers' actions and utilities: Each follower has 3 actions À = (Good, Bad, ao). The utility of follower with type # 0 is equal the utility of the single follower with type (i. Utilities for type j 0 and action do are specially defined:
vle, (i,j))
if 0 * 0 and +
if 0; # 0 and do:
ae, -)
if 6; and ag-
if 0; = O and a + ag-
Note that the best-response action of a follower with type 0 is always ag, regardless of the leader's 's strategy.
Leader's actions and utilities: The leader has the same action set as the single-follower game: L θ (ii.j) : E [n], [K]]. For any leader action E C.
if 1 followers choose ag and one plays Good, a(e, a) { otherwise.
23

---

Published as a conference paper at ICLR 2026
Reduction from Single-Follower Bayesian Stackelberg Game to Multi-Follower Game
Given an online learning algorithm Alg for the n-follower problem, we construct an online learning algorithm for the single-follower problem as follows:
each round = l,....,
Obtain strategy xf E (L) from algorithm Alg. Output x!.
Receive a sample of the single follower's type 0 = (i',j))~2
For every follower E [n]] we construct their type 0 in the following way: Independently flip coin that lands on head with probability 1 - If it lands on head, set the follower type 0g O. If it lands on tail, we select the most recent sample of the form (i i,j") from the history {(i", {j"))==== and set the follower's type 0f to j". Each sample can only be used once. If there are insufficient samples, we halt the algorithm.
Provide the constructed types ........ (%.) to algorithm Alg.
In the above reduction process, if we always have sufficient samples in the third step at each round, then the distribution of samples (fi..... 0¹) provided to algorithm Alg is equal to the type distribution D - D. of the n-follower game. Thus, from algorithm Alg's perspective, it is solving the n--flllowrr game with unknown type distribution D. We then argue that we have sufficient samples with high probability. Let H be the number of available samples in the history that we can use to set follower i's type at round t, and let N be the number of samples that actually need. Define
(t) = Pr (vi E [n]. H 2 N which is the probability that we have sufficient samples round t. 12
Claim B.2. 8(t) I 2n exp ( (- 1000
Proof. Note that H: and Nj are Binomial random variables: Hy Bin(t, H), N₁ Bin(t, 100m) )- So, by union bound and Hoeffding's inequality:
8
1
Pr(Mi e [n], H NŞ) S nnP(( < NJ) S 2n exp
100m
21
Let (z) be the leader's ' expected utility in the n-follower game (on type distribution D) and (zx) be the leader's utility in the single-follower game (on type distribution D). We note that, given any strategy x E (CC) of the leader, the best-response action of follower with type 6; = * (in the n--olllower game) is equal to the best-response action of the single follower with type (i, namely, br, br;(i = br((i.)) x)) Thus,
(x) = Pr[exactly one follower has a non-O type]
Elleader's utility/ exactly follower has non-0 type] + 0
12
D(i,)) 1 br, (j. Good
100n
100
j=1
K
D(i,g) br (i..),), Good
100n
100
i=1
j=1
1
1
n-1
U(x)
100
100m
1
2
100
Uxr).
100
Define C
1
1-1
Let Let = Ü(*)) (x*) denote the per-round regret of the online
100
100m
learning algorithm Alg for the n-follower game. Let r(t) ((*)) U(x*) denote the per-round
24

---

Published as a conference paper at ICLR 2026
regret of the Linle-follower algorithm constructed by the above reduction. Consider the expected total regret the n-follower game:
E| E[Reg(T) (T)
E Elr(t)
t=1
(1-8())-BBF(C)
8(1) 1)
T
T
Σ (1 8(t)) C. C[r((]]]] - Σ 8(t)
1=1
T
T
T
2 C B[r(t)]
- -
8(t) CC
Σ
8(t)
1=1
t=1
C. E Reg(()
(C +1) Σ 8(t).
Now, we bound El= 8(t). Consider threshold such that for all t t, we have 8(t) s 722 To find T, we solve
(1/100n 1/n)² 7) 5 72
2n exp
Rearranging, we choose 7 such that
l2(
C+
where C. 100n
1). If S r, we bound 8(1) S For T, we use the bound 8(1) S 7-2
Now, summing over all t,
Σ 8(1) S + -T- -/2
ln
T-
s
0
ITT
7)
Oloog T).
Cr
T
Cr
Then.
(T)) 2 C. E.e(Reg(T)) (log 7).
The regret [[Reg(T)) for single-follower game where the follower has nK types and the leader has L = nk actions is at least Q (V)KT) by Theorem B.2 Thus, we obtain
[[R)g(T)) 2 C (((vk(V)))) O(log 7) = ((vnKT).
which is also 2i mi, FT) because = =nK.
C APPENDIX FOR SECTION 5
C.1 /To T) REGRET ALGORITHM AND THE PROOF OF THEOREM 5.1
We show that the online learning problem for Bayesian Stackelberg game with action feedback can be solved with O(K Tog regret, by using technique developed by Bernasconi et al. (023).
Bernasconi et al. (023) showed that the online learning problem for a linear program with unknown objective parameter can be reduced to a linear bandit problem. We first show that the Bayesian Stackelberg game (which not a linear program as defined in Definition 2.2p can be reformulated linear program. Then, use Bernasconi al. (2023)* reduction to reduce the linear program formulation of online Bayesian Stackelberg game to a linear bandit problem. A difference between work and Bernasccon et al./ (2023) is that, while they consider adversarial online learning setting, we consider a stochastic online learning setting. Directly applying Bernasconi et al. (2023) s result will lead to an Ö K 38 vT) regret bound. Instead, we apply the OFUL algorithm for stochastic linear bandit Abbasi-yadkori al. 2011) to obtain better regret bound of O(K" VT).
25

---

Published as a conference paper at ICLR 2026
Step 1: Reformulate Bayesian Stackelberg game linear program. First, reformulate the Bayesian Stackelberg game optimization problem maX (D(a) (Definition 2.2). which is a nonlinear program by definition, into a linear program. Let variable represent a joint distribution over best-response function W E A and the leader's actions L. Specifically,
(WW)))W.)....... RA*K xL
where
Σ
x(W, () = 1, and x(W,e) 2
WEAnK JEEL
Altematively, be viewed A x L-dimensional matrix, where W indexes the row and E indexes the columns. We maximize the following objective (which is linear in x):
max U(+) EE
(O)),
(16)
WEA"K LEC BE8"
subject to the Incentive Compatibility (IC) constraint, meaning that the followers' best-response actions are consistent with W: vW E Ank,, Vi E [n], v0, E O, Va, E A..
Σ Zo (1i(( w; (;,);,,0)) (=(W))(x((,,,(00000) - (l. 0.)) 20. REC
(17)
Lemma C.1. With known distribution D. the Bayesian Stackelberg game can be solved by the linear program [7 in the following sense: there exists a solution æ to (16
I7 with only one non-zero
row xe (W" :"), and this row x xW*,) E R2 is solution to maX (z).
Proof. First, we prove that the linear program (16) contains an optimal solution with only one non-zero row. Suppose optimal solution has two non- nonzzero rows W,, W2:
Σ
x (W1, p1 > O, Σ (W2, = P2 0. REL
EEL
Consider the conditional expected utility of these two rows. Because, when conditioned on row i, the conditional probability of playing action é is =(W.e) we have:
P1
1 Σ
Σ
I(W1, (WW
U1
P1
REC AEEM
1
Σ
x(W,, (WD
U2
P2 LEC O
Without loss of generality, mass from row W2 to row W1. Specifically, x' is defined as follows:
i1 u2. construct new solution x' by transferring probability
e) P1 + P2 x (),
EEE Vl L,
P1
s' 2W2,, =0, x' ()
= e),
V other W,, AE E
It is straightforward to verify that x' satisfies the IC constraint. Now, show that the utility of x' is weakly greater than the utility of x.
U(x') = Σ Σ
P1 P2 (WW)))) P1
REC AE0
+ utility from rows other than (W1, W2}
(p1 P2)u; + utility from rows other than (W1, W2}
> prun p2u2 + utility from rows other than (Wi Wa} (x).
Note that the W2 row of x' has become O. We can apply this construction iteratively until only one row remains non-zero, without decreasing utility, thus obtaining an optimal solution with only one non-zero row.
26

---

Published as a conference paper at ICLR 2026
Let x² be optimal solution to the linear program [66]
row W*. Let TBs = maX.) (D( be an optimal solution for the Bayesian Stackelberg game. We prove that U(x*) = U (Bs))
17 with only
First, we prove (D( I Ux=".. Let WBs be the best-response function corresponding to Bss ie., "Bs E It( Bs). We construct a feasible solution a to the linear program (7) by setting the row indexed by W nş Tss and assigning zero values to all other rows. By definition, satisfies the IC constraint, so it is a feasible solution. Moreover, Ths and x achieve the same objective value (D( (x). By definition,
(x) is weakly less than the optimal objective value Uxx*) of the linear program, so UD (IBB)) I (x"").
Then, prove Uxx") < UD (DBB)))) Suppose the leader uses the strategy defined by the non-zero row x², which is x "W",, E (C). By the IC constraint of the linear program, the best-response function of the followers is equal W* the expected utility the leader exactly equal U (x*). which is < UD (3n))) because hs is an optimal solution for the Bayesian Stackelberg game.
Step 2: Reduce online Bayesian Stackelberg game to a linear bandit problem. Based on the
linear program formulation [17) we then reduce the online Bayesian Stackelberg game problem to linear bandit problem, using the technique in |Bernasconi et al. (002)) Let X' C A(A"* x L) be the set of feasible solutions to the linear program (16) when the follower types are A E [K]" as:
We define the loss of strategy x X
Lø(x) =- Σ Σ
2(W,))u(e,W(()).
WEA
REC
We define a linear map Ø X RK that maps strategy æ E X' to vector in RK representing the loss of the strategy for each type profile:
Lo, (x)
d(x)
E ERK"
Loge (x)
Its inverse, øt : R RK" + X maps a loss vector back to strategy. Let co 6(X') denote the convex hull of the image set of ạb.
Let Ri be stochastic linear bandit algorithm with decision space co (x2) S R K In particular, we let Ri be the OFUL algorithm -Abbasi-yadkori et al. 2011). At each round, A outputs strategy z' co ((X',, and we invoke Carathédory oracle to decompose z" into K" + elements from (X)), forming a convex combination| (6) We then sample one the elements z/. and apply the inverse map øf to obtain a strategy x' E X' for the leader. After playing strategy x², we observe the utility u' u(E", a²) and feed the utility feedback R.
Theorem C.1. The expected regret of Algorithm is O(K" T).
Proof. Because x² X'= = A(AnK L) is feasible solutions to the linear program x 17 it satisfies the IC constraint, So, when the leader plays x² (WW))/(WW) E A(C), the followers (with types 0) will best respond according to the function (O). Thus, the leader's expected utility at round is
(W,e)
Σ P(W)
Σ D(O)u(E, = U(+') -Eo-'Lo(("')
p(W)
WEA
REC
Then, the regret of Algorithm 5 ilin' T' rounds can expressed
Reg(T) = Σ (Bo-DILo(z")) -oo-
1=1
"The Carathédory oracle hased on the well-known Carathédory Theorem.
27

---

Published as a conference paper at ICLR 2026
ALGORITHM 5: Linear Bandit Algorithm for Bayesian Stackelberg Games
Input: :A linear bandit algorithm Ri over decision space co ( where R. RECOOMENDD
returns element in o(2), and P.OBSERVELOSS takes the loss feedback.
for each round t do
Use M.RECOMMENDO to obtain zí E co ((X) C I
Call a Carathéodory oracle with input (=", (()), which returns k 1 elements
{2f, X[ such that:
K +1
K=+1
where Σ
Draw an index j E fl..... K" + +1} with probabilities X/. Compute x² + =T(()) Note that x' E A(Ark x C) is matrix.
Play z' in the following sense: sample row W E AAnK with probability x² (W, f), then play the mixed strategy x² (W, E (4). Observe the realized utility w' ulle, a').
Feed the loss to Rt by calling PL.OBEERVELOSSS-UU
We let R be the OFUL algorithm (Abbasi-yadkori et al. 2011
where x² is the optimal strategy in X, which minimizes the expected loss (maximizes expected utility). Let Regør d(x) (T) be the expected regret of the linear bandit algorithm Ri on decision space co (xx) in rounds. According to the Theorem 3.1 of Bernasconi al. (2023
Reg(T)) < Regst oo ((x) (T).
We let Ri be the OFUL algorithm (Abbasi-yadkori stochastic loss can be expressed as L' (2. D + n with L'
al. 2011 For any co (()) C R the
| 2 S | = 1. and
'y' being bounded zero-mean noise. Then, from Abbasi- Abbasi-yadkort al. 201 h's Theorem 3, we have with probability at least 55
TL K
x1/2+ +
TL AK"
Regss.co (T) s 4 TK" log
A +
2 2
+ K"llog
1+
where À is tunable parameter in the OFUL algorithm. By setting and
7. we obtain
E [eg( $ (1 - 5) O(K"VTlog 7) 5 = O (ogg))
C.2 PROOF OF LEMMA
We can express the leader's utility function as
u(æ, a) Ex(()((t,a) a) (xr, ua)
EEC
where vector uua = (u(E, a)leez E RL, Note that u(r, a) is linear function of va- Consequently. the expected utility of a strategy R(W) on the true distribution D given by
Uxx, R(W)) Ea- P() (a va)]]
Given samples a!,...,'* N, we can compute U UA because we know the utility function. By Lemma B.1 the pseudo-dimension of the family of linear functions ((x,-) E R(W) RC) is L. Applying Theorem B.I. with N samples, we have
2L log 3N
log 2N
Pr Rr E R(W), (x R(W)) Úw(1, R(W)))
N
28

---

Published as a conference paper at ICLR 2026
Let 6 Te. Taking union bound over all N T and all W W, obtain
2L log(N
log 74
Pr
A E WN (7], Fr R(W), [U( R(W)) (n R(W))
N
2.N
W 1
$ IWT6- T T
(assuming T 2 [WD. Thus, with probability at least J. for every W e W, E [T]. and R(W), we have
Ux, R(W)) - ÜN R(W)) $ 4(L + 1) log(3T)
using the inequality v + vbs 22(a b).
C.3 PROOF OF THEOREM 5.2
By Lemma the event
[A( 1) log(3T)
C= VW W,YN e Vr) R(W), U(x, Unl,,
N
happens with probability at least 1 7/2 Suppose C' happens. The regret at round is given by
r(t) = U2= R(W*)) - U(z,, R(W")).
For any strategy x E R(W), we define the upper confidence bound of its utility as
UCB'(2) (x) (x"(w)(r, + 4(L + 1) log((3)
N'(W)
Since C' holds, it follows that
U(*", ((=",)(W")) s UCB'(x").
Because the UCB algorithm chooses the strategy with the highest upper confidence bound at round 6, we have UCB'(x*) I UCB' (a*). Thus,
(f) s UCB'(x") s UCB'(xx) - Ulz',
R(W")
(s' R(W*)) ( U(o", R(W*))+ 4(L + 1) log(3T) No(W")
4(L + +1)+111gg0 log((3
V (W!)
The total regret is at most
T Σ r(t)
Rog(T)
=
1=1
4(L + 1) log
<
N((W))
t=1
(TWW) Σ
4(L + 4(I+1) (3g((3)
Σ
WeW m=1
< Σ
V NT (I 1) log(3T)
WEW
29

---

Published as a conference paper at ICLR 2026
where we applied the inequality Em= / S 2VN. By Jensen's ' inequality,
Σ (N((W) s
Σ
NT(W)
1 T. V W
W WEW
W
WEW
Thus,
(Tg(T) s 8 E VIWIT V(L+1)log(31)
WEW
0 V' T TlggT)
where we used [W| = O( A24) from Lemma
3.2
Finally, considering the case where C' does not happen (which has probability most (tx)
E[Reg(T)) (T) (1
1 + (nnOVVLKLARRR .logT) + 72
1 T
OVvnkiz A2LL .lggT
D SIMULATIONS
We empirically simulate and validate the results of the studied algorithms in both the type-feedback setting and action feedback setting. For the former, consider the independent type setting to understand how much better, in practice, is Algorithm 2 (customized for independent types) as opposed the general purpose Algorithm|] [ (works for general type distributions). We consider an (I, = 2, K = 6, A = 2, n 2) instance and simulate the results in Figure 2 As expected, the specialized algorithm does indeed outperform the general one.
For the action feedback case, we empirically compare our UCB-based Algorithm3] with the linear bandit approach inspired by |Bernasconi et al. (2023). Algorithm We especially consider the small L regime where our theory does not provide any concrete guidance. Shown in Figure 3 consider an (L = 2, K 6, A = 2, n = 2) instance and observe the advantage of the -CB-based algorithm over the linear bandit one.
Type Feedback Simulations
Action Feedback Simulations
0.90
Alg Regret
+
Lin Bandit Regret
Alg 2 Rogost
12
Als (UCB+BR Region) Regret
0.80
Bagret
8-
0.70
0.80
4-
20
60 Round
100
20
40
60
100
Round
Figure 2: Cumulative regret from the type- feedback based Algorithms I and 2 for (L 2, K = 6, A = 2, n = 2) instance with inde- pendent types. We plot the average 2000 simulations with 90% confidence intervals.
Figure 3: Cumulative regret from Algorithm
5 (the Linear- Bandit approach inspired by
Bernasconi et al. (023)) and Algorithm 3 for
2, 6, A 2, = 2) instance. We plot the average over 2000 simulations with 90% confidence intervals.
30


Reviews:
[{"review_id": "Y5JhDapYcU", "reviewer": "Reviewer_jBAa", "summary": "This paper studies the problem of learning an optimal commitment against multiple followers, each of whose type is drawn from a distribution. In doing so, this paper generalizes the usual Stackelberg paradigm of optimal commitment against a single follower and even the Bayesian Stackelberg setting where the single follower’s type is drawn from a distribution.\n\nThe latter problem is known to be NP-hard in general, implying hardness for this more general problem. A natural algorithmic approach for this problem is to partition the leader’s action space into regions that correspond to best-response regions for the different follower profiles. However, the bottleneck to such an approach is that the number of partitions grows exponentially in the number of types for the follower — this problem doubly applies with multiple followers, since the number of best-response (BR) profiles has exponential dependence on the number of followers as well.\n\nThis paper surmounts this technical difficulty by using results from computational geometry to bound the number of non-empty regions with exponential dependence only on the number of “pure” actions of the learner. The paper also provides an explicit enumeration of these non-empty regions with the same asymptotic parameters, thus providing an offline algorithm for the problem. Then, they strengthen this to an online learning algorithm, which is able to learn the optimal policy at a rate faster than just learning the distributions based on intricate technical analysis. Their results cover both the settings where the type of the followers is seen at the end of each round versus just their action, and provide lower bounds with the same exponential dependence.", "questions": "Do the results extend to settings where the action sets are arbitrary convex sets of a specified dimension, especially for the leader?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper provides a novel technique that breaks through the barrier of exponential best response profiles with multiple followers/ follower types, by focusing on the dimension of the leader's action space. This allows for a fine-grained view of the complexity of finding an optimal commitment and opens the door for the upper bound results in the paper which as noted, from the first positive results for multiple followers. The paper covers a variety of settings and is overall a very strong submission with novel technical contributions.", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lUWVqfn1mE", "reviewer": "Reviewer_Sbtn", "summary": "The paper studies the online learning version of the multi-follower Bayesian Stackelberg game. The authors consider the setting where the leader knows each follower's utility function but not their private types. The paper designs learning algorithms for the leader under both type-feedback and action-feedback settings, and provides detailed regret analysis.", "questions": "Please see my comments above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow. The authors conduct an in-depth analysis of the geometric properties of the game, which provides insights for the learning algorithms. I find the proposed algorithm interesting as it significantly reduce regret. The theoretic results look solid and strong to me (did not check all the proof details though). The multi-follower setting is much more general than the standard version, and the propose method can potentially improve the applicability of the Bayesian Stackelberg game.", "weaknesses": "There are some minor issues with the paper. The definition of $W$  in Subsection 3.2 seems inconsistent. If $W$ is a matrix, then the $i$-th element of $W$ should be $w_i: \\Theta^K \\mapsto A^K$, not $w_i: \\Theta \\mapsto A$. Am I missing something here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DKwfZ1UPs6", "reviewer": "Reviewer_F5NQ", "summary": "The paper studies multi-follower online Bayesian Stackelberg games. The authors study 2 types of feedback: type feedback, where at each turn the leader observes the tuple of realized types, and action feedback, in which the leader observes the individual actions. Clearly knowing the types implies knowing the actions.\nTypes are either drawn from a joint or product distribution.\nUnder type feedback the authors gives an algorithm which attains regret of $\\sqrt{T\\min(L,K^n)}$  under joint distribution, or, $\\sqrt{T\\min(L,Kn)}$ under product distribution, where $L$ is the number of actions of the followers, $K$ the number of possible types and $n$ the number of players. The algorithm revolves around \nUnder type feedback (under joint distribution) the algorithm is simply follow the leader. Interestingly, the analysis shows concentration around the empirical utility rather than under the correct type distribution. This aligns with the following section on action feedback, where working in the utility space is the correct trick to get around exponential dependencies.\nUnder type feedback and independent distribution, the algorithm simply estimated each distribution separately.\nUnder action feedback, the authors rely on a known reduction for a related problem of online Bayesian persuasion. The technical challenge here is to show that there exists a single LP that solves the problem.", "questions": "Is the improvement from K^{3n/2} to K^n only due to the fact that you consider stochastic types rather than adversarial ones?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This is a good paper that has non trivial contributions, even if maybe a bit lackluster from a technical side.", "weaknesses": "I see two main weaknesses:\n1. Even if I find the overall presentation satisfactory, its quality degrades in some specific points. It is not clear where do you use the best response partitions. For example, the discussion under Lemma 4.1 seems to be very important, but right now it feels somewhat obscure and does not do a good job at explaining the crucial points. Another point in which the presentation is a bit confused is around line 409. It is not even clear if this part relies at all on the reduction of Bernasconi et al. or not. I think not, but better clarity would be nice. Overall, I think the paper suffers from having too many results compressed. I would suggest to the authors that maybe they defer some of the results to the appendix and devote more space to points that are now a bit compressed.\n2. Why do you not consider adversarial types? I think your FTL approach would still be a good candidate for adversarial types (obviously by using FTPL instead). The reduction of Bernasconi for sure also works for adversarial types. So it is a bit strange that you do not consider this problem, which is the most studied in Online learning in Econ settings.\n\n* Typo in statement of Lemma C.1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pX1aZJKUw0", "reviewer": "Reviewer_av7X", "summary": "The paper studies online learning for multi-follower Bayesian Stackelberg games where a leader commits to a mixed strategy and $n$ followers (each with one of $K$ private types) best respond. The authors analyze two feedback models: type feedback and action feedback. The paper proposes a geometric decomposition of the leader’s simplex into best-response regions and algorithms with sublinear regret. For type feedback they give $\\tilde{O}(\\sqrt{\\min\\{L,nK\\}}\\,T)$ for independent types, $\\tilde{O}(\\sqrt{\\min\\{L,Kn\\}}\\,T)$ for general types, and a matching lower bound $\\Omega(\\sqrt{\\min\\{L,nK\\}}\\,T)$. For action feedback they propose a reduction to stochastic linear bandits with $O(Kn\\sqrt{T}\\log T)$ regret and a UCB  approach with $O(\\sqrt{n^{L}K^{L}A^{2L}}\\,L\\,T\\log T)$ regret.", "questions": "Could you elaborate more the statement: “In comparison, Conitzer & Sandholm (2006) prove that the optimal strategy is NP-hard to compute in BSGs with an asymptotically increasing $L$. We show this is polynomial-time solvable for a constant $L$.” (Line 274)\nCould you cite the exact theorem/lemma in Conitzer & Sandholm, specify the precise problem and briefly contrast your assumptions with theirs to explain why constant $L$ yields polynomial time here.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper introduces a clean geometric decomposition of the leader’s strategy space into follower best-response regions and leverages this structure to derive regret guarantees for multi-follower Bayesian Stackelberg games. The resulting bounds avoid polynomial growth in the number of followers $n$, and the authors provide a lower bound that nearly matches the type-feedback upper bounds.", "weaknesses": "1. In the general single-leader-multi-follower setting, a follower’s utility typically depends on both the leader’s action and other followers’ actions (i.e., there are cross-follower externalities). The paper assumes each follower’s payoff depends only on their own action and type plus the leader’s action—which substantially simplifies the model and makes the extension from one to many followers more direct. While this assumption enables clean analysis, it limits the applicability of the results to settings without strategic interdependence among followers.\n2. The analysis assumes followers play the exact best response in every round. This is a strong assumption for a learning setting: in many practical environments followers also learn, face estimation error, or act under noisy rewards, leading to approximate or stochastic best responses. The results would be more interesting with guarantees to $\\varepsilon$-best responses or noise in followers’ payoff observations.\n3. The reduction to stochastic linear bandits is not novel. Similar reductions have appeared in prior work [1].\n\n\n[1] Nearly-optimal bandit learning in stackelberg games with side information. Balcan, Maria-Florina, et al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)