paint-brush
多臂老虎机:适合您任务的最佳强化学习解决方案经过@teenl0ve
2,261 讀數
2,261 讀數

多臂老虎机:适合您任务的最佳强化学习解决方案

经过 Valentine Shkulov
Valentine Shkulov HackerNoon profile picture

Valentine Shkulov

@teenl0ve

Data Science expert with desire to help companies advance by...

9 分钟 read2023/07/20
Read on Terminal Reader
Read this story in a terminal
Print this story

太長; 讀書

本文探讨了多臂老虎机 (MAB),这是一种用于平衡探索(尝试新选项)和利用(使用当前最佳选项)的强化学习技术。它介绍了各种 MAB 算法,例如 ε-greedy、UCB 和 Thompson Sampling。 ε-贪婪方法大多数时候都会利用最知名的选项,但也会探索新的选项。另一方面,UCB 考虑估计的奖励和相关的不确定性。汤普森采样是一种贝叶斯方法,使用概率动作选择。 MAB 在广告、医疗保健、网络优化、动态定价、网络路由和机器学习方面有着广泛的应用。它们探索和利用的平衡使它们成为不确定环境中决策的理想选择。
featured image - 多臂老虎机:适合您任务的最佳强化学习解决方案
Valentine Shkulov HackerNoon profile picture
Valentine Shkulov

Valentine Shkulov

@teenl0ve

Data Science expert with desire to help companies advance by applying AI for process improvements.

0-item
1-item

STORY’S CREDIBILITY

Code License

Code License

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Guide

Guide

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

多臂老虎机 (MAB) 构成了强化学习领域的基石,提供了强大的机制来协商需要在探索和利用之间实现最佳平衡的场景。探索是指尝试新的选择,而利用则意味着坚持当前的最佳选择。在这种情况下,MAB 因其智能学习机制而常常被证明是一个不错的选择。


首先,让我们阐明 MAB 背后的概念。想象一下一个赌徒被一排老虎机包围,每台老虎机都被称为“独臂强盗”。这里要做的关键决定包括确定玩哪些机器、玩的顺序和玩的频率。问题是每台机器都会提供不同的、不确定的奖励。最终目标是在一系列游戏中获得最高的累积奖励。

什么是多臂强盗?

“多臂强盗”这个名字来源于一个思想实验,涉及到一排老虎机上的赌徒(通常被称为“单臂强盗”)。赌徒需要决定玩哪台机器、每台机器玩多少次以及玩什么顺序,以最大化他们的总奖励。


在更正式的定义中,MAB 问题是一个元组 (A, R)

image

MAB 问题的目标是找到一个策略π (从历史数据到行动的映射),以在给定轮数内最大化预期总奖励Q


MAB 的关键困境是“探索”和“利用”之间的权衡:

  1. 探索包括尝试不同的方法来更多地了解它们可能产生的回报。这可能涉及拉次优的手臂,但它有助于收集有关系统的信息。
  2. 开发涉及根据迄今为止收集到的信息,拉动智能体当前认为具有最高预期奖励的手臂。


平衡探索和利用是强化学习和 MAB 问题的核心挑战。


为了解决这个问题,人们开发了许多算法,包括 Epsilon-Greedy、Upper Confidence Bound (UCB) 和 Thompson Sampling 策略。


作为 MAB 扩展的 Contextual Bandits 的详细回顾将在下一篇文章中介绍。

Epsilon(ε)-贪婪

Epsilon(ε)-贪婪策略遵循简单的原则。大多数时候,量化为 (1 - ε),它会选择产生最高估计奖励的操作,从而利用最著名的选项。然而,其余时间(量化为 ε),它选择随机动作,从而探索新的可能性。该策略的独创性在于其简单性和有效性,尽管需要注意的是,它可能会在探索阶段以与回报最高的动作相同的概率选择回报较少的动作,并且 ε 的值决定了探索和利用之间的平衡。


在数学上它可以定义为:

image

这可以通过以下伪代码来定义:


 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

Epsilon-Greedy 策略的 Pythonic 实现相当简单:

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

ε-贪婪算法的优点是简单,并且保证即使在执行许多步骤之后它也会继续探索(一点)。然而,与 UCB 或 Thompson Sampling 不同,它在探索时并没有考虑每个动作的已知程度。

联合银行

相反,UCB 策略在决定行动时会考虑估计奖励和相关的不确定性或方差。它表现出对具有高度不确定性的行动的偏好,寻求减少不确定性并确保更富有成效的探索阶段。 UCB 策略的数学定义如下:

image

其Python实现如下:

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

UCB 中的探索和利用之间的平衡来自于其公式:一个动作的估计值加上一个随着时间的推移而减少(随着了解该动作的更多信息)但随着该动作的不确定性而增加的项。因此,该算法倾向于探索具有高不确定性和高潜在奖励的武器。

汤普森采样

汤普森采样是一种受贝叶斯启发的算法,用于解决多臂老虎机问题。它将先验分布分配给每个强盗(或每个动作)的奖励概率,然后在观察到奖励时更新这些先验。根据最佳动作的后验分布,动作选择是概率性的。


在 Beta-Bernoulli 框架中,我们将每个老虎机的奖励分布视为伯努利分布(即二进制奖励 0 或 1)。然后我们在获得奖励的概率之前分配一个贝塔值。 Beta 分布是伯努利分布的共轭先验,可以轻松进行后验更新。

image

逻辑:

  1. 为每个老虎机分配一个 Beta 分布,参数为 α=1,β=1(均匀先验)。

  2. 每轮:

    1. 从每个 bandit 的当前 Beta 分布中抽取一个随机数。
    2. 选择采样数最高的强盗并拉出该强盗。
    3. 观察被拉走的强盗的奖励。如果成功(1),则将强盗的 α 加 1;如果失败(0),则将强盗的 β 增加 1。
    4. 重复步骤 2 和 3。
 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

因此,汤普森采样“探索”不确定的操作(值分布分散的操作)并“利用”它认为可能具有高价值的操作(分布偏向高值的操作)。


随着时间的推移,随着对每个动作的了解越来越多,分布变得更加峰值,算法选择的动作往往会收敛于具有最高期望值的动作。

汤普森采样中的探索/利用平衡自然来自于分布的形状。这种方法非常有效,但实现起来可能比 UCB 或 ε-贪婪更复杂,特别是对于具有大或连续动作空间或复杂奖励结构的问题。

为什么多臂老虎机是最适合您任务的强化学习?

  1. 简单性:MAB 算法比成熟的 RL 算法更简单且计算效率更高,后者需要维护和更新潜在的大型状态动作值表或逼近器。
  2. 探索和利用的平衡:MAB 算法提供了强大的方法来管理尝试新操作和坚持已知的良好操作之间的权衡。
  3. 实时适应性:MAB算法可以实时适应动作奖励分布的变化。
  4. 轻松集成:MAB 的简单性和高效性允许轻松集成到现有系统中,以最小的干扰提供直接的好处。
  5. 广泛的适用性:MAB已成功应用于各个领域,包括广告(选择要展示的广告以最大化点击率)、医疗保健(个性化治疗策略)和网页优化(A/B测试)。

MAB 的应用

多臂强盗 (MAB) 在各个行业和领域都有广泛的应用。以下是如何使用它们的一些示例:


  1. 在线广告:MAB 可用于根据用户的交互动态调整要向用户显示的广告选择。随着时间的推移,这有助于最大限度地提高点击率或转化率。
  2. 临床试验:在医学研究中,MAB 算法可用于动态分配患者接受不同的治疗。这保证了更多的患者得到最有效的治疗,从而减少遗憾,即因不总是选择最好的治疗而产生的损失。
  3. 新闻文章推荐:新闻网站可以使用 MAB 个性化向每个用户显示的文章。 MAB 算法可以随着时间的推移了解每个用户感兴趣的文章类型,并相应地调整推荐。
  4. 动态定价:电子商务平台或航空公司可以使用 MAB 算法实时优化其定价策略,根据客户行为和市场动态最大化收入。
  5. 网络路由:在计算机网络中,MAB 算法可用于管理拥塞并优化数据包的路由。每条路由都可以视为一条手臂,算法可以动态选择路由以最大限度地减少数据包丢失或延迟。
  6. 机器学习超参数调整:MAB 还可用于优化机器学习模型中超参数的选择。每组超参数都可以视为一个臂,算法可以迭代地细化选择以找到最佳模型配置。


从本质上讲,MAB 的用途远远超出了传统的强化学习任务。它们象征着一个有效的框架,可以在不确定的环境中增强决策过程,为各个领域的现实问题提供实用的解决方案。因此,当手头的任务涉及平衡勘探和开发时,MAB 通常会成为首选,为决策难题提供多功能、强大且适应性强的解决方案。

结论

多臂老虎机具有有效平衡探索和利用的能力,为许多现实世界的决策问题提供了强大的解决方案。它们固有的适应性和多功能性使它们成为一种有价值的工具,不仅在强化学习领域,而且在从医疗保健到在线广告的广泛应用中。无论您是数据科学家、机器学习爱好者,还是希望增强决策过程的专业人士,理解和实施 MAB 策略都可以是一次丰富且有益的体验。

L O A D I N G
. . . comments & more!

About Author

Valentine Shkulov HackerNoon profile picture
Valentine Shkulov@teenl0ve
Data Science expert with desire to help companies advance by applying AI for process improvements.

標籤

这篇文章刊登在...

Read on Terminal Reader
Read this story in a terminal
 Terminal
Read this story w/o Javascript
Read this story w/o Javascript
 Lite