2021-11-06

2021年研究室紹介予定

岩崎研究室の研究紹介予定です．

https://sites.google.com/site/a2ciwasaki/

原則としてオンラインで行います．

在来生研修会
- 11月5日１８：００～２０：００
- URLは在来生研修の案内を見てください．
- 使用したスライドはこちら

www.slideshare.net

公開ゼミ
- ゼミ終了後３０分程度，在学生を交えて雑談します．
- １１月１７日１３：３０～１５：００，内容はデータ分析です．
- １１月１８日１４：４０～１６：００，内容は英語のライティングです．
- URLはatsushi.iwasaki@uec.ac.jpまでお問い合わせください．
調布祭（１１月２０，~~２１日~~）
- ２０日~~両日とも~~１５：３０～１６：００で紹介と雑談をします．
- URLはatsushi.iwasaki@uec.ac.jpまでお問い合わせください．
- ２１日は諸事情で中止になりました．個別に面談を希望する方はご連絡ください．

2020-11-26

WindowsでOpenSpiel (DeedMindの強化学習ライブラリ)を動かす方法 (WSL: Ubuntu18.04.5 LTS)

はじめに

今回はWindowsでOpenSpiel (DeedMindの強化学習ライブラリ) を動かそうとしたところ，つまってしまったので，その環境構築手順と解決策をまとめます．

環境

Windows 10

WSL: Ubuntu18.04.5LTS

conda 4.8.3 (Miniconda)

OpenSpiel

OpenSpielはDeepMindが提供している(深層)強化学習ライブラリです．

DeepMindはGoogle傘下の人工知能開発企業で，開発したプログラムの中でも，人間のプロ囲碁棋に勝利したAlphaGoがよく知られています．

OpenSpielには様々な強化学習のアルゴリズムが実装されており，とても参考になります．

今回はこのOpenSpielの環境構築の方法を紹介します．

github.com

Windows Subsystem for Linux(WSL)

プログラムにはWindows上では動作しないものがあります．そのときに，活躍するのがWindows Subsystem for Linux (WSL) です． WSLは簡単にいうと，Windows上でLinuxを動かすことのできる便利なツールです．

WSLのインストールについて以下の記事がおすすめです．この記事ではUbuntu 20.04 LTSを選択していますが，この記事で用いているのはUbuntu 18.04 LTSなので注意してください (通常のインストール・使用にはなんの問題もありません).

逆にこの時点でWSLをインストールしていない方は，Ubuntu 20.04 LTSをインストールすることをおすすめします．(Ubuntu 20.04 LTSのほうがOpenSpielのインストールが簡単です．)

WSL 2 のインストール，Ubuntu 20.04, 18.04 のインストールと利用

Anaconda (Miniconda)

Pythonに限らず多くのプログラムはライブラリのバージョンへ依存しています．そのため，自分の元のPython環境 (usr/bin/python) に直接ライブラリをインストールすると，あるプログラムは動くけど，あるプログラム動かないなどの問題が発生することがあります．

そこで用いられるのが仮想環境です．環境ごとにインストールするライブラリやそのバージョンを指定することで，上記の問題を解決することができます． Pythonの仮想環境では，conda, virtualenv, venvなどが挙げられますが，今回はAnaconda (Miniconda) を用いた仮想環境の構築を紹介します. ¹ (仮想環境は特になんでも大丈夫です)

環境構築は以下の記事を参考にしています．

Ubuntu 18.04上でminicondaを使う

minicondaのインストール方法

# minicondaのインストールに用いるシェルファイルをダウンロード
$ wget https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh
# インストールを実行
$ bash Miniconda3-latest-Linux-x86_64.sh
# パスを通す (勝手に通っているときもある気がする)
$ ~/miniconda3/bin/conda init bash
$ source ~/.bashrc
# パスが通っているか確認
$ which conda

OpenSpielのインストール方法

基本的には公式がインストール方法を紹介してくれているので，それに従ってインストールを行います．

https://github.com/deepmind/open_spiel/blob/master/docs/install.md

Ubuntuに必要なパッケージをインストール

./install.sh

仮想環境の構築

公式ではvirtualenvを使用していますが，今回は先ほどインストールしたcondaを用いて仮想環境を構築します．

# 環境の作成 環境名(OpenSpielの部分)はなんでも大丈夫です．pythonは3.7以上を使用しましょう
$ conda create -n OpenSpiel python=3.7
# 仮想環境を有効にする
$ conda activate OpenSpiel

pipのアップグレード

公式通り

curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py
# Install pip deps as your user. Do not use the system's pip.
$ python3 get-pip.py
$ pip3 install --upgrade pip
$ pip3 install --upgrade setuptools testresources

pythonライブラリのインストール

$ pip3 install -r requirements.txt

はまったところ (Ubuntu 18.04 LTS)

OpenSpileはpythonだけでなくC++(C?) を用いたライブラリなので，そのコンパイルをする必要があります．しかし，コマンドを実行するとコンパイルエラーが発生しうまくビルドすることができませんでした．(Ubuntu 20.04 LTSではこの問題は発生しませんでした．)

$ ./open_spiel/scripts/build_and_run_tests.sh

エラー内容

error: explicit specialization of 'value' in class scope
  int value() const {
      
～中略～

Makefile:94: recipe for target 'all' failed
make: *** [all] Error 2

これを調べてみるとコンパイラのバージョンが古いことが問題だったようなので，アップデートを行います. 以下のissueで似たようなことが起こっていたので，それを参考にしています．

https://github.com/deepmind/open_spiel/issues/321

コンパイラのインストールと変更

$ apt-get install clang-10
# clang++ をclang-10に置き換える
$ sudo ln -s -f $(which clang-10) /usr/bin/clang++

再びコマンドを実行すると無事ビルドが成功しました．(テストがなぜが１つ通りませんが問題なく動作します)

$ ./open_spiel/scripts/build_and_run_tests.sh

python pathを通す

最後にプロジェクトのパスを通して終了です．

.bashrcに以下を追記します．

# /<path_to_open_spiel>はopen_spielのディレクトリパス
export PYTHONPATH=$PYTHONPATH:/<path_to_open_spiel>
export PYTHONPATH=$PYTHONPATH:/<path_to_open_spiel>/build/python

WSLを再起動するとOpenSpielが使用できるようになります．適当な例を動かしてみましょう．この時，仮想環境の起動を忘れないように注意してください．

最後に

今回はDeepMind社の強化学習ライブラリOpenSpielのWindowsにおける環境構築について紹介しました．環境構築には私もよく苦労するので，少しでも皆さんの助けになればと思います．

これは経験則ですが，condaの仮想環境でパッケージをインストールするときはpipコマンドを用いることを強くおすすめします．condaコマンドでインストールすると環境が汚くなる場合があります．特にpip, condaコマンドは混ぜるな危険です．condaをどうしても使用しなければいけない場合でも，その時はcondaコマンドだけを使うようにしましょう．↩

2020-11-09

An evolutionary dynamical analysis of multi-agent learning in iterated games の要約・再現実験 (ver. 学生チェック)

はじめに

マルチエージェント強化学習は，マルチロボット制御などへの応用が期待されています．しかし，複数のエージェントに設計者の望む学習をさせるのは困難です．本記事では，ゲーム理論の分析手法である，進化ダイナミクスを用いることでエージェントの学習軌跡・結果を予測する研究について紹介します．具体的には，「Tuyls, K., T Hoen, P. J., & Vanschoenwinkel, B. (2006). An evolutionary dynamical analysis of multi-agent learning in iterated games. Autonomous Agents and Multi-Agent Systems」の要約と，実験結果の再現を行いたいと思います．

モデル

まずは，今回論文で用いられているゲーム (環境) について，説明します．

2人2手番標準形ゲームの定義

2人2手番標準形ゲームは，2人のプレイヤ（プレイヤ1，プレイヤ2）が行動{1, 2}からそれぞれ1つずつ選択し，2人の選択した行動に対応する利得を獲得するゲームです．プレイヤ1とプレイヤ2の利得は以下の行列 $A$ ， $B$ に従って与えられます．この行例はプレイヤ1の行動が行にプレイヤ2の行動が列に対応します．例えばプレイヤ1が行動2，プレイヤ2が行動1を選択した場合，プレイヤ1の利得 $P_1$ には $a_{21}$ ，プレイヤ2の利得 $P_2$ には $b_{21}$ が与えられます．

\begin{equation} A =\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{array} \right) \end{equation}

このゲームおいて，プレイヤmは戦略と呼ばれる，行動の選択確率を持ち，その確率に従いプレイヤは行動を選択します．戦略は以下のように定義されます． \begin{equation}S_m = (x_1, x_2)\ , x_1 + x_2 = 1　(x_1, x_2はそれぞれの選択確率)\end{equation}

この時，確実に1つの行動を選ぶような戦略 $S_m=(1, 0) , S_m = (0, 1)$ を純粋戦略，それ以外のどちらの行動も確率的に選択される戦略を混合戦略と呼びます．

また各プレイヤの利得はこの戦略から求めることができます，例えば，プレイヤ1の戦略を $S_1＝(x_{11}, x_{12})$ ，プレイヤ2の戦略を $S_2 = (x_{21}, x_{22})$ とすると，それぞれの利得は

\begin{equation}P_1 ＝ x_{11} x_{21} a_{11} + x_{11} x_{22} a_{12} + x_{12} x_{21} a_{21} + x_{12} x_{22} a_{22} \end{equation}

\begin{equation}P_2 ＝ x_{11} x_{21} b_{11} + x_{11} x_{22} b_{12} + x_{12} x_{21} b_{21} + x_{12} x_{22} b_{22} \end{equation}

になります．

Class 1~3

この2人2手番標準形ゲームはその利得構造に応じて，３つの異なる均衡を形成するクラスに分類できます．

Class 1

利得が以下の条件を満たすとき，少なくとも1人のプレイヤは支配的な戦略を持ち，1つの厳格な均衡が存在します． \begin{equation}( (a_{11} - a_{21})(a_{12}-a_{22})>0) \vee ( (b_{11}-b_{12})(b_{21}-b_{22})>0)\end{equation} 支配的な戦略とは，プレイヤが相手の戦略・行動によらず，自分の利得を最大化できる戦略です．条件式に注目すると， $(a_{11}-a_{21})(a_{12}-a_{22})>0$ が成り立つの以下の場合です．

\begin{equation} ( a_{11}>a_{21} \land a_{12}>a_{22} ) \vee ( a_{11}>a_{21} \land a_{12}>a_{22} )\end{equation}

$( a_{11}>a_{21} \land a_{12}>a_{22} )$ が成り立つ場合，相手が1を選択したとき，プレイヤ1は行動1を選択する方が利得が高く，また相手が行動2を選択する場合も同様です． ( a_{11}>a_{21} \land a_{12}>a_{22} )が成り立つ場合，プレイヤ1が行動2を選択すると常に利得が高くなります． $(b_{11}-b_{12})(b_{21}-b_{22})>0$ はプレイヤ2について同様の意味を持ちます．

片方のプレイヤが支配的な戦略を持つとき，他方のプレイヤはこの戦略に応じた行動を選択することが最適となります．このとき，2人のプレイヤが常に同じ行動を選択するような戦略の組が均衡となります．このような均衡のことを厳格な均衡と呼びます．

Class 2

利得が以下の条件を満たすとき，2つの純粋戦略均衡と混合戦略均衡が存在します． \begin{eqnarray} ( (a_{11} - a_{21})(a_{12}-a_{22})<0) \land \\ ( (b_{11}-b_{12})(b_{21}-b_{22})<0) \land \\ ( (a_{11}-a_{21})(b_{11}-b_{12}) > 0) \end{eqnarray} ここでは単純化のために $a_{11}>a_{P_{21}}$ の場合について考えます．すると以下の関係が成り立ちます． \begin{equation} (a_{11} > a_{21}) \land (a_{12} < a_{22}) \land (b_{11} > b_{12}) \land (b_{21} < b_{22}) \end{equation} このとき，それぞれのプレイヤは相手がどの行動をとったかによって，適切な反応(行動)が異なります．ここで，プレイヤ1が行動1を固定した場合を考えると，プレイヤ2の最適反応は行動1となります( $b_{11}>b_{12}$ )．プレイヤ2が行動1を取るとき，プレイヤ1の最適反応も行動1となります ( $a_{11}>a_{12}$ ) ．よってこれは純粋戦略均衡となります．またプレイヤ1が行動を2に固定した場合もプレイヤ2の最適反応は行動2となり，同様にこれも純粋戦略均衡となります．しかし，前述のようにプレイヤは確率的に行動を選択する混合戦略を持つことができます．このとき，プレイヤ１の戦略 $s_1 = ( \frac{b_{22}-b_{21}}{b_{11}-b_{12}-b_{21}-b_{22}}, \frac{b_{11}-b_{12}}{b_{11}-b_{12}-b_{21}+b_{22}})$ , プレイヤ２の戦略 $s_2 = ( \frac{a_{22}-a_{12}}{a_{11}-a_{12}-a_{21}+a_{22}} \frac{a_{11}-a_{21}}{a_{11}-a_{12}-a_{21}+a_{22}})$ が混合戦略均衡となります．

Class 3

利得が以下の条件を満たすとき，1つの混合戦略均衡が存在します． \begin{eqnarray} ( (a_{11}-a_{21})(a_{12}-a_{22}) < 0) \land \\ ( (b_{11}-b_{12})(b_{21}-b_{22})<0) \land \\ ( (a_{11}-a_{21})(b_{11}-b_{12})<0) \end{eqnarray} 先ほどまでと同様に， $a_{11}>a_{21}$ の場合について考えます．すると以下の関係が成り立ちます． \begin{equation} (a_{11} > a_{21}) \land (a_{12} < a_{22}) \land (b_{11} < b_{12}) \land (b_{21} > b_{22}) \end{equation} ここでClass2と同様にプレイヤ1の行動1に固定して考えて見ると，プレイヤ2の最適反応は2となります( $b_{11} \gt b_{12}$ )．プレイヤ2が行動2を取る場合，プレイヤ1の最適反応は行動2となります ( $a_{21} \gt a_{22}$ )．(そしてこのとき．．．) このように今の自分の行動に対する相手の最適反応が，いまの行動のままでは最適反応にならないため，この条件下では純粋戦略均衡が存在しません．しかし，Class3もClass2と同様の混合戦略均衡が存在します．

本稿で使う具体的なゲーム

本稿では上記の3つのクラスに分類されるゲームを用います．

Class 1 囚人のジレンマ

Class 1に当てはまるのは以下のような利得表をもつゲームです．

\begin{equation} A =\left( \begin{array}{cc} 1 & 5 \\ 0 & 3 \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} 1 & 0 \\ 5 & 3 \\ \end{array} \right) \end{equation}

このゲームでは，プレイヤ1および2は行動1が支配戦略となり，強均衡が存在します．この時，プレイヤの利得は $P_1=1$ , $P_2=1$ となります．もしプレイヤ1および2がともに行動2を選択した場合，利得は $P_1=3$ ， $P_2=3$ となり，2人のプレイヤがより多くの利得を得ます．しかし，相手が行動2を選択しているとき，行動1を選択すれば，相手の利得は0になりますが，自分は現在の利得よりも大きな5を得ます．このため，両プレイヤは結局行動1を選択します．このように合理的な行動選択が全体にとって望ましい結果にならないゲームを，囚人の黙秘や自白に例えて「囚人のジレンマ」と呼びます．

Class 2 両性の争い

Class 2に当てはまるのは以下のような利得表をもつゲームです．

\begin{equation} A =\left( \begin{array}{cc} 2 & 0 \\ 0 & 1 \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \\ \end{array} \right) \end{equation}

このゲームでは，プレイヤ1が行動1，プレイヤ2が行動2を選択する場合とプレイヤ1が行動2，プレイヤ2の行動2を選択する場合の2つの純粋戦略均衡が存在します．両プレイヤが行動1を選択する均衡では $P_1=2$ , $P_2=1$ ，行動2を選択する均衡では $P_1=1$ ， $P_2=2$ となり，どちらも全体にとっては望ましい結果ですが，各プレイヤにとってはどちらかが”我慢”をすることになります．このようなゲームを男女のデートの場所選びに例えて「両性の争い」また「男女の戦い」と呼びます．また２つ混合戦略均衡が存在し，それぞれ

\begin{equation} S_1=( \frac{2-0}{2-0-0+1}, \frac{1-0}{2-0-0+1}) =(\frac{2}{3}, \frac{1}{3}) \end{equation}

\begin{equation} S_2=( \frac{1-0}{1-0-0+2}, \frac{2-0}{1-0-0+2}) =(\frac{1}{3}, \frac{2}{3}) \end{equation}

となります．試しに片方の戦略を純粋戦略に置き換えてみると，利得は改善しないので，これが均衡になっていることがわかります．

Class 3 唯一の混合戦略均衡

Class 3に当てはまるのは以下のような利得表をもつゲームです．

\begin{equation} A =\left( \begin{array}{cc} 2 & 3 \\ 4 & 1 \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} 3 & 2 \\ 1 & 4 \\ \end{array} \right) \end{equation}

このゲームでは純粋戦略均衡は存在しません．例えば，プレイヤ1が行動1を選択する場合，プレイヤ2は行動1を選択し，プレイヤはそれぞれ利得 $P_1=2$ , $P_2=3$ を受け取ります．しかし，プレイヤ1がプレイヤ2が行動1を選択する場合，行動2を選択することが最適反応となるため，プレイヤ1は行動2を選択します．

一方で，混合戦略均衡は２つ存在し，それぞれ

\begin{equation} S_1=( \frac{4-2}{3-2-1+4},\ \frac{3-1}{3-1-2+4})=(\frac{1}{2}, \frac{1}{2}) \end{equation}

\begin{equation} S_2=( \frac{1-3}{2-3-4+1},\ \frac{2-4}{2-3-4+1})=(\frac{1}{2}, \frac{1}{2}) \end{equation}

となります．この場合もClass 2と同様に，片方の戦略を純粋戦略に置き換えてみると，利得は改善しないので，これが均衡になっていることがわかります．

ナッシュ均衡とパレート効率性

ゲーム理論における一般的なゲームでは，ナッシュ均衡が実現すると考えられています．これはどのような戦略をとれば良いかというゲーム理論の問いに対する解の1つで，これまで分析した均衡は全てナッシュ均衡です．2人n手番標準形ゲームにおいて，ナッシュ均衡は以下のように定義されます．

2人のプレイヤが戦略の組 $s=(s_i,s_j)$ に従ってプレイする時，もし $P_1(s_i,s_j) \ge P(s_x, s_j) \forall x \in {1,...,n} \land P_1(s_i, s_j) \ge P(s_i, s_x)\ \forall x \in {1,...,n}$ であれば戦略の組sはナッシュ均衡である．

これはどちらか一方のプレイヤが戦略を変えても得をしないことを意味します．つまりナッシュ均衡では各プレイヤの戦略がお互いに最適反応となります．

もう１つパレート効率性という概念を紹介します．ゲームにおいて，あるプレイヤの利得を改善するには，誰かの利得を減らさなければならない状態のことをパレート効率的であると言います．これは以下のように定義します．

ある戦略の組み合わせ， $s$ が存在し，もし全てのプレイヤが最低でも同じ利得，1人以上のプレイヤが今よりも大きな利得を受け取る $s'$ が存在しなければsはパレート効率的である．

これらの「ナッシュ均衡」と「パレート効率性」を用いると，囚人のジレンマのナッシュ均衡はパレート効率的でないことがわかります．「囚人のジレンマ」の例でナッシュ均衡に従う利得は $P_1=1$ ， $P_2=1$ ですが，両プレイヤが行動2を選択すると，利得は $P_1=3$ ， $P_2=3$ になります．このように両プレイヤの利得が増加するので，「囚人のジレンマ」のナッシュ均衡はパレート効率的ではありません．

進化ゲームと人口ゲーム

進化ゲームとは，生物の進化の概念に着想を得た，ゲーム理論における戦略の分析方法です．これまで，ゲーム理論では，ナッシュ均衡の概念を用いて様々な分析が行われてきました．しかし，ナッシュ均衡だけではtrimbling hand (震える手) などの，より現実を反映したゲームの均衡を適切に予測することができませんでした．そこで，生物の進化の過程における，選択（淘汰）と突然変異の概念を利用することで，戦略分析を動学的なモデルとして扱う進化ゲームが提案されました．進化ゲームでは戦略を生物の種に置き換えることで，その環境において生き残る種，つまりゲームにおいて有効な戦略を導きます．生物は選択（淘汰）と突然変異を繰り返すことで進化を遂げて来ました．淘汰されるかどうかはその環境に適応できたかどうかによって決まり，また適応できるかどうかは環境だけでなく人口分布によって決定されます．また一定の確率で突然変異することで，その多様性を保ってきました．

これをゲームに置き換えて考えてみましょう．ある環境にははじめ，異なる戦略を持つ複数の種のプレイヤが存在します．全体の人口の総量は変わることがないため，ある種のプレイヤは自分と同じ戦略，また異なる戦略を持つプレイヤと実際にゲームをプレイし，その利得の大小によって，人口を変化させます．つまり今のゲーム・人口分布において，有利な戦略は人口を増やし，不利な戦略は人口を減らします．また淘汰だけではなく，ある一定の突然変異確率に従って，その人口を増減させます．これを繰り返すことで，最終的にはある１つの戦略または複数の戦略が共存する形で人口変化は収束し，生き残った戦略がそのゲームにおいて有効な戦略となります．以上が進化ゲームにおける有効な戦略分析の考え方です．

ESSの定義

次に進化ゲームにおける均衡の定義，ESS (Evolutionary Stable Strategies)：進化的に安定な戦略について説明します．進化的に安定な戦略とは，突然変異戦略の進化圧力に対してロバストな戦略のことです．例えば，同じ戦略を持つプレイヤの集団を考えます．この集団の中で．ある一定の割合が突然変異戦略に変化し，元の集団を侵攻し始めます．もし新しい戦略の成長率が元の戦略よりも小さい場合，その戦略はやがて消滅します．この時，元の戦略は進化的に安定しているということが言えます．

次にESSの定義について説明します．人口の大部分を占める戦略s，突然変異戦略をs'とし，s'の割合を $\epsilon$ とします．この時，ある1体のプレイヤがランダムで選ばれたプレイヤと対戦するとき，s'と対戦する確率は $\epsilon$ ，sと対戦する確率は $1-\epsilon$ になります．この確率を用いて，各プレイヤの利得は以下のように求められます．戦略sを持つプレイヤ

\begin{equation} P(s,(1-\epsilon )s + \epsilon s')\ i.e. (1-\epsilon )P(s,s) + \epsilon P(s, s') \end{equation}

戦略s'を持つプレイヤ

\begin{equation} P(s',(1-\epsilon )s + \epsilon s')\ i.e. (1-\epsilon )P(s',s) + \epsilon P(s', s') \end{equation}

この利得からESSは次のように定義することができます．

もし任意の戦略 $s' \neq s$ について， $0 \lt \epsilon \lt \delta$ における任意の $\epsilon$ が $(1-\epsilon )P(s,s) + \epsilon P(s, s') > (1-\epsilon )P(s',s) + \epsilon P(s', s')$ を満たすような $\delta \in [0,1$ ]が存在するとき，戦略sはESSである．

ナッシュ均衡とESSの関係

次にESSとナッシュ均衡の関係について説明します．これまでの研究によって，特定のゲームにおいてナッシュ均衡がESSを包含していることが明らかになっています．これはESSの条件がナッシュ均衡よりも厳しいからです．まずナッシュ均衡は定義から他のプレイヤ戦略に対しての最適反応です．しかし戦略sがESSであれば，sは他の戦略だけでなく，s自身に対しても最適反応である必要があります．そうでなければsよりもsに対して有効な戦略s'が存在し，s'の突然変異確率が十分に大きいとき，sは進化的に安定ではありません．この理由からナッシュ均衡はESSを包含します．

レプリケータダイナミクス (Replicator Dynamics)

ここでは実際に進化ゲームの概念に基づき，戦略分析する手法Replicator Dynamics（RD）について説明します． RDは戦略分布における人口の変化の期待値の近似値のことを指し，以下の微分方程式に定式化されます．この微分方程式を解くことで，進化ゲームにおける戦略人口の変化の流れを知ることができます．

\begin{equation} \frac{dx_i}{dt}= [(A \textbf{x} )_i −\textbf{x} \cdot A \textbf{x} ]x_i \tag{1} \end{equation}

$x_i$ は戦略 $s_i$ の人口（母集団）中の割合， $A$ は利得行列で $(A \textbf{x} )_i$ は戦略 $s_i$ の平均利得， $\textbf{x} \cdot A \textbf{x}$ は母集団全体の平均利得です．ここで母集団全体を示す $\textbf{x}$ は各戦略のベクトルとして表現されます． $\textbf{x}=\{x1,x2,x3,...\}$ .また $x_i$ の成長率， $\frac{dx}{dt}/x_i$ は母集団全体の平均利得と戦略 $i$ の平均利得の差に等しくなります．

上では母集団が1つの場合を考えましたが，母集団が2つある場合もRDを求められま．これを進化的非対称ゲームと呼び，以下のように定義されます．

\begin{equation} \frac{dp_i}{dt}= [(A \textbf{q} )_i −\textbf{p} \cdot A \textbf{q} ]p_i \tag{2} \end{equation}

\begin{equation} \frac{d q_i}{dt}= [(B \textbf{p} )_i −\textbf{q} \cdot B \textbf{p} ]q_i \tag{3} \end{equation}

$p_i$ ， $q_i$ はそれぞれの母集団における戦略 $s_i$ の割合を指します (あくまで添字なので，母集団1の $s_i$ と母集団2の $s_i$ は同一であるとは限りません) ． $(A \textbf{q} )_i$ ， $(B \textbf{p} )_i$ はそれぞれ $s_i$ の平均利得を， $\textbf{p} \cdot A \textbf{q}$ ， $\textbf{q} \cdot B \textbf{p}$ は母集団の平均利得を示します.(ここでは $\textbf{p}$ ， $\textbf{q}$ の違いに注意してください)．またここで，母集団はそれぞれ異なる利得行列 $A$ ， $B$ を用いていることに注意してください．(また $A = B^t$ である場合，(2) (3) 式は (1) と一致します)

ナッシュ均衡，ESS，RDの関係

次にこれまで紹介した3つの概念，ナッシュ均衡，ESS，RDの関係について説明します．従来研究によってRDが漸近的に安定であれば，それはナッシュ均衡であり，ESSであることが示されています．RDは微分方程式で表されるため，そこには平衡点が存在します．RDにおいて以下の条件を満たすとき，それは漸近的に安定です．（正式な定義については省略します）

RDの平衡点の近傍から出発する軌道が平衡点の近くに留まり続けるとき (この条件をリアプノフ安定性と呼ぶ)
RDの平衡点の近傍から出発する軌道が平衡点に収束するとき

強化学習

強化学習とは機械学習における大きな分類の１つで，エージェントと呼ばれる行動主体が行動の結果得た報酬をもとに方策を学習するアルゴリズムです．主に複数のエージェントによって構成されるマルチエージェント強化学習とゲーム理論は非常に近い関係にあり，強化学習における用語は，ゲーム理論では以下のように読み替えることができます．

ゲーム → 環境
戦略 → 方策
利得 → 報酬
プレイヤ → エージェント

また見方さえ変えれば，標準形ゲームは (もちろん他のゲームも) マルチエージェント強化学習の環境として簡単に扱うことができます．これら２つの研究分野はお互いに貢献しており，例えば，ゲーム理論では，強化学習エージェントによる方策獲得のプロセスは戦略の分析方法ととらえることができます．逆にマルチエージェント強化学習では，複数のエージェントに望ましい方策を学習させるためにゲーム理論が用いられます．

強化学習の一般的な定義

まずは強化学習の一般的な定義について説明します．強化学習はエージェントと環境によって構築されます．環境は状態集合 $s \in S$ から現在の状態sを持ち，エージェントの行動 $a \in A$ と遷移関数 $T(s, a) = s'$ によって状態を遷移させます．また状態遷移に応じて環境は報酬値 $R(s, a)$ をエージェントに与えます．エージェントは環境から状態sを観察し，行動aを決定します．この時エージェントは方策 $\pi(s) (\sum_{a'} \pi(s,a') = 1)$ と呼ばれる行動選択戦略に従い, 行動を決定します．またエージェントは行動によって環境から得た報酬をもとに方策を更新します．これは以下の流れで行われます．

エージェントが環境から状態を観測する．
エージェントは状態と自身の方策から行動を決定し，それを実行する (環境に出力する) ．
環境は状態と行動に従い，状態を遷移させ，報酬をエージェントに与える．
エージェントは環境から得た報酬をもとに方策を更新する．

この流れを，１ステップと呼びます．エージェントはステップを重ねることで学習を行いますが，環境はその性質に応じて，ステップ数や報酬獲得などの終了条件を持ちます．環境が終了条件を満たすと，環境は初期状態に遷移し，そこから学習を再開します．この初期状態から終了までを１エピソードと呼びます．強化学習ではこのエピソード数を設定することで，学習を終了させることが一般的です．

Q学習

強化学習における代表的な手法の１つがQ学習です． Q学習ではQ値と呼ばれる状態・行動ごとの価値を推定することで方策を学習します．ある状態sにおける行動aの価値は $Q(s,a)$ と表現されます．ある時刻 $t$ における状態 $s$ ,行動 $a$ のQ値を $Q_t(s,a)$ とすると，時刻 $t+1$ における $Q_{t+1}(s,a)$ は次状態 $s'$ と報酬 $r$ を用いて以下のように更新されます．

\begin{equation} Q_{t+1}(s, a) ← (1−\alpha)Q_t (s, a)+ \alpha (r + \gamma max_a' Qt (s', a')) \tag{4} \end{equation}

ここで， $\alpha \in [0,1$ ] は学習率を示し，一度の経験をどれだけ重視するというパラメータです．この学習率が大きいほど，１度の更新量が大きくなります． $\gamma \in [0,1$ ] は割引率で未来に得られる報酬の重要性を示します．この割引率が大きいほど，未来の報酬を重視します．このQ値の繰り返し更新，推定していくことで，エージェントは方策を学習します．

Q学習における戦略

上では，Q値（状態行動価値）の推定方法について説明しましたが，それだけでは方策を決定することができません．方策を決定するためには，状態価値から行動の選択確率を決定する必要があります．最も簡単な行動選択方法がグリーディ選択と呼ばれるものです．グリーディ選択では，単に最も大きな価値を持つ行動が選択されます．数式では以下のように定義されます.

\begin{equation} \pi(s, a) = \begin{cases} 1 & (a = argmax_{a'} Q(s, a')) \\ 0 & (othrewise) \end{cases} \end{equation}

$\epsilon$ グリーディ選択は，確率 $\epsilon$ でランダムな行動を選択し，それ以外はグリーディ選択に従う選択方法です．この $\epsilon$ によって，エージェントは探索的な行動ができます．また本稿ではボルツマン選択が採用されています． ボルツマン選択ではボルツマン分布に従って行動が選択され，それぞれの選択確率は以下のように定義されます．

\begin{equation} \pi(s,a) = \frac{e^{ \tau Q(s, a)}}{ \sum_{a'} e^{ \tau Q(s, a') }} \end{equation}

ここで $\tau$ はボルツマン分布の温度パラメータを示し， $\tau$ が小さい時にはエージェントは探索を行い， $\tau$ が大きいときはグリーディ選択に近くなり，同じ行動を取り続けます．

RDとQ学習の関係

強化学習における大きな課題の1つがマルチエージェント強化学習，すなわち複数の強化学習エージェントに集団の中で適切な行動を学習させることです．マルチエージェント強化学習を困難にしている原因はエージェント間の相互作用です．あるエージェントが受け取る報酬，状態遷移はそのエージェントの行動だけでなく，他のすべてのエージェントの状態，行動によって決定されます．そのため，他のエージェントを適切に考慮した学習，適切な環境構築，パラメータ設定など様々な工夫が必要となります．

この問題に対して，先行研究ではCross Learingの学習結果がRDの帰結に収束することが示されています．つまり，CrossLearingを用いたマルチエージェント強化学習において，その学習結果をRDによって予測できることが示唆されました．

そこで，この論文ではQ学習のダイナミクスを求め，それを実際の学習結果との比較を行っています．この結果が一致すれば，Q学習を用いたマルチエージェント強化学習における，あるパラメータ設定の学習結果を予測することができます．

Q学習のダイナミクスの導出

Q学習のダイナミクスを導出します．ここでは，詳細については割愛させていただくので，知りたい方は論文をご覧ください．

先ほども述べたようにQ学習のエージェントの行動選択はボルツマン選択を採用するため，エージェントのある時刻tにおける行動 $a_i$ の選択確率 $x_i$ は以下になります．

\begin{equation} x_i(t) = \frac{e^{ \tau Q_{a_i}(t)}}{ \sum_{j} e^{ \tau Q_{a_j}(t)}} \end{equation}

この選択確率の変化量は上式を微分して，以下になります．

\begin{equation} \frac{dx_i}{dt} = \frac{d}{dt} \frac{e^{ \tau Q_{a_i}}}{ \sum_{j} e^{ \tau Q_{a_j}}} = \tau x_i [\frac{dQ_{a_i}}{dt} - \sum_j \frac{dQ_{a_j}}{dt}x_j] \tag{5} \end{equation}

次に $\frac{d Q_i(t)}{dt}$ を求めます．ある時刻tにおけるQ値の更新式を考えます．

(4)式から

\begin{equation} Q_{a_i}(t+1) ← Q_{a_i}(t)+ \alpha (r_{a_i}(t+1) + \gamma max_{a_k} Q_{a_k} - Q_{a_i}(t)) \end{equation}

この時Q値の変化量は

\begin{equation} \frac{d Q_{a_i}}{dt} = \alpha (r_{a_i} + \gamma max_{a_k} Q_{a_k} - Q_{a_i}) \tag{6} \end{equation}

この(6)式を用いて，(5)式から

\begin{eqnarray} \frac{dx_i}{dt} =& \tau x_i (\alpha r_{a_i} + \alpha \gamma max_{a_k} Q_{a_k} - \alpha Q_{a_i} - \sum_j x_j \alpha (r_{a_j} + \gamma max_{a_k} Q_{a_k} - Q_{a_j}))　\\ =& \tau \alpha x_i (r_{a_j} + \sum_j x_j r_{a_j} - Q_{a_i} + \sum_j x_j Q_{a_j}) \end{eqnarray}

$\sum_j x_j = 1$ であるから

\begin{eqnarray} \frac{dx_i}{dt} =& \tau \alpha x_i (r_{a_i} + \sum_j x_j r_{a_j} - Q_{a_i} \sum_j x_j + \sum_j x_j Q_{a_j})\\ =& \tau \alpha x_i (r_{a_i} + \sum_j x_j r_{a_j} + \sum_j x_j (Q_{a_j} - Q_{a_i})) \end{eqnarray}

$\frac{x_j}{x_i}$ は $\frac{e^{\tau Q_{a_j} } }{e^{\tau Q_{a_i} } }$ と置き換えられるため

\begin{equation} \frac{dx_i}{dt} = \tau \alpha x_i (r_{a_i} + \sum_j x_j r_{a_j}) + \alpha x_i \sum_j x_j \ln(\frac{x_j}{x_i}) \end{equation}

また $r_{a_i}$ は $\sum_j a_{ij} y_j$ と書き換えることができるため，最終的にQ学習のダイナミクスは以下になります．

\begin{equation} \frac{dx_i}{dt}= x_i \tau \alpha ((A \textbf{y} )_i −\textbf{x} \cdot A \textbf{y}) + x_i \alpha \sum_j x_j \ln(\frac{x_j}{x_i}) \tag{7} \end{equation}

同様にプレイヤ2は

\begin{equation} \frac{dy_i}{dt}= y_i \tau \alpha ((B \textbf{x} )_i −\textbf{y} \cdot B \textbf{x}) + y_i \alpha \sum_j y_j \ln(\frac{y_j}{y_i}) \tag{8} \end{equation}

これらの式は下に示す突然変異付きのレプリーターダイナミクスと非常に似ていることがわかります．

\begin{equation} \frac{dx_i}{dt}= [(A \textbf{x} )_i −\textbf{x} \cdot A \textbf{x} ]x_i + \sum_j \epsilon_{ij}(x_j - x_i ) \tag{10} \end{equation}

数値実験

先ほど導出したQ学習のダイナミクスと実際の学習軌跡，レプリーターダイナミクスとその帰結をそれぞれのクラスの利得表を用いた繰り返しゲームにおいて，比較したいと思います．実験に用いたコードはこちらを確認してください．(詳しいパラメータもこちらを確認してください)

github.com

実験結果

Ｑ学習のダイナミクスと学習軌跡

以下にそれぞれClass 1，2，3の利得表のＱ学習のダイナミクスと実際の学習軌跡を示します．これらのグラフの横軸xはエージェント1が行動1を取る確率，縦軸yはエージェント2が行動1を取る確率です．Ｑ学習のダイナミクスでは，各パラメータ $\tau$ について，ある方策を持つ場合，それぞれのエージェントが行動1を取る確率の変化速度を矢印を用いて示しています．Ｑ学習の学習軌跡は，各パラメータ $\tau$ について，実際に各初期戦略からの学習軌跡を示しています．

これら2つを比較すると，Class 1とClass 2の場合に，Q学習のダイナミクスとエージェントが学習軌跡が一致しています．しかしClass3では $\tau = 1$ ， $\tau = 2$ では概ねQ学習のダイナミクスとエージェントが学習軌跡が一致していますが， $\tau = 10$ 場合に，Ｑ学習のダイナミクスが $(0.5, 0.5)$ を中心に円を描くような速度を示しているのに対して，実際の学習軌跡を見ると外側の角に向かって学習を進めています．またその学習結果，学習の終了地点はClass 3， $\tau = 10$ 以外はＱ学習のダイナミクスにおいて，その平衡点に収束しています．しかし，Class 3， $\tau = 10$ では， $(0.5, 0.5)$ の点ではなく，方策が各純粋戦略に収束しています．

f:id:mitsuki-sakamoto:20201026231402p:plain — Class 1 : Q学習のダイナミクス ( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231406p:plain — Class 1 : Q学習のダイナミクス ( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231414p:plain — Class 1 : Q学習の学習軌跡 ( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231419p:plain — Class 1 : Q学習の学習軌跡 ( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231503p:plain — Class 2 : Q学習のダイナミクス( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231507p:plain — Class 2 : Q学習のダイナミクス( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231517p:plain — Class 2 : Q学習の学習軌跡 ( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231522p:plain — Class 2 : Q学習の学習軌跡 ( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231559p:plain — Class 3 : Q学習のダイナミクス( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231604p:plain — Class 3 : Q学習のダイナミクス( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231613p:plain — Class 3 : Q学習の学習軌跡 ( $\tau$ : 1, 2, 10)

f:id:mitsuki-sakamoto:20201026231617p:plain — Class 3 : Q学習の学習軌跡 ( $\tau$ : 1, 2, 10)

レプリーターダイナミクスとその帰結

以下にそれぞれClass 1，2，3の利得表のレプリーターダイナミクスとその帰結を示します．これらのグラフの横軸xは母集団1の純粋戦略 ${1, 0}$ が人口に占める割合，縦軸yは母集団2の純粋戦略 ${1, 0}$ が人口に占める割合です．レプリーターダイナミクスでは，各パラメータ $\tau$ について，ある戦略分布の場合に，それぞれの集団における純粋戦略 ${1, 0}$ の人口変化速度を矢印を用いて示しています．レプリーターダイナミクスの帰結は，各パラメータ $\tau$ について，実際に各初期戦略分布からその帰結まで軌跡を示しています．

レプリケーターダイナミクスの帰結はそれが示す微分方程式に従い人口を更新を繰り返した結果であるため，これら2つは当然一致します．なのでここではレプリーターダイナミクスとＱ学習のダイナミクスとの比較を行います．Ｑ学習のダイナミクスとレプリーターダイナミクスを比較すると，すべて外形が一致しています．またその平衡点を比べると， $\tau$ が大きい場合と $\epsilon$ が小さい場合に対応が見て取れます．

f:id:mitsuki-sakamoto:20201026231225p:plain — Class 1 : レプリーターダイナミクス ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231446p:plain — Class 1 : レプリーターダイナミクス ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231429p:plain — Class 1 : RDの帰結 ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231433p:plain — Class 1 : RDの帰結 ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231450p:plain — Class 2 : レプリーターダイナミクス( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231531p:plain — Class 2 : RDの帰結 ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231536p:plain — Class 2 : RDの帰結 ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231545p:plain — Class 3 : レプリーターダイナミクス ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231549p:plain — Class 3 : レプリーターダイナミクス ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231627p:plain — Class 3 : RDの帰結 ( $\epsilon$ : 0.01, 0.1, 0.25)

f:id:mitsuki-sakamoto:20201026231631p:plain — Class 3 : RDの帰結 ( $\epsilon$ : 0.01, 0.1, 0.25)

考察

Q学習のダイナミクスとQ学習の学習軌跡について

実験の結果，Class 3， $\tau = 10$ 以外について，Ｑ学習のダイナミクスと学習軌跡が概ね一致していました．一方，Class 3， $\tau = 10$ の場合は大きく異なる結果となりました．しかし，以下に示すように，元の論文ではQ学習のダイナミクスと学習軌跡が一致しています．この原因ついては今後，詳しい考察をしたいと思います．

f:id:mitsuki-sakamoto:20201027020745p:plain — Class 3 Q学習のダイナミクス (論文からの引用)

f:id:mitsuki-sakamoto:20201027020913p:plain — Class 3 Q学習の学習軌跡 (論文からの引用)

Q学習のダイナミクスとRDについて

実験の結果，Q学習のダイナミクスとレプリーターダイナミクスダイナミクスは概ね一致していました．また平衡点に着目すると， $\tau$ と $\epsilon$ に対応があることがわかりました．これは $\tau$ と $\epsilon$ がランダム性を示すパラメータであるためと考えます． $\epsilon$ はレプリーターダイナミクスにおいて突然変異率を示し，この値が大きくなるほどランダム性が大きくなり，戦略分布は多様性を持ちます．また $\tau$ は前述のように，ボルツマン選択における探索のパラメータです． $\tau$ が小さいほど，エージェントはより探索行動を取り，行動のランダム性は大きくなります．このような理由から， $\tau$ が大きい場合と $\epsilon$ が小さい場合に対応が見て取れると考えます．

おわりに

今回は，「Tuyls, K., T Hoen, P. J., & Vanschoenwinkel, B. (2006). An evolutionary dynamical analysis of multi-agent learning in iterated games. Autonomous Agents and Multi-Agent Systems」の要約と，実験結果の再現を行いました．この論文にあるように，Q学習のダイナミクスを求めることで，Ｑ学習の学習軌跡，学習結果を予測することができました．しかし，Class 3の場合にＱ学習のダイナミクスと学習軌跡が一致せず，また論文とも異なる結果となりました．今後はこの原因についての調査や，戦略の次元を拡張しこの手法を適応させてみたいと思います．

2020-11-09

An evolutionary dynamical analysis of multi-agent learning in iterated games の要約・再現実験 (初稿)

はじめに

モデル

まずは，今回論文で用いられているゲーム (環境) について，説明します．

2人2手番標準形ゲームの定義

2人2手番標準形ゲームは，2人のプレイヤ1，プレイヤ2が行動{1, 2}から1つを選択し，2人の選択した行動に対応する利得を獲得するゲームです．プレイヤ1とプレイヤ2の利得は以下の行列 $A$ ， $B$ に従って与えれられます．この行例はプレイヤ1の行動が行にプレイヤ2の行動が列に対応します．例えばプレイヤ1が行動2，プレイヤ2が行動1を選択した場合，プレイヤ1には利得 $P_1$ は $a_{21}$ が，プレイヤ2には利得 $P_2$ は $b_{21}$ が与えられます．

\begin{equation} A =\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{array} \right) \end{equation}

この時，確実に1つの行動を選ぶような戦略 $S_m=(1, 0) , S_m = (0, 1)$ を純粋戦略.それ以外のどちらの行動を選択する可能性のある戦略を混合戦略と呼びます．

また戦略からも各プレイヤの利得を求めることができます，例えば，プレイヤ1の戦略を $S_1＝(x_{11}, x_{12})$ ，プレイヤ2の戦略を $S_2 = (x_{21}, x_{22})$ とすると，それぞれの利得は

\begin{equation}P_1 ＝ x_{11} x_{21} a_{11} + x_{11} x_{22} a_{12} + x_{12} x_{21} a_{21} + x_{12} x_{22} a_{22} \end{equation}

\begin{equation}P_2 ＝ x_{11} x_{21} b_{11} + x_{11} x_{22} b_{12} + x_{12} x_{21} b_{21} + x_{12} x_{22} b_{22} \end{equation}

のようになります．

Class 1~3

この2人2手番標準形ゲームはその利得構造から異なる種類の均衡を形成する3つクラスに分類することができます．

Class 1

利得が以下の条件を満たす時，少なくとも1人のプレイヤは支配的な戦略を持ち，1つの厳格な均衡が存在します． \begin{equation}( (a_{11} - a_{21})(a_{12}-a_{22})>0) \vee ( (b_{11}-b_{12})(b_{21}-b_{22})>0)\end{equation} 支配的な戦略とは，プレイヤが相手の戦略・行動によらず，ある行動を選択するという戦略です．条件式に注目すると， $(a_{11}-a_{21})(a_{12}-a_{22})>0$ が成り立つの以下の場合です．

\begin{equation} ( a_{11}>a_{21} \land a_{12}>a_{22} ) \vee (a_{11} < a_{21} \land a_{12} < a_{22} )\end{equation}

左の場合，相手が1を選択した時プレイヤ1は1行動1を選択する方が良く，また相手が行動2を選択した場合も同様です．右の場合，行動2についてこれが成り立ちます． $(b_{11}-b_{12})(b_{21}-b_{22})>0$ はプレイヤ2について同様の意味を持ちます．

片方のプレイヤが支配的な戦略を持つ時，他方のプレイヤはこの戦略に応じた行動を選択することが最適となります．よってこの時，2人のプレイヤは常に同じ行動を選択し，これを厳格な均衡と呼びます．

Class 2

利得が以下の条件を満たす時，ふたつの純粋戦略均衡と混合戦略均衡が存在します． \begin{eqnarray} ( (a_{11} - a_{21})(a_{12}-a_{22})<0) \land \\ ( (b_{11}-b_{12})(b_{21}-b_{22})<0) \land \\ ( (a_{11}-a_{21})(b_{11}-b_{12}) > 0) \end{eqnarray} 先ほどと同様に，条件に注目するとここでは単純化のために $a_{11}>a_{P_{21}}$ の場合について考えます．この時， \begin{equation} (a_{11} > a_{21}) \land (a_{12} < a_{22}) \land (b_{11} > b_{12}) \land (b_{21} < b_{22}) \end{equation} という関係が成り立ちます．この時，それぞれのプレイヤは相手の行動に対して，適切な反応(行動)が異なります．ここで，プレイヤ1が行動1を固定した場合を考えると，プレイヤ2の最適反応は行動1となります( $b_{11}>b_{12}$ )．プレイヤ2が行動1を取る時，プレイヤ1の最適反応も行動1となります( $a_{11}>a_{12}$ )．よってこれは純粋戦略均衡となります．またプレイヤ1が行動を2に固定した場合もプレイヤ2の最適反応は行動2となり，同様にこれも純粋戦略均衡となります．しかし，前述のようにプレイヤは確率的に行動を選択する混合戦略を持つ場合があります．このような場合，プレイヤ１の戦略 $s_1 = ( \frac{b_{22}-b_{21}}{b_{11}-b_{12}-b_{21}-b_{22}}, \frac{b_{11}-b_{12}}{b_{11}-b_{12}-b_{21}+b_{22}})$ , プレイヤ２の戦略 $s_2 = ( \frac{a_{22}-a_{12}}{a_{11}-a_{12}-a_{21}+a_{22}} \frac{a_{11}-a_{21}}{a_{11}+a_{12}+a_{21}+a_{22}})$ の場合に混合戦略均衡となります．

Class 3

利得が以下の条件を満たす時，1つの混合戦略均衡が存在します． \begin{eqnarray} ( (a_{11}-a_{21})(a_{12}-a_{22}) < 0) \land \\ ( (b_{11}-b_{12})(b_{21}-b_{22})<0) \land \\ ( (a_{11}-a_{21})(b_{11}-b_{12})<0) \end{eqnarray} 先ほどまでと同様に， $a_{11}>a_{21}$ の場合について考えます．この時， \begin{equation} (a_{11} > a_{21}) \land (a_{12} < a_{22}) \land (b_{11} < b_{12}) \land (b_{21} > b_{22}) \end{equation} という関係が成り立ちます．ここでClass2と同様にプレイヤ1の行動1に固定して考えて見ると，プレイヤ2の最適反応は2となります( $b_{11} \gt b_{12}$ )．プレイヤ2が行動2を取る場合，プレイヤ1の最適反応は行動2となります( $a_{21} \gt a_{22}$ )．そしてこの時．．．このように相手の最適反応に対し，現在の行動が最適反応にならないため，この条件下では純粋戦略均衡が存在しません．しかし，Class3もClass2と同様に混合戦略均衡が存在します．

本稿で使う具体的なゲーム

本稿では先ほど紹介した3つのクラスに分類されるゲームを用いて実験を行います．

class 1 囚人のジレンマ

Class1に当てはまるのは以下のような利得表です．

\begin{equation} A =\left( \begin{array}{cc} 1 & 5 \\ 0 & 3 \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} 1 & 0 \\ 5 & 3 \\ \end{array} \right) \end{equation}

このゲームでは，プレイヤ1，2はそれぞれ相手の行動に関わらず，行動1を選択することが支配戦略となり，厳格な均衡が存在します．この時，プレイヤの利得は $P_1=1$ , $P_2=1$ となります．もしプレイヤ1，2ともに行動2を選択した場合，利得は $P_1=3$ ， $P_2=3$ となり，2人のプレイヤがより多くの利得を得ていることができます．しかし，相手が行動2を選択しているとき，行動1を選択すれば，相手は利得を得ることができなくなりますが，自分は現在の利得よりも大きな利得を得ることができます．なので，両プレイヤは結局行動1を選択することになります．このように合理的な行動選択が全体の望ましい結果にならないものを，囚人の黙秘や自白に例えて「囚人のジレンマ」と呼びます．

class 2 両性の争い

Class2に当てはまるのは以下のような利得表です．

\begin{equation} A =\left( \begin{array}{cc} 2 & 0 \\ 0 & 1 \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \\ \end{array} \right) \end{equation}

\begin{equation} S_1=( \frac{2-0}{2-0-0+1}, \frac{1-0}{2-0-0+1}) =(\frac{2}{3}, \frac{1}{3}) \end{equation}

\begin{equation} S_2=( \frac{1-0}{1-0-0+2}, \frac{2-0}{1-0-0+2}) =(\frac{1}{3}, \frac{2}{3}) \end{equation}

となります．試しに片方の戦略を純粋戦略に置き換えてみると，利得は改善せずこれが均衡になっていることがわかります．

class 3 唯一の混合戦略均衡

Class3に当てはまるのは以下のような利得表です．

\begin{equation} A =\left( \begin{array}{cc} 2 & 3 \\ 4 & 1 \\ \end{array} \right) \end{equation}

\begin{equation} B =\left( \begin{array}{cc} 3 & 2 \\ 1 & 4 \\ \end{array} \right) \end{equation}

このゲームでは純粋戦略均衡は存在しません．例えば，プレイヤ1が行動1を選択するとわかっている場合，プレイヤ2は行動1を選択し，プレイヤはそれぞれ利得 $P_1=2$ , $P_2=3$ を受け取ります．しかし，プレイヤ1がプレイヤ2が行動1を選択するとわかっている場合，行動2を選択することが最適反応となるため，プレイヤ1は行動2を選択します．全ての純粋戦略の組み合わせで，均等となるような純粋戦略は存在しないことがわかります．しかし混合戦略均衡は存在し，均衡は

\begin{equation} S_1=( \frac{4-2}{3-2-1+4},\ \frac{3-1}{3-1-2+4})=(\frac{1}{2}, \frac{1}{2}) \end{equation}

\begin{equation} S_2=( \frac{1-3}{2-3-4+1},\ \frac{2-4}{2-3-4+1})=(\frac{1}{2}, \frac{1}{2}) \end{equation}

となります.この場合もclass 2と同様に，片方の戦略を純粋戦略に置き換えてみると，利得は改善せずこれが均衡になっていることがわかります．

ナッシュ均衡とパレート効率性

ゲーム理論における一般的なゲームに置いては，ナッシュ均衡と呼ばれるものが実現すると考えられています．これはどのような戦略をとれば良いかというゲーム理論の問いに対する解の1つで，これまで分析した均衡は全てナッシュ均衡に含まれます．ナッシュ均衡は以下のように定義されます．

2人のプレイヤが戦略 $s=(s_i,s_j)$ に従ってプレイする時，もし $P_1(s_i,s_j) \ge P(s_x, s_j) \forall x \in {1,...,n} \land P_1(s_i, s_j) \ge P(s_i, s_x)\ \forall x \in {1,...,n}$ であれば戦略sはナッシュ均衡である．

これはどちらか一方のプレイヤが戦略を変えても得をしないことを意味します．つまりナッシュ均衡では各プレイヤの戦略がお互いに最適反応になっているということです．

またもう１つパレート効率性という概念を紹介します．ゲームにおいて，他のプレイヤが損をしなければ，利得が改善できない状態のことをパレート効率的であると言います．これは以下のように定義されます．

戦略の組み合わせ， $s$ が存在し，もし全てのプレイヤが最低でも同じ利得，1人以上のプレイヤが今よりも大きな利得を受け取る $s'$ が存在しなければsはパレート効率的である．

これらの「ナッシュ均衡」と「パレート効率性」を用いると，囚人のジレンマはナッシュ均衡がパレート効率的でない場合と考えることができます．先ほどの「囚人のジレンマ」の例でナッシュ近郊に従う利得は $P_1=1$ ， $P_2=1$ でありますが，両プレイヤが行動2を選択すると，利得は $P_1=3$ ， $P_2=3$ です．このように両プレイヤの利得が増加しているため，これはパレート効率的ではありません．

進化ゲームと人口ゲーム

進化ゲームとは，生物の進化の概念に着想を得た，ゲーム理論における戦略の分析方法です．これまで，ゲーム理論では，ナッシュ均衡の概念を用いて様々な分析が行われてきました．しかし，ナッシュ均衡だけではtrimbling hand (震える手) などの，より現実を反映したゲームでは均衡を適切に予測することができませんでした．

そこで，生物の進化の過程における，選択（淘汰）と突然変異の概念を利用することで，戦略分析を動学的なモデルとして扱う進化ゲームが提案されました．進化ゲームでは戦略を生物の種に置き換えることで，その環境において生き残る種，つまりそのゲームにおいて有効な戦略を導きます．生物は選択（淘汰）と突然変異を繰り返すことで進化を遂げて来ました．淘汰されるかどうかはその環境に適応できたかどうかによって決まり，また適応できるかどうかは環境だけでなく人口分布によっても決定されます．また一定の確率で突然変異することで，その多様性を保ってきました．

これをゲームに置き換えて考えてみましょう．ある環境にははじめ，異なる戦略を持つ複数の種のプレイヤが存在します．全体の人口は変わることがないため，ある種のプレイヤは自分と同じ戦略を持つものまた異なる戦略と実際にゲームをプレイした結果，利得の大小によって，その人口を変化させます．つまりゲーム・人口分布において，有利な戦略は人口を増やし，不利な戦略は人口を減らします．また淘汰だけではなく，ある一定の突然変異確率に従って，その人口を増減させます．これを繰り返すことで最終的には，ある１つの戦略または複数の戦略が共存する形で人口変化は収束し，生き残った戦略がそのゲームにおいて有効な戦略だということができます．これが進化ゲームにおける有効な戦略分析の考え方です．

ESSの定義

次に進化ゲームにおける均衡の定義，ESS (Evolutionary Stable Strategies)：進化的に安定な戦略について説明します．進化的に安定な戦略とは，突然変異戦略の進化圧力に対してロバストな戦略のことを指します．例えば，同じ戦略を持つプレイヤの集団を考えます．この集団の中で．ある一定の割合が突然変異戦略を持ち，元の集団を侵攻し始めます．もし新しい戦略の成長率が元の戦略よりも小さい場合，やがてその戦略は消滅します．この時，元の戦略は進化的に安定しているということが言えます．

次にESSの定義について説明します．人口の大部分を占める戦略ｓ，突然変異戦略をs'とし，s'の割合をεとします．この時，ある1体のプレイヤがランダムで選ばれたプレイヤと対戦するとき，s'と対戦する確率はε，sと対戦する確率は1-εになります．この確率を用いて，各プレイヤの利得は以下のように求めることができます．戦略sを持つプレイヤ

\begin{equation} P(s,(1-\epsilon )s + \epsilon s')\ i.e. (1-\epsilon )P(s,s) + \epsilon P(s, s') \end{equation}

戦略s'を持つプレイヤ

\begin{equation} P(s',(1-\epsilon )s + \epsilon s')\ i.e. (1-\epsilon )P(s',s) + \epsilon P(s', s') \end{equation}

この利得からESSは次のように定義することができます．もし任意の戦略 $s' \neq s$ について， $0 \lt \epsilon \lt \delta$ における任意の $\epsilon$ が $(1-\epsilon )P(s,s) + \epsilon P(s, s') > (1-\epsilon )P(s',s) + \epsilon P(s', s')$ を満たすような $\delta \in [0,1$ ]が存在するとき，戦略sはESSである．

ナッシュ均衡とESSの関係

次にESSとナッシュ均衡の関係について説明します．これまでの研究によって，特定のゲームにおいてナッシュ均衡がESSを包含していることが明らかになっています．これはESSの条件がナッシュ均衡よりも厳しいからです．まずナッシュ均衡は定義から他のプレイヤ戦略に対しての最適反応です．反対にもし戦略sがESSであれば，sは他の戦略だけでなく，s自身に対しても最適反応である必要があります．もしそうでなければ，そこにはsよりもsに対して有効な戦略s'が存在し，s'の突然変異確率が十分に大きいとき，sは進化的に安定ではありません．このような理由からナッシュ均衡はESSを包含します．

レプリケータダイナミクス

ここでは実際に数式を用いて，戦略分析する手法ReplicatorDynamics（RD）について説明します． RDは戦略分布における，人口の変化の期待値の近似値のことをさし，以下のようの微分方程式に定式化されます．この微分方程式を解くことで，進化ゲームにおける戦略人口の変化の流れを知ることができます．（ここでは淘汰の概念のみを用いていますが，特に突然変異を用いるレプリケータダイナミクスを突然変異付きレプリケータダイナミクスと呼びます．）

\begin{equation} \frac{dx_i}{dt}= [(A \textbf{x} )_i −\textbf{x} \cdot A \textbf{x} ]x_i \tag{1} \end{equation}

$x_i$ は戦略 $s_i$ の人口（母集団）中の割合， $A$ は利得行列で $(A \textbf{x} )_i$ は戦略 $s_i$ の平均利得， $\textbf{x} \cdot A \textbf{x}$ は母集団全体の平均利得を指します．ここで母集団全体を示すxは各戦略のベクトルとして表現されます． $\textbf{x}={x1,x2,x3,...}$ .また $x_i$ の成長率， $\frac{dx}{dt}/xi$ は母集団全体の平均利得とその戦略の平均利得の差に等しくなります．

上では母集団が1つしかない場合を考えましたが，母集団が2つある場合もRDを求めることができます．これらは進化的非対称ゲームと呼ばれます．これらは以下のように定義されます．

\begin{equation} \frac{dp_i}{dt}= [(A \textbf{q} )_i −\textbf{p} \cdot A \textbf{q} ]p_i \tag{2} \end{equation}

\begin{equation} \frac{d q_i}{dt}= [(B \textbf{p} )_i −\textbf{q} \cdot B \textbf{p} ]q_i \tag{3} \end{equation}

$p_i$ ， $q_i$ はそれぞれの母集団における戦略 $s_i$ の割合を指します(あくまで添字なので，母集団1の $s_i$ と母集団2の $s_i$ は同一であるとは限らない)． $(A \textbf{q} )_i$ ， $(B \textbf{p} )_i$ はそれぞれsiの平均利得を， $\textbf{p} \cdot A \textbf{q}$ ， $\textbf{q} \cdot B \textbf{p}$ は母集団の平均利得を示します.(ここでは $\textbf{p}$ ， $\textbf{q}$ の違いに注意してください)．またここで，母集団はそれぞれ異なる利得行列 $A$ ， $B$ を用いていることに注意してください．(また $A = B^t$ である場合，(2) (3) 式は(1)と一致します)

ナッシュ均衡，ESS，RDの関係

では，次にこれまで紹介した3つの概念，ナッシュ均衡，ESS，RDの関係について説明します．従来研究によってRDが漸近的に安定であれば，それはナッシュ均衡であり，ESSであることが示されています．RDは微分方程式で表されるため，そこには平衡点が存在します．RDにおいて以下の条件を満たすとき，漸近的に安定であると言えます．（正式な定義については省略します）

均衡に十分近いRDの解の経路が任意に近いままであるとき(この条件をリアプノフ安定性と呼ぶ)
均衡の十分近い点から始まるRDの解の経路が均衡に収束するとき

強化学習

ゲーム → 環境
戦略 → 方策
利得 → 報酬
プレイヤ → エージェント

強化学習の一般的な定義

まずは強化学習の一般的な定義について説明します．強化学習はエージェントと環境によって構築されます．環境は状態集合 $s \in S$ を持ち，現在の状態sを持ち，エージェントの行動 $a \in A$ と遷移関数 $T(s, a) = s'$ によって状態を遷移させます．また状態遷移に応じて環境は報酬値 $R$ をエージェントに与えます．エージェントは環境から状態sを観察し，行動aを決定します．この時エージェントは方策 $\pi(s) (\sum_{a'} \pi(s,a') = 1)$ と呼ばれる行動選択戦略に従い, 行動を決定します．またエージェントは行動によって環境から得た報酬をもとに方策を更新します．これは以下のような流れで行われます．

エージェントが環境から状態を観測する．
エージェントは状態と自身の方策から行動を決定し，それを実行する(環境に出力する)．
環境は状態と行動に従い，状態を遷移させ，報酬をエージェントに与える．
エージェントは環境から得た報酬をもとに方策を更新する．

Q学習

\begin{equation} Q_{t+1}(s, a) ← (1−\alpha)Q_t (s, a)+ \alpha (r + \gamma max_a' Qt (s', a')) \tag{4} \end{equation}

ここで， $\alpha \in [0,1$ ] は学習率を示し，一度の経験をどれだけ重視するというパラメータです．この学習率が大きいほど，１度の更新量が大きくなります． $\gamma \in [0,1$ ] は割引率で未来に得られる報酬の重要性を示します．この割引率が大きいほど，未来の報酬を重視するようになります．このQ値の繰り返し推定していくことで，エージェントは方策を学習します．

Q学習における戦略

\begin{equation} \pi(s, a) = \begin{cases} 1 & (a = argmax_{a'} Q(s, a')) \\ 0 & (othrewise) \end{cases} \end{equation}

$\epsilon$ グリーディ選択は，確率 $\epsilon$ でランダムな行動を選択し，それ以外はグリーディ選択に従う選択方法です．この $\epsilon$ によって，エージェントは適切な行動を探索できるようになります．また本稿ではボルツマン選択が採用されています． ボルツマン選択ではボルツマン分布に従って行動が選択され，それぞれの選択確率は以下のように定義されます．

\begin{equation} \pi(s,a) = \frac{e^{ \tau Q(s, a)}}{ \sum_{a'} e^{ \tau Q(s, a') }} \end{equation}

ここで $\tau$ はボルツマン分布の温度パラメータを示し， $\tau$ が小さい時には探索を行い， $\tau$ が大きいときはグリーディ選択に近くなります．

RDとQ学習の関係

強化学習における大きな課題の1つがマルチエージェント強化学習，複数の強化学習エージェントに集団の中で適切な行動を学習させることです．マルチエージェント強化学習を困難にしている原因がエージェント間の相互作用です．あるエージェントが受け取る報酬，状態遷移はそのエージェントの行動だけでなく，他のすべてのエージェントの行動によって決定されます．そのため，他のエージェントを適切に考慮した学習，適切な環境構築，パラメータ設定など様々な工夫が必要となります．

この問題に対して，先行研究ではCrossLearingの学習結果がRDに収束することが示されています．つまり，CrossLearingを用いたマルチエージェント強化学習において，その学習結果(帰結)をRDによって予測できることが示唆されました．

Q学習のダイナミクスの導出

Q学習のダイナミクスを導出します．ここでは，詳細については割愛させていただくので，知りたい方は論文をご覧ください．

先ほども述べたようにQ学習のエージェントの行動選択はボルツマン選択を採用するため，エージェントのある時刻tにおける行動 $a_i$ の選択確率 $x_i$ は以下のようになります．

\begin{equation} x_i(t) = \frac{e^{ \tau Q_{a_i}(t)}}{ \sum_{j} e^{ \tau Q_{a_j}(t)}} \end{equation}

この選択確率の変化量は上式を微分して，以下になります．

\begin{equation} \frac{dx_i}{dt} = \frac{d}{dt} \frac{e^{ \tau Q_{a_i}}}{ \sum_{j} e^{ \tau Q_{a_j}}} = \tau x_i [\frac{dQ_{a_i}}{dt} - \sum_j \frac{dQ_{a_j}}{dt}x_j] \tag{5} \end{equation}

次に $\frac{d Q_i(t)}{dt}$ を求めます．ある時刻tにおけるQ値の更新式を考えます．

(4)式から

\begin{equation} Q_{a_i}(t+1) ← Q_{a_i}(t)+ \alpha (r_{a_i}(t+1) + \gamma max_{a_k} Q_{a_k} - Q_{a_i}(t)) \end{equation}

この時Q値の変化量は

\begin{equation} \frac{d Q_{a_i}}{dt} = \alpha (r_{a_i} + \gamma max_{a_k} Q_{a_k} - Q_{a_i}) \tag{6} \end{equation}

この(6)式を用いて，(5)式から

$\sum_j x_j = 1$ であるから

$\frac{x_j}{x_i}$ は[tex:\frac{e^{\tau Q_{a_j}}}{e^{\tau Q_{a_i}}}]と置き換えられるため

\begin{equation} \frac{dx_i}{dt} = \tau \alpha x_i (r_{a_i} + \sum_j x_j r_{a_j}) + \alpha x_i \sum_j x_j \ln(\frac{x_j}{x_i}) \end{equation}

$r_{a_i}$ は $\sum_j a_{ij} y_j$ と書き換えることができるため，最終的にQ学習のダイナミクスは以下のようになります．

\begin{equation} \frac{dx_i}{dt}= x_i \tau \alpha ((A \textbf{y} )_i −\textbf{x} \cdot A \textbf{y}) + x_i \alpha \sum_j x_j \ln(\frac{x_j}{x_i}) \tag{7} \end{equation}

またプレイヤ2は

\begin{equation} \frac{dy_i}{dt}= y_i \tau \alpha ((B \textbf{x} )_i −\textbf{y} \cdot B \textbf{x}) + y_i \alpha \sum_j y_j \ln(\frac{y_j}{y_i}) \tag{8} \end{equation}

これらの式は下に示す突然変異付きのレプリーターダイナミクスと非常に似ていることがわかります．

\begin{equation} \frac{dx_i}{dt}= [(A \textbf{x} )_i −\textbf{x} \cdot A \textbf{x} ]x_i + \sum_j \epsilon_{ij}(x_j - x_i ) \tag{10} \end{equation}

数値実験

github.com

実験結果

Ｑ学習のダイナミクスと学習軌跡

以下にそれぞれClass 1，2，3の利得表を用いて行いました．Ｑ学習のダイナミクスと実際の学習軌跡を示します．これらのグラフの横軸xはエージェント1が行動1を取る確率，縦軸yはエージェント2が行動1を取る確率です．Ｑ学習のダイナミクスでは，各パラメータ $\tau$ について，ある方策を持つ場合，それぞれのエージェントが行動1を取る確率の変化速度を矢印を用いて示しています．Ｑ学習の学習軌跡は，各パラメータ $\tau$ について，実際に各初期戦略からの学習軌跡を示しています．

レプリーターダイナミクスとその帰結

以下に囚人のジレンマの利得表を用いて行いました．レプリーターダイナミクスとその帰結を示します．これらのグラフの横軸xは母集団1の純粋戦略 ${1, 0}$ が人口に占める割合，縦軸yは母集団2の純粋戦略 ${1, 0}$ が人口に占める割合です．レプリーターダイナミクスでは，各パラメータ $\tau$ について，ある戦略分布の場合に，それぞれの集団における純粋戦略 ${1, 0}$ の人口変化速度を矢印を用いて示しています．レプリーターダイナミクスの帰結は，各パラメータ $\tau$ について，実際に各初期戦略分布からその帰結まで軌跡を示しています．

レプリケーターダイナミクスの帰結はレプリーターダイナミクスに従い人口を更新を繰り返した結果であるため，これら2つは当然一致します．ここではレプリーターダイナミクスとＱ学習のダイナミクスとの比較を行います．Ｑ学習のダイナミクスとレプリーターダイナミクスを比較すると，すべて概ね一致しています．またその平衡点を比べると， $\tau$ が大きい場合と $\epsilon$ が小さい場合に対応が見て取れます．

考察

Q学習のダイナミクスとQ学習の学習軌跡について

Q学習のダイナミクスとRDについて

おわりに

今回は，「Tuyls, K., T Hoen, P. J., & Vanschoenwinkel, B. (2006). An evolutionary dynamical analysis of multi-agent learning in iterated games. Autonomous Agents and Multi-Agent Systems」の要約と，実験結果の再現を行いました．この論文にあるように，Q学習のダイナミクスを求めることで，Ｑ学習の学習軌跡，学習結果を予測することができました．しかし，Class 3の場合にＱ学習のダイナミクスと学習軌跡が一致せず，また論文とも異なる結果となりました．今後はこの原因についての調査をや，戦略の次元を拡張しこの手法を適応させてみたいと思います．

2020-11-06

2020年研究室紹介予定

岩崎研究室の研究紹介予定です．

https://sites.google.com/site/a2ciwasaki/

原則としてオンラインで行います．

在来生研修会
- 11月6日１８：００～２０：００
- URLは在来生研修の案内を見てください．
- 使用したスライドはこちら

www.slideshare.net

* 公開ゼミのURLも来て頂ければお伝えします．

公開ゼミ
- ゼミ終了後３０分程度，在学生を交えて雑談します．
- １１月１１日１３：３０～１５：００，内容はゲーム理論です．
- １１月１９日１４：４０～１６：００，内容はデータ分析です．
- URLはatsushi.iwasaki@uec.ac.jpまでお問い合わせください．
調布祭（１１月２１，~~２２日~~）
- ２１日~~両日とも~~１５：３０～１６：００で紹介と雑談をします．
- URLはatsushi.iwasaki@uec.ac.jpまでお問い合わせください．
- ２２日は諸事情で中止になりました．個別に面談を希望する方はご連絡ください．