テクニカル・サマリー：複数の正解を持つ学習 – 異なるフィードバックモデル下での後悔界（Regret Bounds）

1. 問題定義と動機

本研究は、単一の入力インスタンス $x$ に対して、単一のターゲットラベルではなく、許容されるラベルの集合 $S \subseteq \mathcal{Y}$ が存在する「複数の正解を持つオンライン学習」の問題を扱う。この定式化は、言語生成（プロンプトに対して多くの適切な補完が存在する）、オープンエンドな質問回答、対話生成、およびレコメンデーションシステムといった現代的なタスクに基づいている。

本研究は、ラウンド $t \in [T]$ で進行するオンライン学習パラダイムに焦点を当てている。各ラウンドにおいて、アドバーサリ（敵対者）はインスタンス $x_t$ と許容されるラベルの集合 $S_t$ を提示する。学習者はラベル $\hat{y}_t$ を予測し、$\hat{y}_t \notin S_t$ である場合に損失 1 を被る。本論文では、この問題を 3 つの異なるフィードバックモデルの下で分析している：

1. Mistake-unknown（間違いが不明）: 学習者は単一の有効なラベル $y_t \in S_t$（アドバーサリによって選択されたもの）のみを受け取るが、自身の予測が正しかったかどうかは知らされない。
2. Mistake-known（間違いが既知）: 学習者は単一の有効なラベル $y_t \in S_t$ と、自身の予測 $\hat{y}_t$ が間違いであったかを示すバイナリインジケーターを受け取る。
3. Set-valued（集合値）: 学習者は、有効なラベルの集合全体 $S_t$ を開示される。

分析は、実現可能（realizable）な設定（すべての $t$ に対して $h^*(x_t) = S_t$ となる仮説 $h^* \in \mathcal{H}$ が存在する）と、アグノスティック（agnostic）な設定（学習者が累積損失を最小化する $\mathcal{H}$ 内の最良の仮説と競合する）の両方を対象としている。

2. 手法と組合せ論的特徴付け

著者らは、各フィードバックモデルで利用可能な情報に適合させたツリー・シャッタリング（tree-shattering）議論を通じて、マルチラベル仮説クラス $\mathcal{H}$ の学習可能性を特徴付けるための新しい組合せ論的次元を導入している。

組合せ論的次元

• Set-Valued Littlestone Dimension ($LD_{set}$): ノードが $\mathcal{Y}$ の部分集合でラベル付けされた集合値ツリー上で定義される。ツリーがシャッター（破砕）されるとは、すべての予測のパスに対して、開示された集合 $S_t$ と整合しつつ、予測されたラベルに対して間違いを犯す仮説が存在することを指す。
• Mistake-Known Littlestone Dimension ($LD_{known}$): ノードが単一のラベルでラベル付けされたマルチラベルツリー上で定義される。シャッタリングには、開示された単一のラベル $y_t$ との整合性、および予測に対する間違いが必要となる。
• Mistake-Unknown Littlestone Dimension ($LD_{unknown}$): 「間違いオフセット（mistake offset）」関数を用いて定義される。ツリーが $d$-shattered であるとは、任意のパスにおける累積的な間違いの数に仮説のオフセットを加えたものが $d$ を超えることを指す。これは、正誤に関する即時のフィードバックが欠如していることを考慮している。

アルゴリズム

実現可能設定のために、著者らは各フィードバックモデルに対する**標準最適アルゴリズム（SOA: Standard Optimal Algorithms）**を提案している。これらのアルゴリズムは、整合的な仮説のバージョン空間を維持し、残されたバージョン空間の最悪ケースの次元を最小化する予測を行う。

• Mistake-Unknown 用 SOA: バージョン空間とオフセット関数を維持し、結果として得られるサブクラスの最大 $LD_{unknown}$ を最小化するラベルを予測する。
• Mistake-Known 用 SOA: 潜在的な間違いビットによって形成されるサブクラスの最大 $LD_{known}$ を最小化するように予測を行う。
• Set-Valued 用 SOA: 開示された集合 $S_t$ によって形成されるサブクラスの最大 $LD_{set}$ を最小化するように予測を行う。

3. 主要な結果

実現可能なオンライン学習

本論文は、任意のマルチラベルクラス $\mathcal{H}$ における実現可能な設定での最適な間違い界（mistake bound）の完全な特徴付けを提供している：

• Mistake-unknown: 最適な間違い界は $\min(LD_{unknown}(\mathcal{H}), T)$ である。
• Mistake-known: 最適な間違い界は $\min(LD_{known}(\mathcal{H}), T)$ である。
• Set-valued: 最適な間違い界は $\min(LD_{set}(\mathcal{H}), T)$ である。

これらの結果は、有限なクラスに関する先行研究を、任意（おそらく無限）の仮説クラスへと一般化するものである。著者らは、$LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$ であり、これは任意のインスタンスに対するすべての仮説のラベル集合の共通部分が空でない場合に成立することを証明している。

アグノスティック・オンライン学習（後悔界）

重要な貢献は、アグノスティック設定において、後悔率（regret rates）がフィードバックモデル間で劇的に変化することを示した点にある。これは、後悔が通常 $\tilde{\Theta}(\sqrt{T})$ となる単一ラベル学習とは対照的である。

1. Mistake-Unknown: 著者らは、たとえ $LD_{unknown}=1$ の単純な仮説クラスであっても、後悔が $T$ に対して線形（$\Omega(T)$）に増大し得ることを示している。これは、$LD_{unknown}$ によって特徴付けられる実現可能な学習可能性が、このフィードバックモデルにおける劣線形な後悔を保証しないことを意味している。
2. Mistake-Known: 論文は、$O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$ の劣線形な後悔の上界を確立している。これは、SOA ベースのエキスパートを用いた、非確率的バンディット（non-stochastic bandits）への還元によって達成される。
3. Set-Valued:
   • 特定のクラス（例：クラス $H_3$）については、後悔は定数（$O(1)$）となる。
   • 一般的なクラスについては、後悔は $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$ で抑えられる。注目すべきは、この界がラベル空間のサイズ $|\mathcal{Y}|$ に依存しないことであり、これにより無限のラベル空間に対しても成立することが可能となっている。

バッチ学習への示唆

導出された組合せ論的次元とオンラインの界は、対応するバッチ学習問題のサンプル複雑性の界を暗示している。著者らは、フルセット・フィードバックモデルにおけるバッチ学習の最初の既知の上界を提供し、単一正解ケースにおける既存の境界を有限から無限のクラスへと改善している。

4. 意義と主張

本論文は、3 つの異なるフィードバックモデルの下での、実現可能なオンライン・マルチラベル学習に関する初の完全な組合せ論的特徴付けを提供することを主張している。その主要な理論的意義は、実現可能な学習可能性とアグノスティックな学習可能性の分離にある。Mistake-unknown 設定においては、標準的なリトルストーン次元（Littlestone dimension）では意味のある後悔界を捉えることができない。

さらに、本研究はアグノスティックなマルチラベル学習における豊かな構造を浮き彫りにしている：

• フィードバックモデルは、達成可能な後悔率を根本的に変える（線形から定数へ）。
• 集合値フィードバックモデルは、特定のクラスに対して定数の後悔を、また一般的なクラスに対して次元に依存しない界を可能にする。これは単一ラベル学習では観察されない現象である。
• これらの結果は、アグノスティックなマルチラベル学習を特徴付けるには、実現可能な学習可能性に十分なもの以上の組合せ論的オブジェクトが必要であることを示唆している。

著者らは、真の許容ラベル集合に対するエラーを最小化するという基礎的な予測タスクに、より適切に適合させるために、自身の後悔の定義が先行研究（例：Joshi et al. [JLB+25] および Raman et al. [RST24]）とは異なっていることを明記している。