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

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

Upper Confidence Bounds

Upper Confidence Boundsという方策について簡単にまとめたい。

今回の例においては、スロットマシンをどう選んで遊んでいくかを考えることがポイントであるが、

その際、結果を最大化するために、最適なマシンを選んでいくことが重要になってくる。

しかし、選択回数が少ないマシンについては、そのマシンからの結果が正確に推定できていない可能性がありますよね。

これらのバランスをとる方法が、Upper Confidence Boundsである。

マシンを選択する際、毎回以下の氷菓式で求められる評価値を算出し、最もスコアの高いアームを引く。



\bar{\mu_{i}}(t) = \hat{\mu}_{i}(t) + \sqrt{\frac{\log t}{2N_{i} (t)}}



\bar{\mu_i}(t)

時刻tのアームiのスコア



\hat{\mu}_{i}(t)
時刻tのアームiの標本平均



N_{i} (t)
時刻tまでのアームiの選択回数

*メリットとデメリット

メリット

どの程度マシンについて知っているかを考慮してマシンを選択できる。
パラメータを設定する必要がない。
最終的に最も良いアームのみを選ぶように収束する。

デメリット

悪いマシンをExploreのために引きすぎてしまう。

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手段は、ほとんどの場合、現在の最良の選択肢を選ぶが、
ときどき小さな ε 確率でランダムなオプションを選ぶことがある。

簡単に Bandit Algorithm Basic

What is Bandit Algorithm....

スロットマシンをする時、気になるのは、「どのマシンが一番当たりを出しやすいか」である。

今、目の前にスロットマジンが5台あるとして、50回遊べるだけのお金を持っているとしよう。

今現在の状況として、

目的:当たる確率を最大にしたい
マシン:5種類それぞれ違う当たる確率
遊べる回数:50回

この場合、どのマシンをどのように遊べばもっとも良い結果になるのだろうか。

考えられる戦略として、
1、それぞれ均等に遊ぶ(10回ずつ)
2、一つの台で遊び続ける
3、あたりの多かった台を集中的に選ぶ

Bandit Algorithmの目的は、

限られた試行回数の中で、もっとも良い選択をする

ということだ。

例えば、旅行の時の宿選び、合コンでの恋人選び、ランチのメニュー選びなど、

世の中には腐る程選択肢が溢れている。

ビジネスについてならば、

広告のクリエイティブはどうれが良い、メールのポイント、

たくさん思い浮かばれる。

しかし、これらを100%予測して行動することは不可能に近く、

思考を繰り返しながら経験値をして蓄え、次のチョイスをするのがベストになってくる。

条件も限られており、予算がいくらだ、期限はいつまでだと、

選択をより困難にしてくる。

そこで、ダメな選択肢をできる限り選ばないで、ベストな結果を出したい

という時に有効なのがBandit Algorithmである。

このアルゴリズムは2フェーズに別れており、

現在知っている情報以外の情報を得るためのExplore(例:行ってないレストランに行ってみる)と、

持ってる情報の中で利益を最大化することのExploit(例:行きつけのレストランでいつものメニューを頼む)

である。

この二つのトレードオフとして、

良い選択肢がわかっているのに、Exploreばかりしていると、効率の無駄使いになるし、

良い選択肢がまだわからないのに、Exploitばかりしていても効率的でない。

そこのバランスが重要になってくる。

このトレードオフを解決するのに使われるのが、

Algorithm Basicであり、

ExploreとExploitを効率的に行い、一定期間で最大の利益を出すメソッドである。

Python code is here.

tishow.hateblo.jp