Data Science expert with desire to help companies advance by applying AI for process improvements.
The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.
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)
MAB 问题的目标是找到一个策略π
(从历史数据到行动的映射),以在给定轮数内最大化预期总奖励Q
MAB 的关键困境是“探索”和“利用”之间的权衡:
平衡探索和利用是强化学习和 MAB 问题的核心挑战。
为了解决这个问题,人们开发了许多算法,包括 Epsilon-Greedy、Upper Confidence Bound (UCB) 和 Thompson Sampling 策略。
作为 MAB 扩展的 Contextual Bandits 的详细回顾将在下一篇文章中介绍。
Epsilon(ε)-贪婪策略遵循简单的原则。大多数时候,量化为 (1 - ε),它会选择产生最高估计奖励的操作,从而利用最著名的选项。然而,其余时间(量化为 ε),它选择随机动作,从而探索新的可能性。该策略的独创性在于其简单性和有效性,尽管需要注意的是,它可能会在探索阶段以与回报最高的动作相同的概率选择回报较少的动作,并且 ε 的值决定了探索和利用之间的平衡。
在数学上它可以定义为:
这可以通过以下伪代码来定义:
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 策略的数学定义如下:
其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 分布是伯努利分布的共轭先验,可以轻松进行后验更新。
逻辑:
为每个老虎机分配一个 Beta 分布,参数为 α=1,β=1(均匀先验)。
每轮:
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 或 ε-贪婪更复杂,特别是对于具有大或连续动作空间或复杂奖励结构的问题。
多臂强盗 (MAB) 在各个行业和领域都有广泛的应用。以下是如何使用它们的一些示例:
从本质上讲,MAB 的用途远远超出了传统的强化学习任务。它们象征着一个有效的框架,可以在不确定的环境中增强决策过程,为各个领域的现实问题提供实用的解决方案。因此,当手头的任务涉及平衡勘探和开发时,MAB 通常会成为首选,为决策难题提供多功能、强大且适应性强的解决方案。
多臂老虎机具有有效平衡探索和利用的能力,为许多现实世界的决策问题提供了强大的解决方案。它们固有的适应性和多功能性使它们成为一种有价值的工具,不仅在强化学习领域,而且在从医疗保健到在线广告的广泛应用中。无论您是数据科学家、机器学习爱好者,还是希望增强决策过程的专业人士,理解和实施 MAB 策略都可以是一次丰富且有益的体验。