Q学習において方策をどのように定めるかということは、Q値、行動価値関数などの形式的な定義の後に来ることが多いです。そのような形式的な定義が頭に入っている前提で、方策を選ぶというQ学習において極めて重要な概念について私なりに説明していきます。
グリーディー法
行動価値（厳密にはQ値）の高いものばかりを優先して取るという手法です。
そのような行動は以下のように定式化されます。これは直感的でわかりやすいです。
a^*=max_{a}Q(s_t, a)
そして、そのような行動をとる確率は以下のように表されますが、直感的にわかりにくいです。
\pi(s_t,a)=\delta(a, a^*)
このクロネッカーのデルタで形式的な定義をしているのがわかりにくいです。
クロネッカーのデルタによる確率分布の意味
あなたは渋谷に来ました。
目の前にラーメン屋、健康定食屋さんがあります。
この状態では。Q値は以下のように求められたとします。
- ラーメン屋に行くこと: 100
- 健康定食屋に行く: 23
グリーティー法でない普通の方策であれば、
- ラーメン屋に行くこと: 20%
- 健康定食屋に行くこと: 66%
など確率的にどちらかが適当に確率が大きくなります。
この確率分布に従って多分健康定食屋に行くやろうけど、わんちゃんラーメン屋に行くことも理論上はありうる、みたいな状況になります。
一方で、グリーディー法の先ほどの形式的な定義によると
確率分布は
- ラーメン屋に行く:100%
- 健康定食屋に行くこと:0%
みたいなQ値の高い行動に対して確率が極端なものになります。もはや、確率分布というか、確定的な動きをしてますね。
このことを小難しく表したのが、クロネッカーのデルタを用いた先程の表現であり、それ以上の深い意味はないですね。
グリーディー法で方策を決める問題点
グリーディー法は、現時点でのベストしか考慮しないので、他の行動を検討することにつながりません。
例えば、グリーディー法で生きる太郎くんがいたとします。太郎くんは、小学生時代は「真冬も半袖は半パンがかっこいい」という間違った、それでいて当時はQ値が高い行動を選択していたします。しかし、もし太郎くんがもっと柔軟に、「ぱっと見半袖半パンがかっこいいかもしれないけど、おしゃれなコートで登校するのもありなのでは？」と、現時点でのQ値は高くないけれども、他の行動を用いたら、太郎くんの人生は実は、より良いものになっていた可能性もあるわけです。
では、グリーディー法と対極的な方策の選び方には他に何があるでしょう？
ランダム法 - 行き当たりばったりのセレンディピティ
この方策の選び方は、ランダムに行動を選ぶことです。より具体的には、等確率に行動を選びます。例えば、ラーメンを食べる、ポテトを食べる、タピオカを飲む、のうち1/3ずつの確率で行動を選びます。
これによって、Q値だけを見ると、ラーメンを食べるのが良かったけど、実際タピオカを飲んでみると、「食べるタピオカを作って売れば儲かるのでは？」といったビジネスアイデアがうかび、その後に起業して億万長者になる、みたいな漫画みたいな展開もありうるわけですね。
でも、どっちもどっちじゃね？
はい、そうですね。グリーディー法をとれば近視眼的な選択しかできないが、ランダム法で選択をすれば、「今までせっかくQ値計算したけど、ランダムなんなら意味ないやんけ〜うへー」となってしまうのです。探索をすれば知識が利用できないが、知識を利用すれば探索ができない、という難しい問題に直面します。
これが「利用と探索のトレードオフ」 Exploitation-explolation Trade-off です。
英語の名称は韻踏んでてかっこいいですね。どこぞのラッパーが考えたのでしょうか？
ではどうすればいいの？
「神のなせるままに、行動するしかないのか」
「いや、とりあえずQ値だけは計算してベストを尽くそう」
いや、諦めるのはまだ早いです。
そんなあなたに「ε-グリーディー法」や「ボルツマン選択」をお勧めします。
ε-グリーディー法
ケンタウロスみたいに、上半身は人間、下半身は馬という動物を知っていますか？
では、もし体が上半身:下半身=ε:1-εみたいなケンタウロスがいたらどうでしょう？
ε-グリーディー法はグリーディー法とランダム法の両方を取ったもの。
\pi(s_t,a_t)=P(a_t|s_t)=(1-\epsilon)\delta(a,a*)+\epsilon/N_A
こんな感じです。ここで$N_A$は今の状態でとりうる行動の総数ですね。
イプシロンを1-0の間で変化させて、どちらをどれだけ寄与させるか決めるという感じです。
少し苦肉の策感は否めませんね。。
ボルツマン選択
ボルツマン選択では、行動の確率分布を以下に従って変えます。
\pi(s_t,a_t)=P(a_t|s_t)\propto exp(\beta Q(s_t,a_t))
ここの比例$\propto$は何を表すのでしょうか？
これは、例えば、ラーメンを食べる、タピオカを食べる、などのそれぞれのQ値を正規化して、確率を求めるということです。
つまり
Q_{ラーメン}, Q_{タピオカ}
のようにQ値がわかっているときに
exp(\beta Q_{ラーメン}), exp(\beta Q_{タピオカ})
などをとりあえず計算します。そして、それぞれの値の和を求めます。
sum = exp(\beta Q_{ラーメン}) + exp(\beta Q_{タピオカ})
これにより以下のような、それぞれの行動の確率がもとまる、ということです。
exp(\beta Q_{ラーメン})/sum, exp(\beta Q_{タピオカ})/sum
なお、定数$\beta$は逆温度と呼ばれ、このパラメータを調整する必要があります。
これは、ε-グリーディ法のεと同じノリで、要は、グリーディー法の度合いとランダム法の度合いを決定するものです。
例えば、$\beta=0$だと、確率分布は完全にランダム法のそれと一致します。また、$\beta=1$だとグリーディー法と同じように、「Q値が高いものが、高い確率を持つ」というふうな確率分布が得られます。
まとめ
方策の決め方として、グリーディ法とランダム法があるが、以下の問題をはらむ。
探索するとQ値が利用できない。一方で、Q値ばかりを利用すると誤った行動を取る可能性もある。
このような探索と利用のトレードオフに対処するには、ε-グリーディ法やボルツマン選択がある。
けど、結局パラメータ選ぶのがむずくね？という感じでした。
参考文献
イラストで学ぶ人工知能概論 第二版
感想
教科書の数式は、形式的なものが多かったり、情報が抽象的に圧縮されすぎていることが多いです。
ですので、なるべく比喩を用いて説明しながら、この記事を書くことも、学習の一環として有効だったと感じました。
特に、ティーティングテクニックと呼ばれる、教えながら学ぶという方法は、学習効果が極めて高いことが数々の研究で示唆されてきました。
今後もこのような直感的な説明の記事を書いていきます。