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

Gymで強化学習⑨動的計画法:理論編

    前回の記事では有限マルコフ決定過程において最適なポリシーを見つけるための代表的な手法をざっと見渡しました。この記事ではその中で最初に取り上げられた動的計画法の理論を詳細に解説します。そして次回の記事では実際にコードを交えて動的計画法をGymの環境を使って解説します。

    動的計画法を学ぶ意義

    まず、動的計画法を学ぶ意義について解説します。動的計画法は、環境における状態、報酬、行動の関係が確率的に完全にわかっている場合に有用な手法です。

    動的計画法はよく強化学習の本などで最初の方に登場します。しかし、なぜ有限な環境を想定するのか。また、環境の完全なモデルを想定するのではあまり実用性がないのではないか。

    こういった疑問が湧くかもしれません。

    まず、有限であるとは、状態と行動の組み合わせに限りがあり、さらに状態遷移の確率が知られていることを指します。そのことを利用すると状態価値関数の計算をディクショナリや表などを利用して計算できます。

    つまり、有限な環境を想定すると、実際に計算することができ理解がしやすくなります。後で「有限である」から「有限ではない」環境(状態、行動)への拡張をすることもできます。

    有限でない場合は状態価値関数などが連続な値を取り扱うことになりますが、最適なポリシーの見つけるためのアプローチに変わりはありません。よって有限マルコフ決定過程における手法を学ぶ・研究することを強化学習の第一歩として位置付けることは我々の学習を効率良くすることになります。決して無駄ではありません。

    逆に、有限マルコフ決定過程における手法をよく理解しておかないと後で躓く可能性があります。

    また、動的計画法には大切な考え方がたくさん含まれています。ここで使われる手法は他の有限マルコフ決定過程の手法に共通することが多いです。

    もちろん、有限マルコフ決定過程だと扱える問題に制限がありますが、前述したように「有限である」から「有限ではない」環境(状態、行動)への拡張をすることができます。

    それに対しては二つのアプローチがあります。

    一つ目の対策は、連続値をとる状態や行動を有限な区間に分けることで離散的に扱う方法です。問題によっては状態と行動の離散化よって有限マルコフ決定過程における手法がそのまま適用できます。

    二つ目の対策は、状態価値関数や行動価値関数が連続値を扱えるように拡張する手法です。ディクショナリや表などの代わりに連続値を扱う関数を状態価値関数と行動価値観数として求めます。その上で有限マルコフ決定過程における手法と同様なアプローチを適用します。

    有名なのは深層強化学習で状態価値や行動価値を計算にディープラーニングのモデルを使います。また、それらの関数はエージェントが経験を繰り返すことで学習されます。

    有限マルコフ決定過程における手法は状態価値や行動価値を計算することができれば適用できるので、上記のような拡張を施すことで有限な環境でなくとも応用ができるようになります。

    なのでこの先で躓つまずくことがあったら動的計画法を見直してみてください。

    ポリシーを改善するとは

    動的計画法は、簡単にいうと繰り返し状態価値関数を更新しながら、ポリシーを改善していく手法です。そのためにはまず、ポリシーを改善するとは何なのかを理解する必要があります。

    最適なポリシーを見つけるためには、まずポリシーを評価できることが必要です。ポリシーが評価できればどのポリシーがより最適であるかを比較することができるからです。

    ではポリシーを評価し比較するとはどういうことなのかを解説します。

    まず、ポリシーを評価するにはある状態ssにおいて期待される生涯報酬の総和を計算します。つまり、このポリシーπ\piによる状態価値関数を使います。

    vπ(s)v_\pi(s)

    この値が高いほどそのポリシーはその状態においてより最適であると言えます。

    よって、二つのポリシーπ′\pi'とπ\piを比べるには、この二つのポリシーによる状態価値関数の値を比べれば良いことになるます。

    vπ′(s)>vπ(s)v_{\pi'}(s) > v_{\pi}(s)

    この場合、状態ssにおいて、ポリシーπ′\pi'の方がポリシーπ\piよりも最適であると言えます。

    そこでポリシーπ\piを改善してより最適なポリシーへと改善することを考えます。より最適なポリシーになるためには状態ssにおいてポリシーπ\piが選ぶ行動aaよりも最適な行動a′a'を選択する必要があります。「より最適」とは、行動による状態遷移によって期待される生涯報酬がより高くなることを意味します。

    ここで話を単純にするためにポリシーπ\piによって状態ssにおける行動aaが一意に決まるとします。ポリシーを確率ではなく、行動の値を直接出力するものとします。

    a=π(s)a = \pi(s)

    すると、状態価値関数vπv_\piは行動価値関数qπq_\piで次のように表現できます。

    vπ(s)=qπ(s,π(s))v_\pi(s) = q_\pi(s, \pi(s))

    このポリシーπ\piによる行動選択よりも最適な行動を選ぶポリシーをπ′\pi'とするならば、状態ssにおいてより最適な行動を選択することを次のように表現できます。

    qπ(s,π′(s))> qπ(s,π(s))q_\pi(s, \pi'(s)) > q_\pi(s, \pi(s))

    つまり、状態ssにおいて、ポリシーπ′\pi'による状態価値関数がポリシーπ\piによる状態価値関数よりも高い値を返すことになります。

    vπ′(s)>vπ(s)v_{\pi'}(s) > v_\pi(s)

    このポリシーの改善をあらゆる状態において行えばどのポリシーよりも最適なポリシーへと改善していくことができるはずです。これがポリシーを改善することの意味です。

    一般にs∈Ss \in Sをすべての可能な状態とすれば、最適なポリシー∗*は、その他のポリシーπ\piに対して、次の条件を満たします。

    v∗(s)≥vπ(s),s∈Sv_*(s) \ge v_\pi(s), \quad s \in S

    つまり、最適なポリシーはあらゆる状態においてその他のすべてのポリシーよりも最適あるいは同等であることになります。

    なお、有限マルコフ決定過程では可能なポリシーの数も有限にはなるのですが、状態や行動の数によって考慮する状態・行動の組み合わせの数は急激に大きくなります。

    入門的な意味で紹介される動的計画法ではあまり大きくない状態数・行動数を扱うことを前提とすることがほとんでです。なぜなら後に見るように動的計画法では状態価値関数と行動価値関数を何度も何度も繰り返し更新する必要があり収束するまでに時間がかかるからです。

    ただし、より多くの状態を扱えるように非同期性などを導入してエンジニアリングによる高速化を行うことも可能です。これについては理論の理解には不要なのでこの記事では扱いません。

    次に状態価値関数と行動価値関数の復習をします。後で解説するポリシー反復法と価値反復法で必要となるからです。

    ポリシーの評価

    ここまで状態価値関数や行動価値関数の詳細については触れませんでした。ここでは、ポリシーの評価をする際に必要な数式を復習します。

    強化学習ではベルマン方程式を土台として理論を構築します。これは動的計画法においても同様です。ベルマン方程式の利点は無限に続く可能性のある状態価値関数や行動価値関数を現在と将来に分けることで扱いやすくできることです。

    まずは、簡単にポリシーや価値関数などを復習しながらベルマン方程式を再導入しましょう。

    ポリシーをπ(a∣s)\pi(a | s)と表現します。これはある状態st=ss_t = sにおいて行動at=aa_t = aを選択する確率を表します。さらに、ポリシーπ\piに従う状態価値関数vπv_\piは以下のように表現できます。

    vπ(s)≐Eπ[gt∣st=s] v_\pi(s) \doteq \mathbb{E}_\pi[g_t | s_t = s] 

    ここでgtg_tは状態st=ss_t = sからスタートすることで得られる報酬の総和です。これを報酬過程として表現すると以下になります。

    gt=rt+γrt+1+γ2rt+2+… =∑k=0∞γkrt+kg_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots  = \sum\limits_{k=0}^\infty \gamma^k r_{t+k}

    γ\gamma(ガンマ)は割引率です。

    この一連の報酬はポリシーによって選択される行動に左右されます。つまり、gtg_tが実際どのような値を取るのかはポリシーによるので期待値はEπ\mathbb{E}_\piとπ\piをつけて表現しています。

    まとめると、上式の状態価値関数はポリシーπ\piに従うエージェントが状態st=ss_t = sにいることで得られる報酬の総和の期待値です。しかし、このままだと数式として無限に続く可能性のある報酬過程を内包しており扱いが簡単ではありません。

    よって、ベルマン方程式を使って式を現在の報酬と将来に渡る報酬の総和に分けることで無限を表現することにします。

    vπ(s)≐Eπ[gt∣st=s]=Eπ[rt+γgt+1∣st=s]\begin{aligned} v_\pi(s) &\doteq \mathbb{E}_\pi[g_t | s_t = s] \\ &= \mathbb{E}_\pi [r_t + \gamma g_{t+1} | s_t = s] \end{aligned}

    これが成り立つのは報酬過程を次のように書き換えられるからです。

    gt=rt+γrt+1+γ2rt+2+…=rt+γ(rt+1+γrt+2+… )=rt+γgt+1\begin{aligned} g_t &= r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots \\ & = r_t + \gamma (r_{t+1} + \gamma r_{t+2} + \dots) \\ &= r_t + \gamma g_{t+1} \end{aligned}

    上記のベルマン方程式におけるgt+1g_{t+1}の期待値は同じポリシーによる状態価値関数として書き直せます。

    vπ(st+1)=Eπ[gt+1∣st+1]v_\pi(s_{t+1}) = \mathbb{E}_\pi[g_{t+1} | s_{t+1}]

    ここで状態をst+1s_{t+1}としているのは次の状態がどうなるのかはポリシーや環境における状態遷移に依存するからです。これと比較すると現在の状態はst=ss_t = sで確定しています。

    以上を取り入れると状態価値関数は以下になります。

    vπ(s)≐Eπ[gt∣st=s]=Eπ[rt+γgt+1∣st=s]=Eπ[rt+γvπ(st+1)∣st=s]\begin{aligned} v_\pi(s) &\doteq \mathbb{E}_\pi[g_t | s_t = s] \\ &= \mathbb{E}_\pi [r_t + \gamma g_{t+1} | s_t = s] \\ &= \mathbb{E}_\pi [r_t + \gamma v_\pi(s_{t+1}) | s_t = s] \end{aligned}

    状態価値関数vπv_\piの計算には状態価値関数vπv_\piそのものが必要なことに注意してください。これについては後でブートストラッピングと共に解説します。

    さらに、ポリシーπ\piにおける期待値Eπ\mathbb{E}_\piをポリシーの確率関数で表現できます。

    vπ(s)≐Eπ[gt∣st=s]=Eπ[rt+γgt+1∣st=s]=Eπ[rt+γvπ(st+1)∣st=s]=∑aπ(a∣s) E[rt+γvπ(st+1)∣st=s,at=a]\begin{aligned} v_\pi(s) &\doteq \mathbb{E}_\pi[g_t | s_t = s] \\ &= \mathbb{E}_\pi [r_t + \gamma g_{t+1} | s_t = s] \\ &= \mathbb{E}_\pi [r_t + \gamma v_\pi(s_{t+1}) | s_t = s] \\ &= \sum\limits_a \pi(a | s)  \mathbb{E} [r_t + \gamma v_\pi(s_{t+1}) | s_t = s, a_t = a] \end{aligned}

    E[rt+γvπ(st+1)∣st=s,at=a]\mathbb{E} [r_t + \gamma v_\pi(s_{t+1}) | s_t = s, a_t = a]はある状態st=ss_t = sにおいて行動at=aa_t = aを選んだ時に得られる生涯報酬の期待値です。これとポリシーが状態st=ss_t = sで行動at=aa_t = aを取る確率π(a∣s)\pi(a|s)との積の和を計算することでポリシーによる状態価値関数の期待値しています。この部分がEπ\mathbb{E}_\piにおけるπ\piの意味です。

    なお、E[⋅]\mathbb{E} [ \cdot ]の中にvπ(st+1)v_\pi(s_{t+1})が入っており、それがポリシーπ\piに依存するのに変わりはありません。ただ、E\mathbb{E}が意味する期待値の計算そのものは状態遷移の確率によって決まります。

    この状態遷移の確率とは、状態ssで行動aaを選択した時に状態s′s'に移行して報酬rrを受け取る確率でp(s′,r∣s,a)p(s', r | s, a)と表現できます。ここで報酬が確率関数の縦線の左側に入っているのは報酬が状態や行動などに依存したり報酬自体にランダム性がある場合を考慮しています。

    仮に、報酬が状態によって一意に決まるのだとしたらr=r(s)r = r(s)だし、報酬が行動と状態遷移によって決まるのならr=r(s,a,s′)r = r(s, a, s')とも表現できます。上記の表記p(s′,r∣s,a)p(s', r | s, a)を使うことでどのようなケースでもカバーできます。

    では、状態遷移の確率を使って期待値E\mathbb{E}の部分を書き換えます。

    vπ(s)≐Eπ[gt∣st=s]=Eπ[rt+γgt+1∣st=s]=Eπ[rt+γvπ(st+1)∣st=s]=∑aπ(a∣s) E[rt+γvπ(st+1)∣st=s,at=a]=∑aπ(a∣s) ∑s′,rp(s′,r∣s,a)[r+γvπ(s′)]\begin{aligned} v_\pi(s) &\doteq \mathbb{E}_\pi[g_t | s_t = s] \\ &= \mathbb{E}_\pi [r_t + \gamma g_{t+1} | s_t = s] \\ &= \mathbb{E}_\pi [r_t + \gamma v_\pi(s_{t+1}) | s_t = s] \\ &= \sum\limits_a \pi(a | s)  \mathbb{E} [r_t + \gamma v_\pi(s_{t+1}) | s_t = s, a_t = a] \\ &= \sum\limits_a \pi(a | s)  \sum\limits_{s', r} p(s', r | s, a) [r + \gamma v_\pi(s')] \\ \end{aligned}

    つまり、ある状態ssにおける行動aaの確率とその状態と行動による状態遷移(状態の変化と受ける報酬)の確率を全て考慮して現在の報酬と生涯報酬の和の期待値を計算しています。

    ϵ\epsilon-greedy(イプシロン・グリーディ)法などを使用せずに、行動が状態によって一意に決まるのであれば、π(s)\pi(s)を状態ssにおける行動aaを一意に選択する関数として、以下のように状態価値関数を定義できます。

    vπ(s)=∑s′,rp(s′,r∣s,π(s))[r+γvπ(s′)]v_\pi(s) = \sum\limits_{s', r} p(s', r | s, \pi(s)) [r + \gamma v_\pi(s')]

    しかし、ここで一つ問題があります。そもそも上記の状態価値関数をどう計算するのでしょうか。仮にあるポリシーが存在するとして、このポリシーによる状態価値関数をどう計算するのでしょうか。

    問題の核心は状態価値関数vπv_\piの計算に状態価値関数vπv_\piそのものが入っていることです。これは無限を表現するために必要ですが、実際に計算するとなると状態価値関数がわかっていない段階では身も蓋もありません。

    そこで前回紹介したブートストラッピングの手法が登場します。

    まず、状態価値関数を何らかの値で初期化します。これが最初の推測値となります。ランダムな値でも構いませんが、ここではすべての状態価値を0とします。

    v(s)←0,s∈Sv(s) \leftarrow 0, \quad s \in S

    ここで状態価値関数をvπv_\piではなくvvとしているのは、まだこのポリシーの状態価値関数がわかっていないからです。

    Python風に書くと状態価値関数を状態ssをキーとしたディクショナリとして次のようになります。大文字のSSは状態のリストです。

    # 状態価値関数の初期化
    for s in S:
        v[s] = 0

    さらに、以下はvvをポリシーπ\piに従って評価し更新するファンクションをPythonコード風に書いています。

    def policy_evaluation(policy, v):
        # 更新前後の価値関数の差の最大値が閾値より小さくなるまで続ける
    
        while True:
    
            delta = 0
    
            for s in S:
                # 更新前の状態価値関数の値
                old_v = v[s]
    
                # 状態価値関数を更新        
                v[s] = calculate_value(policy, s, v)
    
                # 前回の価値関数との最大の差
                delta = max(delta, abs(old_v - v[s]))
    
            if delta < THRESHOLD:
                break

    calculate_value(policy, s, v) ではある状態ssにおけるこのポリシーによる状態価値関数の値を計算しています。つまり、以下の部分です。

    v(s)←∑s′,rp(s′,r∣s,π(s))[r+γv(s′)]v(s) \leftarrow \sum\limits_{s', r} p(s', r | s, \pi(s)) [r + \gamma v(s')]

    ここではポリシーπ\piが確率的ではなく状態ssに対して一意の行動aaを返すもとのしています。

    矢印を使っているのは、上式によって状態ssにおける状態価値関数の値を更新しているからです。更新の際に推測値であるv(s′)v(s')を使っているのがブートストラッピング法になります。

    なお、繰り返しますが、v(s′)v(s')をvπv_\piではなくvvとしているのは、この状態価値関数は収束するまでは、ポリシーπ\piの状態価値関数の近似とは言えないからです。

    上記の計算を何度も繰り返すことで推測された状態価値関数の値が収束していきます。

    更新された状態価値関数の値と前回の状態価値関数からの値との差の最大値が指定した閾値しきいち(THRESHOLDで指定)よりも小さくなったらループを抜けて更新を終了します。

    以上により、あるポリシーにおける状態価値関数の推定が可能となります。さらに、ポリシーの改善を付け加えれば最適なポリシーを見つけることができるはずです。

    ポリシー反復法

    ポリシーの一部を変更するとその後の決定過程に影響が出るので、状態価値関数も更新する必要があります。これは状態価値関数がポリシーに依存していることを考えれば当然と言えます。

    よってポリシーの改善(変更)を行った後にはポリシーの再評価(更新)が必要になります。さもないと次にポリシーの改善を行う際に古いポリシーの状態価値関数と比較することになるので意味がありません。

    このようにポリシーの評価と改善を繰り返すことでポリシーを最適化します。この手法をポリシー反復法(Policy Iteration)と呼びます。イテレーションとは反復する、何度も繰り返すという意味です。

    ポリシーの評価は状態価値関数によって決まります。そして、ポリシーの改善は状態によって選択する行動を変更することで行われます。この二つを何度も繰り返すことでポリシーが最適化されていくわけです。

    ポリシーを改善するには、ある状態ssにおいて行動を選ぶ際に、次の状態に遷移することで得られる状態価値の期待値が最大になる行動aaを選びます。

    π(s)←arg⁡max⁡a∑s′,rp(s′,r∣s,a)[r+γv(s′)]\pi(s) \leftarrow \arg\max\limits_a \sum\limits_{s', r} p(s', r | s, a) [ r + \gamma v(s')]

    ここでのπ(s)\pi(s)はある状態ssに対して行動を一意に返すファンクションです。確率的なポリシーを使っても期待値の計算が変わるだけですが、簡単のためにこうしています。

    ∑s′,rp(s′,r∣s,a)[r+γv(s′)]\sum\limits_{s', r} p(s', r | s, a) [ r + \gamma v(s')]の部分は、状態ssにおいて行動aaを選んだ時の状態価値の期待値です。遷移する状態は複数あり、確率的に決まることを想定しています。

    ポリシーは状態ssをキーとして行動aaを返すディクショナリとします。行動は状態によって一意に決まると想定しているので、各状態にランダムな行動を設定しておきます。Python風に書いてみます。

    # ポリシーの初期化
    for s in S:
        policy[s] = random.choice(A) # 行動のセットAからランダムに選択

    ポリシーを改善するファンクションをPython風に書いてみると以下になります。

    def policy_improvement(policy, v):
        done = True
    
        for s in S:
            # 更新前のポリシーによる行動選択
            old_a = policy[s]
    
            # 行動選択を更新
            policy[s] = calculate_best_action(policy, s, v)
    
            # 前回の価値関数との最大の差
            if old_a != policy[s]:
                done = False # まだポリシーが安定していない
    
        return done

    calculate_best_action(policy, s, v) は状態ssにおいて最大の状態価値の期待値を出す行動を選択しています。

    ここでもブートストラッピングが使われているのでポリシーと状態価値関数がデタラメな初期の頃は最適な行動を選びませんが、ポリシーの改善とポリシーの評価を繰り返すうちに最適化されていきます。

    すべての状態においてポリシーの改善前後で行動選択が一致するならば、これ以上の改善は必要ないので done=True が返されます。

    ポリシーの評価と改善のファンクションを組み合わせるとポリシー反復法は以下のようになります。

    # ポリシーの初期化
    for s in S:
        policy[s] = random.choice(A) # 行動のセットAからランダムに選択
    
    # 状態価値関数の初期化
    for s in S:
        v[s] = 0
    
    # done = True になるまでポリシー反復法を繰り返す。
    done = False
    
    while not done:
        policy_evaluation(policy, v)
        done = policy_improvement(policy, v)

    あくまでもPython風に書いたもので実行はできませんが、実行されたとすると最終的に v と policy はポリシー評価の閾値を満たす範囲内で最適化されていることになります。

    価値反復法

    ポリシー・イタレーションの欠点としては毎回ポリシーの評価をすべての状態を使って閾値が満たされるまで繰り返し行う必要があることです。

    もちろん、その理由はブートストラッピングによって状態価値関数を推測する上で何度もループを繰り返さないと推測値からより正確な値へと近づいていかないからです。

    しかし、ポリシーの評価とポリシーの改善を交互に何度も繰り返すのであれば、ポリシーの評価が収束するのを毎回待つ必要があるのでしょうか。実際にはその必要がないことがわかっています。毎回、完全な収束を待たずに数回のループを繰り返すだけでも最終的には最適ポリシーを生み出すことができます。

    つまり、ポリシーの評価が完全に終わるまで待つ必要がなく、行動の選択は状態価値関数が最大の値を返す行動を選ぶことであるならば、状態価値観数の更新をする際に常に最大の値に更新してはどうでしょうか。

    v(s)←max⁡a∑s′,rp(s′,r∣s,a)[r+γv(s′)]v(s) \leftarrow \max\limits_a \sum\limits_{s', r} p(s', r | s, a) [ r + \gamma v(s') ]

    このように更新した状態価値関数が収束したならば、最適なポリシーは
    常に状態価値関数の最大値を選ぶものになります。よって、ポリシーを設定する必要もありません。

    このように状態価値関数の改善を行う手法を価値反復法(Value Iteration)と呼びます。

    まず、状態価値関数を何らかの値で初期化します。ここでは0を設定しています。

    # 状態価値関数の初期化
    for s in S:
        v[s] = 0

    次に価値反復法を行います。

    このファンクションはポリシー反復法におけるポリシーの評価とほぼ同じですが、ここでのポリシーは状態価値関数を使って最大の値が出る行動を選ぶものと想定されています。よってポリシーを別に定義する必要がありません。

    def value_iteration(v):
        # 更新前後の価値関数の差の最大値が閾値より小さくなるまで続ける
    
        while True:
    
            delta = 0
    
            for s in S:
                # 更新前の状態価値関数の値
                old_v = v[s]
    
                # 状態価値関数を更新        
                v[s] = calculate_max_value(s, v)
    
                # 前回の価値関数との最大の差
                delta = max(delta, abs(old_v - v[s]))
    
            if delta < THRESHOLD:
                break

    calculate_max_value(s, v) では状態ssからの生涯報酬の期待値を最大にする行動を選んでいることを前提としています。

    価値反復法が収束すると最適なポリシーは最適な状態価値関数を使って、次のように定義できます。

    π∗(s)=arg⁡max⁡a∑s′,rp(s′,r∣s,a)[r+γV∗(s′)]\pi_*(s) = \arg\max\limits_a \sum\limits_{s', r} p(s', r | s, a) [ r + \gamma V_*(s')]

    価値反復法は、ポリシー反復法におけるポリシーの評価とポリシーの改善を一つのループにまとめたものとして取られることができます。

    こうしてみると価値反復法だけで良さそうですが、実際にはポリシー反復法も使われます。

    というのも動的計画法において、ポリシー反復法と価値反復法のどちらを選択すべきかは複数の要因に依存します。

    例えば、価値反復法では状態価値関数を最大化する行動をするので、状態価値関数の更新を行うたびに暗にポリシーが変更されているのと同じことになります。このため場合によっては状態価値関数の収束が不安定になり長い時間がかかる可能性があります。

    つまり、ポリシー反復法と価値反復法のどちらが優れているかは、環境の特性に依存します。よって、両方のアルゴリズムを実験し性能を比較することを推奨します。

    (続く)

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

    あなたへのおすすめ