acceptodds
Under review as a conference paper at ICLR 2027

Learning Rewards in Strategic Games

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 on the number of expert samples . 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 . Finally, we evaluate our approach in a realistic anti-poaching setting, demonstrating the benefits of active exploration for reward recovery and downstream strategic performance.

Primary area:
reinforcement learning
Keywords:
inverse reinforcement learning, multi-agent, stackelberg games

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_qRThOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies inverse reward learning in two-player Stackelberg games, focusing on recovering rewards that support effective downstream strategic decision-making rather than exact reward identification. The authors first establish the limitations of learning from a fixed policy and derive a minimax lower bound on Stackelberg sub-optimality. They then propose an active IRL algorithm that combines maximum-likelihood reward estimation with Fisher-information-based experimental design. Under linear reward parametrization and entropy-regularized follower responses, the algorithm achieves a finite-sample sub-optimality guarantee with an optimal O(K−1/2)O(K^{-1/2}) dependence on the number of online interactions. Experiments on an anti-poaching benchmark and synthetic games demonstrate improvements in reward learning and downstream strategic performance.

Critical strengths

S1. Well-motivated problem formulation. The paper focuses on learning rewards that preserve strategic performance rather than exactly recovering the true rewards. The impossibility result for fixed-policy observations also provides a clear motivation for active exploration.

S2. Solid theoretical contributions. The paper connects reward estimation, Fisher information, and Stackelberg sub-optimality through the reward transfer lemma. The analysis is technically interesting, particularly the use of self-concordance and experimental design.

S3. Finite-sample guarantees. The authors establish both upper and lower bounds on Stackelberg sub-optimality, matching the O(K−1/2)O(K^{-1/2}) rate up to logarithmic factors. This provides theoretical support for the proposed active learning approach.

S4. Encouraging experimental results. The experiments show improvements over random exploration baselines, especially when transferring the learned rewards to different leader objectives. The additional synthetic experiments help illustrate the benefits of active exploration.

Critical weaknesses

W1. Gap between theoretical bounds and practical sample complexity. The upper and lower bounds match in their dependence on KK, but not on the dimension dd. Moreover, the theoretical warm-up requires exponentially many samples in ηS\eta S, while the experiments use much smaller warm-up budgets. Can the authors clarify the total sample complexity, including the warm-up phase? Is the exponential dependence on ηS\eta S necessary, and can the dimensional gap between the upper and lower bounds be improved?

W2. Computational complexity. The algorithm requires optimizing the Fisher-information-based objective over leader policies at each iteration. Since this optimization is generally nonconvex, it is unclear how efficiently it can be solved and whether approximate solutions preserve the theoretical guarantees. How is the online information-maximization problem solved in practice? Can the theoretical guarantees accommodate approximate optimization?

W3. Strong modeling assumptions. The analysis assumes known linear reward features and exact entropy-regularized follower responses. The experiments also follow these assumptions, leaving the robustness of the method under model misspecification unclear. How sensitive is the method to misspecification of the reward features or the follower's softmax response model?

W4. Limited comparisons with informed exploration methods. The experiments mainly compare the proposed method with random exploration and fixed-expert baselines. Comparisons with other active exploration strategies would better establish the advantage of the proposed information criterion. How does the proposed exploration criterion compare with existing active inverse learning approaches, particularly Chen et al. (2025)? Is the main novelty methodological or primarily theoretical?

W5. Ambiguity in the experimental setup. In Appendix H.1, the source leader reward is defined as r1=−r2r_1=-r_2. However, the Stackelberg planning problem ordinarily assumes that the leader's own reward is known. If this reward and the zero-sum relation are both available to the learner, the follower's reward would already be determined. What information about the leader's reward and the zero-sum relationship is available to each algorithm in the experiments? How is the unknown follower reward assumption maintained?

Questions for authors

Please addresses my questions in the weaknesses part.

3 comments
AuthorsOpenReview ↗

Response to the reviewer 1/2

We thank the reviewer for the time and effort spent on our paper, and for the positive assessment of the problem formulation, of the reward transfer analysis and of the experiments. We answer each weakness below. Some points were also raised by the other reviewers, and we refer to the corresponding answers where relevant.

W1: Gap between the bounds, and sample complexity.

Dimension. The reviewer is right: our bounds match in KK, not in dd. The upper bound scales as d⋄d\sqrt{d^\diamond d}, where d⋄≤dd^\diamond \le d is the dimension of the reward directions the follower can distinguish (Appendix B.1), against d\sqrt{d} in Theorem 1. Reviewer 7s1s raised the same point, and we have restricted our optimality claim to the rate in KK (see our answer to their Q2). We do not know yet which of the lower and upper bounds is loose.

Total sample complexity. Including the warm-up, reaching SubOpt⁡≤ϵ\operatorname{SubOpt} \le \epsilon requires

N=nwarm+K=O~(ηSe2ηS∣B∣d2log⁡δ−1)+O~(Rmax⁡2 d⋄(d(1+ηS)+log⁡δ−1)ϵ2)N = n_{\text{warm}} + K = \tilde{O}\left(\eta S e^{2\eta S}|\mathcal{B}|d^2\log\delta^{-1}\right) + \tilde{O}\left(\frac{R_{\max}^2\, d^\diamond\left(d(1+\eta S) + \log\delta^{-1}\right)}{\epsilon^2}\right)

interactions. The exponential term is a burn-in that does not depend on ϵ\epsilon: this is what our two-phase design buys, compared for instance to Wu et al. (2022), where the analogous factor multiplies ϵ−2\epsilon^{-2} (see our answer to Reviewer 7s1s, Q1).

Is the exponential necessary? Such a dependence is standard when inverting a logistic model, and corresponds to the constant κ\kappa of the logistic and GLM bandit literature [1-3]. We do not have a lower bound showing that it is necessary in our setting. In practice it is conservative: the theorem covers all rewards with ∥ω∥2≤S\|\omega\|_2 \le S, while Figure 2 shows that our algorithm performs well with a much smaller warm-up, or none (using λ>0\lambda > 0).

W2: Computational complexity and approximate optimization.

The warm-up design is a convex problem, solved by Frank-Wolfe up to a certified factor 1+ϵ1+\epsilon that is already accounted for in our analysis (Appendix E). The online selection rule is indeed non-convex in general. In our experiments, we solve it with SLSQP up to a tolerance.

Our guarantees extend to approximate solutions. Let Explore⁡k(μ):=Trace⁡(Gk−1†(ω^k−1on)Iμ(ω^k−1on))\operatorname{Explore}_{k}(\mu) := \operatorname{Trace}(G_{k-1}^{\dagger}(\hat\omega^{\text{on}}_{k-1})\mathcal{I}_{\mu}(\hat\omega^{\text{on}}_{k-1}))

be the objective at iteration kk. The selection rule is used at a single step of the proof (l. 1972), as Explore⁡k(μ~)≤Explore⁡k(μkon)\operatorname{Explore}_k(\tilde\mu) \le \operatorname{Explore}_k(\mu^{\text{on}}_k). Therefore:

  • if the solver is α\alpha-approximate, i.e. Explore⁡k(μkon)≥αsup⁡μExplore⁡k(μ)\operatorname{Explore}_k(\mu^{\text{on}}_k) \ge \alpha \sup_{\mu} \operatorname{Explore}_{k}(\mu) for some α∈(0,1]\alpha \in (0,1], the bound of Theorem 3 holds up to a factor 1/α1/\sqrt{\alpha};
  • if it is ϵk\epsilon_{k}-optimal, i.e. Explore⁡k(μkon)≥sup⁡μExplore⁡k(μ)−ϵk\operatorname{Explore}_{k}(\mu^{\text{on}}_{k}) \ge \sup_{\mu} \operatorname{Explore}_{k}(\mu) - \epsilon_{k}, the bound of Theorem 3 acquires the additive term O~(Rmax⁡dηS+log⁡δ−1+dK∑k=1Kϵk)\tilde{O}\left(R_{\max}\sqrt{\frac{d\eta S + \log\delta^{-1} + d}{K}\sum_{k=1}^K \epsilon_{k}}\right).

W3: Modeling assumptions and misspecification.

Linear rewards with known features and entropy-regularized responses are common assumptions in this literature, including in the works discussed in W4. Our analysis does not cover misspecification, we can however provide two partial answers:

  • A fixed but unknown temperature is handled as is, since the model only depends on the product ηω\eta\omega.
  • For the features, any reward is linear in the canonical features with d=∣A∣∣B∣d = |\mathcal{A}||\mathcal{B}| (Remark 1), so that misspecification can always be traded for a larger dimension.

To test the robustness of our interactive protocol with misspecification, we added a subsection H.4 to the Appendix of the new revision of the paper, testing the senstivity of our algorithm to misspecifications of the follower's response.

AuthorsOpenReview ↗

Response to the reviewer 2/2

W4: Comparison with informed exploration methods, and nature of the novelty.

The novelty is both methodological and theoretical, the main part being theoretical. Compared to Chen et al. (2025), the closest work in terms of exploration:

  • Algorithm. Their rule selects the action maximizing a design criterion of the Fisher information at the current MLE. Ours weights the Fisher information by the cumulated information GkG_k, hence accounts for the directions already explored, and is preceded by an optimal design warm-up.
  • Theory. Their guarantees are asymptotic (asymptotic normality of the MLE [4]) and require exact identifiability of the reward and a positive definite Fisher information. Ours are finite-sample, which Chen et al. (2025) left as an open question, and require neither of the aforementioned assumptions: we only need strategic identifiability, and bound the sub-optimality of the leader over a range of downstream tasks, with a lower bound matching in KK.

A comparison with other works, including Wu et al. (2022) and Chen et al. (2023), is given in our answer to Reviewer 7s1s (Q1). Additionally, the revision of the paper added new comparisons of our algorithm with baselines from Wu et al. (2022) and Chen et al. (2025), in Appendix H.1.1.

W5: Experimental setup and the zero-sum relation.

We emphasize that the follower's reward is unknown to all algorithms in our benchmarks, and our algorithm uses neither the leader's reward nor the zero-sum relation during training: its selection rule only depends on the Fisher information of the follower's responses. The relation r1=−r2r_1 = -r_2 is used for two purposes only:

  • to define the expert of the fixed-expert baselines, and to allow the Zero-sum OLS baseline (Liao et al., 2025), which is the only method that exploits the zero-sum structure;
  • to define the target task at evaluation, where the leader is optimized for (r1,r^2)(r_1, \hat r_2), with r1r_1 given as an arbitrary leader objective.

Our plots should therefore read as: given the estimate ω^\hat\omega, what sub-optimality does the leader incur when optimizing for a given task. The transfer metrics (Figure 3, Appendix H) use other leader objectives, for which the game is not zero-sum. We clarified this in Appendix H.1 of the new revision.

We thank the reviewer again for these comments, and are happy to discuss further.

[1] Faury, Abeille, Calauzènes, Fercoq, Improved optimistic algorithms for logistic bandits, ICML 2020.

[2] Abeille, Faury, Calauzènes, Instance-wise minimax-optimal algorithms for logistic bandits, AISTATS 2021.

[3] Lee, Yun, Jun, A unified confidence sequence for generalized linear models, with applications to bandits, NeurIPS 2024.

[4] Hoadley, Asymptotic properties of maximum likelihood estimators for the independent not identically distributed case, The Annals of Mathematical Statistics, 1971.

Thanks, my questions are well-addressed, and I choose to raise my score to 4.

Reviewer_7s1sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies active reward learning in repeated Stackelberg games with linear rewards and an entropy-regularized follower. It combines maximum-likelihood estimation with Fisher-information-based exploration and provides finite-sample guarantees on the leader’s downstream suboptimality.

Critical strengths
  • The focus on downstream strategic performance is meaningful.
  • The fixed-policy impossibility result motivates active exploration.
  • The connection between reward estimation, information geometry, and strategic decision error provides substantive theoretical value.
Critical weaknesses
  • The novelty relative to Wu et al. (2022) and Chen et al. (2023, 2025) needs sharper delineation. These works already cover closely related aspects of active Stackelberg learning, reward estimation, and downstream decision guarantees.
  • The stated expectation bound has better dimension dependence than the displayed high-probability bound. The claimed conversion and resulting minimax optimality require further justification.
Questions for authors
  1. What precise improvement does this work offer over the closest prior methods in assumptions, exploration design, or statistical guarantees?
  2. How does Theorem 3 imply the stated expected bound of O~(d/K)\widetilde O(\sqrt{d/K})? Does the minimax claim concern only the dependence on KK, or also on dd?
3 comments
AuthorsOpenReview ↗

Response to the reviewer 1/2

We thank the reviewer for the time and effort spent on our paper, and for the positive assessment of its focus on downstream strategic performance and of its theoretical value. The two points raised are well taken: we answer them below, and both led to clarifications in the revised version.

Q1: Comparison with previous work.

In short: compared to these works, we target a reward-free objective (a follower reward that yields low sub-optimality for any leader task), we provide hardness results for it (Lemma 2, Theorem 1), and we obtain finite-sample guarantees where the exponential dependencies only appear in an additive burn-in, thanks to a two-phase algorithm. We detail the comparison below, and will add it to the revised version.

1. Wu et al. (2022). Their queries are fixed in advance and their rate carries an exponential factor; ours are adaptive, and this factor is confined to the burn-in.

  • Their result. Building on the closed form of our Lemma 1, they query the mm pure leader strategies in a round-robin fashion (PURE) and invert the logits from empirical frequencies. This recovers the follower's utilities up to ϵ\epsilon after Θ(mlog⁡(mn/δ)/(ρϵ2))\Theta(m\log(mn/\delta)/(\rho\epsilon^2)) queries, where ρ\rho is the smallest probability of a follower action, so that 1/ρ1/\rho is exponential in the temperature in the worst case.
  • Ours. The analogous factor (∣B∣e2ηS|\mathcal{B}|e^{2\eta S}) only appears in our warm-up budget, not in front of the K−1/2K^{-1/2} rate. Our selection rule is adaptive, greedily choosing the most informative leader policy given the data, and our guarantee holds for any K≥1K \ge 1. It also handles the instances that motivate PURE-Exp, their randomized extension, for which no guarantee is given.
  • Setting. They assume tabular rewards, which we recover with d=mnd = mn (Remark 1), and their downstream guarantee requires an inducibility gap, which we do not assume.
  • In Appendix H.1.1, we added a new comparison of our algorithm with PURE.

2. Chen et al. (2023). This is the closest work in terms of tools (MLE and uncertainty quantification for a quantal follower), but it solves a different problem: regret minimization for a fixed, known leader reward.

  • Their result. For a leader acting through prescriptions in a Markov game, they prove regret and offline sub-optimality bounds under several selection schemes, without lower bounds. Their setting is more general than ours in that it covers Markov games and general function approximation.
  • Ours. We learn a follower reward that guarantees low sub-optimality for a whole family of leader tasks, with no leader reward during training. This notion of strategic identifiability comes with an impossibility result for fixed policies (Lemma 2) and a minimax lower bound (Theorem 1). They mention an identification impossibility informally, but neither of these results.
  • Techniques. Their schemes rely either on an optimization over reward confidence sets (Scheme 4), which requires an oracle and does not adapt to the reward-free case since the utilities vanish, or on a UCB-style bonus (Scheme 5), which adapts to our setting but leaves an exponential factor in front of the T\sqrt{T} term. We use a plug-in estimator, and remove this factor from the leading term with an initial optimal design phase, which their work does not consider.

3. Chen et al. (2025). Their exploration rule is the closest to ours (greedy design on the Fisher information), but their guarantees are asymptotic and require exact identifiability.

  • Their result. They prove consistency and asymptotic normality of the MLE, based on the classical theory for non-identically distributed observations. This requires regularity conditions, including the exact identifiability of the reward (their Assumption 5) and a positive definite Fisher information (their Theorem 3).
  • Ours. We provide finite-sample guarantees, which they leave open ("a theoretical analysis of its finite-time behavior is not yet provided and remains an open question"). We do so without assuming exact identifiability or positive definiteness: strategic identifiability is sufficient for downstream tasks, and our analysis is carried on the subspace of directions the follower can distinguish (of dimension d⋄≤dd^\diamond \le d).
  • Techniques. The finite-sample analysis is the main difficulty, and motivates our tools: self-concordance, optimal design, sequential confidence sets and an elliptical potential argument. Also, their selection rule depends on the data only through the current MLE, while ours weights the Fisher information by the cumulated information GkG_k.
  • In Appendix H.1.1, we added a new comparison of our algorithm with variants of the developed framework with A- and D-optimal design.
AuthorsOpenReview ↗

Response to the reviewer 2/2

Q2: Expected bound and minimax claim.

We thank the reviewer for this careful remark, which is correct. The expected bound O~(Rmax⁡d/K)\tilde{O}(R_{\max}\sqrt{d/K}) is a corollary of Theorem 3 with δ=1/K\delta = 1/K, in the regime where KK is large and dd is fixed, namely log⁡K≥d(1+ηS)\log K \ge d(1+\eta S). This is what we meant by "for sufficiently large KK".

In general, Theorem 3 with δ=1/K\delta = 1/K gives

E[SubOpt⁡ω(μ^)]≤O~(Rmax⁡d⋄(d(1+ηS)+log⁡K)K),\mathbb{E}\left[\operatorname{SubOpt}_\omega(\hat\mu)\right] \le \tilde{O}\left(R_{\max}\sqrt{\frac{d^\diamond \left(d(1+\eta S) + \log K\right)}{K}}\right),

where d⋄≤dd^\diamond \le d is the dimension of the reward directions the follower can distinguish (Appendix B.1). The dependence is therefore d⋄d\sqrt{d^\diamond d}, i.e. linear in the worst case, when log⁡K≤d(1+ηS)\log K \le d(1+\eta S), and d⋄\sqrt{d^\diamond} beyond. Compared to the lower bound of Theorem 1, this leaves a d\sqrt{d} gap in the first regime, and our minimax claim concerns the dependence on KK.

We have corrected this in the revision: the expected bound is now stated in the non-asymptotic form above with the explicit threshold, and the optimality claim is restricted to the rate in KK (as we also clarified to Reviewer qRTh). The theorems and their proofs are unchanged.

We thank the reviewer for the positive notes on the value of our work, and for the comments.

AuthorsOpenReview ↗

Follow-up on our rebuttal

Dear Reviewer 7s1s,

Thank you again for your time and feedback on our work.

As the discussion period is ending soon, we wanted to check whether our rebuttal has addressed your concerns. We have also uploaded a revised version of the paper that incorporates your feedback and that of the other reviewers (all changes highlighted in blue). In particular, the statement after Theorem 3 has been made more precise and transformed into a corollary whose short proof is given in the appendix. We also included comments on previous work given in our answer above. If any points remain unclear, we would be glad to provide further clarification.

If you find that our responses resolve the issues you raised, we would be grateful if you would consider updating your score accordingly.

Best regards, Authors

Reviewer_S8g3OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies active reward identification in two-player Stackelberg games. The leader repeatedly commits to mixed strategies and observes the responses of a boundedly rational follower, whose unknown reward function is assumed to be linear in known features. The follower responds according to an entropy-regularized best response. The authors introduce a notion of strategic identifiability, establish limitations of learning from fixed interactions, and propose an active learning algorithm combining maximum-likelihood estimation with optimal experimental design. They derive finite-sample Stackelberg suboptimality guarantees with near-optimal dependence on the number of observations and provide numerical experiments in an anti-poaching application.

Critical strengths

The paper addresses an interesting problem concerning the identification of opponents' objectives through strategic interactions. I particularly appreciate the distinction between recovering the underlying reward function and recovering sufficient information to make strategically effective decisions.

The theoretical analysis is substantial, including an impossibility result, a minimax lower bound, and finite-sample guarantees for the proposed algorithm. The experimental results also support the benefits of active information acquisition and are reported with confidence intervals.

Critical weaknesses

1- My main concern is that the leader actively selects strategies to identify the follower's reward, but these strategies also have consequences for the leader's own payoff. The proposed algorithm focuses on maximizing information acquisition and evaluates performance through the Stackelberg suboptimality of the final learned strategy. It does not account for the rewards or costs incurred during exploration. This distinction seems particularly important for the motivating applications, such as cybersecurity and anti-poaching, where exploratory actions may have serious consequences. I would expect some discussion of how the proposed approach balances information acquisition with the costs of strategic experimentation. The introduction mentions such a tradeoff, but it is not explicitly addressed by the proposed algorithm.

2 - The formulation assumes that the leader can commit to a potentially different mixed strategy at each interaction and that the follower responds according to its corresponding entropy-regularized best response. In classical security applications, Stackelberg models are motivated by an attacker who can observe or infer the defender's committed strategy. However, if the defender changes its strategy at every interaction, it is unclear how the attacker would learn or observe the new strategy before responding. Will there be repeated announcements to the attacker? Furthermore, the analysis assumes a stationary follower reward function and response model throughout the interactions. In applications such as cybersecurity and anti-poaching, the defender may encounter different attackers with different objectives over time. The implications of these assumptions for the proposed learning framework deserve further discussion.

3 - The entropy-regularized response model is central to the formulation, since it provides a unique softmax response whose probabilities contain information about the follower's reward differences. However, this important assumption is not mentioned in the abstract. It would also be useful to clarify what can and cannot be identified without entropy regularization. For example, observing deterministic best responses to suitably selected leader strategies may still reveal ordinal information about the follower's rewards, although not necessarily their magnitudes. Moreover, the follower does not follow a learning algorithm, and the model does not involve state-dependent sequential decision-making. The problem therefore appears closer to active inverse game theory or reward identification from quantal responses than to conventional inverse reinforcement learning. The relationship between these formulations should be explained more explicitly.

4 - The title is too general and does not reflect the specific focus on active reward identification in Stackelberg games with boundedly rational followers. The abstract should also communicate the main modeling assumptions more explicitly. Section 2.1 spends considerable space introducing regret and Nash-gap notions, although the actual problem concerns Stackelberg sub-optimality. I believe this discussion could be shortened to allow more emphasis on the proposed problem formulation and its motivation.

Questions for authors

1 - How should the costs incurred by the leader during reward identification be accounted for? Could the proposed framework accommodate an online exploration–exploitation objective rather than only terminal Stackelberg suboptimality?

2 - How does the follower observe the leader's committed mixed strategy at each interaction? How realistic is this assumption in the motivating security applications, particularly when the leader changes its strategy frequently?

3 - How sensitive is the approach to the assumption that the follower's reward function and response temperature remain fixed across interactions? What happens when different followers are encountered?

4 - What is the essential role of entropy regularization in strategic identifiability? How would the results change under deterministic best responses, and what if the follower's temperature is unknown?

6 comments
AuthorsOpenReview ↗

Response to the reviewer 1/3

We thank the reviewer for the time and effort spent on our paper, and for the positive assessment of the problem we study, in particular of the distinction between recovering the follower's reward and recovering enough information for strategic decisions. The questions raised concern the scope of our setting and the role of our assumptions: we answer them below, and they led to several clarifications in the revised version. References are listed below.

Q1: Costs incurred during identification, and online exploration-exploitation.

We recall that our goal is to learn a follower reward that can be reused: once r^2\hat r_2 is strategically identified, the leader can be re-optimized for any downstream objective r1r_1 without further interaction (Lemma 3 holds for every r1r_1, and Figure 3 illustrates this transfer). In our motivating applications, the leader's objective may be unknown or may change after training (e.g. new protected areas, new threat model), while the follower's incentives are the persistent quantity. We therefore do not assume a leader reward during training, and we measure the terminal Stackelberg sub-optimality.

We emphasize that not every application is adversarial, nor makes exploration costly. In electricity demand-response management, a provider (leader) commits to pricing policies and consumers (followers) adjust their consumption according to private preferences [1]. The provider may first seek to reduce peak demand, then prioritize renewable integration or carbon emissions, while the consumers' trade-off between cost and convenience remains stable. Learning these incentives in an initial exploration phase allows the provider to adapt its prices to each new objective, without experimenting on consumers again.

Moreover, the separation between an exploration phase and deployment is standard: it is the setting of reward-free exploration in RL and of (active) IRL [2, 3, 4], where the interaction cost is likewise not part of the objective. We agree this is a limitation when exploratory actions are costly.

That said, our approach can accommodate a trade-off when combined with a no-regret algorithm (e.g. Chen et al. (2023)) in a very naive explore-and-commit strategy. Splitting the KK online iterations in TT rounds of Active IRL (pure-exploration) followed by K−TK-T no-regret steps, one can guarantee sub-optimality of order O~(Rmax⁡d/T)\tilde{O}(R_{\max}d/\sqrt{T}) with high-probability on any leader objective (Theorem 3), while the regret is upper bounded by 2Rmax⁡T+Expl⁡(K−T),2R_{\max} T + \operatorname{Expl}(K-T), where Expl\text{Expl} is the regret of the second algorithm, typically of order K−T\sqrt{K-T}.

Theorefore, taking T≈KT \approx \sqrt{K} would induce a regret of order K\sqrt{K} while providing a transferable reward with sub-optimality of order K−1/4K^{-1/4}. Specifically, one can achieve, simultaneously for any downstream task DD and with high-probability,

\quad \text{and} \quad \frac{\operatorname{Regret}(K)}{K} \leq \mathcal{O}\left(\frac{R_{\text{max}}}{K^{1/2}}\right),$$ where $\hat{\mu}$ is any leader such that $\operatorname{SubOpt}_{\hat\omega^{\text{on}}_T}(\hat\mu) = 0$ for the task $D$. Other choices of $T$ trade off the cost of exploration against the quality of the transferable reward. We added a similar note as a new Appendix subsection F.3 of the new revision of the paper.
AuthorsOpenReview ↗

Response to the reviewer 2/3

Q2: How does the follower observe the leader's committed mixed strategy?

Observability of the commitment is an assumption of our analysis, not a requirement of the algorithm: Algorithm 1 only uses the sampled follower actions bkb_k, and can be run as is when the follower responds to an imperfect estimate of μk\mu_k. The entropy-regularized response (Assumption 2) is meant to absorb part of this imperfection, as it models a follower that is only soft-optimal, both in its own play and in its perception of the leader.

This is the standard modeling assumption in Stackelberg security games [5, 6]: the attacker conducts surveillance before acting and thereby learns the defender's mixed strategy, and boundedly rational (quantal response) attackers are the common model for human adversaries [7, 8]. It is also the assumption of repeated settings where the defender changes its commitment across rounds [9]. In the anti-poaching setting specifically, [10] relaxes exact observation by letting the attacker respond to a convex combination of the defender's recent strategies, which motivates the extension below.

On the theory side, the case raised by the reviewer can be handled by freezing the leader's policy over batches of BB rounds, so that the follower has time to observe the new commitment (and announcements are BB times less frequent). The greedy selection rule is then applied once per batch. In the analysis, this only changes the effective number of adaptive iterations from KK to K/BK/B: the bound of Theorem 3 holds with KK replaced by K/BK/B, i.e. we pay at most a factor B\sqrt{B}.

To illustrate this, we ran Algorithm 1 on our main anti-poaching application with the leader's policy frozen over batches of size B∈[1,4,16,64]B \in [1, 4, 16, 64], the greedy selection rule being applied once per batch. The figure can be found in Appendix H.4.1 of the new revision of the paper.

Q3: Sensitivity to a fixed follower reward and temperature; different followers.

We distinguish three cases, of increasing difficulty.

Fixed but unknown temperature. This case is handled by our approach as is. The follower's response (Eq. 3) depends on (η,ω)(\eta, \omega) only through the product θ=ηω\theta = \eta\omega, and so does the leader's downstream problem. The MLE therefore estimates θ\theta directly, the selection rule is invariant to η\eta for λ=0\lambda = 0 (the factor η2\eta^2 cancels in Trace⁡(Gk−1†Iμ)\operatorname{Trace}(G_{k-1}^{\dagger}\mathcal{I}_\mu)), and only an upper bound on ηS\eta S is needed, through the constraint set of the MLE and the warm-up budget.

Observed variation. If the temperature varies but is known to the leader, or if followers differ through a context observed before the leader commits (e.g. r2(a,b;c)=⟨ϕc(a,b),ω⟩r_2(a,b;c) = \langle \phi_c(a,b), \omega \rangle with a shared ω\omega), the log-likelihood remains concave in the shared parameter with the same exponential-family structure. The confidence sequence (Theorem 2) and the greedy selection rule then apply with the per-round features, and we expect the same guarantees with η\eta replaced by its largest value; only the warm-up design requires additional care, as it must account for the contexts.

Unobserved heterogeneity. If followers with different rewards are encountered without the leader knowing which one it faces, the model is misspecified and the problem changes in nature: there is no longer a single reward to identify, and the natural target becomes a distribution over follower types. Our guarantees do not cover this case. We could expect the MLE to converge to the best single-follower approximation of the population, with a sub-optimality that degrades with the level of heterogeneity, but we have no result to claim here. We see such a setting as an interesting direction for future work.

AuthorsOpenReview ↗

Response to the reviewer 3/3

Q4: Role of entropy regularization, deterministic best responses, unknown temperature.

Entropy regularization is the standard model of boundedly rational agents (quantal response [11], and its use for human adversaries in security games [7]), and as discussed in Q2 it also brings robustness to an imperfect perception of the leader. Its essential role in our analysis is twofold: it makes the follower's response smooth in the reward, so that (i) observations carry cardinal information on ω\omega through a likelihood, and (ii) an error on the reward translates continuously into a sub-optimality of the leader (Lemma 3).

Under deterministic best responses, both properties are lost. Observing bb in response to μ\mu only reveals that ω\omega lies in the cone {ω~:⟨ψμ(b)−ψμ(b′),ω~⟩≥0, ∀b′}\{\tilde\omega : \langle \psi_\mu(b) - \psi_\mu(b'), \tilde\omega \rangle \ge 0, \ \forall b'\}. As the reviewer notes, this is ordinal information: magnitudes are not identifiable, and information is only gained at the boundaries of the best-response regions, where the follower switches actions. The problem then becomes a geometric search for these boundaries with best-response queries [12, 13], which only recovers the best-response regions and is hard in the worst case: Peng et al. [13, Theorem 7] show that any algorithm needs 2Ω(m)2^{\Omega(m)} queries on some instance to compute the optimal strategy, where mm is the number of leader actions. Our approach does not apply to this regime, as the Fisher information vanishes. In a related setting with noisy reward feedback, Bai et al. [14, Theorem 1] show that any algorithm targeting the exact best-response value suffers a constant error with constant probability, for any sample size.

Finally, a fixed but unknown temperature is handled by our approach as is, since the model only depends on the product ηω\eta\omega (see Q3).

We thank the reviewer again for these comments, which helped us clarify the scope of our work. We hope these answers address the reviewer's concerns, and we are happy to discuss further.

References

[1] Kovács, Inverse optimization approach to the identification of electricity consumer models, Central European Journal of Operations Research, 2021.

[2] Lindner et al., Active exploration for inverse reinforcement learning, NeurIPS 2022.

[3] Wu et al., Inverse game theory for stackelberg games: the blessing of bounded rationality, NeurIPS 2022.

[4] Rolland et al., Identifiability and Generalizability from Multiple Experts in Inverse Reinforcement Learning, NeurIPS 2022.

[5] Tambe, Security and Game Theory, Cambridge University Press, 2011.

[6] Pita et al., Deployed ARMOR protection, AAMAS 2008.

[7] Yang et al., Improving resource allocation strategy against human adversaries in security games, IJCAI 2011.

[8] Nguyen et al., Analyzing the effectiveness of adversary modeling in security games, AAAI 2013.

[9] Balcan, Blum, Haghtalab, Procaccia, Commitment without regrets: online learning in Stackelberg security games, EC 2015.

[10] Fang, Stone, Tambe, When security games go green : Designing Defender Strategies to Prevent Poaching and Illegal Fishing, IJCAI 2015.

[11] McKelvey and Palfrey, Quantal response equilibria for normal form games, Games and Economic Behavior, 1995.

[12] Letchford, Conitzer, Munagala, Learning and approximating the optimal strategy to commit to, SAGT 2009.

[13] Peng, Shen, Tang, Zuo, Learning optimal strategies to commit to, AAAI 2019.

[14] Bai, Jin, Wang, Xiong, Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games, NeurIPS 2021.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the three reviewers for their time and their constructive comments. We are glad that the focus on downstream strategic performance, the impossibility result for fixed policies and the reward transfer analysis were found valuable. We answer each reviewer individually, and summarize here the main points.

  1. Scope of the minimax claim (Reviewers 7s1s, qRTh). Our upper and lower bounds match in KK, but not in the dimension: there is a d\sqrt{d} gap outside the regime log⁡K≥d(1+ηS)\log K \ge d(1+\eta S). We now state the expected bound in its non-asymptotic form, and restrict the optimality claim to the rate in KK. The short proof is added to Appendix F.2. The theorems and their proofs are unchanged.

  2. Comparison with prior work (Reviewers 7s1s, qRTh). We provide a detailed comparison with Wu et al. (2022) and Chen et al. (2023, 2025). In short, we target a reward-free objective, provide hardness results for it, and obtain finite-sample guarantees where the exponential dependencies only appear in an additive burn-in. We clarified this in the revision of the paper.

  3. Theorem 3 with an approximate selection rule (Reviewers S8g3, qRTh). The selection rule is used at a single step of the proof, so that the guarantee extends to approximate selection rules with an explicit additional term. This covers both an approximate solver and a leader trading off exploration with its own cost.

  4. Role of the assumptions (Reviewers S8g3, qRTh). We clarified the role of the observability of the commitment and of the entropy regularization, showed that a fixed but unknown temperature is handled as is, and stated the remaining cases (heterogeneous followers, misspecified features) as limitations.

  5. Experiments (all reviewers). We clarified the experimental setup, in particular that our algorithm uses neither the leader's reward nor the zero-sum relation during training. We added new experiments to the revision of the paper with comparisons to PURE and Chen et al. (2025) baselines, and robustness analysis of our method to batched leader policies and approximate follower's beliefs.

We hope these answers address the reviewers' concerns, and we are happy to discuss further. All changes made for the revision of the paper are added in blue.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.