From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits

技術要約：緩和された指数可能性から厳密な指数可能性へ：部分観測レストレス・バンディットに対する $t$ ステップ・アプローチ

問題提起
本論文は、隠れ状態が2つより多い（$K > 2$）部分観測レストレス・マルチアームド・バンディット（PO-RMAB）におけるウィトル指数（Whittle indices）の計算上の課題に対処している。完全観測の設定では、ウィトル指数は有限状態の動的計画法から導出される。しかし、部分観測下では、状態空間はシンプレックス上の連続的な信念ベクトルとなるため、値関数は閉形式の解を持たない無限ホライゾンの信念状態問題となる。

先行研究である Liu [10] は、能動的（active）な行動と受動的（passive）な行動の間の未知の決定境界を線形化することで、この問題を解決しようと試みた。これは1ステップ（$t=1$）の閾値政策となる。この手法は計算効率には優れているものの、長期的な継続価値を無視した1ステップの能動・受動比較に依存しているため、真の決定境界および厳密なウィトル指数に対して劣った近似しか得られない。

手法
著者らは、Liu [10] の線形化アプローチを一般化した $t$ ステップ・ルックアヘッド閾値政策 フレームワークを提案する。

1. $t$ ステップ・アドバンテージ関数： 与えられた補助金 $m$ とルックアヘッドの深さ $t$ に対して、本手法は有限ホライゾンの値反復に基づく「能動マイナス受動」のアドバンテージ関数 $r_{t,m}(\omega) = Q^A_{\beta,m,t}(\omega) - Q^P_{\beta,m,t}(\omega)$ を定義する。

   • $t=1$ のとき、これは線形閾値 $r_{1,m}(\omega) = \omega B^\top - m$ に簡略化され、$m$ に依存しない。
   • $t > 1$ のとき、アドバンテージ関数が $t$ ステップにわたる将来の報酬を組み込むため、閾値は補助金依存（$m$ 依存）となり、これにより閾値は真の決定境界をより正確に追跡できるようになる。

2. 初通過構造（First-Crossing Structure）： 政策は、信念 $x$ において $r_{t,m}(x) > r_{t,m}(\omega)$ である場合にアームを能動化する。ここで $\omega$ は閾値信念である。本手法は、閾値を通過するまでの受動的な信念更新下における「初通過時間」$L_t(x, \omega; m)$ を計算する。

3. 線形システムの構築： 初通過時間を用いて、著者らはリセット信念における値関数を推定するための線形システムを構築する。これにより、緩和された無差別方程式 $\Phi_t(\omega, m) = 0$ を解くことで、近似的なウィトル指数 $\hat{W}_t(\omega)$ の閉形式（または局所的な閉形式）の表現が得られる。

4. アルゴリズムと検証： 提案されたアルゴリズム（Algorithm 1）は、指数可能性を前提条件とすることなく、直接指数を計算する。もし複数の補助金解が特定の信念状態で存在する場合、アルゴリズムは候補間の最大ペア差が規定の許容誤差 $\epsilon_{ind}$ 以内であるかを確認する数値検証を行う。

主な貢献

• 閾値政策の一般化： 1ステップの線形閾値を $t$ ステップのファミリーへと拡張した。$t > 1$ では、アドバンテージ関数が将来の報酬を考慮するため、閾値は補助金 $m$ に応じて変化し、未知の決定境界をよりタイトに近似する。
• 理論的収束性： 元のウィトル指数可能性の仮定の下で、近似指数 $\hat{W}_t(\omega)$ が $t \to \infty$ において厳密なウィトル指数 $W(\omega)$ に幾何学的に収束することを証明した：
  $$|\hat{W}_t(\omega) - W(\omega)| = O(\beta^t)$$
  極めて重要な点として、指数可能性の仮定はアルゴリズムの実装のためではなく、収束を保証するために使用されている。
• 指数可能性の検証： 特定のインスタンスに対して指数可能性を検証するための実用的な数値基準を導入し、複数の候補補助金が生じるケースにも対応している。

実験結果
著者らは、2,715個のランダム生成された3状態インスタンスと、特定の高割引シナリオを用いて手法を評価した。

• 指数の精度： 近似指数のP95誤差は、$t$ の増加に伴い大幅に減少した（$t=1$ で $2.18 \times 10^{-2}$ から $t=8$ で $8.93 \times 10^{-4}$ へ）。
• ランキングの安定性： 高い割引因子（$\beta = 0.9999$）を持つ3アームのインスタンスにおいて、1ステップ近似（$t=1$）は正しいアームの順序を復元できなかった。しかし、わずかなルックアヘッドである $t=2$ を用いることで、厳密なウィトル指数の順序（$1 > 2 > 3$）を正常に復元できた。
• 政策の性能： 6アームの有限ホライゾン（$T=6$）インスタンスにおいて、$t=2$ および $t=5$ の政策は、1ステップのベースラインおよびマイオピック（近視眼的）政策を上回り、最適な動的計画法のベンチマークに近い報酬を達成した。
• 計算コスト： 実行時間は $t$ とともに緩やかに増加した（例：中央値が $t=1$ の0.05秒から $t=15$ の0.20秒へ上昇）。これは、適度な深さが精度とコストの良好なトレードオフを提供することを示唆している。

意義と主張
本論文は、補助金依存の $t$ ステップ閾値を構築し、その厳密な指数への幾何学的収束を確立することで、Liu [10] が残したギャップを埋めるものであると主張している。著者らは、彼らのアプローチが以下の特性を持つことを強調している：

1. 指数可能性を入力として必要としないため、この性質が未知である問題にも適用可能である。
2. 高次元の部分観測モデルにおける未知の決定境界の計算可能な近似を提供する。
3. 高次元の信念モデルに対して部分保存則（PCL）の手法を適用するための将来的な基礎を、扱いやすい閾値構造を定義することで築いている。

本研究は、中程度のルックアヘッドの深さ（$t=2$ から $t=8$）であっても、高い精度と正しいランキングを得るのに十分であることを示しており、無限ホライゾンの信念状態POMDPを解くための実用的な代替手段を提示している。