Research map / Bandits and online learning / Online convex optimization and games
Regret Minimization in Stackelberg Games with Side Information
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes Stackelberg games with side information (contexts seen by both players), proves no-regret is impossible under fully adversarial contexts and follower types, and gives no-regret algorithms when either sequence is stochastic, plus bandit-feedback extensions.
Problem
Online learning for a leader in Stackelberg games where both players observe a context each round and follower types vary, so the leader must learn context-dependent strategies.
Approach
Defines contextual Stackelberg regret against the best context-dependent policy in hindsight; shows impossibility under full adversary via reduction from online linear thresholding; obtains no-regret by greedy estimation of follower best-response distributions (stochastic followers) and by Hedge over a finite set of policies built from approximate extreme points of contextual best-response regions
Key results
- placeholder
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow both contexts and follower types to be chosen adversarially | Stackelberg games with side information · Fully adversarial setting | contextual Stackelberg regret: Ω(T) | Hurt |
| Make follower types stochastic while contexts remain adversarial | Stackelberg games with side information · Stochastic followers, adversarial contexts; full feedback | expected contextual Stackelberg regret: O \left(\min\{K, A_f\}\sqrt{T \log T} \right) | Helped |
| Make contexts stochastic while follower types remain adversarial | Stackelberg games with side information · Stochastic contexts, adversarial followers; full feedback | expected contextual Stackelberg regret: O \left(\sqrt{K T \log T} + K \right) | Helped |
| Use bandit feedback instead of full feedback | Stackelberg games with stochastic followers and adversarial contexts · Stochastic followers, adversarial contexts | expected contextual Stackelberg regret: O \left(\min\{K, A_f\}\sqrt{T \log T} \right) -> O\left(K^{2/3} A_f^{2/3} T^{2/3} \log^{1/3} T \right) | Hurt |
| Use bandit feedback instead of full feedback | Stackelberg games with stochastic contexts and adversarial followers · Stochastic contexts, adversarial followers | expected contextual Stackelberg regret: O \left(\sqrt{K T \log T} + K \right) -> O \left(K A_f^{1/3} T^{2/3} \log^{1/3} T \right) | Hurt |
Surprising findings
- Fully adversarial no-regret learning is impossible even when the optimal policy class is highly structured (linear thresholding).
Limitations
- Fully adversarial setting admits no no-regret algorithm
- Bandit-feedback results only hold against non-adaptive adversaries and assume follower utility independent of context
- Finding approximate extreme points can be exponentially large in K and A_f
Experimental setup
Benchmarks: synthetic Stackelberg game simulations (K=5, A=A_f=3, d=3)
Metrics: cumulative reward
Baselines: non-contextual Stackelberg learning algorithm (ignores side information)
Builds on: Hedge online linear thresholding barycentric spanners non-contextual Stackelberg learning (Balcan et al.)
Closest papers by meaning
- Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information (ICLR 2026 · similarity 0.92)
- Learning in Structured Stackelberg Games (ICML 2026 · similarity 0.91)
- Learning in Bayesian Stackelberg Games With Unknown Follower's Types (ICML 2026 · similarity 0.90)
- Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring (NeurIPS 2025 · similarity 0.88)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.88)
- Sequential Decision Making in Stochastic Games with Incomplete Preferences over Temporal Objectives (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.