- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies solving a specially structured Stackelberg optimization problem, where the leader's objective is not directly accessible and only queried through pairwise preferences. The authors' approach to the problem is simultaneous learning of the leader's optimal action and the underlying preference parameter. An iterative algorithm is designed and its sublinear regret bound is established (assuming that a subroutine solves the lower-level game to a satisfactory precision).
Critical strengths
I find the perspective and formulation of the paper somewhat interesting -- we would like to solve Stackelberg games without evaluating the exact leader's objective -- though I struggle seeing concrete applications where this setting naturally arises. The algorithm developed is easy to make sense of and it is good that the authors establishes a formal regret guarantee.
Critical weaknesses
On the negative side, I have a few serious concerns on the technical novelty and claimed contributions.
-
The authors formulate a Stackelberg game with followers. However, the structure of the lower-level game (among the followers) given a fixed leader plays no role in the algorithm design and analysis, which defeats the purpose of introducing the -player game setup in the first place. I think a more accurate description of the paper is Stackelberg optimization with a lower-level best response that can be approximately queried.
-
Regarding Assumption 2.5 and relating to the first comment, a major challenge of (Stackelberg) multi-agent game is assumed away. Except for in simple settings (like two-player zero-sum games), it is unrealistic to query an oracle that solves the lower-level game to an approximate Nash equilibrium. Looser solution notions such as (coarse) correlated equilibrium more be more feasible, but are incompatible with the analysis of the paper.
-
The regret analysis seems to involve limited technical novelty. The important intermediate results building up the regret bound are Lemmas 3.1-3.3. To my best knowledge, Lemma 3.1 follows immediately from the assumed lower-level solution precision, and Lemmas 3.2 and 3.3 follow from existing tools in kernel ridge regression and logistic maximum likelihood literature (possibly extended to the setting of noisy observations).
-
The numerical results are not very meaningful. While it is good to see that regret scales with , matching our expectation, the experiments do not touch on some important questions one would naturally have on the formulation and algorithm. For example, 1) what is the gap of regret between learning on preference feedback using the proposed algorithm versus learning when we observe the leader's objective exactly? 2) how does the proposed algorithm compare with alternative methods in the pairwise-feedback setting and full-information setting?
Questions for authors
I would appreciate the authors' response and clarification regarding the comments I raised in the section above. I additionally have the following question.
Regarding Definition 2.4, I believe there is a mismatch between the definition and the interpretation of the definition in line 136-137. We should distinguish between two definitions of equilibrium/optimal solution. The first is , and the second is . The second is more naturally described as a point at which the leader has no incentive to unilaterally deviate, while the first is where the leader maximizes its objective anticipating the best response from the followers.
2 comments
4. Numerical comparisons: We added five baselines in Section 4 (Figure 3) and Appendix F.5 (Table 3): GP-LCB observing scalar cost , our algorithm with known weights , preference-only MaxMinLCB and MultiSBM, and random exploration. All use the same carbon-tax market, lower-level solver and regret metric over rounds and 10 seeds. Our cumulative regret is , compared with and for full-information benchmarks, and for preference-only methods, and for random exploration. This is approximately 58% lower than preference-only learning and 33 times lower than random exploration, while quantifying the cost relative to two full information baselines. We acknowledge that this stylized five-firm, three-dimensional example does not establish scalability or superiority under identical feedback, but rather provides empirical evidence that the proposed learning framework offers meaningful advantages over naive exploration and existing preference-only methods, even in this relatively low-dimensional setting.
5. Definition 2.4: We agree that the original explanation was imprecise. We have clarified that the leader cannot lower its cost by deviating while anticipating the followers' re-equilibration. This matches the stated Stackelberg optimality condition and leaves the analysis unchanged.
We thank the reviewer for the careful assessment. We have clarified the role of the follower game, the approximation assumption and the technical contributions, expanded the experiments, and revised Definition 2.4's explanation.
1. Role of the multi-follower game: We agree that the algorithm does not use individual follower utilities. However, this follower-agnostic formulation is deliberate and follows the setting of Maheshwari et al. (2024) and Maddux et al. (2025), where the leader observes outcomes without knowing the followers' private incentives. From a modeling perspective, we believe this follower-agnostic framework is particularly relevant to applications such as carbon-tax design, congestion pricing, and electricity markets, where regulators lack access to participants' private objectives. However, the lower-level game's structure plays an important role in several parts of our analysis. Assumptions 2.2–2.3 guarantee a unique Nash equilibrium (NE) and a well-defined response map x⋆(π); Assumption 2.5 quantifies follower adaptation error, whose constants enter Theorem 3.5. Propositions B.1–B.2 relate regularity of the equilibrium-induced objectives to the underlying game, including its strong monotonicity. Finally, Corollary 3.6 exploits the Lipschitz continuity of follower utilities to certify approximate NE.
2. Lower-level approximation and correlated equilibria: We acknowledge that an approximate NE oracle may be unrealistic in general games. However, our framework considers strongly monotone follower games, where suitable decentralized learning dynamics admit convergence guarantees under additional regularity conditions (Bravo et al., 2018; Drusvyatskiy et al., 2022). Importantly, the "oracle" represents the followers' own adaptation following each leader intervention, rather than the leader explicitly solving their game. The convergence guarantees of these dynamics are consistent with the approximation requirement of Assumption 2.5, without requiring the leader to know the followers' private utilities.
Regarding correlated equilibria, Proposition 5 of Ui (2008) shows that in smooth games with strictly monotone payoff gradients, the unique correlated equilibrium is concentrated on the unique NE. Since our strong monotonicity assumption implies this, exact correlated equilibria introduce no additional modelling flexibility. Nevertheless, we acknowledge that this equivalence does not directly extend to approximate or coarse correlated equilibria. Establishing corresponding approximation guarantees and adapting our learning framework to these alternative solution concepts would require additional analysis and constitutes an interesting direction for future research.
Reference: Ui, T. (2008). Correlated equilibrium and concave games. International Journal of Game Theory, 37(1), 1–13. https://doi.org/10.1007/s00182-007-0098-x
3. Technical novelty: Our closest references are the follower-agnostic Stackelberg learning frameworks of Maheshwari et al. (2024) and Maddux et al. (2025), which rely on direct observations of the leader's scalar cost, whereas standard preference-bandit methods assume known comparison features. In contrast, our leader neither observes its scalar cost nor can freely select comparison pairs with known feature differences. Instead, preferences compare consecutive outcomes induced by an unknown follower game, observed only at approximate Nash equilibria. This creates a technical challenge absent from both lines of work. Standard preference-bandit analyses control cumulative uncertainty using realized comparison vectors determined by the selected actions. Here, however, the leader selects policies using predicted comparisons ut(π)=μ~t−1(π)−μ~t−1(πt−1), while the realized comparisons Δt=f~t−1−f~t become available only after the followers respond. These generally differ because the equilibrium-induced objective maps are unknown and follower responses are inexact. Consequently, combining existing estimators does not itself establish optimism or permit direct application of standard elliptical-potential bounds, which rely on realized comparisons. Our main contribution is an optimistic learning rule and a regret analysis that bridges this gap between predicted and observed comparisons, specific to our information structure. Namely, Proposition 3.4 establishes optimism by jointly accounting for uncertainty in the unknown trade-off and equilibrium-induced objectives. Theorem 3.5 controls the discrepancy between predicted and realized comparisons, enabling cumulative regret bounds while explicitly capturing its interaction with objective-estimation and follower-approximation errors. Finally, Corollary 3.6 provides a computable finite-time certificate for extracting an ε-Stackelberg equilibrium without the scalar-cost observations typically required by existing methods.