昨日はn本腕バンディットをプログラムで書いてみた。
今日はn本腕バンディット問題に対するアルゴリズムを考えるために、「行動の価値」について考えていく。
行動の価値
どのレバーを下すのかを考えるときに、これまでの結果から、出来るだけ良さげなレバーを選びたいので、「レバーを選ぶ」という行動の価値というものを考えていくことにする。
行える行動の集合をで表すと、
そして、推定される行動の価値を、関数で表すことにする。
なお、関数に添え字がついているのは、行動の価値の推定が、レバーを下ろすという行動をするたびに更新されていくことが考えられるから。
例えば、レバー0を下ろしたときに、得られた報酬が今まで考えていた行動の価値よりも高ければ、レバー0を下ろすという行動の価値はより高いものだと推定されるし、そうでなければ、レバー0を下ろすという行動の価値はより低いものだと推定されていくことになる。
さて、推定される行動の価値が具体的にどのようなものになるかというと、それは、その行動を行ったときに得られた報酬の平均とするのが自然。
すなわち、レバーを下ろすという行動を回()行ったとして、その報酬がそれぞれであったとすると、
となる。
なお、その行動を1回も行っていない場合、推定される行動の価値は0とすることにする。
真の行動の価値
推定される行動の価値とは別に、真の行動の価値というのも考えておく。
これは、エージェントには分かりえないのだけど、「この行動の価値は実はこうだったんだよ」という値。
真の行動の価値をとすると、これは、レバーを下ろしたときに得られる報酬の期待値となる。
すなわち、
なお、たくさん試行を行ってを改善していけば、は期待値に収束するので、となる。
もし真の行動の価値が分かっているのなら、その中で最も価値の高い行動を常に選べば、報酬の合計は最大になる。
そうでなかったとしても、推定される行動の価値を改善していって、真の行動の価値に近づけていけば、行動の選択の精度は高まっていくことになる。
そこで、どうやって推定される行動の価値を改善させていくのかが問題となってくる。
推定される行動の価値の改善
ところで、推定される行動の価値の式をちょっといじってみる。
今、回目にレバーを下ろしたとすると、
となる。
(回目にレバーを下ろしたとしているので、回目までに、レバーは回下ろされているということに注意)
一方、回目に下ろされなかったレバーについては、下ろされた回数が変化しないので、推定される行動の価値はそのまま。
したがって、回目に選択した行動を、それによって得られた報酬をとすると、推定される行動の価値は、
と、再帰的に表現することが出来る。
なので、この式を使って推定される行動の価値を改善していくことが出来る。
※注意
参考にしている本の記述とは、添え字の扱いが1つズレているので注意。
本ではを「回目の選択で参考にする推定価値」としているのに対し、この記事では「回目までの選択から推定された価値」としている。
行動は、1回目、2回目、・・・、回目となるので、の添え字をから始めるのなら、この記事のような考え方をした方が、整合性がある。
(本のように考えるのなら、の添え字はから始めるべき)
ポイントとなることが2つ。
まず、推定される行動の価値が改善されるのは、選択された行動に対してのみ、ということ。
なので、強化学習について学んでみた。(その4) - いものやま。で言及したように、「知識利用」をするだけでは、それ以外の行動については、推定される行動の価値が改善されていかないことになる。
もう一つは、再帰的に表現された更新式の意味合い。
この式は、次のように読むことが出来る:
つまり、観測されたギャップを使って、推定される行動の価値を少しずつ更新している、というわけだ。
この式に出てくる「係数」のことを、ステップサイズと呼んだりもする。
今回の場合、ステップサイズはその行動が選択された回数の逆数で、選択された回数が増えれば増えるほどステップサイズを小さくしていってることになるのだけれど、別の置き方(例えば、固定値)を考えることも出来る。
これで「行動の価値」について考えることが出来たので、明日はそれを使ってどのように行動の選択を行っていけばいいのかを考えていく。
今日はここまで!
- 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
- 出版社/メーカー: 森北出版
- 発売日: 2000/12/01
- メディア: 単行本(ソフトカバー)
- 購入: 5人 クリック: 76回
- この商品を含むブログ (29件) を見る