【マルチエージェント強化学習、分散型強化学習】Distributed Q Learning

今回は協調型のマルチエージェント強化学習アルゴリズムであるDistributed Q Learning を紹介します。

背景

協調型のマルチエージェント強化学習では、いかに各エージェントが協調して、 全エージェントの獲得報酬を最大化することが重要になります。
同じ目的のために、複数の機械が同時に強化学習を行う問題であれば、必ず必要になります。

ちなみに協調型のタスクですので全エージェントの報酬は同値になります。

$$
\begin{aligned}
R_1 = \cdots = R_m = R
\end{aligned}
$$

\(R_i\) はエージェント\(i\)の報酬関数になります。

マルチエージェント強化学習では、各エージェントが単純にQ Learningなどを行う(ILsという)だけでは 学習が収束しないことがしられています。
そこで、今回の紹介するDistributed Q Learningが提案されました。

Distributed Q Learning

Distributed Q Learning は協調型のマルチエージェント強化学習アルゴリズムの1つです。
名前の通り、分散型のQ Learningになります。
この手法の基本的なコンセプトとしては、全エージェントが最大のQ値の更新値\(r+max Q(s')\)を観測したらQ値を更新していくといった、楽観的に学習していく手法です。
つまり、一度高い報酬を得れる行動を見つけたらその行動を信じて、以後も同じ行動を行うといったアルゴリズムになります。

アルゴリズムは以下のようになります。

f:id:ttt242242:20190709082734j:plain

出典:[PDF] Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems - Semantic Scholar

上記のアルゴリズムの「optimistic update」のところで、先程述べたような更新値\(r+max Q(s')\)を観測したらQ値を更新していく部分になります。
次の「equilibria selection」のところで、今の方策\(\pi\)が最大のQ値の行動選択確率が最大でなければ、その行動選択確率を1とします。(つまり、その行動を必ず行うように)

この手法は決定論的なMarkov Game(例:かならず上記の利得表通りに報酬を得られる環境 )で最適方策を学習できることが証明されています。
(詳細は参考文献1を参考にしていただければと思います)

しかしながら、この手法は確率的に報酬が変化するようなな環境には適切に学習できません
先程述べたように、一度高い報酬を得られた行動を取り続けてしまいます。なので、たまたま高い報酬得られてしまった場合にも完全に信じてしまう問題があるためです。

具体例

以下のような利得表を用いてどのように動作するか見てみます。

1,2 A B
A 10 -2
B -2 0

まず両エージェントがBを選択した場合、お互いの獲得報酬は0です。なので、\(Q_1(B),Q_2(B)\)は0となります。
次にエージェント1がA、エージェント2がBを選択した場合、お互いの獲得報酬は-2ですので、エージェント1の\(Q_1(A)=-2\)、エージェント2の\(Q_2(B)\)はこれまでの最大値を更新しなかったため、0のままです。
そして、探索などで、お互いにAを選択した場合には、獲得報酬は10になり、これまでの最大値を超えます。 お互いのQ値は\(Q_1(A)=10,Q_2(A)=10\)となります。
この利得表をみると報酬が10以上の選択はないので、この後に\(Q\)は変化せず、お互いに最適な選択\(A\)を取り続けることがわかります。

実験

問題設定

今回の実験では、
Climbing gameといったMatrix Gameを用います。
協調型のマルチエージェントゲームですので、すべてのエージェントの報酬は同値となります。
Climbing Gameは以下のような利得表になります。

1,2 A B C
A 11 -30 -30
B -30 7 6
C 0 0 5

最適な行動戦略の組み合わせは(A, A)になります。

プログラム

githubにあげました。

tocom242242/distributed_q_learning
Contribute to tocom242242/distributed_q_learning development by creating an account on GitHub.

プログラムの構成は以下のようになります。

run.pyを実行すると実験を開始します。

distributed_q_learner.py

learnメソッドがdistributed-qのアルゴリズムの部分が記述してあります。 基本的にアルゴリズム通りに実装しています。

matrix_game.py

Climbing gameが実装されています。

policy.py

Epsilon-greedy行動選択が実装されています。

run.py

実験実行用プログラムです。
最後に平均報酬をプロットします。

実験結果

f:id:ttt242242:20190709083428j:plain

獲得報酬の移動平均をプロットしました。
利得表からわかるように正しく学習できていれば、 11周辺にプロットされるのですが、 学習が進むにつれて11周辺にプロットされていることがわかります。

参考文献

  1. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.772
  2. [PDF] Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems - Semantic Scholar

コメント

  1. […] Distributed Q Learning〈協〉 […]

タイトルとURLをコピーしました