多臂老虎机问题——一个面向初学者的指南

原文towardsdatascience.com/the-multi-armed-bandit-problem-a-beginner-friendly-guide-2293ce7d8da8多臂老虎机 (MAB) 是决策中的一个经典问题其中代理必须在多个选项称为“臂”之间进行选择并在一系列试验中最大化总奖励。这个问题得名于一个涉及老虎机赌徒的隐喻单臂老虎机每个老虎机都有不同的但未知的支付概率。目标是找到最佳策略来拉动臂选择动作并在一段时间内最大化赌徒的整体奖励。MAB 问题是对利用-探索权衡的一种花哨称呼。多臂老虎机问题是一个在众多工业应用中出现的根本性问题。让我们来探讨它并检查解决它的有趣策略。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5c2a4fdb3263a4976e94bcc3205afb43.png由 Grok 生成的图像示例你刚刚来到一个新城市。你是一名间谍计划在这里停留 120 天来完成你的下一个任务。镇上有三家餐厅意大利菜、中国菜和墨西哥菜。你希望在逗留期间最大限度地提高你的用餐满意度。然而你不知道哪家餐厅最适合你。以下是三家餐厅的情况意大利餐厅平均满意度评分为 8/10中国餐厅平均满意度评分为 6/10墨西哥餐厅平均满意度评分为 9/10困境在于当你开始时并不知道这些满意度评分。你将如何策略性地在 120 顿晚餐中选择最好的餐厅探索假设你平均探索三家餐厅。换句话说你每天访问每家餐厅 40 天。预期的满意度评分将为 (408 406 40 * 9) 920。因此平均每天满意度为 7.67。这是一个最优策略吗如果你选择了墨西哥餐厅你的平均满意度将是 9探索与利用你不想探索太多。同时你也不想随机选择一家餐厅并一直光顾它。你需要一种策略该策略侧重于探索然后是利用——重新访问始终提供最高满意度的餐厅。这导致了探索-利用困境多臂老虎机算法帮助你平衡两者。ε-Greedyε-Greedy算法是一种管理探索和利用的简单方法。以概率 ε你通过随机选择一家餐厅来尝试来探索。以概率 1-ε你通过选择迄今为止提供最佳满意度的餐厅来进行利用。随着时间的推移这种策略帮助你发现最好的餐厅同时偶尔尝试新的选项。以下 Python 代码模拟了 ε-Greedy 算法。真实的平均满意度分数遵循均值为 8、6 和 9标准差为 1、2 和 1.5 的正态分布。importnumpyasnpclassEpsilonGreedy:def__init__(self,n_restaurants,epsilon):self.n_restaurantsn_restaurants self.epsilonepsilon self.visitsnp.zeros(n_restaurants)self.satisfactionnp.zeros(n_restaurants)defchoose_restaurant(self):ifnp.random.random()self.epsilon:returnnp.random.choice(self.n_restaurants)# Exploreelse:returnnp.argmax(self.satisfaction/(self.visits1e-5))# Exploitdefupdate(self,restaurant,score):self.visits[restaurant]1self.satisfaction[restaurant]score n_restaurants3epsilon0.1n_days120true_avg_satisfactionnp.array([8,6,9])true_stddev_satisfactionnp.array([1,2,1.5])total_satisfaction_arr[]foriinrange(50):# Run the simulation 50 timesepsilon_greedy_restaurantEpsilonGreedy(n_restaurants,epsilon)total_satisfaction0for_inrange(n_days):restaurantepsilon_greedy_restaurant.choose_restaurant()scorenp.random.normal(loctrue_avg_satisfaction[restaurant],scaletrue_stddev_satisfaction[restaurant])epsilon_greedy_restaurant.update(restaurant,score)total_satisfactionscoreprint(Total Satisfaction (Epsilon-Greedy):,total_satisfaction)total_satisfaction_arr.append(total_satisfaction)# Calculate average satisfactionnp.mean(total_satisfaction_arr)/n_days,np.std(total_satisfaction_arr)/n_days我用 ε0.1 模拟了该算法 50 次。我观察到平均满意度分数为 8.49±0.35。可以调整 ε 参数。上置信界上置信界算法也试图平衡探索和利用。它考虑了迄今为止记录的平均满意度分数以及餐厅满意度的不确定性。未被访问足够的餐厅会被更多地探索以减少不确定性但表现一致的餐厅仍然受到青睐。一旦它足够自信UCB 算法最终会确定最令人满意的餐厅。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/6b3e00787eace03a189a3e15fa62871f.png上置信界。图由作者提供UCB 涉及最大化上述方程中的括号内的项。上述置信界方程是从Hoeffding 不等式推导出来的。Hoeffding 不等式提供了一个理论保证即餐厅的真实满意度位于估计满意度的置信区间内。第一个项是观察到的平均满意度分数第二个项是置信区间。请注意分母n_i是餐厅被访问的次数。如果n_i较小第二个项较大。因此在利用满意度最高的餐厅之前它给了数据较少的餐厅一个机会。你访问餐厅的频率越低不确定性越高算法会给这个餐厅更高的置信分数以鼓励探索。以下 Python 代码模拟了与 ε-Greedy 算法中相同的满意度分数分布的 UCB 算法。importnumpyasnpclassUCB:def__init__(self,n_restaurants):self.n_restaurantsn_restaurants self.visitsnp.zeros(n_restaurants)self.satisfactionnp.zeros(n_restaurants)self.total_trials0defchoose_restaurant(self):ifself.total_trialsself.n_restaurants:returnself.total_trials# First, visit each restaurant at least onceucb_valuesnp.zeros(self.n_restaurants)forrestaurantinrange(self.n_restaurants):avg_scoreself.satisfaction[restaurant]/(self.visits[restaurant]1e-5)confidence_boundnp.sqrt(2*np.log(self.total_trials1)/(self.visits[restaurant]1e-5))ucb_values[restaurant]avg_scoreconfidence_boundreturnnp.argmax(ucb_values)defupdate(self,restaurant,score):self.visits[restaurant]1self.satisfaction[restaurant]score self.total_trials1n_restaurants3n_days120true_avg_satisfactionnp.array([8,6,9])true_stddev_satisfactionnp.array([1,2,1.5])total_satisfaction_arr[]foriinrange(50):# Run the simulation 50 timesucb_restaurantUCB(n_restaurants)total_satisfaction0for_inrange(n_days):restaurantucb_restaurant.choose_restaurant()scorenp.random.normal(loctrue_avg_satisfaction[restaurant],scaletrue_stddev_satisfaction[restaurant])ucb_restaurant.update(restaurant,score)total_satisfactionscoreprint(Total Satisfaction (UCB):,total_satisfaction)total_satisfaction_arr.append(total_satisfaction)# Calculate average satisfactionnp.mean(total_satisfaction_arr)/n_days,np.std(total_satisfaction_arr)/n_days我模拟了该算法 50 次。我观察到平均满意度分数为 8.84±0.19。Thompson SamplingThompson Sampling 是另一种广泛用于解决多臂老虎机MAB问题的算法。与其他使用固定规则进行探索和利用的方法如 ε-Greedy 或 UCB不同Thompson Sampling 使用概率方法来平衡探索和利用。Thompson Sampling 的核心思想是在可能的满意度分数上维持一个概率分布通常是 Beta 分布。每家餐厅都被分配一个先验概率分布表示你期望有多满意。最初分布较宽反映了不确定性。在每次晚餐之前你从每家餐厅的分布中采样一个潜在的满意度分数并选择采样分数最高的餐厅。晚餐后你根据实际体验到的满意度更新餐厅的概率分布。更新后的分布成为下一次晚餐的先验分布。以下 Python 代码模拟了与ε-Greedy 算法中展示的相同满意度的 Thompson Sampling 算法。importnumpyasnpclassThompsonSampling:def__init__(self,n_restaurants):self.n_restaurantsn_restaurants self.visitsnp.zeros(n_restaurants)self.satisfactionnp.zeros(n_restaurants)self.alphanp.ones(n_restaurants)# Beta distribution parametersself.betanp.ones(n_restaurants)defchoose_restaurant(self):sampled_valuesnp.random.beta(self.alpha,self.beta)returnnp.argmax(sampled_values)defupdate(self,restaurant,score):self.visits[restaurant]1self.satisfaction[restaurant]score# Update the beta distribution based on the satisfaction scoreifscorenp.mean(self.satisfaction/(self.visits1e-5)):self.alpha[restaurant]1# successelse:self.beta[restaurant]1# failuren_restaurants3n_days120true_avg_satisfactionnp.array([8,6,9])true_stddev_satisfactionnp.array([1,2,1.5])total_satisfaction_arr[]foriinrange(50):# Run the simulation 50 timesthompson_sampling_restaurantThompsonSampling(n_restaurants)total_satisfaction0for_inrange(n_days):restaurantthompson_sampling_restaurant.choose_restaurant()scorenp.random.normal(loctrue_avg_satisfaction[restaurant],scaletrue_stddev_satisfaction[restaurant])thompson_sampling_restaurant.update(restaurant,score)total_satisfactionscoreprint(Total Satisfaction (Thompson Sampling):,total_satisfaction)total_satisfaction_arr.append(total_satisfaction)# Calculate average satisfactionnp.mean(total_satisfaction_arr)/n_days,np.std(total_satisfaction_arr)/n_days我模拟了该算法 50 次。我观察到平均满意度评分为 8.5±0.3。所有三种算法的性能都优于基本策略的等概率探索。请注意这只是一个简单示例仅涉及三家餐厅。在实际情况下您可能在一个城市中有数百家餐厅。应用在线广告平台和电子商务应用– 多臂老虎机MAB算法可以通过选择显示哪些广告来优化网站广告位置以最大化点击率CTR或转化率。打车和外卖应用– MAB 可以帮助实时优化司机分配和路线规划以最大化效率和最小化等待时间。我希望您觉得我的文章有启发性。感谢阅读