tocomの調査録(機械学習、強化学習多め)

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

多腕バンディット問題(Nアームバンディット問題)

多腕バンディット問題とは

多腕バンディット問題は、以下の図のような複数の腕を持つマシンがあり、
最も期待値の高い腕を損失を最小化しつつ見つけることが目的の問題です。

f:id:ttt242242:20190815125927p:plain

プレーヤーは各腕を試し、得られた利益から、最も期待値の高い腕を見つけます。
ここで、大事なのがいかに損失を少なくしながら、最も良い腕を見つけることです。

この問題は様々な意思決定問題を一般化した問題です。
(例、目的地までの経路探索探索問題、レストランの選択等)

実装と実験

今回は単純な多腕バンディット問題を実装します。
各腕の利益の期待値は、正規分布に従う乱数によって決定するとします。

また、プレーヤーは簡単な強化学習エージェントとしています。
単純に得られた利益によって各腕の選択確率を調整します。

ソースコード

実験

上記のプログラムを実行すると、以下のような各腕を選択した回数と、

各腕を選択した回数
{0: 1246, 2: 30, 3: 8691, 1: 33}

以下のような利得の推移を出力します。 f:id:ttt242242:20190815130359p:plain

【強化学習、入門】SARSAの解説とpythonでの実装 -迷路を例に-

強化学習の代表的アルゴリズムであるSARSAについて紹介します。

基本

強化学習

強化学習は、試行錯誤を通じて得られる報酬を最大化するように行動指針を修正していく、学習フレームワークです。

よく用いられる図は以下のような図です。

f:id:ttt242242:20190801132632p:plain

強化学習エージェント(図中のロボット)は行動$a$し、
その行動によって変化した状態$s$と報酬$r$を観測します。
観測した情報を元に学習を進めていきます。

迷路問題で言えば、

  • 環境:迷路
  • 状態:マス目(座標)
  • 行動:進捗方向(上下左右)
  • 報酬:ゴール地点で得られる値

となります。
(これは、一例です。状態、報酬、行動に関しては問題に合わせて設計者が設定します)

Qテーブル

Qテーブルは各状態において各行動を取った時に得られるだろう報酬(期待報酬) を記憶しておくテーブルです。
よく$Q(s, a)$と表します。$Q(s, a)$は状態$s$に対して行動$a$を取った時の期待報酬値を意味します。
強化学習エージェントの頭脳といえます。
Q学習等の強化学習では$Q(s, a)$を最適化することが目的となります。

以下に、単純な迷路問題での学習したQテーブルの例を示します。

f:id:ttt242242:20190801132858p:plain

Sがスタート地点、Gがゴール地点、黒が壁を表しています。
強化学習エージェントの目的はSからGまでの経路を求めることです。

各マスを状態$s$とし、各状態の各行動$a$(矢印)に対する期待報酬値$Q(s, a)$(矢印の中の数値)が保存してあります。
ゴールに近づく行動に対しては、高い値となっています。 この値を元に行動選択をすることで、スタート地点からゴール地点までの最短経路を導き出すことができます。

SARSA

SARSAとは

Q学習は代表的な強化学習アルゴリズムの1つであり、
Qテーブルの更新時に遷移先の状態$s'$における最大のQ値を用いることが大きな特徴となります。

$Q(s, a)$を以下のように更新します。

$$ \begin{eqnarray} Q(s, a) \leftarrow Q(s, a) + \alpha (r + \gamma Q(s', a') - Q(s, a)) \end{eqnarray} $$

$Q(s, a)$の更新時に$\langle s, a, r, s', a' \rangle$ を用いるのでSARSAと呼ばれます。

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

  1. 現在の状態 $s$で$Q(s)$を元に行動$a$の選択(ε-greedyなどを用いて)
  2. 実際に行動し、状態遷移。遷移先状態$s'$と報酬$r$の観測
  3. 遷移先の状態$s'$で$Q(s')$を元に次の行動$a'$の選択
  4. $Q(s, a)$を、式1を用いて更新(学習)
  5. 2, 3, 4を$Q(s, a)$が収束するまで繰り返す

実装

問題設定

以下のようなマップの迷路問題を扱います。 かなりシンプルなマップになります。

f:id:ttt242242:20190801132918p:plain

Sはスタート地点はGはゴール地点を表しています。
黒いマスは壁となっています。

状態、行動、報酬は以下の通りです。

  • 状態:マス目(座標)
  • 行動:上下左右の4択
  • 報酬:ゴール地点に着けば100、通常の地点は0、壁や境界線であれば-1の報酬

ソースコード

実験結果

エピソード毎の累積報酬をプロットしました。
(1エピソードはスタート地点からゴールに着くまで)

f:id:ttt242242:20190801144839j:plain

学習が進むことに高い報酬を得れていることがわかります。

参考文献

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

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

強化学習

強化学習

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

【強化学習】UCBアルゴリズム〜多腕バンディット問題を解く〜

UCBアルゴリズムを実装して多腕バンディット問題(マルチアームバンディットプロブレム)で試してみました。

UCBアルゴリズム

UCBアルゴリズムは「知らない選択肢は楽観的に」をポリシーとした行動選択手法です。

UCBではUCB値という値を用いて、行動選択を行います。 選択肢$i$のUCB値は以下のように定義されます。

$$ UCB_i = Q_{i} + C \sqrt{\frac{2 \ln n}{n_i}} $$

$Q_i$ は選択肢iを選択して得られた報酬の平均値。nは全試行回数、$n_i$は 選択肢iの試行回数。Cは定数。 このUCB値が最も高い選択肢をステップ毎に選択します。

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

  1. UCB値を初期化
  2. 最も高いUCB値を持つ選択肢$i$を選択
  3. 選択によって報酬$r$を得る
  4. 選択肢$i$ の期待値$Q_i$、総試行回数n、選択肢の試行回数$n_i$ を1ずつ増やす
  5. 上述した式によって実行した選択肢$i$のUCB値を更新
  6. 2,3,4,5を繰り返す

実験

問題設定

多腕バンディット問題を用います。

今回は5つのアームがあり、3つ目のアームの期待報酬値が最も高い設定とします。

ソースコード

結果

上述したプログラムを実行すると、以下のようなステップ毎の獲得報酬の推移を出力します。

f:id:ttt242242:20190813160145p:plain
ステップ毎のUCBエージェントの利得の推移

UCBアルゴリズムによって、ある程度高い報酬を得ることができていると確認できます。

参考文献

numpyのmeshgridの基本的な使い方

numpy methgridの基本的に使い方と解説

numpy のmethgridの基本的な使い方を解説します。

methgrid を用いることで、1次元配列から格子状の座標を簡単に作成することができます。
まぁ例を見たほうが理解しやすいと思うのでサンプルコードをお見せします。
ちなみに、これ以降のコードはnumpyとmatplotlibをimportしていることが前提となります。

import numpy as np
import matplotlib.pyplot as plt

2つの配列(x=[0, 3, 6], y=[0, 3, 6])をmethgridに与えた時の結果は以下のようになります。

In [2]: x = [0,3,6]
In [3]: y = [0,3,6]
In [4]: X,Y = np.meshgrid(x,y)
In [5]: X
Out[5]: 
array([[0, 3, 6],
       [0, 3, 6],
       [0, 3, 6]])
In [6]: Y
Out[6]: 
array([[0, 0, 0],
       [3, 3, 3],
       [6, 6, 6]])

methgridによって座標を作成できています。 (例えば(X[0], Y[0])=(0, 0))
簡単に図で説明してみるとXは以下のような配列を生成していることがわかります。

f:id:ttt242242:20190813055049p:plain

Yに関しても同様です。

このX, Yを用いることで以下のような図を簡単に作成することができます。

In [7]: fig, ax = plt.subplots()
In [8]: ax.scatter(X, Y)
Out[8]: <matplotlib.collections.PathCollection at 0x7ffb74677e10>

f:id:ttt242242:20190811053502p:plain

ついでにアノテーションも着けたバージョンも

In [9] : for x1 in x:
    ...:     for y1 in y:
    ...:         ax.annotate("({}, {})".format(x1, y1),(x1, y1))

f:id:ttt242242:20190811053515p:plain

参考文献

numpy.meshgrid — NumPy v1.17 Manual

【深層強化学習】Deep Q Network をTensorFlowで実装

今回はDeep Q Networkについて紹介します。 実装にはTensorFlowを用いました。

Deep Q Network

Deep Q Network(DQN)はQ学習Qテーブルをニューラルネットワーク関数近似した強化学習アルゴリズムです。

f:id:ttt242242:20190812053308p:plain 左がQ学習のQテーブル、右はQテーブルをニューラルネットワーク関数近似(Q Network)

厳密にはQテーブルをニューラルネットワーク関数近似しただけでなく、
Experience Replay、Target Network、Reward Clipping等の工夫を加えたものをDeep Q Networkと呼びます。

Deep Q Networkの構成

Deep Q Networkは以下の図のようになります。

f:id:ttt242242:20190811173656p:plain

エージェントはTarget NetworkとQ Networkというニューラルネットワークを保持しています。 この2つのネットワークの構造は同一です。パラメータは異なります。
このネットワークの入力は状態、出力はQ値になります。
得られた経験$\langle s, a, s', r \rangle$(ある状態$s$において行動$a$を行い、状態$s'$に遷移し報酬$r$を得た)を保存するためのExperience Bufferを保持しています。

Deep Q Networkの学習の流れ

図にある通り、以下を繰り返します。

  1. 現在の状態$s$をTarget Network$Q(s', a|\theta^{-})$に入力
  2. Target Networkから出力されたQ値を元に行動選択
  3. 行動したことによって変化した状態 $s'$ 及び報酬$r$の観測
  4. 経験$e=\langle s, a, s', r \rangle$をExperience Bufferに保存
  5. Experience Bufferから任意の経験を取り出し、Q Networkをミニバッチ学習(Experience Replay)(詳細は後述
  6. Target Networkの更新(詳細は後述

Target Networkの更新

任意のインターバルで、 Q NetworkのパラメータをTarget Networkに反映していきます。
これは、Q Learningの過大評価という課題を緩和するために重要なります。

Q Networkのパラメータの反映方法には大きくわけて2つあって、
1つはHard Update もう1つはSoft Update になります。

Hard Updateでは、定期的にQ NetworkのパラメータをTarget Networkにコピーします。
Soft Update では、Q Networkを更新する度に少しずつずづQ Networkのパラメータを反映させていきます。

Experience Replay(Q Networkの学習)

任意のインターバルで、
バッチサイズ分Experience Bufferから 経験をサンプリング($B=\{e_0, e_1, ..., e_{|B|} \} $) し、
以下のTD誤差$\mathcal{L}(\theta)$を最小化するようにQ Networkのパラメータ$\theta$を更新します。

$$ \begin{eqnarray} \mathcal{L}(\theta) = \frac{1}{|B|}\sum_{e \in B} (r + \gamma \max_a Q(s', a|\theta^{-}) - Q(s, a|\theta))^2 \end{eqnarray} $$

Reward Clipping

Reward Clippingは外れ値等に過剰に反応しすぎないために、
報酬値を-1〜1の範囲にクリップすることです。

実装と実験

tensorflowを使って実装してみました。
cartpole問題を用いて、実験します。

Cartpole問題とは

CartPoleは、 棒が設置してある台車があり、
台車を棒が倒れないように
うまくコントロールする問題になります。

f:id:ttt242242:20190428190208p:plain

出典:Leaderboard · openai/gym Wiki · GitHub

制御値、観測、報酬等について
制御値(行動)

制御値は、台を左に押す(0)か 右に押す(1)の二択になります。

操作
0 左に押す
1 右に押す
観測

観測値は、台車の位置、台車の速度、棒の角度、棒の先端の速度の4つになります。

観測情報 最小値 最大値
台車の位置 -2.4 2.4
台車の速度 -inf inf
棒の角度 -41.8° 41.8°
棒の先端の速度 -inf inf
報酬

報酬としては1を与え続けます。

エピソードの終了判定

以下のどれかの条件を満たした場合に、
エピソードが終了したと判定されます。

  • ポールのアングルが±12°以内
  • 台車の位置が±2.4以内
  • エピソードの長さが200以上

ソースコードと解説

ソースコード

一部解説(注意すべき点)

Q Networkを学習する時に注意する必要があります。
経験$\langle s, a_0, r, s' \rangle$が与えられた時に$Q(s, a_0)$だけを学習させるために 少し工夫を加えます。 余計な学習をしないように、Q Networkの出力とtarget$r+\gamma \max_a Q(s',a|\theta^{-})$にマスク処理を行います。

図を用いて説明します。
単純に学習しようとすると、以下の図のようにすべての出力層を考慮してしまいます。 f:id:ttt242242:20190812053338p:plain

しかし、今回考慮したいのは行動$a_0$に対する評価のみです。
なので、余計な学習をしないように、$a_1, a_2$を無視するために、出力$Q(s, a_1), Q(s, a_2)$と$a_1, a_2$に対応したtargetを0にし、学習しないようにします。

f:id:ttt242242:20190812053353p:plain

ソースコード上では、120行〜122行の部分になります。
one hot encodingを用いて対処しています。

実験結果

f:id:ttt242242:20190811182301p:plain

横軸はepisode、縦軸はpoleが立っていられたステップ数を表します。
poleが立っていられる最大ステップは200ステップです。
エピソードが進むごとにpoleを200ステップ立たせられていることがわかります。

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

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

マルチエージェント強化学習は、
複数の強化学習エージェントが同時に学習行動を行う 自律分散型の学習フレームワークのことを言います。

マルチエージェント(マルチエージェントシステム)は、複数(マルチ)のエージェントが相互作用しているシステムです。
エージェントとは、主体的に行動する人間、動物やロボットなどを一般化したものになります。
また、強化学習とは、試行錯誤によって行動方策を学習していく学習フレームワークになります。
強化学習については以下の記事にまとめています。

www.tcom242242.net

マルチエージェント強化学習とは、 同じ環境複数強化学習エージェントが同時に学習して行動し、相互に影響を及ぼしている学習フレームワークです。

f:id:ttt242242:20190802061728p:plain:w340:h280
マルチエージェント強化学習イメージ

マルチエージェント強化学習では、あるエージェントの行動(選択)が、その他のエージェントに影響を与えます。
そのため、シングルエージェントの強化学習に比べて考慮点が多くなり複雑な問題となります。

分散型のシステムではあればマルチエージェント強化学習問題を適用できるタスクとなります。
例えば、複数エレベータの制御、交通信号機の制御にも適用できます。
人間社会も複数の人(エージェント)が同時に学習しているので、マルチエージェント強化学習といえます。

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

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

  • 協調型(全エージェントが受け取る報酬が同じ)
    f:id:ttt242242:20190802141454p:plain:w400:h200
    マルチエージェント強化学習(協調型)
  • 対戦型(あるエージェントの利益はその他のエージェントにとっての損益)
    f:id:ttt242242:20190802141653p:plain:w400:h200
    マルチエージェント強化学習(対戦型)
  • Mix(その他)

など様々な形式が考えられます。