強化学習、マルチエージェント強化学習、その他機械学習全般

機械学習関連のことをまとめていきます。強化学習関連が多いかもしれません

トップページ

強化学習

マルチエージェント強化学習

ライブラリ

参考文献

これからの強化学習

これからの強化学習

  • 作者: 牧野貴樹,澁谷長史,白川真一,浅田稔,麻生英樹,荒井幸代,飯間等,伊藤真,大倉和博,黒江康明,杉本徳和,坪井祐太,銅谷賢治,前田新一,松井藤五郎,南泰浩,宮崎和光,目黒豊美,森村哲郎,森本淳,保田俊行,吉本潤一郎
  • 出版社/メーカー: 森北出版
  • 発売日: 2016/10/27
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログ (3件) を見る

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る

【マルチエージェント強化学習】Joint Action Learners

今回はJoint Action Learners(JAL)と呼ばれるマルチエージェント強化学習手法を紹介します。

Joint Action Learners

JALはマルチエージェント強化学習の手法の中でも非常にシンプルなものになります。
Joint Actionとある通り、各エージェントはすべてのエージェントの行動を観測できます。
期待報酬値は$Q(\vec{a})$といったようにすべてエージェントの行動を用います。
つまり以下のようになります。
$$ \begin{eqnarray} Q_i(\vec{a}) \leftarrow Q_i(\vec{a}) + \alpha (r_i - Q_i(\vec{a})) \end{eqnarray} $$

ちなみに$\vec{a}=\{ a_0,\cdots, a_N \}$といったように全エージェントのベクトルとなります。

各エージェントは自分以外のエージェントの方策を過去の経験から推定します。
推定自体はシンプルで、エージェント$i$がエージェント$j$の方策$\hat{\pi}_j(a)$を推定する場合には以下のように推定します。

$$ \begin{eqnarray} \hat{\pi}_j(a_j) = \frac{n(a_j)}{T} \end{eqnarray} $$ ここで、$n(a_j)$はエージェント$j$が行動$a_j$を選択した回数、
$T$は総行動回数を表しています。
単純に$a_j$の選択確率で方策を推定しています。

そして、各エージェントは、相手の推定方策と期待報酬値を用いて、 行動選択に用いる値$EV$を以下のように計算します。
今回は簡略化するためにエージェントが$i, j$の2体の問題とします。

$$ \begin{eqnarray} EV(a_i) = \sum_{a_j \in A_j}\hat{\pi}_j(a_j) Q(a_i, a_j) \end{eqnarray} $$

各エージェントは、この$EV$を用いて行動選択を行います。
(例、$\epsilon -greedy$で言えば、$\epsilon$の確率でランダム、それ以外の場合$a = arg max_{a_i} EV_i(a_i)$の行動を行います。)

実験

今回以下のようなゼロサムゲームを用いて実験を行います。

1,2 A B
A 1, -1 -1,1
B -1,1 1,-1

各エージェントはAかBどちらか行動を選択し、
選択された行動に応じて報酬が得られます。

この問題では両エージェントの各行動の選択確率が0.5になった時がナッシュ均衡になります。
つまり、AとBをだいたい交互に出すような時にナッシュ均衡になります。

ソースコード

ソースコードgithubにあげました。

GitHub - tocom242242/joint_action_learners_sample

ファイル構成は以下のようになります。

├── README.md
├── jal.py  # Joint Action Learner
├── policy
├── run.py  # 実験実行用ディレクトリ
└── simple_game.py # ゲームクラス

run.pyを実行すれば実験を行えます。

実験結果

f:id:ttt242242:20190620053748j:plain

上記のグラフは横軸がエピソード、
縦軸は各エージェントの2つの行動の選択優位度の差の絶対値$|EV(a_1)-EV(a_2)$|となります。
つまり、この値が0に近づく程、行動$a_1 , a_2$の選択確率が0.5ずつとなり、ナッシュ均衡となります。

グラフから両エージェントの$|EV(a_1)-EV(a_2)$が0に近づているため、ゼロサムゲームではナッシュ均衡に収束していそうです。

今後

今後はJALゼロサムゲーム以外でも実験してみます。

参考文献

https://www.aaai.org/Papers/AAAI/1998/AAAI98-106.pdf

http://www.cs.utexas.edu/~larg/ijcai17_tutorial/multiagent_learning.pdf

強化学習 (機械学習プロフェッショナルシリーズ)

強化学習 (機械学習プロフェッショナルシリーズ)

トップページ

強化学習

マルチエージェント強化学習

ライブラリ

参考文献

これからの強化学習

これからの強化学習

  • 作者: 牧野貴樹,澁谷長史,白川真一,浅田稔,麻生英樹,荒井幸代,飯間等,伊藤真,大倉和博,黒江康明,杉本徳和,坪井祐太,銅谷賢治,前田新一,松井藤五郎,南泰浩,宮崎和光,目黒豊美,森村哲郎,森本淳,保田俊行,吉本潤一郎
  • 出版社/メーカー: 森北出版
  • 発売日: 2016/10/27
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログ (3件) を見る

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る

【強化学習】学習率、ステップサイズパラメータ

今回は学習率について、お話します。
強化学習では学習率をステップサイズパラメータとも言います。
このパラメータは記号で言えば $\alpha$で表記します。

この学習率は
更新量を現在にQ値にどれだけ反映させるか
を決定するパラメータになります。

Q学習の更新式を例に学習率の役割を具体的見てみます。 以下の式がQ学習の更新式になります。

$$ Q(s,a) \leftarrow \underbrace{Q(s,a)}_{元のQ値} + \color{red}{\alpha}\underbrace{(r + \gamma \max_{a' \in A}Q(s',a')-Q(s,a))}_{更新量} $$

見てわかる通り、学習率$\alpha$が更新量であるTD誤差$r + \gamma \max_{a' \in A}Q(s',a')-Q(s,a)$をどれだけ現在のQ値$Q(s,a)$に影響させるかを決定しています。

学習率は$0 \leq \alpha \leq 1$の範囲の値になります。
学習率が0であれば、Q値値をまったく更新しませんし、
1であれば、TD誤差をQ値にすべて反映します。

一般的には学習率は学習初期を高い値に設定して、
学習が進むにつれて減少させていきます。
(厳密的に言えば、解が存在し、静的な問題あれば)

参考文献

強化学習 (機械学習プロフェッショナルシリーズ)

強化学習 (機械学習プロフェッショナルシリーズ)

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る

【強化学習、Reward Shaping】Potential-based reward shapingの特徴(Potential-Based Shaping and Q-Value Initialization are Equivalent)

今回は、Potential-Based Reward Shaping(PBRS)の面白い特徴についてお話しようと思います。

Potential-Based Reward Shapingとは

Reward Shaping手法の1つで、通常の環境からの報酬$r$にある値$F(s, s')=\gamma \phi(s')-\phi(s)$を加えて、学習を高速化させることを目指した手法です。

$$ \begin{eqnarray} r_{shaped} &=& r + F(s, s') \\ &=& r + \gamma \phi(s')-\phi(s)$ \end{eqnarray} $$

$\phi(s)$はポテンシャル関数と呼ばれ、この関数をいかに設定するかが、
学習を高速化させるために重要になります。
詳しくは以下の記事にまとめました。

www.tcom242242.net

Potential-Based Shaping and Q-Value Initialization are Equivalent

では、本題に入ります。
論文「Potential-Based Shaping and Q-Value Initialization are Equivalent」において、PBRSの重要な特徴が述べられています。
それが、

「同じ経験で学習する場合、通常のPBRSによって学習するエージェント1と、
初期のQ値に$\phi(s)$を加え通常の報酬で学習を行うエージェント2の Q値は同値になる」

という性質です。

もう少し具体的に見てみます。
ここでは、エージェント1、エージェント2を用意します。
エージェント1のQ値の初期の値は$Q^1(s, a)=Q_0(s, a)$とし、
エージェント2のQ値の初期の値は$Q^2(s, a)=Q_0(s, a)+\phi(s)$ とします。

エージェント1は通常のPBRSで学習するエージェントなので、以下の式でQ値を更新します。 $$ \begin{eqnarray} Q^1(s, a) \leftarrow Q^1(s, a) + \alpha (r+\gamma \phi(s')-\phi(s) + \gamma max _{a'}Q^1(s', a')-Q^1(s, a)) \end{eqnarray} $$

エージェント2は通常の報酬で学習するので、 $$ \begin{eqnarray} Q^2(s, a) \leftarrow Q^2(s, a) + \alpha (r+ \gamma max _{a'}Q^2(s', a')-Q^2(s, a)) \end{eqnarray} $$ のようにQ値を更新します。

この時に、同じ経験の系列によって学習した場合、常に$Q^1(s, a)=Q^2(s, a)$となります
なので、いちいちステップ毎にPBRSで更新するより、初期状態で$\phi(s)$を加え、後は通常のQ学習を行うほうが楽ですよということを言っています。

補足

定理と証明

参考文献の論文を参考にしていただければと思います。
@todo(後日追加予定)

参考文献

https://arxiv.org/abs/1106.5267

【強化学習】方策(ポリシー)とは

強化学習で方策(ポリシー)というのは、

「ある状態$s$での各行動$a$を行う確率分布」を表すものとなります。

平たく言えば、「このような時には、こういう行動するべきだろう」といったものとなります。

まぁ名前の通り、ポリシーになります。

記号では、方策を$\pi(s, a)$といった形で表現します。

この$\pi(s, a)$は、

状態$s$において行動$a$を行う確率を表しています。

強化学習では、この方策$\pi(s, a)$を最適化(獲得する報酬の最大化)することが目的となります。

参考文献

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

【マルチエージェント強化学習、評価用問題】Boutiler's Coordination Game

今回はBoutiler's Coordination Gameを紹介します。
このゲーム2体のエージェントの協調型のゲームになります。
つまり、うまく協調した時にお互いに最大の報酬が得られるような問題となります。
この問題の状態遷移と報酬については以下の図のようになります。

f:id:ttt242242:20190612072440j:plain

このゲームに状態は6つあり、
状態遷移は各状態においての2エージェントの行動の組み合わせによって決定します。
$\langle A_1, A_2 \rangle$は左がエージェント$1$の行動、右がエージェント$2$の行動となります。
各エージェントの行動は${a, b}$の二択になります。

このゲームは、
$s_1$からスタートします。
まずエージェント1が行動選択し、状態遷移を行っていきます。 右端の状態まで到達した段階で報酬が得られます。
これが1エピソードとなり、行動選択を繰り返します。

最適な状態は$s_4$に毎回遷移することになります。

エージェント1がまず$a$を選択した場合、
エージェント2の行動によらず$s_2$に遷移します。
さらにエージェント1が$a$、エージェント2も$a$を選択した場合、
状態$s_4$に遷移して、両エージェントは報酬10を受け取ります。
そして、状態$s_1$に戻ります。

参考文献

https://www.cs.york.ac.uk/aig/papers/devlin-kudenko-aamas2012.pdf

【強化学習、簡易調査】Reinforcement Learning Experience Reuse with Policy Residual Representation(2019)

※ 本当にざっと読んだだけ

概要

強化学習において、経験の再利用は、サンプルの効率を向上させるために 非常に重要なことである。
重要な課題の1つはどのように経験を表現し、保管するかということである。
これまでの多くの研究では、研究は経験をある特徴量に変換したり、
モデルを作成するなど、それぞれ異なる粒度で、経験の保存をおこなってきた。 しかしながら、新しいタスクは複数の粒度の経験が必要かもしれない。
この論文では、経験を抽象化し、複数の階層構造で保存可能な
policy residual representaion(PRR) networkを提案する。
PRR networkは複数の階層からななるタスクから学習させる。
それゆえ、PRR network は経験を経験をスプクトルのような形式で表現することが可能である。
新しいタスクを学習する時、
PRRは、学習を高速化させるために、異なる経験の形式を供給する。
我々は、PRRをgrid world等の問題で評価し、
先行研究に比べて良い性能を得ることを確認した。

その他メモ

  • Experience 階層型の形式で表現するのはおもしろい
  • Experience reuseの関連研究はかなり参考なりそう

論文情報

著者

  • Wen-Ji Zhou
  • その他

中国系の大学と会社

論文

https://arxiv.org/pdf/1905.13719.pdf

会議

IJCAI 2019