acceptodds
Under review as a conference paper at ICLR 2027

Learning Stackelberg Equilibria from Preferences over Unknown Multi-Objective Trade-offs

Abstract

Interactions among self-interested agents often lead to socially inefficient outcomes. A central authority can counteract this by introducing incentives that steer agents toward more desirable outcomes, a setting naturally captured by a Stackelberg game in which the authority acts as the leader, the agents as followers, and the Stackelberg equilibrium characterizes the desired outcome. Defining what is “desirable”, however, typically requires trading off multiple, possibly competing objectives. While each objective may be easy to evaluate on its own, assigning numerical weights that reflect their relative importance and combine them into a single scalar cost is often difficult. Existing methods for solving Stackelberg games typically assume the leader observes this scalar cost directly. We instead consider a leader who does not know the trade-off parameter, but observes each objective's value at an approximate follower equilibrium and receives a pairwise preference between consecutive realizations. We jointly estimate the equilibrium-induced objective maps via kernel ridge regression and the trade-off parameter via logistic maximum likelihood, combining their confidence bounds in an optimistic action-selection rule. This yields a high-probability regret bound that captures the objective and trade-off estimation errors together with the inexactness of the followers' response. We establish conditions under which the resulting policy achieves no regret and further translate these guarantees into a finite-time criterion for extracting an -Stackelberg policy-response pair from the interaction history. The framework is validated in a carbon-tax design study, showing that the leader can recover a socially desirable policy despite inexactness in the followers' responses.

Primary area:
learning theory
Keywords:
Stackelberg games, learning in games, preference-based learning, multi-objective learning, no-regret learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GrdLOpenReview ↗
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.

  1. The authors formulate a Stackelberg game with NN 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 NN-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.

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

  3. 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).

  4. The numerical results are not very meaningful. While it is good to see that regret scales with εNE\varepsilon_{\rm NE}, 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 J(π⋆,x⋆)≤J(πˉ,x⋆(πˉ))+ϵJ(\pi^\star,x^\star) \leq J(\bar\pi,x^\star(\bar\pi))+\epsilon, and the second is J(π⋆,x⋆)≤J(πˉ,x⋆)+ϵJ(\pi^\star,x^\star) \leq J(\bar\pi,x^\star)+\epsilon. 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

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⋆(π)x^\star(\pi); 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)u_t(\pi)=\tilde\mu^{t-1}(\pi)-\tilde\mu^{t-1}(\pi^{t-1}), while the realized comparisons Δt=f~t−1−f~t\Delta^t=\tilde f^{t-1}-\tilde 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 ε\varepsilon-Stackelberg equilibrium without the scalar-cost observations typically required by existing methods.

4. Numerical comparisons: We added five baselines in Section 4 (Figure 3) and Appendix F.5 (Table 3): GP-LCB observing scalar cost JJ, our algorithm with known weights θ⋆\theta^\star, preference-only MaxMinLCB and MultiSBM, and random exploration. All use the same carbon-tax market, lower-level solver and regret metric over T=200T=200 rounds and 10 seeds. Our cumulative regret is 0.494±0.0190.494\pm0.019, compared with 0.212±0.0170.212\pm0.017 and 0.226±0.0160.226\pm0.016 for full-information benchmarks, 1.170±0.0931.170\pm0.093 and 1.161±0.0961.161\pm0.096 for preference-only methods, and 16.164±0.22216.164\pm0.222 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.

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

This paper studies online learning in Stackelberg games where the leader faces two unknowns: the follower's best-response function and the leader's own preferences over multiple objectives. The leader observes multi-objective outcomes and provides pairwise preference feedback to implicitly reveal a hidden scalar utility. The authors combine kernel ridge regression (to learn equilibrium maps) with Bradley-Terry preference learning (to estimate preference weights), proving a sublinear regret bound.

Critical strengths
  1. The problem formulation is well motivated. This setting is practically relevant for policy-making and mechanism design and has not been studied before.
  2. The main contribution is the sublinear regret bound that cleanly decomposes into three interpretable terms: preference uncertainty, equilibrium uncertainty, and follower suboptimality.
Critical weaknesses
  1. It seems to me the the algorithmic novelty is limited. The algorithm essentially runs two standard subroutines in parallel: GP-UCB for learning equilibrium maps and Bradley-Terry for preference learning. These components are decoupled in their updates and interact only through action selection. While the problem is novel, the solution does not demonstrate why this coupling is non-trivial or requires new algorithmic insights beyond applying both methods simultaneously.
  2. While the carbon-tax case study demonstrates the algorithm works in practice, it is a single stylized example with only five firms and a three-dimensional policy space. A simple baseline like sampling random leader policies at each turn would help understand whether the problem's complexity requires the proposed optimistic acquisition function, or whether the setting is simple enough that naive exploration suffices.
Questions for authors

Can you provide intuition or examples where naive combination of GP-UCB and Bradley-Terry fails or requires careful handling? If there are subtle interactions or technical challenges, please highlight them.

2 comments

We thank the reviewer for recognizing the relevance of the problem and the interpretability of our regret decomposition. We have clarified the algorithmic contribution and expanded the numerical evaluation.

1. Algorithmic novelty: We agree that kernel ridge regression (KRR) and logistic maximum likelihood are established estimators whose updates are performed separately. Our contribution is not a new estimation procedure, but an optimistic action-selection mechanism and regret analysis that couple these estimators under an information structure not covered by existing GP-bandit and preference-bandit methods. 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 analyses 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 distinction makes combining the two estimators non-trivial. The leader selects policies using predicted comparisons ut(π)=μ~t−1(π)−μ~t−1(πt−1)u_t(\pi)=\tilde\mu^{t-1}(\pi)-\tilde\mu^{t-1}(\pi^{t-1}), while the realized comparisons Δt=f~t−1−f~t\Delta^t=\tilde f^{t-1}-\tilde f^t become available only after the followers respond. These quantities generally differ because the equilibrium-induced objective maps are unknown and follower responses are inexact. Consequently, simply running the estimators in parallel does not establish optimism or yield a cumulative regret guarantee: the uncertainty governing action selection depends on predicted comparisons, whereas standard elliptical-potential arguments control realized comparisons used to update the preference estimator.

Our main technical contribution address this through: (I) Proposition 3.4 that first combines the two confidence bounds given by Lemmas 3.2 and 3.3 to establish optimism for the unobservable relative equilibrium cost gt(π)=J(π)−J(πt−1)g_t(\pi)=J(\pi)-J(\pi^{t-1}), explicitly accounting for inexact follower responses; (II) Theorem 3.5 that bridges predicted and realized comparisons, allowing standard elliptical-potential bounds to be used alongside kernel information-gain arguments while controlling the additional errors from estimating equilibrium-induced objectives and approximate follower equilibria; and finally (III) Corollary 3.6 that provides a computable finite-time certificate for extracting an ε\varepsilon-Stackelberg equilibrium without the scalar-cost observations typically required by existing methods.

2. Additional baselines: We addressed the concern about limited comparisons by adding five baselines in Section 4 (Figure 3) and Appendix F.5 (Table 3): GP-LCB with direct scalar-cost feedback on JJ, our method with known trade-off weights θ⋆\theta^\star, preference-only MaxMinLCB and MultiSBM, and random policy exploration. All are evaluated on the same carbon-tax game with the same lower-level solver and regret metric over T=200T=200 rounds and 10 seeds. Our cumulative regret is 0.494±0.0190.494\pm0.019, compared with 1.170±0.0931.170\pm0.093 (MaxMinLCB), 1.161±0.0961.161\pm0.096 (MultiSBM), and 16.164±0.22216.164\pm0.222 (random), whereas the full-information benchmarks achieve 0.212±0.0170.212\pm0.017 and 0.226±0.0160.226\pm0.016. Our method thus reduces regret by approximately 58% versus preference-only learning and by a factor of 33 versus random exploration, while incurring additional regret relative to two full information baselines. The final-20-round average regret is 1.40×10−31.40\times10^{-3} for our method versus 5.15×10−35.15\times10^{-3} for preference-only learning and 84.47×10−384.47\times10^{-3} for random exploration. We acknowledge that the carbon-tax application remains a stylized example with five firms and a three-dimensional policy space. Nevertheless, the new comparisons provide 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.

3. Why a naive GP-LCB + Bradley–Terry combination is insufficient: We recognize three particular scenarios where a naive combination could fail.

First, a naive GP-LCB plug-in scalar-cost acquisition ⟨θ~t−1,μ~t−1(π)⟩−Sqt−1(π)\langle\tilde\theta^{t-1},\tilde\mu^{t-1}(\pi)\rangle-Sq_{t-1}(\pi) could exploit an inaccurate trade-off estimate without exploring informative comparisons. Repeatedly selecting similar policies yields Δt≈0\Delta^t\approx0, so the preference information matrix VtV_t barely grows and the weight estimate may remain incorrect. Our bonus βt−1∥ut(π)∥Vt−1−1\beta_{t-1}\lVert u_t(\pi)\rVert_{V_{t-1}^{-1}} explicitly encourages informative relative outcomes. Second, preferences identify cost differences, not absolute costs. Therefore, a naive absolute bonus βt−1∥μ~t−1(π)∥Vt−1−1\beta_{t-1}\lVert \tilde\mu^{t-1}(\pi)\rVert_{V_{t-1}^{-1}}, could reward directions that are constant across policies and hence irrelevant to preferences. Moreover, the elliptical-potential bound applies to realized Δt\Delta^t, not absolute features. Our action selection mechanism based on optimistic lower confidence bound of the relative-cost gt(π)=J(π)−J(πt−1)g_t(\pi)=J(\pi)-J(\pi^{t-1}) aligns exploration with comparison geometry, and equations (36)–(38) control the gap between ut(πt)u_t(\pi^t) and −Δt-\Delta^t. Third, observations at approximate equilibria induce potentially biased, history-dependent errors, for which conventional zero-mean GP noise bounds (Srinivas et al., 2010; Chowdhury and Gopalan, 2017) are insufficient. Lemma 3.2 instead gives a deterministic KRR confidence bound controlled by the followers' approximation error.

References: Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. (2010). Gaussian process optimization in the bandit setting: No regret and experimental design. Proceedings of the 27th International Conference on Machine Learning (ICML), 1015–1022. https://arxiv.org/abs/0912.3995

Chowdhury, S. R., & Gopalan, A. (2017). On kernelized multi-armed bandits. Proceedings of the 34th International Conference on Machine Learning (ICML), 70, 844–853. https://proceedings.mlr.press/v70/chowdhury17a.html

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

This paper considers a Stackelberg game between a single leader and multiple followers. The leader’s cost function captures a tradeoff among multiple objectives as an unknown linear scalarization of a known set of performance objectives. Given a leader action, the followers aim to choose actions that form a Nash equilibrium.

Within the game setting, the paper studies a learning task for the leader. During iterative interactions with the followers, in each iteration, the leader chooses an action and induces an approximate Nash equilibrium from the followers. The leader observes numerical measurements of each performance objective realized at the followers’ actions, and queries an oracle for a pairwise comparison between the current and previous performance realizations. The leader aims to learn a Stackelberg equilibrium of the game. The authors propose a learning algorithm, which uses kernel ridge regression to estimate the equilibrium induced objective maps and logistic maximum likelihood to estimate the objective tradeoff parameters, and establish regret convergence guarantee of the algorithm under selected assumptions.

Critical strengths

The paper provides a comprehensive treatment of the problem. The extended problem setting is described in detail, then a learning algorithm is stated with careful theoretical regret analysis. The practical motivation is carried throughout: the introduction motivates the single-leader-multiple-follower Stackelberg equilibrium learning setting from practical examples, and the numerical study uses a carbon-tax incentive design to demonstrate the investigated setting and proposed algorithm.

Critical weaknesses
  1. One of the key modeling assumptions is not convincing: the paper assumes the leader does not know the tradeoff parameters, θ∗\theta^*, associated with the performance objectives. Why are these parameters treated as unknown? As the tradeoff reflects the leader’s views on the multiple objectives, I would expect the leader to know its own tradeoff weights.

  2. The novelty of the algorithm is unclear compared to related works: the algorithm adopts two existing estimation techniques to respectively handle the two unknown components. It is not clear how novel these applications are. On a related note, while the authors provide theoretical regret analysis, it is not clear whether the analysis involves extra challenges beyond standard regret analysis arising from the paper’s specific problem structure. Further explanation on what makes the algorithm design and analysis novel and interesting would be useful, especially considering that the paper discusses related works somewhat briefly and the numerical study does not have comparable baselines either (Appendix E.5 explains the reason for no baselines).

Questions for authors
  1. Is the proposed learning algorithm compatible with simplification on the leader objective, e.g., when the leader has a single objective, or when the leader knows its own tradeoff weights θ∗\theta^*? If the algorithm remains applicable, does the term (I) in regret bound (9) vanish in these simplification cases?

  2. What informs the choice of kernel ridge regression and logistic maximum likelihood as estimation techniques? If different estimation techniques are used, will regret analysis change?

2 comments

We thank the reviewer for the constructive comments. We have clarified the motivation, technical contributions, and estimator choices, and added comparative experiments.

1. Why are the trade-off weights unknown?: In applications we envision, such as regulatory policy design, the institution evaluating outcomes need not be the technical team choosing interventions. Decision makers may compare two outcomes without specifying numerical weights, especially when objectives have different units and normalizations. This motivates eliciting pairwise preferences, as in multi-attribute preferential optimization (Astudillo and Frazier, 2020; Lin et al., 2022) and learning from human feedback (Christiano et al., 2017). Importantly, the settings in which the weights are known represent a special case of our framework, requiring no preference learning.

2. Algorithmic/theoretical novelty and baselines: 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)u_t(\pi)=\tilde\mu^{t-1}(\pi)-\tilde\mu^{t-1}(\pi^{t-1}), while the realized comparisons Δt=f~t−1−f~t\Delta^t=\tilde f^{t-1}-\tilde 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 typically 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 θ⋆\theta^\star and equilibrium-induced objectives ff. 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 ε\varepsilon-Stackelberg equilibrium without the scalar-cost observations typically required by existing methods.

We also add five comparisons in Section 4 (Figure 3) and Appendix F.5 (Table 3): two full-information benchmarks (GP-LCB on JJ; our setup with known weights θ⋆\theta^\star), two preference-only methods (MaxMinLCB; MultiSBM), and random exploration. Across T=200T=200 rounds and 10 seeds, our cumulative regret is 0.494, versus 1.170/1.161 for preference-only methods and 16.164 for random exploration. Full-information benchmarks achieve 0.212/0.226. These results show the benefit of combining numerical feedback with preferences, while quantifying the cost of learning unknown weights.

3. Known-weight and single-objective cases: If θ⋆\theta^\star is known, the leader still needs to learn f(π)f(\pi) because follower equilibria are unknown, but can fix θ~t=θ⋆\tilde\theta^t=\theta^\star. Our acquisition rule can then be simplified to ℓtknown(π)=⟨θ⋆,μ~t−1(π)⟩−Sqt−1(π)\ell_t^{\mathrm{known}}(\pi)=\langle\theta^\star,\tilde\mu^{t-1}(\pi)\rangle-Sq_{t-1}(\pi). By Lemma 3.2 and the Cauchy–Schwarz inequality, ∣J(π)−⟨θ⋆,μ~t−1(π)⟩∣≤Sqt−1(π)|J(\pi)-\langle\theta^\star,\tilde\mu^{t-1}(\pi)\rangle|\le Sq_{t-1}(\pi), so optimism gives the sharper per-round bound rte≤2Sqt−1(πt)r_t^e\le2Sq_{t-1}(\pi^t), eliminating uncertainty at the previous policy that appears in Proposition 3.4 (C.1 previously). Following Theorem 3.5 yields RT≤2SBf+2SρCσmγTT+SLφT2CK−c/δR^T\le2SB_f+2S\rho\sqrt{C_\sigma m\gamma_T T}+SL_\varphi T\sqrt{2CK^{-c}/\delta}. Hence the trade-off term (I) and all βT\beta_T-dependent contributions disappear. We recover the single-objective case (m=1m=1) as a particular instance of the known-weights case for θ⋆=1\theta^\star=1, which reduces to ordinary kernel-based learning of its equilibrium-induced cost.

4. Why these estimators?: Since the follower equilibrium map is unknown and only approximate equilibria are observed, we use kernel ridge regression (KRR) to learn the equilibrium-induced objective maps in a nonparametric manner, without requiring a closed-form solution of the lower-level game. Crucially, KRR provides deterministic confidence bounds under bounded cumulative observation corruption, accommodating biased, history-dependent follower-approximation induced errors, unlike standard GP-UCB analyses that assume conditionally zero-mean sub-Gaussian noise (Srinivas et al., 2010; Chowdhury and Gopalan, 2017). Logistic MLE naturally matches the Bradley–Terry preference model and admits confidence bounds for adaptively generated comparisons (Lee et al., 2025; Schlaginhaufen et al., 2025).

Finally, our framework is not restricted to these estimators. Other alternatives could be incorporated provided they offer comparable confidence bounds and cumulative-uncertainty guarantees, although deriving explicit regret bounds may require additional analysis.

References: Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. (2010). Gaussian process optimization in the bandit setting: No regret and experimental design. Proceedings of the 27th International Conference on Machine Learning (ICML), 1015–1022. https://arxiv.org/abs/0912.3995

Chowdhury, S. R., & Gopalan, A. (2017). On kernelized multi-armed bandits. Proceedings of the 34th International Conference on Machine Learning (ICML), 70, 844–853. https://proceedings.mlr.press/v70/chowdhury17a.html

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We sincerely thank all reviewers for their careful evaluations and constructive feedback. In response, we have revised the manuscript to clarify the technical novelty and proof strategy, strengthen the discussion of the underlying assumptions, establish additional theoretical guarantees for important special cases, and substantially expand the numerical evaluation. The changes in the manuscript are marked in blue. We summarize the main changes below.

1. Clarifying the algorithmic and theoretical contributions (Section 3): We have revised the presentation of our optimistic acquisition function (7) to explicitly identify the exploration terms associated with uncertainty in the unknown trade-off parameter and equilibrium-induced objective maps. More importantly, we have substantially rewritten the opening of Section 3.1 to explain the technical challenge distinguishing our analysis from scalar-feedback Stackelberg learning (Maheshwari et al., 2024; Maddux et al., 2025) and standard preference-bandit methods.

2. New theoretical results for known trade-off weights (Appendix E): We have added a dedicated appendix analyzing the special case where the trade-off parameter is known, including the single-objective setting. In this case, preference learning is unnecessary, and the leader can construct an optimistic estimate of its scalar equilibrium cost directly. Proposition E.1 establishes a sharper instantaneous and cumulative regret bound, eliminating the preference-uncertainty term and all associated contributions involving the preference confidence radius in Theorem 3.5. Corollary E.2 further derives a simplified finite-time equilibrium recovery guarantee, with a computable certificate depending only on uncertainty in the equilibrium-induced objective maps.

3. Expanded numerical comparisons (Section 4 and Appendix F.5): We have substantially extended the carbon-tax study by adding five baselines, reported in the new Figure 3 and Appendix F.5 (Table 3): two full-information benchmarks (GP-LCB observing the scalar cost JJ and our method with known trade-off weights θ⋆\theta^\star), two preference-only methods (MaxMinLCB by Pásztor et al. (2024) and MultiSBM by Ailon et al. (2014)), and uniform random exploration. All methods are evaluated on the same five-firm carbon-tax market over 200 rounds and 10 random seeds, using the same lower-level solver and regret metric.

4. Clarifications of the lower-level game and equilibrium concept (Section 2): We have refined the discussion following Assumption 2.5 to explain how decentralized adaptation in strongly monotone follower games can satisfy the required approximation guarantee under suitable regularity conditions, without requiring the leader to know the followers' private utilities. We have also corrected the explanation accompanying Definition 2.4 to clarify that the leader evaluates deviations while anticipating the followers' re-equilibration. The structural role of the follower game is further supported by the existing results in Appendix B, which relate regularity of the equilibrium-induced objective maps to the underlying game through RKHS pullback and equilibrium sensitivity arguments.

We believe these revisions make the theoretical contribution and its relationship to existing approaches clearer, establish useful guarantees for important special cases, and provide a more informative empirical evaluation. We are grateful to the reviewers for their suggestions, which have helped us improve the manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.