Multiscale Reward Hedging from Correct Demonstrations

技術要約：正しいデモンストレーションからのマルチスケール報酬ヘッジング

問題定式化
本論文は、複数のアクションが最適となり得る設定において、正しいデモンストレーションから学習する問題に対処している。標準的な教師あり学習とは異なり、学習者はコンテキスト $x_t$ に対して単一の有効なデモンストレーション $a^*_t$ を観察するが、自身の予測 $\hat{a}_t$ が正しかったかどうかのフィードバックや、基礎となる報酬関数、あるいは損失の大きさに関する情報は一切受け取らない。目的は、未知の報酬関数 $r^*$ に対して、累積的な「隠れたギャップ（hidden gap）」（最適アクションと学習者のアクションとの差）を最小化することである。

この設定は、有限の報酬クラスに関する先行研究（Joshi et al., 2026）を、これまで未解決であった連続的な報酬クラスへと一般化したものである。フィードバックモデルは、オンライン逆最適化や標準的なコンテキスト・バンディットとは異り、学習者が報酬値や正誤ビットを一度も観測せず、単に未知の最適アクション集合の中から一つの有効なアクションのみを観測するという点で異なる。

手法：マルチスケール報酬ヘッジング
核となる貢献は、既知のタイムホライゾン（時間地平）を必要としない、決定論的なマルチスケール報酬ヘッジング・アルゴリズムである。その手法は以下のコンポーネントに基づいている：

1. ギャップ指標とプロキシ： アルゴリズムは、最適性ギャップ関数 $g_r(x, a) = \sup_{b \in A(x)} r(x, b) - r(x, a)$ に焦点を当てる。報酬関数を直接推定する代わりに、学習者は一連の「寛容なバイナリ・プロキシ（tolerant binary proxies）」に対する加重投票を維持する。
2. マルチスケール・カバリング： 精度スケール $\epsilon_j = 2^{-j-1}$ のシーケンスに対して、アルゴリズムはギャップ関数クラス $G$ の適切な $\epsilon_j$-カバー（$C_j$）を構成する。各要素 $h \in C_j$ は、ギャップ $h(x, a) \le \epsilon_j$ である場合にアクションを「良い」とラベル付けするプロキシ $q_{j,h}$ を定義する。
3. 共有投票： 各スケールで個別の学習者を走らせる（これでは互換性のないアクションが生成される）のではなく、アルゴリズムはすべてのスケールにわたるすべてのプロキシを単一の加重投票へと集約する。スケール $j$ におけるプロキシの初期重みは $2^{-j}$ に比例する。
4. 更新ルール： 更新は「ミス・アンアウェア（mistake unaware）」である。デモンストレーション $a^*_t$ を観察すると、アルゴリズムはプロキシのデモンストレーションに対する判断と学習者の予測との比較のみに基づいて重みを更新する：
   • プロキシがデモンストレーションを「良い」と呼び、かつ学習者のアクションを「悪い」とした場合、そのプロキシの重みを2倍にする。
   • プロキシがデモンストレーションを「悪い」とした場合、その重みをゼロにする。
   • それ以外の場合、重みは変更されない。
     このルールにより、学習者のアクションが特定のスケールに対して大きなギャップを持つ場合、そのスケールを表すプロキシの重みが増加し、そのスケールの誤差に対して効果的に「ヘッジ（回避）」が行われる。

主要な理論的結果

• ホライゾンフリーの裾（Tail Bounds）： アルゴリズムは、損失が閾値 $2^{-j}$ を超えるラウンド数に関する同時テール境界を提供する：
  $$|\{t : \ell_t > 2^{-j}\}| \le \log_2 N(G, 2^{-j-1}) + j$$
  ここで $N(G, \epsilon)$ はギャップクラスの被覆数（covering number）である。これらのテールを統合することで、タイムホライゾン $T$ に依存しない累積隠れたギャップの境界が得られる：
  $$\sum_{t=1}^T \ell_t \le \sum_{j \ge 1} 2^{-j} \log_2 N(G, 2^{-j-1}) + 2$$
  この和は、メトリック・エントロピー積分 $H_{dyad}(G)$ によって抑えられる。

• 多項式エントロピーとリグレット率：

  • 多項式被覆数 $N(G, \epsilon) \le (A/\epsilon)^d$ を持つクラスの場合、総ギャップは $O(d \log A)$ で抑えられる。
  • これは、オンライン・トゥ・バッチの設定において $O(d/m)$ の統計的レートに相当する。
  • 線形コンテキスト推薦： 有界な線形報酬（パラメータ半径 $B$、メニュー直径 $K$）について、任意のコンパクトなメニューに対してリグレットは $O(d)$ となる。これは、構造的制限（M-凸性など）を必要とせずに、不適切予測器（improper predictor）を用いて達成された、任意のメニューに対する最初の多項式有限境界である。
  • 低ランクおよびニューラル報酬： 本フレームワークは、低ランク双線形報酬（$O(BKr(m+n))$）および、ネットワークの深さとパラメータに明示的な依存関係を持つ有界ReLUネットワークへと拡張される。

• 計算量：

  • 一般的なアルゴリズムは情報理論的であり、被覆の列挙により計算コストが高くなる可能性がある。
  • しかし、1次元のリプシッツ・パラメータ曲線（例：固定半径ランク2推薦）については、アルゴリズムは厳密であり、多項式時間で動作する。具体的には、メニューサイズ $k$ と報酬評価コスト $C$ を持つ固定半径ランク2推薦の場合、時間計算量は $O(kCT^2)$ である。

• 下界とロバスト性：

  • 本論文は、エントロピー指数 $d$ を持つ連続クラスに対する一致する $\Omega(d)$ の下界を証明しており、$O(d)$ の依存関係のタイトさを確認している。
  • ロバストなバリアントは、劣最適なデモンストレーションを扱い、リグレット境界にデモンストレーターの累積的な劣最適性 $\Delta_T$ を加えるだけで済む。

意義と主張
本論文は、連続報酬クラスにおける正しいデモンストレーションからの学習という未解決問題を解決したと主張している。その主な意義は以下の通りである：

1. 連続クラスに対する初のホライゾンフリー保証： メトリック・エントロピーに基づき、タイムホライゾン $T$ に依存しない連続クラスのリグレット境界を提供する。
2. 任意のメニューに対する不適切予測： 線形コンテキスト推薦において、構造的制限（M-凸性など）を必要とせず、あるいはより高い次元依存性を招くことなく、$O(d)$ のリグレットを達成する。
3. 特定の幾何学における効率性： 一般的な投票は高コストであるが、本論文は、アルゴリズムが厳密かつ多項式時間で動作する非自明なケース（1次元リプシッツ曲線）を特定しており、情報理論的境界と計算可能性の架け橋となっている。
4. 実証的検証： MovieLensデータを用いた再現可能なストレス・テストにより、報酬を観察することなくアクションのデモンストレーションのみを使用して、アルゴリズムがスケールに適応し、提示された評価ポリシーや適切な（proper）オンライン・ベースラインよりも平均潜在ギャップを改善できることを示している。

著者は、一般的な解法は不適切（voteが単一の有効な報酬パラメータに対応するとは限らない）であるが、ターゲットとなる報酬ギャップを正常に最小化できることを強調しており、これは報酬パラメータ自体の推定を目指す「適切な（proper）」オンライン逆最適化手法とは一線を画している。