ランキングフィードバックを用いたオンライン学習と均衡計算

要約: 任意で、さらには敵対的な環境におけるオンライン学習は、逐次意思決定論の分野で広く研究されており、ゲーム理論における均衡計算と密接に関連している。ほとんどの既存のオンライン学習アルゴリズムは環境からの \emph{数値} ユーティリティフィードバックに依存しており、これは人間を介したループ型のアプリケーションでは利用できない場合があるか、プライバシー上の懸念により制限されることがある。 本論文では、学習者が各タイムステップで提案された行動の集合に対する \emph{ランキング} のみを観察するオンライン学習モデルを研究する。私たちは、2つのランキング機構を検討する：現在のタイムステップでの \emph{瞬時} ユーティリティにより誘導されるランキングと、現在のタイムステップまでの \emph{時間平均} ユーティリティにより誘導されるランキング、\emph{全情報} および \emph{バンディット} フィードバック設定の下で。標準的な外部レグレット指標を用いると、一般には \emph{瞬時} ユーティリティ \emph{ランキング} フィードバックではサブ線形の後悔は不可能であることを示す。さらに、ランキングモデルが比較的決定論的である場合、すなわち十分に小さな温度を持つ \emph{Plackett-Luce} モデルの下では、\emph{時間平均} ユーティリティ \emph{ランキング} フィードバックでもサブ線形の後悔は不可能である。 その後、ユーティリティ列の総変動がサブ線形であるという追加仮定の下でサブ線形の後悔を達成する新しいアルゴリズムを開発する。特筆すべきは、全情報の \emph{時間平均} ユーティリティランキングフィードバックの場合、この追加仮定を除去できることである。結果として、正規形ゲームの全てのプレイヤーが私たちのアルゴリズムに従うと、反復プレイは近似的な粗相関均衡を生み出す。 また、オンライン大規模言語モデルのルーティングタスクにおける私たちのアルゴリズムの有効性を示す。