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

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

    Oct 6, 2026Diego Alovisetti, Marco Mussi, Alberto Maria MetelliLearning to Rank

    Politecnico di Milano

  2. Learning in Continuous Games from Pairwise Preference Feedback

    Oct 4, 2026Anas BarakatPairwise Preference LearningNash Equilibrium Computation

    Singapore University of Technology and Design

  3. Online Market Making and the Value of Observing the Order Book

    May 19, 2026Davide Maran, Marcello RestelliAdversarial BanditsAlgorithmic Trading

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