論文の概要: Online Learning and Equilibrium Computation with Ranking Feedback

• arxiv url: http://arxiv.org/abs/2603.19221v1
• Date: Thu, 19 Mar 2026 17:59:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-20 17:19:06.327683
• Title: Online Learning and Equilibrium Computation with Ranking Feedback
• Title（参考訳）: ランク付けフィードバックを用いたオンライン学習と平衡計算
• Authors: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang,
• Abstract要約: 本研究では,学習者が各段階において提案された行動の集合に対してのみ,一品位を観察するオンライン学習モデルについて検討する。 即時的効用評価フィードバックでは, サブリニアな後悔は不可能であることを示す。 我々は,実用性列が線形全変量を持つという仮定を付加して,サブ線形後悔を実現するアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 47.07396244650246
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \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.
• Abstract（参考訳）: オンライン学習は、任意の、おそらくは逆の環境において、シーケンシャルな意思決定において広範囲に研究され、ゲーム理論における平衡計算と密接に関連している。 既存のオンライン学習アルゴリズムの多くは環境からのemph{numeric}ユーティリティフィードバックに依存している。 本稿では,学習者が各段階において提案した一連の行動に対して,emph{ rank}のみを観測するオンライン学習モデルについて検討する。 本稿では,現在の時刻における \emph{instantaneous} ユーティリティによるランキングと,現在の時刻における \emph{full-information} と \emph{bandit} フィードバック設定による \emph{time-average} ユーティリティによるランキングの2つについて検討する。 標準の外部回帰測定値を用いて、即時効用ランキングのフィードバックにより、サブ線形後悔は不可能であることを示す。 さらに、ランク付けモデルが比較的決定論的である場合、温度が十分に小さいプラケット・リュックモデルの下では、時間平均ユーティリティランキングフィードバックではサブ線形後悔も不可能である。 そこで我々は, 効用系列が線形全変量を持つという仮定を付加して, サブ線形後悔を実現するアルゴリズムを開発した。 特に、情報全体の時間平均ユーティリティランキングフィードバックのために、この追加仮定を除去することができる。 その結果、正規形式ゲーム内の全てのプレイヤーが我々のアルゴリズムに従うと、繰り返しプレイは近似した粗い相関平衡をもたらす。 また、オンラインの大規模言語モデルルーティングタスクにおいて、アルゴリズムの有効性を実証する。

関連論文リスト

• Optimal training-conditional regret for online conformal prediction [20.643619398558315]
  本研究では,未知分布のドリフトを受ける非定常データストリームのオンラインコンフォメーション予測について検討する。 具体的には、急激な変化点と滑らかなドリフトの2種類の分散シフトを持つ独立に生成されたデータに焦点を当てる。 我々は,オンライン完全共形アルゴリズムにおいて,予測セットの適切な制約の下でミニマックス下限と一致する非漸近的後悔保証を確立する。
  論文  参考訳（メタデータ） (2026-02-18T15:31:15Z)
• Optimal Linear Decay Learning Rate Schedules and Further Refinements [46.79573408189601]
  実際に使用される学習率のスケジュールは、理論によって推奨されるものとはほとんど似ていない。 我々はこの理論と実践的ギャップの多くを閉じ、その結果、新しい問題適応型学習率スケジュールを導き出すことができる。
  論文  参考訳（メタデータ） (2023-10-11T19:16:35Z)
• Online Control of Unknown Time-Varying Dynamical Systems [48.75672260851758]
  非確率制御モデルにおいて、未知のダイナミクスを持つ時間変化線形系のオンライン制御について検討する。 本研究では,反省行動 (SLS) や反省反応 (Youla) , 線形フィードバック政策 (線形フィードバックポリシー) といった一般的な政策のクラスに関して, 後悔すべき境界について検討する。
  論文  参考訳（メタデータ） (2022-02-16T06:57:14Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Active Online Learning with Hidden Shifting Domains [64.75186088512034]
  本稿では,その後悔度とラベルクエリ数とを適応的にバランスさせる,驚くほど単純なアルゴリズムを提案する。 我々のアルゴリズムは、異なる領域からの入力のインターリービングスパンを適応的に処理できる。
  論文  参考訳（メタデータ） (2020-06-25T15:23:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。