💬 NLP

Online Learning and Equilibrium Computation with Ranking Feedback

This paper investigates online learning with ranking feedback instead of numeric utilities, demonstrating that sublinear regret is generally impossible under standard conditions but achievable via new algorithms when utility sequences have bounded variation, thereby enabling equilibrium computation in games and effective large-language-model routing.

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

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef running a busy restaurant, but you have a very strange problem: You can never taste your own food.

Every day, you serve a customer a plate with several different dishes (actions). The customer eats them, but instead of giving you a score like "8 out of 10," they simply hand you a piece of paper with a ranking list. It might say: "I liked the pasta best, the salad second, and the soup last."

Your goal is to learn which dish is the absolute best over time so you can serve it every day. But here's the catch: you don't know why they liked the pasta. Was it the salt? The temperature? You only know the order.

This paper is about solving that exact problem, but in the world of computers and artificial intelligence. The researchers are asking: "Can we learn to make perfect decisions if we only get a 'ranked list' of feedback instead of a score?"

Here is the breakdown of their discovery, using simple metaphors.

1. The Two Types of Feedback

The paper looks at two different ways the "customer" might give you that ranking list:

The "Instant" Customer (InstUtil Rank): This customer ranks the food based only on how it tasted right now. Maybe they are hungry today but not tomorrow. Their mood changes instantly.
The "Memory" Customer (AvgUtil Rank): This customer ranks the food based on how it has tasted all week long. They remember that the pasta was great yesterday, so they rank it higher today, even if today's batch was just okay.

2. The Bad News: Sometimes You Can't Win

The researchers first tried to find a magic algorithm that works for any situation. They discovered a harsh truth: Sometimes, it is mathematically impossible to learn.

The "Instant" Trap: If the customer's taste changes wildly and unpredictably every second (like a stormy day), and they only give you a ranking, you are stuck. It's like trying to guess the weather by looking at a single cloud that changes shape every second. No matter how smart you are, you can't learn the pattern because the feedback is too noisy and fast.
The "Too Certain" Trap: If the "Memory" customer is too certain (they always rank the best food #1 and the worst #10 with zero hesitation), you also get stuck. It's like a teacher who only writes "A" or "F" on a test but never gives you the actual score. You can't tell the difference between a "99%" and a "90%" because the ranking looks the same. You need some "noise" or uncertainty in the feedback to learn the subtle differences.

3. The Good News: The "Smooth" Solution

So, is the game unwinnable? Not quite. The researchers found a way to win, but with a condition: The world must change slowly.

Imagine the customer's taste doesn't jump from "loves pasta" to "hates pasta" overnight. Instead, their taste drifts slowly, like a river flowing. If the changes are gradual (a concept the paper calls "sublinear variation"), you can win.

How do they do it?
They invented a new kind of "translator" algorithm.

The Translator: Since the algorithm can't see the scores, it looks at the ranking lists and tries to guess the hidden scores. It's like a detective looking at footprints to guess how fast the suspect was running.
The Safety Net: Because the translator isn't perfect, the algorithm adds a little bit of "randomness" (exploration). It occasionally tries a dish it thinks is bad just to make sure it hasn't missed something.
The Result: Over time, the algorithm learns to predict the scores well enough that its "Regret" (the difference between what it got and what it could have gotten) becomes tiny.

4. The Game Theory Twist: Finding a Fair Match

The paper also applies this to Games, specifically things like online dating apps or ride-sharing.

Imagine a dating app. It suggests matches to users. Users don't say "I rate this person 8/10." They just say, "I prefer Person A over Person B."

The app wants to find a Stable Equilibrium: A state where no one wants to switch partners because they are already matched with someone they prefer.
The paper proves that if everyone (the app and the users) uses this new "ranking-based learning" method, the system will naturally settle into a fair, stable match, even without anyone ever saying a number.

5. The Real-World Test: AI Routing

Finally, they tested this on Large Language Models (LLMs).

The Scenario: You have a user asking a question. You have 5 different AI models (like GPT-4, Llama, etc.) that could answer.
The Problem: You don't know which model is best for this specific user right now.
The Solution: The system sends the question to 3 random models. The user ranks the answers. The system uses the paper's algorithm to learn which model to send the next question to.
The Result: The system quickly figured out which model the user liked best and routed them there, minimizing mistakes.

The Big Takeaway

This paper is a guide for the future of AI in a world where we can't always get perfect data. It tells us:

Don't panic if you only get rankings: You can still learn, but you need to be careful.
Change is the enemy: If the environment changes too fast or is too rigid, learning is impossible. But if things change slowly, you can adapt.
It works for groups: This isn't just for one robot; it helps entire groups of people and computers find fair agreements (equilibria) without needing to share their private scores.

In short: You don't need a scoreboard to win the game; you just need to pay attention to the order of the finish line, and be patient enough to let the race unfold.

1. Problem Definition

The paper addresses the problem of online learning in non-stochastic (potentially adversarial) environments where the learner does not receive numeric utility feedback (e.g., exact scores or rewards). Instead, the learner only observes ranking feedback over a set of proposed actions.

Setting: An agent interacts with an environment over $T$ timesteps. At each step $t$ , the agent proposes a set of actions $o(t)$ (either the full action set in Full-Information or a subset of size $K$ in Bandit settings).
Feedback: The environment returns a permutation $\sigma(t)$ representing a ranking of the proposed actions.
Ranking Model: The feedback is generated via the Plackett-Luce (PL) model, parameterized by a temperature $\tau$ . The probability of a ranking depends on the underlying utility vector $r(t)$ .
Two Feedback Mechanisms:
1. InstUtil Rank: Rankings are based on the instantaneous utility $u(t)$ at the current timestep. This models "one-shot" or oblivious feedback providers.
2. AvgUtil Rank: Rankings are based on the time-average utility up to the current timestep ( $u_{avg}^{(t)} = \frac{1}{t}\sum_{s=1}^t u(s)$ ). This models feedback providers with memory (e.g., long-lived users).
Goal: Minimize external regret (the difference between the agent's cumulative utility and the best fixed action in hindsight) and, in game-theoretic settings, compute an approximate Coarse Correlated Equilibrium (CCE).

2. Key Contributions & Methodology

The authors establish fundamental limits on what is achievable and propose new algorithms to overcome these limits under specific conditions.

A. Hardness Results (Impossibility Theorems)

The paper proves that sublinear regret is impossible in general without additional assumptions:

InstUtil Rank: For any constant temperature $\tau$ , sublinear regret is impossible in both Full-Information and Bandit settings. The adversary can construct utility sequences that yield identical ranking distributions but different expected utilities, forcing linear regret.
AvgUtil Rank:
- In the Full-Information setting, if $\tau$ is sufficiently small ( $\tau \le O(\frac{1}{T \log T})$ ), sublinear regret is impossible.
- In the Bandit setting, if $\tau$ is small ( $\tau \le O(\frac{1}{\log T})$ ), sublinear regret is also impossible.
- Insight: When $\tau \to 0$ , the ranking becomes deterministic (always picking the highest utility). In adversarial settings, this lack of stochasticity prevents the learner from distinguishing between utility vectors that induce the same ranking but different cumulative outcomes.

B. Algorithmic Solutions

To achieve sublinear regret, the authors introduce the assumption of Sublinear Variation in the utility sequence (Assumption 5.2): $\sum_{t=2}^T \|u(t) - u(t-1)\| \le O(T^q)$ for $q < 1$ .

Core Methodology: Utility Estimation via Pairwise Decomposition
Since the PL model is non-convex, the authors develop a novel Utility Estimation Oracle (Algorithm 1):

Decomposition: They decompose the $K$ -wise ranking into pairwise comparisons.
Estimation: Using the logistic structure of the PL model, they estimate the probability of one action being preferred over another. By inverting the logistic function, they recover an estimate of the utility difference.
Sliding Window: Estimates are computed using a sliding window of recent permutations to track non-stationary utilities.

Specific Algorithms:

For InstUtil Rank (Algorithm 2):
- Uses the utility estimator to generate a numeric vector $\hat{u}(t)$ .
- Feeds $\hat{u}(t)$ into a standard no-regret oracle (e.g., FTRL, PGD).
- Bandit Setting: Adds an exploration term (uniform distribution) to ensure all actions are sampled with sufficient probability.
- Result: Achieves sublinear regret under the sublinear variation assumption.
For AvgUtil Rank (Algorithm 3):
- Full-Information: Estimates the time-average utility directly. Crucially, the authors show that if the underlying oracle is stable (satisfies Assumption 7.1, e.g., FTRL with strong convexity), the sublinear variation assumption is not required. The algorithm achieves sublinear regret even with arbitrary utility variations.
- Bandit: Estimating the time-average utility is harder because the feedback is based on the empirical mean of sampled actions. The authors introduce a block-based estimation strategy (dividing time into blocks of size $M$ ) to balance bias and variance. This requires the sublinear variation assumption with $q < 1/3$ .

C. Equilibrium Computation

The paper extends these results to Normal-Form Games (NFG):

If all players in a repeated game use the proposed algorithms, their time-average joint strategy converges to an $\epsilon$ -Coarse Correlated Equilibrium (CCE).
The convergence rate depends on the regret bounds derived for the single-agent setting.
Remark: Even when $\tau \to 0$ (where online learning is hard), equilibrium computation remains possible because the deterministic ranking reveals the best response, effectively reducing the problem to Fictitious Play, which converges in certain games.

3. Key Results & Theoretical Bounds

Setting	Feedback Type	Assumption Required	Regret Bound
InstUtil Rank	Full-Info / Bandit	Sublinear Variation ( $P(T) \le O(T^q)$ )	Sublinear (e.g., $O(T^{2/3})$ )
AvgUtil Rank	Full-Info	None (if Oracle is stable)	Sublinear (e.g., $O(T^{5/3} L)$ )
AvgUtil Rank	Bandit	Sublinear Variation ( $q < 1/3$ )	Sublinear (e.g., $O(T^{4/9})$ )
General	Any	Small $\tau$ (Deterministic)	Linear Regret (Hardness)

Hardness: The paper provides tight lower bounds showing that without the variation assumption (or with very small $\tau$ ), regret is $\Omega(T)$ .
Full-Information AvgUtil: A significant theoretical contribution is showing that for Full-Information AvgUtil Rank, the sublinear variation assumption can be removed entirely, provided the learning oracle is stable.

4. Experimental Validation

The authors validate their approach using an Online Large Language Model (LLM) Routing task:

Scenario: A server routes user queries to different LLMs (e.g., GPT-4o, Llama-3, Phi-4) based on user preferences.
Feedback: Users rank the generated responses rather than providing numeric scores.
Setup: The system uses Algorithm 3 with AvgUtil Rank under Bandit feedback.
Outcome: The average regret decreases over time, demonstrating that the router successfully learns to route queries to the optimal model for the specific user, even with non-stationary preferences and only ranking feedback.

5. Significance and Impact

Bridging RLHF and Online Learning: The work formalizes the transition from Reinforcement Learning from Human Feedback (RLHF), which often uses offline ranking data, to online settings where decisions must be made sequentially with limited feedback.
Theoretical Limits: It rigorously defines the boundaries of learning with ranking feedback, showing that "deterministic" rankings in adversarial environments are fundamentally unlearnable without structural assumptions (like low variation).
Game Theory: It provides a new mechanism for computing equilibria in games where players only observe relative preferences (rankings) rather than exact payoffs, which is more realistic for human-in-the-loop systems.
Algorithmic Innovation: The proposed utility estimation via pairwise decomposition and block-based averaging offers a robust framework for converting ordinal feedback into actionable numeric estimates for standard optimization algorithms.

In summary, this paper establishes that while ranking feedback in adversarial environments poses severe challenges (often making sublinear regret impossible), it is achievable under realistic assumptions of slowly changing environments or with specific algorithmic designs for time-averaged feedback, with direct applications to modern AI alignment and multi-agent systems.