【苦しみながら理解するReinforcement Learning】第6章 TD学習

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)] $$

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個得られていれば良いという点で異なる。

TD0

ここでの例題がわかりやすい!

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})の頭文字。

sarsa

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*(最適行動価値関数)を直接近似する。
これによりアルゴリズムの解析が著しく簡単になり、収束性の証明を速い時期に得ることができた。

Q学習

アクター・クリティック手法

アクター・クリティック手法は、価値関数と独立している方策を表現するために、独立したメモリ構造を持つようなTD法。

アクター(actor; 行動器):行動を選択するために使われる行動部
クリティック(critic; 評価器):アクターが選択肢た行動を評価するもの

クリティックの評価方法はTD誤差(TD error)による。

$$ \delta_t = r_{t+1} + \gamma V(s_{t+1}) – V(s_t) $$

アクター・クリティック手法の2つの大きな利点。

  1. 行動選択に最小限の計算量しか必要としない。
  2. いろいろな行動に対して、それを選択するような最適確率を学習することができる。

R学習: 割引のない連続タスクのための学習法

R学習は方策オフ型制御手法の1つ。
経験が有限の収益を持つようなエピソードに分割されることがなく、割引が行われない場合の強化学習問題を扱うための手法。

平均報酬は最終的には、すべての状態で等しくなる。
ある状態では、しばらくの間平均より高い報酬が得られ、他の状態では、平均より低い報酬が得られることになる。

現在の方策野での平均報酬に対して相対的な値であり、相対価値(relative value)という名で呼ぶ。
相対価値を利用することを除けば、R学習はQ学習とよく似た方策オフ型GPIの標準的なTD制御手法の1つである。
つまり、行動方策と推定方策、さらに行動価値観数と推定価値観数を扱う手法である。

ゲーム、事後状態、および他の特殊なケース

事後状態(afterstate)と事後状態価値関数(sfterstate value function)の例。

その他

Gibbs分布

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です