技術的サマリー：欠損-MDP（miss-MDPs）

問題定義

本論文は、状態特徴量が動的に欠損している場合の不確実性下における逐次意思決定の課題に取り組んでいる。マルコフ決定過程（MDP）は完全観測性を前提とするが、現実のシナリオ（不完全なセンサーデータを伴う医療診断など）では、欠損した特徴量が頻繁に存在する。標準的な部分観測マルコフ決定過程（POMDP）は観測関数を通じてこれをモデル化できるが、行動 - 観測履歴からこの関数を学習することは一般的に識別不可能であり、計算的に困難である。

著者は特定の問題設定を定義する：既知の基礎 MDP（遷移関数 $T$）を持つが、欠損関数 $M$ が未知である miss-MDP と、行動 - 観測軌道のデータセットが与えられたとき、$\epsilon$-最適である方策 $\pi^*$ を計算することを目的とする。核心的な難しさは、計画を可能にするためにデータから $M$ を学習することであり、これは一般的な POMDP においては不可能であるが、特定のサブクラスにおいては可能である可能性がある。

手法

1. miss-MDPs の定義

著者は、POMDP の適切なサブクラスとして**欠損-MDP（miss-MDPs）**を導入する。

• 構造: miss-MDP はタプル $(S, A, T, b_0, \varrho, Z, M, \gamma)$ である。
• 観測空間: $Z = \times_{i \in I} (S_i \cup \{\perp\})$。ここで $\perp$ は欠損した特徴量を表す。
• 欠損関数（$M$）: 特徴量が観測されるか欠損するかの確率を決定する確率的関数 $M: S \to \Delta(Z)$。
• 欠損タイプ: この枠組みは、標準的な欠損データ分類（Rubin, 1976）を採用する：
  • MCAR（完全にランダムな欠損）: 欠損は状態値に依存しない。
  • MAR（ランダムな欠損）: 欠損は観測された特徴量にのみ依存する。著者は、常に観測される特徴量にのみ依存する「単純 MAR」と、一般的な MAR を区別する。
  • MNAR（ランダムでない欠損）: 欠損は観測されていない（欠損している）特徴量の値に依存する。

2. 学習アルゴリズム（PAC 保証）

本論文は、データセット $D$ から未知の欠損関数 $\hat{M}$ を近似するための、おそらく近似正解（PAC）学習アルゴリズムを提案する。このアプローチは、特定の欠損タイプの識別可能性に依存している。

• アルゴリズム $A_{sMAR}$（単純 MAR 用）:

  • 特徴量を「常に観測されるもの（$\hat{I}_{always}$）」と「潜在的に欠損するもの」に分割する。
  • 常に観測される特徴量の値に基づき、欠損インジケータの確率を推定する。
  • 定理 1: 単純 MAR において、データセットサイズが増加するにつれて $\hat{M}$ が真の $M$ に高い確率で収束することを証明する。

• アルゴリズム $A_{IMI}$（独立した欠損インジケータ用）:

  • MCAR、単純 MAR、および識別可能な MNAR の一部に適用可能。
  • 以下の仮定を置く：(1) 特徴量間の欠損インジケータの独立性、(2) 自己検閲の不存在（ある特徴量の値が自身の欠損性に影響を与えない）、(3) 正則性（特徴量が観測される確率がゼロでない）。
  • 各特徴量について、他の観測された特徴量に基づいて欠損確率を独立に推定する。
  • 定理 2: これらの仮定の下で $\hat{M}$ に対する PAC 保証を証明する。

• 方策の計算:

  • $\hat{M}$ が近似されると、著者は完全に指定された miss-MDP $\hat{P}$ を構築する。
  • 既存の POMDP ソルバ（例：SARSOP）を用いて、$\hat{P}$ に対する $\epsilon$-最適方策を計算する。
  • 定理 3: $\hat{M}$ が十分に正確であれば、得られる方策が真の miss-MDP $P$ に対して $\epsilon$-最適であることを証明する。

3. 理論的洞察

• 無視可能性: 著者は（注記 1 で）MAR（MCAR を含む）において、欠損関数の特定の確率は、ベイズの定理において相殺されるため、信念更新（現在の状態分布の維持）に対して「無視可能」であることを証明する。しかし、信念間の遷移確率は $M$ に依存するため、方策そのものを計算するには依然としてこの関数が必要である。

主要な貢献

1. 形式化: 欠損データ理論（MCAR、MAR、MNAR）を POMDP 枠組みに統合し、観測関数が学習可能な扱いやすいサブクラスを定義する miss-MDPs の導入。
2. 識別可能性分析: 一般的な POMDP 観測関数の識別不可能性と対照的に、履歴から欠損関数が学習可能な特定の条件（単純 MAR、自己検閲のない独立/MNAR）の特定。
3. PAC アルゴリズム: 欠損関数を学習するための、形式的な PAC 保証を備えたアルゴリズム（$A_{sMAR}$、$A_{IMI}$）の開発。
4. 最適性保証: 十分な精度で $\hat{M}$ を学習することが、真のシステムに対する $\epsilon$-最適方策の計算を可能にすることの証明。

実験結果

著者は 2 つのベンチマークでアプローチを評価した：

1. ICU: 800 の状態を持つ医療意思決定モデル（医師が患者を治療する）。
2. Predator: 最大 1,765 の状態を持つ追跡 - 逃走ゲーム（Tag の変種）。

知見:

• 近似の質: 正しい仮定の下では、学習された $\hat{M}$ と真の $M$ の間の総変動（TV）距離は、データセットサイズが増加するにつれてゼロに収束する。
• 方策のパフォーマンス: 学習された miss-MDP から導かれた方策は、近似が改善されるにつれて最適方策値（$\pi^*$）に収束する。
• 仮定への感度: 誤った仮定（例：MNAR で自己検閲があるデータを MAR と仮定すること）は、悪い近似と非最適方策につながる。
• ベースラインとの比較: 提案されたモデルベースのアプローチは、両方のベンチマークにおいてモデルフリーのベースライン（メモリあり/なしの PPO、POMCP）を大幅に上回った。著者は、モデルフリー手法の失敗を、miss-MDP の特定の部分観測構造を効果的に処理できないことに起因すると指摘し、欠損が除去された場合、これらの手法は成功したと述べている。

意義と主張

本論文は、欠損データ理論と逐次意思決定の間のギャップを埋めると主張する。その主な意義は、POMDP における欠損データを処理するための原理的なモデルベースアプローチを提供し、統計的保証（PAC）を伴う点にある。

欠損を偶発的なものとみなすか、保証なしに補完に依存する先行研究とは異なり、この研究は以下の点で優れている：

1. 欠損プロセスを明示的にモデル化する。
2. 誤差の理論的限界を伴ってデータから欠損関数を学習する。
3. この学習されたモデルを活用して、結果として得られる方策の近似的最適性を保証する。

著者は控えめに、現在のアプローチは基礎 MDP の遷移関数が既知であると仮定していることに言及している。この仮定を解除し、一般的な miss-POMDP へ枠組みを拡張することを将来の課題として特定している。実験結果は、欠損メカニズムが識別可能なパターンに従う設定において、彼らのアプローチが直接の POMDP 定式化（POMCP など）や深層強化学習手法（PPO など）よりも優れていることを確認している。