在Bandit问题的第一期提到（n-Armed Bandit Problem（一）），我们可以使用贪婪算法来得到最大回报。这种贪婪算法有两种，即e等于0或e不等于0。接下来，我们可以分别写出它们的代码并得到实验结果。
根据之前假设，每个决策都会得到一个由高斯分布产生的随机回报值。而这个假设是固定不变的，因此我们可以先写出一个Bandit类：
#coding=utf-8
import math
import random
import matplotlib.pyplot as plt
class Bandit:
"""设置奖励.
"""
def __init__(self, mu, sigma):
"""初始化高斯分布参数"""
self.mu = mu
self.sigma = sigma
def get_reward(self):
"""得到随机数作为奖励"""
return random.gauss(self.mu, self.sigma)
def describe(self):
''''''对Bandit添加描述''''''
return "Bandit({mu:.1f}, {sigma:.1f})".format(
mu=self.mu, sigma=self.sigma)
然后，我们需要对每个bandit的回报进行估计，这里涉及到一个初始化的问题，一般情况下我们对每个bandit的回报设计一个固定的统一值，然后让系统进行自由行走并且接受回报、更新回报。接下来可以写一下回报估计类，
class RewardEstimator:
"""Bandit的回报估计
"""
''''''estimates中存储的是一对tuple，一开始设置为None''''''
estimates = None
def initialize(self, first_estimates):
"""对每一个bandit设置一对tuple，其中e代表此刻的估计值，1代表该估计值是基于过去一共1次观察的结果''''"
self.estimates = [(e, 1) for e in first_estimates]
def receive_reward(self, bandit_number, reward):
"""基于观察次数来更新bandit的回报"""
(current_estimate, current_count) = self.estimates[bandit_number]
#回报更新公式，类似梯度下降
new_estimate = current_estimate + (reward - current_estimate ) / (current_count+1)
self.estimates[bandit_number] = (new_estimate, current_count + 1)
def reward_estimates(self):
"""获取每个bandit的此刻回报估计值"""
return [x[0] for x in self.estimates]
接下来我们可以设计策略了，策略就是使用贪婪算法，即我们允许有e的概率让系统进行随机游走，而允许有1-e的概率让系统服从最优决策。这里我们让贪婪决策继承自RewardEstimator类，这样写的好处是精简代码，并且由于RewardEstimator是固定的，如果使用其他决策算法的话，也可以自由扩展代码。
class EpsilonExplorer(RewardEstimator):
"""e贪婪算法"""
def __init__(self, epsilon):
self.epsilon = epsilon
def describe(self):
"""添加描述"""
return "Epsilon-explorer({:.1%})".format(self.epsilon)
def choose_bandit(self):
"""选择策略，以决定下一个bandit是什么"""
reward_estimates = self.reward_estimates()
num_bandits = len(reward_estimates)
if random.random() < self.epsilon:
return random.randrange(num_bandits)
else:
best_reward = reward_estimates[0]
best_bandit = 0
for k,v in enumerate(reward_estimates):
if v > best_reward:
best_reward = v
best_bandit = k
return best_bandit
有时候，固定的e不一定是最优的，并且，随着时间的推移，我们有理由相信自由行走的幅度可以慢慢减弱，因此这里可以扩充e贪婪算法为衰减型e贪婪算法，即让e的值随着时间的推移逐步呈指数衰减。由于它是改自普通的e贪婪算法的，所以这个类是EpsilonExplorer的子类。
class DescendingEpsilonExplorer(EpsilonExplorer):
"""衰减型e贪婪算法，就逐步缩小e的值即可，其他策略方面继承自父类即可
"""
def __init__(self, epsilon, descent_rate):
self.original_epsilon = epsilon
EpsilonExplorer.__init__(self, epsilon)
self.descent_rate = descent_rate
def describe(self):
return "Descending epsilon-explorer(eps={:.1%}, desc={:.3f})".format(self.original_epsilon, self.descent_rate)
def choose_bandit(self):
self.epsilon *= self.descent_rate
return EpsilonExplorer.choose_bandit(self)
另外，上一期我也提到过，除了贪婪算法进行决策以外，还有一种决策算法叫softmax决策，只不过这里做了一个权重的放缩。
class SoftmaxExplorer(RewardEstimator):
"""Softmax决策器,temperature是一个放缩因子
"""
def __init__(self, temperature):
self.temperature = temperature
def describe(self):
return "Softmax-explorer({:.1f}K)".format(self.temperature)
def choose_bandit(self):
weights = [math.exp(estimate/self.temperature) for estimate in self.reward_estimates()]
total = sum(weights)
choice = random.uniform(0, total)
for bandit_number, weight in enumerate(weights):
choice -= weight
if choice < 0:
break
return bandit_number
最后，我们可以分别比较一下纯贪婪算法、e贪婪算法、衰减型e贪婪算法、Softmax算法这几种决策对结果的影响，一共有10个bandits，共进行了1000次实验，并且我们设置如下几个决策器：
EpsilonExplorer(0),
EpsilonExplorer(0.01),
EpsilonExplorer(0.1),
DescendingEpsilonExplorer(0.1, 0.999),
SoftmaxExplorer(1),
SoftmaxExplorer(0.5),
SoftmaxExplorer(2)
def get_strategies(reward_estimates):
"""列举声明所有决策器"""
strategies = [
EpsilonExplorer(0),
EpsilonExplorer(0.01),
EpsilonExplorer(0.1),
DescendingEpsilonExplorer(0.1, 0.999),
BoltzmannExplorer(1),
BoltzmannExplorer(0.5),
BoltzmannExplorer(2),
]
for strat in strategies:
strat.initialize(reward_estimates)
return strategies
def main(num_bandits, iterations):
"""运行n-bandits问题的主程序"""
bandits = [Bandit(random.uniform(1,10), random.uniform(1, 5) ) for _b in range(num_bandits)]
reward_estimates = [b.get_reward() for b in bandits]
expected_rewards = [b.mu for b in bandits]
best_bandit_choice = expected_rewards.index(max(expected_rewards))
print("*** Bandits and initial reward estimates ***")
print("\n".join(["{bandit} with estimate {est:.1f}".format(bandit=b.describe(), est=e) for (b,e) in zip(bandits, reward_estimates)]))
strategies = get_strategies(reward_estimates)
#对每个策略进行迭代
gain_histories = [[0] for s in strategies]
gains = [0 for s in strategies]
choice_correctness = [[0] for s in strategies] # Stores average correctness of choice; starts with 0 for ease of implementation
for n in range(iterations):
for number_strat, strat in enumerate(strategies):
chosen_bandit = strat.choose_bandit()
reward = bandits[chosen_bandit].get_reward()
choice_correctness[number_strat].append(
choice_correctness[number_strat][len(choice_correctness[number_strat])-1]*n/(n+1)
+ (chosen_bandit==best_bandit_choice)/(n+1)
)
gains[number_strat] += reward
gain_histories[number_strat].append(gains[number_strat]/(n+1))
strat.receive_reward(chosen_bandit, reward)
# 打印累计回报
print("\n*** 累计回报 ***")
for (s,g) in zip(strategies, gains):
print( "{} gained {:.0f}".format(s.describe(), g) )
# 作图
handles =
for (hist, s) in zip(gain_histories, strategies):
h, = plt.plot(hist, label=s.describe())
handles.append(h)
plt.legend(handles=handles, loc=4) # Lower right
plt.title('Average Rewards')
plt.show()
if __name__ == '__main__':
main(10,1000)
然后，作出实验结果曲线。
这个实验结果表明，在实验早期阶段，纯贪婪算法的平均回报较高，而从长期来看，衰减型e贪婪算法表现较好，而softmax算法的温度系数设置较大时长期回报较低，温度系数设置较低时与贪婪算法表现持平。
它们的总回报如下：
Epsilon-explorer(0.0%) gained 9587
Epsilon-explorer(1.0%) gained 9764
Epsilon-explorer(10.0%) gained 9583
Descending epsilon-explorer(eps=10.0%, desc=0.999) gained 9769
Softmax-explorer(1.0K) gained 9502
Softmax-explorer(0.5K) gained 9703
Softmax-explorer(2.0K) gained 9154
可以看到，设置衰减型贪婪算法效果较好，并且对于softmax，设置温度系数较低可以与贪婪算法表现持平。
以上所讲的解决n-armed bandit problem的决策算法都算是贪婪算法的变体，除此之外，还有一种算法叫做UCB，即Upper Confidence Bound，即向上置信界限，即在每次做决策时选择UCB最大的那个，对于贪婪算法与UCB的性能表现，这里就不详细介绍，不过有实验证明，它们的表现如下所示：
从上图可以看出（注意纵轴是Regret）：
纯贪婪算法和随机算法在起初阶段表现相当，但是随后纯贪婪算法就立刻保持原样了，这种算法在实际中是无法应用的；
e贪婪算法表现一般，不过缺乏衰减型e贪婪算法进行对照；
UCB表现最好，虽然无法区分哪种UCB较好；
最后讲一下n-Armed Bandit Problem的应用，由于这个问题实际上是在exploration和exploitation之间做出一个折中，通常可以用于广告投放、医疗试验、推荐系统，例如：想知道一个广告投放效果怎么样，唯一的方法就是放一个广告到网站上然后观察用户的点击率，每一种这样的决策都是在你有信心投放一个旧网站与你想尝试在一个新网站投放之间做探索。
来源：张泽旺 深度学习每日摘要
智造家