在仅能获取动作排名的环境下,实现低遗憾学习并达成博弈均衡。
Online Learning and Equilibrium Computation with Ranking Feedback
- 基于排名反馈设计新算法,突破传统数值反馈限制
- 在序列总变差小的条件下实现亚线性遗憾
- 适用于人机协同与隐私敏感场景,如大模型路由
在线学习在任意甚至对抗性环境中被广泛研究,且与博弈论中的均衡计算密切相关。现有算法通常依赖环境提供的数值型效用反馈,但在人机协同应用中可能不可用或涉及隐私问题。本文研究一种仅能观察动作集合排名的在线学习模型,考虑两种排名机制:当前时刻瞬时效用排名和截至当前时刻的时间平均效用排名,涵盖全信息与贝叶斯反馈设置。通过标准外部遗憾度量,我们证明在一般情况下,瞬时效用排名反馈下无法实现亚线性遗憾;当排名模型较确定(如温度足够小的Plackett-Luce模型)时,时间平均效用排名反馈同样无法实现。随后,我们提出新算法,在效用序列具有亚线性总变差的额外假设下达到亚线性遗憾。值得注意的是,在全信息时间平均效用排名反馈下,该假设可移除。因此,当博弈中所有玩家采用本算法时,重复博弈将收敛至近似粗相关均衡。我们在大语言模型路由任务中验证了算法有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。