数値スコアなしでどこまで学べるか：ランキングだけのオンライン学習と均衡計算

TL;DR（結論）

• 扱うのは、環境から数値の報酬ではなく「提案した行動の順位」だけが返る状況で、オンライン学習やゲームの均衡計算がどこまで可能かという問題です。
• 結論は単純な楽観論ではありません。瞬間効用にもとづくランキングだけでは一般に sublinear regret は不可能で、時間平均効用にもとづくランキングでも、Plackett-Luce モデルの温度が小さすぎるとやはり難しいと示します。
• 一方で、効用列の総変動が sublinear という追加仮定の下では新しいアルゴリズムで sublinear regret を達成でき、特に full-information の time-average ranking ではその仮定すら外せます。その結果、繰り返しゲームでは approximate coarse correlated equilibrium を計算できます。

なぜこの問題か

既存のオンライン学習の多くは、各時刻で各行動の数値効用、あるいは少なくとも数値報酬の一部が得られることを前提にしています。しかし human-in-the-loop の設定では、ユーザーが数値で評価するよりも、複数案の中でどれが上かを示すだけの方が自然です。またプライバシーや制度上の制約で、生の効用値を開示できない状況もあります。つまり、順位は実務上かなり現実的なフィードバックですが、理論側では数値報酬ほど整理されていませんでした。

核心：何を提案したのか

論文の核心は、新しいランキングフィードバックモデルを定義し、その下での regret の下限と上限を統一的に示したことです。順位生成には Plackett-Luce 型の確率モデルを使い、温度パラメータ τ でランキングの決定性を調整します。ここで τ が小さいほど順位はほぼ決定的になり、大きすぎるとほぼランダムになります。この温度が学習可能性の境界に深く関わる、というのが理論上の中心です。

続きはログイン/プランで閲覧できます。