Online Learning and Equilibrium Computation with Ranking Feedback

📄 arXiv: 2603.19221v1 📥 PDF

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

分类: cs.LG, cs.CL, cs.GT

发布日期: 2026-03-19

💡 一句话要点

针对排序反馈的在线学习与均衡计算，提出变分效用下的次线性后悔算法

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 在线学习 排序反馈 后悔最小化 均衡计算 粗略相关均衡

📋 核心要点

  1. 现有在线学习算法依赖数值效用反馈，但在人机交互或隐私受限场景中难以应用。
  2. 针对排序反馈的在线学习，设计算法以实现次线性后悔，并分析瞬时效用和时间平均效用下的可行性。
  3. 在效用序列具有次线性总变分的假设下，算法在大型语言模型路由任务中表现出有效性。

📝 摘要（中文）

本文研究了一种在线学习模型，其中学习者在每个时间步仅观察到一组提议动作的排序。考虑两种排序机制：由当前时间步的瞬时效用引起的排序，以及由当前时间步之前的时间平均效用引起的排序，分别在全信息和bandit反馈设置下进行研究。结果表明，在一般情况下，使用瞬时效用排序反馈无法实现次线性后悔。此外，当排序模型相对确定时（即在温度足够低的Plackett-Luce模型下），使用时间平均效用排序反馈也无法实现次线性后悔。因此，本文开发了新的算法，在效用序列具有次线性总变分的附加假设下，实现了次线性后悔。值得注意的是，对于全信息时间平均效用排序反馈，可以移除此附加假设。因此，当正规博弈中的所有参与者都遵循本文的算法时，重复博弈会产生近似的粗略相关均衡。最后，本文还在在线大型语言模型路由任务中证明了算法的有效性。

🔬 方法详解

问题定义：论文旨在解决在线学习中，当环境仅提供动作排序反馈而非数值效用反馈时，如何设计算法以最小化后悔值的问题。现有方法通常依赖于数值效用反馈，这在许多实际场景中是不可行的，例如人机交互和隐私保护等。此外，即使有数值效用，获取这些数值的成本也可能很高。因此，如何仅通过排序反馈进行有效的在线学习是一个重要的挑战。

核心思路：论文的核心思路是，尽管直接的数值效用不可用，但动作的排序信息仍然蕴含着关于效用的相对信息。论文通过分析不同排序机制（瞬时效用和时间平均效用）下的后悔界，并结合效用序列的变分特性，设计相应的在线学习算法。对于时间平均效用排序反馈，论文证明了在全信息情况下可以移除对效用序列变分的假设。

技术框架：论文的整体框架是针对不同的反馈设置（全信息 vs. bandit）和排序机制（瞬时效用 vs. 时间平均效用），分别分析后悔界，并设计相应的在线学习算法。具体来说，对于瞬时效用排序反馈，论文证明了在一般情况下无法实现次线性后悔。对于时间平均效用排序反馈，论文在效用序列具有次线性总变分的假设下，提出了可以实现次线性后悔的算法。在全信息时间平均效用排序反馈下，该假设可以被移除。

关键创新：论文的关键创新在于针对排序反馈的在线学习问题，提出了新的算法，并在理论上分析了这些算法的后悔界。特别是在全信息时间平均效用排序反馈下，论文证明了可以移除对效用序列变分的假设，这是一个重要的理论突破。此外，论文还证明了当所有玩家都遵循论文提出的算法时，重复博弈可以达到近似的粗略相关均衡。

关键设计：论文的关键设计包括：(1) 针对不同的反馈设置和排序机制，设计不同的在线学习算法；(2) 利用效用序列的变分特性来约束后悔界；(3) 在全信息时间平均效用排序反馈下，通过巧妙的分析，移除了对效用序列变分的假设。具体的算法细节和参数设置在论文中进行了详细描述。

📊 实验亮点

论文证明了在一般情况下，使用瞬时效用排序反馈无法实现次线性后悔。在效用序列具有次线性总变分的假设下，论文提出的算法实现了次线性后悔。特别是在全信息时间平均效用排序反馈下，可以移除该假设。实验结果表明，该算法在在线大型语言模型路由任务中表现出良好的性能。

🎯 应用场景

该研究成果可应用于人机交互、推荐系统、在线广告等领域。例如，在推荐系统中，用户可能更愿意提供物品的排序而非具体的评分。该算法可以利用用户的排序反馈来优化推荐策略。此外，该研究还可应用于博弈论，用于计算近似的粗略相关均衡。

📄 摘要（原文）

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