バンディットアルゴリズム

Multi-armed bandit problem

いくつもある選択肢の内で、どれが効果が高いのかは事前にはわからない状態で
限られた試行回数でできる限りいい選択肢を選んでいき、トータルの報酬を最大化する。

##ランダム選択

~~~:ランダム
def ランダム(回数,報酬):
    global 乱数,アーム数
    
    選択=random.randint(0,アーム数-1)

    更新(回数,報酬,選択)
~~~

##ε-greedy方策
Epsilon Greedy

乱数値(0.0～1.0)が、閾値ϵに対して、以下ならランダムに行動、それより大きければ評価値が最大となる行動(スロット)を選ぶ。

最大の報酬スロットばかりを狙うと、他の報酬の大きいスロットを見逃す可能性があるので
ある一定の確率で他のも試してみるという方策。

閾値ϵを0にすると、最大の報酬スロットばかりを狙うことになるので、貪欲法にになり
1にするとランダム選択になる

~~~:EpsilonGreedy
def EpsilonGreedy(回数,報酬,epsilon):
    global 乱数,アーム数

    if random.random()>epsilon:
        選択=np.argmax(報酬)
    else:
        選択=random.randint(0,アーム数-1)
        
    更新(回数,報酬,選択)
~~~

##UCB方策
Upper Confidence Bound

各アームの評価値を算出することで、選択回数が少ないアームもバランスをとってアームを選んでいくアルゴリズムとなります。

```math
{\hat{\mu_{i,t}} = \frac{\sum_{s=1}^{t}r_s}{N_{i,t}} \\
UCB_{i,t} = \hat{\mu_i} + \sqrt{\frac{2\log t}{N_{i,t}}}　\\
i_{t+1} = \arg\max_i UCB_{i,t}
}
```

~~~:UCB1
def UCB1(回数,報酬):
    global 乱数,アーム数

    総試行回数 = sum(回数)  
    #print("総試行回数",総試行回数)
    if min(回数)==0:
        選択=random.randint(0,アーム数-1)
    else:
        ucb値 = [0.0 for arm in range(アーム数)]
        for i in range(0,アーム数):
            バイアス = np.sqrt((2*np.log(np.array(総試行回数))) /  np.array(回数[i]))
            ucb値[i]  = np.array(報酬[i]) + バイアス
        選択=np.argmax(ucb値)
        
    更新(回数,報酬,選択)
~~~


##可視化結果例

<img width="800" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439291/b6c9d54a-97f2-a1ec-a2c6-6b10b2dcb5b0.png">


##本体コード
~~~
import random
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

グラフ数=10

#データフレーム
df = pd.DataFrame(index=[], columns=range(グラフ数+1))
df.columns=list(range(len(df.columns)))

#腕の成功確率
腕={0:0.1,1:0.1,2:0.1,3:0.1,4:0.9,5:0.1,6:0.2,7:0.1,8:0.05,9:0.2}
アーム数=len(腕)

def アーム(選択):
    global 乱数
    #print(腕[選択])
    if (腕[選択])>乱数:
        return 1  #成功
    else:
        return 0  #失敗

def 更新(回数,報酬,選択):
    回数[選択]=回数[選択]+1
    n=回数[選択]
    成功=アーム(選択)
    報酬[選択]=(報酬[選択]*(n-1)+成功)/n
    
成功=0
失敗=0
回数=[[0]*アーム数 for i in range(グラフ数)]
報酬=[[0]*アーム数 for i in range(グラフ数)]

n=3000
for i in range(1,n+1):
    乱数=random.random()

    ランダム(回数[0],報酬[0])     #回数、報酬
    EpsilonGreedy(回数[1],報酬[1],0)
    EpsilonGreedy(回数[2],報酬[2],0.1)
    UCB1(回数[3],報酬[3])
    EpsilonGreedy(回数[4],報酬[4],0.2)
    EpsilonGreedy(回数[5],報酬[5],0.3)
    EpsilonGreedy(回数[6],報酬[6],0.4)
    EpsilonGreedy(回数[7],報酬[7],0.5)
    EpsilonGreedy(回数[8],報酬[8],0.7)
    EpsilonGreedy(回数[9],報酬[9],0.9)

    df.loc[i] = [i ,
                  sum([x * y for (x, y) in zip(回数[0], 報酬[0])])/sum(回数[0]),
                  sum([x * y for (x, y) in zip(回数[1], 報酬[1])])/sum(回数[1]),
                  sum([x * y for (x, y) in zip(回数[2], 報酬[2])])/sum(回数[2]),
                  sum([x * y for (x, y) in zip(回数[3], 報酬[3])])/sum(回数[3]),
                  sum([x * y for (x, y) in zip(回数[4], 報酬[4])])/sum(回数[4]),
                  sum([x * y for (x, y) in zip(回数[5], 報酬[5])])/sum(回数[5]),
                  sum([x * y for (x, y) in zip(回数[6], 報酬[6])])/sum(回数[6]),
                  sum([x * y for (x, y) in zip(回数[7], 報酬[7])])/sum(回数[7]),
                  sum([x * y for (x, y) in zip(回数[8], 報酬[8])])/sum(回数[8]),
                  sum([x * y for (x, y) in zip(回数[9], 報酬[9])])/sum(回数[9])]

##可視化
plt.figure(figsize=(12.0, 6.0))
plt.xlabel("Time")
plt.ylabel("Average reward")
plt.grid(True) # グリッド
plt.plot(df[0],df[1], label="Random", color="red")
plt.plot(df[0],df[2], label="Greedy", color="green")
plt.plot(df[0],df[3], label="e-Greedy0.1", color="blue")
plt.plot(df[0],df[4], label="UCB1", color="orange")
plt.plot(df[0],df[5], label="e-Greedy0.2", color="black")
plt.plot(df[0],df[6], label="e-Greedy0.3", color="yellow")
plt.plot(df[0],df[7], label="e-Greedy0.4", color="pink")
plt.plot(df[0],df[8], label="e-Greedy0.5", color="violet")
plt.plot(df[0],df[9], label="e-Greedy0.7", color="yellowgreen")
plt.plot(df[0],df[10], label="e-Greedy0.9", color="brown")
plt.legend(loc='lower right') # 凡例
plt.show()
~~~