電機情報工学専門実験 8. 強化学習シミュレーション

電機情報工学専門実験
6. 強化学習シミュレーション
強化学習(Reinforcement Learning: RL)
環境
報酬
状態 s
（観測）
r
Agent
行動
方策（行動の取り方） π に
従って行動選択
a
○ RL Agent の目的・・・最終的に得られる総報酬を最大化すること
「上の目的を達成できるよう方策 π を最適化」
π は一般的に  t (s, a)  p(at  a | st  s) で表現される
条件付き確率：時刻 t でAgent の状態が s である下で、
行動 a を取る確率
T 1
総報酬（収益） Rt  rt 1  rt  2    rt T   rt i 1
i 0
（T ：最終時間ステップ）
ただし、T = ∞ で Rt も ∞ となるので、通常は 
Rt  rt 1  rt  2   2 rt 3      k rt  k 1
の最大化を考える（ 0    1 ；  ：割引率）
k 0
マルコフ決定過程（ＭＤＰ）
通常、得られる報酬は Agent の過去の振舞に依存
過去の全行動を考慮することは困難
多くの RL 問題では、マルコフ決定過程（ＭＤP)下の環境を取扱う
ＭＤＰ・・・次状態 st+1 は、st と at “のみ”で決まる
Pssa' 、報酬の期待値 Rssa ' は以下で表される
Pssa'  p(st 1  s'| st  s, at  a)
MDP における状態遷移確率
Rssa '  E{rt 1 | st  s, at  a, st 1  s'}
とすると、
方策 π に従う Agent が状態 s で行動 a を取ると、
以降得られる報酬は

Q (s, a)  E {Rt | st  s, at  a}  E {  k rt  k 1 | st  s, at  a}

k 0
＝
行動価値関数
以降の行動も π に従うとすると、
Q (s, a)     Pssa'[ Rssa '    p(a'| s' )Q (s' , a' )]
s'
a'
と書ける
Q  に関する Bellman 方程式

RL では Q (s, a) を最大とするようなある π （最適方策）を知りたい！
二つの方策 π と π’ がある時、全状態で
max Q ( s, a)  max Q ' ( s, a)
a
a
ならば、 π は π’ と同等か、それ以上
他の全方策より良い or 同等の方策・・・最適方策 π*
（必ず一つ以上存在）
π* の持つ最適行動価値関数は、
Q* (s, a)   Pssa'[ Rssa '   maxQ* (s' , a' )]
s'
で計算可能（Bellman 最適方程式）
a'
Q* (s, a) を求める方法
○ 動的計画法(Dynamic Programming: DP)
○ RL
ー最適方策獲得の条件－
DP ・・・ (1) 環境のモデル（Vssa' と Rssa '）が存在すること
(2) 環境がＭＤＰでモデル化
多くのRL ・・・ (1) 環境がＭＤＰでモデル化
動的計画法（DP）
DP ・・・ Agent が経験し得る全状態の価値関数を、反復動作
によって獲得する手法
○ 価値関数更新の手順
1. 全ての s において V(s) の値を V0(s) へ初期化
（通常は０）
2. 全ての s において以下を実行
Vk (s)  max Pssa'[ Rssa '  Vk 1 (s' )]　(k  1,)
a
s'
3. 全ての s において計算した | Vk(s) – Vk-1(s) | の
最大値が任意の小さな値δ未満となるまで2. を
繰り返し
RL (Q-learning)
RL ・・・環境のモデル（Vssa' , Rssa '）を必要とせず、試行錯誤
的に最適方策を学習する手法
大別すると・・・
方策オン型： sarsa, sarsa(λ)
方策オフ型： TD法, TD(λ)
実験では、方策オフ型の代表的手法である、 Q-learning
(TD(0)) を取り上げる
Q-learning のアルゴリズム１
Q-learning では、DPのように環境のモデルが既知でなくても、
以下の条件が満たされる状況において、無限大の繰り返しを経て
最適方策へ収束することが保障されている
1. 挙動方策（テキスト参照）が、全状態行動対を選択する
可能性を確保している
2. 学習率αが以下の式を満たす


k 1

k

2

 k 
k 1
※ 条件2. は、学習率が漸進的に減少することを意味しているが、
実験では簡単のため、αの値は一定とする
Q-learning のアルゴリズム２
Q-learning におけるQ値（Q(s, a)）の更新手順
1. Q(s, a) を任意の値へ初期化
2. 任意の状態 s を初期状態として学習スタート
3. 挙動方策（例：ε-グリーディ方策など）に従って行動選択
4. 行動 a を選択した結果、報酬 r と次状態 s’ を観測した時、
以下の更新式に従ってQ値を更新
Q( s, a)  Q( s, a)   [r  max Q( s ' , a' )  Q( s, a)]
a'
5. s  s '
6. s が終端状態（最終的な目標状態）ならば終了して、2.
へ戻り学習を繰り返し。学習自体の終了条件を満たして
いる場合は学習を終了
C 言語によるプログラムについて
・コンパイルは、cc 、または gcc を用いて下さい。
例） test1.c というファイルをコンパイルして、test1run という
実行ファイルを作る場合は、
cc –o test1run test1.c [Return]
と入力
このファイルを実行する場合は、
./test1run （つまり、 ./実行ファイル名）
と入力すれば良い
・ C言語によるプログラミングに関する参考サイト
「0から始めるC言語学習帳」：
http://effy.ldw.jp/c/index.html
「C言語講座」：
http://www.sgnet.co.jp/c/
実験時間外の質問・問い合わせについて
E-mail が一番確実（すぐ返信できるとは限りません）
[email protected]
居室まで直接来てもらっても構いません（2号館2階220Ａ）
（曜日、時間帯によっては不在の場合も）
実験情報に関するHP：
http://www-tkm.ics.nitech.ac.jp/~arao/lecture/EJ_Exp10/EJ_index.html
演習室でのブラウザ利用について
まず、proxy の設定を行ってください
1. Firefox を開く（マウスの右クリックメニューで選択 or
“firefoxl” とキーボードから入力）
2. メニューの「編集」→「設定」→「詳細」を選択し、表示
されたウィンドウの「ネットワーク」タブを選択
3. 「接続設定」をクリックして、HTTPプロキシを
proxy-b.mains.nitech.ac.jp
ポートを
8080
に設定する

Download Report