Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

人工知能の世界において、意思決定はしばしば、ルールが完全に既知である盤面の上で行われる運任せのゲームとして扱われます。ロボットが迷路をナビゲートする場面を想像してみてください。もしエンジニアが、床がどれほど滑りやすいか、そしてロボットの車輪がどのように回転するかを正確に知っていれば、出口への完璧な経路を計算することができます。これは、多くの意思決定システムの標準的なモデルです。しかし、現実世界はこれほど精密であることは稀です。センサーは故障し、材料は摩耗し、データにはノイズが含まれます。つまり、ロボットが滑ったり車が逸れたりする正確な確率は真には知る由がなく、可能性の範囲内で推定されるものに過ぎないのです。これらの不確実性が加わると、問題ははるかに困難になります。地形の挙動が確信できない中で、どうやって安全な経路を計画すればよいのでしょうか。さらに、自動運転や医療用ロボットのような安全性が極めて重要な分野では、単に目的地に素早く到達することではなく、システムが危険な状態に陥ったり、特定の論理的なイベントの連鎖を永遠に繰り返したりしないことを保証することが目標となります。

インド工科大学ボンベイ校と南洋理工大学の研究者たちは、この不確実性と厳格な論理的安全性が交差する困難な課題に取り組みました。彼らは、エージェントが世界を部分的にしか見ることができず、かつ移動のルールが固定された数値ではなく、可能性のある値の集合に属しているという種類の問題に焦点を当てました。研究チームは、これらの複雑で不確実な意思決定問題を解くことが、隠された情報を持つ2人の対戦プレイヤーが関わる、別のよく研究されているタイプのゲームを解くことと数学的に同一であることを証明しました。この双方向のつながりを確立することで、彼らは数十年にわたる既存のゲーム理論の知識を借りて、これらの不確実なロボット問題の計算上の難易度を即座に判断することができました。彼らの研究は、これらのシナリオにおいて安全性を保証することが具体的にどの程度困難であるかを明らかにしており、ある種の論理的目標については既知の手法で解決可能である一方で、他の目標については、いかなるアルゴリズムでも合理的な時間内に解くことができないほど複雑であることを示しています。

彼らの発見の核心は、2つの異なる数学的世界を橋渡しすることにあります。一方には、エージェント（自動運転車など）が、自分の正確な位置を知らず、かつ新しい状態へ遷移する正確な確率も知らない状態で行動を選択しなければならない状況を記述するために用いられる「ロバスト部分観測マルコフ決定過程」があります。単一の確率の代わりに、システムは起こり得る確率の「雲」の中で動作します。もう一方には、成功しようとするプレイヤーとそれを阻止しようとするプレイヤーが、情報の断片しか見えない状態で交互に動きを行う「部分観測確率ゲーム」があります。長年、研究者たちは、単に報酬を最大化することが目標であれば、これら2つのモデルは互いに変換可能であることを知っていました。しかし、目標が「決して歩行者に衝突しない」や「最終的に病院に到着し、そこに永遠に留まる」といった厳格な論理的ルールへと移行すると、そのつながりは断絶していました。今回の研究は、これらの複雑な論理的ルールが存在する場合でも、2つのモデルは依然として完全に等価であることを証明しています。

これを実証するために、研究者たちは両方向に機能する精密な翻訳メカニズムを構築しました。まず、不確実な確率を伴うロバストな意思決定問題を、2人対戦ゲームに変換する方法を示しました。この新しいゲームでは、エージェントが一方のプレイヤーとなり、世界の不確実性がもう一方の対戦プレイヤーとなります。この第2のプレイヤーはランダムに行動するのではなく、エージェントを打ち負かすために、利用可能な選択肢の中から最悪のシナリオを積極的に選択します。研究者たちは、もしエージェントがこの巧妙な相手に対して勝利できるならば、元の不確実な世界においても成功できることを証明しました。さらに驚くべきことに、彼らは逆方向の翻訳も達成しました。いかなる隠された情報を持つ2人対戦ゲームも、ロバストな意思決定問題へと変換できることを示したのです。この逆のステップは技術的に困難でした。なぜなら、ゲームにおいては相手がエージェントの動きを見てから行動するのに対し、意思決定問題では環境が即座にその振る舞いを確定させるからです。チームは、ゲームの構造の中に短く不可視の「一時停止」を挿入することで、この問題を解決し、環境に元の問題と同じ情報を与えるようにしました。この双方向の架け橋により、ある種の計算科学的な結果が、自動的にもう一方のタイプの問題の難易度にも適用されることになります。

この等価性の意味するところは、自動推論の限界を理解する上で即時的かつ深刻です。この架け橋を用いることで、研究者たちは様々な種類の論理的目標に対するこれらの問題の計算複雑性を正確にマッピングすることができました。彼らは、ターゲットへの到達や危険地帯の回避といった単純な目標については、問題は解決可能であるものの、システムの規模に応じて指数関数的に増大する膨大な計算力を必要とすることを見出しました。しかし、研究はまた、明確な限界も特定しました。特定の複雑な論理的目標、具体的には「常に」と「最終的に」の条件が混在する二面的な不確実性環境においては、問題は「決定不能（undecidable）」となります。これは、いかに強力なコンピュータプログラムであっても、あらゆるシナリオに対して答えを保証することは決してできないことを意味します。また、研究者たちは、エージェントのみが盲目であり環境はすべてを見ているという「片側不確実性」の場合の難易度についても明確にし、これらのケースは完全な盲目状態のシナリオよりも一般的に解決しやすいことを示しました。

この研究は、不確実性下での安全な自律システムを設計する際に、計算的に何が可能であるかについての完全な景観を提供しています。これは、隠された情報、敵対的な不確実性、そして複雑な論理的ルールが組み合わさったとき、解決策を見つけることが不可能になる根本的な境界が存在することを裏付けています。この研究は、あらゆるケースを解決するための新しいアルゴリズムを提示するものではなく、むしろ地形の決定的な地図を提供し、エンジニアに対して、どの問題が解決可能であり、どの問題に全く異なるアプローチが必要であるかを正確に伝えています。これら2つの数学的枠組みが同一であることを証明することで、研究者たちは既存の膨大なツールと理論のライブラリを解禁し、この分野が直面する課題を明確に理解した上で前進することを可能にしたのです。