greedyアルゴリズム（貪欲法）

greedyアルゴリズムは、全部をN回試して、報酬の平均が最も高いやつを選択するというアルゴリズムです。

当たりか外れがでる機械が4個あって、どれが一番当たり率が高いか分からないのでgreedyアルゴリズムでやってみる想定にします。機械はa～dまであってそれぞれ当たり率は下記のとおりとします。

a	b	c	d
0.3	0.6	0.8	0.95

当たりが出たら1点もらえて、外れたら0点とします。

import numpy as np
import random

m = np.array([0.3, 0.6, 0.8, 0.95])
n = 3
total = 50

m_r = np.zeros([m.shape[0]])
m_c = np.zeros([m.shape[0]])
m_h = np.zeros([total])
cost = 0
reward = 0

for i in range(m.shape[0]):
    for _ in range(n):
        m_h[cost] = i
        if random.random() <= m[i]:
            reward += 1
            m_r[i] += 1
        cost += 1
        m_c[i] += 1
for i in range(total - m.shape[0] * n):
    good_m = np.argmax(m_r / m_c)
    m_h[cost] = good_m
    if random.random() <= m[good_m]:
        reward += 1
        m_r[good_m] += 1
    cost += 1
    m_c[good_m] += 1
print(cost)
print(reward)
print(reward / cost)
print(m_h)

結果

50
45
0.9
[ 0.  0.  0.  1.  1.  1.  2.  2.  2.  3.  3.  3.  2.  2.  2.  2.  2.  2.
  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  3.  3.  3.  3.  3.
  3.  3.  3.  3.  3.  3.  3.  3.  3.  3.  3.  3.  3.  3.]