#概要(と但し書き)
UCLのDavid Silver教授(Deep Mind社のAlpha-Go Zeroの開発者の1人)のRL Courseを利用して、強化学習理論の基礎を勉強しましたが、すぐに忘れてしまいそうなので、知識の整理も兼ねてまとめてみます。
第1回講義
スライド集
基礎とはいえ理論なので数式が多いです。
項目の順番は講義内容に沿うように書いています。
また、最後の講義(Lecture 10)は理論ではなく、強化学習のゲームAIへの適用についてのケーススタディのため、範囲には含みません。しかし、講義としては一番面白いので、ゲームAIに興味がある方もない方も、1度はご覧になることをおすすめします。
注意書きとして、強化学習とは...については、すでに下記のような素晴らしい記事がたくさんあるので記載しません。
ゼロからディープまで学ぶ強化学習
記事に登場する英語の部分は、公式の日本語訳がわからないために訳していないものもあります。
また、英語のスペリングは基本的にイギリス英語ですが、米語に直したほうが多く引っかかる場合があります。
1の範囲は、エージェントの定義からDynamic Programmingまでです。
2はこちら。
#エージェントの構成要素
強化学習のエージェントの基本的な要素は以下の3つ。(必須というわけではない)
- Policy(方策)：エージェントの行動指針
- Value Function(価値関数)：状態やアクションを評価するための関数
- Model(モデル)：エージェントの視点からの環境
これらの要素がある/ないで、強化学習の様々な考え方を分けることができる。
方策/価値関数
Value-Based：価値関数を保持、更新して学習する。明示的な方策はない。(厳密にはないわけではないが、価値関数が最大のものを常に選択するだけ)
Policy-Based：ある明示的なPolicyに従って行動する。価値関数は行動選択に影響を与えない(内部的に持つ)。
Actor-Critic：方策も価値関数もどちらも利用する。
モデル
Model-Free：モデルなし。環境の構造や遷移を全て把握しようとするのではなく、サンプルをとってどのように環境が作用するかを学習する。
Model-Based：モデルあり。まず環境を把握するためにモデルを構築し、どのような振る舞いが最も最適かをあらかじめ決定する。
##方策
エージェントの行動指針となるもので、ある状態においてどのようなアクションを選択するかを表す関数。
Deterministic Policy(決定論的方策)とStochastic Policy(確率的方策)がある。
###決定論的方策
a = \pi (s)
状態(s)におけるアクション(a)は、方策($ \pi $)によって決定される。
現在の状態で、最終的に最も多くの報酬が得られるアクションを選択する際に利用する。
###確率的方策
\pi {(a|s)} = P[A = a|S = s]
状態(s)におけるアクション(a)は、方策($ \pi $)によって決定される。
しかし、ある状態におけるアクションは一定の確率で選択される。(決定的ではない)
ランダムにアクションを選択する必要がある場合、例えばより多くの状態を探す際などに利用する。
##価値関数
ある状態やあるアクションによって、将来どのくらい報酬が得られるかの予測値を表す(より多くの報酬を得られると予測できる状態はより良い状態)。
State Value Function(状態価値関数)とAction Value Function(行動価値関数)の2つという分け方や、
Optimal Value Function(全ての方策において最適化された価値関数)がある。
##モデル
環境そのものではないが、環境を予測するための情報。
Transition ModelとReward Modelの2つに分けられる。
###Transition Model
P^a_{ss'} = P[S_{t+1} = s'|S_t = s, A = a]
次の状態S'は現在の状態(s)とアクション(a)に依存し、sとaの組み合わせからs'に遷移する確率を表している。
###Reward Model
R^a_{s} = E[R|S = s, A = a]
現在の状態(s)とアクション(a)から、取得できる報酬Rの期待値を表している。
#マルコフ決定過程
##マルコフ性
強化学習の各状態はMarkov Property(マルコフ性)を持つ。
Markov Propertyとは、ある状態は遷移前の状態にのみ依存するということ = それより前の状態は考慮する必要がない。
[S_{t+1}|S_t] = P[S_{t+1}|S_1, ..., S_t]
上記の式は、次の状態$S_{t+1}$は現在の状態$S_t$にのみ依存していることを示す。
よって状態遷移は以下のようになる。
P_{ss'} = P[S_{t+1} = s'|S_t = s]
##Markov Reward Process
Markov Reward Process(MRP)は、マルコフ連鎖に価値判断を追加し拡張したプロセス。
MRPは、$[S, P, R, \gamma ]$で表される。
S：全状態を表す有限のテーブル
P：確率的な状態遷移を表すテーブル(Markov Propertyの式と同じ)
P_{ss'} = P[S_{t+1} = s'|S_t = s]
R：報酬関数
R_s = E[R_{t+1}|S_t = s]
γ：割引率
\gamma \in [0, 1]
以上より、全報酬の合計$G_t$は以下のように表せる。
G_t = R_{t+1} + \gamma R_{t+2} + ...
= \sum_{k=0}^{\infty} \gamma ^k R_{t+k+1}
また各状態の状態価値関数は以下のように表せる。
v(s) = E[G_t|S_t = s]
上記の式は、現在の状態(s)から先に得られるだろうと予測している報酬の合計を表す。
定義した全報酬($G_t$)を、即座に得られる報酬とそれ以降の割引された報酬の合計の２つに分け、組み合わせることでBellman Equation(ベルマン方程式)を得ることができる。
v(s) = E[R_{t+1} + \gamma v(S_{t+1})|S_t = s]
##Markov Decision Process
Markov Decision Process(MDP)は、MRPに行動決定を追加したプロセス。
MDPは、$[S, A, P, R, \gamma ]$で表される。
また、環境内の全ての状態はマルコフ性を有する。
S：全状態を表す有限のテーブル
A：全アクションを表す有限のテーブル
P：確率的な状態遷移を表すテーブル
P^a_{ss'} = P[S_{t+1} = s'|S_t = s, A_t = a]
R：報酬関数
R^a_s = E[R_{t+1}|S_t = s, A_t = a]
γ：割引率
\gamma \in [0, 1]
方策は以下のように表せる。
\pi (a|s) = P[A_t = a|S_t = s]
この式が表すのは、ある状態にいる時どのアクションを選ぶかという確率であり、アクションは現在の状態に依存しているということ。
例えば、お腹が空いている時、そばを食べる確率が50%、うどんを食べる確率が50%なら$ \pi (a|s) = 0.5$となる。
確率的な意思決定は、より多くの状態とアクションを見つける「Exploration(探索)」に利用できる(反対は最大の報酬が得られると予測できる状態やアクションを選択する、「Exploitation(搾取)」)。
また、方策はタイムステップに影響されず変更されない。
###Bellman Expectation Equation
MDPでは各状態における状態価値関数と各アクションの行動価値関数を利用する。
状態価値関数は以下のように表せる。
v_\pi (s) = E_\pi [G_t|S_t = s]
これは方策($ \pi $)に従った時、状態(s)がどれくらいの価値があるかを表している。
また、価値=その状態から将来にかけて取得できる報酬の合計である。
以上より$v(s)$は、$ \pi $に基づいてステップを進めるとした時、状態(s)以降にどのくらいの報酬が得られるのかを表している。
同様に行動価値関数は以下のように表せる。
q_\pi (s, a) = E_\pi [G_t|S_t = s, A_t = a]
$v(s)$と同様に、方策($ \pi $)に従った時、状態(s)におけるアクション(a)がどれくらいの価値があるかを表している。
また、価値=そのアクション実行後から将来にかけて取得できる報酬の合計である。
以上より$q(s,a)$は、$ \pi $に基づいてステップを進めるとした時、アクション(a)を実行してから先でどのくらいの報酬が得られるのかを表している。
MRPの時と同様に価値関数を組み替えて、各価値関数ごとにベルマン方程式を導く。
まずは、状態価値関数。
v_\pi (s) = E_\pi [R_{t+1} + \gamma v_\pi (S_{t+1})|S_t = s]
次に、行動価値関数
q_\pi (s, a) = E_\pi [R_{t+1} + \gamma q_\pi (S_{t+1}, A_{t+1})|S_t = s, A_t = a]
これらは、与えられた方策にしたがったて行動した際、得られる最大の報酬はどのくらいかを予想する(Expect)ための方程式であり、Bellman Expectation Equationという。
###Bellman Optimality Equation
上記では、予想するための価値関数とベルマン方程式を求めたが、次に方策によらずMDPにおける最適な価値関数を求める。
まず、価値関数を定義する。
状態価値関数は、次のように表せる。
v_* (s) = max_\pi v_\pi (s)
全ての方策の上で、状態(s)における最大の価値を表し、最適な状態価値関数($ v_* $)である。
これは方策にかかわらず、その状態以降で期待できる最大の報酬合計であると言える。
行動価値関数は次のようになる。
q_* (s,a) = max_\pi q_\pi (s,a)
全ての方策の上で、状態(s)におけるアクション(a)の最大の価値を表し、最適な行動価値関数($ q_* $)である。
これは方策にかかわらず、アクション(a)を実行してから先で期待できる最大の報酬合計であると言える。
q*が求まるということは、全ての状態において報酬の合計を最大化するアクションが決まるので、最適な行動価値関数を求めることはMDPを解くことと同義である。
次にMDPにおける最適な方策($ \pi _ * $)を定義する。
問題となるのは、ある方策がもう１つの方策よりも優れているというのはどのように判断すれば良いかということである。
答えとなるのが、価値関数による比較である。
全ての状態において、$v_ \pi (s)$が$v_{ \pi '}(s)$よりも価値が高かった場合、$ \pi $は$ \pi ' $よりも良い(最適化された)方策であると言える。
\pi \geq \pi ' \; if \; v_\pi (s) \geq v_\pi '(s), ∀s\\
\pi _* \geq \pi, ∀\pi
その他の全ての方策に対して上記の式が当てはまる場合、その方策は最適な方策であり、いかなるMDPにも必ず１つ以上の最適な方策が存在する。
また最適な方策は、必ず最適な状態価値関数と最適な行動価値関数を満たす。
v_{\pi *}(s) = v_* (s)\\
q_{\pi *}(s, a) = q_* (s,a)
では、どのように最適な方策を見つけるのか。
それは以下の式によって表される。
\pi _* (a|s) = \left\{
\begin{array}{ll}
1 & if \; a = argmax_{a \in A} \, q_* (s, a) \\
0 & otherwise
\end{array}
\right.
以上の式では、現在の状態(s)における最適な行動価値関数から最大の報酬が得られるアクション(a)を選んでいる。
そのため、最適な方策は必ず決定論的となる。
最後にベルマン方程式を求める。
v_*(s) = max_a \, q_*(s,a)
ある状態(s)における最大の価値は、その状態で選択できるアクションの中で最も高い価値を持っているアクションの価値と同値であるということを示している(Bellman Expectation Equationでは、その状態で選択できるアクションの価値の平均)。
q_*(s,a) = R^a_s + \gamma \sum_{s' \in S} P^a_{ss'} v_*(s')
$ q_* $は最大の価値を持つ次の状態の値を使うことはできない。
アクションの結果、どのような状態に遷移するかは確率的だからである。そのため、遷移先の状態の価値の平均を使う。
最適な(Optimal)価値関数を求めるため、上記の式をBellman Optimality Equationと呼ぶ。
最後に、Bellman Optimality Equationを解く方法の例を記載する。
- Value Iteration(Dynamic Programming)
- Policy Iteration(Dynamic Programming)
- Q Learning(Model-Free Control)
- Sarsa(Model-Free Control)
#Dynamic Programming
MDPの項で登場したBellman Optimality Equationを解くための数学的な手法の一つがDynamic Programming(DP)である。
Dynamic：ある問題に対する連続的や時間的な構成要素
Programming：与えられた問題を最適化すること
DPは、ある複雑な問題をそのまま解くのではなく、細かい部分的な問題に分け、分けられた部分的な問題を解くことで、最終的に複雑な問題を解く。
DPを適用する問題には条件があるが、MDPはそれを満たしている。(講義資料参照)
DPでは、エージェントは対象のMDPの全ての情報を持っていると仮定する。(= Model-Based)
その情報は、エージェントがMDPにおける報酬最大化という目的のための行動順序の決定過程に利用される。
Model-BasedなMDPでは、状態価値関数の更新を利用して、方策の評価したり、最適な方策を追求したりする。
上記の理由は、状態や状態遷移の確率までエージェントが知っているため、最初から状態自体の価値を予想し、更新することができるからである。(行動価値関数の更新は状態価値関数の更新よりコストが高い)
与えられた方策における最大報酬の予想(Prediction)は、
入力：MDP$[S, A, P, R, \gamma ]$ + $ \pi $、またはMRP$[S, P_ \pi, R_ \pi, \gamma ]$
出力：価値関数($v_ \pi $)
MDPの報酬の最大化(Control)は、
入力：MDP$[S, A, P, R, \gamma ]$
出力：最適な価値関数 $ v_* $ + 最適な方策 $ \pi _* $
となる。
この項で挙げる3つのDPのアルゴリズムは、Synchronousな価値関数の更新が挙げられる。
ここでいうSynchronousとは、イテレーションを終えるごとに全ての(厳密には全てではない場合あるが)状態価値関数を更新することである。
反対に更新がAsynchronousな場合、1ステップごとに1つの状態またはActionのValueFunctionを更新する。
AsynchronousなDPのアルゴリズムについては、講義資料を参照。
##Policy Evaluation
MDPの完全な情報と方策が与えられた時、その方策が与えられたMDPにおいて最大でどの程度の報酬を得ることができるかを求めることは、その方策(Policy)を評価する(Evaluate)ことになる。(= Bellman Expectation Equationを解く)
Bellman Expectation Equationを反復して更新することで、その方策における各状態の価値を求めることができ、最終的に対象のMDPにおける、与えられた方策を採った場合に得られる最大の報酬を求めることができる。
Bellman Expectation Equationを、1イテレーションごとに$v_1 \rightarrow v_2 \rightarrow v_3 ... \rightarrow v_ \pi $と更新する。
イテレーションの数をk、ある状態をs、sの次の状態をs'と置く時、$v_{k+1}(s)$は$v_k(s')$の平均を使って更新する。
式で表すと以下のようになる。
v_{k+1}(s) = \sum_{a \in A}\pi (a|s) (R^a_s + \gamma \sum_{s' \in S} P^a_{ss'} v_k(s'))
状態(s)の価値は、実行できる各アクションに対して、アクションを実際に実行した先の各遷移先状態(s`)の価値とそれぞれの遷移確率をかけたものを計算し、さらにアクションごとに結果を合計したものとなる。
1イテレーションごとに全ての状態に対して、この更新作業を行う。(Iterative Policy Evaluation)
##Policy Iteration
次に与えられた方策をより良い方策に導くことで、最終的に最も報酬を多く得ることができる方策を探し出す手段に移る。
方策の改善は2つのステップに分けられる。
1ステップ目は、現在の方策を評価する。
これは今までやってきたように、現在の方策($ \pi $)における$v_ \pi $を求めることである。
v_\pi (s) = E_\pi [R_{t+1} + \gamma R_{t+2} + \gamma ^2 R_{t+3}...|S_t = s]
$v_ \pi $が求められたら、2ステップ目として、現在の方策を改善し、新しい方策を導く。
方策の改善は、1ステップ目で求めたvπを利用し、最終的に最も多くの報酬を得られると考えられる状態を遷移していく(= greedy)。
\pi ' = greedy(v_ \pi)
単純なMDPであれば、1度$v_ \pi $を求め、それを使って報酬が最大になるように状態を遷移する方策をとるだけでMDPを解いたことになる(= 最適な方策を見つけた)。
しかし、より複雑な問題であれば、2つのステップを何度も反復する必要があるが、初期値がなんであれ結果として最適な方策($ \pi _*$)を得られることが証明されている。
方策の改善をもう少し詳しく確認する。
方策をgreedyに更新する時、以下のように表すことができる。
\pi ' = argmax_{a \in A} \; q_ \pi (s, a)\\
q_\pi (s, \pi '(s)) = max_{a \in A}\; q_ \pi (s, a) \geq q_ \pi (s, \pi (s)) = v_\pi (s)\\
v_\pi (s) \leq q_\pi (s, \pi '(s)) = \\
E_\pi [R_{t+1} + \gamma v_\pi (S_{t+1})|S_t = s] \leq E_{\pi '}[R_{t+1} + \gamma R_{t+2} + \gamma ^2 R_{t+3}...|S_t = s] = v_{\pi '} (s)
以上のように、新しい方策($ \pi '$)は各状態において報酬が最大となるアクションを選択するため、以前の方策($ \pi $)よりも悪い方策とはなることはない。
そのため、以下のような場合に、更新が終わり、最適な方策にたどり着いたと判断できる。
q_\pi (s, \pi '(s)) = max_{a \in A}\; q_ \pi (s, a) = q_ \pi (s, \pi (s)) = v_\pi (s)\\
v_\pi (s) = max_{a \in A}\; q_ \pi (s, a)
２つ目の式は、Bellman Optimality Equationであるため、これが求められた=MDPを解いたことになる。
##Value Iteration
Policy Iterationでは、最終的にMDPを解くことに成功したが、効率がよくない。
現在の方策を評価し終えてから(Vπを求めてから)、方策の最適化を行う必要はあるのだろうか。
実際、方策の最適化の前に、必ずしもVπを求める必要はない。(講義資料参照)
以上を踏まえ、Policy Iterationのイテレーションごとに方策の最適化も行うというのが、Value Iterationの考え方である。
まず、最適な方策の原理を考える。
最適な方策は、最初の最適なアクションと、その遷移後の状態から最適な方策を採り続けるという2つの部分に分けられる。
そうすると、もしある状態(s)における価値関数($v_ \pi (s)$)が最適な方策をとった時の状態価値関数($v_* (s)$)と等しいとき、状態(s)から遷移可能ないかなる状態(s')においても、$v_ \pi (s') = v_* (s')$となることが成立する。
もし、既にエージェントが$v_* (s')$について知っているならば、$v_* (s)$はそれに基づいて求めることができる。
v_*(s) = max_{a \in A} \; R^a_s \; + \gamma \sum_{s' \in S} \; P^a_{ss'} \; v_*(s')
Rがアクション(a)を取ったことによる即時的な報酬であり、+以降が遷移先の状態(s')の価値と遷移確率をかけたものの合計である = $v_* (s')$となる。
その中で最も得られる報酬が大きいアクションの値を$v_* (s)$に代入する。
式からわかるように、最後の状態から以前の状態に向かって価値関数の更新が行われる(Bellman optimality backup)。
この更新を1イテレーションごとに反復して行うのが、Value Iterationの考え方である。
Value Iterationの目的はMDPにおける最適な方策を見つけることであり、
その目的達成の手段としてイテレーションごとの価値関数の最適化を採用した。
Value Iterationの結果、最終的に最適な状態価値関数($v_* $)にたどり着くことが保証されている。
Value IterationはPolicy Itertionとは違い明示的な方策を持たないが、最終的に得られる$v_* $を手がかりに、最も報酬が獲得できるアクションを取るという方策が最適な方策となる。
##Dynamic Programmingの問題点
DPの問題点は、対象のMDPの全ての状態とアクションの構造を定義し、全て更新するということである。
これはとてもコストが高い。
この問題点を改善するには、Model-Freeなアルゴリズムが必要となる。
#最後に
社会人になって再学習したとはいえ、数学を高校2年でやめた、強化学習独学の文系人が書いているので、間違っているところも多いと思います。
間違いを見つけた際には、私自身の学びのためにも、ご指摘いただけると大変ありがたいです。
#参考資料
An Introduction to Reinforcement Learning(訳本は出版されてますが、有料です)
http://incompleteideas.net/book/bookdraft2017nov5.pdf
Algorithms for Reinforcement Learning
https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf