Online Learning and Equilibrium Computation with Ranking Feedback
Authors: Mingyang Liu
Yongshan Chen
Zhiyuan Fan
Gabriele Farina
Asuman E. Ozdaglar
Kaiqing Zhang
Venue: ICLR 2026 Oral (2026)
Keywords: Online Learning
Equilibrium Computation
Human Feedback
Primary area: learning theory
TL;DR: Hardness and positive results for online learning with ranking feedback. Together with equilibrium computation with ranking feedback.

Abstract: Online learning in arbitrary, and possibly adversarial, environments has been extensively studied in sequential decision-making, and it is closely connected to equilibrium computation in game theory. Most existing online learning algorithms rely on \emph{numeric} utility feedback from the environment, which may be unavailable in human-in-the-loop applications and/or may be restricted by privacy concerns. In this paper, we study an online learning model in which the learner only observes a \emph{ranking} over a set of proposed actions at each timestep. We consider two ranking mechanisms: rankings induced by the \emph{instantaneous} utility at the current timestep, and rankings induced by the \emph{time-average} utility up to the current timestep, under both \emph{full-information} and \emph{bandit} feedback settings. Using the standard external-regret metric, we show that sublinear regret is impossible with instantaneous-utility ranking feedback in general. Moreover, when the ranking model is relatively deterministic, \emph{i.e.}, under the Plackett-Luce model with a temperature that is sufficiently small, sublinear regret is also impossible with time-average utility ranking feedback. We then develop new algorithms that achieve sublinear regret under the additional assumption that the utility sequence has sublinear total variation. Notably, for full-information time-average utility ranking feedback, this additional assumption can be removed. As a consequence, when all players in a normal-form game follow our algorithms, repeated play yields an approximate coarse correlated equilibrium. We also demonstrate the effectiveness of our algorithms in an online large-language-model routing task.

Published as a conference paper at ICLR 2026
ONLINE LEARNING AND EQUILIBRIUM COMPUTATION WITH RANKING FEEDBACK
Mingyang Liu', Yongshan Chen Zhiyuan Fan', Gabriele Farina', Asuman E. Ozdaglar', Kaiqing Zhang²
Massachusetts Institute of Technology
University of Maryland, College Park
3 Northeastem University
ABSTRACT
Online learning in arbitrary, and possibly adversarial, environments has been ex- tensively studied in sequential decision-making, and it is closely connected equilibrium computation in game theory. Most existing online learning algorithms rely numeric utility feedback from the environment, which may be unavailable in human-ing momnan-in-the-leee the-loop applications and/or may be restricted by privacy concerns. In this paper, we study an online learning model in which the learner only ob- serves a ranking over set of proposed actions at each timestep. We consider two ranking mechanisms: rankings induced by the instantaneous utility the current timestep, and rankings induced by the lime-average utility up to the cur- rent timestep, under both full-information and bundit feedback settings. Using the standard external-regret metric, show that sublinear regret is impossible with instantancous-ttili ranking feedback in general. Moreover, when the ranking model is relatively deterministic, i.e., under the Plackett-Luce model with tem- perature that is sufficiently small, sublinear regret is also impossible with time- average utility ranking feedback. We then develop sublinear regret under the additional assumption that the utility sequence has sub- linear total variation. Notably, for full-information time-average utility ranking feedback, this additional assumption can be removed. As consequence, when all players normal-fore game follow our algorithms, repeated play yields an approximate coarse correlated equilibrium. We also demonstrate the effectiveness of our algorithms an online large-language-modee routing task.
algorithms that achieve
INTRODUCTION
Online learning has been extensively studied model for sequential decision decision-making in arbi- trary and possibly adversarial environments (Shalev-Shwartz et al. [012] Hazan et al.] (016).. At each round, the agent commits to strategy, takes action, and then receives feedback from the environment, often in numeric form, such as the utility vector (in the full-information feedback set- ting) or the realized utility value (in the bandit feedback setting). Numerous algorithms achieve no-regret guarantees, i.e., they ensure that the agent's external regret grows sublinearly with time (Shaley-Shwartz et al., 2012: Hazan et al. (016). Moreover, online learning is closely connected to equilibrium computation in game theory: when all players employ no-regret learning in the re- peated play of normal-forn game (NFG), their time-average play approaches a coarse correlated equilibrium (CCE) (Cesa-Bianchi & Lugosi 2006).
However, numeric utility feedback may not always be available in real-world applications. For stance, when the feedback is elicited from an environment with humans in the loop, it is typically much easier for them to compare or rank candidate actions than to provide calibrated numerical scores. This phenomenon has been widely recognized and is exemplified by the success of rein- forcement learning from human feedback (RLHF) in fine-tuning language models (Ouyang et al. 2022). Moreover, even when well-defined numeric utilities exist, they may be inaccessible to the learning agent due to privacy or security constraints. As a concrete example, consider an online platform (see Figure T (a) that recommends commodities to a stream of customers over time, where

---

Published as a conference paper at ICLR 2026
t=2
Plalen d
Paslea
R
Piafern 6
Plaffona
8
%
(a) Online L earning
(b) Equilibrium Computation
Two examples of online learning and equilibrium computation with ranking feedback. In (a), an online platform recommends food options customer at each timestep and receives ranking over the proposed items, which it uses to improve recommendation quality. In (b), an online dating app recommends potential matches; users rank the suggested candidates, and the platform leverages these rankings to learn matching equilibria over time.
Figure 1:
customers arriving at different timesteps may have different preferences. While the platform aims to improve its recommendations, customers may be unable or unwilling to reveal their true valuations. Depending whether customers one-shot (arrive, rank, and leave forever) memory, the ranking feedback may be induced either by the instantaneous utility at each timestep or by the fime- time-average utility aggregated over historical utility vectors. The platform thus seeks to minimize the regrel of its recommendations under ranking-only feedback. Yet, the fundamental limits and algorithmic solutions for this online learning setting remain elusive.
long-lived with
Ranking feedback becomes particularly relevant game-theoretic settings, where multiple humans repeatedly interact, and the goal is compute an equilibrium of the underlying game. For example, consider an online dating platform that recommends potential matches (see Figure (b)). In each round, each user may provide only a ranking over the recommended candidates, and the platform aims to compute an equilibrium outcome, i.e., matching between users. that (approximately) re- spects everyone's 's preferences. Related scenarios arise in other matching platforms, e.g., ride-sharing services that match drivers and passengers based on their preferences, such drivers' preferences over trip lengths and riders' preferences over driving styles (e.g., punctuality or cautiousness). Al- though these applications may seem reminiscent of the classical stable matching model (Gale & Shapley 1962), our setting is fundamentally different. See Appendix for detailed comparison.
In this paper, we systematically study online learning and equilibrium computation with ranking feedback in a nonstochastic environment, where the loss vectors may be generated arbitrarily, and potentially even adversarially. This setting can also be viewed
generalization of the stochastic bandits with ranking feedback studied recently in Maran et al. (2024). See Appendix A for a detailed comparison. Our goal is to understand when regret minimization in this setting is possible, and to develop new algorithms that provide both regret-minimization and cquilbriun-appoximatio guarantees, We summarize our contributions as follows.
Contributions. We consider two types of ranking feedback, categorized by how the rankings generated: one based on the instantaneous utility at each timestep (InstUtil Rank), and one based on the time-average utility up the current timestep (AvgUtil Rank). We establish the following results: (i) sublinear regret is impossible under Inst Rank feedback. Moreover, under Avg Rank feedback, sublinear regret remains unattainable (up to logarithmic factors) when the ranking model is overly deterministic (i.e., when the temperature parameter > in (PL) is small); (ii) we propose new algorithms that achieve sublinear regret under an additional assumption that the utility vectors have sublinear variation; (iii) we show that this variation assumption can be removed under hull-information AvgUtil Rank feedback when 7 is a constant; and (iv) when all players run no-regret learning algorithms in the repeated play of normal-form game, the induced play yields an approximate coarse correlated equilibrium. Our contributions are summarized in Table]] [] We present application to wrrg-llanuagg-modde routing in Section g and provide experimental validation of our algorithms in Appendix
2 PRELIMINARIES
The basic notation and brief introduction normal-form games deferred Appendix B
2

---

Published as a conference paper at ICLR 2026
Lower Bound
Full- Inflomonfonnnnnnn (T(T) for r S (1)
Bandit
InstUtil Rank
AvgUtil Rank
((T) for S
Q(T) for r S
So
Tlog T
log T
Upper Bound
Full-Information
Bandit
(T (1), Sublinear Regret)
InstUtil Rank
Assumption
4.2
AvgUtil Rank
Assumption
4.2
Table I: Summary of our contributions, including the negative results (top) and the positive results (bottom). The bottom table lists the minimal assumptions required to achieve sublinear regret each setting (v indicates that additional assumptions are needed). Here, denotes the temperature parameter the ranking model in (PL).
2.1 ONLINE LEARNING
We study online learning in non-stochastic and potentially adversarial environment, where an agent interacts with the environment over multiple timesteps by selecting an action and receiving feedback at each timestep. The agent's action set finite and denoted as == {aa a......, a! with |A| > 1. At each timestep I, the agent commits to mixed strategy T(() E A In the classical online learning setting (with numeric feedback), with full-information feedback, the agent observes utility vector
(t) E 1]4; with bandit feedback, the agent observes only the realized utility for the sampled action (t) ~ x(1).
(0 (t)
The agent's goal is to minimize her (external) regret, defined the difference between her cumula- tive utility and that of the best fixed action in hindsight. Formally, for any integer T 0, the regret is defined as
R extteraa
max REAM
Σ
1 J (0)
(2.1)
Since our goal is minimize regret, and regret unchanged if the utility vector (t) is shifted by an additive constant at each timestep t, may assume without loss of generality that (alA())))) 0, Le., the last action always receives zero utility for any / E (7).
2.2 ONLINE LEARNING ALGORITIMS WITH NUMERIC FEEDBACK
Our main results later will be modular, in the sense that any standard online learning algorithm with (fullinformmtionn numeric feedback, including projected gradient descent (PGD), multiplicative- weights update (MWU), and Follow-The Teggleeglariieed-- Leader (FTRL) (Hazan al. 2016). can be used as deterministic black-box oracle in the algorithms we develop.
As preliminary, we formally define such deterministic oracles here. Let Alg: U (R-1)* A- denote an online learning algorithm, which can be viewed as a mapping from sequence of utility ==1 from timesteps through t, the algorithm outputs the next strategy (+++1) = Alg (= 2=1) to be played at timestep i 1. Note that this formulation implicitly assumes that Alg is deterministic. Finally, denote the (external) regret incurred by Alg as
vectors to distribution over the action set A. Thus, given utility vectors (u(*))²
R [TT) extterala (Alg, (wf)))² (
u 00 Alg (1)))
max FEAA
(2.2)
which can be made sublinear in I' for any sequence of utility vectors (u())T
Hazan et al, 2016
1=1
ONLINE LEARNING WITH RANKING FEEDBACK
In online learning with ranking feedback, each timestep f, the agent does not have direct access (*) nor the realized utility (the utility of the realized action at timestep t). Instead, timestep she can propose multiset (which may include repeated elements) of actions (!)) and receive
3

---

Published as a conference paper at ICLR 2026
(E(-) returns the set of all permutations) from the environment, representing a ranking of those actions in o!). In the full-information setting, oL*) A. i.e. the whole action set is proposed. In the bandit setting, |o! - K I |Al. Suppose the agent's strategy at timestep t is (1) E AA, then we assume that in this bandit setting, the actions in o(1) are proposed by sampling from T(*) independently (with replacement). This way, the empirical average of the
permutation o( E [o(
utilities will be an unbiased estimator of the expected utility, i.e., E Eecole (a)
(u()) x (T))..
We will adopt this proposal mechanism throughout the paper, which was also used in the literature of adversarial dueling bandits (Saha al. 2021).
Let (())())) (k) E A be the h element of the permutation for any & E [K]. Then, for any L < k2 [K]. action a+ (k1) is preferred over action ( For notational simplicity, we define a² > a² if action a' appears ahead of a² (a' preferred over a²) a permutation σ.
For the ranking model, we consider the standard Plackett-Luce (PL) model (Luce 1959 Placket 1975 where at each timestep conditioned on the proposed action set ot)) the ranking o (1) is sampled according to
K
exp (tr()) (a (ki))
F (6'0)00))
II
(PL)
Σ Dkg exp (Er(t) (alt) (k2)))
where p(() E RA is some utility vector based which the ranking is determined, > 0 is the temperature parameter that determines how uncertain the ranking model is: when 7 - 0-, the model absolutely certain, and the action with a larger utility in ((() will always be ranked in front of the actions with smaller utility in the permutation (ties are broken in favor of the smaller index). The utility vector (t) depends on the problem setting, which we will introduce next.
We consider two types of ranking feedback throughout the paper, based on the choice of (1)) in (PL): (i ranking by the instantaneous utility (InstUtil Rank); (ii) ranking by the time-average utility (tvgUtil Rank). These two feedback types may be motivated by different applications (cf. Section [), and have been studied in Yue et al. (2012); [Saha & Gaillard (2022) : Maran et al. (2024). Both feedback types can also be further separately defined for the full- inlloffffrmaainn and bandit set- tings, respectively, as follows.
InstUtil Rank: Ranking with Instantaneous Utility.
The first type of ranking feedback we consider is based on the instantaneous utility function, i.e., p()) ( in (PI.). This type is relevant when the feedback provider is oblivious or one-shot. For example, stream of customers arrive in an online fashion, each of whom arrives, ranks, and then leaves, see e.g. MMnsour al. (2015). When the environment is stationary and stochastic, the classical dueling-bandir model likewise uses instantaneous utilities for comparison and ranking Du et al. 2020).
Yuue al. 2012
fullinfformation setting. All actions are proposed and evaluated at each timestep t, i.e., (t)) = A. Hence, the agent's performance can be evaluated by (u(²), x= x0)).. Note that this does not imply the agent has access to the full vector (1, as that would defeat the purpose of our aaking-feeddard setting. Accordingly, we evaluate performance using the standard external regret R(T) .extern de- fined in (2.1).
Bandit setting, Only the proposed actions at each timestep / can be evaluated and ranked, with the associated elements in the vector (t), In particular, the proposed actions are evaluated by the average utility of & Emcote (t) (a), leading to the following performance metric of regret:
R(T)
max REA4
I K
Σ
(9) (a)
(3.1)
Note that such a definition is an external regret, which differs from the regret studied in (multi-
saueling-bandite (uue et al.] [012 Du et al. 2020 Saha et al. 2021 Saha & Gaillard 2022 Details can be found in Appendix
AvgUtil Rank: Ranking with Time-average Utility.
4

---

Published as a conference paper at ICLR 2026
The second type of aukkin-feeddban is based on the time-average utility, which differs for the full- information and bandit settings, as detailed below. This type is relevant when the feedback provider has memory and can use the history of utilities for ranking. For example, the customers are long- lived in the platform, see e.g., Küçükgüil et al. (2022) and [Baldwin] (2009). Notably, under bandit feedback, when - 0+ and the environment is stationary and stochastie, such model aligns with the one studied in the recent work of Maran et al. (2024).
Full-information setting. The time-average utility vector of Mavg the r(() in (PL). and the same (external-) )regret , from (.. will be used as the metric. Bandit setting. Only the proposed actions will be given to the environment to evaluate, For in- stance, the platform (learning agent) may recommend user (environment) to try out, so that the user will only know her evaluations of those K restaurants. As result, the average utility is now defined as the empirical mean of the utility vectors over time. Formally, for each timestep t 0 and action E A, we define
E
u((*) will be used as
restaurants among all possibilities to the
Cempitical (a) Eim u(() (a) End (a= d²)
(3.2)
E En'Eoto) 1 (a = aa)
empirical will then be used as the ((() in PL for ranking. The regret metric will still be the one in (3.1).
and u "empirical (a) O. This u (o
(0)
Due space constraints, we defer the background and formalism of equilibrium computation (with
ranking feedback) in the game-theoretic setting to Appendix B
4 HARDNESS RESULTS
In this section, we present hard instances to show that online learning in non-stochastic and poten- tially adversarial environments can be hard in general, under both Insl Rank Avg Rank even when there are only two actions.
Theorem 4.1 in the following shows that for any temperature in (PL) no larger than a constant, there exists sequence of utility vectors such that the expected regret is linear under UnstUti Rank for both full-information and bandit feedback settings.
Theorem 4.1. Consider [nstUtil Rank For any T temptreteaaa T
temperature 0.1, and online learning algorithm, there exists sequence of utilities (u(²) min {E eexteral E [ 2 (T) in both full-information and bandit feedback settings. The expectation is taken over the randomness of the algorithm and the ranking.
1=1 such that
To prove Theorem 4.1 we need to construct two sequences of utility vectors, which yield the same ranking under Util Rank in expectation. However, being no-regret in one of them will result in linear regret in the other. The detailed proof can be found in Appendix D
The key challenge in achieving no-regret in the hard instance above is that the utility vectors (u( t=1 change arbitrarily fast, i.e., the accumulated variation grows linearly in time. Hence, obtain positive results, we may need to restrict how fast they change over time, quantitatively characterized by the following assumption.
Assumption 4.2 (Sublinear variation of utility vectors). The utility vectors (u())) T have a sublin- ear variation over time, i.e., for some q < 1.
T Σ
P(T)
u (- s O((T).
(4.1)
Our result stated in Section 5 next will show that with Assumption 4.2 we can achieve sublinear regret, and thus close the gap. Moreover, note that in game where the opponents all run common no-regret learning algorithms such as Thw.--The-Reeerizeeeedeee tion 4.2 will be satisfied (cf. Lemma
(cf. Definition L.2) Assump-
Next, we show in Theorem that when AvgUüi Rank is used, and T is small enough, the minimal regret is still least linear 7 (up to logarithmic terms).
5

---

Published as a conference paper at ICLR 2026
Theorem 4.3. Consider Avg Rank Kath full-information feedback. For any T O, temperature
0 O<TS O TlgT and online learning algorithm, there exists T 2 ' and sequence of utilities T" )==1
2 (T'). The expectation is taken over the randomness of the algorithm and the ranking.
(u(t))
such that IE [R(T")
To prove Theorem 4.3 we construct log T sequences of utility vectors that induce identical ranking feedback when is small. We then show that at least one of these sequences incurs average regret
1(1). Given Theorem 4.3 it is impossible to achieve o with AvgUtil Rank when is very small. However, in Section 6 we will mitigate the gap by showing that when T is constant (i.e. (1)),
can achieve sublinear regret with Avg Rank even without Assumption 4.2
Due to the different instantiations of (+) in the full-information and the bandit feedback settings under AvgUtil Rank we have a separate hardness result for the latter, stronger than Theorem 4.3 as it allows larger and avoids logarithmic terms. The result can be viewed as strengthening the hardness result for the adversarial bandit setting in Maran et al. (2024), which corresponds to the case in our model with
0+.
Theorem 4.4. Consider Avg Rank with bandit feedbuck. For Forany T > O, temperature O <
AT and online learning algorithm, there exists a sequence of utilities (u()) such that E [ 2 (T) The expectation is taken over the randomness of the algorithu and the ranking.
log
To prove Theorem 4.4 we need to construct two utility sequences such that achieving sublinear regret in the first utility sequence will lead to insufficient exploration for the second sequence. As a result, when 7 is small, those two sequences cannot be distinguished, and a linear regret must be incurred in one of them. Details of the proof can be found in Appendix D
ONLINE LEARNING WITH Untl Rank FEEDBACK
We start by introducing new utility estimation oracle be used in later algorithms.
5.1 UTILITY ESTIMATION
A natural approach to learning from ranking feedback is to use the observed permutations to estimate the underlying numeric utility vectors. At each timestep f, we form an estimate of the current utility vector (t) using a sliding window of the most recent m rounds of observations: when 2 m, we use the past m permutations {o(+))' )o(+))==-mm- to construct an estimate 7t). Due to the non- convexity of (PL). the key step is to decompose length- K ranking into pairwise comparisons. This reduction allows to exploit the logistic structure of pairwise comparison probabilities and, via the monotonicity (and invertibility) of the logistic map, translate the estimation error of ranking probabilities back into an error bound on estimating the utilities. The full procedure given in Algorithm 1 and we state its guarantee next.
Theorem 5.1. Consider [IntUUil Rank and Algorithm 7 Suppose each action is proposed independently with probability least p > at each timestep [T] and let ū(t)
Estimate ( Then, for any 8 10,1) and m', when m''p 2 log (3). with probability at least the estimate (t) satisfies,
T E +
log mee
(0)
u (a+1)
u (0)
p
Treating 6, p, and as constants, the accumulated estimation error 7
will be
bounded by O T be achievable when P(T) is sublinear (Assumption 4.2). Moreover, Theorem 5.1 shows that the upper bound diverges as - 0+, This aligns with intuition: when 0+, the highest-utility action
Vm + +m'P(T) which implies that a sublinear accumulated estimation error can

---

Published as a conference paper at ICLR 2026
ranked first almost deterministically, and thus the feedback carries essentially information about the utility gaps between actions. At the other extreme, when т - +o0, the bound also diverges because the ranking is nearly sampled uniformly and hence largely independent of the underlying utility vector.
The full proof of Theorem 5.1 is deferred Appendix Next, show how to achieve sublinear regret in both full-information and bandit settings with InstUfil Rank based on such an estimator.
5.2 SUBLINEAR REGRET WITH InstUtil Rank
This section shows that for any online learning algorithm that achieve sublinear external regret with numeric utility feedback, we can construct an online learning algorithm with InstUtil Rank feedback based it, black-box way.
With full-information feedback, the learning agent proposes the full action set A at each timestep. In this case, we can obtain (0)), an estimate u (*)), by Algorithm and obtain guarantees using Theorem 5. with p 1, since all actions proposed at each timestep.
With bandit feedback, the utility of the learning agent timestep L is R Σ utt) (o()())) i.e. the average utility of the proposed actions. To achieve sublinear R(T') (as defined in (.1)). each proposed action will sampled from x(() independently with replacement. In other words, an action may be proposed multiple times at a single timestep. To ensure sufficient exploration, namely, every action is proposed with positive probability, we impose uniform lower bound T (((((a) 2 [ for
some 7 > 0 and all A. We enforce this by updating π (++11 (1-
(7))) )=1) +7 1(A),
Le., convex combination of the strategy generated by the no-regret learning algorithm Alg and uniform probability distribution over A. A diagram of the algorithm can be found in Figure 10, and the details are tabulated in Algorithm 2 Then, we have the following theorem.
Theorem 5.2. Consider InstUtil Rank with constant T O. By running Algorithu 2 for any and any full-iffomation no-regret learning algorithm with numeric utility
8 (0, 1). T
feedback, Alg, by choosing the window size m and y properly, we have that with probability at least
1 - 5, the following hold:
)))² ④
RTT) pextenal
< <nl (T))))xxtenn
Alg,
((())
0
(p(T))
T log
(Full-Info)
(T) (..)).exxtennd
Alg:
((t)
(p(T)
$ Té log
)7))
T
(Bandit)
The proof can be found in Appendices G and Theorem 5.2 implies that when p(2), the variation the regret of Algorithm will be sublinear.
of utility vectors, is sublinear (ef. Assumption
ONLINE LEARNING WITH AvgUtil Rank FEEDBACK
6.1 UTILITY ESTIMATION
Since (*)) is generated based on Mavg : u (+), we will estimate uave instead. We will still
(t)
(t) apply Algorithm which generates u an estimate of uavg- when the permutation sampled under Avg Util Rank feedback. Moreover, notice that
(t-1)
u + (t - 1)ul (t-1)
(L-1) Wavg
$ |ultl|
1 t
||_ + + Il))))) S 2
W uavg
aav
t
Thus, - ml+1
(a+1) uavg
Uavg
(8)
the counterpart of Σ | r ( in The- irrelevant of the accumulated utility variation P(T).
orem 5.1 can be bounded by
Et=1 wottmm/t 441
6.2 FULLI-IFFORMATION SETTING
Unlike InstUtil Rank feedback, where we can plug the utility estimates into essentially any (full- information) no-regret learning oracle, the AvgUtil Rank setting requires update rule that is
7

---

Published as a conference paper at ICLR 2026
stable with respect to the perturbations in the accumulated (averaged) utilities, such as Follow-The: Regularized-Leatee (Hazan et al. 2016). The reason is that we would like the strategies produced
from the estimated averages Mavg. .... Davy to remain close to those that would have been produced
[[1]
(1)
from the ground-truth sequence Wavg:... u With such stability, the regret of our learner can be controlled by the regret of this "ideal" learner, and hence remains sublinear up the additional error induced by estimation.
(1)
Assumption 6.1. The (full- (all-information) online learning algorithm Alg satisfies the following con-
dition: for any T > 0. t [T], and sequences of utilities (u())) 1=1 have
(w((s)
E (BA) we
Als ((u())) (m1) Alg ((wr)o))
(x)
160
where L = 0 (T- ) for some constant E 10.
can be verified that FTRL with any strongly convex regularizer satisfies this assumption (cf. Lemma L.3). Then, similar to Section 5.2 any online learning algorithm satisfying Assumption [ can achiev a sublinear regret when equipped with the utility estimator in Algorithm [T The overall
procedure is summarized in Algorithm Jand Figure II with the following guarantee.
Theorem 6.2. Consider Avg Itil Rank with constani т > 0 and full- call-information feedback. By run- ning Al Algorithm 3 for any ò E (0, 1). T >0, O, and any full-information no-regret learning algorithm with numeric utility feedback, Alg, that satisfies Assumption 6.1 by choosing m properly, we have
that with probability at least 6, exteera) satisfies
R(T) extteraal
(TT).xxterna
(Alg, (2()) (w)))
T 1=
+ +0
LT log
))
8
with some c > 2/3, then the external regret extteraa becomes sublinear in T. This choice of can be realized by instantiating Alg FTRL with suitable parameters (see Lemma L.3) Hence, the choice of L will also affect extteral
Theorem 6.2 implies that we choose the stability parameter = θ (T
Alg, (z)))²
)... The formal statement of Theorem 6.2 and its proof can
be found in Appendix [
6.3 BANDIT SETTING
By applying Algorithm we can only obtain estimate of cmmiriiaal (cf. (3.2) instead of Uavg. since it is the former that is used for ranking. However, almost all no-regret learning algorithms made decisions according the accumulated utility, such as mirror descent (Hazan et al. 2016), FTRL, and regret matching (Zinkevich et al. 2007). Let (0) == E #100 (a) for any a E A be the number of times action a has been proposed up to timestep i, where #ace) (a) is the num- ber of occurrences of in the proposed choices o(*) at timestep A natural idea is to compute (t (a)u to get an estimate of (a).. Nonetheless, the vari- ance of this estimator will be too large due to the multiplication of (*)) tt
(t)
(t)
(*()) (a)u(() empincca
divide the timesteps (1,2..... ,t} into [t/M] blocks, with each block containing M timesteps except for the last one. Then, for each block {s M M+1, 1,,
To address this issue,
2,..... + 1)M} (for s s 1 1) and a A, estimate M 2 (a) by computing
1 I (++1)M
()+ (a)m (++1-)) (a) 7 / (a)m (0
n 11 (a) n2 (a)
In this way, the coefficient multiplying u "empirical (a) is now nnto iy (a) in) Ma & f The choice of M therefore induces a bias-variance trade-off: increasing M reduces the variance, but the resulting quantity estimates the average utility action conditional on a being selected in that block, which can differ substantially from the block-average utility of a. This discrepancy becomes more pronounced for large M, since more utility variation can accumulate within a longer block. The full algorithm is introduced in Al Algorithm and Figure 11
((++1)-MM
(e+1))
M.
8

---

Published as a conference paper at ICLR 2026
Theorem 6.3. Consider AvgUtil Rank with constant 0 and bandit feedback. By running Algorithm 3 for any (0,1).T> U, and any full-information no-regret learning algorithm with numeric Milliyy feedback, Alg, that satisfies Assumption [6.1] by choosing m, 7 and M properly, when p(T) < (T") for some q < 3/ and L = (T with e E + 1), with probability at least 8, R(T) satisfies
R (.(T)exttnnall (Als, (u()))=z) 0 ((og 5
L T (pem)+) +
where ① hides logarithmic dependence on T.
In Theorem 6.3 we require c because, for many algorithms, one typically has an external- regret bound of the form (TT),extenal (Alg, (u(t)) )==
S SO + See, egg., FTRL with any
strongly convex regularizer as an example (cf. Lemma taking 1 would make the 7, term linear in T.
L.3 and Hazan et al. (2016). In particular,
7 EQUILIBRIUM COMPUTATION WITH RANKING FEEDBACK
For normal-form game (N,(A)) (2) the external regret of player i [N] is defined as R R.T). = mA Σt= 1 - n:²") ( where n. E AA. the strategy of player i at
timestep & and u, (a:) Ea'exy A, Ui(a') (a) - a;) Minee (1) TT' (a'x) for any a, A; Then,
(T) it is known that the time-average joint strategy Tavg, where Tavg (a) = 7 El= [I x, (a.) for R ( exterraaa
(1)
any a E X As, is an e-CCE with 6: max.e[M]
Applying the algorithm in Section 5 (for InstUtil Rank feedback) or Section 6 (for Avg Util Rank
feedback), we achieve sublinear R,T). extternal for each player E [VV]. Note that ((7) Assump- tion 4.2 can be bounded by the summation of all players' strategy variation (see Lemma K.I. Thus,
to ensure P(T) is sublinear in T, Alg needs to additionally satisfy the following assumption.
Assumption 7.1 (Sublinear variation of strategies). The (full- (illl-informatio)) online learning algorithm Alg needs to satisfy the following condition: for any > 0, t E [T (T- 11, and sequence of utility vectors (u())) 1+1
a=1 E ([-1, [+1 we have Als (zl)))
Alg (ml)))==)) 17, where
17 (T- for some constant 10.
Mirror descent (ef. Wei et al. (2021 Lemma 1) and Liu et al. (023 Lemma C.5)) and FTRL with any strongly convex regularizer both satisfy this property, see Lemma L.3 for the proof. When Assumption 7.1 is satisfied, one can achieve sublinear regret with InstUtil Rank under both full- information and bandit feedback. The formal statement is as follows.
Theorem 7.2. Consider InstUtil Rank with constant T > and Algorithm 2 For any (0, 1), T > O, and any full-information no-regret learning algorithm with numeric utility feedback, Alg, that satisfies Assumption 7.1 by choosing M, m, y according to Theorem 5.2 we have that with probability least 6, the algorithm finds an c-CCE, with
S max [E[N]
(TTT)..o exxteraal
(-(1) Alg,
u
+0
log
))
Ifull-informtiio)
T
e max
[E[N]
(T) external
Alg,
/==1
n7 log
T g
(Bandit)
With Avg Util Rank feedback, when all the players apply Algorithm 3 and both Assumption 6.1 and Assumption aare satisfied by the oracle Alg being used, the external regret of each player will be sublinear in 7 according Theorem 6.2 Finally, we have the statement below.
Theorem 7.3. Consider AvnsiderAAggUti Rank with constant T > O and Algorithm 3 For any 5 E (0. 1), T > 0, and any full-infformationn no-regret learning algorithm with numeric utility feedback, Alg

---

Published as a conference paper at ICLR 2026
LLM Routing
X =
A
1:01
0.30
Average Regret
0:30
0.30
0.33
2:30
4.20
0.55
6:35
0.00
0
5000
5000
5000
Figure 2:
Regret of Algorithm 3 with AvgUtil Rank under bandit feedback for different tempera- tures 7 and numbers of proposed actions K, in the online learning setting.
that satisfies Assumption 6.1 by choosing M, m. according to Theorem 6.2 we have that with
probability at least 8. the algorithm finds an c-CCE under full-information feedback, with
max (EIN) (T
RR(T)extteral
(Alg. (Alg.( 11 (u))
LT log
(Full-Information)
When M, m, and 7 are chosen as in Theorem hold, we have that with probability at least 6. the algorithm finds an e-CCE under bandir feedback, with
6.3 and both Assumption 6.1 and Assumption 7.1
((108 (1))² (L + +
external (Als. (u()) (u))
mam max :E[N]
(Bandit)
Lastly, we would like to remark that although the online learning setting can be hard with a small (ef. the hardness results in Theorem 44.3)and Theorem 4.4). computing equilibrium is still possible even when T + 0+. detailed discussion can be found in Remark K.3
EXPERIMENTS
To demonstrate the practical merit of online learning with ranking feedback, we consider the fol- lowing scenario as an application example, which we term as online large-languge-mmole routing- service provider hosts multiple language models, each possessing distinct strengths. For instance, GPT-4o (Hurst et al.] 2024) may excel in creative writing, whereas GPT-5 specializes in coding. Consequently, users may exhibit different preferences for different models.
We cast personalized large language model (LLM) routing an online learning problem with rank- ing feedback. Fix a particular user and view each candidate model as an action. each timestep t, the user submits a query, and the server samples K candidate responses by drawing models accord- ing to mixed strategy (t) and querying the selected models on that prompt. The user then returns ranking over the proposed responses, providing only relative-preference feedback rather than cal- ibrated scores. This feedback is induced by underlying, vineiiarying utility vector (! that captures the user's instantaneous (or time-aggregated) satisfaction with each model. The server's objective is to update (+) online to minimize external regret with respect to the best fixed model in hindsight, while remaining responsive nonstationary preferences. For instance, a may prior- itize creative writing for a period and later shift toward coding or mathematical problem solving.
generate responses for the HH-RLHF (Bai jet al. 2022) dataset using Qwen3-32B (Yang et al.) (2025), Phi-4 (Abdin et al.] 2024), GPT-40 (Hurst et al. 2024), and 1lama-3.1-700 (Dubey et al. 20024.. We evaluate the responses using reward mode| and execute Algorithm 3 with AvgUtil Rank under bandit feedback. At each time step, prompt is sampled from the dataset along with responses from different models, and the resulting scores form the reward vector. As shown in Figure 2
We simulate this process in Figure 2 Specifically,
the average regret decreases over time, suggesting that our router quickly approaches the performance of always serving the best fixed model in hindsight, i.e., the model with the highest cumulative reward under the user's preferences. More experiments about online learning and equilibrium computation can found in Appendix
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENT
The authors thank the anonymous reviewers and area chair for the value feedback. M.L. was sup- ported by the MathWorks Fellowship. A.O. and G.F. were supported in part by the ONR grant N00014251 12296. G.F. was additionally supported by CCF-2443068 and an A12050 Early Career Fellowship. K.Z. was supported by the ARO grant W911NF-24- 1--000 the NSF CAREER Award 2443704, and the AFOSR YIP Award FA9550-25-1-0258.. UMD.
Y.C.'s work was done while visiting
ETHICS STATEMENT
This research does not involve human participants, personally identifiable information, or sensitive data. All experiments
conducted under hypothetical and simulated environments. No animals or humans were harmed or involved in this study. The authors affirm that the work complies with ethical standards of the research community.
Furthermore, we have carefully considered the potential societal impacts of our research. While the proposed methods could be applied in various real-world settings, acknowledge that any without fairness considerations, may raise ethical
misuse, such as in surveillance or decision concerns. We strongly encourage the responsible use of our work and emphasize that it should not be deployed in contexts that may cause harm or reinforce social biases.
10 REPRODUCIBILITY STATEMENT
All assumptions are listed in Table D and the proofs are presented in the appendices, from Ap- pendix to Appendix L
11 USE OF LARGE LANGUAGE MODELS
In this paper, we use large language models (LLMs) to improve writing (e.g., by correcting gram- matical errors), creating illustrative figures (Figure 1 and generating code.
REFERENCES
Marah Abdin, Jyoti Aneja, Harkirat Behl, Séhastien Bubeck, Ronen Eldan, Suriya Gunasekar, Michael Harrison, Russell J Hewett, Mojan Javaheripi, Piero Kauffmann, al. Phi-4 techni- cal report. arXiv preprint arXiv:2412.08900 2024.
Jacob Abernethy, Kevin Lai, and Andre Wibisono. Fast convergence of fictitious play for diagonal payoff matrices. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1387-1404. SIAM, 2021.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0586. 2022.
Carliss Y Baldwin. The architecture of platforms: A unified view. Platforms, Markets and Innova- tion/Edward Elgar Publishing Limited, 2009.
Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log regret for decentralized bandits in matching markets. In International Conference on Machine Learning (ICML), 2021.
Ulrich Berger. Fictitious play in 2 x games. Journal of Economic Theory, 120(2):39--544 2005.
Avrim Blum and Yishay Mansour, From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
11

---

Published as a conference paper at ICLR 2026
George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1): 374, 1951.
Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang, Sherry Yang, Dale Schu- urmans, Yuejie Chi, and Bo Dai. to online and offline rlhf. In International Conference on Learning Representations (ICLR), 2025.
preference optimization: A unified approach
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Constantinos Daskalakis and Qinxuan Pan. A counter-example to Karlin's strong conjecture for fictitious play. In Annual Symposium on Foundations of Computer Science (FOCS), 2014.
Yihan Du, Siwei Wang, and Longbo Huang. Ducling bandits: From two-dueling to multi-ducling. 2020.
Yihan Du, Anna Winnicki, Gal Dalal, Shie Mannor, and R Srikant. Exploration-driven policy opti- mization in RLHF: Thcoretical insights on efficient data utilization. In International Conference on Machine Learning (ICML), 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Llama 3 herd of models. arXiv e-prints, pp. arXiv-2407, 2024.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Con- textual dueling bandits. In Conference on Learning Theory (COLT), 2015.
Vikranth Dwaracherla, Seyed Mohammad Asghari, Botao Hao, and Benjamin Van Roy. Efficient exploration for LLMs. In International Conference on Machine Learning (ICML), 2024.
S Rasoul Etesami and R Srikant. Decentralized and uncoordinated learning of stable matchings: A game-theoretic approach. In AAAI Conference on Artificial Intelligence (AAAI), 2025.
Drew Fudenberg and David K Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, (9(5-)):1055-108) 1995.
Drew Fudenberg and David K Levine. The theory of learning in games, volume 2. MIT press, 1998.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American matheratical monthly, 69(1)--11,, 1962.
Sergiu Hart and Andreu Mas-Colell A simple adaptive procedure leading to correlated equilibrium. Econometrica, 6865):1127-11500 2000.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ Opti- mization, ((3-4):157-325, 2016.
David R Hunter. Mm algorithms for generalized Bradley-Terry models. The annals of statistics, 32 (1):384 406, 2004.
Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Os- trow, Akila Welihinda, Alan Hayes, Alec Radford, et GPT-4o system card. arXiv preprint arXiv:2410.212760 2024.
Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael Jordan, and Jacob Steinhardt. Learning equilibria in matching markets from bandit feedback. In Neural Information Processing Systems (NeurIPS), 2021.
Can Küçükgül, Özalp Özer, and Shouqiang Wang. Engineering social learning: Information design of time-locked sales campaigns for online platforms. Managemeni Science, 68(7):4899-49 2022.
Lydia Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In Inter- national Conference Artificial Intelligence and Statistics (AISTATS), 2020.
12

---

Foundations and Published as a conference paper at ICLR 2026
Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1-34, 2021.
Mingyang Liu, Asuman E. Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regulariza- tion in solving extensive-form games. In International Conference on Learning Representations (ICLR), 2023.
Duncan Luce. Individual choice behavior, volume 4. Wiley New York, 1959.
Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatbbe bandit exploration. ACM Conference on Economics and Computation (EC), 2015.
Davide Maran, Francesco Bacchiocchi, Francesco Emanuele Stradi, Matteo Castiglioni, Nicola Gatti, and Marcello Restelli. Bandits with ranking feedback. In Neural Information Process- ing Systems (NeurIPS), 2024.
Dov Monderer and Lloyd S Shapley. Fictitious play property for games with identical interests. Journal of Economic Theory, 68(1):258-22) 265, 1996.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sam- pling for preference- based reinforcement learning. In Conference on Uncertainty Artificial Intelligence (UAI), 2020.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. In Neural Information Processing Systems (NeurIPS), 2022.
Chanwoo Park, Mingyang Liu, Kaiqing Zhang, and Asuman Ozdaglar. Principled rhhf from heterogeneous feedback via personalization and preference aggregation. arXiv preprint 00X0:22405.0024. 2024.
Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statistics, 24(2):1932008 1975.
Julia Robinson. An iterative method of solving game. Annals of mathematics, 54(2):296-301, 1951.
Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: Best-of-both-world analyses for online learning from preferences. arXiv preprint arXiv:2202.06694, 2022.
Aadirupa Saha and Aditya Gopalan. Combinatorial bandits with relative feedback. In Neural Infor-
mation Processing Systems (NeurIPS), 2019.
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In International Conference on Machine Learning (ICML), 2021.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling RL: Reinforcement learning with trajec- tory preferences. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Aner Sela. Fictitious play in "one-against-all" multi- player games. Economic Theory, 14(3):635- 651, 1999.
Vade Shah, Bryce L Ferguson, and Jason R Marden. Learning optimal stable matches in decentral- ized markets with unknown preferences. IEEE Conference on Decision and Control (CDC), 2024a.
Vade Shah, Bryce L Ferguson, and Jason R Marden. Two-sided learning in decentralized matching markets. arXiv preprint arXiv:2411.02377 2024b.
Shai Shaley-Shwartz et al. Online learning and online convex optimization. Trends@ in Machine Learning, 4(2):177-19,,20) 2012.
13

---

Published as a conference paper at ICLR 2026
Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-poin optimization. In International Conference on Learning Representa- tions (ICLR), 2021.
Tengyang Xie, Dylan Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit Qe-approximation for sample-efficient RLHF. In International Conference on Learning Representations (ICLR), 2025.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based re- inforcement learning with finite-time guarantees. Advances in Neural Information Processing 2020.
Systems,
An Yang. Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388 2025.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The K- K-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-1566 2012.
Shenao Zhang, Donghan Yu, Hiteshi Sharma, Han Zhong. Zhihan Liu. Ziyi Yang, Shuohang Wang, Hany Hassan Awadalla, and Zhaoran Wang. Self-cxploring language models: Active preference elicitation for online alignment. Trans. Mach. Learn. Res., 2025.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning (ICML), 2023.
Daniel Ziegler, Nisan Stiennon, Jeffrey Wu, Tom Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909. 1rXv:1199.00559,, 2019.
Martin Zinkevich, Michael Johanson, Michael H. Bowling, and Carmelo Piccione. Regret minimiza- tion in games with incomplete information. In Neural Information Processing Systems (NeurIPS),
2007.
14

---

Published as a conference paper at ICLR 2026
A RELATED WORK
Dueling Bandits. Using comparison and/or ranking feedback for sequential decision makiing has mostly been studied under the framework of dueling bandits (Yue et al., 2012 Saha & Gaillard 2022 Saha & Gopalan 2019 Du et al.; 2020, Saha et al.] 2021 Dudik et al. 2015). where the agent takes two (or multiple) actions at each timestep, and receives a ranking of them as feedback. Different from our setting, the ranking feedback in these works was only based on the instantaneons utility at that timestep, while our results can address both settings with instantaneous and time- average utilities for ranking. More importantly, the regret notions studied in these works were particularly designed for the dueling- dueling-bandit setting, and thus different from the classical external regret we focus on here. Finally, dueling bandits mostly focused on environments that are stationary and stochastic (Yue et al. 2012 Saha & Gaillard, 2022, [Saha & Gopalan| 2019 Du et al. 2020), while we focus the non-stochastic setting where the environment is arbitrary and potentially adversarial, as in online learning (Shalev- Shwartz ct al., [0022] Hazan et al. 2016). Due to the last two differences, the implication of these dueling-bandit algorithms in the game-theoretic setting is unclear, while our algorithms find an approximate CCE of the game, as a corollary of the no- (external-)regret guarantee.
Reinforcement I. Learning from Human Feedback (RLHF) and Preference-Based RT.. Inspired by the successes in aligning large language models (LLMMs) (Ouyang et al., 2022), reinforcement learning from human feedback has received increasing attention. RLHF is usually instantiated as preference- learning, where humans rank the model outputs based their preferences, and a reward model is then estimated from the feedback, which will be further used for model fine- tuning. This way, RLHF is oftentimes implemented in an offiie fashion, where batch feedback data are used for reward model estimation (Ziegler et al. 2019 Bai et al., [022] Ouyang et al.] 2022]
Zhu et al. 2023 Park al. 2024). Recently, online versions of RLHF have also been developed
(Dwaracerrla et al. 2024| Du et al., 2024; Xie et al.
2025 Cen et al. 2025: Zhang et al.) 2025).
where the exploration issue was addressed with online feedback. In fact, beyond fine-tuning LLMs, preference-based RL has also been studied in the classical Markov decision process model with online feedback (Novoseller et al,, 2020, Saha et al.) 2023 Xu al., 2020). However, the util- ity/reward functions in these works are again stationary, and the regret notions extend those in the dueling-bane bandits literature, which are thus different from ours. Hence, these results do not apply to our adversarial online learning and game-theoretic settings.
Learning of Stable Matchings. Some of our motivating scenarios for the game-theoretic setting may also be modeled as the stable matching problem (Gale & Shapley] 1962). which has been extensively studied when the agents have full knowledge of their preferences. Recently, growing efforts have been devoted to learning in stable matching markets with unknown preferences, and
through interactions between the agents (Liu et al. 2020 2021 Basu et al.) 2021 Dagadeessn al., 2021 Etesami & Srikant) 2025; Shah et al. 2024b]ar a). Notably. Etesami & Srikant (2025): Shhh et al. 2024b a) also took a game--therrete perspective, by developing learning dynamics for finding matchings in decentralized, uncoordinated fashion. However, one key difference is that the learn- ing agents (e.g., the proposers or the platform) can still receive numeric feedback of the utilities each round, based on the matching result, while in our model, they can only receive the ranking feedback. Moreover, the learning dynamics in Etesami & Srikant (2025); (Shah et al. (2024a b) were specific to the matching model, while ours aim to address general normal-form games.
Recent Work by Maran, Bacchiocchi, Stradi, Castiglioni, Gatti, and Restelli (2024). The work closest to ours is the recent one by [aran et al. (2024), which studied multi- bandits with ranking feedback, also under the standard (external- )regret metric. Different from the ranking model in dueling bandits, the model of Maran et al.] (2024) is based on time-average utilities, setting also considered in our paper. More importantly, in contrast to our paper, Maran et al.] (2024) focused on the stochastic bandits setting where the utility functions are stationary, while our focus is on the adversarial/onlime and theertheocctic settings, with both instantaneous and time-average utility- based rankings. Furthermore, the ranking model in Maran et al. (2024) corresponds to the case of T - 0+ in our framework. Finally and notably, Maran et al. (024) also provided a hardness result for the adversarial bandit setting (with - of in our framework), while our hardness results (with
15

---

Published as a conference paper at ICLR 2026
different hard instances) are stronger in the sense that they allow wider range of T for the bandit setting, and also cover the full-information setting (cf. Table I
B ADDITIONAL NOTATION AND PRELIMINARIES
Notation. For any integer N
define [N] == {l.... N denote the set of positive integers no larger than N. We use bold notation æ to denote a liite-dimensionas vector, and z; to denote the ht element of the vector. For any discrete set S, let [S] denote its cardinality, A = {a E
IR:: E..es o5 = 1, V, 2 for all & E S} be the probability simplex over S, and 1 (S) be an all-one vector with each index being elements in S. For any ordered discrete set S, we use R$ to denote the [S] dimensional real space, where the sth E S element of any æ R is denoted as 2, or zs)). For any vector a E R", let |I=|,, be its Ln-norm and we use || I to denote the L2-norm by default. For any convex compact set C 1² and æ E RR", let Projc (x) argming''c | - -z'l=||- For any event e, let 1 (e) be its indicator, which is equal to one when e holds and zero otherwise. Additionally, for any discrete set S, let Σ (S) be the set containing all the permutations of the exp(x) elements in S. We will use sig(x) I+exp(x)
IR + R denote the logistic function.
B.1 NORMAL-FORM GAMES
An N- N-player normal-form game can be characterized by tuple (N, (A) ( where A = {a), at................... .................. denotes the Cartesian product of sets) is the utility function of player i, where (1(a), a2... AN) is the utility of player i when player j E [N] takes action dj. We call a: = (a1, a2: aN) the joint action and a_;; (01,..., a;-1, -.-1s-.......,.... aN). Player E [N] can choose strategy TT E A,, (T,1 ;,, a strategy profile. When strategy profile л is
A/1 is the (finite) action set for player i E [N]: X A + 1-1, (X
and we call X i=1 A 3 implemented, each player E [N] has an expected utility of Eaexy_, A, (i(a) I (az)).
Lastly, we use the unbold notation æ E A to denote the (possibly correlated) joint strategy of all the players, where (a) is the probability of choosing the joint action a E xX A,
N'
In this paper, we focus on finding an e-approximate coarse correlated equilibrium (e-CCE) of the NFG, which is a probability distribution over the joint action set. It is formally defined as follows:
Definition B.1 (c-CCE). For any joint strategy т E A A,, it is an e- e-CCE 2 Of
max max N a, A:
Σ
ul(a)
((((s)
Σ
I(d,, a-i) -x((a))
x(a)
Se.
(e-CCE)
DEX
When e 0, we refer to as a(n exact) CCE. We also refer to e as the exploitability.
B.2 EQUILIBRIUM COMPUTATION WITH RANKING FEEDBACK
There is mediator (platform) in the game that computes strategies for the players, (e.g., Uber recommends the candidate drivers and users to each other), but with only access to the ranking feedback from the players, e.g., humans. Specifically, when the strategy profile π is implemented by the players, player i's utility of taking action a; E A, is (a,) = Ex'ex A, (4(a)) 1 (a. = o;) 11 (a))). However, instead of observing the utility directly, the mediator can only observe the ranking based on it. Therefore, at each timestep 4, the mediator (0). (0).)) K will choose strategy profile π and propose each player i E [N] a multiset of {(
consisting of K actions, and in different settings proceed differently as follows:
Full-information setting. All the actions of each player i E [N] can be evaluated and ranked at each timestep based some utility vector, which is uz"" under InstUtil Rank
16

---

Published as a conference paper at ICLR 2026
(0) and uavg = E " under AvgUtil Rank, where T(() = -xx1) ..... AN
(0)
is the
strategy profile at timestep t.
Bandit setting. For each player i e [N], only the K actions in of that are proposed at timestep will be evaluated and ranked, with the associated elements in some utility vector.
Specifically, under InstUtil Rank 8; defined below will used: for each as E A:
(0 (a.)
Σ
Uilas, d':);
10_21 a'_,c
under Avg Rank the corresponding empirical average utility is as computed in (3.2 with the (*)) therein being replaced by the fz!")) above. As in the online setting, we as- Σ (ea Ui aa..a
sume that the actions are proposed in an unbiased way, i..., E
(a)(a;)), = for all E A.. In other words, u, is an unbiased estimate of u
The process will be repeated until the mediator finds (approximate) equilibrium of the game, which is the average of the joint strategy over all timesteps.
C ADDITIONAL EXPERIMENTS
To assess robustness across learning setups, we study both full-information and bandit feedback under the two ranking-feedback feedback models in Inst Rank and AvgUti Rank The corresponding regret results are reported in Figures 3 to 6 We also evaluate our methods on randomly generated two-player general-sum games under the same feedback models. For these game experiments, we report the resulting CCE exploitability e across different game parameters in Figures] to together with 95% confidence intervals.
We consider both full-information and bandit feedback. Throughout, experiments run for T 10T iterations, and each player has 10 actions. We evaluate performance across the num- ber of proposed actions K E {3. 5, 10), the temperature parameter 7 E (0.5, 1,2] in (PL). and the accumulated utility variation P(T) = T with q E {0.3, 0.5, 0.7). For AvgUtil Rank under full- information feedback, we consider only the case q 1.0, which does not restrict the utility variation, since the corresponding guarantee does not rely on Assumption 4.2 Moreover, for AvgUtil Rank under bandit feedback, although 0.5 and 0.7 exceed the theoretical threshold required for Algo- rithm 3] we empirically observe that Algorithm 3 still attains sublinear regret. This suggests that Algorithm is more robust practice than the current theory indicates.
For hyper-parameter selection, we conduct a separate grid search for each experimental set- ting. Under InstUtil Rank we tune the estimation window size m and the exploration rate Y; under AvgUtil Rank] we additionally tune the block size M. Specifically, we search 15x x 10a, 10 1.5 10*}. Y {0.1, 0.05, 0.013. and, when applicable. M {3 x 105, 5 10 1071. The learning rate is set to 1 = 1/v7 in all experiments except for bandit feedback under AvgUtil Rank where we use 17 10 10-6, Each parammer config- uration is evaluated over 10 random seeds, namely 10, 1,..,,.),)) 9). For each figure, we report the best-performing choice of m, M, and y, namely, the one that achieves the smallest average regret or e over all seeds at horizon T.
over m E
555x
Utility estimation is performed using Algorithm 1 As the full-information no-regret learning ora- cle with numeric feedback, we instantiate Alg as PGD for InstUtil Rank and as FTRL with L2- regularization for Avg Rank
In tog we report the performance of the learning algorithm for InstUtil Rank under both full-information and bandit feedback, and for AvgUtil Rank under bandit feedback. To generate utility sequences with cumulative variation bounded by 7 we first allocate the total variation bud- get T uniformly random across timesteps. At each timestep direction (t) uniformly at random and use binary search to choose scaling factor (4) such that Prroj (t-1 + (0)) - (t-) equals the variation assigned to round L.
then sample perturbation
17

---

Published as a conference paper at ICLR 2026
For AvgUtil Rank under full-information feedback, our algorithm accommodate sequences of utility vectors with unbounded cumulative variation. We therefore additionally conduct an ablation study on the noise model in Figure 6 We first sample an initial utility vector, and at each timestep the utility vector is defined as the initial utility vector plus an independent random shift. For each coordinate, the shift is drawn from one of three noise distributions: Uniform (- N. (0, (0, or I (1/0f,,²²)
with 0.3. We report the resulting average regret over time in Figure
0.35
6
0:33
015
Figure 3: The exploitability for the full-information feedback setting under both InstUtil Rank and AvgUtil Rank Performance is evaluated across different temperatures and cumulative utility variations p(T) = T Each parameter combination is tested 10 times with different random seeds.
Across all game settings, the exploitability decreases as increases, suggesting that the time- averaged joint strategy converges to a CCE.
D PROOF OF SECTION
In this section, we will show the hardness results in Section
D.1 PROOF OF THEOREM
Theorem 4.1. Consider InstUtil Rank For any T O. temperature 0
S 0.1, and online learning algorithm, there exists a sequence of utilities (u(²) t-1 such that min { [eserna)) E [R(F)]] 2 (T) in both full-informatiion and bandit feedback settings. The expectation is taken over the randomness of the algorithm and the ranking.
Proof. Consider an online learning problem with A = (a,b). so that the utility vector can be represented as (u(a), u(b)). There are two instances with r = 0.1 and K = 2 under bandit feedback.
In the first instance, there are two types of utility vectors (-0.5, 0) and (0.15, 0). At each timestep, 4 and the other with probability 13.
the adversary will choose (-0.5, 0) with probability 13
In the second instance, there are two types of utility vectors (-0.02, 0) and (0.1, Recall sig(r): I + I := exp(z) is the logistic function. At each timestep, the adversary will choose I+exp(a)
3.15
3.100
5:00
022
1003
1100
01
3.
Figure 4: The regret for bandit feedback setting under InstUtil Rank feedback in the online learning setting. The performance is evaluated across different temperatures т, cumulative utility variations P(T) T4, and numbers of proposed actions K. Each parameter combination is tested 10 times with different random seeds.
18

---

Published as a conference paper at ICLR 2026
Argllal
Figure 5:
The regret for bandit feedback setting under Ander/AygUtil Rank feedback the online learning setting. The performance is evaluated across different temperatures т, cumulative utility variations p(T) 74, and numbers of proposed actions K. Each parameter combination tested 10 times with different random seeds.
Average Regret under Different Noise Types
Uniform
Gaussian
Gamma
Average Regret
0.05
0.06
0.08
0.03
0.02
0.01
0.01
0.00
x107
x107
x10'
0.5
1.0
7 2.0
Figure 6: Regret of Algorithm 3 with AvgUtil Rank under full-information feedback, across differ- temperatures and noise types in the online-learning setting.
InstLini Rank Game with Full-information Feedback
ArrUtil Rank Game with Full-infommaioon Feedhock
0.50
0.322
CCE Apyrodimarben <
0.08
CCE Approstisttion
0.20
0.06
0.15
0.04
0.10
0.05
0..00
1.0
Timestep
Timeslop
Figure 7: The exploitability for the full-information setting under both Itil Rank and AvgUtil feedback in the game-play setting. The performance is tested under different temperatures 7. Each parameter combination is tested 10 times with different random seeds.
(-0.02, 0) with probability 4sig/ (ig(-65)/3++9iip (1.))//111111111-1 sig() 0.58 and the other with probability sigl 0.2) si)
4sig( (aig(-5)/13) 5/i15//1 sig(1)
sigl sig))
The expected utility of action in both instances 0. The expected utility of action a in the first instance is -0.05. The expected utility of action in the second instance is 0.03.
19

---

Published as a conference paper at ICLR 2026
Instlial Rank Came with Bandit Feodback
Instini Ronk Game with Bandit Feedback
[K
(7
0.5
K
K 5
W -10
CCE Approximsntiee:
0.20
CCE Approsimattiess
0.20
0.15
0.35
0.00
0.00
0.00
-0.00
-0.00
1..1
0.2
0.4
0.66
0.8
1.0
0.01
012
0.4
0.0
0.8
1.0
Timestop
Timestop
Figure 8: The exploitability for the bandit feedback setting under InstUtil Rank feedback in the game-play setting. Performance is evaluated across different temperatures and numbers of pro- posed actions K, Each parameter combination is tested 10 times with different random seeds.
ArgUhil Rank Gume with Bandit Feedback
AvgUhil Rank Game with Bandit Feedback
(K
0.175
0.175
K -3
0.330
8 -5
Appoxinstion:
K -11
0.125
0.300
0.100
0.075
0.077
CCE
0.000
0.025
0.025
0.3
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Timestop
Timestap
Figure 9: The exploitability for the bandit feedback setting under AvgUtil Rank feedback in the game-play setting. Performance evaluated across different temperatures and numbers of pro- posed actions K. Each parameter combination is tested 10 times with different random seeds.
Moreover, at any timestep t when both actions a, are proposed in o(1, in the ranking ((1), the probability of being preferred over b
(0) Pr
> =)==== 13
sig(- 5) + sig(1.5).
9
13
This coincides with the corresponding probability under the second instance,
4sig(-5)/ (5)/155)33333 + 9sig(1.5)/13 - sig(1) 0.2) (1- 4sig( (oig(-5)/13- + Osig(1.5)/11 sig(1) sig(-0.2) sig(1)
sig(1).
sig(-0.2) sig(1)
Hence, the distribution of the ranking (+)) is identical in the two instances. When (1) (a,b). the preceding equality shows that Pr (0))
matches across instances. When ( {a, a} (or
[b. b)), the ranking is deterministic, so it is trivially the same in both instances.
Therefore, under full-information feedback, for any algorithm that generates (I (1))
T
1=1' we have
2e (t) x(0)
-> E (v 10)) x0)
(1)
E
E
E
20

---

Published as a conference paper at ICLR 2026
The equality (i) holds because 2 is independent of x( given process of generating both instances. Similarly, under bandit feedback,
T
Σ
Σ (a) eEol))
=> E
Σ
(a)
E
u())
IE
x(10
K
aEol!)
In (t), we define (100()) = K Ed'eote) (a= for any a E A.
Then, for both the full-information feedback and the bandit feedback, have
B
Σ
P(O() (1-11)
E x (1) (1)
(1-1)
EE(A)
The first term IP (a , (t-1)) is equal in the two instances according the discussion above, and the second term E (7(1)) |o(1) ...., o(t-1)] is also equal since only depends on the algorithm. Therefore, E [x] is the same in both instances.
However, E (+) 0.05, 0) in the first instance but (0.03, 0) in the second. Therefore, when- ever achieving sublinear regret in the first instance, the algorithm will suffer a linear regret in the second instance, and vice versa.
D.2 PROOF THEOREM 4.3
Theorem 4.3. Consider Avg Util Rank wull-full-infee full-information feedback. For any T > O, temperature < (TogT) and online learning algorithm, there exists T 2 T and sequence of utilities (n(+)²" T" 1-1 such thut E externa)
2 (T'). The expectation is taken over the randomness of the algorithm and the ranking.
We (u(a), u(b)) denote the utility vector when the action set is A {a, b). In the following, we will show a hard instance for 7 - 0+, i.e., we always observe the action with higher utility ranks first the permutation. Then, we will show that T O can be reduced to 7 0+
Proof.
The utility vector at timestep 1 is ( (0.5, 0). We will construct the rest of the utility vectors next.
We call the following an action-a construction, since, except for the last timestep, the observation is that action is always better. Let K e N be the smallest integer such that 2 2 T, then:
Sequence =(0, 1), (0,0)
Sequence (1, (0, 1), (0, 1), (0,0)
Sequence =(, (1, (1, (0. 1). (0, 1), (0, 1), (0. 1). (0.))
(D.1)
Sequence K
0, (0. 1), (0.0)..0.))
2k 2--1-1
24-1
Sequence K (1, ..... (1, 1,0) (0.0)
28-1
Lemma in the following shows that at least one of the sequences will incur a low average utility for the algorithm.
Lemma D.I. Consider D.IIp. For any any online learning algorithm, at least one of the K+1 sequences satisfies that the expected average utility per timestep is less than 0.5 2(++I)*
By Lemma D.1 there exists a sequence with length 2² for some l < K such that the average utility per timestep achieved by the algorithm is less than 0.5 2(K+1) We will pick this sequence the
21

---

Published as a conference paper at ICLR 2026
next 2 utility vectors. If the current utility vector sequence is no less than T, then the hard instance completed. Otherwise, we will establish the following action-b construction:
Sequence = =1, (0.0)
Sequence = (), (1, (1, (0.0)
Sequence (0,,)) (0, (0, 1), (1. 0), (1, (1,0))
...
Sequence K
(0, ().1),.... (0, 1). (1. ().O,.... ..... (0.0).0.0)
2K-1-1
24-1
Sequence K (0, (0.1),... (0, (0,0)
2
Similarly, except for the last observation, action b is the best action in all the observations. Similar Lemma D.I we can show that least one of the sequences incurs average utility per timestep less than 0.5 2[++Jj We will add that sequence to the end of our hard instance.
Tet 2 T be the length of the final instance. Therefore, the average regret will be at least 2(K+1) + M ( Because of the construction, the best action should get at least 0.5 utility per timestep.
When r S 47 To from the construction above, the difference between the cumulative utility of the actions is always 0.3. By the definition in Atl Rank] at any given timestep the probability that an action with lower average utility preferred over an action with higher average utility 1 - sig 0.5
< O TTZ Applying union bound over all timesteps, it follows that with probability at least O (2), such misranking occurs at any timestep. Hence, every permutation ranks the higher-utility action first throughout. In other words, with high probability, the algorithm incurs linear regret.
For any online learning algorithm, at least one of the K ++1 sequences satisfies that the expected average utility per timestep is less than 0.5 2(K11)
Lemma D.1. Consider (D.Ip.
Proof. Note that in this online learning setting, the strategy (()) is determined by (2) ( (t-1), Therefore, in all the sequences in the action-a construction, since action is the best in all the observations, for any two sequences h S k2, the expectation of the strategies is the same for the first +1 utility vectors. For simplicity, we will use (²) denote the probability of choosing action-a at timestep
The average utility at sequence 0 is (-)()) The average utility at sequence 1 is (1) We can see that the utility contributed by (1)) to all the sequences is
(2)
4
- (1)
(1)
(1)
x
(1)
1
2
4
8
2K
2
Similarly, the contribution of (2))
(3) is 1. The contribution of (4) (5) ..... (7) is J. Therefore,
the total contribution of r!(1) (2*
(2=-111 -1)
K.
2. There are K + sequences in total, so that at least
one of the sequences has average utility per timestep less than 2K+1J 2 2K=2
D.3 PROOF OF THEOREM
Theorem 4.4. Consider Avg Util Rank with bandit feedback. For any T 0, temperature 0 < 7
O and online learning algorithm, there exists sequence of utilities (n(9) 4T t= such that (T) 2 2 (TT) The expectation is taken over the randomness of the algorithm and the ranking.
E
22

---

Published as a conference paper at ICLR 2026
Proof. Consider the following two instances. Both of them satisfy A b) and K 1.
Instance (0.1,0)...... (0.1,0), (0.1)),).......11)))
(0.0.2) (0, (0.1)....,(..1
2T
(0.1.0), 00.0.)..... ..... (0.0.2) (0.4, 0.2). 0.4, Instance 2 (0.1)),).......))))
We call the first T' timesteps as the first phase, the next I' timesteps as the second phase, and the last 27 timesteps as the third phase.
For any online learning algorithm to achieve sublinear expected external regret, it must propose action a for least 0.97 timesteps during the first phase with probability at least J since otherwise the expected external regret in the first phase is linear. With probability at least 2. after proposing at least 0.9T timesteps of in the first phase, the online learner must propose action b for least 0.45T timesteps during the second phase to achieve sublinear regret. Then, at
0.27 1.17--0.--00000 0.2
the end of the second phase, with probability least 4' eempirical (2t) (b)
Vempirical (a) 2 0.17-00.55
0.45T-0.2
0.1 -io-
Intuitively, during the third phase, achieving sublinear regret on Instance I requires that action not be proposed too many times. However, if the learner proposes action too infrequently, it may fail sample action a sufficiently often distinguish Instance from Instance which would then lead to linear regret.
Formally, during the third phase of Instance I, the algorithm needs to propose for at least 0.27+27-0.22 0.27 0..17-0.07 0.017 1.897 timesteps with probability at least 2
! after proposing at least
0.9T in the first phase and 0.457 b in the second phase. In other words, is proposed by no more than 0.117 times. Then, in Instance 2, throughout the third phase
(1) (2740. (b) u (27+0.117) (a)
W 'empirical (b) eempirical (a) 2 empirical
empirical
0.45T 0.2 0.97 0.1 + 0.117 0.4
2 0.03.
0.17 + 0.457
0 0.111
(i) follows because, among all ways of placing the 0.117 exploration proposals of action within the third phase, assigning them to the first 0.117 timesteps minimizes the gap between the empirical average utility of actions b and a.
Therefore, when 7 0+, the observations of Instance and Instance 2 are the same with proba- bility at least g. Then, with probability at least g according to the discussion above, any learning algorithm will satisfy one of the following:
Linear regret timestep T:;
Linear regret at timestep 27;
Linear regret at timestep 47' in either Instance 1 or Instance 2.
When 5
3log at each timestep the action with the larger empirical average utility is ranked first
200
with probability at least 1 2I Taking a union bound over all timesteps, we obtain that this action is ranked first at every timestep with probability at least 1 - O (T-1). Therefore, it suffices to consider the limiting case 7 + 0+, which completes the proof.
E PROOF OF THEOREM 5.1
In this section, we proved the high probability bound for the utility estimation error, and with that, gave the regret upper bound of our algorithm under InstUtil Rank feedback. Next, will introduce the key lemma we used for utility estimation, Lemma E.I] which shows that the ranking of K actions can be decomposed into pair-wise rankings.
23

---

Published as a conference paper at ICLR 2026
Algorithm Utility Estimation with Action Permutations: Estimate {o(s)) mn
fol*) un with |a(5)] K for all
1: Input: A set consisting of m permutations of actions
E [m']. and temperature 5 > 0.
2: for 2....... A 1 do
3: for s ......... m do (8) (4) defined as Calculate 3.1 3.2
4:
Σ
(((()) (5) (1) = aa,a' (6) (k) = al Al i <i)
E ( a² o (k) = A and and lt)
n
AKE[K]
5: end for
Let T, = E [m'] :nj1 + n22 0}
(x)
6:
j.1
# 7: Let sig (x) (0, + R = log I- be the inverse function of sig(-). The utility of action
al is then estimated
ū(a') Proj rsig
[TS]
1 Ever, +n
[ 0
[Tyl O.
8: end for
9: Return (ī(aa), ū(a"),)())))))))))(()))) ................................ (,l
E. PAIR-WISE UTILITY ESTIMATION
Lemma Lemma E.I shows that, when the number of proposed actions K > for any two distinct actions b (t), the expected fraction of (a, b)-pair (i.e., pairs formed by choosing one occurrence of and one occurrence of b in the multiset (1) for which is ranked ahead of in g(() equals
T (n(9 (a) u (1)
sig
Equivalently, the induced pairwise marginal is the same as in the K case: matches the probability of observing the permutation (a. b) when only and are proposed. Related pairwise- marginal identities appear in Hunter (2004) p. 396); Lemma Lemma E.T extends them to multisets (allowing repeated actions).
Lemma F.1. Let #s =a)=E (a' represent the number of elements in a multiset S that are equal to a E A. For any utility vector u, temperature >> O, a multiset of proposed actions S with cardinality (S) K, and any two actions a + b E S, we have
1
E.
Σ
K
K
a)) - (o(k)) 1 (o(k))
sig (u(aa
u(b))
#s (a)
is (b)
k1
k2=k
The expectation is taken over the distribution of the permutation under the ranking model (LL).
The proof can be found in Appendix E.2 With Lemma E. the general cases where K 2 actions are proposed can cast into the case with only two actions being proposed, by enumerating all possible action pairs. Therefore, estimate ((() (as) for some a² E A, we will first construct an unbiased estimator of sig (")))(())))))
using Lemma R.1 for all timesteps E +
when both a² lAl E o(*), Since we have assumed without loss of generality that u (*)) (al44) = 0.
these values coincide with sig (a')))")) Then, by Hoeffding's inequality and the monotonicity of
the logistic function sig(?). with high probability, the mean of the logistic function estimators will be
24

---

Published as a conference paper at ICLR 2026
bounded between the minimum and maximum of { n
sig
(a))
(a*)
By Assumption 4.2
m+
(a')
since the utility vectors are changing slowly, that mean can be shown close to sig
With
good estimate of sig (a') we can then take an inverse of sig(-) to estimate u (a²). This
estimation algorithm is summarized in Algorithm and analyzed in Theorem T below.
In the following, we will prove Theorem 5.1 which gives the estimation error bound of the utility vector for each timestep.
Theorem 5.1. Consider InstUtil Rank and Algorithm 7 Suppose each action is proposed independently with probability at least > 0 at each timestep E [T] and let w(t) Estimate )==-m/+1)- Then, for any E (0,1) and 2 m'. when m 2 2log (3),
with probability at least
6, the estimate ū satisfies,
+
4LA1 log
1 (t)
(0)
u (a+1) u (1)
p
Proof. Due to the symmetry of timesteps, we will only prove Theorem 5.1 for t = mm' for notational simplicity.
For any j E [|.A] 1J, we assume that the probability for action at being chosen at each timestep is at least p. Let my denote the number of timesteps (out of m') in which both a² and al-1 occur in the proposed actions. By Hoeffding's 's Inequality, we have that with probability at least 1
m V
m 2
2 log
m. 2 E [mi]
log
2 m'p 12
2
We define
nj
(8) = Σ 1 ((())
(5) (i) = a², 0 (5) (k) = a
and
< k).
<.kE[K]
(8) = Σ 11 (0(()) (0) (i) = a² o (+) (k) = a |41 and > k).
n22
[,KE[K]
and the estimation of u/ (ai)
(5)
(a²)) Proji-
Tsig
1 Σ
1
(5) (3)
0)
n
5.1
mi
n2
(8)
+ m
(8)
Hence,
m!
(4) nz,1
=, 00 0).
1
+
By Lemma 1 since (alA4) = for every s E f1,2..... m'), and noting that n n + (e)
n2 =
#owi(a)) Hol (al-1),, we have
(e)
(()( - u(t) (al41) [(0)))))) sig (a)))
E Eg(
(4)
n
(x)
j.1
+
n
(8)
sig
T
By Hoeffding's Inequality, we have that with probability at least 1 2TA
5
mi
Σ
T
11
(m (5) (3)
nz,1
n3
> >0)
n2 + n22
n
(s)
(s)
sig (} (
5
2m1
log
(4[A)
8
1=1
25

---

Published as a conference paper at ICLR 2026
Let ((mmm))))))))))))) (a²) [-1,1] be the scalar satisfying
sig (aal)))(aa))
1 Σ1
n n2 > 0) sig (a))
mi
Since the logistic function is monotone and continuous, un ).2 (a²) is unique and must exist. Then, with probability at least 2|A|'
5
( u1
((a))
(a²)
-u u (m()')))aa)))
sig
sig
T
(+)
))
sig
sig
1
j,1
(8)
+
13,22 > 0)
sig
1 (uudd)) (ad)
n1 + n2
s=1
(a)
n3
(8)
> 0
3,1
sig (1 (ul())i((a))
m1
n2
3,1
(5)
+ n1
j.2
(5)
1
4|A1| 5
log
2m1
uses the monotonicity of sig and the property of projection.
For any u E [-1, 1]. we have
dsig
(4)
sig
11
1 sig
(-
21
du
T
(- ( 1
2
sig
sig
1
(-t) ) 2
1
sig
e + 1) 2'
Since sig is monotonic, by Taylor expansion and the fact that ((m') (a²), u(m²)) (a)) E [111, 1]. we get that with probability least
"TA
7 (i(mnn(a))) ( S (et (et+1)²
1
4|A1]
(a²)
log
2m1
8
Lemma E.2 in the following shows that (m²)) (a²) is bounded between the minimum and maximum
of {u(*) (a²) ) mi == Then, by further utilizing the assumption that the variation of the utility vectors small, we can bound the distance between (mm)) and (m²).
Lemma E.2. Let Fi...., Fn [-1,, 1] and sigavg = 1/2 Ei sig(z;), we have
min v; S sig (sigavz) S max Ji;- iE(n]
*E(n]
The proof is postponed to Appendix
Hence,
(a)))) m
x=1 mmax (aa) m"
(m ), (a²)
min
26

---

Published as a conference paper at ICLR 2026
Finally,
a( (a') um(m
ST (e +1)
log
4|A]
+ (u(mm'x'00 - x (m (aa)
2m11
St c +1)
V
2m1
log
[|[A]
6
+
+E (1,,....... -13
max
v(() - um (
m'
St
c + 1)²
V
2m1
log
4|,A]
+
u ((tt))(a))) -u('
When m'p' 2 2 2oo (g), with probability at least
2'
mi 2 m'
2 p-
By union bound, with a probability least - ( + )(²)). we have
(a') (mm)) (a') ST (et+1)
m'y² log
4|.A|
m
((++)) (a') (a))
V
Since at can be any action other than alAl, by applying union bound, the following holds with probability at least 1-6. 6,
T e + +1)
log
m'
| um/
[e((011) - -2(0)) -
P
m'
Remark E.3. Due to the monotonicity of the logistic function sig, the following two projections on sig (+) are equivalent:
12 min
(-1)
sig 1
Projisig(- +))gg))))))))))) sig
max
sig
-
sig
Proj (x)
min (max (ar, -1), 1)
sig
sig
E.2 OMITTED PROOFS
Lemma E.1. Let &s (a) Ea)== Eares (a'= = a) represent the number of elements in a multiset that are equal a E A. For any utility vector u, temperature with cardinality (S) = K, and any two actions a + b E S, we have
0, a multiset of proposed actions S
K Σ
(u(aa
u(b)
ts (a) is (b) E
(o
a) 1 (o(k2) =b) s
sig
The expectation taken over the distribution the permutation under the ranking model PL
Proof. We will abuse the notion S from permutations to subsets of actions. When proposing a set of actions S, let denote the event that is ahead of b the permutation given by the environment.
In PL model, the probability that action a ranks before action b is that
PPC. P(( {a.b) a < blT,u) exp (Fu(a)) exp (b)
exp uu))
27

---

Published as a conference paper at ICLR 2026
By definition, let the multiset of the K proposed actions be S. Then, the probability of the K-wise permutation is
K
exp (+ (or (k:)))
P (o S, u.
II
(E.1)
Σ boz
exp (-u (a (k2)))
Recall that E(S) denotes the set that contains all the permutations of the elements in S. Hence, we have
E
Σ
(o((k)
= a) a =b) s
kg
k
K
Σ
P(
Σ
Σ
1 (a(H)) = a)) (a(k2) = b)
(EI(S)
k2=k1+1
K
K
Σ
P(o18,T,u)
Σ
Σ
1 (o(k)) = a) (o((k) 6)
(E.2)
OEI(S): a())=a
k1
K
Σ
S,
Σ
Σ
(o(k)) a) (o(k2)) = b)
(E.3)
(E)
k1=1 k2=
al))=b
K
Σ
P(o S Σ
Σ
(k(h)) = a) (o(h))) b).
(E.4)
DEDIS): (1)g(a.))
R2 k1+1
We deal with E.2 first:
Σ P u)
Σ Σ (o(k))= ( b)
rEX(S): o()==o
k1
K
K
Σ oEE(S): =(1==a
P(o|S,T,u)
(t((b)+ + Σ
Σ
(a(k)) = a) (o(ks) =b)
2
K
K
# (a))==aa
Σ
P(o
Σ
Σ
(a(kk) a) ( b)
OEE(S):
2
o(1==o
=+s(b)P(a(1) = a (,
K
+P(o(1) = a u|S,T
Σ (olSS(a).nn)
Σ
(o((k) a) a) (a(k2) = b)
(EX(S((a)
k1=2 ku=k++1
K-1 K-1
al -0) (((() a
Σ
Σ (o(k)) = a) 1 (o(k2) = =b) 18
Similarly, for E.3 we have
K
Σ +ED(S):
( S, Σ
Σ
( a) -1 (o((2) -)
Na 41
a(1)=b
KK1 K-1
=P =P S,
Σ
Σ
( =) (0)())))))
15\ 18
1 kz=
28

---

Published as a conference paper at ICLR 2026
Let Unique (S) be the set of non-repeated elements in S. Then, (E.4) can be written
K
K
Σ
( S,
Σ
1 (a(kk) a) (a(A2) = b)
dEt(S): ((1)
k1=1 ka=k1+1
K-1 K-1 Σ
E ((o(1)=c(S,,,u))
Σ
(o = a) (o(k)) = b) s | {c}
-
cEUnique(S): ogfa,b)
Ay lig k1+1
Next, we will use induction to show that for any actions a + S, the following holds:
(o(k)) a). n1 (a(k2) b) 8 + (0)sig u(a) -u(b) -bbb) (E.5)
E
Σ
Σ
Base case, 1,
When ts(a) Hs(b) 0, E.5
trivially holds.
When |S| 2 and #s(a)
(b)b)
K
E
Σ
Σ
(o((k) = a) (o(k)) = b) I8 =P = ((a,b)) ,, r,
Ay 1
kg +1
(u(a) =u(b)
sig
(u(a) -u(b)
(
Lemma E.4. For any utility vector u, temperature > O, and a multiset of actions S, the marginal probability of any action a A ranking at the first place of the permutation can be written
exp (2
P (o a S, u) #s (a) Eves exp (a
The proof is presented later in this section.
Induction step. When (E.5) holds for any with [S] = K 1. Then, we will show that still
holds for any S with |S] = K. By Lemma E.4 E.2 is equal to
(b)P (1( = a S,T, u)
K
K
+P(((1) = a S,
E
( (a),
Σ
Σ k
(o(k)) = a) (o(k2) = b)
(a))
exp (a
=#s(a)+s(())
Eves exp (Fu(d')
exp (+ (a))
(s((a)(a) (8) (u(a) (u(a)- (u()) )) u(())
+ +s(sa)
Ex'ss exp ( (a'))
exp ( (a))
+ (s(a) En expeseeplii exp (a') (#s((a) - 1) +s(b)sig (u(a) - u(b)
exp (au
=#s(a)+ss()) Eves exp (Fu(d')
Similarly, E.. is equal to
exp ( u (b))
(u(a) (u(a)-u(b) u(())
(b) Ev'es exp ( (a'))
+s(a) (#s(b) - 1)sig
and E.4 is equal to
1 exp ( uu (a)) + #s(b) exp (b))
exp
*s(a) +s(Ossig (u(a)= u(b)
Eves exp (a)))
29

---

Published as a conference paper at ICLR 2026
Lastly, by summing them up, have
K
B
Σ
1 (a((1)) a) (o(k2) =) i5
k=
Edess exp (a)) #s(a) exp ( (a)) + exp (#) *s(b)sig [u(a) u(6)
exp (a))
(t (b)
En'es exp (a)))
u((a) u(b)
+ #s(a) (b)ssg
t
Note that sig
u(m)=a(b)
expl أ
exp
Mial +exp
Therefore,
exp( السساعم +1
exp
K Σ
au(aa u(b)
E
Σ
((((k) (okk)) b)
=ts(a) +s(bss
k1
and we complete the induction.
Lemma E.4. For any utility vector u, lemperature O, and multiset of actions S, the marginal probability of any action a E A ranking at the first place of the permutation can be written as
exp ( (a))
P (o = a U, #s (a)
EV'es exp (cu
Proof. Let Σ (S) be the set containing permutations of By definition, for any action a E A.
IS
exp (+u (ar (k:)))
((a(1) a
Σ S,T)u,
Σ II
2k2mh exp (2 (a (k2)))
rEM(S):
OETSS:: a(1==a
k1=1
o()==o
Since there #s(a) action in S, by rearranging the terms, have
exp (+u (a))
IS|-1
exp (+u (ki)))
PP (o(() a u,,,,, =t((a)
E
II
Σ Ea'es exp (Fu(a')
S exp (+ (a (k2)))
(E)(S((a)) ki=l
2kgnk
expl (
=#((a)
Σ P Valsstaa,.n (a),,,))
Ev exp (Fu(a')
(E
=ts(a) exp (tu
Enees exp (+u (a')
Lemma E.2. Let F ........ Fn E [1 and sigave = 1 E sig(2;), we have
min x; S sig (sigavz) iE|n]
S max Ti- iE|n]
Proof. The logistic function sig(z) is increasing monotonically with respect since dsig (exp(z)+1)"
dz
exp(x) > 0. Then, without loss of generality, let æ1
< x2 S ... & Fn- Thus, sig(21) <
sigavg sig(
Since sig (x) is monotonic and continuous, there exists only one Ç E t,1, such that sig(C) sigavg.
F ALGORITHMM AND DIAGRAMS
In this section, we present the algorithms' diagrams and pseudo-code of learning with InttUtil Rank and AvgUtil Rank individually.
30

---

Published as a conference paper at ICLR 2026
Timestep t (Full-Information
(6-1)
{ol+)) I s==max(t-ma
(c)
π ((+1)
Estimate(
Oracle Alg(.)
Timestep (Bandit)
i
==1
1(A) [A]]
7
{ st 11,1+
itt
-1 (1-1)
(1+1)
Estimate
Oracle Alg(.)
Figure 10: The diagram of Algorithm 2 with InstUtil Rank under full-information feedback (top) and bandit feedback (bottom). + represents the addition of (1-7) 7) times the output the Alg and ? times a uniform distribution over A.
F.1 THE ALGORITHM AND DIAGRAM FOR Inst Util Rank
We present the diagram and the algorithm pseudo-code learning with InstUtil Rank and Algorithm 2
Figure TO
Algorithm 2 Online Learning with InstUtil til Rank Feedback
1: Input: Action space A. any full-information no-regret learning algorithm Alg with numeric utility feedback, selected action number K, estimation window size m, and exploration rate y.
2: Initialize (1) as uniform distribution [ over .A
3: for timestep t = 1, 2........ T do
4: if inllmmnfornnttion setting then
5: K [A| in this case. Select all [A| actions.
6: else if Bandit setting then
7: Sample K actions independently with replacement from (t).
8: end if
9: Receive a ranking feedback (t) (1), (1))
(K) from the environment.
10: (+) Estimate
(()))) m==mx(t-m+1_1) by calling Algorithm
if Full-information setting then
12: (t-1) Alg (ū()))
13: else if Bandit setting then
1(A) (1-1) (1 A)g (al=)) .=1 + + 7
15: end if
end for
31

---

Published as a conference paper at ICLR 2026
Timestep t (rull-Information)
(tmar(t-m+1.1)
x(++1)
Estimate(-)
Oracle Alg(-)
Timestep (Bandit)
715) empirical
1(A)) 7 TA
(obi)
max (1
(1)
(
(a m))
π ((+1))
Estimate(.)
Oracle Alg(.)
Figure 11: The diagram of Algorithm 3 with AvgUtil Rank under full-information feedback (top)
and bandit feedback (bottom). O represents copying the estimated utility vector for t times. represents the addition of (1 ?) times the output the Alg and y times a uniform distribution over
A.
F.2 THE ALGORITHM AND DIAGRAM FOR Avg Util Rank
We present the diagram and the algorithm pseudo-code of learning with AvgUtil Rank and Algorithm 3
Figure II
G PROOF OF THEOREM 5.2 (FULL-INFORMATION)
In this section, we prove the regret upper bound under Inst Rank and full-information feedback.
Theorem G.1 (Formal version of Theorem 5.2 (Full-Information)) Consider Algorithm lnd full- feeebaak For any E (0, 1). T 0, and any no-regret learning algorithm with numeric
utility feedback, Alg, with probability at least (1 8), by choosing m = ( 3 (log (AAITT) R(T). satisfies
exterral
()
Alg, (u(1)) 1=1
2T c +1)
(pl:) $ T3
log
(4AT
+2 (p())
3 #
log A|ATT)
1/2 )
+ 4 (p(0) *+4(p10)
7 log
4|A[TT)
8
8
(G.1)
32

---

Published as a conference paper at ICLR 2026
Algorithm 3 Online Learning with AtgUti Rank Feedback
1: Input: Action space A, any full-information no-regret algorithm Alg under numeric feedback, selected action number K, estimation window size m, exploration rate 7, and block size M.
2: Initialize 7(1) as uniform distribution [ over
3: for timestep t = 1, 1.2..... T do
4: if Full- Full-information setting then
5: K = |A| in this case. Select all |A| actions.
6: else if Bandit setting then
7: Sample K actions independently with replacement from x(1),
8: end if
9: Receive ranking feedback g( (2)) olt) (K)) from the environment.
10: if Full-information setting then
davg Estimate
(t)
(a(s)) x x-x (1- by calling Algorithm
12:
((-1) f Alg
(6) (avg
ie., the strategy generated by Alg by setting all utility
vectors from timestep 1 to L as Mavg- else if Bandit setting then
(()
13:
14:
empirical = Estimate
((o(s)) J==max(t-m+1.)) by calling Algorithm
15:
Let (*) (a) == E fo(e) (a) for any E A as the number of times action a has been
proposed up to timestep l. Then, the estimated average utility
14/M]
(la-M) (a)n (a:20 (a) ((le-1)M (a)n (3a0)
U avv-- Lavg-est(1) (a) = [c/M]
(a)
2
10) nnll [a)
12 M
<< M
(F.1)
[Let x T Tompirical (a) = (a) for any action A}
((1 ((i(t)
((-1)) (1 A)
(m 5=1 + 1(4)
17: end if
18: end for
Proof. By Theorem 5.1 we have
T
exterral
R( external
Alg.
((t))
t=1 )
T
T
(1) 7 - x(0)
7(()) मे - x7(1))
max REAA
max
REAM
t=1
Σ (1()) (t) ū1()= ने n((1))
max
# REA
(1)
[(1)
1 n (t)
max
REA-
When 2 m, the estimation error between ()) and (t) given by Theorem 5.1 with p = 1 since considering full-information feedback. When m,
u
(1)
max 2 n (t) REAA
4m.
33

---

Published as a conference paper at ICLR 2026
For any given 6, require the utility estimation bound to hold with probability at least 1 4. then by union bound, with probability at least 6,
R (TT eexternal
R(T) exxterall
Alg, (i(1)) )
1=1)
log [ATT
(e +11 +1)²
T + 2m (p(T) +2(T))2)
2t
log (41A1T)
(4)))r)
1/2
By choosing m p
we conclude the proof.
H PROOF OF THEOREM 5.2 (BANDIT)
In this section, we prove the regret upper bound under Inil Rank and bandit feedback. Theorem H.1 (Formal version of Theorem 5.2 (Bandit)). Consider Algorithm 2 and bandit feed- back. For any E (0, 1), T > and any no-regret learning algorithm with numeric utility feedback,
Alg, with probability at least 8), by choosing
p(T)
32| K
T pirj
log
BLAIT
R(T)) satisfies
2
(T)) <R ) external
Alg, (x()))
+ 2
27 log
2
+
TK
e
+
+1 11
(plli)
T
A
(H.1)
64|,A/
(per))
8|A[T
128 A
T
88AA
+
T log
log
K
8
K
p(T)
6
Proof. We define:
R max REAM
(1)) ,7 11))
Then,
R(T) (T) R external
R(T) extterall
R(()
+ R(T) R (T)
AAgg, ( 1=1
R external
Alg,
(
Note that can be bounded by bounding (7() - u(() || as in Appendix G
is sublinear by the The proofs are
definition of Alg. Next, we will introduce lemmas that individually bound
postponed to Appendices H.T and H.2
Lemma H.2 For any T > 0 and 8 E (0, 1), with probability at least 1 8:
R(T) R(T), external s 2 2T log (1))
Lemma H.3 (+). The difference between R(T) and exxteral
(Alg, (z T satisfies:
T Alg,
(2(0))
R(T) exterral
t=1 $ 2TT.
34

---

Published as a conference paper at ICLR 2026
With Lemma H.2
and Lemma H.33 under the conditions in Theorem 5.2 by letting Theorem 5.1
hold with probability
at each timestep and using the union bound, with probability at least
27
1 - 6, the regret satisfies
R(T)
<R
R.
Alg.
T 22()))
21(1)
+
2
27 log
1=1
6
c 1)
log
SLAAT
T
2m
((() +2) + 7T.
p
m
In this case, each action A is chosen with probability least p that satisfies
p21
2
exp
-K
Y
A
[AI
Y
7
)
2
Y
7 A
21
1 -
K
+
K
K
K
IA
[A
A
2
Since K [ $ 1, we have
Ky
K
2
K
=
p2 2 AA
2
A
2
[A)
By letting y
p(t)
T
m
A| K
(pir))
log
(8AAT)
we have
(T)) S R
external
Alg,
((t))
T
O
T (p()))
T log
))
--
[=1
The condition m 2
is also satisfied since
K-A4
8|A
4T > log
mp
log
16 A
H.1 BOUNDING
We will show that (T) R exxteraal is sublinear by using standard concentration bound.
Lemma H.2 ) For any > 0 and 8 (0, 1), with probability at least 8:
R exterral s <2 / 22 log (
Proof. Let
d 1 1 Σ (a) (ui)), x!)).
K
aEo!!)
By our algorithm design, each element of (t)) is sampled i.idd. from (1) with replacement and the update rule of (()) is deterministic, E ((() {o(0))(-1 1-1 { (-1 O, so that {d(t) } is martingale difference sequence.
Due to the bounds of 1 Eecoro u (a)l S (000|| < 1, we have
a
1 I
Σ
Σ
(())(a) - (x(1),+(0))
Σ (a + (a((),((t))
/ 52.
K
aEole)
aEa!')
35

---

Published as a conference paper at ICLR 2026
Furthermore, we have
Σ d
K Σ
(l) - Σ
(((10))=()))
(1l0 ,111)
aEol!
E
(( (u())))
((ul), (u(0)=(()))
Σ
(u(1)
Σ u (oli1)
max REAM
max REAM
=R(T) R(T).
exxterall
Next, we will introduce Azuma- Hoeffiigg inequality finish the concentration bound.
Theorem H.4 (Azuma-Hoeffding inequality). For any martingale difference sequence Yi.... Yn such that Vj E [r] ag S Y by. the following holds for any w 2 O.
2w2
P
Yj
w S Sexp
Σー= (bg -a,)²
Then by Theorem H.4 with probability at least 1
R(T) S (.).eeal + 21 2T log (
H.2 BOUNDING
can be bounded by O (7/"") by definition of (t) in Algorithm 2
Lemma H.3 (+). The difference between R(T) and eexteratta
(Alg, (ū(')) satisfies:
Alg, (2(0) (2()))
R(T) R(T). externa
s 2nI.
1=1
Proof. Let (t++1) Alg (ūil)) (= Then,
R(T) exterral
Alg, ū(t)
T
T
x(())
(1)) 7 x(00)
max REAM
max
c=1
REA4
(1) - - 2001)
u (1) #(1)
(1-
1 (AA
TAi
(1101)
((4)
11)
ū (t)
+
22TT.
U
I PROOF OF THEOREM 6.2
Theorem L1 (Formal version of Theorem 6.2). ConsiderAAggUin Rank with full-information feed- back and Algorithm 3 For any E (0, I], > 0, and any no-regret learning algorithm with numeric utility feedback Alg that satisfies Assumption 6.1 with probability at least (1 - 8), by
36

---

Published as a conference paper at ICLR 2026
choosing m = 2 log
(1ATTT) (R(T)xxxerrn satisfies
Alg, (u(') +AlT (e++1) LT + 47 log
[4|A|]
R eTttttrrl
<R
(I.1)
+ 4|ALLT'S (log T +1) (log (4|A1T) )) + 4|A|LT'S log
[|AAT
6
Proof. Let #(++1) Alg (nll)))==) Le., the strategy generated by Alg when the ground-truth utility vectors are given. Then,
Alg, (u(t)) )
R exttorall Re())exttrnal
(1 ----=(0)
Σ (u()) क -F(1))
max REA
max
REAA
u x(t) x 210))
m-1
T
(t)
((+)
| - n x000 (u())
+
m
(1)) n1(3
<2m +
tm m
By Assumption 6.1 and Theorem 5.1 for any 2 m. with probability at least
8 we have
r ( + +1) 2 log
1AAIT
(-1
1(1)
=(0)
$ Lt
(0) wavg
SLIVIA
Σ
m
S s+1
s=t-m+1
Then,
(2((1)) T
eetteral
exteeral
Alg,
t=1
log
4/A/T g
T 7 + 2T| Σ
<2m + T|AlT +1)²
Σ
1
8+1
m=
==t --t-m +1
log (A[A[T)
<2m L|AlT (et + +1)²
T
LI
m2t + 1)
m
t=1
log 4AATT
<2m + I|AlT (et +1)²
T
Lm ||
Σ
2|AmmL7
m
log (AA//T)
<L|A|T (et + +1)²
2 2m Lm² |Al (log T + 1) + 2 2.AmmLi ALL..
m
By choosing 2 log
(AATT) (
have
R(T) external
< (T) external
T )Tm) + (TT log Alg, ( ) )=1
4[A[TT
8
log( ?! n
Moreover,
where 1 since considering full-information feedback.
37

---

Published as a conference paper at ICLR 2026
J PROOF OF THEOREM 6.3
Theorem J.1 (Formal version of Theorem 6.3 Consider AvgUtil Rank with bandit feed-
back and Algorithm 3 For any E (0, T > 0, and any no-regrei learning algo-
rithm with numeric utility feedback Alg that satisfies Assumption 6.11 with probability least
(1 -δ), by choosing m 2T
|AI log 12[A|T
min L (P(T)) 11. and M
max { {TT (pCN) + |A|* log
AR
2m J. R(T) satisfies
8
R(T) <R( exxterrl
Alg, (u(tt) (u(t))= 1-1)
3 + LLATTW + -2 + 2V 2T log 8
(I.1)
where
[A| log 3 Co
?
W(T) 4Cs (log T +1)
T
e (e++1) T/T|
log
12|
5
16K Co M
M
7
m
MM (log + 1) p(T) 2M (log T T +).
Proof. In the first part of the proof, we will bound
empirical "empirical
(6)
According to Theo-
rem 5.1 and union bound, since each action is proposed with probability at least 6 for any t. 2 m, we have
[ with probability
at least
3
T|-A| (et + +1)
12|A log
5
Σ
(a+1)
empirical
u empirical
u
emmiriccal
cmpirical
m
S m=
Let # 4om (a) be the number of action a E A being proposed in (!!) Then, for any t E [T a E A, we have
and
Cempriical (a) Et to(o (a) + (1) (a)
(++1) "empirical (a) u (t)
"empirical (a)
u (1)
cmmirical (a)
E to (a) + # #o (a)
Vempirical (a) (1-1)) (a)
(t)
(1++)) Hor40) (a)
+
1=1 #olo) (a) #o(e11) (a)
E #orss (a) to (a)
<K eemiriiaal (a)
(((+)((a)
K
Σ
(a) # (a)
Σ -a=l # 4o00 (a) + # #ouID (a)
Next, we will show that since each action will be proposed with probability at least D with high probability, there is a lowerbound for E tole (a) for any timestep t.
Lemma J.2. Consider the case when actions proposed with probability at least p >> 0 each timestep. Then, for any 5 > 0, any action a E A, and T > 0, with probability at least 1 - 8, the
following holds for any t log( (AIZ)
P
[AT 8
log
3F E (T), such that t
I 1l St and E (t)
(I.2)
p
38

---

Published as a conference paper at ICLR 2026
Proof. For any log LAIZ
and action a E A, the probability of (J2) does not hold is at most
P
loc 14
[A[T]
(1 p)
I exp
-
log
8
=
A
Therefore, by union bound, with probability E A.
5,
J.2
holds for any [2] and any action
For notational simplicity, let Cg- log 2r
According to Lemma J.2 with probability
least 1 3| for any timestep / 2 Cg. we have
Σ (a) (a)
(I.3)
C
2CB
By union bound, J.3 holds for any action a with probability Therefore, for any E [T' - 1] and A, we have
3
(t) Cempirical (a) u empirical (a) 4K C8
(1+1)
t ++1
It holds for 1 < Cs- because 4K FT 2 4K 2 2 and all utilities are bounded in [-1, Finally, by Theorem 5.1 and union bound, with probability at least 1
3 we have
T|A| c + +1)
12
log
[-1
U
(t) empirical
u empirical
4KCs
Σ
m
s s
s=t-m+1
Let ne (a) = E. foon (a) for any A as the number of times action is proposed up to timestep t. For any a E A and 2 M, we define
[/M]
(o-M) Cempirical (a) (a)
((s-1)M) (a)n (a)
cempirical
U Mang est (a) =
[t/M
(x) ()ll-)))a(aa)
L/M
(s.M) empirical
(a)r((-10) (a) eempirical
1)M0 (o)n((=-1))1)))
(+)
avyg- Bast-est (a)
[L/M]
(() nn((s-1)M)
Note that define u (0)
dempirical (a)
empirical
(0)
(a) Mempirical (a) 0. For 1. M, define
(0)
uuvg-est (a) Mavg-
(t)
(t)
0 for any action A. In the rest of the proof, we will bound individually.
(1) u avg est
avt
(t)
and
u avg est Wavg
(t)
(1)
(t) unvg-
J.1
Uavg-es est
UPPER BOUND
For any a A, we have
W/M
12 (s)
(+t))
Wavg-est (a) - -Wavg -2avk-oor (a))
5
(++M)
Cempirical (a) - u (e:Ad)
"empirica (a)
1/M
(( - n nnll- 11.1)
1
Σ
n n((=-1).M))a)
((-11)M) Pempirical (a)
(a)
((--1)M) Nempiiical (a)
[t/
n(a.M)(a) n - 1>MM
39

---

Published as a conference paper at ICLR 2026
According to Lemma J.2 n(= (a) n ((((-1))M)aa)
M 20%
when M 2 Cg. Therefore, when
M 2 Cs. since n n
a
I s M, we have
Uavg ran(a)) (a)
u "avg uavg-est est (a)
(t)
[e/M]
2C
Σ
((--1)M) @ (a) - Tuaaprica (a) Vempirical (a)
-empiricaa
1
J.2
avg est
Have
UPPER BOUND
For any a E A.
u aast est (a)
(4)
avg (a)
[e/M]
(e-M) Vempirical (a)
Cmmpriiaal (a))(((-1)54((a)
((--1)M)
Σ
Wavg (a)
[t/M]
(() n(((=11)M) (a)
[e/M] (+.M) empirical (a)n (M) ut emmpricca
((--1)M) (2)n((6-1)40(a)
(MM
L
(a) =n((=-1)A0(a)
uavg
(c) avg
(a) (MMM)
Note that + can be bounded by
(M [L/MM)u (M1I/M
E Ei=M|A/M/H+ (a)
(MLe/M))(a)
M
(M/M/MM (MI1/MM)(a
(a)
(a) -
2M
Havg
M [1/M+++
For
we have
[4/M/
(s.M) Cempirical (emptrica(aa)((e (a)n(())))a) uI emmptrcall
((s-1)Af) (a)m((s-1)M)) (1)M))
Σ
1
ulos(a)
Lt/M
(o (a) (n(+-1)MM)
M
WMM Σ
(a) (a) -empirical empirical
(a-M)
s.M
(l))
[t/M]
M)) (((o-1)MM)
M
1)M+1
(a-br) Mempirienl
(a)n (a) (a) (1a-1) (a)n (G 1)
When (()-M) (a) 1n((s-1)M)) 0, both
compirical
and
nio 2(02)aa))1 Da)
M Ex 2 1)M+1 ((d))(a) (a) are in the convex hull of { (1))
6'=(6-1)a44) Therefore,
+.M
(s:M) emmpircall (a) (M (a) emmprrical (a)
Σ
u (
(1 (a) 1)ar))
M
s'=(s-1)M++
((('((a) a (a)
max
(8 101 " SC.M
MM--1
Σ
uls't1(aa) - (a))
(1=
40

---

Published as a conference paper at ICLR 2026
Therefore, for any t 2 M and A, we have
M-M-1
(1) Mavg-eat (a) u Lo (a)
Σ
w (1 (a) - (1) + 2M
S
LI/M
1)M+1
By combining all the pieces together, we have
-11)
Mavg- est
(a)
u (a)
1/MJ
2CB
Σ
(a
empirieal (a)
21 Cempirient (a) +
(o.N)
v ((a-1)M)
ampirieal
(a)
u cmpirical (a))
((--1)M)
t/M
sml
Le/Mdj
8-M-1
u1 (a) u((2(aa)++ 2M
+
Σ
Σ
[t/M]
d 114+1
Then, since
[T/M]
min((s+1))
[T/M]
M
Σ
Σ
Σ
L1/M]
t=s.M
we have
U uavg- eest (a) ((( (a)
(t)
1
(t)
Mavg-cen cut (a) - (1)
Wavg
(a)
+
Uavy -avg-est (a) u
[T/MJ Σ
[T/MJ
<20s
(olnn Tempirical (a)
Vompirical (a)
(s
+ (
(a)
eempirical (a))
(M)))))M((a)))
((s-1)M)
Σ
M
[T/M|
8-
(llo't) - al07(oo) (a)(((())
IT/M Σ
M
T 2M
+
+
2M
t
[T/M]
Σ
7 M) Cempirical (a)
Vempirical (1)) +
(s-M)
(((o-1jad) 1jaff)
Cempirical
(a)
Vempirical
()--1)M)
(a) (log (LT/MJ) + +1)
sml
[T/M]]
M-M-1
(()++))(a) - -n())---())) ul)) (log (LT/M)) 2M (log T + 1) + 2M.
+ M
1)4+1
When s 1,
u ()M)
(a) u empirical (a) = 0 by definition. When 8 > 1, since M > 2m, we
empirical
have
4s 4
(s 1)M - m 22 (s 1)M/2 2 +2 (8 (8- 1--1)
8 M
M
Hence,
r|A| (et +
log
12(ATT
(a-1)M-1
7 1((s-1)M) (a) w w (a)
5s
+ 4KOs
Σ
7
m
8' +
s'=(s 1)M - m+1
T T|
(et + +1)
log
[2|A|TT 8
16K CA M
M
7
41

---

Published as a conference paper at ICLR 2026
Therefore,
T
Bavg est (a) -u (a)
T|Al]
c +1
log
12
<4C, [T/M] (log T +)
+
16KC
m M
M
+ MM (log T 1) P(T) 2M (log T + 1)
T2T
(et +
log
12|AIT
8
<4Cs (log T +1)
16KC's T
M 4
M
+ MM (log 1) p(T) 2M (log T + +2).
Lastly, similar to the proof in Appendix I let (1+1)) Alg ((ul)))=1)
Then, we have
Alg, (u))) 2 )21)))²))
R external T.. external
2 (t) ((1) - =700)
( (1)
| (11 =
SVIA Σ
T
(1 A)1 (
(w(())
1 (AA)
+
6=1
A
<(1 - (1--)VI1)
Σ Alg
(1()
=(0)
+ +
1 (A)
((8)
A
e=1
<VAA |4| Σ
Alg
(il0)-cstt s=1
(+)))
)
(1))
+ 2 2 /
t=1
Further, by Assumption 6.1 we have
T
T
VAA
Alg
(((1)
est
s=1
-(())
SLV
A
Lav est
2avg
1=1
<
x(1)
Lavg (c)
t=1
42

---

Published as a conference paper at ICLR 2026
By combining all the pieces together, we have
Alg, (z((1) I
R exxteraal (.()eextemd
1m1
T
T|A
(et +1
log
(2[|/[T)
8
m 16K C8 NTT
+ LAAT
4Cs (log T 1)
M
?
+ LATT M (log T + 1) p(n) + 2M (log +2))
(logT+2)) + +2 ATT
< R (T).exteral
Alg,
(2()) (2(())==]
T
1=11
(log (t))
1
LT
m (log (+))
2
+
LT
LMP + 2T
72
M M
72M
where Ô hides all the log T terms. Lastly, by Lemma
H.2
with probability at least 1
6 have
R S .externaaa
+ 2 27
2og log (5)
Moreover, by taking = min L (P(T)) à 1 m = 2T |A1
(2|AATT) and M
log
{4T (P(T)) - |A| log
[22 12
2m ). we can easily verify that m 2
2
A 1 and
M 2 Cz. Finally, by a union bound argument, we complete the proof.
K PROOF OF SECTION
Lemma K.1. For any T > 0 and sequence of strategy profiles (T(1),, TT ??)....,, TT),, the variation of ulility vectors of any player i E (N) satisfies that
Σ
u
(2)
u, 1
A
My
7 1011
(K.1)
2m2jml
where maxj Agg
Proof. For any timestep player i E [N], and joint action a_; XiziAA let π (1) (a
1i T5 (o,).
Then, for any timestep t. player i E [N], and action a, E Ars we have
(1) (a:) ui (1-1) (a))) s
Σ
ulaa'1 ai) ( - (1--1)
ui
d'Ex/=1
(Ui(ai)'ii) EXiri
a'
(1) - ((--11)
(Ui a' a' EX
|/ ---1111
As 1000
< (1) - '1 -
Further, for any a, , D' E [0. 1]. we have lab- a'8l = lab - ab' + al' a'Ul < a b - 6' +
la 10-ale a'lb' < la a'l 1b 81). Therefore, by recursively using it, for any a_ X As.
have
(a (1--) (1)1))( (a=
m (a.)
II m (1-1) (aj)
5 Σ
10 (0,)
m
[1-1) (a;)
141
43

---

Published as a conference paper at ICLR 2026
Finally,
"4 ui
(8) S vlAi - π
(t-1)
S
VA.
II A
Σ j'
[t
(t-1)
K.1 PROOF OF THEOREM 7.2 AND THEOREM 7.3
Before proving Theorem 7.2 and Theorem 7.3 we will show that when Assumption 7.1 is satisfied, the strategy variation is bounded.
Lemma K.2. Suppose Assumption satisfied. For both full-information and bandit settings, Algorithm 2 satisfies the following,
Σ a -(111) TTT
Suppose Assumption 6.1 is also satisfied, then the following holds for Algorithm in the bandit setting.
Σ (1)) x((t1|| +
Proof. For Algorithm 2nn and the full-information setting, the proof simply follows from the fact that ( 1|- and Assumption 7.1
For Algorithm and the bandit setting, we have
((++1) (+) (1 71 Alg ((x()) 6+1 )=1) Alg
((
(w))))
S
s=1
Thus, we can conclude the proof.
For Algorithm 3 and the bandit setting, for any t * (mod M). we have (()) Therefore, by Assumption 7.1 we have
((1-1) -Uavg
uag-
(1-1) (1)
<
Alg
(t-1)) avvg
Alg
i1 avg--est
((t))
s=1
Alg
(1-1) aav--ost
Alg
(1-1)
avg-est
((0)
Cemprrica (a)n (a) (1 Compiiiial (a)n (t- (t-2) (a)
(a)
For any (mod M), let
then we have
(())(a) nic (a)
(t/M
1)0arg-ost
(t-1)
u avg cett
avg csst
t/M
24 avg est
M
(1| @avgg-
+ +[/ull)
5 1
2M
VIAI.
1
Therefore,
(1-1)
-((1) < Alg
) 1-1
Alg
(2(()
( cest
s=1 )1
rat
==1
Alg (w!lizn)
t-1 )
)
( )
((uي))-))) s=ي
Alg
+ Alg
Alg
5=1
x=1
,=1
(4)
2M
-n + Lt
VIAl
t
= 2LM VAA.
44

---

Published as a conference paper at ICLR 2026
where (i) uses Assumption 6.1 and Assumption 7.1 time is bounded by
Then, the accumulated variation of x( over
T ((+1) - x: x S + 2
Σ
T/T 222/AAl
M
since there are at most M timesteps of E [T] satisfying & (mod M).
With Lemma K.2 we can prove that R. eexterrlaa is sublinear for any player E [N] by Theo-
rem 5.2 Theorem 6.2 and Theorem 6.3 Then, by the folklore result that ro-external-regret learn-
ing leads to approximate CCE (Hart & Mas-Colell, 2000)
Blum & Mansour 2007). Theorem 7.2
and Theorem 7.3 are proved.
Remark K.3. With the hardness in Theorem 4.3 under Avg Util Rank feedback, both
regret result for the online setting and the equilibrium computation result for the game setting hold (that cannot be arbitrarily small). However, computation result may still be possible when T - 0+: with such a deterministic ranking model, the best-response action against the history play the the opponents now available, precisely leading
for a constant т
note that the equilibrium
to the celebrated algorithm of fictitious-pla (FP) (Robinson 1951 Brown 1957). FP is known to
converge to an equilibrium certain games (Robinson) 1957 Monderer & Shapley 1996 Sela
1999 Berger] 2005) (with (slow) convergence rates (Robinson 1957; Daskalakis & Pan 2014
Abernethy et al. (202I), despite that it fails to be no-regret in the online setting (Fudenberg & Levine 1995 1998).
L PROPERTIES OF FOLLOW-HHE-REGULARVZEE-EEEEE (FTRL)
Firstly, we will define the strongly convex function. Definition L.1. For any integer n and a convex set X' C RR,", ie (bxx): X - R called co-strongly convex (Co 0) when
CD x²11
(x)) 2 (xx') + (Vi((z'), x x²)
2 x
(L.1)
holds for any x, x' E.
Specifically, if (L.1) holds for co 0, then we call v convex function.
Next, we will introduce the well-known no-regret learning algorithm of Follow- Thww-The-Reeee Regulaeegar-ized Leader (Shalev-Shwartz Shwartz al. 2012 Hazan al., 2016).
(FTRL)). For any T > 0 and at any timestep t E {0) [ - 1], given the utility vectors (uls)) ==1" the strategy timestep + π ((++1), defined as,
Definition L.2 -Follow-The-a Reg.-eegllaiize---eeeaee
(f+1)
argmax TEAA
A ΣΣ (ela)) (ul)),z)) )
(FTRL)
for some constant X > Typically, À is taken be (T
) for some constant r >> 0.
Next, we will introduce the smoothness of (FTRL)
Lemma L.3, For any -t-sonnyyy convex and differentiable function sb: A + R. FTRL satisfies
Assumption 6.1 and Assumption 7.1 with I. and VIAAl.
Proof. By the first-order optimality, at any timestep / E {0) U [ 1] for any two sequences of utility vectors (u())) and (e) ==1" let the corresponding strategy generated by (FRLL be
Inspecting the proofs of these theorems shows that readily derive upper bound (T( exterval that is tighter than the corresponding bound on RT) in the handit setting. Consequently, R. esterral can also
be bounded in games under the handit feedback.
45

---

Published as a conference paper at ICLR 2026
((++1) and x/ ((++)) respectively, we have
(o) Vep (xl+1)
x((+t1 x(+11) -0
(s)) Vesi (Tr(ett)) ,x x((12)
u
S 0.
==1
By summing them up and rearranging the terms, we have
(l))
n ((++1 - x 2 (ve (Te1((t1)) (V - -v (I((tt) x1((11) x((t1))
Since va is co-strongly convex, we have
(x(t1) 2 v (z((ttt
+ V (π((t11) x (1+1) - x1(t)))
CD
(++1) - (((t1) ?
2
s x
(((tt2)
2 인 ( + ( (1(+2)) T (((t1) - x((+2))
00
[((+1)
x((22))??
2
By summing them up and rearranging the terms, we have
(v (V(((11t1)) ( - veb (T((T1)) x((+]) - x((11))
2 co |- (1++1] - ((++1)|
Therefore,
co [ - x1(tt11?2 5
u (e)
u
(+) ((++1) - x((+1)
u (8)
|+(++1) -- x((21||
u
sm1
where (i) is by Hölder's Inequality. Then, | - n ((++]]
so that FTRL satisfies Assumption 6.1 with Furthermore, note that the results above also hold for sequences of utility vectors different lengths (not necessarily equal length simulta- neously). As result, we have
(((+1)) 70(0
1
VAAI Go
for any E {0) [T- 1J. which implies that
A in Assumption 7.1 for FTRL.
M CONCLUSION AND LIMITATIONS
In this paper, we studied online learning and equilibrium computation with ranking feedback, which particularly relevant to application scenarios with humans in the loop. Focusing on the classi- cal (external-)regret metric, we designed novel hardness instances to show that achieving sublinear regret can be hard in general, in a few different ranking models and feedback settings. We then de- veloped new algorithms to achieve sublinear regret under an additional assumption on the sublinear variation of the utility, leading to an equilibrium computation result in the repeated game setting- Finally, we justify the effectiveness of our approach by simulating routing the user's query to the optimal LLM. We believe our work paves the way for promising avenues of future research. For example, it would be interesting to close the gap between the lower-bound and the positive result for AvgUti Rank under bandit feedback, i.e., either show the hardness when 7 is a constant or achieve sublinear regret for constant without Assumption 4.2 Moreover, applying our algorithms to real-world datasets with ranking feedback, such as ride-sharing and match-dating would also be of great interest.
46


Reviews:
[{"review_id": "JHBx0ZKUyc", "reviewer": "Reviewer_xsDY", "summary": "This paper studies online learning and equilibrium computation when the learner only observes rankings rather than numeric utilities, in a fully adversarial setting. This connects this to finding coarse correlated equilibria in normal-form games. The authors consider two ranking models, i.e. InstUtil Rank and AvgUtil Rank, under both full-information and bandit feedback. They first prove hardness results: with InstUtil Rank, any algorithm suffers $\\mathcal{O}(T)$ regret for constant temperature $\\tau$. With AvgUtil Rank, when $\\tau$ is very small, sublinear regret is still impossible. They then show that positive results are possible if utilities vary slowly over time, designing estimation-based algorithms that (i) convert ranking feedback into approximate numeric utilities via a Plackett–Luce estimator, and (ii) feed these estimates to a generic numeric-feedback online learner (e.g., FTRL/MWU). With InstUtil Rank and sublinear variation, they obtain sublinear regret in both full-information and bandit settings; with AvgUtil Rank and full information, they can drop the variation assumption and get sublinear regret so long as the underlying numeric-feedback algorithm is stable in cumulative utilities (Assumption 6.1). Finally, they extend the algorithms to multi-player normal-form games and show that if every player follows their no-regret ranking-based learner, the time-averaged play converges to an approximate coarse correlated equilibrium with explicit error bounds.", "questions": "* Is sublinear variation $P(T)$ information-theoretically necessary for sublinear regret, or is it mainly an artifact of the current estimation + analysis?\n* Can you characterize more explicitly how the regret scales with $\\tau$ in the intermediate regime between “very small” (hardness) and “\\mathcal{O}(1)” (positive results)?\n* The results assume a known $\\tau$ and exact PL model. How sensitive are the algorithms and regret bounds if $\\tau$ is misspecified or the rankings are only approximately PL?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper cleanly formulates adversarial online learning with ranking feedback and explicitly distinguishes instantaneous vs time-averaged ranking models and full-information vs bandit settings.\n* The authors provide matching-style hardness results and positive results that reveals the tradeoff between hardness and possibility.\n* The paper shows how ranking-based no-regret dynamics imply convergence to approximate coarse correlated equilibria in general normal-form games (Theorem 7.2 and 7.3).", "weaknesses": "* Many positive results require the utility sequence to have sublinear variation (e.g. Assumption 4.2), these conditions are quite strong in fully adversarial environments.\n* The hardness results for AvgUtil Rank hinge on $\\tau$ being extremely small, the paper does not fully clarify how sharp these thresholds are.\n* Experiments are only briefly mentioned and relegated to the appendix. From the main text, it’s hard to see how the algorithms behave in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aPFesP87HU", "reviewer": "Reviewer_aUGV", "summary": "This paper studies no-regret algorithms under ranking feedback. In the usual no-regret setting, the algorithm sees the utility of the chosen action/ counterfactual utilities of all actions at the end of each round. However, in the ranking setting, the feedback is in the form of relative rankings of the actions, based on the Plankett Luce model, i..e. a softmax over some underlying ground truth utilities (that can be adversarially chosen each round). The paper studies two models of rankings, one based on instantaneous utilities, i.e. with myopic/ short lived agents who only live in each round and the other based on the time average or cumulative utilities over time. The main results of the paper are to characterize under what conditions no-regret learning is possible. \n\nFirst, the paper observes that without noise in the ranking process (i.e. higher temperatures in the Plankett-Luce model), it is impossible for any algorithm to separate fundamentally different utility functions from each other, leading inevitably to high worst case regret -  this is intuitively true when considering purely ordinal information. Next, they observe that with sufficient, i.e. linear variation in time of the ground truth utility, it is again impossible for the learner in the instantaneous ranking setting to distinguish between different utilities.  These results are matched by constructive results showing that no-regret learning is indeed possible with sufficient (but not too high) randomness in the PL model, and with sublinear variation in the utilities over time, with the latter assumption being dropped in the full information setting.\n\nThe algorithmic results are based upon a natural algorithmic procedure that finds a natural approximate utility that best explains the observed rankings - “natural” in the sense that it inverts the PL model based on empirical observations. The best guess utilities thus obtained are fed through any no-regret algorithms from a blackbox class of “consistent” algorithms that behave roughly similarly on similar utility sequences, a property satisfied by popular no-regret algorithms such as FTRL.", "questions": "How does the paper connect to the offline problem of learning static ground truth utilities from ranking information? Is there a technical connection between algorithms for this problem and the algorithmic techniques in your paper?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The main strength of the paper is that it studies a natural and well-motivated problem that was hitherto unsolved. This problem has no shortage of consequential direct applications and is solvable without requiring fundamentally new machinery. That said, the paper is well written and has non-trivial analysis for both the upper and lower bounds results. Further, the assumptions for the positive results are well justified by the lower bounds constructions.", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P7IFrr8WGm", "reviewer": "Reviewer_XTgL", "summary": "This paper studies an online learning when ranking feedback, where the ranks of a given set of actions is returned instead of the conventional rewards. The authors show that sublinear regret cannot be achieved if the ranking function is highly deterministic, controlled by the parameter $\\tau$. On the other than, if the ranking function is more random, sublinear regret is possible. This is an interesting result as in general human rankings are not consistent.  Further, a convergence results in Nash equilibrium is established.", "questions": "Does the theorem apply to the setting where the reward function itself is sampled from a set of reward functions? Is this setting somewhat related to the choice of $\\tau$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is written well and easy to follow. The motivations are clear and ranking model (PL) is standard and popular. Various problem settings are considered, e.g., bandit, full information, and Nash equilibrium. The derivations are clear and results are as expected. Solid and extensive work.", "weaknesses": "The ranking model is somewhat limited as having a consistent reward model in practice is very rare, e.g., RLHF in LLM. Is it possible to consider a problem where the reward function itself is sampled from a set of reward functions? This setting might be more realistic. In might be interesting to test inconsistent reward in the simulation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2n1nvcugw3", "reviewer": "Reviewer_7iCZ", "summary": "A common setting for online learning (in the broadest sense) is adapting to feedback where utilities for different actions cannot be computed. Instead, learners may have access to ranking information where the adversary selects one or more actions among a set of actions. This work considers ranking feedback generated by the Plackett-Luce ranking model assuming ranking vectors from either instantaneous or time-averaged utility vectors. The authors formally establish that no-regret learning is not possible when the ranking is deterministic, i.e. actions are ranked in order of utility. When there is some temperature in the rankings, no-regret learning can be achieved in the full-information setting and in the bandit setting under an additional sub-linearity assumption on the utility vectors. This leads to a CCE as is standard in games where all participants employ a no-regret learning algorithm.", "questions": "None.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- The paper motivates from a real phenomenon, giving the examples of RLHF or customers for a service providing a single instance of feedback where utility cannot be easily computed.\n- They provide formal definitions of their notions of utilities and the standard no-regret guarantees, as well as guarantees when no-regret cannot be achieved.\n- The paper appears theoretically sound.", "weaknesses": "The paper motivates their problem from real cases, but then sets up a theoretical framework without demonstrating practical advantages/successes for the real problem they identify as the motivation. In my view, not establishing this connection limits its impact among practitioners in the motivating cases in the short or long term. For example, it is unclear to me how bandits with ranking feedback, as formalized here, applies to the setting of RLHF, which is presented as a motivating example for this work. \nThe authors provide limited experiments in a synthetic setting that validates their theoretical result is correct and the algorithm is implementable. However, their theoretical results do not seem novel or interesting, given the slew of similar results across various online learning papers, each with slight variations on the bandit / feedback type. Therefore, in my view, the experiments would need to demonstrate practical value for the paper to be accepted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)