🤖 machine learning

Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information

This paper presents novel learning algorithms for online Stackelberg games with side information that achieve a nearly-optimal $O(T^{1/2})$ regret under bandit feedback by reducing the problem to linear contextual bandits, thereby improving upon previous $O(T^{2/3})$ rates and demonstrating effectiveness in applications like auction bidding and Bayesian persuasion.

Original authors: Maria-Florina Balcan, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Keegan Harris, Zhiwei Steven Wu

Published 2026-05-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Maria-Florina Balcan, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Keegan Harris, Zhiwei Steven Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a high-stakes game of chess, but with a twist: one player (the Leader) makes a move first, and the other player (the Follower) sees that move and immediately responds with the best possible counter-move. This is called a Stackelberg Game.

In the real world, this happens everywhere:

Airport Security: The TSA (Leader) decides where to put their dogs and scanners. A smuggler (Follower) sees this and tries to sneak through the weakest spot.
Wildlife Protection: Rangers (Leader) decide where to patrol. Poachers (Follower) watch and hunt where the rangers aren't.

The Problem: Learning in the Dark

Usually, the Leader knows exactly how the Follower thinks. But in this paper, the authors imagine a scenario where the Leader is blind to the Follower's specific goals. The Leader only gets a "hint" (called Side Information) before making a move—like knowing it's a rainy day, or that the airport is crowded.

After the game is played, the Leader only gets a score (did I catch the smuggler? did I lose money?). They don't get to see the Follower's internal thoughts or their exact strategy. This is called "Bandit Feedback." It's like playing a video game where you only see your health bar go up or down, but you don't see the enemy's move or the map.

Previously, the best algorithms for this "blind" learning were slow and clumsy. They needed a lot of practice rounds to get good, and their mistakes grew at a rate of roughly $T^{2/3}$ (where $T$ is the number of rounds).

The Breakthrough: The "Utility Translator"

The authors, Maria-Florina Balcan and her team, built a new algorithm that learns much faster. They improved the mistake rate to roughly $T^{1/2}$ . In plain English, this means the Leader learns twice as fast as before.

How did they do it? The "Menu" Analogy.

Imagine the Leader is a chef trying to please a customer (the Follower).

The Old Way: The chef tries random recipes, tastes the result, and slowly guesses what the customer likes. This is slow.
The New Way (The Paper's Method): The chef realizes that instead of guessing recipes, they should guess the customer's satisfaction score directly.

The authors created a clever trick:

They pretend the game isn't about choosing a strategy (like a patrol route), but about choosing a vector of scores (a list of numbers representing how happy the Leader would be against different types of followers).
They use a "translator" (a linear contextual bandit algorithm) to pick the best score-vector.
Then, they work backward to find the actual strategy (the patrol route) that produces that score.

By translating the complex, messy game into a simple "score prediction" problem, they can use powerful, existing math tools to learn incredibly fast.

The Two Scenarios

The paper tests this "Translator" in two different worlds:

The Weather Changes, The Criminals are Random: The context (weather, time of day) is chosen by a tricky adversary, but the types of followers (smugglers, poachers) appear randomly.
The Criminals Change, The Weather is Random: The weather is random, but the types of followers are chosen by a tricky adversary.

In both cases, their new algorithm wins, achieving the "nearly-optimal" speed of $T^{1/2}$ .

Other Games They Played

The authors showed that this "Translator" trick isn't just for security games. It works for:

Online Auctions: Bidding on items where the value depends on outside news (like fashion trends).
Bayesian Persuasion: A sender trying to convince a receiver to take an action by revealing partial information (like a salesperson trying to sell a product based on a customer's mood).

What About Unknown Utilities?

What if the Leader doesn't even know their own scoring system? (e.g., "I don't know exactly how much I value catching a poacher vs. saving fuel").
The authors extended their method to handle this too, assuming the Leader's value is a simple linear combination of the context. It still works fast, though it requires a bit more computing power to figure out the hidden values.

The Bottom Line

The paper solves a long-standing puzzle in game theory: How do you learn to play a strategic game when you can't see your opponent's mind, only their reaction?

By turning the problem into a "score prediction" game, they created a method that learns significantly faster than anything before it. They proved this mathematically and showed in computer simulations that their method beats the old ones, just like a grandmaster chess player who has learned to see the board in a new, more efficient way.

Technical Summary: Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information

Problem Formulation

This paper addresses the problem of online learning in Stackelberg games with side information (context). The setting involves a repeated interaction between a leader and a sequence of followers over $T$ rounds. In each round $t$ :

Both players observe a context $z_t \in \mathcal{Z} \subseteq \mathbb{R}^d$ (side information, e.g., weather, traffic, or intelligence reports).
The leader commits to a mixed strategy $x_t \in \Delta(\mathcal{A}_l)$ .
A follower $f_t$ (of one of $K$ possible types) observes the context and the leader's strategy, then plays a best-response action $a_{f,t}$ .
The leader receives a reward based on their utility function $u(z_t, a_{l,t}, a_{f,t})$ , while the follower receives utility based on their own function.

The learning environment is characterized by bandit feedback: the leader observes only their own realized utility and the follower's action, but never observes the identity of the follower type or the follower's utility function. The paper considers two primary adversarial/stochastic regimes:

Adversarial Contexts, Stochastic Followers: The sequence of contexts is chosen by an adversary, while follower types are drawn from an unknown stationary distribution.
Stochastic Contexts, Adversarial Followers: The sequence of contexts is drawn from an unknown distribution, while follower types are chosen by an adversary.

The goal is to minimize Contextual Stackelberg Regret, defined as the difference between the cumulative utility of the optimal hindsight policy (which knows the context and follower sequence) and the leader's cumulative utility.

Methodology

The core contribution is a reduction to linear contextual bandits in the leader's utility space. While the leader's utility is non-linear with respect to their mixed strategy $x_t$ (due to the follower's best-response function), the authors exploit the finite number of follower types ( $K$ ) to linearize the problem.

The Reduction

Utility Space Representation: For a given context $z$ and strategy $x$ , the leader's utility against each follower type $i \in [K]$ can be computed. These utilities form a vector $u(z, x) \in \mathbb{R}^K$ .
Linearization: The actual utility received in round $t$ against follower type $f_t$ can be expressed as the inner product $\langle u(z_t, x_t), \mathbf{1}_{f_t} \rangle$ , where $\mathbf{1}_{f_t}$ is a one-hot vector representing the follower type.
Discretization: Although the strategy space $\Delta(\mathcal{A}_l)$ is infinite, the paper restricts the leader to a finite set of $\delta$ -approximate extreme points ( $E_t$ ) of the contextual best-response regions. This discretization incurs negligible regret ( $O(1)$ ) while ensuring the set of possible utility vectors $U_t = \{u(z_t, x) : x \in E_t\}$ is finite.
Algorithm 1: The proposed algorithm operates as follows:
- Observe context $z_t$ and compute the set of feasible utility vectors $U_t$ .
- Query a linear contextual bandit algorithm $\mathcal{R}$ to recommend a vector $v_t \in U_t$ .
- Invert the mapping to find the mixed strategy $x_t$ that induces $v_t$ .
- Play $x_t$ , observe the reward, and feed the realized utility back to $\mathcal{R}$ .

Instantiations

The paper instantiates Algorithm 1 with specific bandit algorithms depending on the setting:

OFUL (Optimism in the Face of Uncertainty for Linear models): Used when follower types are stochastic. It learns the unknown distribution $p^*$ over follower types.
logdet-FTRL (Follow-The-Regularized-Leader with log-determinant barrier): Used when follower types are adversarial. This variant handles adversarial losses in linear contextual bandits.

Extension to Unknown Utilities

The framework is extended to settings where the leader's utility function $u$ is unknown. Under a linearity assumption (Assumption 3.3), where $u(z, a_l, a_f) = \langle z, U(a_l, a_f) \rangle$ , the problem is reduced to a higher-dimensional linear contextual bandit problem. The feature vector is expanded to include the interaction between context, leader action, and follower action, allowing the algorithm to learn the unknown parameters $\theta$ .

Key Contributions and Results

1. Improved Regret Bounds

The paper closes the gap between known upper and lower bounds for bandit feedback in this setting:

Stochastic Followers / Adversarial Contexts: Achieves $\tilde{O}(\sqrt{T})$ regret (specifically $O(K\sqrt{T}\log T)$ ). This improves upon the previous best of $\tilde{O}(T^{2/3})$ by Harris et al. (2024).
Adversarial Followers / Stochastic Contexts: Achieves $\tilde{O}(\sqrt{T})$ regret (specifically $O(K^{2.5}\sqrt{T}\log T)$ ).
These rates match known lower bounds up to logarithmic factors, establishing near-optimality.

2. Unknown Utility Extension

The authors show that if the leader's utility function is unknown but linear in the context, the $\tilde{O}(\sqrt{T})$ regret rate is preserved, albeit with a polynomial dependence on the dimension of the context ( $d$ ) and the sizes of the action spaces ( $A_l, A_f$ ). The regret scales as $\tilde{O}(\text{poly}(d, K, A_l, A_f)\sqrt{T})$ .

3. Applications to Other Domains

The reduction technique is applied to two other settings where side information is prevalent but previously unstudied in this specific bandit context:

Second-Price Auctions: Learning to bid in combinatorial second-price auctions with side information. The paper provides the first no-regret algorithms for this setting with bandit feedback.
Online Bayesian Persuasion: Learning signaling policies in Bayesian persuasion games with public and private states. The results extend to settings with side information, achieving $\tilde{O}(\sqrt{T})$ regret.

4. Empirical Validation

Numerical simulations on synthetic Stackelberg games demonstrate that the proposed algorithm (Algorithm 1-OFUL) significantly outperforms previous baselines (specifically Algorithm 3 from Harris et al., 2024) in terms of cumulative utility and regret, even in cases where follower utilities depend on side information (a scenario where prior algorithms were not applicable).

Significance and Claims

The paper claims to provide the first nearly-optimal (up to logarithmic factors) learning algorithms for Stackelberg games with side information under bandit feedback. By shifting the learning problem from the non-linear strategy space to the linear utility space, the authors leverage the rich literature on linear contextual bandits to overcome the computational and statistical challenges of the original problem.

The significance lies in:

Theoretical Tightness: Matching the lower bounds for this class of problems, resolving the gap left by previous $T^{2/3}$ results.
Generality: The reduction is modular, allowing the application of different bandit algorithms to different adversarial/stochastic assumptions without redesigning the core Stackelberg learning logic.
Broad Applicability: Demonstrating that the same structural reduction applies to auctions and Bayesian persuasion, suggesting a unified approach for learning in strategic environments with side information.

The authors note that while the worst-case runtime is exponential due to the size of the discretized strategy set (inheriting NP-hardness from offline Stackelberg computation), the approach is practical for settings with small numbers of effective follower types or dominated actions, and empirical results show strong performance.