2014年9月24日水曜日

ICML2014 : A new Q(lambda) with interim forward view and Monte Carlo equivalence


Q(λ)というのが見慣れなかったので、今回紹介するのはこれ。
http://jmlr.org/proceedings/papers/v32/sutton14.pdf


事前知識


Q学習 Q-learning


1989年のWatkinsの論文で提唱された強化学習の中のTD 法(temporal difference learning)の手法のひとつ。ほかに強化学習を解く手法には動的計画法・モンテカルロ法があげられるらしい。この3つですべて説明できるかはわからない。
今回は新しいQ-learning手法を提唱するとともにモンテカルロ法と(一部?)同等であることを示しているそうなので、手法の垣根を超える論文なのかもしれない(注:今の時点でタイトルしか読んでない)



最終目的は最適な行動をとって、報酬を最大化すること。
しかし状態(環境)によって報酬は異なり、すべての通りを試すのは難しい。

とりあえずこの辺りの話で出てくるものを一覧にすると、


  • 予測問題 :方策(π)を固定して十分長い試行を行った後に累積報酬が観測できるので、未来まで含めた累積報酬の期待値=値関数・状態価値Vを学習する
  • 制御問題 :行動関数 Qを学習して今後の累積報酬を最大化するような行動をとる
という二つのアプローチが考えられる。
ここで累積報酬とは
Rt = rt+1 + γrt+2 + γ^2 rt+3 ...

というように未来に与えられる報酬はγで割り引いて計算する。(つまり未来の状態から学習していく?)


そのうち予測問題では
  • 動的計画法:すべてのパターンを網羅的に足し合わせる←ベストだが重い
  • モンテカルロ法:十分長い試行後に累積報酬を観測
などの手法が考えられる。



しかしこのような学習は即時にできない問題点がある。

そこで用いられている手法が
  • 予測問題:TD(λ)
  • 制御問題:Q(λ) (方策オフ)Sarsa(λ)(方策オン) (On policy), Actor-Critic法(連続的な選択に向く)
0<=λ<=1であり、λ=1のときは理想的にはモンテカルロ法のように十分長い試行後を考える。λがその間のときにはbootstrap(本来の標本からのサンプル)とモンテカルロ法(その文脈上でのサンプルを次々に進めていく)が混ざりあうのが理想らしい。

TD法は以前の値関数を利用し、
Vi+1(st) = Vi(st)+α[rt+1+γVi(st+1)-Vi(st)]
という風に、学習率α(これが収束に大事らしい)でbootstrapで更新していく。
このかっこの中がTD誤差と呼ばれる。





一方制御問題ではQ関数を学習し、すなわち状態stととりうる行動atに対して
その行動をとった場合に得る報酬&行動後の報酬の最大値でQ関数を更新する。

このとき行動者の状態と、その状態で選択できる行動の数だけセットを用意する必要があるため、連続的な選択には向いていないらしい。(Actor-critic法を使うとありましたが今回は触れませんでした)


通常は有限状態数のマルコフモデルを考え、報酬を増加させる方策(ある状態のときある行動をとる確率密度)を考えるのがon-policy手法( Sarsa, TD(λ))であり、方策とは無関係に(全通りを考え最大値をとる)Q関数を学習するのがQ-learningである。例えばε-greedy法(確率εでランダム、それ以外でgreedy)などの方法による方策の固定はどちらの手法でも用いられるが、on-policy法では期待値を利用するため方策に依存し、off-policy法では方策に依存してサンプリングしてくるが最大値?をとってくるので方策自体には依存しない。



しかしこれまでのQ(λ)法ではλ=1のときに厳密には?モンテカルロ法と一致していなかった。

概要

λ=1のときにモンテカルロ法と一致するQ(λ)法(PTD(λ)アルゴリズム&PQ(λ))を開発した。
方策なしアルゴリズムでλ=1のときにモンテカルロ法と一致する初めてのアルゴリズムである。
とりあえず求めたいのが重みベクターθで



こう定義されている。

そこでなんやかやすると



こんな更新式になる。ローが方策の比率?、δが累積報酬、φがstate-actionの特徴ベクトル。

細かいところを追うのはちょっと厳しいですねぇ。。
時間があったらまた読んでみます(´;ω;`)

とりあえず今回は勉強になったからよし。





0 件のコメント:

コメントを投稿