そういえばQ熱って感染症があったな。不明の(Query)熱という意味だそうな。関係ないがQというパズルゲームがあって名作らしい。
食わず嫌いをしていても仕方がないのでちょっと調べてみた。割と単純な探索アルゴリズムの一種だった。自然界の～とか、脳内の～とか言うから胡散臭くなるだけで、コンピュータ上で動作させる他の探索アルゴリズムの一種だと思います。
結論は、枝コスト選択の難しさの解決を後回しにしたところで避けられない。というより、枝コスト選択を先にやらなくて良い、という事実が唯一にして最大のメリット。
アルゴリズムの概要
探索の際に選ぶ枝のコストを確率として予め求めておくのではなく、探索しながら更新していく。
前提は以下。
- stは時刻tにおける状態。
- atは時刻tにおける行動。
- Q(st,at)は状態stにおいて行動atを選択する価値。
- rt+1は環境の変化によって貰える報酬。
- maxaQ(st+1,a)は 状態st+1のもとで最もQ値が高い行動aを選んだ場合のQ値。
- γ(0<γ<1)は割引率。
- α(0<α<1)は学習係数。
Q(st,at)を更新しQ(st+1,at+1)にする式は以下。
Q(st+1,at+1) := Q(st,at) + α(rt+1+γ maxaQ(st+1,a)-Q(st,at))
γ、rt+1の値によるが、Q(st+1,at+1)>Q(st,at)となるためには、Q(st,at)よりも、次の状態における最良の行動aを選択した価値Q(st+1,a)の方が大きい必要がある。
一般的にγ=0.9～0.99のように1に近い値を設定することが多いようなので、概ね最良の行動の選択maxaQ(st+1,a)による価値の増加分に報酬rt+1を加えたものがQ(st+1,at+1)となる。
アルゴリズムの設計
- 全ての状態とその時に取りえる行動の組(s,a)についてQ(s,a)の値をランダムに設定する。
- t=0、s0にセットする。
- 状態stから行動atを選択し状態st+1とする。
- 状態の更新を一定回数行ったらt=0,s0に戻す。
- グルグル回し、何回か終わったら終了。
状態の更新にはε-greedyアルゴリズムを用いる。状態stから状態st+1に遷移する際、常に最大のQ値となる行動を取るということは、最初にランダムで与えたQ(s,a)を教師として枝コストに確率を与えているのと同じになるからN.G.。定数ε(0<ε<1)を用い(1-ε)の確率で最大のQ値となる行動を選ぶようにする。
胡散臭くなってきた！結局枝コストの求め方の難しさに帰着する。たぶん確率密度とかの話ではなくエイヤっとεを決めるんだろう。