限りなく院生に近いニート@エストニア

エストニアという国で一人ダラダラしてます。

The Epsilon-Greedy Algorithm

ε-greedyは機械学習においてよく使われる方法であり、そんなに理解に苦しいアルゴリズムではない。
Exploit のみを続けることに対するリスクを緩和する方法である。

僕が理解できれば、みんな余裕ってわけよ!

例えば、今目の前に3台のスロットマシンがあるとしよう(k=3)。
さらにそれぞれのマシンは、それぞれ違う確率で当たりが出るとし、合計100回チャレンジできるとする。

この時、どのマシンをどのくらい使えば、もっとも高い利益を出せるかという考え方については、前回触れたこちらの通りである。

tishow.hateblo.jp

ε-greedyは先に述べたようにそこまで複雑ではない。

マシンをプレイする時、それぞれのマシンがどのような結果を出していくかを皆追うと思う。そのとき、





Probability = (1 - \epsilon ) + \frac{ \epsilon}{k}

で現在もっともスコアの高いマシンを選択し、




Probability =  \frac{ \epsilon}{k}

で、ハイスコア出ないマシンを選択する。
この時、εは0.1とか、そういう小さい値である。

最初の12回の試合の後、マシン1を4回まわし、$ 1を2回、$ 0を2回獲得したとしよう。 このとき、マシン1の平均は$ 2/4 = $ 0.50である。

そしてマシン2を5回まわし、$ 1を3回、$ 0を2回獲得したとしよう。 マシン2の平均支払いは$ 3/5 = $ 0.60である。

そしてマシン3を3回まわし、$ 1を1回、$ 0を2回獲得したとしよう。 マシン3の平均支払いは$ 1/3 = $ 0.33である。

そして、試行13で再生するマシンを選択する必要があるが、このとき乱数pを0.0から1.0まで生成する。
また、ε= 0.10と設定したとする。
p> 0.10の場合は、現在の最高平均支払い額があるため、マシン2を選択する。
しかし、p <0.10の場合、ランダムなマシンを選択するので、各マシンは1/3の確率で選択される。

注意することは、すべてのマシンからランダムに選択するため、マシン2が選択される可能性があるということだ。

時間がたつにつれて、もっとも良いマシンはより頻繁にプレーされるため、より頻繁にプレイされる。
要するに、ε-greedy手段は、ほとんどの場合、現在の最良の選択肢を選ぶが、
ときどき小さな ε 確率でランダムなオプションを選ぶことがある。