完全観測可能な非決定論的問題における状態の安全性を決定するアルゴリズム：技術報告書

要旨: 学習されたアクションポリシーは逐次意思決定でますます人気が高まっていますが、安全性の保証が欠如しているという課題があります。最近の研究では、初期状態とアクション結果の非決定性の下でこのようなポリシーの安全性を検証するパイプラインが導入されました。パイプラインの中核には、安全である状態を決定する問題（その状態から安全なポリシーが存在するか）と、欠陥を特定する問題、すなわち安全な状態から安全でない状態へ遷移する状態-アクションの組を見つける問題があります。安全性を決定する最も有効なアルゴリズムである TarjanSafe は、ベンチマーク上で有効ですが、私たちはそれが状態空間に対して指数関数的な最悪ケースの実行時間を持つことを示します。線形時間の代替手段も存在しますが、実務上は遅いです。このギャップを埋める新しいポリシー反復アルゴリズム iPI を提案します。これにより、両者の長所を組み合わせます。すなわち、TarjanSafe の最良ケースの実行時間に匹敵しつつ、最悪ケースは多項式で保証します。実験は我々の理論を裏付け、TarjanSafe に適した問題では iPI が同様の性能を示す一方で、適さない問題では iPI が指数関数的により良くスケールします。