3 回 : 強化学習手法のプログラムの理解 ゲーム理論と最適化手法第

ゲーム理論と最適化手法 第 3 ^回 : ^{強化学習手法のプロ}

グラムの理解

上田 俊

佐賀大学理工学部

Email: [email protected] Web: https://www.fu.is.saga-u.ac.jp/sgrueda/

2019 ^年 10 ^月 1 ^日

今日のプログラム

• https://www.fu.is.saga-

u.ac.jp/sgrueda/?page id=65 ^から

Q-Learning.xlsx ^と Q-Learning.txt ^をダウ ンロード

• wifi の回線を開けるために，ダウンロー

ドが終わった人から wifi ^{を切断してくだ}

さい．

マルコフ決定過程

• s ∈ S : ^状態

• a ∈ A : ^行動

• P (s

| s, a) : ^{状態遷移確率}

•

状態 s で行動 a を取った時に次状態 s

に遷 移する確率

• r(s) : ^状態 s ^{に遷移した時の報酬}

政策

• 強化学習の目的は，よりよい政策 π ^を獲 得すること．

• π(s, a) = P (a | s) : ^状態 s ^{において，ど}

の行動 a を取るべきかについての確率的

な指針

25 ^{を言った方が負け}

• 2 ^{人で交代に，} 1 ^から順に 25 ^{までの数を} 言う．

• 言う数の個数は， 1 ^個， 2 ^個， 3 ^個のいず れか好きなのを選んでよい．

• 最後に 25 ^{を言った方が負け．}

後手必勝

• 24 ^{を言えれば，相手に} 25 ^{を言わせて} 勝ち．

• 20 ^{を言えれば，} 21 ^， 22 ^， 23 ^のどれが 返ってきても 24 ^{を言うことができる．}

• あとは， 16 ^， 12 ^， . . . , 4 ^{とさかのぼる．}

• つまり，後手であれば， 1 ^， 2 ^， 3 ^のいず

れかが来て， 4 を言うことで必勝モード

になる．

マルコフ決定過程と政策の一部

4

1 ²

4

3 5

3

7

6

𝜋 1,2 𝜋 1,3

𝜋 1,4

𝑃 3 1,2

𝑃 5 1,2

𝑃 4 1,3 𝑃 5 1,2 𝑃 5 1,3

𝑃 5 1,4 𝑃 6 1,3 𝑃 6 1,4

𝑃 7 1,4

状態価値関数と行動価値関数

• V

(s) : ^状態 s ^{において政策} π ^に従う場 合に得られる報酬 ( ^の期待値 ) ^{，状態価値} 関数

• Q

(s, a) : ^状態 s ^{において行動} a ^をとっ た後に政策 π に従う場合に得られる報 酬 ( ^の期待値 ) ^{，行動価値関数}

• V

(s) = ∑

a

π (s, a)Q

(s, a) の関係に

ある．

ベルマン方程式

• マルコフ決定過程において価値関数は以 下の再帰的な性質を満たす : V

(s) =

∑

a

π(s, a) ∑

s^′

P (s

| s, a)[r(s

) + V

(s

)]

• 同様に，行動価値関数に関して，

Q

(s, a) = r(s) + ∑

s^′

V

(s

)P (s

| s, a) V

(s

) = ∑

a^′

π(s

, a

)Q

(s

, a

)

が成り立つ．

Q ^学習

• 以下で定義される最適行動価値関数 Q

(s, a) ^{を学習する} : Q

(s, a) =

r(s) + ∑

s^′

P (s

| s, a) max

Q

(s

, a

)

• 以下の更新式で少しずつ Q

(s, a) ^に近づ ける : Q(s, a) ←

Q(s, a)+ α(r(s

)+max

Q(s

, a

) − Q(s, a))

• α は更新率であり， α = 0.1 程度に設定

する．

Q ^{学習のアルゴリズム}

1

Q ^{値を初期化する．}

2

for i = 1 to L ( ^{トライアル数} ) do

1

時刻 t = 0 ^とし， s

を観測する．

2

repeat

1

政策

に従って

を選択し行動する．

2

環境から

と

を観測する．

3 Q

学習の更新式に従って

の値を更新 する．

4

時刻

とする．

3

until ゲームが終了する．

3

end for

行動選択

• 完全にランダム

• グリーディー法

•

最も Q 値の高い行動を選択する．

• ε - ^{グリーディー法}

•

確率 ε で全行動からランダムに選択する．

•

確率 1 − ε でグリーディー法を用いて選択 する．

• ボルツマン選択

第 3 ^{回小レポート課題}

• 自分の分野における，強化学習が適用で

きそうな問題とその理由を説明しな

さい．

今日のプログラム ( ^再掲 )

• https://www.fu.is.saga-

u.ac.jp/sgrueda/?page id=65 ^から

Q-Learning.xlsx ^と Q-Learning.txt ^をダウ ンロード

• wifi の回線を開けるために，ダウンロー

ドが終わった人から wifi ^{を切断してくだ}

さい．