不完全情報ゲームの均衡学習

2025年度人工知能学会全国大会 (JSAI2025) の企画セッション「学習理論におけるゲーム理論のフロンティア」での発表資料です．
https://www.ai-gakkai.or.jp/jsai2025/ks/#ks-12

Transcript

1. 不完全情報ゲームの均衡学習 株式会社サイバーエージェント AI事業本部 AI Lab 阿部拳之 JSAI 2025 企画セッション 「学習理論におけるゲーム理論のフロンティア」 (2025/05/28)
2. 自己紹介 ▪ 名前 – 阿部 拳之（あべ けんし） – @bakanaouji（ばかなおうじ） ▪ 経歴 – 東京工業大学総合理工学研究科知能システム科学専攻（〜2017年） ▪ 強化学習×進化計算をメインに研究 – 株式会社ハル研究所（2017年〜2018年） ▪ ゲームプログラマー – 株式会社サイバーエージェント AI事業本部 AILab（2018年〜） ▪ 強化学習チーム・リサーチャー兼チームリーダー ▪ Learning in Games・凸最適化について研究 1
3. 今回の発表 ▪ ここ数年で，ポーカーやstrategoなどの大規模な不完全情報ゲームにおいて人間 を超える（あるいは匹敵する）AIが作られています ▪ そのようなAIを学習するアルゴリズムには様々なテクニックが用いられていま すが，根底にある理論的背景は実は共通しています ▪ そこで，本発表では不完全情報ゲームの戦略学習における基礎的・理論的な背 景を中心に解説します 2
4. 展開型ゲームの導入 3
5. 不完全情報ゲーム ▪ 各プレイヤがゲーム内の情報を完全に観測できない状況 で意思決定を行う多人数ゲーム ▪ 例 – ポーカー – ガイスター – 麻雀 4
6. 不完全情報ゲームにおけるAIの成功例 ▪ [Brown and Sandholm, 2018]：二人プレイヤ のポーカーAI Libratusを提案 ▪ [Brown and Sandholm, 2019]：六人プレイヤ のポーカーAI Pluribus ▪ [Perolat et al., 2022]：Strategoというボード ゲームのための学習アルゴリズムDeepNash を提案 ▪ [Bakhtin et al., 2023]：No-press Diplomacyと いう戦略ゲームを学習 ▪ アルゴリズムは多岐にわたれど，理論的背 景は同じ 5
7. 𝑁人展開型ゲーム ▪ フォーマルに不完全情報ゲームを記述 ▪ プレイヤーの集合： 𝑁 ∪ 𝑐 – プレイヤー𝑐：ランダム性を操作するダ ミープレイヤー（チャンスプレイヤー） ▪ 実現しうる履歴の集合：𝐻 – 各履歴ℎ ∈ 𝐻はプレイヤーの行動の列 ▪ 終端履歴の集合：𝑍 ⊆ 𝐻 ▪ 情報集合𝑥： – 各プレイヤが区別できない履歴の集合 – つまり，プレイヤ𝑖は𝑥内の履歴ℎ, ℎ′ ∈ 𝑥 を区別することができない 6
8. 𝑁人展開型ゲーム ▪ プレイヤー関数：𝑃 ℎ = 𝑃 𝑥 – 履歴ℎにおいて行動を取るプレイヤー ▪ 行動関数：𝐴 ℎ = 𝐴 𝑥 – 履歴ℎにおいて取れる行動の集合 ▪ 利得関数：𝑢𝑖 (𝑧) – 終端履歴𝑧においてプレイヤー𝑖が受け 取る利得 ▪ 特に𝑁 = 2かつ𝑢1 𝑧 = −𝑢2 𝑧 であるような ゲームを二人零和展開型ゲームと呼ぶ 7
9. 戦略と期待利得 ▪ プレイヤー𝑖の戦略：𝜋𝑖 𝑎 𝑥 – プレイヤー𝑖が情報集合𝑥において行動𝑎 ∈ 𝐴 𝑥 を取る確率 ▪ 戦略の組𝜋にしたがったときにプレイヤー𝑖が得られる利得の期待値 𝑣𝑖 𝜋 ≔ ෍ 𝑧∈𝑍 𝜌𝜋 𝑧 𝑢𝑖 𝑧 – 𝜌𝜋 ℎ = 𝜋𝑃 ℎ1 𝑎1 ℎ1 × ⋯ × 𝜋𝑃 ℎ𝐿 𝑎𝐿 ℎ𝐿 ：戦略の組𝜋にしたがったとき に履歴ℎに到達する確率 8
10. ナッシュ均衡 ▪ 各プレイヤが自身の利得を最大化できているような戦略の組 ∀𝑖, 𝜋∗ ∈ arg max 𝜋𝑖 𝑣𝑖 (𝜋𝑖 , 𝜋𝑖 ∗) – 直感的には，それぞれのプレイヤが自分だけ戦略を変えることのメリット がない状況 ▪ 展開型ゲーム，特に二人零和展開型ゲームでは，ナッシュ均衡を最適解として 求めることが１つの大きな目的 ※ 以降では，議論を容易にするため二人零和展開型ゲームを考えます 9
11. NashConv ▪ ナッシュ均衡との近さを図るために用いられる指標 NashConv 𝜋 ≔ max 𝜋1 ′ 𝑣1 𝜋1 ′ , 𝜋2 − 𝑣1 𝜋 + max 𝜋2 ′ 𝑣2 𝜋1 , 𝜋2 ′ − 𝑣2 𝜋 – 各プレイヤーが現在の戦略から逸脱することで得られる利得のゲインを足 したもの ▪ 定義から任意の戦略の組𝜋に対してNashConv 𝜋 ≥ 0であり，𝜋がナッシュ均衡 であるときに限りNashConv 𝜋 = 0を達成 10
12. ナッシュ均衡の計算 11 ▪ 一般に，（二人零和であっても）展開型ゲームのナッシュ均衡を厳密に計算す ることは困難 – 展開型ゲームを標準型ゲームに変換することで線形計画法で一応解ける min 𝑥∈Δ𝑚 max 𝑦∈Δ𝑛 𝑥⊤𝐴𝑦 – しかし，ゲーム木の情報集合の数に対して次元数𝑚, 𝑛が指数関数的に増加 ▪ よって，ナッシュ均衡を効率良く近似するアルゴリズムの研究が盛んに行われ ている
13. 均衡学習に必要な仮定 と戦略表現 12
14. 完全記憶（perfect recall） ▪ 展開型ゲームの均衡学習においてしばしば置かれる仮定 ▪ 各プレイヤーが過去に観測した情報集合と自身が取った行動を忘れないと仮定 – ざっくりいうと，どういう経路を辿って今のゲーム状況になったのかを覚 えている 13
15. 完全記憶による利点 ▪ 情報集合𝑥への到達確率を𝜌𝜋 𝑥 とする：𝜌𝜋 𝑥 = σ ℎ∈𝑥 𝜌𝜋 ℎ ▪ （利点①）完全記憶のもとでは， 𝜌𝜋 𝑥 はプレイヤーごとに分解して書ける： 𝜌𝜋 𝑥 = 𝜌𝑖 𝜋 ℎ ෍ ℎ∈𝑥 𝜌−𝑖 𝜋 ℎ = 𝜌𝑖 𝜋 𝑥 ෍ ℎ∈𝑥 𝜌−𝑖 𝜋 ℎ ▪ （利点②） プレイヤー𝑖がある情報集合𝑥において行動𝑎を取り，その次に情報 集合𝑥′で行動を行う場合，𝑥, 𝑎, 𝑥′に関して以下の関係が成り立つ： 𝜌𝑖 𝜋 𝑥′ = 𝜌𝑖 𝜋 𝑥 𝜋 𝑎 𝑥 14 ≔ 𝜌−𝑖 𝜋 𝑥
16. 戦略表現 ▪ Behavioral-form戦略 – 戦略を情報集合𝑥ごとの条件付き分布で直接表現：𝜋𝑖 𝑎 𝑥 ▪ Sequence-form戦略 – 戦略を情報集合𝑥への到達確率𝜌𝑖 𝑥, 𝑎 を用いて表現：𝜋𝑖 𝑎 𝑥 ≔ 𝜌𝑖 𝑥,𝑎 σ𝑏 𝜌𝑖 𝑥,𝑏 ▪ 𝜋𝑖 𝑎 𝑥 を最適化変数だと考えるか，𝜌𝑖 𝑥, 𝑎 を最適化変数だと考えるかの違い 15
17. それぞれのメリット・デメリット ▪ Behavioral-form – 直感的かつ実装が行いやすい（強化学習の方策とのアナロジーもある） – ニューラルネットとの相性が良く大規模ゲームの学習への適正◎ – 学習アルゴリズムの収束性の理論解析は複雑になりがち ▪ Sequence-form – 均衡学習問題を単純なbilinearゲームとして書くことができる min 𝑥∈𝒳 max 𝑦∈𝒴 𝑥⊤𝐺𝑦 ▪ 愚直に標準型ゲームに変換した場合よりも遥かに次元数が減らせる – 標準型ゲームと同様の理論解析を使い回せる – 関数近似と相性が悪く大規模ゲームの学習への適正△ 16
18. NO-REGRET LEARNING 17
19. 平均戦略 ▪ 反復𝑡 = 1から𝑇までアルゴリズムを実行したときのプレイヤー𝑖の反復間の平均 戦略を以下で定義する： ത 𝜋𝑖 𝑇 𝑎 𝑥 = σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥 𝜋𝑖 𝑡 𝑎 𝑥 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥 ▪ 愚直に考えると自然に出てくる定義 1 𝑇 σ𝑡=1 𝑇 𝜋𝑖 𝑡 𝑎 𝑥 とは異なることに注意！ ▪ 平均戦略ത 𝜋𝑖 𝑇が均衡に収束するような学習アルゴリズムをまず作ることから始め ることが多い 18
20. リグレット ▪ 各プレイヤ𝑖のリグレット 𝑅𝑖 𝑇 ≔ 1 𝑇 max 𝜋𝑖 ′ ෍ 𝑡=1 𝑇 𝑣𝑖 𝜋𝑖 ′, 𝜋−𝑖 𝑡 − 𝑣𝑖 𝜋𝑡 ▪ 直感的には，「この戦略を取っていたらこれくらい利得をあげられた」という 量を定量化したもの ▪ リグレットが0に収束するような学習アルゴリズム (𝑅𝑖 𝑇 = 𝑜 1 ) をno-regretであ ると呼ぶ 19
21. リグレットと平均戦略 ▪ 【リグレットと平均戦略の収束性】 二人零和展開型ゲームにおいて，平均戦略 のNashConvは各プレイヤーのリグレット の和によって表現できる： NashConv ത 𝜋𝑇 = 𝑅1 𝑇 + 𝑅2 𝑇 ▪ アルゴリズムがno-regretである ➔ 平均戦略ത 𝜋𝑇が均衡に収束する！ (i.e., NashConv ത 𝜋𝑇 = 𝑜 1 ) 20 𝑇 𝑇 − 1 𝑇 − 2 1 平均戦略: 1 𝑇 σ𝑡=1 𝑇 𝑥𝑡 ・・・ 𝑥𝑇 𝑥𝑇−1 𝑥𝑇−2 𝑥1 ナッシュ均衡 𝑇 → ∞
22. 平均戦略ത 𝜋𝑇に対する直感的解釈 ▪ Sequence-form戦略の意味での平均戦略，つまり到達確率の反復間の平均につい て考えてみる： ҧ 𝜌𝑖 𝑇 ℎ ≔ 1 𝑇 ෍ 𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 ℎ ▪ 【sequence-form戦略の平均戦略と到達確率の関係性】 任意の履歴𝒉について，以下が成り立つ： ҧ 𝜌𝑖 𝑇 ℎ = 𝜌𝑖 ഥ 𝜋𝑇 ℎ ▪ 「ത 𝜋𝑇について考える」 = 「sequence-form戦略の意味での平均戦略 ҧ 𝜌𝑖 𝑇について 考える」ということ！ 21
23. 証明スケッチ ▪ 平均戦略の定義から，𝜌𝑖 ഥ 𝜋𝑇 ℎ は以下のように書ける： 𝜌𝑖 ഥ 𝜋𝑇 ℎ = ത 𝜋𝑖 𝑇 𝑎1 𝑥 ℎ1 × ത 𝜋𝑖 𝑇 𝑎2 𝑥 ℎ2 × ⋯ × ത 𝜋𝑖 𝑇 𝑎𝐿 𝑥 ℎ𝐿 = σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥1 𝜋𝑖 𝑡 𝑎1 𝑥1 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥1 × σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥2 𝜋𝑖 𝑡 𝑎2 𝑥2 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥2 × ⋯ × σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥𝐿 𝜋𝑖 𝑡 𝑎𝐿 𝑥𝐿 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥𝐿 ▪ ここで，完全記憶の仮定から，𝜌𝑖 𝜋𝑡 𝑥𝑙 = 𝜌𝑖 𝜋𝑡 𝑥𝑙−1 𝜋𝑡 𝑎𝑙−1 𝑥𝑙−1 と書けるので， σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥1 𝜋𝑖 𝑡 𝑎1 𝑥1 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥1 × σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥2 𝜋𝑖 𝑡 𝑎2 𝑥2 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥2 × ⋯ × σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥𝐿 𝜋𝑖 𝑡 𝑎𝐿 𝑥𝐿 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥𝐿 = σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥𝐿 𝜋𝑖 𝑡 𝑎𝐿 𝑥𝐿 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥1 = σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥 ℎ𝐿 σ 𝑡=1 𝑇 1 = 1 𝑇 ෍ 𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑧 22 分母・分子で打ち消し合う
24. ここまでの議論まとめ 1. Sequence-form戦略の意味での平均戦略 ҧ 𝜌𝑖 𝑇 ℎ ≔ 1 𝑇 σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 ℎ は，各プレイヤー 𝑖のリグレット𝑅𝑖 𝑇を抑えることで均衡へと収束する 2. sequence-form戦略の平均戦略 ҧ 𝜌𝑖 𝑇 ℎ をbehavioral-form戦略へと変換 ത 𝜋𝑖 𝑇 𝑎 𝑥 = σ𝑡=1 𝑇 𝜌𝑖 𝜋𝑡 𝑥 𝜋𝑖 𝑡 𝑎 𝑥 σ 𝑡=1 𝑇 𝜌 𝑖 𝜋𝑡 𝑥 – ҧ 𝜌𝑖 𝑇 ℎ = 𝜌𝑖 ഥ 𝜋𝑇 ℎ であることを利用 3. 各プレイヤー𝑖のリグレット𝑅𝑖 𝑇を抑えられると到達確率で重み付けた平均戦略 ത 𝜋𝑖 𝑇が均衡に収束する 23
25. COUNTERFACTUAL REGRET MINIMIZATION 24
26. どうやってリグレットを最小化する？？ ▪ No-regretを達成できれば平均戦略が均衡へ収束するので，あとはno-regretな学 習アルゴリズムを用意できれば良い ▪ 期待利得関数𝑣𝑖 はsequence-form戦略の空間で考えると各プレイヤーから見てた だの線形関数となる – sequence-form戦略上の最適化問題として考えると，オンライン凸最適化の no-regret学習アルゴリズムがそのまま使い回せる ▪ 例：勾配法，Hedgeなど ➔ ではbehavioral-form戦略のまま学習させたい場合はどうすれば良い？？ 25
27. Immediate Counterfactual Regret (ICR) ▪ 情報集合𝑥ごとのリグレットについて考える 𝑅𝑖,CF 𝑇 𝑥 ≔ 1 𝑇 max 𝑎∈𝐴 𝑥 ෍ 𝑡=1 𝑇 𝜌−𝑖 𝜋𝑡 𝑥 𝑞𝑖 𝜋𝑡 𝑥, 𝑎 − ෍ 𝑏∈𝐴 𝑥 𝜋𝑖 𝑡 𝑏 𝑥 𝑞𝑖 𝜋𝑡 𝑥, 𝑏 – 𝑞𝑖 𝜋𝑡 𝑥, 𝑎 ：情報集合𝑥において行動𝑎を取った際の条件付き期待利得 ▪ 直感的には，「この行動を取ったらこれくらい利得をあげられた」という量を 定量化したもの 26
28. ICRの理論的性質 ▪ 【ICRによるリグレット上界 [Zinkevich et al., 2007]】 リグレット𝑹𝒊 𝑻はICRによって以下のように抑えられる： 𝑅𝑖 𝑇 ≤ ෍ 𝑥 max 0, 𝑅𝑖,CF 𝑇 𝑥 ▪ 全体のリグレット𝑅𝑖 𝑇を抑えるためには，情報集合𝑥ごとのリグレット𝑅𝑖,CF 𝑇 𝑥 を 抑えれば十分！ 27
29. 情報集合ごとのリグレット最小化 ▪ ではどうやって情報集合ごとにリグレットを最小化するか？ ▪ 𝑙𝑡 𝑥, 𝑎 = 𝜌−𝑖 𝜋𝑡 𝑥 𝑞𝑖 𝜋𝑡 𝑥, 𝑎 と定義すると，ICRは以下のように書き直せる： 𝑅𝑖,CF 𝑇 𝑥 ≔ 1 𝑇 max 𝜋𝑖 ⋅ 𝑥 ∈Δ 𝐴 𝑥 ෍ 𝑡=1 𝑇 𝑙𝑡 𝑥 , 𝜋𝑖 ⋅ 𝑥 − 𝜋𝑖 𝑡 ⋅ |𝑥 – 𝑙𝑡 𝑥 を損失ベクトルとして受け取るオンライン凸最適化問題と同じ！ ➔ 勾配法などの適当なno-regretな学習アルゴリズムを使えば𝑅𝑖,CF 𝑇 𝑥 = 𝑜 1 を達成できる ▪ （まとめると）それぞれの情報集合𝑥でno-regretな学習アルゴリズムを動かせば 良い！ 28
30. Counterfactual Regret Minimization (CFR) ▪ 各情報集合ごとに，Regret Matchingと呼ばれるno-regretな学習アルゴリズムを 動かすアルゴリズム ▪ CFRの更新式 𝜋𝑖 𝑇+1 𝑎|𝑥 = max(𝑅𝑖,CF 𝑇 𝑥, 𝑎 , 0) σ 𝑎∈𝐴(𝐼) max(𝑅 𝑖,CF 𝑇 𝑥, 𝑎 , 0) , 𝑖𝑓 ෍ 𝑎∈𝐴(𝐼) max(𝑅𝑖,CF 𝑇 𝑥, 𝑎 , 0) > 0 1 |𝐴 𝑥 | , otherwise ▪ 学習率のようなハイパラを１つも持たない and behavioral-form戦略をダイレク トに学習できるので使いやすい 29 [Zinkevich et al., 2007]
31. CFRの理論的性質 ▪ 【CFRのリグレット上界 [Zinkevich et al., 2007]】 反復𝒕 = 𝟏から𝑻までCFRに従って各プレイヤーの戦略を更新したとき，各プレイヤ ーのリグレットは以下のように抑えられる： 𝑅𝑖 𝑇 ≤ Δ𝑖 𝑋𝑖 max 𝑥∈𝑋𝑖 𝐴 𝑥 𝑇 – Δ𝑖 ： max 𝑧,𝑧′∈𝑍 𝑢𝑖 𝑧 − 𝑢𝑖 𝑧′ – 𝑋𝑖 ：プレイヤー𝑖にとっての情報集合の集合 ▪ リグレットが𝑂 1 𝑇 で抑えられるので，平均戦略ത 𝜋𝑇も 1 𝑇 程度の速さで均衡に収 束する！ 30
32. 証明の流れ 1. Regret Matchingが確率単体上のオンライン最適化問題において，no-regretであ ることを示す 2. 各情報集合ごとの学習アルゴリズムとしてRegret Matchingを用いれば， 𝑅𝑖,CF 𝑇 𝑥 = 𝑜 1 であることが示せる 3. 全体のリグレットと情報集合ごとのリグレットの関係性から，全体のリグレッ トも𝑜(1)で抑えられることが示せる 𝑅𝑖 𝑇 ≤ ෍ 𝑥 max 0, 𝑅𝑖,CF 𝑇 𝑥 = 𝑜 1 . 31
33. その後の発展 ▪ 大規模ゲームで良い性能を達成した学習アルゴリズムのほとんどがCFRと同様 に「情報集合ごとのリグレット（あるいは期待利得）をもとに学習」する： 𝜌−𝑖 𝜋𝑡 𝑥 𝑞𝑖 𝜋𝑡 𝑥, 𝑎 − ෍ 𝑏∈𝐴 𝑥 𝜋𝑖 𝑡 𝑏 𝑥 𝑞𝑖 𝜋𝑡 𝑥, 𝑏 or 𝜌−𝑖 𝜋𝑡 𝑥 𝑞𝑖 𝜋𝑡 𝑥, 𝑎 ▪ なのでまずは基本的な理論的背景としてICRを理解するところから始めると吉 32
34. おわりに 33
35. まとめ ▪ 展開型ゲームの均衡学習において，リグレット最小化は非常に基礎的な要素 ▪ Behavioral-form戦略で学習を行いたい場合でも，sequence-form戦略での収束性 を考えてアルゴリズム設計を行うと理論的保証が与えやすい ▪ CFRの解説・実装を公開しているので，参考にしてもらえたら幸いです – https://qiita.com/bakanaouji/items/f70d7948931c96d94ef8 – https://github.com/bakanaouji/cpp-cfr 34
36. 参考文献 35 ▪ Anton Bakhtin, David J Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexander H Miller, and Noam Brown. Mastering the Game of No-Press Diplomacy via Human- Regularized Reinforcement Learning and Planning. In ICLR, 2023. ▪ Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 2018. ▪ Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 2019. ▪ Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 2022. ▪ Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In NeurIPS, 2007.