技術要約：アクションによってトリガーされる観測を伴う強化学習

1. 問題定義

本論文は、状態観測の可用性が外生的または固定されているのではなく、アクションによってトリガーされるという、特定の部分観測マルコフ決定過程（POMDP）のクラスに対処している。標準的な強化学習では、エージェントはアクションのたびに新しい状態を観測する。しかし、臨床診断や金融取引などの多くの実用的なシナリオでは、状態観測を得ることはコストがかかる、信頼性が低い、あるいは特定の行動によってトリガーされる必要がある。

著者らは、この設定を**アクション・トリガー型・散発的追跡可能マルコフ決定過程（ATST-MDP）**として定式化している。

• メカニズム： エージェントが状態 $s$ においてアクション $a$ を実行すると、報酬を受け取り、環境は $s'$ へと遷移する。極めて重要な点は、$s'$ が常に観測されるわけではないということである。確率 $\beta(a)$ で「観測イベント（データバースト）」が発生し、$s'$ と前回のバースト以降の累積報酬が明らかになる。確率 $1-\beta(a)$ では、状態フィードバックは提供されない。
• 課題： エージェントは、制御ポリシーを最適化すると同時に、不確実性を減少させるために（より高い $\beta(a)$ を持つアクションを選択することで）いつ観測をトリガーするかを決定しなければならない。つまり、情報の獲得コストと制御性能のバランスを取る必要がある。
• 相違点： ノイズはあるが頻繁に発生する標準的なPOMDPや、フィードバックが単に遅れている外生的な遅延を伴うRLとは異なり、ATST-MDPは、エージェントのアクション選択が状態の開示頻度を直接決定するという内生的な遅延を特徴とする。

2. 手法

2.1 拡張状態空間とベルマン方程式

部分観測性を扱うために、著者らは拡張状態空間 $\mathcal{X} = \mathcal{S} \times \mathcal{A}^{<\infty}$ を定義している。拡張状態 $x = (s_1, a_1, \dots, a_n)$ は、最後に観測された状態 $s_1$ と、その後のアクションのシーケンスで構成される。

• 十分性： 拡張状態は履歴の十分統計量として機能し、この問題を $\mathcal{X}$ 上の完全観測MDPとして扱うことを可能にする。
• ダイナミクス： $\mathcal{X}$ 上の遷移は混合である。確率 $\beta(a)$ で、状態は新しい観測状態へとリセットされる（$x$ が $s'$ になる）。確率 $1-\beta(a)$ では、アクションシーケンスが追加される（$x \leftarrow x \cdot a$）。
• ベルマン方程式： 著者らは、この拡張空間における価値関数 $V^\pi$ および $Q^\pi$ に関するベルマン最適方程式を導出し、最適な拡張ポリシー $\pi^*$ の存在を証明している。

2.2 アクションシーケンスへの再定式化

拡張状態空間が無限に分岐することを認識し、著者らはデータバーストの更新構造（renewal structure）に基づく再定式化を提案している。すなわち、アクションごとに決定を下すのではなく、エージェントは各データバーストにおいてアクションシーケンス $a \in \mathcal{A}^\mathbb{N}$ をコミットし、次の観測が発生するまでそれを実行する。

• これにより、問題は $(\mathcal{S}, \mathcal{A}^\mathbb{N})$ 上の決定プロセスへと変換される。
• 価値関数 $K^\pi(s, a)$ は、状態 $s$ からアクションシーケンス $a$ を実行し、次のデータバーストが発生するまでに蓄積される期待割引報酬と、明らかになった状態からの継続価値を表す。

2.3 線形MDP仮定下での線形表現

無限次元のアクションシーケンス空間を扱いやすくするため、本論文では、遷移カーネルと報酬が特徴マップ $\phi(s, a)$ に対して線形であるという線形MDP構造（仮定 4.1）を仮定している。

• 重要な洞察： この仮定の下では、アクションシーケンスの価値関数 $K^\pi$ は、有限次元の特徴マップ $\psi: \mathcal{S} \times \mathcal{A}^\mathbb{N} \to \mathbb{R}^{2d}$ において線形表現を持つ。
• 構築： 特徴マップ $\psi$ は、遷移ダイナミクスから導出されるアクション行列 $M_a$ と観測確率 $\beta_a$ を用いて構築される。具体的には、$\psi$ はアクションシーケンスに沿った特徴の進化と、各ステップでデータバーストが発生する確率をエンコードする。
• 結果： $K^\pi(s, a) = \langle \psi(s, a), v^\pi_{1,2} \rangle$ となり、ここで $v^\pi_{1,2}$ はポリシーに依存するベクトルである。これにより、無限のアクション空間にもかかわらず、標準的な回帰ベースの手法を使用することが可能となる。

2.4 推定および学習アルゴリズム

本論文では、ATST-LSVI-UCB（Action-Triggered Sporadically Traceable Least-Squares Value Iteration with Upper Confidence Bounds）を提案している。

• 特徴推定： 真の特徴マップ $\psi$ は未知であるため、アルゴリズムはリッジ回帰と経験平均を用いて、探索データから基礎となるアクション行列 $M_a$ と観測確率 $\beta_a$ を推定する。定理 4.6 および系 4.9 は、$\psi$ の $\epsilon$-許容近似を構築するための非漸近的なサンプル複雑性の境界を提供している。
• アルゴリズム： アルゴリズムは幾何学的ホライゾンを持つエピソードで動作する。推定された特徴マップに対して後退価値反復（backward value iteration）を実行して、楽観的な価値推定（UCBボーナスを使用）を計算し、貪欲なアクションシーケンスを実行する。
• 最適化： アクション空間は無限であるが、$\max_a K(s, a)$ の最適化は、特徴マップのコンパクトな像（image）上で実行される。実際には、有限の深さ、あるいは最終的に周期的なシーケンスに限定することで近似できる。

3. 主な貢献

1. ATST-MDPの定式化： アクションによってトリガーされる状態観測を伴う環境のための新しいフレームワークであり、標準的なMDPと一般的なPOMDPの間の溝を埋めるものである。
2. 理論的基礎： 拡張状態空間におけるベルマン方程式の導出と、最適ポリシーの存在の証明。
3. 線形表現： 線形MDP仮定の下では、アクションシーケンスの価値関数が有限次元の特徴マップに対して線形であることを示し、効率的な学習を可能にした。
4. アルゴリズムとリグレット界： 楽観的な価値反復アルゴリズムであるATST-LSVI-UCBの提案。著者らは、エピソード学習において $\tilde{O}(\sqrt{d^3 K (1-\gamma)^{-3}})$ のリグレット界を証明しており、これは完全観測の線形MDPにおける既知の最適レートと一致する。
5. サンプル複雑性： データからアクションシーケンスの特徴マップを推定するためのサンプル複雑性の保証を確立し、それが次元 $d$ に対して多項式であり、状態空間のサイズ $|\mathcal{S}|$ に依存しないことを示した。

4. 結果

• 理論的側面： リグレット界は、部分観測性とアクションによる遅延という複雑さが加わっているにもかかわらず、完全観測の線形MDPにおける最先端の性能と一致している。この界は、特徴次元 $d$、エピソード数 $K$、および割引係数の逆数 $(1-\gamma)$ にスケールする。
• 実証的側面： 2つのテーブル環境、RiverSwim（探索重視）と RiverBalance（安定化重視）を用いた実験により、アルゴリズムの有効性が示された。
  • RiverSwim では、疎な観測（低い $\beta$）が、逆に長いオープンループのコミットメント（探索）を促すことで、収束を加速させた。
  • RiverBalance では、頻繁な観測（高い $\beta$）が高い報酬をもたらした。これは、安定性を維持するために状態依存の補正が必要なタスクであったためである。
  • これらの結果は、最適な観測頻度がタスクに依存することを示している。

5. 意義と主張

本論文は、アクションによってトリガーされる状態観測を伴う強化学習の理論的基礎を提供することを主張している。その意義は以下の通りである：

• ギャップの解消： 一般的なPOMDP手法が計算の困難さから苦慮する、特定の（能動的知覚やコストのかかるセンシングといった）実用的に関連性の高いクラスのPOMDPに対処している。
• 計算可能性： データバーストによって誘発される更新構造と線形MDP仮定を活用することで、手に負えない部分観測問題を、扱いやすい線形回帰問題へと変換している。
• 最適性： 完全観測の設定と同等のリグレットレートを達成しており、これは、観測メカニズムが理解され活用されていれば、散発的な観測性の「コスト」を軽減できることを示唆している。
• 報酬フリーの推定： 特徴マップの推定は報酬フリーである。つまり、環境の構造的学習（ダイナミクスと観測確率）を特定の報酬関数から切り離すことができ、柔軟なポリシー適応が可能である。

著者らは、今後の課題として、無限のアクションシーケンス最適化のための効率的な近似スキームの設計や、事前に収集された探索データなしに特徴推定を適応的に洗練させる完全オンラインアルゴリズムの開発に焦点を当てるべきであると述べている。