K摇臂赌博机 --ε-贪心算法(原理与Python代码实现模拟)

吐出硬币，赌徒事先并不知道每个摇臂吐出概率的的情况，需要使得赌徒获得硬币最大？

解决这个问题，其中有两种简单的解法：

仅利用：

 选择目前为止平均奖赏最大的摇臂，缺点没有很好地估计摇臂的期望奖赏，可能经常选择不到最优的

奖赏，

仅探索：

 将选择的机会平均分给每个摇臂，计算每个摇臂的平均奖赏，选择其中平均奖赏最大的那一个，缺点

，很好地估计摇臂的期望奖赏，但是会失去很多选择最优奖赏的机会。

 我觉得是这样理解，结合实际应用场景，实际中，我们知道平均奖赏最大的摇臂，一般可能都会比

我们投入的币少，毕竟商家是为了赢钱，所以用仅探索法，选择平均奖赏最大的，可能一直选择不到奖赏最

大的，也就是可能奖赏最大的摇臂，他吐币的概率低，为吐币概率高的摇臂他吐出的币少，如果使用仅利用

，那么我们得到最优奖赏的次数就很好，因为奖赏最大的摇臂吐币概率很低。所以这个告诉我们，不要妄想

靠这种方式挣钱，精明的商家早就算好了。

ε-贪心算法

贪心算法的基本思路：

ε是基于概率进行探索，ε作为随机选择一个摇臂的概率，那么1-ε的概率用于从平均奖赏最大的摇臂里面

选择。

算法实现的过程：

输入：摇臂的总数，K

k(小写) 表示当前选择第k个摇臂

奖赏函数 R

尝试次数 T

探索概率 ε

累计奖励用r表示累计奖励

Q(i) 表示第i个摇臂的平均奖赏

初始化 r=0，Q(i) = 0

For i in range(T):

If random()<ε:

k = Random.choice(range(1,K+1))

Esle：

k = argmax(Q(i))

v = R(k)  (表示当前的奖赏)

r = r + v

Count(k) = count(k)+1

Print(“the reward is”.format(r)) # 输出累计奖赏

Python代码模拟仿真：

使用贪心算法实现

from numpy import random
K = [1,2,3,4,5] # 总共的摇臂数有5个
R = {1:2,2:3,3:5,4:1,5:9}  # 各个摇臂对应的奖赏
prob = {1:0.6,2:0.5,3:0.2,4:0.7,5:0.05}  #各个摇臂对应的概率吐币的概率
T = 10000
eplison = 0.1
count = dict(zip(list(range(1,6)),[0]*5))  # 计算每个摇臂的摇到的次数

r = 0
for i in range(T):
    
    Q = dict(zip(list(range(1,6)),[0]*5))
    
    if random.random() < eplison:
        k = random.choice(K)
    else:
        k = max(Q,key=Q.get)
    
    v = random.choice([R[k],0],p=[prob[k],1-prob[k]])
    r += v
    Q[k] = (Q[k]*count[k]+v)/(count[k]+1)
    
    count[k] = count[k] + 1
print("end the reword is {}".format(r))

r = 0
for i in range(T):
    k = random.choice(K)
    v = random.choice([R[k],0],p=[prob[k],1-prob[k]])
    r+=v
print("end the reword is {}".format(r))   

经过我多次运行对比，大家也可以去跑一p，使用ε-贪心算法的结果总是比随机好，说明ε贪心算法还

是有用的，比随机好