Stackelberg POMDP: Learning to Lead via Reinforcement Learning
Authors: Matthias Gerstgrasser, Gianluca Brero, Alon Eden, Darshan Chakrabarti, Nicolas Lepore, Vincent Li, Eric Mibuari, Amy Greenwald, +1 more
Organizations: John A. Paulson School of Engineering and Applied Sciences, Harvard University · Data Science Initiative, Brown University · School of Computer Science and Engineering, Hebrew University of Jerusalem · Department of Industrial Engineering and Operations Research, Columbia University · Department of Computer Science, Brown University
Many real-world domains--including e-commerce platform design, security planning, and multi-agent coordination--feature leader-follower problems where one decision-maker commits to a policy and others react strategically. We develop a reinforcement learning framework for such interactions in sequential environments with partial observations and multiple followers. Followers may adapt through no-regret learning or reinforcement learning, potentially departing from equilibrium behavior. The framework embeds follower adaptation into the leader's environment to construct a single-agent partially observable Markov decision process--the Stackelberg POMDP. For policy-interactive response algorithms, which access the leader's policy through queries, we prove that an optimal policy based only on the leader's game history yields an optimal commitment under the specified response procedure. We use proximal policy optimization with a centralized critic and train contextual meta-followers to respond across leader policies. In indirect mechanism design, mechanisms using buyer messages achieve higher social welfare than optimal standard sequential price mechanisms across all tested type counts, with responses certified as approximate Bayesian coarse correlated equilibria. In platform design, learned display rules increase mean consumer surplus by 8.4% over an optimized fixed price cap while accommodating hidden seller costs. In Atari bilateral trade, meta-learned follower responses support joint learning of visual gameplay and economic decisions; assigning leadership to the seller or buyer shifts transaction prices and payoffs in that agent's favor. Controlled ablations examine how response credit, policy consistency, and reward timing affect learning.
Figures & tables
Figure 1 : A Stackelberg POMDP episode. In the follower response phase , algorithm A is simulated for E steps. At each step e , A issues a query (a leader observation history hℓ,e ) and receives the leader’s response aℓ,e∼πS(hℓ,e) , updating its state from sb,e to sb,e+1 . By step E , the algorithm state sb,E contains the follower response profile π−ℓ∗ . In the reward phase , the leader plays the game G against these follower policies, yielding total return Rℓ(τ) .
Application
Leader’s choices
How followers respond
Leader’s goal
Indirect mechanism design
Allocation and pricing rules
Multiplicative weights
Maximize social welfare
Platform intervention
Price-contingent display
Q-learning
Maximize consumer surplus by mitigating algorithmic collusion
Atari bilateral trade
How to play and trade ammunition
Contextual meta-follower
Maximize the leader’s payoff from gameplay and trade
Table 1 : Leader choices, follower responses, and goals in the three application families.
Figure 2 : MSPM welfare with two messages and 25 fresh seeds per type count. (a) Training on the scaled two-type benchmark of Agrawal et al. (2020) . Welfare of the current mechanism is evaluated every 200 episodes, without smoothing; shading is one standard error. Horizontal lines mark exact optimal SPM welfare 0.380 and ex post efficient welfare 0.440 . (b) Comparison across type counts. W∗ is ex post efficient welfare, and the SPM optima are exact. MSPM entries give the mean (sample SE) of each seed’s best certified evaluation over 10,000 episodes. Types 3–6 use independent uniform value grids.
Intervention / summary
c=1.0
c=1.5
Equal-cost average
Fixed threshold p(7)=1.55
0.6431
0.6431
0.6431
Clipped minimum [p(4),p(7)]
0.8280
0.6431
0.7356
Random search (one run)
0.5144
0.4129
0.4636
PPO: mean
0.8047±0.0132
0.5897±0.0206
0.6972±0.0154
PPO: median
0.8429
0.6431
0.7430
Table 2 : Consumer surplus on fresh seller responses. Every policy is evaluated at both hidden costs on 25 fresh seller seeds per cost. PPO rows summarize the final policies from 25 leader runs. Means and medians are computed across run-level scores, with each run’s two costs averaged first in the last column; ± denotes one standard error across leader runs. Validation selects the fixed and clipped rules; fresh scores never select a policy. Random search supplies one selected policy, evaluated on an independent fresh cohort.
Figure 3 : Learned commitment and normalized PPO training. Left: a top-performing final policy (seed 801), selected among all 25 runs by highest final validation score, with smallest-seed ties. Dark blue admits both sellers, light blue only the lower-price seller, and near-white neither. L and H mark observed long-run price pairs at costs 1.0 and 1.5: all 25 fresh responses per cost reach the respective marked pair, with both sellers displayed. Right: current-policy validation CS throughout training. Thin lines show individual runs; shading is one standard error around their mean. All curves and benchmark lines average both costs and the same five validation seller seeds. The random-search line evaluates its selected policy. The horizontal axis counts seller-response computations; see Appendix B.2 for response and evaluation protocols.
Figure 4 : Fixed-context diagnostics for the two contextual meta-followers. Panel (a) shows buyer purchases and shots against constant seller-price vectors p1 . Panel (b) shows seller quotes against constant buyer-threshold vectors t1 ; the dotted line p=t marks the acceptance boundary. Panel (c) combines role-specific follower payoffs. The buyer curve varies the seller price, whereas the seller curve varies the buyer threshold, so the two curves come from separate evaluations. Each point averages 20 held-out episodes using the schedule (20,50,80,110,140) ; error bars show one sample standard error and are visually negligible.
Figure 5 : StackPOMDP training under role reversal, including exact pre-update evaluation. Panels report (a) seller payoff, (b) buyer payoff, and (c) mean accepted transaction price. Curves average 25 training-seed policy means per role evaluated on the same 20 held-out episodes; bands show one standard error across seed-level means. At initialization, every seed-specific reconstruction has the same deterministic economic output, 0.5 . The next four points are prespecified training checkpoints and the last is the actual post-training policy. Seller leadership raises accepted prices and seller payoff, whereas buyer leadership lowers prices and shifts payoff toward the buyer.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6 : MSPM training on the uniform value grids with three through six types per buyer. Welfare gaps W−W∗ are evaluated exactly every 200 episodes, without smoothing; zero denotes ex post efficient welfare. Shading is one standard error. Dotted lines mark the exact optimal SPM benchmarks.
Figure 7 : Atari policy architecture. (a) The shared composite actor uses image and low-dimensional state features for gameplay and a generic Beta head for the economic action. The meta-buyer supplies the complete contextual state to both branches; leaders restrict the economic branch to event identity. (b) The meta-seller alone replaces the generic economic head with live-state and commitment branches that produce a Beta-distributed price.
Training stage
nsteps
Learning rates, initialization, and trainable modules
Fixed-ammunition gameplay
200
Base rate 2.5×10−4 ; new visual and state encoders, Atari head, and private critic; economic action inactive.
Delayed-ammunition gameplay
205
Base rate 2.5×10−4 ; transferred visual encoder and Atari head use 2.5×10−5 , while the state encoder and new critic use the base rate; economic action inactive.
Contextual meta-buyer
205
Base rate 1×10−4 ; transferred visual encoder and Atari head use 1×10−5 , while the state encoder, generic Beta head, and new critic use the base rate. The Beta head is initialized with mean 0.95 and concentration 10 .
Contextual meta-seller
205
Gameplay actor frozen; live branch uses 5×10−4 , context branch and event slope use 2×10−3 , and the new critic uses 1×10−4 ; the three groups are clipped separately at 0.5 . The Beta head is initialized with mean 0.5 and concentration 2 .
Each StackPOMDP leader
205
Base rate 1×10−4 ; transferred visual encoder and Atari head use 1×10−5 , while the state encoder, new event-only Beta head, and new critic use the base rate. The Beta head is initialized with mean 0.5 and concentration 2 .
Appendix
Table 3 : Atari training configuration. Every stage trains for approximately two million environment transitions. Here nsteps counts policy-action rows per complete episode, excluding cached actions.
Figure 8 : Controlled response-credit ablation. (a) Exact expected gradients with respect to the leader logit: full credit gives p(1−p) and gameplay-only credit gives −p(1−p) . (b) Sampled REINFORCE training from p=1/2 , using 25 matched seeds, 64 complete episodes per update, learning rate 0.1 , and 1,000 updates. Both methods execute 128,000 actual transitions, including response queries. Curves show the mean exact value J(p)=p ; shading is one standard error across seeds and is narrow at this scale.
Figure 9 : Commitment consistency across phases. In iterated Prisoner’s Dilemma, a phase-aware leader obtains higher reward by inducing cooperation during response queries and defecting during reward play, but this is not one Stackelberg commitment. Each learning-rate curve averages 25 independent seed-level policy means, using 20 held-out episodes per scheduled evaluation. Shaded regions show one sample standard error across runs.
Figure 10 : Leader reward with and without reward during follower Q-learning in Battle of the Sexes. Plots show reward during actual play only (the relevant quantity for Stackelberg equilibria). Coordination failures give the leader payoff 0 in the left panel and −5 in the right panel; the follower payoff is 0 in both. Reward exclusion yields final-game payoff 2 in all 25 final policies in each panel. With response rewards included, 5 of 25 attain it without a penalty and none attain it with the penalty. Each curve averages 25 independent seed-level policy means evaluated on 20 held-out episodes; shaded regions show one standard error.
Comparison
Mean difference (SE)
Test
Adjusted p
MSPM
MSPM minus SPM, 2 types
0.0600(0.0000)
S
3.0×10−7
MSPM minus SPM, 3 types
0.0556(0.0000)
S
3.0×10−7
MSPM minus SPM, 4 types
0.0392(0.0014)
S
3.0×10−7
MSPM minus SPM, 5 types
0.0396(0.0014)
S
3.0×10−7
MSPM minus SPM, 6 types
0.0338(0.0003)
S
3.0×10−7
Appendix
Table 4 : Retrospective statistical comparisons. Differences follow the order in the first column. S: exact sign test; B: crossed bootstrap; W: Welch test. Adjusted p -values use Holm correction within each displayed family. There are 25 training seeds per condition; the platform also resamples seller seeds. Zero SE records identical observed outcomes across seeds. The random-policy comparison reaches the bootstrap’s Monte Carlo resolution before adjustment.
We initiate the study of structured Stackelberg games, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the follower's (unknown) type. Motivated by applications such as security games and AI safety, we show how this additional structure can help the leader learn a utility-maximizing policy in both the online and distributional settings. In the online setting, we first prove that standard learning-theoretic measures of complexity do not characterize the difficulty of the leader's learning task. Notably, we find that there exists a learning-theoretic measure of complexity, analogous to the Littlestone dimension in online classification, that tightly characterizes the leader's instance-optimal regret. We term this the Stackelberg-Littlestone dimension, and leverage it to provide a provably optimal online learning algorithm. In the distributional setting, we provide analogous results by showing that two new dimensions control the sample complexity upper- and lower-bound.
We study sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as partially observable Markov games (POMGs). The central challenge is to learn latent dynamics from partial observations while facing an adversary whose behavior depends on the learner's strategy, making standard regret notions inadequate. We prove that an epoch-based optimistic maximum-likelihood algorithm achieves O~(T) policy regret for fixed problem parameters, with explicit dependence on the horizon, adversary memory, confidence radius, and the aggregate Eluder dimension of the observable-operator class. The algorithm selects one policy per geometrically growing epoch using confidence sets built cumulatively from past data, which keeps the cost of comparing adversary responses across policies logarithmic in T. We also prove a lower bound matching the T and aggregate-Eluder-dimension dependence, up to problem-dependent and logarithmic factors. Finally, we extend the framework to horizon-adaptive guarantees and adversaries with geometric fading memory.
Raman Arora
Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA.
Reinforcement learning algorithms are commonly analyzed (and designed) under the Markov assumption. This is unrealistic, as most environments encountered in practice are either partially observable, or require function approximation that restricts the agent to access non-Markovian state features. We consider the problem of learning an optimal reactive policy in a finite environment with deterministic observations (or equivalently, hard state aggregation). We introduce a new algorithm, Committed Q-learning, and prove almost-sure convergence to the optimal reactive policy under an intuitive assumption we call rewire-robustness. This assumption is strictly weaker than the q⋆-realizability condition used in prior work. Our algorithm is a variant of classical Q-learning in which the behavior policy commits to a single action upon entering a feature, and only resamples actions when the observed feature changes. A crucial part of our analysis is the introduction of quasi-Markov environments.
Onno Eberhard, Claire Vernade, Michael Muehlebach
Max Planck Institute for Intelligent Systems, Tübingen, Germany · University of Tübingen · University of Technology Nuremberg.