強化学習3 動的計画法・TD手法

Aidemy　2020/11/16

はじめに

　こんにちは、んがょぺです！バリバリの文系ですが、AIの可能性に興味を持ったのがきっかけで、AI特化型スクール「Aidemy」に通い、勉強しています。ここで得られた知識を皆さんと共有したいと思い、Qiitaでまとめています。以前のまとめ記事も多くの方に読んでいただけてとても嬉しいです。ありがとうございます！
　今回は、強化学習の3つ目の投稿になります。どうぞよろしくお願いします。

＊本記事は「Aidemy」での学習内容を「自分の言葉で」まとめたものになります。表現の間違いや勘違いを含む可能性があります。ご了承ください。

今回学ぶこと
・動的計画法について
・TD手法について

動的計画法

動的計画法とは

・Chapter2ではベルマン方程式を使って最適な方策を見つけるということを説明したが、このChapterでは実際にこれを行っていく。
・環境のモデルが「マルコフ決定過程（MDP）」で完全に与えられているとするとき、最適な方策を求める手法を「動的計画法（DP）」という。

方策評価

・手法$\pi$をとった時の価値関数$V^\pi(s)$を計算することを方策評価という。実行方法は以下の通り。
・まず方策を更新する際の閾値$\epsilon$を事前に設定する。そして方策$\pi$を入力し、$V(s)$を全ての状態において0と仮定し、更新時に全ての状態の差分が閾値よりも小さくするために、「$\delta$」を定義しておく。
・ここまで定義したら、全ての状態sについて、「v=$V(s)$」として、ベルマン方程式で「$V(s)$」を計算する。更新量を比較するために、あらかじめ定義しておいた「$\delta$」を「$\max(\delta,|v-V(s)|)$」に更新し、これが「$\epsilon$」を下回ったらその時点で計算を終了し、「$V(s)$」を「$V^\pi(s)$」の近似解と仮定して出力する。
・以上についてのコードが以下である。

・方策評価を行う関数「policy_evaluation()」について、引数には「方策pi、状態states、閾値epsilon」を渡す。
・はじめに「$\delta=0$」を定義する。そして、ここからは全ての状態sについて上記手法を行なっていく。まずは「v=V.copy()」で変数「v」に価値関数Vを代入する。また、次の計算で算出される「V[s]」を格納する変数「x」も用意しておく。
・「for (p, s1) in T(s, pi[s]):」について、「p」はエピソードTで得られる「そのActionを起こす確率（$\pi(a|s)$)」で、「s1」は「遷移先のState（after_state）」である。これらを使ってベルマン方程式（Chapter2の公式参照）で$V(s)$を計算する。これを「x」に代入する。
・この$V(s)$と$v(s)$を使った上記の式で「$\delta$」を計算し、閾値「$\epsilon$」を下回ったら価値関数の近似値「V」を返す。

・実行部分

・実行部分を見てみると、「policy_evaluation()」の「v」部分に当たるVと、引数で渡すpiを定義している。関数を適用した結果、StateAの価値関数とStateBの価値関数がそれぞれ算出されている。

方策反復

・前項の価値評価によって算出された「$V^\pi(s)$」において、greedy手法をとるような方策を「$\pi'$」とすると、「$V^\pi(s)$ < $V^{\pi'}(s)$」となることが知られており、これを価値改善という。
・この価値改善と価値評価を繰り返すことで、最適価値関数を導出することができる。このことを方策反復という。
・価値改善を行う関数「policy_iteration()」のコードは以下のようになる。

・上記コードについて、まずは価値関数Vと方策piを初期化する。これを行なったら、Vについて、Chapter2で作成した関数「policy_evaluation()」で方策評価を行う。同時に、「policy_flag=True」とする。
・各状態sについて、更新したVを使ってゲルマン方程式で方策piを算出し、これに従ってactionをソートする。そして、方策が被ってなければpiにactionを格納してループを継続する。これが終了したら方策piを返す。

・実行部分

・方策反復関数「policy_iteration()」は方策piを返すので、この実行結果は「StateAの時ActionXを取り、StateBの時ActionXをとる」という方策を表している。

価値反復

・前項の方策反復は、方策piを計算するために毎回全ての状態について価値関数を計算し直すことを複数回おこなわなければならず、状態が増えるほど計算量も多くなってしまう。これを解決するのが「価値反復」という手法である。
・価値反復では、価値vを計算するために各状態sについて、価値関数を直接求めて更新する手法を取るので、価値関数の計算は一度で済む。
・以下は価値反復関数「value_iteration()」のコードである。

・この関数について、まずは状態価値Vを今までと同様に初期化する。方策反復と違って方策piは考慮されないので、piの初期化を行う必要はない。次に、各行動について、方策評価を行って計算される$V(s)$の最大値を更新する。
・最後に、この$V(s)$から最も報酬が得られる行動を計算し、方策「pi」として返す。この時の最も報酬が得られる行動は前項の方策反復の時と同じように計算できる。

・実行部分

TD手法

TD手法とは

・以上の手法は動的計画法であり、状態遷移確率Pがあらかじめわかっていければならない。逆に、状態遷移確率がわかっていない時はChapter1で学んだように、実際に集めた報酬からこれを推定していく必要がある。
・この推定方法として「TD手法」というものがある。TimeDifferanceの略で、最終結果を見ずに現在の推定値を利用して次の推定値を更新するという方法で行われる。
・TD法には、「Sarsa」「Q-learning」_といった手法がある。

・以降は、以下の「環境2」を使っていく。

・開始地点は図の「start」のマス、終点は「+1」または「-1」のマス、黒いマスは遷移不可で、隣のマスの上下左右に動くことができる。また、8割の確率で、選択した通りに遷移することができるが、1割で選択した向きの90度時計回りに遷移し、残り1割で反時計回りに遷移する。報酬は、終点のマスはその点数、それ以外のマスは「-0.04」であるとする。
・以下のコードは、スタート地点から「上に二つ、右に三つ」進もうとした時の位置を出力する関数である。

・新しい環境を使うので、まずはそれを定義する。エピソードを定義する関数「T()」は、「take_single_action()」で使用するため、0列目がprobabilily,1列目がnext_stateの配列を返すように定義する。また、next_stateの状態を変化させるため、stateとdirectionから移動先を定義する「go()」も作成する。
・遷移確率に基づいて次の状態を決定する関数である「take_single_action()」はここでも使用する。上記「T()」で定義した「遷移確率」がxを越えるまで「次の状態」を更新し、更新が終了した時点での報酬を設定する。
・最後に、実際に「今いるstateから上に2回右に3回」移動する関数「move()」を作成する。actionsとして、0列目が上下の動き、1列目が左右の動きを定義し、0列目について2回take_single_actionで移動し、同様に1列目について3回移動してstateを更新する。

・実行部分

・環境についてはそれぞれのマスを定義している。初期地と終点も定義し、move()を使うことで移動後のstateがわかる。

Sarsa

・SarsaはTD手法の一つで、ベルマン方程式を試行錯誤しながら解いていくものである。価値反復などでは$V(s)$を使っていたが、ここでは行動価値関数$Q(s,a)$を使用する。このQ関数は[全ての状態×全ての行動]の配列で表す。
・この時の「全ての状態」について、環境2では、取りうる状態は11通り、「全ての行動」は上下左右の4通りである。よってQ関数は11×4の配列にしたいのだが、状態は座標で表されるため、これをうまく表現できない。よって、状態の部分は「x座標×10 + y座標×1」で対応させる。

・具体的なコードは以下の通り。（前項と重複する箇所は省略）

・「get_action()」は、後で定義するQ関数（q_table）の最大値によって行動を決定する関数である。この時渡される「t_state」は、先述した「座標を変換したstate」である。
・「take_single_action()」は今までのものと用途は同じだが、返される値として、rewardが設定されていない場合、すなわち行動先が壁や障害物で移動できない時は、その場に止まると言う意味で、状態「state」とreward「-0.04」を返し、rewardが設定されているマスにいるときは「next_state」とそのrewardを返す。
・「update_qtable()」は実際に行動価値関数Qを算出し、更新する関数である。この更新の時に使われる公式は以下である。
$$Q(s,a) += \alpha[r + \gamma Q(s',a') - Q(s,a)]$$

・この$\alpha$は学習率であり、事前に設定しておく必要がある。今回は「0.4」で設定する。また、割引率$\gamma$は「0.8」とする。また、この時渡される状態も、「座標を変換したstate」とする。計算自体は公式通りに行えば良い。
・最後に、状態「state」を「座標を変換したstate」にする「trans_state()」関数を作成する。

・実行部分

・Sarsaを実行するにあたり、まずは行動価値関数Qを初期化する。今回はエピソード数は500、時間ステップは最大1000回とし、またエピソードの終了条件として「5回連続で平均報酬が0.7以上」を設定するため、これを管理する配列も準備する。環境などは前項と同じ。
・次に、500回の各エピソードについて、(終了条件を満たすまで)以降の全てを繰り返す。
・まずはstateを初期化する。これに基づいて、Q関数に渡す「t_state」、行動「action」を計算する。それぞれ「trans_state()」「get_action()」関数を使用する。
・次に、エピソード中の各時間ステップについて「take_single_action()」で、行動aを行なった場合の次の状態s'と報酬rを取得し、報酬を累積していく。また、状態s'についてもQ関数に渡す「t_next_state」、行動「next_action」を計算する。
・これらを「update_qtable()」に渡して、行動価値関数を更新する。また、次の時間ステップに行くためにstateやactionも更新する。
・最終的に終点についたら、そのエピソードは終了し、次のエピソードに移動する。移動する前に、エピソード終了条件である報酬について「total_reward_vec」を更新し、それを出力する。同様に、終了したエピソードの番号と、それが何ステップで終了したかを出力する。
・もしこの「total_reward_vec」の最小値が0.7を超えたらエピソードの繰り返しも終了する。

・実行結果（一部のみ）

・実行結果をみてみると、報酬が「0.2」であったエピソードが直近5エピソードから除外され、全ての報酬が0.7を超えたエピソード21+1で終了している。

Sarsaでのε-greedy手法の実装

・前項の手法では、Q関数の最大値のみを選択していたが、これではより優れた手法を見逃す恐れがある。これを避けるために、ε-greedy手法を使って新しい手法を探索していく。
・Chapter1でもε-greedy手法を使ったが、少し変えて使用する。今回は、「episodeが早いうちはεを大きくして探索の割合を増やし、episodeが進むにつれてεの値を小さくして探索を狭めていく」というやり方を使う。式としては以下のものを使う。
$$\epsilon = 0.5 * (1 / ( episode + 1)) $$

・具体的なコードは以下の通りで、「get_action()」部分だけが異なる。

・上記関数について、まずは「epsilon」を上の式で算出。このepsilonが一様乱数「np.random.uniform(0,1)」以下であれば、前項と同様にQ関数の最大値に基づいて次の行動を決定し、そうでなければランダムに次の行動を決定することとしている。

・実行部分

・実行部分についてもほとんど前項と違いはないが、初めに定義している「action」は乱数が絡むget_action()を適用せず、Q関数の最大値を使って決定している。next_actionについてはこの関数を使用している。

Q学習

・Sarsaとは別のTD手法として「Q学習」と言うものがある。Sarsaと基本的には同じで、違う点について、各時間ステップの処理において、次の行動を決定してからQ関数の更新を行うのがSarsaであるのに対して、Q関数の更新を行ってから次の行動を決めるのがQ学習である。
・よって、関数「update_Qtable()」には「next_action」は渡さず、その代わりにnext_stateにおけるQ関数の最大値「next_max_q」_を算出し、これを使ってQ関数を更新する。これ以外はSarsaと全く同じ。

まとめ

・環境のモデルがマルコフ決定過程で完全に与えられているとき、Chapter2のベルマン方程式を使って最適な方策を最適な方策を求める手法のことを「動的計画法（DP）」という。
・ある手法$\pi$をとったときの価値関数$V^\pi(s)$を計算することを方策評価という。また、greedy手法をとったときの方策の方が価値関数は大きくなることが知られており、これを価値改善という。評価と改善を繰り返すことで最適な手法を見つけることができ、これを方策反復という。
・方策反復の応用として、方策ではなく価値を計算するために価値関数を更新する手法のことを価値反復という。これにより、価値関数の計算量が大幅に減らせる。
・方策反復や価値反復は動的計画法で、状態遷移率が与えられたモデルにのみ使用できるため、これが与えられていないモデルに対しては、TD手法というものを使用する。TD手法にはSarsaやQ学習がある。
・SarsaやQ学習はベルマン方程式により、行動価値関数Qを算出することで最適な方策を考える。

今回は以上です。最後まで読んでいただき、ありがとうございました。