cs.LGMar 19, 2026

Online Learning and Equilibrium Computation with Ranking Feedback

Authors: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

Organizations: Massachusetts Institute of Technology · University of Maryland, College Park · Northeastern University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 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 ranking over a set of proposed actions at each timestep. We consider two ranking mechanisms: rankings induced by the instantaneous utility at the current timestep, and rankings induced by the time-average utility up to the current timestep, under both full-information and 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, 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.

Figures & tables

Figure 1: Two examples of online learning and equilibrium computation with ranking feedback. In (a), an online platform recommends food options to a customer at each timestep and receives a 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.
Lower BoundFull-InformationBandit
InstUtil RankΩ(T)\Omega(T) for τ≤O(1)\tau\leq\mathcal{O}\left(1\right)
AvgUtil RankΩ~(T)\widetilde{\Omega}(T) for τ≤O(1Tlog⁡T)\tau\leq\mathcal{O}\left(\frac{1}{T\log T}\right)Ω(T)\Omega(T) for τ≤O(1log⁡T)\tau\leq\mathcal{O}\left(\frac{1}{\log T}\right)
Table 1: 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 in each setting (✓indicates that no additional assumptions are needed). Here, τ>0\tau>0 denotes the temperature parameter of the ranking model in PL .
Figure 2: Regret of Algorithm 3 with AvgUtil Rank under bandit feedback for different temperatures τ\tau and numbers of proposed actions KK , in the online learning setting.
Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: The exploitability for the full-information feedback setting under both InstUtil Rank and AvgUtil Rank . Performance is evaluated across different temperatures τ\tau and cumulative utility variations P(T)=TqP^{(T)}=T^{q} . Each parameter combination is tested 1010 times with different random seeds.
Figure 4: The regret for bandit feedback setting under InstUtil Rank feedback in the online learning setting. The performance is evaluated across different temperatures τ\tau , cumulative utility variations P(T)=TqP^{(T)}=T^{q} , and numbers of proposed actions KK . Each parameter combination is tested 1010 times with different random seeds.
Figure 5: The regret for bandit feedback setting under AvgUtil Rank feedback in the online learning setting. The performance is evaluated across different temperatures τ\tau , cumulative utility variations P(T)=TqP^{(T)}=T^{q} , and numbers of proposed actions KK . Each parameter combination is tested 1010 times with different random seeds.
Figure 6: Regret of Algorithm 3 with AvgUtil Rank under full-information feedback, across different temperatures τ\tau and noise types in the online-learning setting.
Figure 7: The exploitability for the full-information setting under both InstUtil Rank and AvgUtil Rank feedback in the game-play setting. The performance is tested under different temperatures τ\tau . Each parameter combination is tested 1010 times with different random seeds.
Figure 8: The exploitability for the bandit feedback setting under InstUtil Rank feedback in the game-play setting. Performance is evaluated across different temperatures τ\tau and numbers of proposed actions KK . Each parameter combination is tested 1010 times with different random seeds.
Figure 9: The exploitability for the bandit feedback setting under AvgUtil Rank feedback in the game-play setting. Performance is evaluated across different temperatures τ\tau and numbers of proposed actions KK . Each parameter combination is tested 1010 times with different random seeds.
  nj,1(s)≔∑i,k∈[K]\ind(σ(s)(i)=aj,σ(s)(k)=a∣A∣and i<k),\displaystyle n_{j,1}^{(s)}\coloneqq\sum_{i,k\in\left[K\right]}\ind\left(\sigma^{(s)}\left(i\right)=a^{j},\sigma^{(s)}\left(k\right)=a^{\left|\mathcal{A}\right|}\text{and}~i<k\right), 
  nj,2(s)≔∑i,k∈[K]\ind(σ(s)(i)=aj,σ(s)(k)=a∣A∣and i>k).\displaystyle n_{j,2}^{(s)}\coloneqq\sum_{i,k\in\left[K\right]}\ind\left(\sigma^{(s)}\left(i\right)=a^{j},\sigma^{(s)}\left(k\right)=a^{\left|\mathcal{A}\right|}\text{and}~i>k\right). 
Appendix
Algorithm 1 Utility Estimation with Action Permutations: Estimate ({σ(s)}s=1m′)\left(\left\{\sigma^{(s)}\right\}_{s=1}^{m^{\prime}}\right)
Figure 10: The diagram of Algorithm 2 with InstUtil Rank under full-information feedback (top) and bandit feedback (bottom). +◯\textcircled{+} represents the addition of (1−γ)(1-\gamma) times the output the Alg{\rm Alg} and γ\gamma times a uniform distribution over A\mathcal{A} .
Figure 11: The diagram of Algorithm 3 with AvgUtil Rank under full-information feedback (top) and bandit feedback (bottom). represents copying the estimated utility vector for tt times. +◯\textcircled{+} represents the addition of (1−γ)(1-\gamma) times the output the Alg{\rm Alg} and γ\gamma times a uniform distribution over A\mathcal{A} .
 u~avg−est(t)(a)≔{1⌊t/M⌋∑s=1⌊t/M⌋u~empirical(s⋅M)(a)n(s⋅M)(a)−u~empirical((s−1)M)(a)n((s−1)M)(a)n(s⋅M)(a)−n((s−1)M)(a)t≥M0t<M\displaystyle\widetilde{u}^{(t)}_{\rm avg-est}(a)\coloneqq\begin{cases}\frac{1}{\left\lfloor t/M\right\rfloor}\sum_{s=1}^{\left\lfloor t/M\right\rfloor}\frac{\widetilde{u}^{(s\cdot M)}_{\rm empirical}(a)n^{(s\cdot M)}(a)-\widetilde{u}^{((s-1)M)}_{\rm empirical}(a)n^{((s-1)M)}(a)}{n^{(s\cdot M)}(a)-n^{((s-1)M)}(a)}&t\geq M\\ 0&t<M\end{cases} (E.1)
Appendix
Algorithm 3 Online Learning with AvgUtil Rank Feedback
More in this topic

Online Learning

Online learning studies algorithms that update predictions or decisions from sequential feedback while controlling cumulative error or regret.

See all 132 papers

Explore similar work

CardsList
Oct 6, 2026

Learning a Ranking from Human Feedback in Log-Concave Random Utility Models

We study the problem of recovering the ranking of a fixed set of items according to their unknown numerical utilities. At each interaction with the environment, a learner presents the item set to a human and receives comparative feedback of two types. Under full-ranking feedback, each interaction reveals a noisy ranking of all items, whereas under winner-only feedback, it reveals only the item ranked first. In both settings, we model human feedback using a random utility model with log-concave noise and study the number of observations needed to recover an εε-accurate ranking with high probability. This novel criterion tolerates ordering errors only between items whose utilities differ by less than εε. For both feedback types, we establish worst-case sample-complexity lower bounds and develop algorithms that match these bounds up to logarithmic factors. Neither algorithm requires knowledge of the noise distribution, while only requiring an upper bound on its variance. Our results show that the ranking problem under winner-only feedback is intrinsically harder by exposing the sample complexity dependence on the minimum winning probability across the item set.

Diego Alovisetti, Marco Mussi, Alberto Maria Metelli

Politecnico di Milano

Learning to Rank
AskPDF
Oct 4, 2026

Learning in Continuous Games from Pairwise Preference Feedback

We study learning in continuous games when players receive only pairwise preference feedback, revealing which of two actions is preferred but neither payoff values nor preference magnitudes. We first show that standard external regret and coarse correlated equilibria (CCE) are not identifiable from this ordinal information: the same sequence of play can incur zero and linear regret in two ordinally equivalent games, while the distributions that remain CCE across all cardinal representations consistent with the same preferences are exactly those supported on pure Nash equilibria. Motivated by this gap, we develop a first-order ordinal theory based on normalized unilateral preference directions, introducing an ordinal directional regret benchmark and corresponding equilibrium notions. We show that block-normalized pseudogradient dynamics achieve sublinear ordinal regret and, under additional structure, Nash-convergence guarantees. We then use a single-comparison estimator to implement these dynamics from finite pairwise comparisons. With one comparison per player and round, the resulting algorithm achieves sublinear finite-resolution ordinal regret against arbitrary opponent behavior and, in ordinal potential games, almost-sure last-iterate convergence to the Nash set. Our results provide regret, dynamics, and equilibrium guarantees directly from preference feedback without reconstructing cardinal utilities.

Anas Barakat

Singapore University of Technology and Design

Pairwise Preference LearningNash Equilibrium Computation
AskPDF
May 19, 2026

Online Market Making and the Value of Observing the Order Book

We study an online market-making problem in which a learner sequentially posts bid and ask prices for a single asset while interacting with traders holding private valuations. Unlike existing online learning formulations that assume fully censored feedback, we introduce an action-dependent feedback model inspired by real limit order books: when a trade occurs, the trader's valuation remains hidden, whereas when no trade occurs, informative feedback about supply and demand is revealed. We show that this additional information fundamentally changes the learnability of the problem. In the stochastic setting with i.i.d. market prices, we propose an elimination-based algorithm that achieves O(T)O(\sqrt T) regret with high probability, without requiring any smoothness assumptions on the distribution of trader valuations. We then extend this result to a broad class of mean-reverting price processes by considering both local, autoregressive dynamics and a weaker global drift condition based on cumulative deviations from the mean. Under either assumption, we establish high-probability O(T)O(\sqrt T) regret bounds, relying on a new concentration inequality of independent interest. Finally, in the adversarial setting with oblivious prices, we design an explore-then-perturb algorithm that guarantees O(T2/3)O(T^{2/3}) regret in expectation. Our results quantify the value of observing the order book in online market making and demonstrate that even limited, action-dependent feedback can substantially improve regret guarantees compared to standard bandit feedback models.

Davide Maran, Marcello Restelli

Politecnico di Milano, Piazza Leonardo da Vinci, 32-36 - Citt`a Studi, Milano (MI)

Adversarial BanditsAlgorithmic Trading
AskPDF