Deep RL Bootcampで強化学習の勉強 Vol. 1
2017年に UC Berkeleyで開催されたDeep RL Bootcampの動画を見たのでそれをまとめていこうと思う.
強化学習とは
MDPと呼ばれる問題設定において,方策と呼ばれる行動指針を学習するアルゴリズム.
ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習の一種. Wikipediaより
教師あり学習などとの違いは,教師あり学習は学習データと教師ラベルのデータセットから相互の関係性(回帰・分類)を学習するのに対して,強化学習はエージェントと環境との相互作用によって,その時々に対する出力を学習する.
強化学習では環境からのフィードバックを前提とする.
強化学習のすみわけ
強化学習の住み分けは以下の感じ.
Policy Optimizationから派生するPolicy GradientsとDynamic Programmingから派生するQ-Learningなどがある. Policy Optimizationの中のPolicy Gradients(方策勾配法)はDeep Learningとの組み合わせで用いられることが多い. こちらについては別の記事で触れようと思う.
今回はDynamic ProgrammingのValue IterationとPolicy Iterationについて触れる.
Markov Decision Process (MDP)
Markov Decision Process (MDP)は状態遷移が確率的に行われるようなシステムをモデル化したもの.
強化学習の枠組みはMDPをベースとして考えられることが多いのでここで理解しておく.
定義
Sは状態の集合(ロボットのジョイント角度など).
Aは行動の集合(各ジョイントに送るトルク).
Tは状態遷移関数.決定的・確率的を問わない.現在の状態と行動が与えられた時に求められる次状態,またはその分布を返す関数.
Rは報酬関数.ある状態sにおいて行動aを選択し,次状態s'へと遷移した時に得られる報酬を決定する関数.
は初期状態.もしくは初期状態の分布
はdiscount factor(割引率).現在と比較しいてどれくらい将来の報酬を見積もるかを決定するスカラー値.利子のようなものと理解しておけば良い.
HはHorizon.どのくらい長く行動を行うかの指標.有限でも無限でも良い.
問題設定
MDPが与えられたときの最適化問題.
今回の目的は以下の通り.
MDPが与えられたとき,報酬和を最大化するような最適方策を求める.
この問題設定を解くために,Value IterationとPolicy Iterationを考える.
Value Iteration
はじめに最適価値関数を用意する.
これは状態から,最適方策に従って行動したときの期待割引報酬和.
これは最適な方策を取ったときの各状態の価値,すなわちその状態にいると将来的にどれくらいの価値が得られるかということを示す値ということになる.
ではからスタートしてに行くときのはどのように表されるか?
このようにの再起的な式として表される.
再起的な価値関数を求めるためにValue Iterationを用いる. これにより,から初めて再起的にを求める.
とすると,
のようになる. このときはのときの価値関数ということになる.
毎回のの更新をValue updateやBellman update/back-upと呼んだりする.
無限回の更新によって最適な価値関数を得ることができることが証明されている.
最適価値関数を得ることができたら,MDPを解くための方策を獲得したことになる.
次に,価値関数と同様に行動価値関数というものを考える.
では行動は最適方策に従う行動であったが,今回ははどんな行動でも良い.
行動価値関数は状態において行動を選択た後に最適方策に従う行動を取った場合に,状態において将来的にどれくらいの価値を得られるかを示す関数ということができる(ややこしい).
価値関数と同様に行動価値関数においてもupdateの式を考えると,
となる.
行動価値関数[tex: Q^(s, a)]を考える理由はいくつかあるが,一つとして,価値関数のみでは最適行動を選択できないということが挙げられる. 価値関数は行動を選択した際の遷移確率を考慮していないが,行動価値関数はある状態からある行動を選択した際の価値を考えているため,この問題が発生しない. また[tex:max_a Q^(s,a)]が状態における方策となるので,方策を更新する必要がなく,行動価値関数のみを保持しておくだけで良くなる.
Value Iterationでは収束までにどれくらいのHを設定しておけば良いかが分からないため,実際に使用する場合はとりあえず大きな値(無限回)を設定しておく必要がある.
Policy Iteration
Policy Iterationは大枠はValue Iterationとほぼ同じだが,とても重要なのでちゃんと理解したい.
Value Iterationの更新方法は以下の通りだった.
状態において最適方策に従って行動する.
Value Iterationにおいては毎回のValue updateの際に,その時々の最適方策が獲得されている必要がある.
では,方策が最適でなかった場合はどうか?
例えば方策が適当に与えられており,ある状態における方策がどれくらい良い方策なのかを評価したい場合,その方策に従ったときの価値関数は,
となる.
これでその方策がどれくらい良いのかということを評価できることができるようになったので,これを更新していきたい.
Policy Iterationは方策評価と更新を行う.
1)現在の方策をとしてそのときの価値関数を評価し,2)その価値関数の値をもとに次状態の価値関数が最大となるような現在の行動を方策として更新する.
これをとのさが限りなく小さくなるまで繰り返す.
1)の方策評価においてはValue IterationのようにValue updateを行う方法と,Policy Iterationにおける価値関数の式を線形システムとして計算する方法の2種類がある. Policy Iterationではmaxの式が外れるので線形システムとして計算できるというのが良い点.
まとめ
MDPで方策を求める方法としてValue IterationとPlicy Iterationを勉強した.
Value IterationやPolicy IterationではTやRがあらかじめ与えられている前提でMDPが解けるというものだった.
次の勉強では遷移関数や報酬関数が与えられていないときはどのように方策を求めれば良いのか,ということをまとめていく.