强化学习中的multiarmed-Bandit以及经典解法epsilon-greedy算法。。。
最近在看Management Science上的⽂章《A Dynamic Clustering Approach to Data-Driven Assortment Personalization》，其中提到了⼀个Multiarmed-Bandit模型，想要深⼊学习⼀下，但是查遍各种⽹站，都没有中⽂的关于这个问题的介绍，因此去油管上学习，然后翻译成中⽂在这⾥跟⼤家分享。
Exploration and exploitation tradeoff
在强化学习中有⼀个经典问题，即Exploration and esploitation tradeoff，在该问题中有⼀个两难境地：到底我们应该花精⼒去探索从⽽对收益有更精确的估计，还是应该按照⽬前拥有的信息，选择最⼤收益期望的⾏动？
由此引申出Multiarmed-Bandit模型
Multiarmed-Bandit Model
假设现在有n台⽼虎机，每台⽼虎机的收益不同，但我们事先并不知道每台⽼虎机的期望收益。
我们在这⾥假设：每台⽼虎机的收益服从⽅差为1的正态分布，均值事先并不知道。我们需要探索每台⽼虎机的收益分布，并最终让⾏动选择拥有最有的期望收益的⽼虎机。
传统的解决⽅案 A/B test
A/B test的思路是，给每台⽼虎机分配数量相同的测试数⽬，然后根据所有⽼虎机的测试结果，选择表现最优的⽼虎机进⾏剩下的所有操作。流传千古
这种⽅法的最⼤劣势就是将探索与开发割裂开来。在探索过程中只考虑探索，只收集信息，⽽在开发的阶段就不再考虑探索，也就失去了学习的机会，有可能陷⼊了局部最优，没有找到最优的⽼虎机。
epsilon-greedy 算法
epsilon-greedy算法也是⼀种贪婪算法，不过在每次选择的过程中，会以⼀个较⼩的改了选择不是最优⾏动的其他⾏动，从⽽能够不断进⾏探索。由于epsilon较少，并且最终算法会找到最优的⾏动，因此最终选择最优的⾏动的概率会趋近于1-epsilon。
下⾯展⽰python代码：
import numpy as np
import matplotlib.pyplot as plt
class EpsilonGreedy:
def__init__(lf):
lf.epsilon =0.1# 设定epsilon值
lf.num_arm =10# 设置arm的数量
lf.arms = np.random.uniform(0,1, lf.num_arm)# 设置每⼀个arm的均值，为0-1之间的随机数 lf.best = np.argmax(lf.arms)# 找到最优arm的index
lf.T =50000# 设置进⾏⾏动的次数
不孕不育医院哪家好
lf.hit = np.zeros(lf.T)# ⽤来记录每次⾏动是否找到最优arm
lf.num = np.zeros(lf.num_arm)# ⽤来记录每次⾏动后各个arm被拉动的总次数
def get_reward(lf, i):# i为arm的index
return lf.arms[i]+ al(0,1)# ⽣成的收益为arm的均值加上⼀个波动
def update(lf, i):
lf.num[i]+=1
def calculate(lf):
for i in range(lf.T):
if np.random.random()> lf.epsilon:
index = np.ward)大大连
el:
a = np.ward)
index = a
while index == a:
index = np.random.randint(0, lf.num_arm)
if index == lf.best:
lf.hit[i]=1# 如果拿到的arm是最优的arm，则将其记为1
lf.update(index)
def plot(lf):# 画图查看收敛性
x = np.array(range(lf.T))
悠悠球轴承
y1 = np.zeros(lf.T)
t =0
薏仁水有什么功效
for i in range(lf.T):
t += lf.hit[i]
y1[i]= t/(i+1)
y2 = np.ones(lf.T)*(1-lf.epsilon)
plt.plot(x, y1)
plt.plot(x, y2)
plt.show()
E = EpsilonGreedy()
E.calculate()
E.plot()
最终的结果如下图所⽰：
随着⾏动的不断进⾏，累计准确率（选到最优arm的频率）在不断上升，并且逼近了我们所设置的上线，证明了-greedy算法的有效性！
UCB 算法
在解决multiarmed-bandit问题中，还有⼀个⽐-greedy算法更加实⽤的算法，称为Upper Confidence Bound(UCB)算法。
在-greedy算法收敛后，始终会以⼀个的概率去选择不是最优的⽅案，⽽此时最优的⽅案⼤概率已经被找到，因此就造成了⽩⽩的浪费。UCB算法就很好的解决了这个问题。
下⾯展⽰UBC的python代码：
1−ϵϵϵϵϵ
import numpy as np
import matplotlib.pyplot as plt
# Set δ = 1/n**4 in Hoeffding's bound
# Choo a with highest Heoffding bound
class UCB:
def__init__(lf):
lf.num_arm =10# 设置arm的数量
lf.arms = np.random.uniform(0,1, lf.num_arm)# 设置每⼀个arm的均值，为0-1之间的随机数 lf.best = np.argmax(lf.arms)# 找到最优arm的index
lf.T =100000# 设置进⾏⾏动的次数
lf.hit = np.zeros(lf.T)# ⽤来记录每次⾏动是否找到最优arm
lf.num = np.ones(lf.num_arm)*0.00001# ⽤来记录每次⾏动后各个arm被拉动的总次数
lf.V =0
lf.up_bound = np.zeros(lf.num_arm)
def get_reward(lf, i):# i为arm的index
return lf.arms[i]+ al(0,1)# ⽣成的收益为arm的均值加上⼀个波动
def update(lf, i):
lf.num[i]+=1
维铁缓释片
lf.V += lf.get_reward(i)
def calculate(lf):英语介绍春节
for i in range(lf.T):
for j in range(lf.num_arm):
lf.up_bound[j]= lf.reward[j]+ np.sqrt(2*np.log(i+1)/lf.num[j])
index = np.argmax(lf.up_bound)
if index == lf.best:
lf.hit[i]=1
lf.update(index)
def plot(lf):# 画图查看收敛性
x = np.array(range(lf.T))
y1 = np.zeros(lf.T)
t =0
for i in range(lf.T):
t += lf.hit[i]
y1[i]= t/(i+1)
plt.plot(x, y1)
plt.show()
U = UCB()
U.calculate()
U.plot()
运⾏之后的结果为：
可见，随着⾏动不断进⾏，累计选取最优⽼虎机的频率不断上升，并且没有1-上限。
-greedy 算法与UCB 算法对⽐
为了更好说明UCB算法的优越性，我们将这两种算法放在⼀起进⾏对⽐，代码如下：
成都特产有哪些import numpy as np
import matplotlib .pyplot as plt
class MultiArmedBandit :
def __init__(lf ):
lf .epsilon = 0.1 # 设定epsilon 值
lf .num_arm = 10 # 设置arm 的数量
lf .arms = np .random .uniform (0, 1, lf .num_arm ) # 设置每⼀个arm 的均值，为0-1之间的随机数 lf .best = np .argmax (lf .arms ) # 找到最优arm 的index
lf .T = 100000 # 设置进⾏⾏动的次数
lf .hit_epsilon = np .zeros (lf .T ) # ⽤来记录每次⾏动是否找到最优arm
lf .hit_ucb = np .zeros (lf .T )
lf .reward_epsilon = np .zeros (lf .num_arm ) # ⽤来记录每次⾏动后各个arm 的平均收益
lf .reward_ucb = np .zeros (lf .num_arm )
lf .num_epsilon = np .zeros (lf .num_arm ) # ⽤来记录每次⾏动后各个arm 被拉动的总次数
lf .num_ucb = np .ones (lf .num_arm )*0.000000001
lf .V_epsilon = 0
lf .V_ucb = 0
lf .up_bound = np .zeros (lf .num_arm )
def get_reward (lf , i ): # i 为arm 的index
return lf .arms [i ] + np .random .normal (0, 1) # ⽣成的收益为arm 的均值加上⼀个波动
def update_epsilon (lf , i ):
lf .num_epsilon [i ] += 1
lf .reward_epsilon [i ] = (lf .reward_epsilon [i ]*(lf .num_epsilon [i ]-1)+lf .get_reward (i ))/lf .num_epsilon [i ] lf .V_epsilon += lf .get_reward (i )
def update_ucb (lf , i ):
lf .num_ucb [i ] += 1
lf .reward_ucb [i ] = (lf .reward_ucb [i ]*(lf .num_ucb [i ]-1)+lf .get_reward (i ))/lf .num_ucb [i ]ϵϵ
