簡単に Bandit Algorithm Basic

What is Bandit Algorithm....

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

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

今現在の状況として、

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

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

考えられる戦略として、
１、それぞれ均等に遊ぶ（１０回ずつ）
２、一つの台で遊び続ける
３、あたりの多かった台を集中的に選ぶ

Bandit Algorithmの目的は、

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

ということだ。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

である。

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

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

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

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

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

Algorithm Basicであり、

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

Python code is here.

tishow.hateblo.jp

A/B test with python (Bandit)

In this article, I am going to write a Bayesian Bandit algorithm.

import matplotlib.pyplot as plt
import numpy as np
from scipy.stats import beta

NUM_TRIALS = 2000
BANDIT_PROBABILITIES = [0.2, 0.5, 0.75]

Bandit probabilities are divided into three value just in case. Quick favorite.
Trial number is 2000.

So, I am going to define a class called Bandit.

class Bandit:
    def __init__(self, p):
        self.p = p
        self.a = 1
        self.b = 1
        
    def pull(self): # arm of slot machine
        return np.random.random() < self.p
    
    def sample(self): # sample from current beta distribution
        return np.random.beta(self.a, self.b)
    
    def update(self, x):
        self.a += x
        self.b += 1 - x

This works like slot machine.
a, b are the beta parameters defined a uniform distribution in the beginning and p is the probability of winning.

This class should have a ability to pull the slot machine defined definition pull() returns the random number and we can get also sample from its current distribution.

Lastly, we have also update function. x is either 0 or 1.

def plot(bandits, trial):
    x = np.linspace(0, 1, 200)
    for b in bandits:
        y = beta.pdf(x, b.a, b.b) 
        plt.plot(x, y, label="real p: %.4f" % b.p)
    plt.title("Bandit distributions after %s trials" % trial)
    plt.legend()
    plt.show()

This is just going to plot PDF of each bandit and we can compare it on the same chart.

OK. Then, we need to run a actual experiment.

def experiment():
    bandits = [Bandit(p) for p in BANDIT_PROBABILITIES]
    
    sample_points = [5, 10, 20, 50, 100, 200, 500, 1000, 1500, 1999]
    
    for i in range(NUM_TRIALS):
        bestb = None
        maxsample = -1
        allsamples = []
        for b in bandits:
            sample = b.sample()
            allsamples.append("%.4f" % sample)
            if sample > maxsample:
                maxsample = sample
                bestb = b
        if i in sample_points:
            print("Current samples: %s" % allsamples)
            plot(bandits, i)
            
        x = bestb.pull()
        bestb.update(x)

if __name__ == '__main__':
    experiment()

Bandit should be initialize at first.
Sample points are where we want to reasonably show a plot. Any values are ok.
We also keep track of the maximum sample and best will be.

A/B test with python

This is just going to make our generated datas as well as is able to emulate a real data collection surface.

class DataGenerator:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2
        
    def next(self):
        if np.random.random() < self.p1:
            click1 = 1
        else:
            click1 = 0
        
        if np.random.random() < self.p2:
            click2 = 1
        else:
            click2 = 0
        return click1, click2

p1 and p2 are probability of click for group 1 and group 2.

Next, I will write a function for obtaining the p-value.

def get_p_value(T):
        det = T[0,0]*T[1,1] - T[0,1]*T[1,0]
        c2 = float(det) / T[0].sum() * det / T[1].sum() * T.sum() / T[:,0].sum() / T[:,1].sum()
        p = 1 - chi2.cdf(x=c2, df=1)
        return p

I am going to explain p-value later in the other article.

Next, I will write a function for running a experiment.
That is going to include the probability of click for group1 and group2 and the number of samples.
In this case, I am going to take 2500 samples.

def run_experiment(p1, p2, N):
    data = DataGenerator(p1, p2)
    p_values = np.empty(N)
    T = np.zeros((2,2)).astype(np.float32)
    for i in range(N):
        c1, c2 = data.next()
        T[0,c1] += 1
        T[1,c2] += 1
        if i < 10:
            p_values[i] = None
        else:
            p_values[i] = get_p_value(T)
    plt.plot(p_values)
    plt.plot(np.ones(N)*0.05)
    plt.show()
    
run_experiment(0.1, 0.11, 2500)

    data = DataGenerator(p1, p2)

The data written above is to create an instance of data generator.

     if i < 10:
            p_values[i] = None
        else:
            p_values[i] = get_p_value(T)

We have to ignore the first a few datas in terms of taking into account p-value.
Because if we try to calculate the p-value too early, the formula might be broken.

      c2 = float(det) / T[0].sum() * det / T[1].sum() * T.sum() / T[:,0].sum() / T[:,1].sum()

I divided by row sums and column sums, so if any of those are 0, I cannot calculate it.