💬 NLP

Online Learning and Equilibrium Computation with Ranking Feedback

本文研究了在仅能获得动作排序反馈（而非数值效用）的在线学习场景下，证明了在一般瞬时效用排序下无法实现次线性遗憾，并提出了在效用序列总变差有界或全信息时间平均排序等特定条件下实现次线性遗憾的新算法，进而证明了该算法在博弈重复演化中可收敛至近似粗相关均衡，并在大语言模型路由任务中验证了其有效性。

原作者： Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

发布于 2026-03-20

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文探讨了一个非常有趣且贴近现实的问题：当我们在做决定时，如果只能得到“排名”反馈（比如“哪个更好”），而不是具体的“分数”反馈（比如“打多少分”），我们该如何学习并做出最优选择？

为了让你轻松理解，我们可以把这篇论文的核心内容想象成**“在迷雾中通过比较来导航”**的故事。

1. 核心场景：没有分数的餐厅推荐

想象你是一家在线美食平台的算法（也就是论文中的“学习者”）。你的任务是每天给顾客推荐餐厅。

传统做法（数字反馈）： 顾客吃完后，你会收到一个具体的评分，比如“这家餐厅 4.5 分，那家 3.2 分”。有了这个精确数字，你很容易知道哪家更好，并调整策略。
现实困境（排名反馈）： 但在很多情况下，顾客不愿意或无法给出具体分数。他们可能只会说：“我觉得A 餐厅比 B 餐厅好吃，B 又比 C 好吃"。你得到的只是一个排名（A > B > C），而不是具体的分数。
- 这就好比你在迷雾中，别人只告诉你“左边比右边好”，却不告诉你左边到底有多少好。

这篇论文就是研究：在这种只有“排名”没有“分数”的迷雾中，我们能不能学会做出最好的选择？能不能让大家的体验越来越好？

2. 两种“排名”的来源：瞬间感觉 vs. 长期记忆

论文区分了两种获取排名的方式，这就像顾客评价的两种心态：

瞬间感觉（Instantaneous Utility）：
- 比喻： 顾客是“一次性过客”。他们今天来了，尝了一口，觉得“今天 A 比 B 好吃”，然后就走人了，完全不记得昨天的事。
- 挑战： 这种反馈非常不稳定。今天 A 好吃，明天可能因为心情不好，B 就比 A 好。
- 论文发现： 如果环境变化太快（像这种过客心态），而且排名非常“绝对”（比如只要有一点点差别，顾客就 100% 确定谁好谁坏，没有模糊空间），那么无论你怎么学，都很难达到“后悔很少”的效果。这就好比在狂风中试图走直线，风太大，你根本走不稳。
长期记忆（Time-Average Utility）：
- 比喻： 顾客是“老主顾”。他们不仅看今天的味道，还会回想过去一个月的平均体验。他们会说：“虽然今天 A 不错，但过去一个月 B 更稳定，所以 B 排第一。”
- 优势： 这种反馈更平滑，因为它包含了历史平均信息，像是一个“平滑器”，过滤掉了当天的随机波动。
- 论文发现： 如果顾客的“记忆”足够长，或者排名系统有一定的“模糊度”（允许一点不确定性），我们就能设计出聪明的算法，让后悔值随着时间慢慢变小（即次线性后悔），最终学会做出最佳选择。

3. 核心挑战与解决方案：如何从“排名”猜出“分数”？

既然没有分数，算法怎么知道该往哪个方向走呢？

挑战： 就像你只知道“苹果比梨甜”，但不知道苹果具体有多甜，梨有多酸。如果环境是敌对的（比如有人故意给你误导性的排名），这就很难办。
解决方案（算法的魔法）：
1. 猜测与修正： 论文设计了一种“猜测器”。算法会不断尝试不同的组合，观察顾客的排名反应。
2. 利用“温度”参数： 论文引入了一个“温度”概念（ $\tau$ $τ$ ）。
  - 低温（ $\tau \to 0$ ）： 顾客非常挑剔，只要有一点点差别就立刻分出高下。这种情况下，如果环境变化太快，算法就学不会（因为稍微变一下，排名就全乱了，算法跟不上）。
  - 适中的温度： 顾客有点“糊涂”，允许一点误差。这种模糊性反而帮了算法的大忙，让算法能透过噪音看到趋势。
3. 假设环境不会“变脸”太快： 为了让算法有效，论文假设环境的口味变化是缓慢的（比如顾客口味不会今天突然从爱吃辣变成爱吃甜，而是慢慢过渡）。在这个假设下，算法就能通过不断的“猜测 - 排名反馈 - 修正”，逐渐逼近最优解。

4. 游戏与平衡：当所有人都这样学习时

论文还做了一个更宏大的推演：如果在一个多人游戏（比如网约车平台匹配司机和乘客，或者约会软件匹配男女）中，所有人都使用这种“只看排名”的学习算法，会发生什么？

比喻： 想象一个巨大的舞会，每个人都在找舞伴。没人知道对方具体喜欢什么（没有分数），只知道“我觉得 A 比 B 好”。
结果： 论文证明，只要大家都用这种聪明的算法，经过一段时间的互相试探和排名反馈，整个系统会自发地达到一种**“粗相关均衡”（Coarse Correlated Equilibrium）**。
通俗解释： 这意味着，虽然没人知道完美的匹配方案是什么，但大家通过不断的“试错”和“互相排名”，最终会形成一种大家都比较满意、没人想单方面改变策略的稳定状态。就像舞会最后大家都找到了合适的舞伴，虽然可能不是理论上的完美，但大家都挺开心，没人想换人了。

5. 实际应用：大语言模型的路由

论文最后还展示了一个很酷的应用：大语言模型（LLM）的路由。

场景： 你有好几个 AI 模型（比如有的擅长写诗，有的擅长写代码）。用户来提问，你该把问题发给哪个模型？
问题： 你很难给每个模型打分（因为很难量化“写得好”）。
应用： 你可以让模型生成几个回答，然后让用户（或另一个评判模型）只给出一个排名（“回答 A 最好，回答 B 次之”）。
效果： 论文的实验表明，使用他们的算法，系统能很快学会把问题分发给最擅长处理该问题的模型，即使它从未收到过具体的分数，只收到了排名。

总结

这篇论文就像是在教我们**“如何在没有尺子的情况下丈量世界”**。

它告诉我们：如果只给排名不给分数，在某些极端情况下（环境变化太快且排名太绝对）是学不会的。
但它也给出了希望：只要环境变化不是太剧烈，或者排名系统允许一点“模糊”，我们就有办法设计出聪明的算法。
这些算法不仅能帮个人做出更好的选择（如推荐餐厅），还能帮整个社会系统（如匹配平台）自动找到一种大家都能接受的稳定平衡。

这就好比在迷雾中，虽然看不清路标（分数），但只要大家互相指路（排名），并且路不是瞬息万变的，我们最终都能找到回家的路。

这是一篇发表于 ICLR 2026 的论文，题为《基于排序反馈的在线学习与均衡计算》（Online Learning and Equilibrium Computation with Ranking Feedback）。该论文研究了在无法获取数值型效用反馈（numeric utility feedback），只能获取动作排序（ranking feedback）的在线学习场景下的理论界限与算法设计。

以下是该论文的详细技术总结：

1. 问题背景与动机 (Problem & Motivation)

背景：传统的在线学习（Online Learning）通常假设智能体（Agent）能接收到环境反馈的数值型效用（如奖励值或损失向量）。然而，在许多现实应用（如人机交互、推荐系统、强化学习从人类反馈 RLHF）中，获取精确的数值评分往往困难、昂贵或涉及隐私。相比之下，人类更倾向于对候选动作进行排序（Ranking）。
核心挑战：在非随机、甚至对抗性的环境中，仅凭排序反馈进行在线学习并最小化外部遗憾（External Regret）是否可行？如果可行，需要满足什么条件？
应用场景：
- 在线推荐：平台向用户推荐商品，用户仅对推荐列表进行排序，而不给出具体评分。
- 博弈均衡计算：在重复博弈中，玩家仅能根据对手的历史行为对策略进行排序，平台需利用这些排序计算粗相关均衡（CCE）。
- 大语言模型路由：根据用户偏好将查询路由到不同的 LLM，用户仅对返回结果进行排序。

2. 模型设定 (Model Setup)

论文定义了两种主要的排序反馈机制，均基于 Plackett-Luce (PL) 模型（温度参数为 $\tau$ ）：

瞬时效用排序 (InstUtil Rank)：排序基于当前时间步 $t$ $t$ 的瞬时效用向量 $u(t)$ $u (t)$ 。
- 适用于“一次性”交互或无记忆的用户。
平均效用排序 (AvgUtil Rank)：排序基于截至当前时间步 $t$ $t$ 的时间平均效用 $u_{avg}(t) = \frac{1}{t}\sum_{s=1}^t u(s)$ $u_{a v g} (t) = \frac{1}{t} \sum_{s = 1}^{t} u (s)$ 。
- 适用于有记忆的用户或长期交互场景。

此外，设定分为两种反馈模式：

全信息 (Full-Information)：所有动作都被提议并排序。
带限制 (Bandit)：仅提议 $K$ 个动作并排序。

3. 核心贡献与理论结果 (Key Contributions & Results)

3.1 不可能性结果 (Hardness Results)

论文首先证明了在一般条件下，仅凭排序反馈实现次线性遗憾（Sublinear Regret）是不可能的：

InstUtil Rank：无论 $\tau$ 大小如何，在对抗性环境下，遗憾下界为 $\Omega(T)$ （线性遗憾）。这是因为效用向量变化过快，排序反馈无法提供足够的信息来区分不同的效用序列。
AvgUtil Rank：
- 当 $\tau$ 非常小（即排序模型高度确定性， $\tau \to 0^+$ ）时，遗憾下界仍为 $\Omega(T)$ 。
- 在全信息设置下，若 $\tau \le O(\frac{1}{T \log T})$ ，遗憾下界为 $\tilde{\Omega}(T)$ 。
- 在 Bandit 设置下，若 $\tau \le O(\frac{1}{\log T})$ ，遗憾下界为 $\Omega(T)$ 。
- 结论：在极度确定性的排序反馈下，无法区分不同的效用历史，导致无法学习。

3.2 算法设计与正结果 (Algorithms & Positive Results)

为了克服上述困难，论文引入了效用向量总变差（Total Variation）次线性的假设，即 $\sum_{t=2}^T \|u(t) - u(t-1)\| \le O(T^q)$ ( $q < 1$ )。在此假设下，提出了新的算法：

核心思想：利用滑动窗口和成对比较（Pairwise Comparisons）从排序中估计数值效用向量。
- 利用 PL 模型的性质，将 $K$ 个动作的排序分解为两两比较的概率，通过逻辑回归（Logistic）结构反推效用差值。
- 设计了一个效用估计 Oracle（Algorithm 1），将排序反馈转化为对效用向量的估计 $\hat{u}(t)$ 。
针对 InstUtil Rank 的算法 (Algorithm 2)：
- 将估计出的效用 $\hat{u}(t)$ 输入到标准的无遗憾学习算法（如 FTRL, PGD）中。
- 结果：在效用变差次线性的假设下，实现了次线性遗憾。
- Bandit 设置：引入了探索机制（混合均匀分布），确保每个动作被采样，从而保证估计的无偏性。
针对 AvgUtil Rank 的算法 (Algorithm 3)：
- 全信息设置：直接估计平均效用 $\hat{u}_{avg}(t)$ 。由于平均效用随时间变化较慢（ $\|u_{avg}(t) - u_{avg}(t-1)\| \le 2/t$ ），不需要效用变差次线性的假设即可实现次线性遗憾（当 $\tau$ 为常数时）。
- Bandit 设置：由于只能观测提议动作的样本均值，直接估计平均效用方差过大。算法采用了分块（Block）策略，在每个时间块内估计平均效用，以平衡偏差与方差。
- 结果：在效用变差次线性（ $q < 1/3$ ）的假设下，实现了次线性遗憾。

3.3 博弈均衡计算 (Equilibrium Computation)

当所有玩家都运行上述无遗憾算法时，重复博弈的时间平均策略分布收敛到近似粗相关均衡（ $\epsilon$ -CCE）。
论文证明了在满足策略变差次线性（Assumption 8.1，通常由 FTRL 等算法满足）的条件下，上述算法在博弈场景下依然有效。

4. 实验验证 (Experiments)

LLM 路由任务：模拟了一个在线大语言模型路由场景。用户查询不同模型，平台根据用户反馈的排序（而非具体分数）来调整路由策略。
结果：实验显示，随着时间推移，算法的平均遗憾显著下降，证明了算法能够适应非平稳的用户偏好，并快速收敛到表现最好的固定模型。
参数敏感性：验证了不同温度参数 $\tau$ 和提议动作数量 $K$ 对算法性能的影响。

5. 总结与意义 (Significance)

理论突破：首次系统性地研究了在对抗性环境下，仅凭排序反馈进行在线学习的理论界限。明确了在何种条件下（如效用变化缓慢、温度参数适中）学习是可能的。
算法创新：提出了一种通用的框架，将排序反馈转化为数值效用估计，并无缝集成到现有的无遗憾学习算法中。特别是针对 AvgUtil Rank 的 Bandit 设置，设计了创新的分块估计方法。
实际应用：为 RLHF、推荐系统、匹配市场等无法获取精确数值反馈的场景提供了理论指导和算法方案。
局限性：目前的正结果依赖于效用序列的变差次线性假设（InstUtil 和 AvgUtil Bandit）。未来的工作致力于在更弱的假设下（如常数 $\tau$ 且无变差假设）实现次线性遗憾，或证明其不可能性。

一句话总结：
该论文证明了在对抗性环境中，仅凭排序反馈进行在线学习通常是不可能的，但在效用变化缓慢或平均效用反馈且温度适中的条件下，通过创新的效用估计算法可以实现次线性遗憾，并进而计算出博弈均衡，为大模型路由等实际应用提供了理论支撑。