Learning Rewards in Strategic Games

Antoine Bergerault; Cyrille Kone; Giorgia Ramponi

cs.GTOct 15, 2026

Learning Rewards in Strategic Games

Authors: Antoine Bergerault, Cyrille Kone, Giorgia Ramponi

Organizations: ALPI Lab, University of Zurich

Abstract

Understanding the objectives that drive agents' behavior is crucial in strategic environments, where multiple agents interact and adapt to one another. This challenge arises in domains such as cybersecurity, autonomous driving, and online markets, where agents' underlying incentives are typically unknown and must be inferred from their observed behavior. Inverse reinforcement learning (IRL) provides a natural framework for this problem, but extending IRL to strategic multi-agent settings introduces a fundamental challenge: a reward that explains observed behavior does not necessarily induce optimal strategies when used for decision-making. In this work, we study this problem through the lens of strategic identifiability, and show that learning from a fixed policy pair can be insufficient to strategically identify rewards, independent of the number of expert samples $K$ . Motivated by this, we introduce an active IRL algorithm for two-player repeated Stackelberg games, in which the leader adaptively selects policies to elicit informative responses about the follower's reward. Combining maximum-likelihood estimation with experimental design, we derive finite-sample guarantees on the Stackelberg sub-optimality induced by the learned reward, matching up to polylogarithmic factors a new minimax learning rate of $K^{-1/2}$ . Finally, we evaluate our approach in a realistic anti-poaching setting, demonstrating the benefits of active exploration for reward recovery and downstream strategic performance.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of the impact of a poacher reward error on downstream tasks in a wildlife preservation setting. At deployment, a small error in reward estimation can lead to highly sub-optimal behavior from a rational patrol.

w\in\argmin_{\tilde{w}\in\Delta(\mathcal{A})}\max_{a\in\mathcal{A}}\tr\left(W(\tilde{w})^{\dagger}\mathcal{I}_{\delta_{a}}(0)\right),\quad\text{s.t.}\quad\Image\mathcal{I}_{\delta_{a}}(0)\subseteq\Image W(\tilde{w})\ \ \forall a\in\mathcal{A},

(16)

Algorithm 1 Active Stackelberg IRL for two-player normal-form games

Panel of Figure 2 — Figure 2: Mean $\operatorname{SubOpt}$ with the number of poacher actions. 95% CIs over 50 seeds.

Panel of Figure 3 — Figure 3: Patrol coverage and associated mean $\operatorname{SubOpt}$ across downstream tasks. Trained on 1,600 poacher actions. Darker map cells indicate greater coverage; the triangle marks the ranger base.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

\argmin_{\tilde{w}\in\Delta(\Pi_{\mu})}\max_{\mu}\max_{b\in\mathcal{B}}\left\lVert g_{\mu}(b)\right\rVert_{V(\tilde{w}),*}^{2},

(88)

Appendix

Algorithm 2 Warm-up procedure (WARM)

Panel of Figure 4 — Figure 4: Rewards, patrols, and poacher behavior in the Lobéké environment. The 23 accessible poaching targets are embedded in a $5\times 5$ park grid, darker cells indicate larger concentration, and the triangle marks the ranger base.

Panel of Figure 5 — Figure 5: Target and transfer diagnostics as a function of the number of observed poacher actions. We evaluate the algorithms across $50$ distinct seeds.

Panel of Figure 6 — Figure 6: Transfer SubOpt by the downstream value gap of the true source-optimal leader policy. Cells average results for tasks in their respective bucket, each forming exactly $1/3$ of the tasks. Averaged over $50$ seeds.

Panel of Figure 7 — Figure 7: Illustrative patrol policies for diverse tasks. Algorithms with logit-response and fixed-expert assumptions. Illustrations of the learned policies for different leader rewards. Averaged over $50$ seeds, reporting mean target and final SubOpt. w/ is for the performance when using warm-up.

Panel of Figure 8 — Figure 8: Joint selection of the warm-up budget and information multiplier for Active IRL after 1,600 observed poacher actions. Means computed over $100$ fixed tuning tasks and $32$ paired seeds. We use an MLE ridge of $10^{-6}$ for speed and stability (same as in the evaluation pipeline).

Panel of Figure 9 — Figure 9: Target metrics in the sparse-information game. Averaged over $100$ seeds.

Panel of Figure 10 — Figure 10: Empirical scaling on the minimax hard instance. We use $16$ independent seeds per coordinate and report the maximum sub-optimality mean over all coordinates.

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,717 papers

Stackelberg POMDP: Learning to Lead via Reinforcement Learning
Oct 7, 2022Matthias Gerstgrasser, Gianluca Brero, Alon Eden +6Game-Theoretic RL Reinforcement Learning
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 +2
Learning in Structured Stackelberg Games
Apr 11, 2025Maria-Florina Balcan, Kiriaki Fragkia, Keegan HarrisGame Theory Stackelberg Games
Carnegie Mellon University, Pittsburgh, USA · University of California, Berkeley, USA
Collaborating in Multi-Armed Bandits with Strategic Agents
May 13, 2026Idan Barnea, Ofir Schlisselberg, Yishay MansourMulti-Armed Bandits Mechanism Design
Tel Aviv University · Google Research

Oct 7, 2022J/K move · Enter open · S save

Stackelberg POMDP: Learning to Lead via Reinforcement Learning

Matthias Gerstgrasser, Gianluca Brero, Alon Eden, Darshan Chakrabarti+5

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+2

Game-Theoretic RL Reinforcement Learning Multi-Agent Reinforcement Learning Partially Observable Markov Decision Processes Mechanism Design

Open paper AskPDF arXiv

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.

Abstract

Reinforcement Learning

Explore similar work

Stackelberg POMDP: Learning to Lead via Reinforcement Learning

Learning in Structured Stackelberg Games

Collaborating in Multi-Armed Bandits with Strategic Agents