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
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.
Algorithm 1 Active Stackelberg IRL for two-player normal-form games
Figure 2: Mean SubOpt with the number of poacher actions. 95% CIs over 50 seeds.
Figure 3: Patrol coverage and associated mean 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
argminw~∈Δ(Πμ)maxμmaxb∈B∥gμ(b)∥V(w~),∗2,
(88)
Appendix
Algorithm 2 Warm-up procedure (WARM)
Figure 4: Rewards, patrols, and poacher behavior in the Lobéké environment. The 23 accessible poaching targets are embedded in a 5×5 park grid, darker cells indicate larger concentration, and the triangle marks the ranger base.
Figure 5: Target and transfer diagnostics as a function of the number of observed poacher actions. We evaluate the algorithms across 50 distinct seeds.
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.
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.
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).
Figure 9: Target metrics in the sparse-information game. Averaged over 100 seeds.
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 studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
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.
Matthias Gerstgrasser, Gianluca Brero, Alon Eden +6
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
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 collaborative learning in multi-agent Bayesian bandit problems, where strategic agents collectively solve the same bandit instance. While multiple agents can accelerate learning by sharing information, strategic agents might prefer to free-ride and avoid exploration. We consider a setting with persistent agents that participate in multiple time periods. This is in contrast to most previous works on incentives in multi-agent MAB, which assume short-lived agents, namely each agent has a single decision to make and optimizes their expected reward in that single decision. As in the multi-agent MAB model with incentives, our model does not have monetary transfers, and the only incentives are through information sharing. We propose CAOS, a mechanism that sustains collaboration as a Nash equilibrium while achieving strong regret guarantees. Our results demonstrate that collaborative exploration can be sustained purely through information sharing, achieving performance close to that of fully cooperative systems despite strategic behavior.