PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

あなたは、二人のライバル関係にあるビデオゲームのキャラクターに、新しい謎めいたボードゲームの遊び方を教えようとしていると想像してください。片方のキャラクター、名前を「マックス」としましょう。彼はできるだけ早く宝箱に到達したいと考えています。もう一方は「ミン」で、マックスを阻止したいと考えています。例えば、彼を罠に誘い込んだり、永遠に堂々巡りをさせたりすることです。これは単なる運任せのゲームではありません。あらゆる動きが確率を変化させる、知略の戦いです。コンピュータサイエンスの世界では、これは「ターン制確率ゲーム（Turn-Based Stochastic Game）」と呼ばれます。これは、二人の対戦相手が意思決定のために順番に手番を行いますが、その決定の結果にはダイスの目が絡む、という状況を説明する格好いい言い方です。

通常、コンピュータにゲームを教えるとき、私たちはコンピュータがすべてを見通せると想定します。ルール、盤面、そして相手が何を考えているかさえもです。しかし、現実の世界はもっと混沌としています。多くの場合、コンピュータはルールを全く知りません。プレイしながら、間違いを犯し、何が起こるかを見ることで、ルールを学んでいかなければならないのです。これは「強化学習（Reinforcement Learning）」と呼ばれます。目標は、「おそらく近似的に正しい（Probably Approximately Correct: PAC）」戦略を見つけることです。これは少し難しい言葉ですが、簡単に言えば、「合理的な量の練習をした後、ほぼ確実に、最善の戦略に限りなく近い戦略を見つけ出すような学習手法を設計できるか？」という意味です。

厄介なのは、特定の種類の目標――例えば「いつかは宝に到達する」といった目標――の場合、ゲームが永遠に続く可能性があり、プレイヤーが真に敵対的であるならば、学習は数学的に不可能であるということです。もし相手があなたを欺こうとしているなら、相手はあなたが学習するのを助けているふりをして、後で罠を露わにするかもしれません。この論文は、この問題の非常に困難なバージョンに取り組んでいます。つまり、「二人のプレイヤーが互いに会話できず、互いの動きを見ることができず、ルールさえ知らない状態で、このゲームを上手くプレイすることを学べるか？」という問題です。

---

ダイスを使ったかくれんぼの大ゲーム

この論文において、著者たち（アリ・アサディ、クリシュネンドゥ・チャタジー、パボル・ケビス）は、パラドックスのように聞こえる課題に挑んでいます。彼らは、マックスがターゲットに到達しようとし、ミンがそれを阻止しようとするゲームを、二人のライバルプレイヤーに教えようとしています。ただし、条件があります。彼らは暗闇の中でプレイしているのです。彼らは盤面のルールを知らず、メモを共有することもできず、今この瞬間に相手が何をしているのかさえ分かりません。

これまでの多くの試みでは、研究者たちは二つの大きな、非現実的な仮定を置いていました。第一に、プレイヤーは学んだことをすべて書き留めることができる「公開ノート」を共有できると仮定していました。第二に、プレイヤーは全員同じ学習アルゴリズムを使用している、例えば二人の学生が同じ教科書から写しているような状態であると仮定していました。論文の著者は、「待ってください、それは現実の世界の仕組みではありません」と言います。実際には、プレイヤーはしばしばプライベートな情報を持っており、それぞれ異なる方法で学習するものです。彼らはこう問いかけました。「もし全員が自分の秘密を守り、自分自身の脳を使って学習する場合でも、上手くプレイすることを学べるのだろうか？」

「待ち時間の問題」

なぜこれがこれほど難しいのかを理解するために、宝箱が100万年に一度しか開かない扉の向こうに隠されているゲームを想像してみてください。もしプレイヤーがただ推測しているだけなら、彼らは永遠に待ち続けることになるかもしれません。数学の世界では、これは「無限ホライゾン（infinite horizon）」問題と呼ばれます。もしゲームが永遠に続く可能性があり、相手が終了を遅らせるために賢明であれば、自分が正しいことを学んでいるのか、それとも決して起こらないかもしれない奇跡を待ち続けているだけなのか、確信を持つことはできません。

著者たちは、学習が可能であるためには、セーフティネットが必要であることに気づきました。彼らは「期待条件付き距離（Expected Conditional Distance: ECD）」という概念を導入しました。これは、ゲームにおける「忍耐メーター」のようなものだと考えてください。これは、「もしターゲットに到達可能であるならば、平均してどれくらいの時間でそこに到達するか？」を測定します。もしECDが小さければ、それはゲームが永遠に引き延ばされることなく、宝は通常比較的早く見つかることを意味します。もしECDが膨大であれば、それはゲームが非常に長い待ち時間のループに陥る可能性があることを意味します。

論文は、もしこの「忍耐メーター」が限定されている（つまり、ゲームが永遠に続くことがない）ならば、暗闇の中でも学習は「可能である」ことを証明しています。彼らは、この数値を知っていれば、無限のゲームを有限のゲームへと効果的に変えられることを示しました。つまり、その時点までに宝が見つかっているはずだと判断して、一定の数のステップでゲームを打ち切ることができるのです。重要なのは、このような仮定（ECDや、従来の文献に見られる他の同様の制約）がない場合、この種のゲームにおいて学習は一般的に不可能であるということです。論文は、ECDが唯一の方法であると主張しているわけではありませんが、それがこの新しい設定において問題を解くための具体的な鍵となったのです。

秘伝のレシピ：段階的な学習

では、彼らは実際にどのようにプレイヤーを教えているのでしょうか？著者たちは、洞窟の地図を作る探検家チームのように機能する、巧妙な一対の学習アルゴリズム（マックス用とミン用）を設計しました。

1. マップの拡張: 単に「状態A」や「状態B」と考えるのではなく、プレイヤーは「時間」が第3の次元となっている3Dマップを想像します。彼らはゲームを「状態とステップ」のペアに分解します。これは、「ステップ1ではキッチンにいて、ステップ2では廊下にいる」と言うようなものです。これにより、彼らは終わりから逆算して計画を立てることができます。
2. 「ベストアーム」のトリック: マップ上のあらゆる地点において、プレイヤーは行動を選択しなければなりません。彼らは「バンディット学習（Bandit Learning）」と呼ばれる分野のテクニックを使用します（ギャンブラーが最高の当たりスロットを探そうとしている様子を想像してください）。彼らはさまざまな動きを試し、どれが最も効果的であるかを確認し、それに固執します。ただし、単に運が良かっただけではないことを確認するために、高い信頼度を持ってこれを行います。
3. 探索ループ: プレイヤーは、マップの「未探索」の部分を探索することから始めます。彼らはこれらの未知の場所を、見つけるべき新しい「宝」として扱います。特定の場所における最善の動きを理解すると、その場所を「探索済み」としてマークし、次に進みます。これを繰り返しながら、ステップバイステップで戦略を構築していき、最終的にゲーム全体の計画を立てます。
4. プライベートな合意: ここに魔法があります。彼らは決して会話しませんが、両者は似たようなリズムに従います。彼らは、双方が十分に探索したと感じるまでプレイを続けます。どちらのプレイヤーも、自分自身のプライベートな視点において、これ以上「未探索」の場所が見つからない状態になったとき、両者はゲームシミュレーターに対して、「終了です！これが私たちの戦略です」と合図を送ります。

結果：新しい形の学習

この論文の主な発見は、力強い「イエス」です。彼らは、この方法を用いれば、プレイヤーは（ごくわずかな誤差範囲内で）ほぼ完璧な戦略を、高い確率で学習できることを証明しました。決定的なのは、彼らがゲームをプレイする必要のある回数（サンプル複雑性）が、管理可能な多項式的な形で増えることです。これは、ゲームが大きくなっても、学習時間が無限に爆発することなく、妥当な範囲に収まることを意味します。

これは大きな成果です。なぜなら、これほど複雑な敵対的ゲームを、分散型（共有された脳を持たない）かつプライベート（共有されたメモを持たない）な設定で学習できることを示したのは、初めてだからです。以前は、効果的に学習するためには情報を共有する必要があると考えられていました。著者たちは、ECDという「忍耐メーター」と、巧妙な逆方向の計画戦略を用いることで、暗闇の中でも学習できることを示しました。

また、彼らは、ECDのような追加の仮定なしにこの種のゲームを学習することは、一般的には不可能であることも明確にしました。もしゲームがターゲットに到達するまでの時間に制限なく、永遠に続く可能性があるならば、いかなる学習アルゴリズムも成功を保証することはできません。論文は非常に明確です。数学を成立させるためには、その時間の境界（バウンド）が必要なのです。

なぜこれが重要なのか？

「理論上のゲームでダイスを振っている二人のプレイヤーのことに、誰が関心を持つのか？」と思うかもしれません。しかし、これは単なるボードゲームの話ではありません。この種の数学は、自動運転車、ネットワークセキュリティ、あるいは自動取引などのための安全なAIを構築するためのバックボーンとなっています。現実世界のシナリオでは、異なるシステム（あるいはハッカー）が、互いが何をしているか完全には知らないまま、絶えず相互作用しています。

この論文は、私たちに新しいツールキットを与えてくれます。たとえすべてのAIエージェントに秘密を共有することを強制できず、たとえ彼らが互いを出し抜こうとしていたとしても、「悪いこと」が無限の時間経過後に起こらないということが分かっていれば、彼らを賢く、安全に学習させることができるのです。これは、中央集権的なボスがいなくても、混沌とした不確実な世界をナビゲートできるAIを構築するための、一歩となります。

要するに、著者たちは、ライバルを相手に暗闇の中でゲームを学ぶという、不可能に思える問題に取り組み、「忍 Patience メーター」と巧みな逆方向の思考を用いることで、一歩ずつ明かりを灯す方法を見出したのです。