深圳大学人工智能概述_实验三（多臂老虎机）
发布时间
阅读量：
阅读量
问题描述
你进了一家赌场，假设面前有
台数老虎机（arms）。我们知道，老虎机本质上是运气游戏的一种形式，在这里我们假设每台老虎机
都有一定概率
吐出一块钱，或者不吐钱（ 概 率
）。假设你手上只有
枚代币单位（tokens），每次游戏消耗一枚代币意味着你每次游戏都需要一枚代币。
次，那么如何做才能使得期望回报（expected reward）最大呢？
不同解决思路
设置相关变量
贪心
思路：总是选择当前评估值最高的老虎机进行游戏，并根据游戏结果调整该台老虎机的获奖概率
伪代码：
贪心
在不同情况下选择未被充分探索的老虎机（非基于预测概率的随机选择是一种探索策略），以获取潜在高回报；同时，在持续尝试过程中逐步提高对各老虎机出奖概率的估计精度；另一种策略则直接应用到当前被认为具有最高获奖概率的老虎机上（一种利用策略）。
流程图：
伪代码：
softmax
思路：每一次都采取随机策略（非等概率地进行选择），高奖励概率的老虎机更容易被选中。
伪代码：
程序设计
因为每台老虎机默认设置了出奖概率参数，并且在三种不同的算法中都采用了相同的回报机制。建议首先构建相应的可用类。
老虎机类
- 属性：奖机数量、各台机器中奖几率（允许用户自行设定初始值，并可采用随机生成的方式初始化参数）以及最优中奖概率值
- 方法：采用根据出奖几率分配奖励机制（仅限于1或0两种结果）
ps:
有0.4的概率出奖即，随机生成一个[0,1]的数，小于0.4的概率
小于0.4时返回1；否则返回0 即可实现
class BernoulliBandit():
def __init__(self, K, probas=None): #n为摇臂的个数，probas为每个摇臂获得奖励的概率
assert probas is None or len(probas) == K
self.K = K
if probas is None:
np.random.seed(int(time.time()))
self.probas = [np.random.random() for _ in range(self.K)]
else:
self.probas = probas
self.best_proba = max(self.probas)
def generate_reward(self, i):
# The player selected the i-th machine.
if np.random.random() < self.probas[i]:
return 1 #满足发生的概率，就获得奖励1
else:
return 0
python
求解算法有关参数设计
：第i台老虎机评估的概率 ------列表即可
:第i台老虎机玩过的次数 --------列表即可
：总获奖积分 ------数即可
：第k台老虎机返回的奖励 ------列表即可
y：平均每步得分（用来衡量算法好坏） ------列表即可
贪心算法代码
def greedy_strategy(bandit,T,r,Q,count):
r=0
y=[]
for t in range(1,T+1):
j=np.argmax(Q)
reward=bandit.generate_reward(j)
r+=reward
y.append(r/t)
Q[j]=(Q[j]*count[j]+reward)/(count[j]+1)
count[j]+=1
print("累积奖励：",r)
print("每个摇臂选择次数： ",count)
print("每个摇臂的估计值： ",Q)
print("每个摇臂真实获奖的概率： ",bandit.probas)
return y
python
贪心算法代码
def greedy_e_strategy(bandit,K,T,epsilon,r,Q,count):
r=0
y=[]
for t in range(1,T+1):
if np.random.random()<epsilon:
j=np.random.randint(0,K)
else:
j=np.argmax(Q)
reward=bandit.generate_reward(j)
r+=reward
y.append(r/t)
Q[j]=(Q[j]*count[j]+reward)/(count[j]+1)
count[j]+=1
print("累积奖励：",r)
print("每个摇臂选择次数： ",count)
print("每个摇臂的估计值： ",Q)
print("每个摇臂真实获奖的概率： ",bandit.probas)
return y
python
softmax算法代码
def softmax(bandit,K,T,epsilon,Q,r,count):
r=0
y=[]
property_list=np.zeros(K)
for t in range(1,T+1):
Probability_accumulation=0
total_accumulation=sum(pow(e,Q[i]/epsilon) for i in range(K))
random_value=np.random.random()
for i in range(K):
property_list[i]=pow(e,Q[i]/epsilon)/total_accumulation
Probability_accumulation+=property_list[i]
if random_value<Probability_accumulation :
j=i
break
reward=bandit.generate_reward(j)
r+=reward
y.append(r/t)
Q[j]=(Q[j]*count[j]+reward)/(count[j]+1)
count[j]+=1
print("累积奖励：",r)
print("每个摇臂选择次数： ",count)
print("每个摇臂的估计值： ",Q)
print("每个摇臂真实获奖的概率： ",bandit.probas)
return y
python
结果查看
- 可视化平均奖励
随着尝试次数的增加，平均得分趋于稳定，其中贪心（中间）的结果浮动较大。
- 每台老虎机估测获奖概率与实际获奖概率比较
整体代码
import numpy as np
import time
import matplotlib.pyplot as plt
e=2.718
class BernoulliBandit():
def __init__(self, K, probas=None): #n为摇臂的个数，probas为每个摇臂获得奖励的概率
assert probas is None or len(probas) == K
self.K = K
if probas is None:
np.random.seed(int(time.time()))
self.probas = [np.random.random() for _ in range(self.K)]
else:
self.probas = probas
self.best_proba = max(self.probas)
def generate_reward(self, i):
# The player selected the i-th machine.
if np.random.random() < self.probas[i]:
return 1 #满足发生的概率，就获得奖励1
else:
return 0
#参数K：摇臂个数，T：试验次数，epsilon：探索概率,r:累积奖励,Q:每个摇臂的估计值,count:每个摇臂的选择次数
def greedy_e_strategy(bandit,K,T,epsilon,r,Q,count):
r=0
y=[]
for t in range(1,T+1):
if np.random.random()<epsilon:
j=np.random.randint(0,K)
else:
j=np.argmax(Q)
reward=bandit.generate_reward(j)
r+=reward
y.append(r/t)
Q[j]=(Q[j]*count[j]+reward)/(count[j]+1)
count[j]+=1
print("\n贪心-ε策略：\n")
print("累积奖励：",r)
print("每个摇臂选择次数： ",count)
print("每个摇臂的估计值： ",Q)
print("每个摇臂真实获奖的概率： ",bandit.probas)
return y
def greedy_strategy(bandit,T,r,Q,count):
r=0
y=[]
for t in range(1,T+1):
j=np.argmax(Q)
reward=bandit.generate_reward(j)
r+=reward
y.append(r/t)
Q[j]=(Q[j]*count[j]+reward)/(count[j]+1)
count[j]+=1
print("\n贪心策略:\n")
print("累积奖励：",r)
print("每个摇臂选择次数： ",count)
print("每个摇臂的估计值： ",Q)
print("每个摇臂真实获奖的概率： ",bandit.probas)
return y
def softmax(bandit,K,T,epsilon,Q,r,count):
r=0
y=[]
property_list=np.zeros(K)
for t in range(1,T+1):
Probability_accumulation=0
total_accumulation=sum(pow(e,Q[i]/epsilon) for i in range(K))
random_value=np.random.random()
for i in range(K):
property_list[i]=pow(e,Q[i]/epsilon)/total_accumulation
Probability_accumulation+=property_list[i]
if random_value<Probability_accumulation :
j=i
break
reward=bandit.generate_reward(j)
r+=reward
y.append(r/t)
Q[j]=(Q[j]*count[j]+reward)/(count[j]+1)
count[j]+=1
print("\nsoftmax:\n")
print("累积奖励：",r)
print("每个摇臂选择次数： ",count)
print("每个摇臂的估计值： ",Q)
print("每个摇臂真实获奖的概率： ",bandit.probas)
return y
fig,axs=plt.subplots(1,3,figsize=(10,5))
k_=5
T_=4000
bandit = BernoulliBandit(K=k_)
y_ge=greedy_e_strategy(bandit,K=k_,T=T_,epsilon=0.1,r=0,Q=np.zeros(k_),count=np.zeros(k_))
x=[i for i in range(0,T_+1)]
y_ge=[0]+y_ge
axs[0].plot(x,y_ge)
axs[0].set_xlabel('round')
axs[0].set_ylabel('average reward')
axs[0].set_title('greedy-epsilon strategy')
y_g=greedy_strategy(bandit,T=T_,r=0,Q=np.zeros(k_),count=np.zeros(k_))
x=[i for i in range(0,T_+1)]
y_g=[0]+y_g
axs[1].plot(x,y_g)
axs[1].set_xlabel('round')
axs[1].set_ylabel('average reward')
axs[1].set_title('greedy strategy')
y_sf=softmax(bandit,K=k_,T=T_,epsilon=0.1,r=0,Q=np.zeros(k_),count=np.zeros(k_))
x=[i for i in range(0,T_+1)]
y_sf=[0]+y_sf
axs[2].plot(x,y_sf)
axs[2].set_xlabel('round')
axs[2].set_ylabel('average reward')
axs[2].set_title('softmax strategy')
plt.suptitle("K:%d T:%d "%(k_,T_))
plt.show()
python
想法：
1、在估测每台老虎机出奖概率
在初始状态下正常全零的情况下会发现贪心策略会出现较大的波动（有时表现优异有时表现不佳）。这是由于基于贪心算法的核心机制是当某一老虎机表现出色后其评分会被提升从而促使后续选择该设备即使后续未再获得奖励但其评分仍高于零点在之后的步骤中它将不再考虑其他老虎机。即意味着一旦某台老虎机首次给予奖励就会一劳永逸地选择该设备直到不再遇到其他可能提供更高回报的选项。但是若把这种单一策略应用到复杂场景中可能会导致无法捕捉到潜在更高的回报机会因此需要采取更为灵活的策略如动态调整参数或结合探索与利用的思想以平衡即时收益与长期收益之间的关系
全部设为1后差别会非常大！让贪心也具有了探索的潜力，得分表现优异，其本质在于过于注重失误而忽视了整体策略的优化。
2、这个问题可以看成多台老虎机也可以看成一个老虎机的多个摇臂。
3、可再定义忏悔值等不同指标去帮助观测算法在此问题上的差异
全部评论 (0)
还没有任何评论哟~