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

Gymで強化学習⑲近似的な解決方法

    前回まではグリッド・ワールドである凍った湖を扱ってきました。その理由は、状態と行動の組み合わせの数が有限であり、ディクショナリや2次元のデータ構造で簡単に実装ができるからです。

    しかし、強化学習はグリッド・ワールドに限定されたものではありません。よって、ここからは状態の値が有限ではない場合を扱います。

    例えば、画像データを観測値として扱うとピクセルの配色の組み合わせが膨大な数になります。他にも、連続値をとる観測値も無数の値があります。例えば、宇宙船のスピードなどが考えられます。

    このように状態の値に対する制限がなくなると強化学習の適応範囲が一気に広がります。

    しかし、有限な状態の時と違ってあらゆる状態を探索しまくるといった手法が使えません。むしろ、ほとんどの状態に遭遇しないことでしょう。なので状態価値や行動価値の表を埋め尽くすことができません。

    そこで何らかの関数による近似による解決法を考えます。また、関数近似というとニューラルネットワークを思い浮かべる方も多いと思いますが、それについても議論していきます。

    関数近似で解決

    仮に、グリッド・ワールドのアプローチを無数にある状態に対して再利用することを考えてみましょう。巨大なグリッドを使ってほぼ無数の状態を表現できるとします。

    画像
    無数の状態をグリッドにできるとしたら

    状態が無数にあっても2次元の行動価値関数をテーブルとして表現できたなら、探索を無限に行えば全ての状態に予測値を付与することができそうです。でも無限の時間がかかるでしょう。よって、有限の時間では不可能になります。

    もう一つのアプローチとしては状態値をいくつか区分けしてグループごとに価値を決める手法があります。これは状態の離散化と呼ばれます。

    画像

    これが有効な場合もあります。ただし、状態の離散化を行う際に、どこで状態を区切るかなどの判断が必要となり、それは環境に対する理解をある程度必要とします。なので、よくわからない環境や複雑な環境では適用できません。また、離散化を使うことで最適なポリシーが生まれる保証もありません。

    であれば、状態が無数にある環境において、できるだけ探索しながらも探索できていない状態の価値に対しては何らかの穴埋めを行うといった解決方法を考えてはどうでしょうか。状態が無数にあるのだから、テーブルを使うのではなく無数の状態値を受け入れる関数を使います。

    つまり、状態価値関数や行動価値関数は連続値をとる状態値を入力値として受け入れる関数となります。よって、訪れたことがない状態に関しても計算することができます。つまりは、近似するわけです。

    例えば、状態価値をyyして、状態の値をxxとしたときに次のような関係を使うと経験からのサンプルデータをうまく説明できたとします。

    画像

    状態のサンプル数は有限ですが、無限の状態に対する価値を予測できるわけです。これが近似の強みです。

    直感的に言うと、仮に上図の一部を隠したとしてもその部分の予測はある程度は可能なのと似ています。「こことあそこはこうだったから、そっちは大体こんな感じかな」という予測をするわけです。これって人間の頭脳が行う予測と似ています。我々も全ての状態を経験していなくとも、想像できるわけです。ある意味、近似をしています。

    このようにして、訪れたことがない状態に対しても価値の予測ができ行動の選択に利用できます。なお、近似されているとはいえ、状態価値関数や行動価値関数を使うことに関しては以前と同様の考え方になるので、これまで学んできた強化学習のテクニックが再利用できることになります。

    価値関数の近似

    強化学習で近似的な手法を使うのは状態の無限性を有限なものに置き換えているといえます。なぜなら、関数は有限なパラメータによって規定されるからです。

    例えば、状態価値yyは、状態xxとほぼ直線的な(線型の)関係があるとします。

    画像
    線形関数による近似

    そこで線形関数による近似を考えます。それは次のように定義できます。

    y=ax+by = a x + b

    ここで、aaとbbは、関数のパラメータです。この二つのパラメータによって無限に値がある状態xxに関する状態価値yyを近似しています。

    なので無数にある各状態に対する価値を予測するのではなく、状態価値関数のパラメータを予測することになります。なのでうまく近似ができるのであれば、これまでのように各状態に対する価値を計算し収納するよりも効率の良い手法です。

    しかし、上記で仮定したようにある関数(線形関数)を使っての近似が成り立つことがあらかじめわかっているとは限りません。もしかしたら線形な関係ではなく、非線形な関係かもしれません。よって関数そのものを発見することが必要となります。これに関しては、ニューラルネットワークを使うことで解決しますが、今はそこまでは踏み込まずに解説を続けます。

    状態価値関数はパラメータのベクトルを使って、次のように表現できます。

    v^(st,wt)≈vπ(st)\hat{v}(s_t, \boldsymbol{w}_t) \approx v_\pi(s_t)

    ここで、v^(st,wt)\hat{v}(s_t, \boldsymbol{w}_t)は、あるポリシーによる状態価値関数vπ(st)v_\pi(s_t)を近似しています。

    また、パラメータはwt=[w1,w2,…,wn]{\boldsymbol{w}_t} = [ w_1, w_2, \dots, w_n]となっており一つ以上の数値が可能だとします。例えば、状態が一つの数値ではなく数個の値を含むベクトルであるなどの場合、複数のパラメータ(要素)が必要となります。

    なお、nnはパラメータの要素数です。また、wt{\boldsymbol{w}_t}のようにttが付いているのは、パラメータ自体があるステップttにおいての予測であると言う意味です。

    上記の線形関数の例に当てはめると、n=2n = 2でa=w1a = w_1とb=w2b = w_2 となります。

    v^(st, wt)=w1st+w2\hat{v}(s_t, \boldsymbol{w}_t) = w_1 s_t + w_2

    行動価値関数についても同様に考え、一般に次のように表現できます。

    q^(st,at,wt)≈qπ(st,at)\hat{q}(s_t, a_t, \boldsymbol{w}_t) \approx q_\pi(s_t, a_t)

    q^(st,at,wt)\hat{q}(s_t, a_t, \boldsymbol{w}_t)は、あるポリシーによる行動価値qπ(st,at)q_\pi(s_t, a_t)を近似しています。ここのwt{\boldsymbol{w}_t}は行動価値関数を近似する関数のパラメータです。

    このように表現された状態価値関数や行動価値関数のパラメータは、モンテカルロ法やTD学習法などによって環境内を探索した経験から得たデータを利用して更新していきます。

    以下ではQ学習を使って話を進めます。

    勾配降下法

    Q学習の更新式は以下のようになっていました。煩雑なのでポリシーの記号π\piは省略しています。

    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 \left[ r_t + \gamma \max\limits_a q(s_{t+1}, a) - q(s_t, a_t) \right]

    この式は、行動価値をTDエラーの方向へと少しずつステップサイズα\alphaによって更新しています。なお、TDエラーは、ターゲットと古い予測との差になります。

    ターゲットrt+γmax⁡aq(st+1,a)r_t + \gamma \max\limits_a q(s_{t+1}, a)は新しい情報を取り入れた行動価値の予測であり、それが古い予測q(st,at)q(s_t, a_t)より大きければ、TDエラーは性の値になるので、その方向へと行動価値を増やします。逆に、新しい予測が古い予測より小さければ、TDエラーは負の値になるので、その方向へと行動価値を減らします。収束すればTDエラーはゼロになります。

    しかし、行動価値関数q(st,at)q(s_t, a_t)をq^(st,at,wt)\hat{q}(s_t, a_t, \boldsymbol{w}_t)で近似している場合では、近似によるエラーを減らす方向へとパラメータを更新することを考えます。そのために、勾配降下法(あるいは確率的勾配降下法)を使います。

    まず、パラメータによるエラーとして以下の価値の平均二乗誤差(Mean Squared Error)を使います。

    MSE=12[q(st,at)− q^(st,at,wt) ]2\text{MSE} = \frac{1}{2} \left[ q(s_t, a_t) -  \hat{q}(s_t, a_t, \boldsymbol{w}_t) \right]^2

    注釈:本来、MSEは、状態や行動のエラーの平均を示します。モンテカルロ法のような手法では、エピソード内のすべてのサンプルを用いてこの平均を計算します。しかし、ここではTD法を考慮しており、エラーは各ステップごとに計算されます。ですので、これは複数のエラーの平均を取るのではなく、各エラーを個別に考慮します。この違いは、エラーの大きさを一括して測るか、それとも一つずつ測るかの違いです。しかし、その意図は同じです。

    12\frac{1}{2}が付いているのは後で式が単純になるからです。この値が小さくなるようにパラメータを更新すれば、近似の精度が上がることになります。

    そのためには、上記のエラーの勾配を計算します。勾配は、上記のエラーに対して各パラメータで偏微分を行うことで計算できます。


    ちょっと話がそれますが、微分、偏微分、勾配に付いて簡単に説明します。詳しくはこちらの記事でも解説しています。

    ある関数f(x)f(x)があるとします。この関数は一つの入力変数xxを持ちます。例えば、線形関数f(x)=ax+bf(x) = a x + bを考えます。

    ここでxxを増やすと、f(x)f(x)は傾きaaによって変化します。これを微分と呼び次のように表現します。

    df(x)dx=a\frac{d f(x)}{dx} = a

    つまり、xxによるf(x)f(x)の変化率を表しています。

    次に、関数f(x1,x2)f(x_1, x_2)を考えます。この場合、x1x_1とx2x_2それぞれについて関数の微分を考えることができます。このように複数の変数がある関数においてはそれぞれの変数に対する微分を偏微分と呼びます。

    なお、x1x_1に対して偏微分を計算する際には、x2x_2は変化しないと考えます。そして、関数f(x1,x2)f(x_1, x_2)をx1x_1で偏微分したものを次のように表現します。

    ∂f(x1,x2)∂x1\frac{\partial f(x_1, x_2)}{\partial x_1}

    これがx1x_1を変化させた時にf(x1,x2)f(x_1, x_2)がどのくらい変化するのかを表しています。

    また、x2x_2に関する偏微分は次のように表現されます。

    ∂f(x1,x2)∂x2\frac{\partial f(x_1, x_2)}{\partial x_2}

    このようにして計算した偏微分をベクトルとしてまとめたものを購買と呼びます。

    ∇ f(x1,x2)=(∂f(x1,x2)∂x1, ∂f(x1,x2)∂x2)\nabla f(x_1, x_2) = \left( \frac{\partial f(x_1, x_2)}{\partial x_1}, \frac{\partial f(x_1, x_2)}{\partial x_2} \right)

    あるいは次のようにも書きます。

    ∇ f(x1,x2)=gradf(x1,x2)\nabla f(x_1, x_2) = \text{grad} f(x_1, x_2)

    grad は gradient(勾配)から来ています。


    偏微分を使うと、価値の平均二乗誤差の変化率を次のように表現できます。以下では、パラメータの一つとしてw1w_1を使っています。

    ∂MSE∂w1\frac{\partial \text{MSE}}{\partial w_1}

    これを使ってMSEが小さくなる方向へとw1w_1を更新します。

    w1←w1−α ∂MSE∂w1w_1 \leftarrow w_1 - \alpha \dfrac{\partial \text{MSE}}{\partial w_1}

    ここでのα\alphaはパラメータ更新のためのステップサイズです。

    偏微分の中身をさらに展開すると以下になります。

    ∂MSE∂w1=∂12[q(st,at)− q^(st,at,wt) ]2∂w1=−[q(st,at)− q^(st,at,wt) ]∂q^(st,at,wt)∂w1\begin{aligned} \frac{\partial \text{MSE}}{\partial w_1} &= \frac{ \partial \frac{1}{2} \left[ q(s_t, a_t) -  \hat{q}(s_t, a_t, \boldsymbol{w}_t) \right]^2 }{ \partial w_1 } \\ &= - \left[ q(s_t, a_t) -  \hat{q}(s_t, a_t, \boldsymbol{w}_t) \right] \frac{ \partial \hat{q}(s_t, a_t, \boldsymbol{w}_t)}{\partial w_1} \end{aligned}

    よって更新式は次のようになります。

    w1←w1+α[q(st,at)− q^(st,at,wt) ]∂q^(st,at,wt)∂w1w_1 \leftarrow w_1 + \alpha \left[ q(s_t, a_t) -  \hat{q}(s_t, a_t, \boldsymbol{w}_t) \right] \frac{ \partial \hat{q}(s_t, a_t, \boldsymbol{w}_t)}{\partial w_1}

    鉤括弧の中身[q(st,at)− q^(st,at,wt) ]\left[ q(s_t, a_t) -  \hat{q}(s_t, a_t, \boldsymbol{w}_t) \right]はTDエラーです。

    同様にw2w_2に関しても次のように表記できます。

    w2←w2+α[q(st,at)− q^(st,at,wt) ]∂q^(st,at,wt)∂w2w_2 \leftarrow w_2 + \alpha \left[ q(s_t, a_t) -  \hat{q}(s_t, a_t, \boldsymbol{w}_t) \right] \frac{ \partial \hat{q}(s_t, a_t, \boldsymbol{w}_t)}{\partial w_2}

    これを勾配を使ってまとめると次のように書けます。

    wt+1← wt+α [q(st,at)− q^(st,at,wt) ]∇ q^(st,at,wt)\boldsymbol{w}_{t+1} \leftarrow \boldsymbol{w}_t + \alpha \left[ q(s_t, a_t) -  \hat{q}(s_t, a_t, \boldsymbol{w}_t) \right] \nabla \hat{q}(s_t, a_t, \boldsymbol{w}_t)

    この式を使ってMSEが減るように勾配に従ってパラメータを更新する方法を方法を勾配降下法と呼びます。

    線形関数による近似

    行動価値関数を線形関数で近似した場合を考えます。状態変数はsts_tだけとします。

     q^(st,at=a,wt)=w1 st+w2 \hat{q}(s_t, a_t=a, \boldsymbol{w}_t) = w_1  s_t + w_2

    注釈:この行動価値はある行動at=aa_t = aに対するものであり、行動ごとに異なるパラメータのがあるとしています。\hat{q}_a}(s_t, \boldsymbol{w}_t)と書いた方が明白かもしれません。

    勾配は次のようになります。

    ∇  q^(st,at,wt)=(∂q^(st,at,wt)∂w1,∂q^(st,at,wt)∂w2)=(st,1)\begin{aligned} \nabla  \hat{q}(s_t, a_t, \boldsymbol{w}_t) &= \left(\frac{\partial {\hat{q}(s_t, a_t, \boldsymbol{w}_t)}}{\partial w_1}, \frac{\partial {\hat{q}(s_t, a_t, \boldsymbol{w}_t)}}{\partial w_2} \right) \\ &= (s_t, 1) \end{aligned}

    これとTDエラーを掛け合わせて、ステップサイズによって少しずつパラメータを更新していけば、MSEが小さくなっていきます。

    なお、状態値が複数の値からなるベクトルである場合は、パラメータの数が増えるだけで勾配を使う考え方は同じです。例えば、状態がベクトルであり、st=(s1,s2)\boldsymbol{s}_t = (s_1, s_2)となって、要素がs1s_1とs2s_2の二つあるとします。

     q^(st,at,wt)=w1 s1+w2s2+w3 \hat{q}(s_t, a_t, \boldsymbol{w}_t) = w_1  s_1 + w_2 s_2 + w_3

    これに対する勾配は次になります。

    ∇ q^(st,at,wt)=(s1,s2,1)\nabla \hat{q}(s_t, a_t, \boldsymbol{w}_t) = (s_1, s_2, 1)

    つまり、線形関数の場合は、勾配は入力値そのものになっています。最後の切片(バイアス)だけは勾配が1です。

    さらに、線形関数による近似の場合、よく特徴エンジニアリング(Feature Engineering)を行います。つまり、状態の要素値をそのまま使うのではなく、何らかの変換を施した値を使うのです。特に、要素同士に何らかの関連がある場合に要素同士を掛け合わしたりして特徴量を取り出します。

    これはディープラーニング以前の機械学習ではよく行われていたことで、状態値についての理解を必要とします。

    例えば、状態ベクトルst\boldsymbol{s}_tから3つの特徴量を計算したとします。

    x1=f1(st)x2=f2(st)x3=f3(st)\begin{aligned} \text{x}_1 &= \text{f}_1(\boldsymbol{s}_t) \\ \text{x}_2 &= \text{f}_2(\boldsymbol{s}_t) \\ \text{x}_3 &= \text{f}_3(\boldsymbol{s}_t) \end{aligned}

    すると、線形近似の式は次になります。

     q^(st,at,wt)=w1 x1+w2x2+w3x3+w4 \hat{q}(s_t, a_t, \boldsymbol{w}_t) = w_1  x_1 + w_2 x_2 + w_3 x_3 + w_4

    その場合でも、勾配の計算は同じで以下のようになります。

    ∇ q^(st,at,wt)=(x1,x2,x3,1)\nabla \hat{q}(s_t, a_t, \boldsymbol{w}_t) = (x_1, x_2, x_3, 1)

    ニューラルネットワーク

    関数近似の手法として考えられるのは、前述した線形関数の他に、決定木、k最近傍法、ニューラルネットワークなどいろいろなものが考えられます。これら機械学習の手法はデータから学習してパラメータを推定することができます。

    その中でも一番有望なのはニューラルネットワークになります。

    ニューラルネットワークは特に非線形な関数の近似に優れています。普遍性定理(Universal Approximation Theorem)と呼ばれる性質があり、任意の連続関数を近似することができることが証明されています。

    連続関数は値がつながっており、途中で崖のように値が不連続に変化することがありません。よって、あらゆる点で勾配を計算することができるので勾配降下法でパラメータの調整を行えます。

    ニューラルネットワークの利点は手作業で特徴エンジニアリングを行う必要がないことです。その代わりにネットワークの構造を考える手間はかかりますが、パラフルな関数近似が行えるので関数近似というともっぱらニューラルネットワーク、特にディープラーニングが使われます。

    また、ディープラーニングによる関数近似を行う強化学習を深層強化学習と呼びます。


    次回は、線形関数による近似を使ったQ学習の実装を紹介します。手作業で特徴エンジニアリングを含んだ実例なので今回の話がより具体的になり理解が深まるでしょう。

    (続く)

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

    あなたへのおすすめ