Online Learning and Equilibrium Computation with Ranking Feedback
Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman E. Ozdaglar, Kaiqing Zhang · 2026
Read Online Learning and Equilibrium Computation with Ranking Feedback by Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman E. Ozdaglar, Kaiqing Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19221.txt.
Introduction
Liu and co-authors study online learning when the learner sees only a ranking of actions, not numeric scores. Such feedback fits settings with humans in the loop or privacy limits. They prove that with rankings from current scores, low regret is not possible in general. The same holds for average-score rankings when choices are near fixed. New methods do reach low regret when scores change slowly over time. In games, joint use of the methods leads play toward a coarse correlated balance.
Catalog record
| CREATOR | Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman E. Ozdaglar, Kaiqing Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 156491 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.19221
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online Learning and Equilibrium Computation with Ranking Feedback Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman E. Ozdaglar, Kaiqing Zhang 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. 1 Introduction Online learning has been extensively studied as a model for sequential decision-making in arbitrary and possibly adversarial environments ( Shalev-Shwartz et al. 2012 ; Hazan et al. 2016 ) . At each round, the agent commits to a strategy, takes an action, and then receives feedback from the environment, often in numeric form, such as the utility vector (in the full-information feedback setting) 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 ( Shalev-Shwartz et al. 2012 ; Hazan et al. 2016 ) . Moreover, online learning is closely connected to equilibrium computation in game theory: when all players employ no-regret learning in the repeated play of a normal-form 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 instance, 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 reinforcement 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 1 (a)) that recommends commodities to a stream of customers over time, where 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 on whether customers are one-shot (arrive, rank, and leave forever) or long-lived with memory, the ranking feedback may be induced either by the instantaneous utility at each timestep or by the time-average utility aggregated over historical utility vectors. The platform thus seeks to minimize the regret of its recommendations under ranking-only feedback. Yet, the fundamental limits and algorithmic solutions for this online learning setting remain elusive. Ranking feedback becomes particularly relevant in game-theoretic settings, where multiple humans repeatedly interact, and the goal is to compute an equilibrium of the underlying game. For example, consider an online dating platform that recommends potential matches (see Figure 1 (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. , a matching between users, that (approximately) respects everyone’s preferences. Related scenarios arise in other matching platforms, e.g. , ride-sharing services that match drivers and passengers based on their preferences, such as drivers’ preferences over trip lengths and riders’ preferences over driving styles ( e.g. , punctuality or cautiousness). Although these applications may seem reminiscent of the classical stable matching model ( Gale & Shapley 1962 ) , our setting is fundamentally different. See Section 2 for a 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 as a generalization of the stochastic bandits with ranking feedback studied recently in Maran et al. 2024 . See Section 2 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 equilibrium-approximation guarantees. We summarize our contributions as follows. Contributions. We consider two types of ranking feedback, categorized by how the rankings are generated: one based on the instantaneous utility at each timestep ( Item InstUtil Rank ), and one based on the time-average utility up to the current timestep ( Item AvgUtil Rank ). We establish the following results: (i) sublinear regret is impossible under Item InstUtil Rank feedback. Moreover, under Item AvgUtil Rank feedback, sublinear regret remains unattainable (up to logarithmic factors) when the ranking model is overly deterministic ( i.e. , when the temperature parameter \tau>0 in Equation 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 full-information Item AvgUtil Rank feedback when \tau is a constant; and (iv) when all players run our no-regret learning algorithms in the repeated play of a normal-form game, the induced play yields an approximate coarse correlated equilibrium. Our contributions are summarized in Table 1 . We present an application to large-language-model routing in Section 9 , and provide experimental validation of our algorithms in Appendix B . 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 Bound Full-Information Bandit Item InstUtil Rank \Omega(T) for \tau\leq\mathcal{O}\left(1\right) Item AvgUtil Rank \widetilde{\Omega}(T) for \tau\leq\mathcal{O}\left(\frac{1}{T\log T}\right) \Omega(T) for \tau\leq\mathcal{O}\left(\frac{1}{\log T}\right) Upper Bound ( \tau=\mathcal{O}(1) , Sublinear Regret) Full-Information Bandit Item InstUtil Rank 5.2 Item AvgUtil Rank ✓ 5.2 ( q<\frac{1}{3} ) 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, \tau>0 denotes the temperature parameter