co-safe LTL計画のための厳密なモデルフリーポリシー反復法

本論文は、有限Markov決定過程(MDP)におけるco-safe linear temporal logic (sc-LTL)目的に対するモデルフリー強化学習を研究している。sc-LTL目的は標準的なproduct constructionにより最大到達可能性目的に帰着できる。この問題に対して、直接的なサンプルベースのbootstrap法(TDやQ-learningなど)は、Bellman方程式の解の非縮小性と非一意性のため最適政策に収束しない可能性がある。そこで、割引サロゲートを用いて非一意性を解消するclamp setを特定し、その後、非割引の政策評価と貪欲な政策改善を適用して最適解を求める新しい2段階のモデルフリー強化学習法を開発した。

先行研究では、sc-LTL目的に対するモデルフリー法は、Bellman方程式の非縮小性や解の非一意性により最適政策への収束が保証されない問題があった。本手法は、割引サロゲートを導入してclamp setを特定することで非一意性を解決し、非割引の政策評価と政策改善を組み合わせることで、最適政策への有限終了を理論的に保証する点が新しい。

手法の肝は2段階のアルゴリズムである。第1段階では、割引サロゲートを用いてBellman方程式の解の非一意性を解消するclamp setを特定する。第2段階では、そのclamp setに基づいて非割引の政策評価を行い、貪欲な政策改善を繰り返す。政策評価のalmost-sure収束と政策反復アルゴリズムの有限終了を理論的に証明している。

理論的結果は、確率的グリッドワールド上の数値実験により検証された。具体的には、提案アルゴリズムが最適政策に収束すること、および政策反復が有限回で終了することが実験的に確認された。

要旨からは、提案手法の計算複雑性や、より複雑なLTL目的への拡張、連続状態空間への適用などに関する議論は不明である。また、clamp setの特定が実際にどの程度のサンプル効率に影響するかについての詳細な分析も要旨には含まれていない。

要旨で参照されている関連研究として、co-safe LTL planningにおけるモデルフリー強化学習の既存手法や、Bellman方程式の非一意性を扱う研究が挙げられる。具体的には、TD学習やQ-learningの収束性に関する研究、およびsc-LTL目的のためのproduct constructionを用いた計画手法が関連する。