いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。(その6)

昨日はn本腕バンディットをプログラムで書いてみた。

今日はn本腕バンディット問題に対するアルゴリズムを考えるために、「行動の価値」について考えていく。

行動の価値

どのレバーを下すのかを考えるときに、これまでの結果から、出来るだけ良さげなレバーを選びたいので、「レバー i \: (i=0, 1, \cdots , n-1)を選ぶ」という行動の価値というものを考えていくことにする。

行える行動の集合を \mathcal{A}で表すと、

 {
\mathcal{A} = \{\mbox{レバー}i\mbox{を下ろす} \: | \: i = 0, 1, \cdots , n-1\}
}

そして、推定される行動の価値を、関数 Q_t: \mathcal{A} \rightarrow \mathbb{R}で表すことにする。

なお、関数 Q_tに添え字 t \: (t=0, 1, \cdots , T)がついているのは、行動の価値の推定が、レバーを下ろすという行動をするたびに更新されていくことが考えられるから。
例えば、レバー0を下ろしたときに、得られた報酬が今まで考えていた行動の価値よりも高ければ、レバー0を下ろすという行動の価値はより高いものだと推定されるし、そうでなければ、レバー0を下ろすという行動の価値はより低いものだと推定されていくことになる。

さて、推定される行動の価値が具体的にどのようなものになるかというと、それは、その行動を行ったときに得られた報酬の平均とするのが自然。
すなわち、レバー iを下ろすという行動を k回( k \le t)行ったとして、その報酬がそれぞれ r_1, r_2, \cdots , r_kであったとすると、

 {
Q_t(\mbox{レバー}i\mbox{を下ろす}) = \frac{r_1 + r_2 + \cdots + r_k}{k}
}

となる。
なお、その行動を1回も行っていない場合、推定される行動の価値は0とすることにする。

真の行動の価値

推定される行動の価値とは別に、真の行動の価値というのも考えておく。
これは、エージェントには分かりえないのだけど、「この行動の価値は実はこうだったんだよ」という値。

真の行動の価値を Q^{\ast}: \mathcal{A} \rightarrow \mathbb{R}とすると、これは、レバーを下ろしたときに得られる報酬の期待値となる。
すなわち、

 {
Q^{\ast}(\mbox{レバー}i\mbox{を下ろす}) = E_i
}

なお、たくさん試行を行って Q_tを改善していけば、 Q_tは期待値に収束するので、 Q_t \rightarrow Q^{\ast}となる。

もし真の行動の価値が分かっているのなら、その中で最も価値の高い行動を常に選べば、報酬の合計は最大になる。
そうでなかったとしても、推定される行動の価値を改善していって、真の行動の価値に近づけていけば、行動の選択の精度は高まっていくことになる。
そこで、どうやって推定される行動の価値を改善させていくのかが問題となってくる。

推定される行動の価値の改善

ところで、推定される行動の価値の式をちょっといじってみる。

今、 t回目にレバー iを下ろしたとすると、

 {
\begin{align}
Q_t(\mbox{レバー}i\mbox{を下ろす}) &= \frac{r_1 + r_2 + \cdots + r_k}{k} \\
  &= \frac{r_1 + r_2 + \cdots + r_{k-1}}{k} + \frac{r_k}{k} \\
  &= \frac{k-1}{k} \cdot \frac{r_1 + r_2 + \cdots + r_{k-1}}{k-1} + \frac{r_k}{k} \\
  &= \left(1 - \frac{1}{k} \right) \cdot Q_{t-1}(\mbox{レバー}i\mbox{を下ろす}) + \frac{1}{k} \cdot r_k \\
  &= Q_{t-1}(\mbox{レバー}i\mbox{を下ろす}) + \frac{1}{k} \left(r_k - Q_{t-1}(\mbox{レバー}i\mbox{を下ろす}) \right)
\end{align}
}

となる。
 t回目にレバー iを下ろしたとしているので、 (t-1)回目までに、レバー i (k-1)回下ろされているということに注意)

一方、 t回目に下ろされなかったレバーについては、下ろされた回数が変化しないので、推定される行動の価値はそのまま。

したがって、 t回目に選択した行動を a_t、それによって得られた報酬を r_tとすると、推定される行動の価値は、

 {
Q_t(a) = \left\{ \begin{array}{ll}
Q_{t-1}(a) + \frac{1}{k} \left( r_t - Q_{t-1}(a) \right) & (a_t = a) \\
Q_{t-1}(a) & (a_t \ne a)
\end{array} \right.
}

と、再帰的に表現することが出来る。
なので、この式を使って推定される行動の価値を改善していくことが出来る。

※注意
参考にしている本の記述とは、添え字 tの扱いが1つズレているので注意。
本では Q_tを「 t回目の選択で参考にする推定価値」としているのに対し、この記事では「 t回目までの選択から推定された価値」としている。
行動は、1回目、2回目、・・・、 T回目となるので、 Q_tの添え字を Q_0から始めるのなら、この記事のような考え方をした方が、整合性がある。
(本のように考えるのなら、 Q_tの添え字は Q_1から始めるべき)

ポイントとなることが2つ。

まず、推定される行動の価値が改善されるのは、選択された行動に対してのみ、ということ。
なので、強化学習について学んでみた。(その4) - いものやま。で言及したように、「知識利用」をするだけでは、それ以外の行動については、推定される行動の価値が改善されていかないことになる。

もう一つは、再帰的に表現された更新式の意味合い。
この式は、次のように読むことが出来る:

 {
(\mbox{改善された価値}) = (\mbox{これまでの価値}) + (\mbox{係数}) \times (\mbox{報酬とこれまでの価値のギャップ})
}

つまり、観測されたギャップを使って、推定される行動の価値を少しずつ更新している、というわけだ。
この式に出てくる「係数」のことを、ステップサイズと呼んだりもする。
今回の場合、ステップサイズはその行動が選択された回数の逆数で、選択された回数が増えれば増えるほどステップサイズを小さくしていってることになるのだけれど、別の置き方(例えば、固定値)を考えることも出来る。


これで「行動の価値」について考えることが出来たので、明日はそれを使ってどのように行動の選択を行っていけばいいのかを考えていく。

今日はここまで!

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る