强化学习指南：用Python解决Multi-Armed Bandit问题

Introduction

你在镇上有一个最喜欢的咖啡馆吗？ 当你想喝咖啡时，你可能会去这个地方，因为你几乎可以肯定你会得到最好的咖啡。 但这意味着你错过了这个地方的跨城镇竞争对手所提供的咖啡。

如果你一个接一个地尝试所有咖啡的地方，品尝你生活中更糟糕的咖啡的可能性会非常高！ 但话说回来，你有可能找到一个更好的咖啡酿造者。 但是所有这些与强化学习有什么关系呢？
我很高兴你问。

我们的咖啡品尝实验中的困境源于不完整的信息。换句话说，我们需要收集足够的信息来制定最佳的整体战略，然后探索新的行动。这最终将最大限度地减少整体糟糕的体验。

多臂强盗是这种类比的简化形式。它用于表示类似的问题，找到解决它们的好策略已经帮助了很多行业。

在本文中，我们将首先了解实际上是多臂强盗问题，它是现实世界中的各种用例，然后探讨如何解决它的一些策略。然后，我将向您展示如何使用点击率优化数据集在Python中解决此挑战。

目录

• 什么是多臂强盗问题？
• 用例
• 解决方案策略
  • 没有探索（贪婪的方法）
  • Epsilon Greedy
  • 腐朽的Epsilon贪婪
  • Softmax Exploration
  • 上置信区（UCB
• 非固定强盗问题
• 从头开始​​实施广告点击优化的Python实施

什么是多武装强盗问题（MABP）？

强盗被定义为偷钱的人。单臂强盗是一种简单的*，您可以将硬币插入机器，拉动杠杆，并获得即时奖励。但为什么它被称为强盗？事实证明，所有赌场都以这样的方式配置这些*，以至于所有赌徒最终都会亏钱！

多臂匪徒是一种复杂的*，其中代替1，赌徒可以拉动几个杠杆，每个杠杆给出不同的回报。对应于每个杠杆的奖励的概率分布是不同的并且对于赌徒来说是未知的。

任务是确定要拉出哪个杠杆，以便在给定的一组试验后获得最大奖励。 这个问题陈述就像一步Markov决策过程，我在本文中讨论过。 选择的每一个手臂相当于一个动作，然后立即奖励。

伯努利MABP背景下的探索剥削

下表显示了5人伯努利强盗的样本结果，其武器标记为1,2,3,4和5：

这被称为伯努利，因为返回的奖励是1或0.在这个例子中，看起来3号臂给出最大回报，因此一个想法就是继续玩这个手臂以获得最大的回报（纯粹的利用））。

仅仅基于给定样本的知识，5可能看起来像一个坏手臂，但我们需要记住，我们只玩了一次这个手臂，也许我们应该多玩几次（探索）是 更自信。 只有这样我们才能决定使用哪种手臂（剥削）。

用例

Bandit算法正在该行业的许多研究项目中使用。 我在本节列出了一些用例。

临床试验

临床试验期间患者的健康状况与实际研究结果同样重要。 在这里，探索相当于确定最佳治疗方法，并且开发在试验期间尽可能有效地治疗患者。

Network Routing

路由是为网络中的流量选择路径的过程，例如电话网络或计算机网络（互联网）。 将信道分配给正确的用户，使得总吞吐量最大化，可以表述为MABP。

Online Advertising

广告活动的目标是最大化显示广告的收入。 每次网络用户点击优惠时，广告客户都会获得收入。 与MABP类似，在探索之间需要进行权衡，其目标是使用点击率收集广告效果的信息，以及开发，我们坚持目前为止表现最佳的广告。

Game Designing

打造热门游戏具有挑战性。 MABP可用于测试游戏/界面中的实验变化，并利用显示玩家积极体验的变化。

Solution Strategies

在本节中，我们将讨论解决多臂强盗问题的一些策略。 但在此之前，让我们熟悉一下我们将在这里使用的一些术语。

Action-Value Function

预期收益或预期奖励也可称为行动价值函数。 它由q（a）表示，并定义了每个动作在时间t的平均奖励。

假设K臂强盗的奖励概率由{P1，P2，P3 … Pk}给出。 如果在时间t选择第i个臂，则Qt（a）= Pi。

问题是，我们如何确定某个策略是否优于其他策略？ 一种直接的方法是比较在n次试验后我们获得的每种策略的总奖金或平均奖励。 如果我们已经知道对于给定强盗问题的最佳行动，那么一个有趣的方式来看待这个是遗憾的概念。

Regret

让我们说我们已经意识到了解决给定强盗问题的最佳手段。 如果我们反复拉动这个手臂，我们将得到一个最大的预期奖励，可以表示为水平线（如下图所示）：

但是在一个真正的问题陈述中，我们需要通过拉动不同的手臂进行重复试验，直到我们确定手臂在一个时间t拉动以获得最大平均回报。 由于学习而花费的时间/轮次导致的损失称为遗憾。 换句话说，即使在学习阶段，我们也希望最大化我的奖励。 后悔的命名非常恰当，因为它可以准确地量化你后悔没有选择最佳手臂的程度。
现在，如果我们遵循一种没有做足够的探索并最终利用次优手臂的方法，人们可能会对如何改变后悔感到好奇。 最初可能会有很低的遗憾，但总的来说，我们远远低于给定问题的最大可实现奖励，如下图中的绿色曲线所示。

根据探索的方式，有几种方法可以解决MABP问题。 接下来，我们将讨论一些可能的解决方案策略

没有探索（贪婪的方法）

一种天真的方法可能是计算每个时间步长的所有武器的q或动作值函数。 从那时起，选择一个给出最大q的动作。 每个动作的动作值将通过以下函数存储在每个时间步长：
然后它在每个时间步长选择最大化上述表达式的动作，由下式给出：

但是，为了在每个时间t评估这个表达式，我们需要对整个奖励历史进行计算。 我们可以通过运行总和避免这种情况。 因此，在每个时间t，可以使用奖励计算每个动作的q值：

这里的问题是这种方法只是利用，因为它总是选择相同的行动，而不用担心探索可能会带来更好奖励的其他行动。 实际找到最佳手臂需要进行一些探索，否则我们可能会永远地拉下次优臂。

Epsilon Greedy Approach

一个潜在的解决方案可能是现在，然后我们可以探索新的行动，以便我们确保我们不会错过更好的选择。 使用epsilon概率，我们将选择随机动作（探索）并选择具有最大qt（a）且概率为1-epsilon的动作。

概率为1- epsilon - 我们选择具有最大值的行动（argmaxa Qt（a））
使用概率epsilon - 我们从一组所有动作中随机选择一个动作A
例如，如果我们遇到两个动作–A和B的问题，那么epsilon贪婪算法的工作原理如下所示：

这比贪婪的方法要好得多，因为我们在这里有一个探索的元素。 但是，如果两个动作的q值之间存在非常微小的差异，那么即使这个算法也只会选择概率高于其他动作的动作。

Softmax Exploration

解决方案是使选择动作的概率与q成比例。 这可以使用softmax函数来完成，其中在每个步骤中选择操作a的概率由以下表达式给出：

Decayed Epsilon Greedy

epsilon的值对于决定epsilon greedy对给定问题的效果非常重要。 我们可以通过保持epsilon依赖于时间来避免设置此值。 例如，epsilon可以保持等于1 / log（t + 0.00001）。 随着时间的推移，随着我们对最佳动作或手臂的信心越来越强，我们将越来越少地开始探索。

随机选择动作的问题在于，即使我们知道某些手臂是坏的，在足够的时间步之后，该算法将继续以概率epsilon / n来选择。 从本质上讲，我们正在探索一个听起来不太有效的不良行为。 解决这个问题的方法可能是有利于探索具有强大潜力的武器，以获得最佳价值。

Upper Confidence Bound

上置信区（UCB）是多臂强盗问题中使用最广泛的解决方法。 该算法基于面对不确定性的乐观原则。
换句话说，我们对手臂越不确定，探索手臂就越重要。

• 在上图中显示了几次试验后3个不同臂a1，a2和a3的动作值函数的分布。该分布表明a1的动作值具有最高的方差，因此具有最大的不确定性。
• UCB说我们应该选择a1手臂并获得奖励，这使我们对其行动价值的不确定性降低。对于下一个试验/时间步，如果我们仍然非常不确定a1，我们将再次选择它，直到不确定性降低到阈值以下。

这样做的直观原因是，当以这种方式乐观地行动时，会发生以下两种情况之一：

• 乐观是合理的，我们得到积极的回报，这最终是目标
• 乐观主义没有道理。在这种情况下，我们玩一个我们认为可能会给予大量奖励的手臂，而事实上并非如此。如果这种情况经常发生，那么我们将了解这一行动的真正回报是什么，而不是将来选择它。

UCB实际上是一系列算法。在这里，我们将讨论UCB1。

UCB1涉及的步骤：

• 一次播放每个K动作，给出与每个动作相对应的平均奖励的初始值

• 对于每轮t = K：

• 让Nt（a）代表到目前为止播放动作a的次数

• 在最大化以下表达式时播放动作：

• 观察奖励并更新所选行动的平均奖励或预期收益

我们不会进入UCB的数学证明。 但是，了解与我们选择的操作相对应的表达式非常重要。 请记住，在随机探索中我们只有Q（a）才能最大化，而在这里我们有两个术语。 第一个是动作值函数，第二个是置信度。

• 每次选择a时，不确定性可能会降低：Nt（a）递增，并且，当它出现在分母中时，不确定性项会减少。
  

• 另一方面，每次选择除a之外的动作时，t增加，但是Nt（a）不增加; 因为t出现在分子中，不确定性估计值会增加。

• 使用自然对数意味着随着时间的推移，增加量会变小; 最终将选择所有操作，但是将随着时间的推移频率降低选择具有较低值估计值或已经频繁选择的操作。

• 这最终会导致最终重复选择最佳动作。

Regret Comparison

在本文给出的所有算法中，只有UCB算法提供了一种策略，其中后悔增加为log（t），而在其他算法中我们得到线性后悔与不同的斜率。

Non-Stationary Bandit problems

我们在这里做的一个重要假设是我们正在使用相同的强盗和分布，每个时间步的奖励都是相同的。 这被称为固定问题。 用另一个例子解释一下，假如每次投掷硬币时你得到的奖励为1，结果就是头部。 假设由于磨损而导致1000次硬币投掷后硬币变得有偏差，那么这将成为一个非固定的问题。

为了解决非平稳问题，更新的样本将是重要的，因此我们可以使用恒定的折扣因子alpha，我们可以像这样重写更新方程：

请注意，我们已经使用常量alpha替换了Nt（at），这确保了最近的样本具有更高的权重，并且这些最近的样本更多地决定了增量。 还有其他技术为具有非固定奖励的强盗提供不同的解决方案。 您可以在本文中阅读有关它们的更多信息。

Python Implementation from scratch for Ad CTR Optimization

如用例部分所述，MABP在在线广告领域有很多应用。

假设一家广告公司正在运行10个不同的广告，这些广告针对网页上的类似人口集合。 我们在此处有用户点击广告的结果。 每个列索引代表不同的广告。 如果广告被用户点击，则我们为1;如果不是，则为0。 原始数据集中的示例如下所示：

这是一个模拟数据集，它将广告＃5作为提供最大奖励的广告。

首先，我们将尝试随机选择技术，我们随机选择任何广告并将其显示给用户。 如果用户点击广告，我们会获得付款，如果没有，则没有任何利润。

# Random Selection

# Importing the libraries
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# Importing the dataset
dataset = pd.read_csv('Ads_Optimisation.csv')

# Implementing Random Selection
import random
N = 10000
d = 10
ads_selected = []
total_reward = 0
for n in range(0, N):
    ad = random.randrange(d)
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    total_reward = total_reward + reward

随机选择算法的总奖励为1170.由于该算法没有学习任何东西，因此不会巧妙地选择任何给出最大回报的广告。 因此，即使我们查看过去1000次试验，也无法找到最佳广告。

现在，让我们尝试使用Upper Confidence Bound算法来做同样的事情：

# Implementing UCB
import math
N = 10000
d = 10
ads_selected = []
numbers_of_selections = [0] * d
sums_of_reward = [0] * d
total_reward = 0

for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    for i in range(0, d):
        if (numbers_of_selections[i] > 0):
            average_reward = sums_of_reward[i] / numbers_of_selections[i]
            delta_i = math.sqrt(2 * math.log(n+1) / numbers_of_selections[i])
            upper_bound = average_reward + delta_i
        else:
            upper_bound = 1e400
        if upper_bound > max_upper_bound:
            max_upper_bound = upper_bound
            ad = i
    ads_selected.append(ad)
    numbers_of_selections[ad] += 1
    reward = dataset.values[n, ad]
    sums_of_reward[ad] += reward
    total_reward += reward

UCB的总流失率为2125.显然，这比随机选择和智能探索技术要好得多，这种技术可以显着改善我们解决MABP的策略。

经过1500次试验后，UCB已经开始支持Ad＃5（索引4），这恰好是最佳广告，并且可以获得给定问题的最大回报。

结束笔记

作为一个活跃的研究领域，MABP将渗透到该行业的其他各个领域。 这些算法非常简单和强大，即使是小型科技公司也越来越多地使用它们，因为它们所需的计算资源通常很少。

展望未来，还有其他基于概率模型的技术，例如Balaraman教授在这个惊人的视频中解释的Thompson Sampling。

在班加罗尔举行的DataHack Summit 2018会议上，您可以参加一个备受期待的非常有用的强化学习讲座！ 有关详细信息，请访问 https://www.analyticsvidhya.com/datahack-summit-2018/。