強化学習輪読 #16

公開:2020/10/10
更新:2020/10/11
14 min読了の目安(約13300字TECH技術記事

今日の概要

  • 関数がテーブルではなくパラメータで圧縮した形式に.
  • gradient method と semi-gradient method
  • 線形関数による近似

Chapter 9 On-policy Prediction with Approximation

この章では強化学習における関数近似を紹介する.特に状態価値関数のオンポリシーを扱う.

  • ここまでの章:

    • テーブル型の関数
    • 任意のsSs \in S に対応した価値が実数値として与えられる設定
  • この章:

    • パラメータ w\mathbf{w} を用いて状態価値関数を近似
    • v^(s,w)vπ(s)\hat{v}(s, \mathbf{w}) \approx v_{\pi}(s)と表記する
  • v^\hat{v}

    • 線形関数ならw\mathbf{w}は特徴量に対する重みベクトル
    • 多層ニューラルネットなら重みw\mathbf{w}は(connection weight)など
    • 決定木ならばw\mathbf{w}は全ての分割点と葉の重みなど

多くの場合,このw\mathbf{w}の次元は状態の数よりも小さく設定される.

ここで注目すべきはある状態について価値が更新されたとき,それに関連して他の状態の価値も更新される点である.これをgeneralization と言う.

関数近似(generalization)のメリットは,

  • メモリ削減
  • 関係する状態の結果から類推して学習できる
  • 状態を部分的にしか観測していなくても未観測な状態について学習できる

といった点があげられる.一方で運用やアルゴリズム/結果の理解を難しくさせていると言うデメリットもある.

9.1 Value-function Approximation

価値関数の近似について述べていく.
この本で紹介されている強化学習の手法は,価値関数の推定を繰り返して更新していく方法である.

復習

vπ(s)=Eπ[Rt+γRt+1+γ2Rt+2+ St=s]=Eπ[Gt  St=s]=Eπ[Rt+1+γGt+1  St=s]=Eπ[Rt+1+γvπ(St+1)  St=s]=Eπ[k=tt+nRkγkt1+γnvπ(St+n)  St=s] \begin{aligned} v_{\pi}(s)&=\mathbb{E}_{\pi}[R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots | \ S_t = s]\\ &=\mathbb{E}_{\pi}[G_t\ | \ S_t = s] \\ &=\mathbb{E}_{\pi}[R_{t+1} +\gamma G_{t+1} \ |\ S_t = s]\\ &=\mathbb{E}_{\pi}[R_{t+1} +\gamma v_{\pi}(S_{t+1})\ | \ S_t = s]\\ &=\mathbb{E}_{\pi}[\sum_{k=t}^{t+n} R_{k} \gamma^{k-t-1} + \gamma^{n} v_{\pi}(S_{t+n})\ | \ S_t = s] \end{aligned}
  • モンテカルロ:エピソードの終端までの情報をターゲット (数式2行目)
  • TD(0):次の状態の推定価値が正しいと仮定したターゲット(数式4行目)
  • n-step TD:2つの中間をとった形式 (数式5行目)

ここからはその更新対象とそのターゲットの関係を表す記号として \mapsto を導入する.
これを用いて,関数近似の場合の上記3つを記述すると,

  • MC:StGt   (=Rt+γRt+1+)S_t \mapsto G_t ~~~ (= R_t + \gamma R_{t+1} + \cdots)
  • TD(0):StRt+1+γv^(St+1,wt)S_t \mapsto R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w_t})
  • n-step TD:StGt:t+nS_t \mapsto G_{t:t+n}  (=Rt+γRt+1++γnRt+n+v^(St+n,wt))(= R_t + \gamma R_{t+1} + \cdots + \gamma^{n}R_{t+n} + \hat{v}(S_{t+n}, \mathbf{w_t}))

となる.また,DPの政策評価における更新は,

  • DP 政策評価:sEπ[Rt+1+γv^(St+1,wt)St=s]s \mapsto \mathbb{E}_{\pi}[R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w_t})|S_t = s]
    と書ける.(任意の状態sについて全て更新すると言う意味)

sus \mapsto uの学習は入力値-出力値がより正しくなるような関数を見つける作業だと言うことができ,各更新はsの推定価値をuの近似としてより尤もらしい値に近づけている.ただし,以下の点に注意する.

  • ここまで:ある状態sの価値を更新してその他の状態は動かさない
  • ここから:1つの状態価値について更新すると他の状態の価値も更新される

入力と出力の例を用いて入出力を関係付ける関数を近似的に求める機械学習は教師あり学習と言う.そして出力が実数のときは特に関数近似法(function approximation)と呼ばれる(?).このようにして各更新を単純な教師あり学習としてみることで強化学習を行うことができる.基本的に,

  • ニューラルネット
  • 決定木
  • 多変量回帰

などどんな手法でも可能であるが,全てが強化学習にふさわしいわけではない.それはオンライン性の面で,

  • インクリメンタルに取得したデータから効率的に学習できる
  • 非定常な(時間経過によって変化する)目的関数を扱える

ことが求められる.これは同じ訓練データでも異なる値をとることが多いためである.また,中には政策π\piを変化させながら行動価値qπq_{\pi}を学習する方法(GPI, Generalized Policy Iteration)も存在する.

9.2 The Prediction Objective (VE\overline{VE})

予測の目的関数VE\overline{VE}について説明する.

テーブル形式の関数では,

  • 真の分布から観測される実現値から推定
  • それぞれの状態が独立

しているため予測の精度についてあまり重要視しなかった.しかし,関数近似をする際は,

  • ある状態の更新が他の多くの状態に影響を与える
  • 全ての状態の値を得ることができない

と言う性質がある.そのためμ(s)0,sμ(s)=1\mu(s) \geq 0, \sum_s \mu(s) =1となるように重みμ\muを決めて各状態について誤差を重視する度合いを決める必要がある.そしてそのμ\muを用いて最小化すべき目的関数(Mean Squared Value Error)

VE=sSμ(s)[vπ(s)v^(s,w)]2 \overline{VE} = \sum_{s \in S} \mu(s) [v_{\pi}(s) - \hat{v}(s, \mathbf{w})]^2

を設定する.このμ\muは状態sを通る頻度などで設定される.On-policyの学習の時,このμ\muはオンポリシー分布(On-policy distirbution)と呼ぶ.(この章ではこれを主に用いる)

  • 継続的なタスク
  • エピソードのタスク

でそれぞれ区別する必要があるが,継続的なタスクではいずれ定常な分布となる.また,エピソードのタスクでは以下のようにμ\muは計算される.

  • h(s)h(s):sでエピソードが始まる確率
  • η(s)\eta(s):s推移する平均的な回数

とすると,

η(s)=h(s)+sˉη(sˉ)aπ(asˉ)p(ssˉ,a),  (sS) \eta(s) = h(s) + \sum_{\bar{s}}\eta(\bar{s}) \sum_a \pi(a|\bar{s})p(s | \bar{s},a), ~~ (\forall s \in S)

となる.そして,割引率のないオンポリシー分布は,

μ(s)=η(s)sη(s) \mu(s) = \frac{\eta(s)}{\sum_s \eta(s)}

と計算できる.(割引率がγ\gammaを導入したい場合η\etaの式の第2項にかける)

理想的にはVE(w)VE(w),w\overline{VE}(\mathbf{w}^{*}) \leq \overline{VE}(\mathbf{w}), \forall \mathbf{w}なる大域的最適解w\mathbf{w}^{*}を見つけたいが,これは難しいことも多いため局所解を見つけることが目標となる.とはいえ,収束する保証はなく,発散する可能性もある.

続く二つのセクションでは,

  • 現状の推定値を用いて次の時点の推定値の更新を行う関数近似の強化学習のフレームワーク
  • (特に線形関数を用いた)勾配計算に基づく更新方法

について説明する.

9.3Stochastic-gradient and Semi-gradient Methods

確率的勾配降下法(SGD)をベースとした強化学習の手法を紹介する.

gradient method

まず,

  • w=(w1,w2,,wd)T\mathbf{w} = (w_1, w_2, \ldots, w_d)^T
  • v^(s,w)\hat{v}(s,\mathbf{w})は任意のsSs \in Sについてw\mathbf{w}で微分可能
  • タイムステップttごとにw\mathbf{w}を更新
  • ttにおけるw\mathbf{w}wt\mathbf{w}_tとする
  • 各タイムステップにおいて,Stvπ(St)S_t \mapsto v_{\pi}(S_t)のサンプルを観測

と設定する.このとき,

  • 分布μ\muから状態を観測する

と言えるため,VE\overline{VE}を最小化する確率的勾配降下法は,

wt+1=wt12αEμ[VE(wt)]wt12α[vπ(St)v^π(St,wt)]2=wt+α[vπ(St)v^π(St,wt)]v^π(St,wt) \begin{aligned} \mathbf{w}_{t+1} &= \mathbf{w}_t - \frac{1}{2}\alpha \nabla \mathbb{E}_{\mu}[\overline{VE}(\mathbf{w}_t)]\\ &\approx \mathbf{w}_t - \frac{1}{2}\alpha \nabla \left[v_{\pi}(S_t) - \hat{v}_{\pi}(S_t,\mathbf{w}_t ) \right]^2\\ &= \mathbf{w}_t + \alpha\left[v_{\pi}(S_t) - \hat{v}_{\pi}(S_t,\mathbf{w}_t ) \right]\nabla\hat{v}_{\pi}(S_t,\mathbf{w}_t ) \end{aligned}

のような更新式で表される.
(勾配を降るようにパラメータを更新する勾配法を確率的なサンプリングによって行う)

ただし,

f(w)=(f(w)w1,f(w)w2,,f(w)wd)T \nabla f(\mathbf{w}) = \left( \frac{\partial f(\mathbf{w})}{\partial w_1}, \frac{\partial f(\mathbf{w})}{\partial w_2},\ldots, \frac{\partial f(\mathbf{w})}{\partial w_d} \right)^T

である.しかし,真のvπv_{\pi}は観測できない.これを前節までと同様に,観測したデータからターゲットを推定した値UtU_tで代用(StUtS_t \mapsto U_t)し,

wt+α[Utv^π(St,wt)]v^π(St,wt) \mathbf{w}_t + \alpha\left[U_t - \hat{v}_{\pi}(S_t,\mathbf{w}_t ) \right]\nabla\hat{v}_{\pi}(S_t,\mathbf{w}_t )

とする.もちろんUtU_tにはノイズが含まれているが,UtU_tが不偏推定量すなわち

Ep,π[UtSt=s]=vπ(St) \mathbb{E}_{p, \pi} [U_t | S_t = s] = v_{\pi}(S_t)

であれば,十分小さいα\alphaのもとwt\mathbf{w}_tは局所最適解に収束することが保証される.((2.7)と同様.)

例えば,政策π\piによって実際(もしくはシミュレーション)の相互作用から生成される観測値があるとすると,真の分布から生成される報酬の期待値が真の価値であるから,モンテカルロ法ではUt=GtU_t = G_tとすれば不偏である.疑似コードは以下のようになる.

semi-gradient method

既知の推定値を正しいとした元で次の時点の推定を行うブートストラップな手法(DP, TDなど)では,これが難しい.例えばDPでは

a,s,rπ(aSt)p(s,rSt,a)[r+γv^(s,wt)] \sum_{a,s',r}\pi(a|S_t)p(s',r|S_t,a)[r + \gamma\hat{v}(s',\mathbf{w}_t)]

としてしまい,wt\mathbf{w}_tに依存してしまうためバイアスが生まれる.このことからもわかるように,収束させるにはターゲットをwt\mathbf{w}_tについて独立にする必要がある.

ターゲットがwt\mathbf{w}_tに依存する場合をsemi-gradient法(半勾配法?)と呼ぶ.
この方法は勾配法(gradient method)と違い,ロバストに収束することが一般に保証されていない.

しかし,semi-gradient methodには以下のメリットがあり,利用される場合がある.

  • v^\hat{v}が線形関数のときは収束する.
  • 高速な学習が可能
  • 継続的にオンラインで学習可能

例えば,典型的なsemi-gradient法のsemi-gradient TD(0)はターゲットUtU_t

Ut=Rt+1+γv^(St+1,w) U_t = R_{t+1} + \gamma \hat{v}(S_{t+1},\mathbf{w})

として行う.疑似コードは以下のように表される.

state aggregation (状態集約)

状態集約は最も簡単な関数近似で状態をグループ化し,各グループに一つの価値をもつ.
これはSGDの特殊な形式だと考えることができ,

  • w\mathbf{w}:各グループの価値を合わすグループ数次元のベクトル
  • 勾配v^\nabla\hat{v}のg番目の要素は,
v^(St,w)wg={1(Stg番目のグループに属する)0(その他) \frac{\partial \hat{v}(S_t, \mathbf{w})}{\partial w_g} = \begin{cases} 1 & (S_tがg番目のグループに属する) \\ 0 & (その他) \end{cases}

として考えられる.

Example 9.1 State Aggregation on the 1000-state Random Walk

Example 6.2などで行ったランダムウォークについて1000個の状態がある場合を考える.

  • 左から右に番号1~1000の状態
  • 500からスタート
  • 今いる状態から左の100個もしくは右の100個の合計200状態に当確率で遷移
  • はみ出したとき,もしくは1,1000に到達した時点で終了
  • 左で終了すると報酬-1
  • 右で終了すると報酬+1

  • 赤線は真の価値関数
  • 灰色は分布μ\mu
  • 青線は以下の条件でgradient MCを行った際の各グループの価値
    • 100000エピソード
    • α=2×105\alpha = 2 \times 10^{-5}
    • 左から100個ずつ10グループに集約

この結果から

  • おおよそVE\overline{VE}の大域的最適解
  • 分布の重み付けによって端の方は誤差が多少大きくなっている

と言うことがわかる.

Linear Method

v^(s,w)\hat{v}(s, \mathbf{w})が線形の場合の(semi)勾配法について説明する.

gradient linear method

  • xi:SR  (i=1,2,,d)x_i : \mathcal{S} \rightarrow \mathbb{R} ~~ (i = 1, 2, \ldots, d)
  • 状態sの特徴量:x(s)=(x1(s),x2(s),,xd(s))T\mathbf{x}(s) = (x_1(s), x_2(s), \ldots, x_d(s))^T
  • v^(s,w)=wTx(s)=i=1dwixi(s)\hat{v}(s, \mathbf{w}) = \mathbf{w}^T \mathbf{x}(s) = \sum_{i=1}^d w_i x_i(s)

とする.このとき,

v^(s,w)=x(s) \nabla \hat{v}(s, \mathbf{w}) = \mathbf{x}(s)

となるから,一般的なSGDにおける更新は,

wt+1=wt+α[Utv^(St,wt)]x(St) \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[U_t - \hat{v}(S_t, \mathbf{w}_t)\right]\mathbf{x}(S_t)

数学的に扱いやすいため解析によく用いられる.収束などの結果はこの線形関数に関してであることが多い.

特に線形の場合,局所最適解がただ一つであることから,局所最適解に収束する保証があるアルゴリズムが大域的最適解に収束することが保証されることになる.(e.g. gradient MC)

semi-gradient linear method

semi-gradient TD(0)も線形関数による近似であれば収束することが知られている.
(ただし,gradient methodと違い,大域的最適解への保証ではない)
更新式は,xt=x(St)\mathbf{x}_t = \mathbf{x}(S_t)として,

wt+1=wt+α(Rt+1+γwtTxt+1wtTxt)xt=wt+α(Rt+1xtxt(xtγxt+1)Twt) \begin{aligned} \mathbf{w}_{t+1} &= \mathbf{w}_t + \alpha \left(R_{t+1} + \gamma\mathbf{w}_t^T \mathbf{x}_{t+1}- \mathbf{w}_t^T \mathbf{x}_{t}\right)\mathbf{x}_t\\ &= \mathbf{w}_t + \alpha \left(R_{t+1}\mathbf{x}_t - \mathbf{x}_t\left(\mathbf{x}_t - \gamma \mathbf{x}_{t+1}\right)^T \mathbf{w}_t\right) \end{aligned}

となる.ここで,

b=Eμ,π,p[Rt+1xt],  A=Eμ,π,p[xt(xtγxt+1)T] \mathbf{b} = \mathbb{E}_{\mu,\pi,p}\left[R_{t+1}\mathbf{x}_{t}\right] , ~~ A =\mathbb{E}_{\mu,\pi,p}\left[\mathbf{x}_{t}\left(\mathbf{x}_{t} - \gamma\mathbf{x}_{t+1} \right)^T\right]

とすると,wt\mathbf{w}_{t}が与えられたときの平均的なwt+1\mathbf{w}_{t+1}は,

Eμ,π,p[wt+1wt]=wt+α(bAwt)    () \mathbb{E}_{\mu,\pi,p}\left[\mathbf{w}_{t+1} | \mathbf{w}_{t}\right] = \mathbf{w}_t + \alpha\left(\mathbf{b} - A\mathbf{w}_t\right) ~~~~ \cdots (*)

と計算でき,bAwTD=0\mathbf{b} - A\mathbf{w}_{TD} = \mathbf{0}なる重みベクトルwTD\mathbf{w}_{TD}に至ったとき更新が停止する.このwTD\mathbf{w}_{TD}は,TD不動点(TD fixed point)と呼ばれ,

wTD=A1b \mathbf{w}_{TD} = A^{-1}\mathbf{b}

と計算できる.実際,semi-gradient TD(0)ではこの点に収束することがわかっている.
収束の証明と逆行列の存在を以下で証明する.

[証明] wTD\mathbf{w}_{TD}への収束

以下を仮定して進める(あとで証明).

  • AAが正定値行列

上の式(*)を変形すると,

E[wt+1wt]=(IαA)wt+αb \mathbb{E}[\mathbf{w}_{t+1} | \mathbf{w}_{t}] = (I - \alpha A)\mathbf{w}_{t} + \alpha \mathbf{b}

と表せる.マルコフ過程であるから,

E[wt+1wt1]=(IαA)E[wtwt1]+αb \mathbb{E}[\mathbf{w}_{t+1} | \mathbf{w}_{t-1}] = (I - \alpha A)\mathbb{E}[\mathbf{w}_{t} | \mathbf{w}_{t-1}] + \alpha \mathbf{b}

と表せて,漸化式を解くと,

E[wt+1w1]=(IαA)t(w1c)+c,  c=A1b \mathbb{E}[\mathbf{w}_{t+1} | \mathbf{w}_{1}] = (I - \alpha A)^t (\mathbf{w}_{1} - \mathbf{c}) + \mathbf{c}, ~~ \mathbf{c} = A^{-1}\mathbf{b}

となる.α\alphaは十分に小さく,AAが正定値より対角要素が全て正であるから,

limtE[wt+1w1]=c=wTD \lim_{t \to \infty} \mathbb{E}[\mathbf{w}_{t+1} | \mathbf{w}_{1}] = \mathbf{c} = \mathbf{w}_{TD}

よりwTD\mathbf{w}_{TD}への収束が示される.

証明終了

[証明] AAが正定値

継続的なタスクでγ<1\gamma < 1のとき,linear TD(0)での行列AAは以下のように表せる.

A=sμ(s)aπ(as)r,sp(r,ss,a)x(s)(x(s)γx(s))=sμ(s)sp(ss)x(s)(x(s)γx(s))=sμ(s)x(s)(x(s)γsp(ss)x(s))=XD(IγP)X \begin{aligned} \mathbf{A} &=\sum_{s} \mu(s) \sum_{a} \pi(a \mid s) \sum_{r, s^{\prime}} p\left(r, s^{\prime} \mid s, a\right) \mathbf{x}(s)\left(\mathbf{x}(s)-\gamma \mathbf{x}\left(s^{\prime}\right)\right)^{\top} \\ &=\sum_{s} \mu(s) \sum_{s^{\prime}} p\left(s^{\prime} \mid s\right) \mathbf{x}(s)\left(\mathbf{x}(s)-\gamma \mathbf{x}\left(s^{\prime}\right)\right)^{\top} \\ &=\sum_{s} \mu(s) \mathbf{x}(s)\left(\mathbf{x}(s)-\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s\right) \mathbf{x}\left(s^{\prime}\right)\right)^{\top} \\ &=\mathbf{X}^{\top} \mathbf{D}(\mathbf{I}-\gamma \mathbf{P}) \mathbf{X} \end{aligned}

ただし,

  • XRS×dX \in \mathbb{R}^{|\mathcal{S}|\times d}:特徴行列
  • PRS×SP \in \mathbb{R}^{|\mathcal{S}|\times \mathcal{S}}:推移確率行列
  • DRS×SD \in \mathbb{R}^{|\mathcal{S}|\times \mathcal{S}}diag(μ)diag(\mu)

を表す.

ここで,以下の既知の2つの定理を証明なしに用いる.

定理1

正方行列MMについて,対称行列SSS=M+MTS = M + M^Tと表されるとき,SSが正定値であることとMM正定値であることは必要十分条件である.

定理2

対称行列SSについて,全ての対角要素が正でかつ,対応する対角外要素の(絶対値?)の和よりも大きいとき,対称行列SSは正定値行列である.

以上を用いれば以下の手順で証明できる.

  1. D(IγP)D(I - \gamma P)の対角要素が正でそのほかが負
  2. D(IγP)D(I - \gamma P)の行の和が正
  3. D(IγP)D(I - \gamma P)の列の和が正
  4. D(IγP)D(I - \gamma P)が正定値
  5. Aが正定値

1. D(IγP)D(I - \gamma P)の対角要素が正でそのほかが負

DDが対角行列,Pの要素が確率(0以上1以下),γ<1\gamma < 1より自明.

2. D(IγP)D(I - \gamma P)の行の和が正

Pが遷移確率行列で,行の和をとると1であるため自明

3. D(IγP)D(I - \gamma P)の列の和が正

1D(IγP)=μ(IγP)=μγμP=μγμ=(1γ)μ \begin{aligned} \mathbf{1}^{\top} \mathbf{D}(\mathbf{I}-\gamma \mathbf{P}) &=\boldsymbol{\mu}^{\top}(\mathbf{I}-\gamma \mathbf{P}) \\ &=\boldsymbol{\mu}^{\top}-\gamma \boldsymbol{\mu}^{\top} \mathbf{P} \\ &=\boldsymbol{\mu}^{\top}-\gamma \boldsymbol{\mu}^{\top} \\ &=(1-\gamma) \boldsymbol{\mu} \end{aligned}

4. D(IγP)D(I - \gamma P)が正定値

S=D(IγP)+D(IγP)TS = D(I-\gamma P) + D(I - \gamma P)^Tの対角要素と対角以外の要素について考えると,上記1,2,3より,全ての対角要素が正でかつ対応する対角外要素の絶対値の和よりも大きい.よって,定理2よりSは正定値である.また,これにより定理1よりD(IγP)D(I-\gamma P)が正定値である.

概念図:

5. AAが正定値

任意のyRS\mathbf{y} \in \mathbb{R}^{|S|}について,z=Xy\mathbf{z} = X\mathbf{y}とすると,

yTAy=yXTD(IγP)Xy=(Xy)TD(IγP)Xy=zTD(IγP)z>0 \begin{aligned} \mathbf{y}^T A \mathbf{y} &= \mathbf{y} X^T D(I-\gamma P) X \mathbf{y}\\ &= (X \mathbf{y})^T D(I-\gamma P) X \mathbf{y}\\ &= \mathbf{z}^T D(I-\gamma P) \mathbf{z} > 0 \end{aligned}

より AAは正定値である.

証明終了

解の性能について

収束する解wTD\mathbf{w}_{TD}は,

VE(wTD)11γminwVE(w) \overline{VE}(\mathbf{w}_{TD}) \leq \frac{1}{1-\gamma} \min_{\mathbf{w}} \overline{VE}(\mathbf{w})

を満たすことが示される.つまり,最低でも大域的最適解の11γ\frac{1}{1-\gamma}倍の性能が保証されている.しかし,γ\gammaは1に近いことが多いため,TD(0)では性能が低下する可能性もある.
6,7章でも紹介された通り,MCに比べて分散が小さいことや高速であるため,どの手法が最適化は問題の性質や許容できる学習時間に依る.

また,On-policy 分布にしたがって更新されることは重要なポイントであり,そうでない場合は発散する可能性がある.このような状況での可能な開放については11章で扱う.

n-step semi-gradient TD

semi-gradient TD(0)と同様に,n-stepでもsemi-gradient methodが考えられる.

wt+n=wt+n1+α[Gt:t+nv^π(St,wt+n1)]v^π(St,wt+n1) \mathbf{w}_{t+n} = \mathbf{w}_{t+n-1} + \alpha\left[G_{t:t+n} - \hat{v}_{\pi}(S_t,\mathbf{w}_{t+n-1}) \right]\nabla\hat{v}_{\pi}(S_t,\mathbf{w}_{t+n-1} )

ただし,

Gt:t+nRt+1+γRt+2++γn1Rt+n+γnv^(St+n,wt+n1),0tTn G_{t:t+n} \doteq R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^{n} \hat{v}\left(S_{t+n}, \mathbf{w}_{t+n-1}\right), \quad 0 \leq t \leq T-n

その他のブートストラップ手法でのsemi-gradinet method

  • semi-gradient DP
  • semi-gradient Sarsa(0)

でも同様に収束することが示される.また,エピソードのタスクでも学習率の減衰など多少の条件を付け加えれば良い.

Example 9.2 Bootstrapping on the 1000-state Random Walk

semi-gradient method を用いた状態集約の学習を示す.

  • 左の図はsemi-gradient methodのTD法による推定値
  • 右の図はTDのステップ数と学習率の違いによる誤差の変化

を表す図で,左の図からは多少の誤差が生じていることがわかる.しかし右図から,10エピソードでの学習結果として7章のテーブル型のn-step TDと同じような結果が得られることがわかり,学習の速さなどの面でメリットがあることがわかる.

今日のまとめ

  • テーブル関数を圧縮して関数近似
  • 関数近似では一つの更新があらゆる状態の価値の更新になる
  • ターゲットが不偏推定量のとき(e.g. MC法)はgradient method
  • 不偏推定量でないとき(e.g. TD法)はsemi-gradient method
  • 線形関数による近似であれば多くのsemi-gradient methodで局所解に収束