技術要約：堅牢なマルコフ決定過程のための適応型方策ポートフォリオ

問題定義

堅牢なマルコフ決定過程（RMDP）は、不確実性集合（不確実性集合 $U$）内のあらゆる妥当な遷移関数に対して方策を最適化することで、不確実性下での逐次的な意思決定に対処する。標準的なアプローチは、最悪のケースの値を最大化する単一の方策を求めるものである。しかし、これは過度に保守的な挙動を招く可能性がある。なぜなら、たとえそれらの環境が起こりにくい、あるいは観測によってすぐに排除されるものであっても、方策が $U$ 内の最も困難な環境に支配されてしまうからである。

ロバスト・リグレット（Robust Regret）の最小化は代替案となるが、これは特定の実現値に対する最適方策との差分を最小化するものであり、それでもなお、あらゆる可能な環境に対して単一の方策をコミットしてしまう。これは、どのモデルが環境を支配しているかを特定するためのオンラインの証拠を活用できていない。

本論文では、**適応型方策ポートフォリオ（Adaptive Policy Portfolios）**を提案する。これは、オフラインで合成された有限個のメモリレスなランダム化方策の集合と、軽量なオンライン・セレクターを組み合わせたものである。このポートフォリオの目的は、ロバスト・リグレットを最小化することである。ここでロバスト・リグレットとは、真の環境が既知であった場合に最適であったであろう方策に対する、最悪のケースにおける損失と定義される。目標は、事前検証された有限の方策セットに対してオンライン選択が行われるという、制御された形態の適応を実現することである。

手法

理論的枠組み

著者らは、2つの核心的なサブ問題の計算複雑性を分析している：

1. 認証（Certification）： 特定のポートフォリオ $\Pi$ が与えられたとき、そのロバスト・リグレットが閾値 $t$ を下回るかどうかを判定する。
2. 合成（Synthesis）： ロバスト・リグレットを最小化する、サイズが最大 $k$ のポートフォリオを構築する。

この分析では、実数の理論（Theory of the Reals）（$\exists\mathbb{R}, \forall\mathbb{R}, \exists\forall\mathbb{R}$）の階層構造と、平方根和（SQRS）問題を利用している。論文では、一般的な（非長方形の）不確実性と、$(s, a)$-長方形の不確実性（ある状態・行動ペアにおける不確実性が他のペアと独立している場合）を区別している。

主要な理論的メカニズムには以下が含まれる：

• リフト構成（Lift Construction）： 「ボーナス」アクションを用いることで、方策の比較問題を、あらゆる実現において参照方策が最適となるようなリグレット認証問題へと変換する手法。
• 制限変換（Restriction Transformation）： 許可されていないアクションを「破滅的」（高い負の報酬をもたらすシンクへ導く）にすることで、合成された方策を特定の行動セットに制約する方法。これにより、最小化が所望のクラス内に留まることを保証する。
• 困難性の還元（Hardness Reductions）： 本論文は、多項式非正性、ブール充足可能性（UNSAT/SAT）、および平方根和をエンコードするRMDPを構築し、下界を確立している。

実践的な構築

理論的な困難さにもかかわらず、著者らは以下のオフライン構築パイプラインを提案している：

1. 離散化（Discretization）： 不確実性のパラメータ空間をセルに分割する。
2. 候補生成（Candidate Generation）： 各セルの中心点に対して最適方策を計算する。
3. 評価（Evaluation）： 各候補をすべてのセルに対してロバストに評価し、「リグレット・プロファイル」（パラメータ空間全体にわたるリグレットのベクトル）を生成する。
4. クラスタリング（Clustering）： これらのプロファイルに対してK-meansクラスタリングを適用し、空間を最もよくカバーする $k$ 個の方策のサブセットを選択する。
5. オンライン展開（Online Deployment）： 実行時には、観測が蓄積するにつれて、ポートフォリオのメンバーをバンディットの腕（arm）として扱い、**上側信頼限界（UCB）**アルゴリズムを使用して、最適なポートフォリオメンバーを選択する。

主要な貢献

1. 適応型方策ポートフォリオの導入： 本論文は、適応型方策ポートフォリオを、単一のロバスト方策へのコミットメントと、フル・ビリーフ状態プランニング（例：ベイズ適応型MDP）との間の、有限かつ検証可能な形態の適応として定式化した。
2. 複雑性の分類：
   • 認証： 非巡回的な $(s, a)$-長方形RMDPにおける決定論的ポートフォリオに対して、認証は $\forall\mathbb{R}$-完全 であることが証明された。これは、長方形性が通常RMDPを単純化するにもかかわらず、ポートフォリオメンバーによる点ごとの最大値操作が、必要な量化子の交互作用を再導入するためである。
   • 合成： 一般的な有理多角形不確実性の下で、サイズ $k$ 以下のポートフォリオを構築する問題は $\exists\forall\mathbb{R}$-完全 である。
3. 困難性の源泉の特定： 論文は、計算の困難性の構造的な原因を特定している：
   • ブール困難性（Boolean Hardness）： 両方の方策に共有される不確実な遷移から生じる。
   • 平方根和の困難性（Square-Root Sum Hardness）： 共有される不確実な選択がサイクル上に存在する場合に生じる。
   • 代数的困難性（Algebraic Hardness）： 方策空間自体の最適化から生じる。
4. 経験的検証： プロトタイプ実装により、離散化とクラスタリングを用いて構築されたポートフォリオが、単一の方策と比較して経験的ロバスト・リグレットを大幅に減少させることが示された。リグレットはポートフォリオのサイズが増えるにつれて急激に減少する。

結果

理論的な結果

複雑性のランドスケープは論文の表1にまとめられている：

• 特定の方策の認証は、一般には $\forall\mathbb{R}$-完全であり、非巡回的な長方形ケースであっても coNP-hard（および coSQRS-hard）である。
• 特定の方策ポートフォリオの認証は、非巡回的な長方形RMDPにおける決定論的ポートフォリオに対してさえ、$\forall\mathbb{R}$-完全である。
• 単一のランダム化方策の合成は、一般には $\forall\mathbb{R}$-hardであり、長方形ケースでは NP/coNP/SQRS-hard である。
• 有界なポートフォリオの合成は、一般には $\exists\forall\mathbb{R}$-完全である。長方形の不確実性の下では、$k=1$ の場合でも困難である。

これらの結果は、標準的な計算複雑性の仮定の下では、効率的な汎用アルゴリズム（厳密な合成や認証のためのもの）の存在は期待できないことを示唆している。

経験的な結果

著者らは、データセンターの気候制御問題と、3Dグリッド内のUAV制御問題の2つのベンチマークで手法を評価した。

• リグレットの減少： 経験的ロバスト・リグレットは、ポートフォリオサイズ $K$ が増加するにつれて大幅に減少した。例えば、UAV-Largeベンチマークでは、リグレットは $K=1$ のときの 0.126 から $K=10$ のときの 0.003 まで低下した。
• オンライン識別： UCBを使用することで、システムは固定されているが未知の環境において、最適なポートフォリオメンバーを正常に特定した。$K$ が大きくなるにつれて（ニアタイが発生するため）「正確な」ベストメンバーを特定できる割合は減少したが、推奨された腕のリグレット（ベストメンバーに対するもの）は最小限に抑えられていた。これは、たとえ正確なベストメンバーが特定できなくても、選択されたメンバーがほぼ同等に優れていることを示している。

意義と主張

本論文は、適応型方策ポートフォリオが、単一のロバスト方策の過度な保守性と、フル・ビリーフ状態プランニング（例：ベイズ適応型MDP）の困難さとの間の、有限かつ検証可能な中間領域を提供すると主張している。

著者らは、理論的な複雑性の境界が高い（厳密なアルゴリズムの効率的な構築を否定する）一方で、実践的なオフライン構築が経験的に大幅に低いロバスト・リグレットをもたらすことを強調している。本研究は、なぜこれらの問題が困難なのか（実数の理論やSQRSとの関連付けを通じて）を理解するための厳密な理論的基礎を提供し、単純な離散化とクラスタリングのアプローチが実用において効果的であることを示している。

論文は、理論的な困難さと実用的な有用性の間のギャップ、特に長方形の不確実性下での有界合成や、単一方策の最小リグレットの正確な複雑性が、依然として開かれた領域であることを結論づけている。提案された手法は、オンラインでのビリーフ更新の計算オーバーヘッドなしに、実行時の特殊化を可能にする。