2019-02-08

強化学習：プランニングと学習（その１）

強化学習 Planning

f:id:shirakonotempura:20190208134221j:plain

はじめに

今回からの話はSutton本、第8章（Planning and Learning with Tabular Methods）の内容になります．

本当は前回の記事（SARSA・Q学習）に引き続き、Actor-Criticについて整理したかったのですが、諸事情で8章の内容の理解に努めたいと思います．

今まではいろんな人のQiitaやブログを見ながらやってきたのですが、Q学習・関数近似が終わればDQNの実装に入っていくのか、この章の内容について書かれている記事はあまりなかったので、いつもよりは自力で書いてます．そのため、だいぶ内容に不備があると思いますが何卒ご了承ください．

幸い実装や例題は公開されているものがありますので、そちらをふんだんに利用させていただく予定です．

これは私の学習用ノート．メモ、備忘録です．

プランニングについて

これまで強化学習に関して整理してきた内容の中でプランニング（planning）という言葉は出てきませんでしたので、この言葉の説明から始めます．

Sutton本には

The word planning is used in several different ways in different fields. We use the term to refer to any computational process that takes a model as input and produces or improves a policy for interacting with the modeled environment

出典：Reinforcement Learning: An Introduction, R Sutton & A Barto, p.160

とありますが、ざっくりと言えばプランニングは『モデルを使って』、方策を改善していくことだと理解しています．

一方の学習（Learning）はその名のとおり学習のことです．ただし、これまでの内容では価値関数や方策を学習の対象としてきましたが、今回の内容ではモデルも学習対象となってきます．

『今回の』と書きましたが、実はこれまでに登場したモデルベース（Model Based）の強化学習は、本質的にはモデルの学習を行うモデルです．しかし、モデルベースの代表であった動的計画法では、学習すべきモデルが既に既知であることを前提にしていたので、そもそもモデルを学習する必要がなかったわけです．

一方のモデルフリーの強化学習の枠組み（モンテカルロやTD学習）においては、Model-Freeなのでモデルは出てきません．この枠組みでは、モデルがないのでとりあえず実際に行動して得られた経験を使って価値関数を計算し、方策の改善を行っていました．

以上をまとめておきます．

モデルベース強化学習（Model-Based RL）
- 経験からモデルについて学習を行う
- モデルを使って、行動価値や方策の改善を行う
- 動的計画法（Dynamic Programming）とか
モデルフリー強化学習（Model-Free RL）
- 経験から価値関数や方策の改善を行う（モデルは使わない）
- モンテカルロ法、TD学習（Q学習、SARSA）とか

f:id:shirakonotempura:20190208085231p:plain

出典：Reinforcement Learning: An Introduction, R Sutton & A Barto, p.162の図を編集

モデル（Model）について改めて考えてみる

強化学習においてモデルというのは、ある状態でとった行動で得られる報酬や次の状態が推定できるもののことを指しています．状態と行動（あるいは方策）を与えれば、報酬・次の状態を返す関数のように考えればよいかと思います．

そう考えると、モデルは実際にエージェントが行動をする環境と何が違うのか、この２つを混同しそうになるかもしれません．現に私は、この章の目的が全く分からないってくらい、めちゃくちゃ悩みました．（私だけかもしれません）

悩んだ結果、以下のような考え方に行きつきました．

実際の環境：エージェント（本当に動くやつ）がいる．
モデル：エージェント（本当に動くやつ）がいない．

誤った考え方だとは思うのですが、この章を理解するにあたってはこれでいけます．おそらくモデル上でエージェントを仮想的に動かす場合もあると思いますのであしからず．

そもそも迷路にしろ、スロットにしろ、すべてコンピューター上で行っているのでややこしいんですよね．

Tabular Model

ひとことでモデルと言っても、いくつか種類があるようです．（線形ガウスモデルとかDeep Belief Network モデルとか・・・、調べきれてません）

今回は、章のタイトルにもあるとおり、テーブル型のモデルを用います．これはいたってシンプルなもので、状態 $S$ および行動 $A$ を入力側、その入力に対する報酬 $R$ および次の状態 $S'$ を表形式で持って置くというものです．

たぶん以下のようなイメージ（入力から出力が確定的なものとしています）

f:id:shirakonotempura:20190208090235p:plain

モデルフリーRLとモデルベースRLの統合

この章での主たる目的は、モデルフリーの考え方とモデルベースの考え方を統合することにあります．
なぜそんなことをする必要があるのかというと、統合することでお互いの長所を使いつつ、短所をなくすことができるためです．感覚的にはモデルを想定しなくてもよいモデルフリーの方が有能だろうと思っていたのですが、そうではないようです．

モデルフリーの場合、モデルを介さず直接、環境を通じて得られた本物の経験を使って価値関数・方策の更新を行うことができます．また、学習の際に最小化すべき誤差を考えた場合、モデルフリーの場合の誤差は本物の経験と推定値の差であるが、モデルベースの場合、モデルそのものが推定されたものであるため、そのモデルから推定される推定値は誤差が大きくなってしまいます．

一方で、モデルベースのメリットとしては、モデルは関数のようなものなので、教師あり学習の考え方に似ています．つまり、もしモデルの入出力の関係性についてなにか知識を持っているのであれば、簡単に学習のアルゴリズムに適用することができます．また、構築したモデルの情報から、学習がまだ不十分なところを見つけることができるため、重点的に学習をさせることができます．

２通りの経験の利用

モデルフリーRLとモデルベースRLを統合した場合の、経験、価値・方策およびモデルの関係性を以下に示す．

f:id:shirakonotempura:20190208091054p:plain

経験、価値・方策およびモデルの関係

出典：Reinforcement Learning: An Introduction, R Sutton & A Barto, p.162

図から分かるように、実際の環境から得られた経験（Experience）は、以下に示す２つの目的に使用されます．

モデルの学習（Model Learning）：経験をもとにモデルを改善する
直接的強化学習（Direct Learning）：経験をもとに価値関数・方策を改善する

モデルから価値関数・方策を改善していく流れのことを、Direct Learningに対してIndirect Learningと呼ばれることもありますが、この改善のことがまさにプランニングとなります．
また、統合後のアルゴリズムでは価値関数・方策は、経験からの直接的強化学習とモデルを利用したプランニングの両者によって改善されていくことが分かるかと思います．

この一連の学習アルゴリズムにはDynaという名前が付けられています．
次の項でDynaについてもう少し詳しく見ていきます．

DynaおよびDyna-Q

以下に一般的なDynaの構造を示します．

f:id:shirakonotempura:20190208142129p:plain

出典：Reinforcement Learning: An Introduction, R Sutton & A Barto, p.163の図を編集

先の説明とほぼ同じことの繰り返しになりますが、Dynaでは実際の環境から得られた経験を使って、①直接、価値関数・方策を改善する流れと、②モデルを学習し、モデルから得られるサンプル（疑似の経験）を使って価値関数や方策を改善する（プランニング）の流れを持っています．

Dynaの中で最も単純なアルゴリズムがDyna-Qと呼ばれるアルゴリズムです．名前からも推測できると思いますが、DynaとQ学習を組み合わせたアルゴリズムになります．

Q学習はモデルフリーの学習方法ですので、実際に得られた経験から直接Qテーブルの値を更新していました．

Dyna-Qでは、まず通常のQ学習同様、ある状態 $S$ においてエージェントが実際に行動 $A$ を行い経験として報酬 $R$ および次の状態 $S'$ を獲得し、行動価値 $Q(S,A)$ の更新を行います．
その後、次のステップに行く前に、今得られた経験（状態 $S$ で行動 $A$ を取ったら、報酬 $R$ を得て状態が $S'$ に遷移したという事実）を使って、モデルの学習（更新）を行います．
そして、学習後のモデルからサンプリングを行い、得られた疑似の経験を使って行動価値 $Q(S,A)$ の更新を行います．
このサンプリングと更新をｎ回行って、エージェントが次のステップに移ります．なおこのnはplanning stepと呼ばれるもので、ハイパーパラメータになります．

Dyna-Qの疑似コードは以下のように書くことができます． f:id:shirakonotempura:20190208144455p:plain

出典：Reinforcement Learning: An Introduction, R Sutton & A Barto, p.164に加筆

例題の実行と考察までしようと思ったんですが、長くなってきたので一旦切ります．

まとめ

モデルの学習およびプランニングについて整理しました
復習を兼ねてモデルベースとモデルフリーの強化学習について整理しました．
モデルベースとモデルフリーの考え方を統合したアルゴリズム（Dyna、Dyna-Q）について整理しました．

次回は、例題の迷路問題などを使ってDyna-QとQ学習の違いなどの考察をしていきたいと思います．

2019-02-05

強化学習：TD学習（SARSA、Q学習）

強化学習 SARSA Q学習

f:id:shirakonotempura:20190202132807j:plain

はじめに

前回は、TD（temporal-difference）学習の基本編として定式化とアルゴリズムの紹介を行いました．

強化学習：TD学習（基本編） - 他力本願で生き抜く（本気）

今回は、その中でも有名かつベーシックな学習アルゴリズムであるSARSAとQ学習（Q-learning）について整理していきます．Sutton本の6.4章からの話になります．

これは、私の学習用ノート．メモ、備忘録です

今回の内容、実装は以下の記事を参考にさせていただきました．

qiita.com

SARSA

SARSA法は、方策オン（on-policy）型制御のアルゴリズムで、実際の方策に従って得られる行動および状態を価値の更新に使用します．

具体的に数式で見ていきます．前回の最後に紹介したTD法での行動価値関数の更新式を以下に示します．見やすくするために、次の状態[tex:s{t+1}]および次の行動[tex:a{t+1}]を、 $s'$ および $a'$ で表します．

$$Q(s, a) \leftarrow Q(s, a) + \alpha[r' + \gamma Q(s', a') - Q(s, a)]$$

この式はある状態 $s \in S$ での行動 $a\in A(s)$ の価値 $Q(s,a)$ を、その行動によって観測された報酬 $r$ と次の状態 $s'\in S$ 、および、その状態で方策に従って選ばれた次の行動 $a' \in A(s')$ の行動価値 $Q(s', a')$ を使って更新しています．

これをバックアップ線図で書くと、以下のように書けます．（ちょっとペンを紛失してしまったので、図をそのまま使わせてもらいます．ごめんなさい）

f:id:shirakonotempura:20190202141653j:plain

この一連の状態 $s$ 、行動 $a$ 、報酬 $r'$ 、状態 $s'$ 、行動 $a'$ の頭文字をとってSARSAという名前が付けられています．

SARSAのアルゴリズム

Sutton本6.4章に記述されているアルゴリズムを以下に示します．

Sarsa (on-policy TD control) for estimating $Q \approx q_*$
Algorithm parameters: step size $\alpha \in (0, 1$ ]. small $\epsilon \gt 0$
Initialize $Q(s,a)$ , for all $s \in S+$ , $a \in A(s)$ , arbitrarily excerpt that Q(terminal, ・) = 0
Loop for each episode:
$\qquad$ Initialize $S$
$\qquad$ Choose $A$ from $S$ using policy derived from $Q$ (e.g., ε-greedy)
$\qquad$ Loop for each step of episode;
$\qquad \qquad$ Take action $A$ , observed $R, S'$
$\qquad \qquad$ Choose $A'$ from $S'$ using policy derived from $Q$ (e.g., ε-greedy)
$\qquad \qquad$ $Q(s,a) \leftarrow Q(s,a) + \alpha [R + \gamma Q(s',a') - Q(s,a)$ ]
$\qquad \qquad$ $S \leftarrow S'; \; A \leftarrow A' ;$
$\qquad$ until S is terminal

Q学習

引き続き、方策オフ型のアルゴリズムであるQ学習について整理していきます．
Q学習による行動価値の推定を数式で書くと次のようになります．

$$Q(s, a) \leftarrow Q(s, a) + \alpha[r' + \gamma \; argmax_{a'} Q(s', a') - Q(s, a)]$$

Q学習では、状態 $s$ を起点にまずε-greedy法により行動 $a$ を選択します．行動 $a$ の結果、報酬 $r'$ 、次の状態 $s'$ を得ます。ここまではSARSA法と変わりません。

その後の価値関数の更新が、SARSAとは異なり、max関数を用いて、最も価値の高い行動をとる状態行動対を用いて $Q(s,a)$ を更新しています．

価値関数を更新したあとの実際の行動、つまり $s'$ から実際に次の状態に進む際の行動 $a'$ は、価値関数更新時にmax関数で求められた行動ではなく、ε-greedy法を使って決めます．

バックアップ線図で書くと、以下のように書けます． f:id:shirakonotempura:20190202145253j:plain

Q学習のアルゴリズム

Sutton本6.5章に記述されているアルゴリズムを以下に示します．

Q-learning (off-policy TD control) for estimating $\pi \approx \pi$
Algorithm parameters : step size $\alpha \in (0, 1$ ]. small ε　> 0
Initialize $Q(s,a)$ , for all $s \in S+$ , $a \in A(s)$ , arbitrarily except that $Q(terminal, ・)$ =0
Loop for each episode:
$\qquad$ Initialize $S$
$\qquad$ Loop for each step episode:
$\qquad \qquad$ Choose $A$ from $S$ using policy derived from $Q$ (e.g., ε-greedy)
$\qquad \qquad$ Take action $A$ , observe $R, S'$
$\qquad \qquad Q(S,A) \leftarrow Q(S,A) + \alpha [R + \gamma \; argmax_{A} Q(S', A) - Q(S,A)$ ]
$\qquad \qquad S \leftarrow S'$
$\qquad$ until $S$ is terminal

実装

こちらに公開されているコードを使ってSARSAとQ学習の実装を行います．問題設定は、Sutton本の6.5章にあるCliff Walking（崖歩き問題）になります．

Cliff Walikng

崖歩きの問題では、以下のような格子状の環境を想定しています．

f:id:shirakonotempura:20190205032113p:plain

ルール
- エージェントは『up, down, right and left』の４つの行動をとることができる．
- エージェントは１つの行動をとるたびに-1の報酬を得る．
- エージェントの初期配置は左下のマス（スタート）．
- エージェントが右下のマス（ゴール）に到達した時点でエピソードは終了
- 『The Cliff』と書かれたエリアに移動した場合、-100の報酬を得て、エピソードは終了
- エピソード終了後、エージェントは左下のマスに戻り、次のエピソードが開始．

行動選択はε-greedy法で行いεは0.1、ステップサイズパラメータ（学習率） $\alpha$ は0.5としています．

結果

500エピソードの学習で得られた学習経路（最適行動）および学習曲線を以下に示します．
学習曲線の値は、500回エピソードの学習を1エポックとして、50エポック実施した平均の値を示しています．
なお、崖上（The Cliff）の行動に意味はありません．

SARSAの場合、実際に取る行動が価値の更新に影響するので、崖に落ちる行動をとってしまうと価値が下がります．ですので崖に落ちるという行動を避けながらゴールに向かう経路を学習しています．一方でQ学習の方は、ベストな行動で価値を更新するので、実際の行動で崖に落ちようが落ちまいが関係なく最短経路を学習しています．Q学習では落ちることのリスクを考慮に入れていませんので、SARSAよりも崖に落ちる回数は増えます．

そのため得られる報酬の平均を見れば、SARSAの方がQ学習を上回っていることが分かります．

SARSAであってもランダムな探索行動をとらなければ、崖に落ちるというリスクはないことになります．つまり実際にとる行動がベストアクション一択になり、落ちるリスクを避けて迂回する必要がなくなります．そのため、この2つの学習方法はεの値を０に近づけていくと等価になります．

SARSA（迂回（崖から離れる）経路を取っています）

['R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D']
['U', 'R', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'R', 'R', 'D']
['U', 'U', 'U', 'R', 'U', 'R', 'R', 'U', 'U', 'U', 'R', 'D']
['U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'G']

Q学習（崖のきわを通る最短経路を取っています）

['L', 'L', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'R', 'D', 'D']
['L', 'R', 'R', 'D', 'R', 'R', 'D', 'R', 'D', 'D', 'R', 'D']
['R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D']
['U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'G']

f:id:shirakonotempura:20190205032814p:plain

傾向を分かりやすくするため、10データずつの移動平均を取り巻した． f:id:shirakonotempura:20190205045530p:plain

まとめ

代表的なTD学習アルゴリズム、SARSAおよびQ学習について整理しました．

Q学習はぼんやり理解して使ったことはあったのですが、トレースとは言え自分でいろいろ説明を書いてみるとより理解できた気がします．

実装部分はほぼ何もしていないので（写経のみ）、もうちょっと真面目にせねばと思いつつ時間が足りない・・．

2019-02-02

強化学習：TD学習（基本編）

強化学習 TD学習ブートストラップ

はじめに

前回までに、動的計画法（DP法）およびモンテカルロ法の概要を整理しました．今回は、この２つの手法を組み合わせたTD法という学習手法について整理します（Sutton本：6章）

これは私の学習ノートです．メモ、備忘録です．

今回も、以下の記事を参考にさせていただいています．ありがとうございます．
qiita.com

DP法とMC法の復習

TD法の説明に入る前に、DP法とMC法の概要をざっくりと整理します．そもそも、強化学習でやっていることは方策の元での状態・行動価値（価値関数）を推定し、方策を改善していくというものでです．

DP法では、推定したい価値関数を次の状態の価値関数を用いて計算しました．しかしその前提として、状態遷移（行動を起こしたら、次にどういう状態になるか）が把握できている必要があり、問題の全体像が分買っていない場合は、DP法を使うことはできません．

そこで、状態遷移のモデルが分からないならば、実際に行動をとって情報を集めよう。というのがMC法になります．MC法では試行に基づいてエピソードを生成し、得られた収益を平均することで価値関数の期待値を求めます．しかし、エピソードが終了するまで学習ができないという点がネックになります．

DP法：ブートストラップ（次の状態を使った価値関数の推定）が可能．でも状態遷移のモデルが分かっている必要がある．
MC法：状態遷移が分からなくても価値関数の推定が可能．でも、ブートストラップが使えない．

TD法（Temporal Difference Method）

今回紹介するTD法は、この中間、いいところをとった方法と言えます．つまり、実際にとった行動の結果から価値関数を推定するという点はMCと同じなのですが、その際、エピソード終了を待たず、DP法と同じように次の状態（またはさらにその先も）を使って価値関数の推定を行うことができる手法になります．

TD法の定式化

TD法ではMC法と同様、価値関数の推定は実際に試行を繰り返して行います．時刻 $t$ での状態 $s_t$ を起点として、エピソード終了時に得られる実際の収益を $R_t$ とした場合、MC法における価値関数更新は以下の式で表すことができます．

$$V(s_t) \leftarrow V(s_t) + \alpha [R_t - V(s_t)]$$

ここで、定数 $\alpha$ はステップサイズ・パラメータ、あるいは学習率と呼ばれます．

上記の式における $R_t$ がエピソードの終了を待たねば得られないのですが、TD法ではここを次のステップの推定値に置き換えます．ここが、動的計画法のアイデアになります．

$$V(s_t) \leftarrow V(s_t) + \alpha [r_{t+1} + \gamma V(s_{t+1}) - V(s_t)]$$

結果として、MC法では収益 $R_t$ を目標として更新するのに対し、TD法では $r_{t+1} + \gamma V(s_{t+1})$ を目標にして価値関数の更新を行うことになります．

繰り返しになりますが、TD法は以下のメリットを持つ学習方法だと言えます．

終端状態になるまで学習を行うのを待つ必要がない（DP法のメリット）
他の行動の価値を使って学習を行うことが出来る（DP法のメリット）
状態遷移のモデルを把握してなくてもよい（MC法のメリット）

以下に、DP法、MC法、TD法（後述のTD(0)）のバックアップ線図を示します．

f:id:shirakonotempura:20190202090949p:plain — DP(動的計画）法

f:id:shirakonotempura:20190202091012p:plain — MC（モンテカルロ）法

f:id:shirakonotempura:20190202091023p:plain — TD（Temporal-Difference）法

TD法のアルゴリズム

TD法は別に次のステップの状態しか使えないわけではなく、2ステップ先、3ステップ先と少し先の状態価値を使って推定を行うことができます．それはn-step TD学習（Sutton本：7.1章あたり～）と呼ばれます．

以下に示すアルゴリズムは直近（次のステップ）の価値関数の推定値を用いる方法でTD(0)とか1step-TD法と呼ばれるものになります．なお、MC法は終着状態（Terminal）のステップまで推定に利用するn-step TD学習となります．

Tabular TD(0) for estimating $v_\pi$
Input: the policy $\pi$ to be evaluated
Initialize $V(s)$ arbitrary (e.g., $V(s) = 0, \forall _s \in S^+$
Repeat (for each episode):
$\qquad$ Initialize $S$
$\qquad$ Repeat (for each step of episode):
$\qquad\qquad A \leftarrow$ action given by $\pi$ for $s$
$\qquad\qquad$ Take action $A$ , observe $R, s'$
$\qquad\qquad V(s) \leftarrow V(s) + \alpha [R + \gamma V(s') -V(s)$ ]
$\qquad$ unitil $S$ is terminal

Grid World での実装

例によって、コードを拝借しGrid WorldでTD法の実装を行いました．
得られた状態価値の推定値を以下に示します．精度よく推定できていますね．

f:id:shirakonotempura:20190202092151p:plain

行動価値関数の定式化

ここまで、状態価値関数 $V(s_t)$ を使ってTD法の説明をしてきましたが、行動価値関数 $Q(s_t, a_t)$ にも当然使えます．むしろ、こっちがよく使う式だと思うのですがSutton本の6.1章の導出のところでは出てきません．次回以降に説明する予定のSARSAなどのアルゴリズムの説明ではこちらの式がベースになります．

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [r_{t+1} + \gamma Q(s_{t+1}, a_{a+1}) - Q(s_t, a_t)]$$

まとめ

強化学習の重要な学習法の１つであるといえる、TD法について基本の式の定式化を行いました．

実は、TD法においても、一度も現れない状態行動対が現れるのは望ましくないため、MC法と同じく確率的に探索を行う工夫が必要です．次回はその中で最もベーシックな手法はSARSA（方策オン型）、Q-learning（方策オフ型）と呼ばれる手法についてまとめる予定です．

2019-02-02

強化学習：モンテカルロ法（without ES）

強化学習モンテカルロ法

はじめに

前回はモンテカルロ法を用いた行動価値関数の評価と方策改善について紹介しました．

強化学習：モンテカルロ法（行動価値評価） - 他力本願で生き抜く（本気）

その際、開始点探査（ES、Exploring Starts）という仮定をおいていましたが、今回はそれを仮定せずにモンテカルロ法で方策改善を行うことを紹介します．

これは私の学習ノートです．詳しく知りたい方は、以下の記事を呼んだ方が身になると思われます．

yamaimo.hatenablog.jp

モンテカルロ法 without ES

Sutton本の5.4章の冒頭で、突如『どうすれば非現実なExploring Startsの仮定を避けられるのだろうか』と出てきます．

これを読んで、そもそもなぜ、ESを外す必要があるだろうと思ったのですが、5.2章によれば、一般的に信頼性がある仮定ではないようです．

エピソードの中で、起こりうる状態行動対がちゃんと選択されればいいけど、選択されない可能性があるから、全部選択されるルールを設けてしまおう！としたのが開始点探査の仮定です．

私の頭では、それでそんなに問題がないような気もしますが、全ての状態を開始点として網羅させるというのは、実際には起こりえないような状況まで仮定してしまっているから良くない、ということでしょうか．難しい・・．

若干消化不良ですが、とにかく非現実なこの仮定を外す方法を考えていきます．

方策オン型（On-policy）と方策オフ型（Off-policy）手法

開始点探査の仮定を取り除く方法として、方策オン型と方策不型と呼ばれる２つの方法が挙げられます．

順に説明していきますが、方策オフ型は複雑すぎて私の知能では理解がおよびませんでしたので、言葉の説明だけにとどめています．ご了承ください．（詳細はSutton本：5.5～5.7章をご覧ください）

方策オン型モンテカルロ

方策オン型モンテカルロではが次の行動を起こす際に使用する方策 $\pi$ に、評価・改善対象の方策を使用します．改善対象の方策を使用することを方策オン（On-policy）と呼んでいます．方策オン型では、方策 $\pi$ を確定的なものからソフトなもの（選ばれる行動は確率に従う）に変更して、任意の状態行動対 $(s,a) \in \;S × /; A(s)$ について、 $\pi(s,a) \gt 0$ であることを保証する方法です．
こうすることで、開始探査点の仮定を取り除いても任意の状態行動対が観測されるようになります．

ソフトなものと言っていますが、具体的にはε-Greeedy方策を指しています．確率的なものであれば何でもいいと思うで、例えばとか、ここでは、という方が正しいかもしれません．

$A^*$ をgeedyな行動としたとき、 $0 \lt \epsilon \lt 1$ の $\epsilon$ に対して以下のように方策 $\pi(s,a)$ が決められます．

$\pi (s,a) = \left \{ \begin{array}{} 1 - \epsilon + \frac{\epsilon}{|A(s)|} \quad (if\;a = A^*)\\ \frac{\epsilon}{|A(s)|} \quad \qquad \;\;\; (otherwise)\\ \end{array} \right.$

以下にε-Greedy方策を用いた、方策オン型モンテカルロ法のアルゴリズムを示します

On-policy first-visit MC control(for ε-soft policies)
Initialize, for all $s \in S$ , $a \in A(s)$
$\qquad Q(s,a) \leftarrow arbitrary$
$\qquad Returns(s,a) \leftarrow empty \; list$
$\qquad \pi(s,a) \leftarrow an \;arbitrary \;\epsilon-soft \;policy$

Repeat forever:
$\qquad (a) \;Generate \;an \;episode \;using \pi$
$\qquad (b) \;For \;each \;pair \;s,a \;appearing \;in \;the \;episode:$
$\qquad \qquad G \leftarrow \;return \;following \;the \;first \;occurrence \;of \;s,a$
$\qquad \qquad Append \;G \;to \;Returns(s,a)$
$\qquad \qquad Q(s,a) \leftarrow \;average(Returns(s,a)$
$\qquad For \;each \;s \;in \;the \;episode:$
$\qquad \qquad A^* \leftarrow arg max_{a} Q(s,a)$
$\qquad \qquad For \;all \;a \in \;A:$

$\qquad \qquad \qquad \pi(s,a) \leftarrow \left \{ \begin{array}{} 1 - \epsilon + \frac{\epsilon}{|A(s)|} \quad (if\;a = A^*)\\ \frac{\epsilon}{|A(s)|} \quad \qquad \;\;\; (otherwise)\\ \end{array} \right.$

方策オフ型モンテカルロ

方策オン型モンテカルロでは、評価・改善用の方策 $\pi$ とは別の方策 $\pi'$ を使って、状態行動対の行動を観測し、その観測結果を使って方策 $\pi$ の評価・改善を行う方法です．たとえ、状態行動対を作り出す方策 $\pi$ が確定的なものであったとしても、 $\pi'$ がソフトなものであれば、開始探査点の仮定を取り除いても任意の状態行動対が観測されるというものです．

まとめ

モンテカルロ法において開始探査点（Exploring Starts）の仮定を取り除く方法として、方策オン型および方策オフ型モンテカルロ法についてまとめました．

以下の記事も参考にさせていただきました．

qiita.com

yoheitaonishi.com

2019-02-01

強化学習：モンテカルロ法（行動価値評価）

モンテカルロ法強化学習行動価値

はじめに

前回はモンテカルロ法を使って状態価値を評価するアルゴリズムを紹介しました．今回は行動価値を評価するアルゴリズムについて紹介します．

強化学習：モンテカルロ法（状態価値評価） - 他力本願で生き抜く（本気）

これは私の学習ノートです．詳しく知りたい方は、以下の記事を呼んでください．

今さら聞けない強化学習(8): モンテカルロ法でOpenAI GymのCartpoleを学習 - Qiita

強化学習について学んでみた。（その14） - いものやま。

モンテカルロ法による行動価値の評価（Sutton本の5.2章）

繰り返しになりますが、前回紹介したアルゴリズムでは状態価値の評価を行うことができます．しかし、環境のダイナミクス（モデル）が分からない状況では、状態価値が分かるだけでは十分ではありません．

なぜなら、行動 $a \in A(s)$ を取った時の状態の遷移確率 $P^a_{ss'}$ が分からないので、その行動による収益の期待値を計算できず、どの行動をとるべきかを知ることができないからです．（経路探索であれば、状態価値が分かれば各状態で取る行動を知ることはできます）．

そこで、状態価値の代わりに行動価値関数を評価することを考えていきます．

といっても、行動価値関数を用いる場合も状態価値関数を用いる場合もアルゴリズムはほぼ同じです．状態価値関数の場合は開始点を状態 $s$ としエピソードを生成させますが、行動価値関数の場合は開始点を状態 $s$ 、行動 $a$ としてエピソードを生成すればよいです．

開始点探査（Exploring Starts）について

行動価値関数も状態価値関数もほぼ同じと書きましたが、一点注意する必要があります．それは評価しようとする行動価値 $Q^\pi (s,a)$ の行動対 $(s, a$ が観測されないと、その行動価値を評価することはできないという点です．

要は、必ずすべての行動対が選ばれる必要があるような条件を設定する必要があります．それをここでは開始点探査（Exploring Starts、略してES）と呼んでいます．

行動価値関数を用いた方策改善

上記ESを考慮した方策評価によって、全ての状態の状態価値 $Q^\pi (s,a)$ が計算できれば、方策の改善は難しくありません．ある状態における、最も行動価値の高い行動を方策 $\pi (s)$ に入れてしまえばよいだけです．

$$\pi (s) \leftarrow \;arg max_{a} Q(s, a)$$

ただし、方策評価を全て行ってから、方策改善を行うという作業を繰り返すと、方策改善が行われるまでにかなりの時間を要することになります．そこで、方策評価が終わるまで待つのではなく、方策評価の途中で方策改善も行っていくこと計算効率を上げることができます．価値反復法と同様の考え方になります．

ここまでの内容をまとめると以下のようなアルゴリズムで書くことができます．

Monte Carlo ES
$Initialize, \;for \;all \;s \in S, \;a \in A(s):$
$\qquad Q(s,a) \leftarrow arbitrary$
$\qquad \pi (s) \leftarrow arbitrary$
$\qquad Returns(s,a) \leftarrow empty list$

$Repeat \;forever:$
$\qquad Choose \;S_0 \in S \;and \;A_0 \;in\ A(S_0) \;s.t. \;all \;pairs \;have \;probability \gt 0$
$\qquad Generate \;an \;episode \;starting \;from \;S_0, \;A_0 \;following \;\pi$
$\qquad For \;each \;pairs \;s, \;a \;appearing \;in \;the \;episode:$
$\qquad \qquad G \leftarrow return \;following \;the \;first \;occurrence \;of \;s, \;a$
$\qquad \qquad Append \;G \;to \;Returns(s, \;a)$
$\qquad \qquad Q(s,a) \leftarrow average(Returns(s,a))$
$\qquad For \;each \;s \;in \;the \;episode:$
$\qquad \qquad \pi(s) \leftarrow arg max_{a}Q(s,a)$

まとめ

今回はモンテカルロ法による行動価値の評価および方策改善についてまとめました．

次回は、ES（開始点探査）を行わないモンテカルロ法について整理する予定です．（ちょっと難しそうなので断言はできません）

2019-02-01

強化学習：モンテカルロ法（状態価値評価）

強化学習モンテカルロ法状態価値

今回の内容はSutton本5章のモンテカルロ法（Monte Carlo Method）についてです．

これは私の学習ノートです．詳しく知りたい方は、以下の記事を呼んでください．

qiita.com

おさらい

モンテカルロ法の説明のために、これまでまとめてきた方法について概要を示します．
以下にこれまで何度も出てきたバックアップ線図を示します．

f:id:shirakonotempura:20190126165021p:plain

状態 $s$ から方策 $a$ をとり、報酬 $R^a_{ss'}$ を得て状態 $s+1$ に遷移している様子を描いています．行動 $a$ を取る確率は方策 $\pi(s,a)$ で決まり、行動 $a$ をとったあとに状態 $s$ から状態 $s+1$ への遷移は遷移確率 $P^a_{ss'}$ によって確率的に決まります．つまり図中に描き切れないほど無数の枝分かれが存在します．

この枝分かれは、エピソードの終着点（Terminalとか言われます）まで繰り返されます．終着点がない場合は、無限に繰り返されることになります．（実際に計算するときは、もう十分だと考える未来まで枝分かれを考慮し、打ち切っていました）．

上のバックアップ線図をもとに、方策状態 $\pi$ に従った場合の状態状態 $s$ の価値を数式で表すと、以下のように書けます．

$$V^\pi (s) = \sum_{a} \pi (s,a) \sum_{s'}P^a_{ss'}[R^a_{ss'} + \gamma V^\pi (s')]$$

この式は、ある状態の価値はその後の状態の価値を用いて表すことができるということを示しています．これをブートストラップと呼びます．価値関数のブートストラップ性を利用して、状態価値関数を反復的に求めることができ、さらにそれを利用して前回は最適な方策を決めることができました．

バックアップ線図で書いたような、枝分かれを確率に従って辿っていき、価値を計算する方法を動的計画法（Dynamic Programming）と呼びます．

動的計画法の問題点

先の式の $[R^a_{ss'} + \gamma V^\pi (s')$ ]の部分は、枝分かれを進んで終着点にたどり着くまでに得られる報酬の総和です．それに方策および遷移確率を乗じているので、先の式で計算しているものは、全ての枝分かれを考慮した報酬の期待値となります．

前述のように動的計画法を使って、最適方策を求めることができましたが、ひとつ大きな制約があります．それは環境のダイナミクスが既知であるということです．

環境のダイナミクスが既知というのは、どういう行動をしたら何が起こるかということを把握できているということを意味します．Grid Worldの例で言えば、右に動くという行動を選択すれば、（遷移確率に従い）右に動こうとするし、グリッドAやBに到達すればA'、B'にワープするということを完全に分かっている状況のことを言います．

現実世界の環境では、行動とその後に起こることを完全に分かっている状況は決して多くありません．仮にあらゆる行動に対して起こりうる変化を全て把握できるとしても、それらをすべてモデリングしておくことは現実的ではありません．
もちろん、学習の対象によっては環境のダイナミクスが既知のケースもあるはずですので、これまでの方法が全く無意味というものではありません．

モンテカルロ法の登場

前段の説明が長くなりましたが、環境のダイナミクスが既知でないくても、これまでやってきたような価値の推定・方策の改善を行う方法がモンテカルロ法になります．

強化学習におけるモンテカルロ法では、エピソードに従ってエージェントは行動をとり報酬を得ます．各状態で実際に得られた報酬の平均をとることで期待値を計算します．

モンテカルロ法のイメージは、元の記事を参照ください．

モンテカルロ法による状態価値推定アルゴリズム

Sutton本5.1章に記載されている、モンテカルロ法を用いた状態価値推定アルゴリズムを以下に示します．これは、初回訪問（First Visit）モンテカルロ法と呼ばれるアルゴリズムになります．

$Initialize:$
$\qquad \pi \leftarrow \;policy \;to \;be \;evaluated$
$\qquad V \leftarrow \;an \;arbitrary \;state-value \;function$
$\qquad Returns(s) \leftarrow \;an \;empty \;list, \;for \;all \; s \in S$

$Repeat \;forever:$
$\qquad \;Generate \;an \;episode\; using \;\pi$
$\qquad \;For \;each \;state \;s \;appearing \;in \;the\;episode$
$\qquad \qquad \;G \leftarrow \;return \;following \;the \;first \;occurrence \;of \;s$
$\qquad \qquad \;Append \;G \;to \; Returns(s)$
$\qquad \qquad \;V(s) \leftarrow \;average(Return(s))$

実際は1つのエピソード中に複数回、同じ状態が観測される可能性があるのですが、初回訪問モンテカルロ法では、ある状態が観測されたときに『その状態が初めて観測された場合だけ』収益を計算しています．

一方で、初回以外の収益も足す方法は逐一訪問（Every-visit）モンテカルロ法と名前が付けられており、この場合は何度も観測された状態については、それぞれの状態で計算される収益の平均を用いることになります．

まとめ

モンテカルロ法で状態価値を推定するアルゴリズムについて整理しました．

次回も同じくモンテカルロ法ですが、行動価値の評価について整理してみます．

2019-01-31

強化学習：再帰処理と反復処理

強化学習マルコフ決定過程状態価値行動価値

前回、状態価値関数を定式化し、決まった方策のもとベストな行動を学習することができました．おそらくこのベストな行動を次の方策としていけば、最適な方策が見つかりそうな気がします．

ですが、実装してみると分かりますが、非常に計算時間が遅いです．誇張じゃなく、考慮する未来を3ステップ増やすだけで、お昼ご飯食べてお茶できるくらい時間が増えたりします．

これは私の学習ノートです．詳しく知りたい方は、以下の記事を呼んでください．

qiita.com

再帰処理と反復処理

先に結論から言うと、再帰処理と反復処理では、反復処理が圧倒的に計算時間が短くなります．圧倒的です．

いきなり再帰処理、反復処理と言ってもよくわからないと思いますので順番に見ていきます．

再帰処理

再帰処理は、これまで枝分かれのダイアグラムで説明してきた計算方法です．
図を省略するため、ある行動を選択した後の遷移確率は確定的（確率１でその行動を実施する）とさせてください．

f:id:shirakonotempura:20190131034155p:plain

図中の緑丸を起点（求めたい状態価値関数）だとします．この状態から、取りうる行動に対して枝分かれをしていきます（下に行くほど未来になります）．

今取った行動（黒丸）から次の状態（赤丸）に遷移します．緑丸の状態価値を求めるには、赤丸の状態価値が必要となります．しかし、緑丸と同様、赤丸の状態価値を求めるにはさらに未来の青丸の状態価値が必要となることが分かります．

この計算方法では状態・行動・その次の状態を使って、どんどん未来を掘り進めていく必要があるため、枝分かれ（考慮すべき未来）が指数関数的に増えていきます．そのため計算時間がバカになりません．

反復処理

次に反復処理による計算方法を紹介します．以下に計算のイメージ図を示します．ダイアグラムは再帰処理の場合と異なり、今の状態と次の状態で終わっています．

f:id:shirakonotempura:20190131034212p:plain

先と同様に、緑丸を起点（求めたい状態価値関数）、次の状態を赤丸で示しています．赤丸の状態価値関数には、適当な値（全部０でいいみたいです）を初期値として設定すればよいです．この赤丸の状態価値を使えば、緑丸の状態価値が分かります．当然、初期値が適当なので、求められる状態価値も変な値です．

今起点とした緑丸以外の全ての状態に対しても同様の計算行い値を更新していきます．この操作を図中の紫色の矢印で示しています．ここまでをk=0ステップとします．

k=0ステップで、上層の状態価値が更新されましたので、k=1ステップの下層の状態価値にそれを利用します．これを繰り返すことで、状態価値を適当に決めた0から反復的に更新させていくことができます．
枝分かれが２層しかないので、計算処理が早くなります．枝分かれが指数関数的に増えることに比べれば、反復回数が増えることの影響はわずかなものなので、再帰処理よりも早く収束します．

このアルゴリズムを方策反復評価（Iterative Policy Evaluation）と呼びます．

『その場更新型』バックアップ（In-place ）

上に示した説明では、上層（ $V(s)$ ）と下層（ $V(s')$ ）で2つの配列を持っています．手順としては、上層のスイープを全状態に対して終了してから、下層に代入し、再度上層のスイープというステップになっています．つまり、スイープ中は下層の状態価値は固定です．

より高速化を図った別の方法として、『その場更新（In-place）型』反復処理のアルゴリズムがあります．ｋのアルゴリズムは配列を１つしか使いません．つまりスイープの途中で、ある状態の更新が終われば、その結果を次の状態を更新する際の状態価値として使用します．

このアルゴリズムは、得られたデータをすぐに利用するので収束は早いとされる一方で、スイープの順番が大きく影響することになります．

Sutton本によれば、通常こちらの『その場更新（In-place）』型を用いるということです（4.1章）

方策反復評価のアルゴリズム

最後に、方策反復評価のアルゴリズムを示します．（これは『その場更新型』のアルゴリズムです）

$Input\; \pi ,\;the\;policy\;to\;be\;evaluated$
$Initialize\;an\;array\;V(s)=0,\;for\;all\;s\;\in S^+$
$Repeat$
$\qquad \Delta \leftarrow 0$
$\qquad For\; each\; s \in S:$
$\qquad \qquad v \leftarrow V(s)$
$\qquad \qquad V(s) \leftarrow \sum_{a}\pi(a|s)\sum_{s', r}p(s', r|s, a)[r + \gamma V(s')$ ]
$\qquad \qquad \Delta \leftarrow\;max(\Delta,|v-V(s)|)$
$until\;\Delta \lt \theta\;(a\;small\;positive\;number)$
$Output\;V \approx v_\pi$

ポリシーの改善

ここまでで、状態価値および行動価値、反復法による価値関数の更新について説明しました．ここから、ついにポリシー $\pi$ の改善に移っていきます．

ベストな行動と最適ポリシーの関係

ある状態 $s$ において、複数の行動が選択肢として与えらえているとします．この状態における最適なポリシー $\pi^*(s)$ とは、その名の通り、最もベストな行動を選ぶポリシーのことです．

ベストな行動はどうやって決めることができるかについて、以下の図を使って説明します．

f:id:shirakonotempura:20190131055121p:plain

緑の丸を起点の状態 $s$ になります．とりうる行動 $a$ は4つの黒丸で与えられています．この中のいずれかの行動がベストな行動になります．行動 $a$ を取った後で得られる収益は、状態遷移確率 $P^a_{ss'}$ を経て、報酬 $R^a_{ss'}$ および次の状態 $s'$ の価値関数 $V^\pi(s)$ で表されます．

f:id:shirakonotempura:20190131055137p:plain

グレーで囲んだこの収益は、各行動に対して計算されますので、この例の場合４つの収益が計算されます．この収益が最も高くなる行動を選ぶことが、状態 $s$ での最適なポリシー $\pi^*(s)$ となります．式で書くと、以下のように書くことができます．

$$\pi^*(s) = arg\ max_a \sum_{s'}P^a_{ss'}[R^a_{ss'} + \gamma V^\pi(s')]$$

ポリシーの改善

これまでの学習内容を整理します

あるポリシー $\pi$ があったとき、 - そのポリシーに従ったときの状態価値を求める（反復方策評価、iterative policy evaluation） - その状態での最適な方策 $\pi^*$ を求める（方策改善、policy improvement）

改善されたポリシー $\pi^*$ に従って新しい状態価値を求めれば、さらにその状態価値を使ってポリシーを改善していくことができます．

この繰り返しの作業を方策反復と呼びます

方策反復のアルゴリズム

初期化 Initialization

$V(s) \in R\;and \;\pi(s) \in A(s)\;arbitrarily\;for\;all\;s \in S$
方策評価 Policy Evaluation

$Repeat$
$\qquad \Delta \leftarrow 0$
$\qquad For\;each\;s\; \in S:$
$\qquad \qquad v \leftarrow V(s)$
$\qquad \qquad V(s) \leftarrow \sum_{a}\pi(a|s)\sum_{s', r}p(s', r|s, a)[r + \gamma V(s')$ ]
$\qquad \qquad \Delta \leftarrow\;max(\Delta,|v-V(s)|)$
$until \; \Delta \lt \theta$
方策改善 Policy Improvement

$policy{-}stable\leftarrow true$
$For\;each\;s \in S:$
$\qquad old-action \leftarrow \pi(s)$
$\qquad \pi(s) \leftarrow arg max_{a} \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')$ ]
$\qquad If\;old-action\neq \pi(s),\;then\;policy-stable\leftarrow false$
$If\;policy-stable,\; then\;stop\;and\;return\; V \approx v^* \; and \; \pi \approx \pi^*$ $;\; else\;go\;to\;2$