メインコンテンツへスキップ
見出し画像

Gymで強化学習⑧有限マルコフ決定過程

    前回の記事では具体例を通して状態価値関数、行動価値関数、ベルマン方程式などを復習しました。その際に、1次元のグリッド・ワールドを使いました。グリッド・ワールドを使ったのは状態の数が有限になり理解しやすいからです。また、行動も有限にして取り扱いやすくしました。

    状態と行動が有限なので状態価値関数や行動価値関数を配列や表にして表現することができます。このように表形式(Tabular)が使えるような環境におけるマルコフ決定過程を有限のマルコフ決定過程(Finite Markov Decision Process)と呼びます。

    有限のマルコフ決定過程では、最適なポリシーを見つけるための代表的な手法として以下があります。

    • 動的計画法

    • モンテカルロ法

    • TD法

    • SARSA

    • Q学習

    Richard Suttonが書いた有名な強化学習の本「Reinforcement Learning, An Introduction」では、有限のマルコフ決定過程における強化学習を解説する際に、動的計画法から段階的にQ学習へと知識を積み上げています。

    また、ディープマインドでアルファ碁などを研究開発したDavid Silverによる講義ビデオでも同様な順序に従っており、ほぼRichard Suttonの本の流れに従っています(彼の講義ビデオの中で上記の本を参照しています)。

    よって、この記事では動的計画法からQ学習への大まかな流れを上記のリストに従って解説します。

    動的計画法

    動的計画法(Dynamic Programming)は、環境における状態、報酬、行動の関係が確率的に完全にわかっている場合に有用な手法です。動的計画法は一般に大きな問題をより小さな問題に分割して計算し、その結果をより多くな問題を解くために利用する方法です。

    環境のモデルを完全に把握している場合、ある状態である行動をとったときにどのくらいの報酬が得られるのかがわかっています。しかし、ある状態の状態価値はわかっていません。これをベルマン方程式で解くことはできるでしょうか。

    ベルマン方程式では状態価値関数v(s)v(s)は状態st=ss_t = sから受け取る報酬rtr_tとその後の状態st+1s_{t+1}の状態価値v(st+1)v(s_{t+1})の合計の期待値を返します。

    v(s)≐E[rt+γv(st+1)∣st=s]v(s) \doteq \mathbb{E}[ r_t + \gamma v(s_{t+1}) | s_t = s]

    ≐\doteqは定義を意味します。

    ここには大きな問題とより小さな問題が相互に関係しています。つまり、状態価値関数v(s)v(s)の計算を大きな問題だとすると、それを分割して現在状態st=ss_t = sから受ける報酬rtr_tと、その次の状態st+1s_{t+1}の状態価値v(ss+1)v(s_{s+1})との合計の期待値というより小さい問題になっています。

    しかし、大きな問題とより小さな問題の両方で同じ状態価値関数を使っており、これではイタチごっこになってしまいます。なぜなら、環境のモデルを完全に把握していても状態価値関数はわかっておらず、状態価値関数を知るために状態価値関数そのものを知っていないとならないからです。

    これでは状態価値関数を計算するのは不可能に見えますが解決方法があります。

    例として状態価値関数の値をあるポリシーに従って計算したいとします。この場合、なんらかの値で状態価値関数を初期化しておきます。

    仮に、すべての状態における状態価値関数の値を0とします。

    v0(⋅)←0v_0(\cdot) \leftarrow 0

    初期化された状態価値関数をv0(⋅)v_0(\cdot)と呼びましょう。⋅\cdot(ドット)はどんな状態でもという意味です。

    次に、ある状態ssにおける状態価値関数を推定したいとします。ベルマン方程式による状態価値関数を更新するための式として以下のように捉え直します。

    vk+1(s)←Eπ[rt+γvk(st+1)∣st=s]v_{k+1}(s) \leftarrow \mathbb{E_\pi}[ r_t + \gamma v_k(s_{t+1}) | s_t = s ]

    ここではvkv_kで計算した情報を利用して、状態価値関数を更新したものをvk+1v_{k+1}と呼んでいます。つまり、より小さな問題で計算した値を利用してより大きな問題の計算に利用しているわけです。動的計画法ではこのような計算を繰り返し行います。

    例えば、初期の状態価値関数v0v_0から、状態価値関数を更新します。

    v1(s)←Eπ[rt+γv0(st+1)∣st=s]  =Eπ[rt∣st=s]\begin{aligned} v_1(s) &\leftarrow \mathbb{E_\pi}[ r_t + \gamma v_0(s_{t+1}) | s_t = s ] \\ &\ \ = \mathbb{E_\pi}[r_t | s_t = s ] \end{aligned}

    つまり、v0v_0はどんな状態に対しても0に初期化したので、最初の更新では状態価値関数の推定値はその状態における報酬値の期待値と等しくなります。

    なお、話を単純にするために状態価値関数の更新はすべての状態に対して同時に行われているものとしています。実際には状態を一つずつ訪れながら更新していくのでどの状態の値が先に更新されたかによって他の状態の更新のされ方が変わってきます。

    次の更新v2v_2ではv1v_1で計算した情報を利用できるので状態価値関数の推定値がより正確になります。これを何度も繰り返し状態価値関数の推定値の差の絶対値∣vk+1−vk∣| v_{k+1} - v_k |がある程度小さくなったら収束したとして状態価値関数の更新を止めます。

    なお、状態価値の差は状態ごとにあるので、その中で一番大きいものが設定した閾値しきいちより小さいかで判断します。

    max⁡s∈S∣vk+1(s)−vk(s)∣<閾値\max\limits_{s \in S} |v_{k+1}(s) - v_k(s)| < \text{閾値}

    また、このようにある初期値(これも推定値)から始めて推定値を更新していく手法をブートストラッピング(Bootstrapping)と呼びます。ブートストラッピングとは、推定値を計算するのに推定値を使う手法の総称です。

    英語で Pull yourself up by your bootstraps. (自分のブーツのストラップで自分を引き上げる)という言い回しは、他人からの助けに頼らずに自分自身の努力で状況を改善することを意味します。ここでは、状態価値関数をある初期値から始めて、推定値の計算に自らの推定を使うことを繰り返して推定値を改善していることを指します。

    環境のモデルを利用し、ブートストラッピングで状態価値関数を計算できれば、最適なポリシーは状態価値を常に最大にするように行動を選択し続けることで得ることができます。

    なお、何度も計算を繰り返す反復を使用した状態価値関数の更新の手法としてポリシー反復法(Policy Iteration)と価値反復法(Value Iteration)があります。次回の記事で解説します。

    動的計画法の問題点は、「環境のモデルが完全にわかっている」という条件があるために強化学習の環境で適用できないケースが多々あることです。また、状態、行動、報酬のパターンが増えると状態価値関数が収束するまでに繰り返す計算量がとても多くなります。

    次から現れる手法はどれも動的計画法と同じく最適な価値関数を計算できれば最適なポリシーが導き出せるという考え方では同じです。しかし、環境のモデルを完全に把握することを前提としません。また、より計算量が少なくて済むようになっています。

    モンテカルロ法

    モンテカルロ法(Monte Carlo Method)自体は、様々な経済や科学分野で使われる手法の総称です。ランダムに実行されるシミュレーションを通して統計的にある値の確率分布を予測します。これを強化学習に応用することで環境のモデルを予測します。

    つまり、モンテカルロ法が適用される強化学習では、環境のモデルがない状態から始まります。たくさんのエピソードを通して様々な状態、行動、報酬を経験することで状態遷移などの情報を統計的に獲得します。

    簡単に言うと、たくさんの状態、行動、報酬のサンプルを得て平均を計算することである状態における状態価値を予測する手法です。多くのサンプルを使えばベルマン方程式における状態価値関数v(st)v(s_t)の精度が上がっていきます。

    v(st)←average(gt(st))v(s_t) \leftarrow \text{average}( g_t(s_t) )

    gt(st)g_t(s_t)は状態sts_tからの生涯報酬gtg_tです。

    gt=rt+γgt+1g_t = r_t + \gamma g_{t+1}

    なお、gtg_tの計算はエピソードが終わった後に、最後の報酬から遡って計算します。

    このようにして、あらゆる状態に対する状態価値が推定できれば、常に最大の状態価値を持つ状態へと遷移する行動を選択することが最適なポリシーとなります。

    モンテカルロ法が動的計画法と大きく異なるのは、モンテカルロ法では経験から知識を得て予測をすることです。より学習の要素が加わっていると言えます。

    問題点は、エピソードを何度も繰り返さないと環境のモデルの予測精度が良くならないので学習に時間がかかることです。できるだけ多くの状態と行動と報酬を経験する必要があるからです。また、一つのエピソードが終わないと平均を計算して予測値の更新をすることができないので経験から得た知識をすぐに行動の選択に利用することができません。

    TD法

    TD法(Temporal Difference Method)は動的計画法とモンテカルロ法の考えを組み合わせたものです。動的計画法のようにベルマン方程式を繰り返し使って状態価値や行動価値を予測します。ただし、環境の完全なモデルを持たないのでモンテカルロ法のように経験から学ぶ必要もあります。

    なお、モンテカルロ法とは違ってエピソードが終わるのを待たずに状態価値や行動価値の予測を更新していきます。この意味では動的計画法と同様にブートストラッピングを行なっており、推定するために以前に推定した値を利用していることになります。

    しかし、動的計画法と異なり環境のモデルがないので、経験から得た情報を取り入れながら反復した計算を行います。

    その際、TD法では次のようにステップ間での状態価値関数の差を利用しています。

    v(st)←v(st)+α[rt+γv(st+1)−v(st)]v(s_t) \leftarrow v(s_t) + \alpha [ r_t + \gamma v(s_{t+1}) - v(s_t)]

    つまり、もとの状態価値関数v(st)v(s_t)と新たな情報を取り入れた状態価値rt+γv(st+1)r_t + \gamma v(s_{t+1})との差を計算してより新しい情報を取り入れていく手法になています。

    α\alphaは学習率です。0から1の値になります。よく、0.01などの値を使い現在の行動価値関数の値を大きく残しながらも新しい値を取り込むようになっています。そうすることで行動価値関数が安定し大きく変動することがないからです。ただし、学習率は、ハイパーパラメータ(hyper-parameter)なので自分で調節する必要があります。

    例えば、状態価値をすべてゼロに初期設定しておき、ある状態である行動を行うたびにベルマン方程式を使って行動価値を更新して更新します。

    この手法では、エピソードの終了を待たずに状態価値や行動価値を更新していくのでモンテカルロ法よりもはやい時点で経験から得た知識を利用できるので学習が速く進む利点があります。

    もちろん、最初はデタラメな予測になる可能性が高いですが、経験を通して予測の精度が徐々に上がっていきます。

    TD法に基づいたポリシーには大きく分けて、オン・ポリシー(On-Policy)とオフ・ポリシー(Off-Policy)があります。

    ちなみに、オン・ポリシーをオン方策型、オフ・ポリシーをオフ方策型と呼ぶ日本語訳もよく見受けます。どちらでも意味が通じれば良いでしょう。この記事ではポリシーを方策とは呼んでいないので、オン・ポリシーとオフ・ポリシーで統一します。

    オン・ポリシーとオフ・ポリシーのTD法の代表として、それぞれSARSAとQ学習があります。

    SARSA

    SARSAの名前は、状態→行動→報酬→状態→行動を表す英語State、Action、Reward、State、Actionの頭文字からきています。英語発音だとサァサと巻き舌のRを入れながら発音するようですが、日本語ではなんと呼ぶのでしょうか。サルサでしょうか(知りません)。

    SARSA(とQ学習)では行動価値関数を使ったブートストラッピングを行います。例えば、次のような行動決定過程があったとします。

    st,at,rt,st+1,at+1s_t, a_t, r_t, s_{t+1}, a_{t+1}

    ここでは状態sts_t、行動ata_t、報酬rtr_t、状態st+1s_{t+1}、行動at+1a_{t+1}が経験されました。この経験を使って行動価値関数をq(st,at)q(s_t, a_t)に対して次のようにベルマン方程式を使って行動価値の更新します。

    q(st,at)←q(st,at)+α[rt+γq(st+1,at+1)−q(st,at)]q(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha [ r_t + \gamma q(s_{t+1}, a_{t+1}) - q(s_t, a_t)]

    rt+γq(st+1,at+1)r_t + \gamma q(s_{t+1}, a_{t+1})が経験から得た報酬を取り込んだ行動価値の予測になります。また、q(st,at)q(s_t, a_t)は新しい経験を取り入れる前の行動価値の予測なので、新しい予測と以前の予測との差を計算して、その差が縮まるようにq(st,at)q(s_t, a_t)を更新しています。

    ちなみに、上記の更新式は以下のようにも書き換えれれます。この方が分かりやすいと感じるかもしれません。同じことではありますが。

    q(st,at)←(1−α) q(st,at)+α[rt+γq(st+1,at+1)]q(s_t, a_t) \leftarrow (1 - \alpha)  q(s_t, a_t) + \alpha [ r_t + \gamma q(s_{t+1}, a_{t+1})]

    さて、行動価値関数q(s,a)q(s, a)を使って、ある状態ssにおける最大価値を与える行動arg⁡max⁡aq(s,a)\arg\max\limits_{a} q(s, a)を選ぶとすると、探索がまったくなく搾取だけになってしまいます。よって、ランダムな行動を選択するようにϵ\epsilon(イプシロン)-greedy法を使います。

    ϵ\epsilonはある確率によってときどき探索をすることを意味します。また、greedy(グリーディ、貪欲)は搾取を行うことなので、ときどき探索しながら普段は搾取するという手法になります。

    なお、ϵ\epsilonの値はエピソードが進むと徐々にゼロへと導かれるようにするので最終的には搾取だけとなりランダムな行動はなくなります。よって、それまでに十分な学習を終える必要があります。

    さて、上記の更新式では、実際の経験からの情報を使っています。つまり、ポリシーに従って得た行動価値であるq(st,at)q(s_t, a_t)とq(st+1,at+1)q(s_{t+1}, a_{t+1})の値を使っています。このことをオン・ポリシーと呼びます。

    何も問題なさそうですが、オン・ポリシーだと探索によるランダムな行動も上記の更新に含まれてしまいます。よって、現状の知識からの最善な行動価値を使わないケースも出てきます。

    次に見るオフ・ポリシーのQ学習とはこの点で異なります。

    Q学習

    Q学習(Q-Learning)は次のようにベルマン方程式を使った行動価値の更新を行います。

    q(st,at)←q(st,at)+α[rt+γmax⁡aq(st+1,a)−q(st,at)]q(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha [ r_t + \gamma \max\limits_{a} q(s_{t+1}, a) - q(s_t, a_t)]

    上記の更新式では、実際の経験からの値q(st+1,at+1)q(s_{t+1}, a_{t+1})を使っていません。むしろ、現在の行動価値関数において最善な行動を状態st+1s_{t+1}で取った場合の値max⁡aq(st+1,a)\max\limits_{a} q(s_{t+1}, a)をを使用しています。

    これは現時点の経験と知識から知り得る最善なポリシーに従うことになり、実際に使われたポリシーとは異なるポリシー、つまりはオフ・ポリシーな行動決定による行動価値の評価を次の状態に対して行なっています。

    よって、ϵ\epsilon-greedyによる探索を行いつつも行動価値の更新は現時点で知り得る最善なポリシーに従うようになっています。

    このため、SARSAと違って探索によるランダムな行動からの行動価値を使って更新するということもなく、より最適なポリシーに従う行動価値の評価と更新を行なっているので学習より進むにつれてより効率的になります。

    有限でないマルコフ決定過程

    最後に、有限でないマルコフ決定過程について少しだけ触れます。

    有限でない状態を扱うには、それを分割して有限な区間を一つの状態として扱うことで対処することができる場合があります。これは結局のところ有限なマルコフ決定過程に変換しているだけではあります。

    また、分割の仕方によってはうまくいかない可能性もあります。さらに、分割しても状態の数が多すぎてなかなか収束しないこともあり得ます。

    もう一つの方法としてはディープラーニングを使って有限でない状態をそのまま扱う方法です。ここでは状態価値関数や行動価値関数がニューラルネットワークに置き換わるので表形式の状態管理などは行いません。

    次回は動的計画法を具体的にプログラムに書いて実験します。

    (続く)

     
     
    「わかりやすく、具体的に」AIとサイエンスの情報を発信中

    あなたへのおすすめ