今回はマルチエージェント強化学習においての学習の目標となるナッシュ均衡について紹介しようと思います。
ナッシュ均衡
まずナッシュ均衡を数式で表現すると、以下のようになります。
$$
\begin{eqnarray}
Q_i(\pi_i^{\ast}, \pi_{-i}^{\ast}) \geq Q_i(\pi_i^{-}, \pi_{-i}^{\ast}) | \forall i
\end{eqnarray}
$$
\begin{eqnarray}
Q_i(\pi_i^{\ast}, \pi_{-i}^{\ast}) \geq Q_i(\pi_i^{-}, \pi_{-i}^{\ast}) | \forall i
\end{eqnarray}
$$
この式は、 「エージェント$i$以外のエージェント群$-i$がナッシュ均衡戦略$\pi_{-i}^{\ast}$の時、 エージェント$i$もナッシュ均衡戦略$\pi_i^{\ast}$を選択した時に最も高い報酬を得ることができる」 ということが全エージェント$ \forall i$に当てはまることを表現しています。
つまり、ナッシュ均衡状態の時には、どのエージェントもナッシュ均衡戦略以外の戦略を選択した時には 損をしてまうので、現在の戦略を変更するインセンティブをもたない状態となります。
ナッシュ均衡状態に収束してしまえば、全エージェントがgreedy選択をしていれば、戦略は変化しないので、システムが安定していることになります。 そのため、マルチエージェント強化学習では各アルゴリズムがナッシュ均衡戦略に収束するかどうか が重要な評価項目とされています。
ナッシュ均衡の問題点
しかしながら、ナッシュ均衡は完璧な状態であるとは限りません。
ナッシュ均衡戦略は複数存在することがあり、どのナッシュ均衡が良いかを判断しなければならないことや、
ナッシュ均衡戦略は全エージェントの報酬和を最大化(全体最適状態)するものではない可能性があるということです。
有名な例で言えば、囚人のジレンマ問題です。
囚人のジレンマではナッシュ均衡は全エージェントにとって最悪な状態となります。
コメント