TD学習(時間的差分学習:Temporal Difference Learning)はモンテカルロ法と動的計画法(DP)の考え方を組み合わせたものです。TD方はモンテカルロ法と同様、環境のダイナミクスのモデルを用いずに、経験から直接学習することができます。またDPと同様に最終結果を待たずに、他の推定値の学習結果を一部利用し、推定値を更新できます(ブートストラップを行えます)。
DP、TD、モンテカルロ法はすべて一般化方策反復(GPI)を用います。これらの方法間の主な違いは予測問題の扱い方です。
TD予測
TDとモンテカルロ法は、経験を用いてV^πの推定値Vを更新します。モンテカルロ法では、各訪問に対応する収益がわかるまで待ち、その値をV(st)の目標値として利用します。
$$ V(s_t) <- V(s_t) + \alpha [R_t – V(s_t)] $
1 2 3 |
Rt:時刻tに対応する実際のん収益値 定数α:ステップサイズ・パラメータ |
この方法をα不変MC
(constant-α MC)と呼びます。モンテカルロ法ではV(st)の増分量を決定するために、エピソードの終わりまで待たなくてはなりません(実際、Rtはエピソードの終わりになるまでわかりません。)
一方、TD法では次の時間ステップを待つだけで良く、TD法では時刻t + 1 で直ちに目標値を作り、観測した報酬rt+1 と推定量V(st + 1)を使って適切な更新を行えます。最も単純なTD法はTD(0)
と呼ばれ以下のようになります。
$$ V(s_t) <- V(s_t) + \alpha [t_{t+1} + \gamma V ( s_{t + 1} ) – V(s_t)] $$
TD法は、モンテカルロ法のサンプリング手法とDPのブートストラップ法を融合させたものとなります。
TD更新法とモンテカルロ法の更新をサンプルバックアップ(sample backup)と呼びます。後続状態(あるいは状態行動対)のサンプルが得られるまで待ち(look ahead)、後続状態の価値と得られた報酬値を利用してバックアップ値を計算し、元の状態(あるいは状態行動対)の価値を変更することに由来します。サンプルバックアップと、DPの完全バックアップは、すべての後続状態の完全な分布ではなく、後続状態のサンプルが1個得られていれば良いという点で異なる。
ここでの例題がわかりやすいかったのでぜひ本書を確認してみてください!
TD予測法の利点
ある推定値から学習を行うのにTD法では部分的に別な推定値を利用できます。つまり推測から推測を学習するようなブートストラップを行っています。
モンテカルロ法とDP手法に対するTD法の利点とは何でしょうか?DPに対するTD手法の利点の1つは、TDが環境のモデル、つまり報酬と次の状態の確率分布を必要としない点です。モンテカルロ法に対するTD手法の利点は、そのままTDをオンライン手法として完全な漸進型の実装できることです。(エピソードが終わる前に収益の計算ができることです。)
TD法とモンテカルロ法のいずれも正しい予測に漸近的収束するならば、次の疑問はどちらが先に正しい予測にたどりつくのか
です。この問題は現時点では数学的な証明はなく、未解決となっています。
TD(0)の最適性
10エピソードや100ステップなどの限られた数の経験しか与えられていない場合を想定しましょう。漸進学習手法による通常のアプローチでは、経験を繰り返し提示して、1つの答えに収束するまでこれを繰り返します。これを一般的にバッチ更新(batch updating)と呼びます。流れは以下の通り。
- 価値関数の近似Vが与えられる
- 終端状態に至るまで、各時間ステップでα不変MCやTD(0)の式で増分値が計算される
- 増分値の合計を行う
- 価値関数が1回更新される
- 更新された価値関数を用いて、経験すべてについてこの過程を繰り返す
- 新しい増分値を求める
- これを価値関数が収束するまで繰り返す
ここも本書の例が大変参考になりました!最尤推定値(maximum-likelihood estimate)や確実性等価値推定(certainty-quivalence estimate)にも言及がありました!
Sarsa: 方策オン型TD制御
TD予測法を制御問題に適用する方法について考えます。方策オン型と方策オフ型がありますが、この章では方策オン型について。状態価値関数ではなく、行動価値観数を学習するように変更を加えます。前述のV^πを学習するためのTD手法をそのまま利用することができます。
TD(0)での状態価値の収束性を保証する定理は、行動価値を対象として次式にも同様にあてはまります。
$$ Q(s_t, a_t) <- Q(s_t, a_t) + \alpha [r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) ] $$
因みに、sarsaは式内に出てくる要素(st, at, r_{t+1}, s_{t+1}, a_{t+a})の頭文字。
Q学習: 方策オフ型TD制御
強化学習におけるもっとも重要な発展の1つは、Q学習として知られている方策オフ型TD制御の開発です(Watkins, 1989)。もっとも簡単な形式は1ステップQ学習と呼ばれ、次のように定義されます。
$$ Q(s_t, a_t) <- Q(s_t, a_t) + \alpha [r_{t+1} + \gamma \max_{a} Q(s_{t+1}, a) – Q(s_t, a_t)] $$
学習で獲得される行動価値関数Qは使われている方策とは独立に、Q*(最適行動価値関数)を直接近似します。これによりアルゴリズムの解析が著しく簡単になり、収束性の証明を速い時期に得ることができます。
アクター・クリティック手法
アクター・クリティック手法は、価値関数と独立している方策を表現するために独立したメモリ構造を持つようなTD法。
1 2 3 |
アクター(actor; 行動器):行動を選択するために使われる行動部 クリティック(critic; 評価器):アクターが選択した行動を評価するもの |
クリティックの評価方法はTD誤差(TD error)を用います。
$$ \delta_t = r_{t+1} + \gamma V(s_{t+1}) – V(s_t) $$
アクター・クリティック手法の2つの大きな利点。
- 行動選択に最小限の計算量しか必要としない。
- いろいろな行動に対して、それを選択するような最適確率を学習することができる。
R学習: 割引のない連続タスクのための学習法
R学習は方策オフ型制御手法の1つ。経験が有限の収益を持つようなエピソードに分割されることがなく、割引が行われない場合の強化学習問題を扱うための手法。平均報酬は最終的にはすべての状態で等しくなります。ある状態では、しばらくの間平均より高い報酬が得られ、他の状態では、平均より低い報酬が得られることになります。
方策の平均報酬に対し相対的な値であり、相対価値(relative value)と呼びます。相対価値を利用することを除けば、R学習はQ学習とよく似た方策オフ型GPIの標準的なTD制御手法の1つです。つまり、行動方策と推定方策、さらに行動価値観数と推定価値観数を扱う手法ということになります。
ゲーム、事後状態、および他の特殊なケース
事後状態(afterstate)と事後状態価値関数(sfterstate value function)の例が掲載されていました。