Answer-Set-Programming-based Abstractions for Reinforcement Learning

問題提起
強化学習（RL）は、エージェントが相互作用を通じて方策を学習することを可能にするが、現実的なアプリケーションでは、膨大な状態空間と行動空間に直面することが多く、素朴な学習手法では実行不可能になる。Deep Q-Learningのような近似手法は汎化性能を提供する一方で、膨大な訓練データを必要とし、不安定性を示すことも頻繁にある。Relational Reinforcement Learning (RRL) は、オブジェクトとその関係について推論するために一次述語論理を利用することで、これらの制限に対処し、類似した状態間での汎化を促進する。具体的には、van Otterlo (2004) による CARCASS フレームワーク（Compact Abstraction using Relational Conjunctions for Aggregation of State-action Spaces）は、論理的抽象化を用いてマルコフ決定過程（MDP）をモデル化している。しかし、オリジナルの CARCASS 実装は Prolog と SLDNF 分解に依存しており、それは原理的には宣言的であるものの、効率性のために（ルールの順序付けやカットなどの）手続き的な特徴を必要とすることが多く、非単調推論、最適化、および好みの処理をネイティブにサポートしていない。

手法
著者らは、ASP（Answer-Set Programming）を用いて CARCASS フレームワークを再実装するための一般的な手法を提案している。ASP は、非単調推論、最適化、および制約をサポートする、完全に宣言的な論理ベースの知識表現言語である。

1. ASP による CARCASS のエンコーディング: 著者らは、抽象的な状態および状態・行動ペアを基底項（ground terms）にマッピングするためのラベル付け関数を定義する。彼らは以下の要素からなるモジュール式のエンコーディングを構築する：

   • プログラム ($P_{\hat{s}_i}$): 個々の抽象状態を、その抽象状態を定義するリテラルを本体とするルールとしてエンコードする。
   • プログラム ($P_{\hat{s}_i, \hat{a}_{i,j}}$): 抽象的な状態・行動ペアの被覆関係（covering relation）をエンコードし、aCov 原子を介して具体的な行動を抽象的な行動へと結びつける。
   • 決定リストメカニメント ($P_{\hat{C}}$): 具体的な状態ごとに正確に一つの被覆抽象状態を選択するための選択ルールと、選択が順序付けられたリストに従うこと（最も低いインデックスを優先すること）を保証するための制約を使用する。
   • 「空」の抽象状態 ($\hat{s}_\infty$): 最も高いインデックスを持ち、特定のルールによってカバーされていないすべての状態をカバーするデフォルトのフォールバックを保証する。

2. オンライン学習の統合: 著者らは、このエンコーディングをオンライン Q 学習ループ（アルゴリズム 2）に統合する。与えられた具体的な状態に対して、ASP ソルバは最適なアンサーセットを計算し、被覆する抽象状態と許容される抽象的な行動の集合を決定する。その後、エージェントは選択された抽象的な行動によってカバーされている具体的な行動を選択し、抽象的な状態・行動ペアの Q 値を更新する。

3. 背景知識: このフレームワークは、複雑な特性（例：経路探索、タワーの完全性）を、事前に計算したり手続き的に実装したりすることなく、抽象化プロセスの中で直接推論するために、背景知識 ($P_B$) を含めることを可能にする。

主要な貢献

1. 一般的なエンコーディング手法: 本論文は、CARCASS の抽象化を ASP でエンコードする体系的な手法を導入し、完全に宣言的な言語がいかにして関係的な状態・行動の抽象化を実現できるかを示している。
2. オンライン学習への適応: 著者らは、動的な抽象状態および行動の選択を処理しながら、ASP ベースの CARCASS 抽象化をオンライン Q 学習の設定内で利用する方法を示している。
3. 実証的評価: 実装は、2 つの異なるドメインで評価される：
   • Blocks World: $n$ 個のブロックを用いたスタッキング・タスクであり、抽象化によって状態・行動空間を $n$ に依存しない一定のサイズに削減する。
   • MiniGrid: グリッドワールドのナビゲーション・タスク（例：Door Key, Multi Room）のスイートであり、背景知識を用いて部屋のレイアウトや最短経路を推論し、次のノードに基づく抽象状態を構築する。

結果
実証的評価では、20 ブロック・ワールドと 3 つの MiniGrid 環境において、抽象 Q 学習と具体的な Q 学習を比較している。

• 安定性: 抽象 Q 学習は、初期学習の後、中央値の報酬と四分位範囲が高い水準で維持される一貫した安定性を示したが、具体的な Q 学習は、複雑な環境において顕著な変動や収束の失敗を示した。
• 質: 抽象 Q 学習は高い成功率（例：MiniGrid タスクの最後の 500 エピソードでほぼ 100%）を達成した。これは、同じ期間内に正の報酬を得ることに失敗することが多かった具体的な Q 学習を大幅に上回る結果である。
• サンプル効率: 抽象的なアプローチは、具体的なアプローチと比較して、高品質な方策を学習するために有意に少ないエピソードを必要とした。例えば、20 ブロック・ワールドにおいて、抽象学習はエピソード 376 までに正の中央値報酬に達したが、具体的な学習はベースラインの負の報酬にとどまった。
• モデリングの違い: MiniGrid のケーススタディにおいて、ASP によるエンコーディングは経路探索や制約のコンパクトで宣言的な仕様化を可能にしたが、同等の Prolog 実装では明示的なアルゴリズム探索（幅優先探索）が必要であった。これは、問題の仕様と制御ロジックを分離するという ASP の利点を際立たせている。

意義と主張
本論文は、特にドメイン知識が利用可能な場合に、ASP で実装された CARCASS が RL における抽象化を構築するための有望なアプローチであることを結論付けている。著者らは、ASP ベースの抽象化が、以下の機能をサポートすることで、Prolog ベースの CARCASS に対する柔軟な代替案を提供すると主張している：

• 汎化: 関係的な表現を通じて。
• 行動の制限: 宣言的な制約を通じて。
• 問題の分解: 複雑な推論パターン（経路探索やタワー分析など）をルール内に直接エンコードすることによる。
• 高度な推論: 非単調推論、最適化、および不完全な知識の下での推論を含む。

著者らは、学習された方策は許容可能な品質であり、より少ないサンプルで学習されているものの、一般に最適方策への収束を保証するものではないこと、また、抽象化自体が（Blocks World のケースで見られたように、抽象化が最適性をトレードオフとして扱い、NP 困難なプランニング問題における最適性を保持しない可能性があることから）最適方策を保持する保証はないことを控えめに述べている。本研究は、精緻化に耐えうる（elaboration-tolerant）方策学習をサポートする、知識駆動型のリレーショナル RL への一歩として位置づけられている。