技術要約：潜在状態バンディットのための適応的探索

1. 問題定式化

本論文は、報酬分布が自律的に進化する観測不可能な（潜在的な）マルコフ状態に依存する、非定常なマルチアームドバンディット問題を取り扱う。標準的なコンテキストバンディットとは異なり、学習者は状態 $s_t$ を直接観測することはできず、選択されたアクション $a_t$ と、その結果得られる確率的な報酬 $r_t$ のみを観測できる。

核心となる課題は、隠れた状態に応じて最適なアームが変化することであるが、学習者は行動と報酬の履歴のみから現在の状態を推論しなければならない。この設定は、以下の3つの具体的な技術的困難をもたらす：

1. 混同された報酬推定： 標準的なアルゴリズムは状態分布にわたって報酬を平均化するため、最適なアームが状態間で変化する場合、系統的なバイアスが生じる。
2. 時間的な報酬帰属： 報酬のパフォーマンスの変化が、学習の進展によるものか、あるいは隠れた状態の遷移によるものかを区別することが困難である。
3. 限定的な状態情報： アルゴリズムは状態の特徴量に直接条件付けることができず、間接的な信号に頼らざるを得ない。このタスクは、状態空間が大きくなるにつれてより困難になる。

目標は、現在の隠れた状態における最適なアームの報酬と、実際に選択されたアームとの累積的な差として定義される**動的レグレット（dynamic regret）**を最小化することである。

2. 手法

著者らは、LinUCBフレームワークに**ラグ付きコンテキスト（Lagged Context）とプロービング戦略（Probing Strategies）**を統合した一連のアルゴリズムを提案している。このアプローチは、潜在的なマルコフ遷移モデルを明示的に推定することを避け、代わりに低次元の統計量を用いて状態を分離することに依存している。

2.1 ラグ付きコンテキスト (LC-UCB)

最初のコンポーネントである**ラグ付きコンテキストUCB (LC-UCB)**は、直前の行動と報酬のペア $(a_{t-1}, r_{t-1})$ をコンテキスト特徴ベクトル $\phi_t$ として扱う。

• 直感： マルコフ的な状態変化が緩やかな場合、直前の報酬は直前の状態 $s_{t-1}$ に関する情報を提供し、それは現在の状態 $s_t$ と高い相関を持つ。
• メカニズム： このアルゴリズムは、$(a_{t-1}, r_{t-1})$ から現在の報酬 $r_t$ へのマッピングを学習する。これにより、学習者は状態を暗黙的に追跡し、すべての状態にわたる平均ではなく、推論された直近の状態に最適なアームを選択できるようになる。
• 限界： 複数の状態が同じアクションに対して同様の報酬を生み出す場合（非識別性）、LC-UCBは識別不能となり、状態推論における曖昧さを招く可能性がある。

2.2 指紋（フィンガープリント）のためのプロービング

この曖昧さを解消するために、著者らは、隠れた状態を一意に特定する複数のアームからの報酬の結合観測である「状態の指紋（state fingerprints）」を生成するプロービング戦略を導入している。2つのパラダイムが提案されている：

1. ランダム化プロービングUCB (RP-UCB)： 複数の実験ユニット（例：ユーザー）に対して異なるアームを同時に割り当てることが可能な場合に適用可能。これは、同じタイムステップからの真の結合観測 $(r_0, r_1)$ を収集する。
2. 逐次プロービングUCB (SP-UCB)： 単一ユニットの設定に適用可能。アームを連続的にサンプリングし（例：時刻 $t$ でアーム0、時刻 $t+1$ でアーム1）、そのペア $(r_t, r_{t+1})$ を合成された指紋として扱う。これは、状態が「粘着性（sticky）」（高い自己遷移確率）を持つという仮定に基づいている。

2.3 適応的探索 (AdaRP-UCB / AdaSP-UCB)

固定スケジュールのプロービングは、モデルに自信がある場合でもレグレットを発生させる。著者らは、3つのゲーティングメカニズムを用いて、必要に応じてのみ指紋を更新する**適応的プロービング（Adaptive Probing）**のバリアントを提案している：

• 残差ゲート (Residual Gate)： 予測誤差（スチューデント化残差）が閾値を超えた場合にプロービングをトリガーする。これは、モデルのドリフトや状態遷移を示唆する。
• 不確実性ゲート (Uncertainty Gate)： 上位2つのUCBスコアの差が小さい場合にプロービングをトリガーする。これは、アーム選択における高い不確実性を示す。
• 陳腐化（ハザード）ゲート (Staleness/Hazard Gate)： 指紋が指数関数的なハザード関数によって定義される期間更新されていない場合にプロービングをトリガーし、情報の陳腐化を防ぐ。

これらのゲートは、振動的な挙動を防ぐために、最小プロービング間隔（$\tau_{min}$）に従う。

3. 主な貢献

1. アルゴリズムの枠組み： 潜在状態バンディットを扱うために、ラグ付きコンテキストと協調的なプロービングを組み合わせた、LC-UCB、RP-UCB、SP-UCB、およびそれらの適応的バリアント（AdaRP-UCB、AdaSP-UCB）の開発。これらは、隠れた状態の完全なマルコフモデルを推定することなく動作する。
2. 理論的分析： 動的レグレットを、表現の曖昧さ（近似誤差）、プローブのコスト、および指紋が陳腐化した後のドリフトの3つの要素に分解。本論文は、適応的プロービングがこれらの要因のバランスを取ることでレグレットを最小化することを示す境界（bounds）を提供している。
3. 実証的検証： 隠れた状態の数 ($S$)、遷移率（自己遷移確率 $p_{stay}$）、報酬ノイズ ($\sigma$)、およびタイムホライゾン ($T$) を変化させた体系的な評価。

4. 実験結果

アルゴリズムは、古典的なベースライン（UCB1、Thompson Sampling）、敵対的メソッド（EXP3）、および非定常メソッド（Sliding Window UCB、Discounted UCB）と比較して評価された。

• パフォーマンス： 適応的プロービング手法（特にAdaRP-UCBおよびAdaSP-UCB）は、サマリー（指紋）が状態を区別でき、かつ十分に頻繁に更新される環境において、すべてのベースラインを一貫して上回った。
  • AdaRP-UCB は、13個のランダム化構成のうち12個で最も低いレグレットを達成し、揮発性の高い環境において顕著な利点を示した。
  • AdaSP-UCB は、単一ユニットの設定で、低ノイズ、低混合率、または大きな状態空間において最高のパフォーマンスを発揮した。
• 失敗モード： 本論文では、手法が劣化する特定の条件を特定している：
  • 高ノイズ： ノイズ ($\sigma$) がアーム間のギャップに対して高い場合、指紋は弱くなり、非定常なベースライン（D-UCBなど）の方が優れた性能を示す可能性がある。
  • 弱い指紋の分離性： 異なる状態が同様の結合報酬分布を生み出す場合、プロービング戦略はそれらを判別できない。
  • 高速な切り替え： 逐次プロービング（SP-UCB）は、プロービングウィンドウ内で状態が頻繁に変化する場合（低い $p_{stay}$）、合成された指紋が無効になるため失敗する。
• アブレーション研究： 指紋特徴量 ($\phi_{fp}$) を削除すると、粘着性のある状態の環境においてレグレットが大幅に増加し、結合観測の価値が確認された。ラグ付きコンテキスト ($\phi_{lag}$) を削除した場合の影響は、一部のランダム化設定において小さかった。これは、適応的なタイミングが主な推進力であったことを示唆している。

5. 意義と主張

本論文の主な貢献は、環境が自律的なマルコフ過程を通じて進化する**構造化された非定常性（structured non-stationarity）**に対する実用的なアプローチであるという点にある。標準的な非定常バンディットが変化を任意のドリフトとして扱うのに対し、またPOMDPが完全な観測性や複雑なデコーディングを必要とするのに対し、本アプローチは軽量な履歴サマリーとプロービングを使用して、現在の最適なアームの推定を維持する。

著者らは、以下のレジームにおいて、本手法が最も効果的であることを強調している：

1. 潜在状態が短期間において予測可能である（低混合率）。
2. プロービング戦略が、関連する状態を分離するのに十分な統計量（指紋）を生成できる。
3. 適応的なゲーティングメカニズムが、過度なプローブ・レグレットを発生させることなく、これらのサマリーを最新の状態に保つことができる。

本研究は、隠れた状態の完全な遷移ダイナミクスを学習する必要のない、計算効率の高い解決策（LinUCBに基づく）を提供することで、コンテキストバンディットと潜在状態強化学習の間の溝を埋めるものである。