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

Gymで強化学習⑯TD学習法:理論編

    前回はモンテカルロ法の実装を行いました。この強化学習のシリーズではこれまで動的計画法とモンテカルロ法の理論と実装を行ってきましたが、この両方の知識を組み合わせたものがTD学習法となります。

    なぜTD学習法?

    TD学習法では、モンテカルロ法のように経験から学習します。さらに、動的計画法のようにブートストラッピングを行います。つまり、エピソードが終わるのを待つ必要はありません。つまり、経験から得た情報をすぐに状態価値関数や行動価値関数に反映することができます。

    また、たくさんの強化学習の手法はTD学習法の考え方を土台としています。例えば、TD学習法を基にした手法として、オンポリシーではSARSA、オフポリシーではQ学習がそれぞれ有名です。よって、TD学習法を理解することは重要であり、TD学習法は強化学習において一番応用が効く概念だとも言えます。

    なお、TDとはTemporal-Difference(時差、時間差)のことです。ここでの時間差とは、エピソード内で生じるステップのことです。ステップttの状態ssで行動aaを選択して報酬rrを受け取り、次のステップt+1t+1で新しい状態に移り、また行動選択をするという経験を繰り返しますが、ここでステップttからt+1t+1と遷移するのが時計の針が動くようなイメージでTD(時間差)と呼んでいます。ただし、実際の時間の経過とは関係はありません。

    画像
    ステップごとに学習が進む

    上図のようにTD学習法ではステップごとに学習が進んでいきます。このためTD学習法ではさまざまな利点があります。これについては、後述します。

    まずは、TD学習法を動的計画法とモンテカルロ法の概念を組み合わせて導出しましょう。

    平均値の計算方法を変える

    モンテカルロ法ではエピソードごとに集めた生涯報酬のサンプルの平均を使って状態価値や行動価値の予測をしました。初回訪問と逐一訪問で訪問数の計算の違いはありますが、最終的には生涯報酬のサンプルの総和を訪問回数で割るという手法に変わりはありません。

    仮にある状態ssから得た生涯報酬のサンプルがg1,g2,…,gNg_1, g_2, \dots, g_NとN個あったとします。すると、その平均が状態ssの状態価値の予測値vN(s)v_N(s)となります。

    vN(s)=g1+g2+⋯+gNNv_N(s) = \dfrac{g_1 + g_2 + \dots + g_N}{N}

    上記の式を次のように書き換えます。

    vN(s)= g1+g2+…gN−1N+ gNN= g1+g2+…gN−1N−1N−1N+ gNN=vN−1(s)(1−1N)+gNN=vN−1(s)+1N [gN−vN−1(s)]\begin{aligned} v_N(s) &= \dfrac{g_1 + g_2 + \dots g_{N-1}}{N} + \dfrac{g_N}{N} \\ &= \dfrac{g_1 + g_2 + \dots g_{N-1}}{N-1} \frac{N-1}{N} + \dfrac{g_N}{N} \\ &= v_{N-1}(s)(1 - \frac{1}{N}) + \frac{g_N}{N} \\ &= v_{N-1}(s) + \frac{1}{N} \left[ g_N - v_{N-1}(s) \right] \end{aligned}

    つまり、N個のサンプルによる平均値はN-1個のサンプルによる平均値とN個目のサンプルの値を使って次のように表現できます。

    vN(s)=vN−1(s)+1N[gN−vN−1(s)]v_N(s) = v_{N-1}(s) + \frac{1}{N} \left[ g_N - v_{N-1}(s) \right]

    この手法を使うと生涯報酬サンプルの総和g1+g2+⋯+gNg_1 + g_2 + \dots + g_Nを計算する必要がありません。よって、総和がどんどん大きくなっていくという問題が生じないので実装でもよく使われます。前回のモンテカルロ法の実装でも使うことができたのですが、分かりやすさを優先して単純な総和と訪問回数を別々に管理する方法でコードを書きました。

    平均値計算の解釈を変える

    さて、この平均値の求め方を次のように解釈します。

    新しい平均値の計算方法では、新しい情報gNg_Nと古い予測vN−1(s)v_{N-1}(s)の差を計算してNNで割ったものを古い予測vN−1(s)v_{N-1}(s)に足すことで新しい予測としています。なお、新しい情報gNg_Nは、状態ssからの生涯報酬のN番目のサンプルであり、古い予測vN−1(s)v_{N-1}(s)はN-1番目までに集めた状態ssからの生涯報酬のすべてのサンプルからの平均値です。

    画像

    平均する数値のリストに新しい数値を追加する時、新しい数値が以前の平均よりも大きければ平均が大きくなります。また、新しい数値がより小さければ平均が小さくなります。同様に、新しい情報gNg_Nが古い予測vN−1(s)v_{N-1}(s)よりも大きければ、新しい予測値は古い値よりも大きくなります。逆に、新しい情報gNg_Nが古い予測vN−1(s)v_{N-1}(s)よりも小さければ新しい予測値は古い値よりも小さくなります。

    以上より、新しい平均値の計算方法は、新しい情報が予測に与える影響を表現していると解釈できます。なお、1N\frac{1}{N}は、NNが大きくなるほど小さくなるので新しい情報が予測値を更新する際の影響力はだんだん小さくなっています。サンプル数が増えるので当然でもあるのですが、強化学習では新しい情報の方がより重要になることがあります。

    例えば、イプシロン・グリーディ法などでは新しい情報(生涯報酬のサンプル)の方がより最適になる傾向があるのでNNの大きさによらず新しい情報を一定の割合で取り入れた方が学習効率が上がります。

    なので、単純な平均の計算という考えを離れて、予測を更新するという考え方に切り替えます。

    平均値から更新式へ変える

    まず、平均値の計算を次のように更新式に書き換えます。

    v(st)←v(st)+α[gt−v(st)]v(s_t) \leftarrow v(s_t) + \alpha \left[ g_t - v(s_t) \right]

    sts_tはステップttにおける状態を意味します。

    なお、α\alphaは1N\frac{1}{N}ではありません。よって、α\alphaには平均を計算するために生涯報酬の総和を状態の訪問数NNで割り算するという意味はありません。

    むしろ、新しい価値予測の値に少し近づけるための係数と考えます。つまり、更新するスピードをコントロールするための係数でありステップサイズ(step size)と呼ばれます。これは人間が設定する必要があるハイパーパラメータになります。よって、訪問数NNに反比例して小さくなることもありません。

    上式を次のように書き換えるとステップサイズの意味がよりはっきりします。

    v(st)←(1−α) v(st)+α gtv(s_t) \leftarrow (1 - \alpha) \ v(s_t) + \alpha \ g_t

    つまり、α\alphaは古い予測v(st)v(s_t)と新しい情報gtg_tの加重平均を計算しています。例えば、α=0.1\alpha = 0.1ならば、古い予測の値に9割の重みを与え、新しい情報の値に1割の重みを与えることになります。このように新しい情報を一定の割合で取り込むことになり、モンテカルロ法と比べると新しい情報をより重要視していることになります。

    このように新しい情報を取り込み続けることで状態価値関数が真の値へと収束することが期待されます。

    なお、モンテカルロ法では生涯報酬gtg_tの計算をするにはエピソードの終了を待つ必要があります。よって、状態価値関数や行動価値関数の予測値の更新はエピソードの終了を待って行われました。しかし、これまでの考え方の変更によって、我々はすでに単純な平均による計算から離れており、更新のスピードはステップサイズで調節できるのだからエピソードの終了を待たずに少しずつ更新を行いたいものです。

    なぜなら、もっと頻繁にエピソード内でも学習ができれば効率が良くなることが考えられるからです。

    そのために、動的計画法で使ったブートストラッピングを導入します。

    ブートストラッピング導入

    ブートストラッピングはすでに予測された値をもとに新しい予測値を更新するので、エピソードの終了を待つ必要がありません。

    そこで、状態sts_tからの生涯報酬gtg_tをブートストラッピングによって予測します。

    gt=rt+γv(st+1)g_t = r_t + \gamma v(s_{t+1})

    ステップttでなんらかの行動を取ったことで報酬rtr_tを受け取り、次の状態st+1s_{t+1}に遷移しています。なお、γ\gammaは割引率です。

    ここで、状態sts_tにおける生涯報酬の予測が、状態st+1s_{t+1}の状態価値の予測に依存して計算されています。このようにある予測のために以前に予測した値を使うことをブートストラッピングと呼びました。

    まとめると次のようになります。

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

    状態sts_tである行動を起こしたことで得た情報から新しい状態価値の予測値がブートストラッピングで計算されます。新しい状態価値の予測rt+γv(st+1)r_t + \gamma v(s_{t+1})と、古い状態価値の予測v(st)v(s_t)の差を計算しα\alphaで指定された係数をかけて状態価値の予測値が更新されます。

    つまり、一つのステップからの経験で状態価値関数の更新が行えるわけです。動的計画法で学んだようにブートストラッピングをしながら何度も繰り返し状態価値をあらゆる状態で計算するとやがては最適値へと収束していくことが期待されます。

    TD学習法とポリシーの評価

    これまで状態価値関数の予測について考えてきました。実際には何らかのポリシーに従うことで状態価値関数が決まります。よってTD学習を使用した際のポリシーの評価について考えます。ポリシーの評価とはあるポリシーに従った際の状態価値関数のことを指します。

    一般に、あるポリシーπ\piに従うことによる状態価値関数は次のように異なる期待値として定義できます。

    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}

    1行目のEπ[gt∣st=s]\mathbb{E}_\pi[g_t | s_t = s]はポリシーπ\piに従って行動する場合に状態ssから得られる生涯報酬gtg_tの期待値を意味します。これはモンテカルロ法では生涯報酬のサンプルの平均で予測しました。

    2行目で生涯報酬gtg_tをベルマン方程式により生涯報酬gtg_tを分解しています。つまり、状態ssから得られる報酬rtr_tと次の状態からの生涯報酬gt+1g_{t+1}を割り引いたものの和となります。

    3行目では次のステップからの生涯報酬gt+1g_{t+1}を次の状態における状態価値vπv_\piで表現しています。動的計画法では与えられた環境のモデル(状態遷移の確率)を利用してブートストラッピングを行い上記の期待値を予測しました。

    TD学習法では、モンテカルロ法によるサンプルを使う手法と動的計画法によるブートストラッピングを組み合わせます。よって、探索から得たたくさんのサンプルを使い経験から学ぶので環境のモデルを必要としません。また、ブートストラッピングによる予測ではエピソードの終了を待つ必要はありません。

    なお、前節で導出した以下の更新式はTD学習法が状態価値の予測を更新するためのものです。

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

    ポリシーπ\piに従いながら、この更新式を使って状態価値の予測を何度も更新することでv(st)v(s_t)が真のポリシーの評価vπ(s)v_\pi(s)へ近づくことを目指します。

    よって、TD学習法ではポリシーの評価をステップ毎に行なっていることになります。

    TD学習法による強化学習

    これまでの議論をまとめると、TD学習法が動的計画法やモンテカルロ法より優れている点は以下になります。

    • ブートストラッピングが使えるので動的計画法と違って状態遷移の確率、つまり環境のモデルを必要としない。経験から学べる。

    • ステップごとに学ぶのでモンテカルロ法のようにエピソードの終了を待つ必要がない。また、エピソードに必ず終了の状態があるという条件を必要としない。つまり、環境がエピソディックである必要がない。

    簡単にいうとTD学習法を適用できる環境が動的計画法やモンテカルロ法よりも多くなります。また、ステップごとに学習するので学習の速度が速くなることが期待されます。

    また、モンテカルロ法では、せっかくの経験を無駄にすることがあります。例えば、初回訪問の手法ではたくさんのサンプルを切り捨てることがあり経験を無駄にしがちです。さらにオフポリシーでは重点サンプリング比率が計算できない場合(ターゲットポリシーが取り得ない行動を挙動ポリシーが選んだ時)の経験も無駄になります。TD学習法はステップ毎に学ぶので無駄が少なくなります。

    今回の記事ではTD学習法を状態価値関数の予測やポリシーの評価という面から解説しました。これにイプシロン・グリーディ法などによるポリシーの改善を組み合わせれば強化学習を行うことができます。

    なお、TD学習法による強化学習ではモンテカルロ法のようにサンプルを集めるための探索を行う必要があり、オンポリシーとオフポリシーの両方のアプローチが存在します。

    次回はオンポリシーのTD学習法であるSARSAについて解説します。

    (続く)

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

    あなたへのおすすめ