各行各业网站建设,seo关键词排名优化手机,门头沟做网站公司,网站建设和管理工作强化学习 强化学习#xff08;Reinforcement Learning#xff0c;RL#xff09;是一种机器学习方法#xff0c;强化学习的基础框架是马尔可夫决策过程#xff0c;它允许智能体#xff08;Agent#xff09;能够在与环境#xff08;Environment#xff09;的交互中通过试…强化学习 强化学习Reinforcement LearningRL是一种机器学习方法强化学习的基础框架是马尔可夫决策过程它允许智能体Agent能够在与环境Environment的交互中通过试错来学习最优策略。 智能体在环境中执行行动Action并根据行动的结果接收反馈即奖励Reward。这些奖励信号指导智能体调整其策略以最大化长期累积奖励。 强化学习的核心是价值函数Value Function它估计了从给定状态出发并遵循特定策略所能获得的期望累积奖励。通过不断更新价值函数智能体学会区分哪些状态和行动更有可能导致高奖励从而做出更好的决策。 近年来强化学习在多个领域取得了显著进展尤其是在游戏、机器人、推荐系统和自然语言处理等领域。例如AlphaGo利用深度学习和强化学习技术在围棋游戏中战胜了世界冠军展示了强化学习在解决复杂问题上的巨大潜力。 1-参考网址
强化学习K臂老虎机问题 2-核心知识点 1-K臂老虎机问题的生活案例 2-K臂老虎机问题的计算思路-使用新旧估计值推断将原本连加的复杂计算变为简单的小学运算 3-什么是平稳问题/非平稳问题-老虎机是一种最简化的模型计算的概率值都是固定的(先不考虑非平稳问题每次的输出都是一个我们琢磨不透的一个变化的分布) 针对【第1个老虎机】每摇动5次就会中奖一次(假定奖励函数都是为1) V10 V20 V30 V40 V51 Q11/5 3-最大收益案例-由于【算力有限/尝试次数】有限引出【探索/利用困境】 4-探索/利用困境的求解方案1-温和贪婪-不同的ε对结果影响较大 5-探索/利用困境的优化方案-【OIV积极初始值】【UCB动作选择】【GB梯度赌博算法】 6-探索/利用困境的优化方案1-OIV积极初始值-核心思想搞一个特别大的理想预期值(这个值可能永远都不能达到)于是在这个较高的心里预期下就可以用于用于探索完成所有的餐厅试吃找到全局最优解 7-探索/利用困境的优化方案2-UCB动作选择-核心思想在动作选择时综合考虑动作的估计价值和其不确定性即该动作被探索的次数即让选择次数少的餐厅Qi值更大一点【心里预期更高认为这家店可能还有好活】这样留够足够的好奇心再次进行探索 8-探索/利用困境的优化方案3-GB梯度赌博算法-核心思想上面的算法都是计算每家餐厅的价值收益值每家餐厅之间的价值收益不互相影响计算完每家的价值估计之后再进行动作选择GB梯度赌博算法-抛弃价值估计转向概率优化。直接把【每家餐厅的收益】结合【动作偏好函数】进行计算计算下一步的决策动作 9-【OIV积极初始值】VS【UCB动作选择】-UCB 动作选择和积极初始值这两种解决方案并非互斥它们也不是简单的演进关系而是在解决探索 - 利用困境上相互补充、各有侧重 10-OIV积极初始值-为什么会出现一个尖?-前面的所有过程都是在进行探索【波动很大,中间可能遇到最美味的餐厅,这个尖就是那个最佳餐厅】一旦完成所有的探索后续模型就会大概的了解到所有餐厅的大概情况Qk后序就会慢慢的收敛-所以在完成所有的探索之前曲线会波动很大后续就会慢慢收敛 3-相关截图
1-K臂老虎机题的简化计算 2-最大收益案例 由于【算力有限/尝试次数】有限引出【探索/利用困境】 3-探索/利用困境 4-探索/利用求解方案1-温和贪婪 【温和贪婪】对比【贪婪】前面的计算过程都相同但是在后续进行使用的时候【贪婪】是只选择第i个选项而【温和贪婪】还会对其他选项进行尝试 1-先拟定一个P(进行探索的概率)则1-P是进行利用的概率 2-然后按照哦这个拟定的概率P进行实验-计算出该探索概率下的最大收益 5-探索/利用求解方案1-温和贪婪针对不同ε的绘图 6-探索/利用优化方案1-积极的初始值方法OIV 积极的初始值方法OIVOptimistic Initial Values核心思想搞一个特别大的理想预期值(这个值可能永远都不能达到)于是在这个较高的心里预期下就可以用于用于探索完成所有的餐厅试吃找到全局最优解 7-探索/利用优化方案2-UCB动作选择方法 在动作选择时综合考虑动作的估计价值和其不确定性即该动作被探索的次数即让选择次数少的餐厅Qi值更大一点【心里预期更高认为这家店可能还有好活】这样留够足够的好奇心再次进行探索 8-探索/利用优化方案3-GB梯度赌博算法 4-知识整理
1-K臂老虎机问题的生活案例1
以下以在美食广场选择餐厅就餐为例详细说明强化学习中探索/利用求解方案里贪婪算法的运用过程。
1-场景设定
你身处一个大型美食广场这里有 10 家不同的餐厅分别提供不同类型的美食比如中餐、西餐、快餐等。你每周都会来这个美食广场吃一次饭目的是找到让自己最满意即获得最高享受和满足感的餐厅。
2-算法初始化
在最初阶段你对这 10 家餐厅一无所知所以给每家餐厅的初始评分即估计价值 Q Q Q 都设为 0。每次选择餐厅就餐后你会根据实际体验给该餐厅一个评分范围是 0 - 10 分。同时你设定了一个探索概率 ϵ \epsilon ϵ 假设初始值为 0.2。
3-探索与利用过程
第 1 周
决策依据由于刚开始所有餐厅的评分都是 0按照贪婪算法的逻辑如果单纯依据评分选择任意一家餐厅的价值都是一样的。但因为有 0.2 的探索概率所以这次选择餐厅是完全随机的。假设你随机选择了餐厅 A。体验与更新就餐后你根据体验给餐厅 A 打了 7 分此时餐厅 A 的评分更新为 7 分其他餐厅评分仍为 0 分。
第 2 周
决策依据现在要决定去哪家餐厅。这时候会根据探索概率 ϵ \epsilon ϵ 来做决策。通过随机数生成器生成一个 0 - 1 之间的随机数如果这个随机数小于 0.2就进行探索随机选择一家餐厅如果大于 0.2就进行利用选择当前评分最高的餐厅。假设生成的随机数是 0.3大于 0.2所以你选择利用去了评分最高的餐厅 A。体验与更新这次在餐厅 A 的体验一般你给它打了 4 分。然后更新餐厅 A 的评分采用加权平均的方式假设之前去了 1 次这次是第 2 次新评分 Q ( A ) 7 × 1 4 × 1 1 1 5.5 Q(A)\frac{7\times1 4\times1}{1 1}5.5 Q(A)117×14×15.5 分其他餐厅评分依旧为 0 分。
第 3 周
决策依据再次生成随机数假设这次生成的随机数是 0.1小于 0.2所以进行探索。你随机选择了餐厅 B。体验与更新在餐厅 B 用餐后你觉得非常满意给它打了 9 分。此时餐厅 B 的评分更新为 9 分餐厅 A 评分是 5.5 分其他餐厅评分还是 0 分。
第 4 周
决策依据又到了选择餐厅的时候生成随机数假设为 0.8大于 0.2进行利用所以你选择了当前评分最高的餐厅 B。体验与更新这次在餐厅 B 的体验依然不错你给它打了 8 分。更新餐厅 B 的评分 Q ( B ) 9 × 1 8 × 1 1 1 8.5 Q(B)\frac{9\times1 8\times1}{1 1}8.5 Q(B)119×18×18.5 分餐厅 A 评分 5.5 分其他餐厅评分 0 分。
4-探索概率调整
随着时间推移你对这些餐厅的了解越来越多。为了更倾向于选择已经发现的优质餐厅你逐渐降低探索概率 ϵ \epsilon ϵ 。比如到第 10 周时把 ϵ \epsilon ϵ 降低到 0.1。这样一来大部分情况下你会选择评分最高的餐厅但仍有一定机会去尝试其他餐厅以应对餐厅质量可能发生的变化。
5-长期结果
经过一段时间的尝试你可能会发现某几家餐厅的评分一直比较高比如餐厅 B 和餐厅 C。之后大部分时间你会选择这两家评分高的餐厅就餐利用但偶尔也会因为探索概率的存在去尝试其他餐厅看看是否有更好的选择。
通过这个案例可以看到贪婪算法结合探索概率帮助你在寻找最满意餐厅的过程中平衡了对已知优质餐厅的利用和对未知餐厅的探索。 2-K臂老虎机问题的生活案例2 好的我们来用一个非常贴近生活的真实案例—— “上班族小王每天选择午餐餐厅的决策过程” ——来详细说明 ε-贪婪算法在探索与利用中的应用。
1-背景设定
智能体 (Agent) 小王环境 (Environment) 公司附近午餐餐厅的集合比如餐厅A、B、C、D状态 (State) 每天午餐时间为了简化我们假设每天状态相同只关注动作选择动作 (Action) 选择去哪家餐厅吃饭A、B、C、D奖励 (Reward) 小王的用餐满意度。我们可以量化它比如 非常满意 3分 (好吃、快、便宜)一般满意 1分 (能吃但没亮点)不满意 -1分 (难吃、等太久、太贵)极度不满 -3分 (食物中毒、天价账单) 目标 长期最大化午餐满意度总奖励。挑战 小王最初不知道每家餐厅的真实质量平均奖励。他需要尝试探索不同的餐厅来了解它们同时也要尽量选择已知好的餐厅利用来保证大部分时间的满意度。
小王采用 ε-贪婪策略
小王设定一个探索概率 ε比如 ε 0.3。小王维护一个Q值表 (Q-Table)记录他对每家餐厅当前估计的平均满意度。初始时所有Q值都为0或一个中性值表示一无所知。 餐厅Q值 (估计平均满意度)A0B0C0D0
2-背景设定决策过程模拟 (ε 0.3) Day 1: 决策 生成一个随机数0-1之间。0.5 ε (0.3) ➔ 利用 (Exploit)。但所有Q值都是0没有“已知最好”。这时通常默认随机选一个这也算一种初始探索。假设小王随机选了餐厅A。 体验 排队很长味道一般。小王打分1。 更新Q值 更新餐厅A的Q值。假设学习率 α 0.5 (表示新经验的重要性)。 新Q(A) 老Q(A) α * (奖励 - 老Q(A)) 0 0.5 * (1 - 0) 0.5 Q表更新后 餐厅Q值A0.5B0.0C0.0 | D | 0.0 | Day 2: 决策 随机数 0.2 ε (0.3) ➔ 探索 (Explore)小王随机选择了餐厅C之前没去过。 体验 出乎意料的好吃速度快价格实惠。小王打分3。 更新Q值 新Q(C) 0 0.5 * (3 - 0) 1.5 Q表更新后 餐厅Q值A0.5B0.0C1.5 | D | 0.0 | Day 3: 决策 随机数 0.7 ε (0.3) ➔ 利用 (Exploit)选择当前Q值最高的餐厅 ➔ 餐厅C (Q1.5)。 体验 依然不错但感觉没昨天惊艳了可能厨师发挥小波动。小王打分2。 更新Q值 新Q(C) 1.5 0.5 * (2 - 1.5) 1.5 0.5 * 0.5 1.5 0.25 1.75 Q表更新后 餐厅Q值A0.5B0.0C1.75 | D | 0.0 | Day 4: 决策 随机数 0.4 ε (0.3) ➔ 利用 (Exploit)选择当前Q值最高的餐厅 ➔ 餐厅C (Q1.75)。 体验 人太多等位太久影响了心情。食物尚可。小王打分1。 更新Q值 新Q(C) 1.75 0.5 * (1 - 1.75) 1.75 0.5 * (-0.75) 1.75 - 0.375 1.375 Q表更新后 餐厅Q值A0.5B0.0C1.375 | D | 0.0 | Day 5: 决策 随机数 0.1 ε (0.3) ➔ 探索 (Explore)小王随机选择了餐厅B。 体验 非常糟糕又贵又难吃还等了很久。小王打分-3。 更新Q值 新Q(B) 0 0.5 * (-3 - 0) -1.5 Q表更新后 餐厅Q值A0.5B-1.5C1.375 | D | 0.0 | Day 6: 决策 随机数 0.8 ε (0.3) ➔ 利用 (Exploit)选择当前Q值最高的餐厅 ➔ 餐厅C (Q1.375)。 体验 恢复正常水平好吃快捷。小王打分3。 更新Q值 新Q(C) 1.375 0.5 * (3 - 1.375) 1.375 0.5 * 1.625 1.375 0.8125 2.1875 Q表更新后 餐厅Q值A0.5B-1.5C2.1875D0.0
3-过程分析 (固定 ε0.3)
利用 (Exploit - 70% 概率) 大部分时间Day 3, 4, 6小王会选择当前他认为最好的餐厅C因为C的Q值一直领先。这保证了他大部分时间能获得相对不错的满意度2, 1, 3尤其是在C表现稳定后。探索 (Explore - 30% 概率) 小部分时间Day 2, 5小王会随机尝试其他餐厅。 成功探索 (Day 2) 发现了非常棒的餐厅C这是策略的巨大成功找到了最优选项。C的Q值被大幅提升之后成为主要利用对象。失败探索 (Day 5) 踩雷了餐厅B。虽然这次体验极差-3但获得了宝贵信息知道了B是雷区以后可以避免。B的Q值被大幅降低。 信息获取与更新 无论探索还是利用每次就餐后小王都会根据实际满意度奖励更新他对该餐厅的评估Q值。这使他对餐厅质量的估计越来越准确A一般B很差C很好D未知。未探索选项 餐厅D到目前为止还没有被探索过纯属随机没选到。只要ε0在未来的日子里小王仍有小概率去尝试D从而可能发现新的好餐厅或者又一个雷。
4-ε 衰减的引入 (优化策略)
小王很快发现了一个问题随着时间推移他已经基本确定了C是最好的Q值最高A一般B很差。但按照固定ε0.3的策略他仍然有30%的概率去随机尝试A、B、D。尝试A或D可能还行A已知一般D未知但尝试已知很差的B显然是浪费钱和心情而且他对C已经很有信心了不需要那么频繁地探索了。
解决方案ε 衰减
初始设定 小王设定初始 ε₀ 0.9早期极度需要探索衰减因子 γ 0.95每次决策后ε乘以0.95下限 ε_min 0.1。衰减过程 Day 1: ε 0.9 (高探索)Day 2: ε 0.9 * 0.95 0.855Day 3: ε 0.855 * 0.95 ≈ 0.812Day 4: ε ≈ 0.812 * 0.95 ≈ 0.771Day 5: ε ≈ 0.771 * 0.95 ≈ 0.732Day 6: ε ≈ 0.732 * 0.95 ≈ 0.695… (继续衰减)假设到 Day 30ε ≈ 0.9 * (0.95)^29 ≈ 0.1 (达到下限之后稳定在0.1)
ε 衰减带来的好处
早期 (高 ε) 前几周小王疯狂探索各种餐厅包括D。这让他快速发现了潜在的宝藏餐厅如C和雷区如B并初步建立起对A的评价。信息收集效率高。中期 (ε下降) 随着Q值逐渐稳定C最好A次之B最差D未知但尝试过几次可能一般小王探索的频率逐渐降低。他更多地去C享受美食利用只在偶尔ε变小时去尝试一下D唯一未充分了解的或者再验证下A。避免了频繁踩雷B。后期 (低 ε) 几个月后ε稳定在0.1。小王绝大部分时间 (90%) 都在最好的餐厅C吃饭最大化利用已知最优解。极少时间 (10%) 会随机尝试一下其他餐厅主要是为了防止餐厅C质量突然下滑或者新开了一家更好的餐厅E——虽然这个简单模型没考虑环境变化。几乎完全避免了去已知很差的B。
5-总结
通过小王选餐厅的案例我们清晰地看到了 ε-贪婪算法如何工作
核心循环 在每个决策点每天基于当前探索概率ε和Q值表选择动作去哪吃- 获得奖励用餐体验- 更新Q值调整对该餐厅的评价。探索 (ε概率) 随机尝试旨在发现未知信息新好餐厅或确认雷区。案例中发现C成功踩雷B失败但有价值尚未尝试D未知。利用 (1-ε概率) 选择当前已知最好的选项旨在获得稳定收益。案例中大部分时间选择高Q值的C。ε衰减 (优化关键) 模拟了人的学习过程——早期广撒网高探索后期专注于已知最好的高利用。解决了固定ε导致的后期过度探索问题比如一直有30%概率去吃已知很差的B。Q值学习 不断用实际体验修正对每个动作餐厅价值的估计是决策的基础。
ε-贪婪策略尤其是带衰减的提供了一种简单有效的方法在信息不完全的环境下平衡尝试新事物获取信息探索 和选择已知最优解获取收益利用 的矛盾最终目标是最大化长期收益午餐总满意度。 3-计算的结果和ε的取值有没有关系如何和ε的取值有关那如何进行算法优化
1-4o-Mini回答
在上述美食广场选择餐厅的案例所涉及的强化学习探索/利用问题中计算结果与 ϵ \epsilon ϵ 的取值密切相关以下为你详细分析关系以及对应的算法优化方法。
计算结果与 ϵ \epsilon ϵ 取值的关系
高 ϵ \epsilon ϵ 值接近 1
探索性强当 ϵ \epsilon ϵ 取值接近 1 时意味着大部分情况下会进行随机探索。在美食广场的例子中你会频繁地随机选择不同的餐厅就餐。这样做能快速收集到大量关于各个餐厅的信息但可能导致你不断尝试新餐厅而没有充分利用已经发现的优质餐厅。结果影响前期可能会得到各种不同的体验评分各个餐厅的评分更新较为频繁。但由于很少选择当前评分高的餐厅可能会在一段时间内无法稳定地获得较高的满意度。例如你可能多次尝试到体验较差的餐厅整体满意度波动较大。
低 ϵ \epsilon ϵ 值接近 0
利用性强如果 ϵ \epsilon ϵ 取值接近 0那么绝大部分时间都会选择当前评分最高的餐厅。在美食广场场景下你会很快固定在某一家或几家评分高的餐厅就餐。结果影响前期如果过早地确定了“最佳”餐厅可能会错过其他真正更优质的餐厅陷入局部最优。因为缺乏对其他餐厅的探索当这家“最佳”餐厅的质量发生变化如更换厨师导致菜品质量下降时你可能无法及时发现更好的替代餐厅从而导致长期满意度逐渐降低。
算法优化方法
动态调整 ϵ \epsilon ϵ 值
衰减策略随着学习过程的推进逐渐降低 ϵ \epsilon ϵ 值。在美食广场的例子中刚开始你对所有餐厅都不了解需要较多的探索所以可以将 ϵ \epsilon ϵ 设为较高的值如 0.8。随着尝试的餐厅数量增多对各餐厅的了解逐渐加深就可以逐渐降低 ϵ \epsilon ϵ 值。例如每尝试 10 次后将 ϵ \epsilon ϵ 降低 0.1直到 ϵ \epsilon ϵ 达到一个较低的稳定值如 0.1。这样既能保证前期有足够的探索又能在后期充分利用已经发现的优质餐厅。基于时间或经验的调整除了简单的线性衰减还可以根据具体的学习进度或经验进行更复杂的调整。比如当你发现某个餐厅的评分明显高于其他餐厅且已经尝试了一定次数后就可以快速降低 ϵ \epsilon ϵ 值更倾向于利用这个优质餐厅。
基于置信区间的选择
UCB 算法UCBUpper Confidence Bound算法是一种改进的贪婪算法它不仅考虑动作的估计价值还考虑了估计的不确定性。在美食广场的例子中对于每家餐厅除了记录其平均评分还会记录尝试的次数。UCB 算法会选择具有最高置信上界的餐厅置信上界综合考虑了平均评分和尝试次数。尝试次数少的餐厅其置信上界会相对较高这样就会促使算法在前期对更多餐厅进行探索同时在后期逐渐倾向于选择评分高且尝试次数多的餐厅。Thompson 采样这是另一种基于概率的探索方法。对于每个餐厅根据其历史评分构建一个概率分布。在选择餐厅时从每个餐厅的概率分布中采样得到一个值选择采样值最大的餐厅。随着尝试次数的增加概率分布会逐渐收敛从而实现探索和利用的平衡。
多策略融合
可以将贪婪算法与其他探索策略结合使用。例如在前期使用完全随机探索 ϵ 1 \epsilon 1 ϵ1快速了解各个餐厅的大致情况然后切换到 ϵ \epsilon ϵ-贪婪算法进行更有针对性的探索和利用。或者在不同的时间段采用不同的 ϵ \epsilon ϵ 策略如工作日和周末采用不同的 ϵ \epsilon ϵ 值因为不同时间段餐厅的服务质量和菜品可能会有所不同。 2-KIMI回答
在强化学习的探索/利用问题中计算结果与ε的取值密切相关。调整ε策略可以优化算法性能以下是详细分析
不同ε取值对结果的影响
ε取值较大时智能体更倾向于探索会更多地尝试新的动作从而有机会发现潜在的更高奖励。但过多的探索可能导致智能体在已知的较优动作上花费较少时间从而在短期内错过获得更高累积奖励的机会。ε取值较小时智能体更倾向于利用已有的知识选择当前看来最优的动作这样可以更快地获得较高的累积奖励。但过小的ε可能导致体智能过早地收敛到一个局部最优解而错过全局最优解。
如何与ε的取值有关
初始阶段在问题的初始阶段智能体对环境了解较少较大的ε值有助于快速收集关于不同动作的信息从而更快地建立对环境的初步认识。学习过程中随着智能体对环境的了解逐渐加深可以适当减小ε值减少探索的频率更多地利用已有的知识来获得较高的奖励。环境变化如果环境是动态变化的即奖励结构可能会随时间发生改变那么需要保持一定的ε值来持续探索以便适应环境的变化。
算法优化方法
动态调整ε值一种常见的方法是让ε值随着时间逐渐减小。例如可以采用线性衰减、指数衰减等方式。初始时设置较大的ε值进行充分的探索随着学习的进行逐渐减小ε值使智能体逐渐从探索转向利用。基于状态或上下文调整ε值根据当前的状态或上下文信息来动态调整ε值。在某些状态下可能需要更多的探索而在其他状态下则可以更多地利用已有的知识。结合其他探索策略除了ε-贪婪策略外还可以结合其他探索策略如 optimism in the face of uncertainty 或 Thompson sampling 等以更有效地平衡探索与利用。利用先验知识或经验如果有关于问题的先验知识或经验可以根据这些信息来调整ε值。例如在已知某些区域奖励较高的情况下可以适当降低这些区域的ε值减少不必要的探索。多智能体协作在多智能体系统中智能体之间可以共享探索信息从而减少每个智能体的探索负担提高整体的学习效率。 3-DeepSeek回答
好的我们来深入探讨计算结果与ε取值的关系以及如何进行算法优化并继续使用“小王选餐厅”的案例来说明。
核心结论计算结果性能与ε的取值密切相关且这种关系是非线性的、环境依赖的。
1. ε取值如何影响计算结果性能
在“小王选餐厅”的案例中ε代表了小王随机探索新餐厅而不是去当前已知最好的餐厅C的概率。ε的不同取值会导致截然不同的长期结果 ε 过大例如 ε 0.8 优点 探索非常充分。小王很快就能尝试完所有餐厅A, B, C, D快速发现最优餐厅C的可能性很高。也能很快确认雷区B。缺点 利用严重不足。即使小王已经知道C是最好的他仍然有80%的概率不去C而是随机选其他餐厅包括已知很差的B。这导致 大量低质量午餐 频繁吃到B-3分和可能一般的A、D。平均收益低 长期累积的满意度总奖励会很低因为他浪费了太多机会在次优或极差的选择上。结果 收敛速度快找到最优解C快但最终性能差平均奖励低。像一个“好奇心过重但不会专注”的人。 ε 过小例如 ε 0.01 优点 利用非常充分。一旦小王“偶然”发现了餐厅C比如在早期某次极小的探索概率下他几乎99%的时间都会去C吃饭获得稳定的高满意度2或3。缺点 探索严重不足。 可能错过最优解 如果早期随机探索没选中C而是先选中了A一般或B很差小王会过早地锁定在这些次优或极差的选择上因为Q(A)或Q(B)会先被更新为正值或“不那么负”而其他餐厅Q值还是0。他可能永远发现不了真正最好的餐厅C。对次优解过于执着 即使锁定在A一般上他也几乎不会去尝试C或D。结果 最终性能可能高如果幸运地早期找到C但也可能很低如果锁定在B或A。收敛速度慢且不稳定找到最优解C需要极长的时间甚至永远找不到。像一个“极其保守拒绝尝试新事物”的人。 ε 适中例如 ε 0.1 或 使用衰减策略 目标 在早期进行足够的探索以大概率发现最优解C并识别雷区B同时在后期进行充分的利用以最大化在C就餐的次数。结果 平衡了探索与利用。最终性能高平均奖励接近最优收敛速度相对较快且稳定。像一个“既愿意尝试新事物又懂得专注在好事物上”的聪明人。
总结ε对结果的影响
收敛速度找到最优解的速度 通常随着ε增大而加快探索更多更快发现所有选项。渐近性能长期平均奖励 存在一个最优的ε范围。过大或过小的ε都会导致渐近性能下降。稳定性找到最优解的概率 过小的ε可能导致永远找不到最优解锁定在次优解稳定性差。适中的ε稳定性好。环境依赖性 最优的ε值强烈依赖于具体环境 动作数量 餐厅越多可选动作越多通常需要更大的ε或更高的初始ε来保证充分探索。奖励方差/噪声 同一家餐厅满意度波动越大奖励噪声大可能需要更大的ε来持续验证Q值的准确性。次优动作的惩罚 像餐厅B这种极差选项负奖励大且稳定的存在使得过大的ε代价高昂需要更谨慎更小的ε或更快的衰减。最优动作的优势 餐厅C比A好很多最优动作优势明显则适度的探索就能带来巨大收益ε可以相对小些。环境是否平稳 如果餐厅质量会随时间变化非平稳环境则需要持续不断的探索ε不能衰减到0 来跟踪变化。
2. 如何进行算法优化解决对ε的依赖问题
既然ε的选择如此关键又如此困难需要针对不同环境调整研究者开发了多种优化方法核心思想是减少对固定ε的依赖或让ε动态适应学习过程
优化方法1ε衰减 (ε-Decay)
核心思想 在学习初期使用较高的εε₀ 促进充分探索快速获取环境信息。随着时间推移训练步数/回合数增加逐渐降低ε 到一个较小的下限值ε_min增加利用的比例。常用衰减方式 线性衰减 ε max(ε_min, ε₀ - slope * t) (t 是时间步)指数衰减 ε max(ε_min, ε₀ * decay_rate^t)逆时间衰减 ε max(ε_min, ε₀ / t) 或 ε max(ε_min, ε₀ / (1 decay_factor * t)) 在餐厅案例中的优化 早期前几周ε0.9 - 疯狂尝试所有餐厅快速发现C是好餐厅B是雷区。中期几周后ε逐渐降到0.3 - 主要去C偶尔再试试D或验证A。后期几个月后ε稳定在0.1 - 几乎只去C利用极少10%随机尝试一下防止错过变化或新店。 优点 简单有效显著缓解了固定ε的缺点早期探索不足后期利用不足。是实践中最常用、成本最低的优化方法。缺点 衰减率和初始/最终值仍是需要设定的超参数。衰减可能不够智能比如某个动作探索得还不够充分但ε已经降得很低了。
优化方法2自适应ε (Adaptive ε) / 基于不确定性的探索
核心思想 不再固定或按预定计划衰减ε而是根据智能体当前学习的状态动态调整ε。一个常见依据是动作的不确定性Uncertainty。简单实现思路示例 记录每个动作餐厅被选择的次数 N(a)。定义不确定性U(a) 1 / sqrt(N(a) 1)。尝试次数越少的动作不确定性越大。设定一个总体的不确定性阈值U_threshold 或 基准不确定性。如果平均不确定性或 最大不确定性 高于阈值则增加ε需要更多探索来降低不确定性。反之则降低ε可以利用了。 在餐厅案例中的可能表现 初期所有N(a)0 U(a)都很大 - ε很高充分探索。发现C很好 (N(C)增加快U(C)降低快)但D从未去过 (U(D)仍然很高) - ε保持中等鼓励去探索D。尝试过D后 (N(D)0)如果D一般 (U(D)降低)且其他餐厅不确定性都较低 - ε降低到很小。如果某个餐厅的满意度突然波动很大比如C某天得了-1分可能临时增加一点ε再去C多试几次确认。 优点 更智能地将探索资源分配给信息价值最高的动作尝试次数少、奖励波动大的动作理论上比固定衰减更高效。缺点 实现更复杂需要维护额外信息如计数、不确定性估计引入新的超参数如不确定性阈值、调整规则。
优化方法3完全避免ε基于置信度的探索策略
核心思想 放弃ε-贪婪框架采用不依赖探索概率参数ε的策略直接在动作选择中显式地平衡价值估计和不确定性估计。代表算法 UCB (Upper Confidence Bound): 选择具有最高上置信界的动作UCB(a) Q(a) c * sqrt(ln(t) / N(a))。其中 Q(a)当前平均奖励估计利用。c探索强度常数超参数但作用不同于ε。ln(t)总时间步的对数鼓励探索早期未充分尝试的动作。N(a)动作a被选择的次数。sqrt(ln(t) / N(a))对Q(a)估计不确定性的度量探索。 Thompson Sampling (TS): 一种贝叶斯方法。 为每个动作a的奖励分布如伯努利或高斯分布维护一个后验分布基于历史观察更新。每一步从每个动作a的后验分布中采样一个奖励值 θ_a。选择具有最大采样值θ_a的动作。本质以当前估计下该动作是最优的概率来选择它。不确定性高的动作其后验分布方差大采样值可能更大被选中的机会更大。 在餐厅案例中的优势 UCB 新餐厅DN(D)小其UCB值 Q(D) c * ... 会很大即使Q(D)初始为0必然在早期被高优先级探索。已知很差的B其Q(B)负且N(B)大UCB值会非常低几乎不会被选中。无需设定ε探索自然聚焦在潜力大的未知选项上。Thompson Sampling 同样会优先探索尝试次数少后验方差大的餐厅D。对于已知很差的B其后验分布的均值会很负采样出一个很大值的概率极低因此几乎不会被选中。 优点 通常比ε-贪婪即使衰减有更好的理论保证和实际性能。探索更精准高效自动规避已知差动作。无需手动设置探索概率ε。缺点 实现比ε-贪婪复杂尤其是TS需要维护和采样后验分布。UCB中的c、TS中的先验分布仍是超参数但调优相对鲁棒。计算开销可能略大。
总结如何优化
起点ε-贪婪 衰减 这是最简单、最常用、最容易实现的优化方法。优先尝试这个 选择合适的衰减方式和参数ε₀, ε_min, 衰减率需要通过实验网格搜索、随机搜索等在目标环境上微调。进阶自适应ε / UCB / Thompson Sampling 如果ε-贪婪衰减效果不佳特别是环境复杂、动作空间大、奖励噪声大、次优动作惩罚高时或者追求更高性能可以考虑这些更高级的策略。 UCB 是一个很好的替代方案实现相对简单理论坚实。Thompson Sampling 通常在经验上表现最好尤其适合贝努利奖励如点击率预估但实现稍复杂。自适应ε 处于两者之间可以基于ε-贪婪框架改进。 超参数调优 无论选择哪种策略包括UCB的c、TS的先验都不可避免地需要进行一定程度的超参数优化Hyperparameter Tuning。常用方法 网格搜索 (Grid Search) 在预设的参数组合中遍历。随机搜索 (Random Search) 在参数空间随机采样点尝试。贝叶斯优化 (Bayesian Optimization) 更智能地选择下一个待评估的参数点效率更高尤其当实验成本高时。 评估指标 优化时要选择合适的评估指标 最终平均奖励 (Average Return) 最重要的指标反映长期性能。收敛速度 (Learning Curve) 学习到高性能的速度。稳定性 (Variance) 多次运行结果的一致性。
最终结论
ε的取值对强化学习尤其是ε-贪婪策略的性能有决定性影响。一个糟糕的ε会导致智能体要么过于保守错过最优解要么过于浪费在次优/差动作上耗费资源。算法优化的核心目标就是减轻或消除对固定ε参数的脆弱依赖。 最实用有效的方法是ε衰减。追求更高性能或更智能探索时可考虑基于置信度的策略UCB, Thompson Sampling它们从根本上摒弃了ε参数通过显式地量化不确定性来指导探索。无论哪种方法结合超参数调优和严谨的评估都是必不可少的步骤。 4-积极初始值Optimistic Initial Values, OIV
积极初始值Optimistic Initial Values, OIV 是解决探索/利用困境的一种经典优化方案其核心思想是通过对价值估计如 Q 值设置“乐观”的高初始值来系统性地驱动早期探索。它巧妙地利用了强化学习算法自身的学习机制无需显式的探索概率如 ε或复杂的置信度计算。
核心思想利用“乐观偏差”激励探索 “乐观”假设 在算法开始时对所有状态-动作对s, a的初始 Q 值Q₀设置一个显著高于其真实期望奖励的值。例如如果知道环境中可能的最大单步奖励是 R_max 10那么可以设置初始 Q₀ 15 或 20甚至更大。即使不知道 R_max也可以设置一个非常大的正数如 Q₀ 100。 驱动探索的机制 初始“失望”效应 由于初始 Q 值被故意高估智能体在第一次执行任何动作后获得的实际奖励r几乎必然小于其初始 Q 值r Q₀。根据 Q 值更新规则如 Q_new Q_old α * (r - Q_old)这会导致该动作的 Q 值下降。“好奇心”的产生 当一个动作被执行后其 Q 值下降。此时那些尚未被执行过或执行次数少的动作其 Q 值仍然保持在高昂的初始值 Q₀。在基于价值的策略如 greedy 或 ε-greedy下智能体会优先选择当前 Q 值最高的动作。因此那些保持高 Q₀ 的未探索动作看起来比已探索并“失望”过的动作更具吸引力。自动轮询 这种机制会导致智能体系统地尝试所有尚未执行过的动作。每当一个动作被执行后它的 Q 值下降使得另一个具有更高初始Q 值的未尝试动作成为“最有吸引力”的选择。这个过程持续下去直到所有动作都被尝试过至少一次。 从探索到利用的自然过渡 初始探索阶段 在早期由于所有动作的初始 Q 值都很高且未被“验证”智能体会高效地遍历所有可能的动作状态-动作对。这是由上述“失望”效应和“高初始值吸引力”机制自动驱动的。价值收敛阶段 随着每个动作被执行多次其 Q 值通过不断接收实际奖励进行更新会逐渐从初始的高估状态向真实的期望奖励值收敛。利用主导阶段 一旦 Q 值收敛到接近真实值那些真正能带来高奖励的动作的 Q 值就会稳定在较高的水平虽然低于初始值但高于其他动作。此时greedy 策略自然就会选择这些最优动作进入利用主导阶段。不再需要初始值的“诱饵”作用。
与 ε-Greedy 的对比在餐厅案例中的应用
标准 ε-Greedy (无 OIV): 初始 Q 值通常设为 0 或小随机数。早期探索依赖随机性ε 概率。智能体可能重复尝试第一个偶然发现的不错动作如餐厅 A而迟迟不去尝试其他动作如 C, D错过潜在的最优解。 ε-Greedy 乐观初始值 (OIV): 初始 Q 值设为很高的值如 100 分。Day 1: 小王选餐厅。所有餐厅 Q100。他可能随机选 A或者用 greedy 选任意一个都一样。体验后打分 1。 更新 Q(A): Q(A) 100 α * (1 - 100) 100 - 很大的负数 ≈ 大幅下降 (比如降到 50)。 Day 2: 当前 Q 值A≈50, B100, C100, D100。Greedy 策略会选择 当前 Q 值最高 的动作。A 不再是最高B, C, D 仍是 100。小王几乎必然会选择 B、C 或 D 中的一个例如随机选 B。体验后打分 -3。 更新 Q(B): Q(B) 100 α * (-3 - 100) 100 - 很大的负数 ≈ 大幅下降 (比如降到 30)。 Day 3: 当前 Q 值A≈50, B≈30, C100, D100。Greedy 策略会选择 C 或 D。小王选 C体验后打分 3。 更新 Q©: Q(C) 100 α * (3 - 100) 100 - 较大的负数 ≈ 下降 (比如降到 70)。虽然下降但仍是当前最高之一。 Day 4: 当前 Q 值A≈50, B≈30, C≈70, D100。Greedy 策略会选 D (唯一仍是 100 的)。小王尝试 D体验后打分 0。 更新 Q(D): Q(D) 100 α * (0 - 100) 大幅下降 (比如降到 50)。 Day 5 及以后 现在所有餐厅都被尝试过至少一次Q 值初步反映了真实体验C≈70, A≈50, D≈50, B≈30。Greedy 策略会稳定地选择 餐厅 C当前最高 Q 值≈70。利用阶段开始。Q 值会随着后续在 C 的用餐继续微调如吃到更好的变成 75吃到稍差的降到 68但 C 大概率保持最高。
优点
驱动系统性探索 强制智能体在早期尝试所有动作避免遗漏潜在的最优解。探索是定向的选择当前估值最高的未充分探索动作而非纯随机。无需显式探索参数 不需要设置和调整像 ε 这样的探索概率参数。探索行为由学习算法内部的价值估计更新机制自动引发。简单易实现 只需要改变初始值设定算法主体如 Q-learning, SARSA无需修改。早期探索高效 在离散、动作空间不太大的问题中能快速覆盖所有可能动作。
缺点与注意事项
初始值设定依赖 设置过高 每个动作需要被“失望”多次才能将 Q 值拉低到真实水平导致早期探索时间过长可能包含过多低效探索。收敛到最优策略变慢。设置过低 失去“乐观”的驱动力可能无法保证所有动作都被充分探索退化成标准初始化0或随机小数的行为可能错过最优解。需要领域知识 最优的初始值通常需要对环境的最大可能奖励R_max有一定估计。虽然可以设置一个非常大的数如 1e5但可能带来数值稳定性问题或延长收敛时间。 非平稳环境问题 如果环境的真实奖励分布会随时间变化非平稳环境OIV 的早期探索完成后智能体可能会过度利用之前学到的最优动作不再充分探索以发现环境变化后的新最优动作。它主要驱动一次性的初始探索。函数逼近限制 在使用函数逼近器如神经网络估计 Q 值的深度强化学习中OIV 的效果可能不明显或难以实现。因为网络参数的初始化通常有固定方式如 Xavier, He难以直接控制所有 (s, a) 对的初始 Q 估计值都保持“乐观”且高水平。可能鼓励不必要的探索 在明显次优的动作上也需要执行一次带来负奖励才能将其高估的 Q 值拉低。
如何与 ε-Greedy 结合使用
OIV 和 ε-Greedy 不是互斥的可以结合使用以获得更好的效果尤其是在非平稳环境中
OIV (乐观初始值) 确保早期高效、系统性地覆盖所有动作。ε-Greedy (带或不带衰减) 在 OIV 驱动的初始探索完成后提供一个持续的、低水平的随机探索机制ε 0 或 ε_min 0。这有助于 持续跟踪环境是否发生变化非平稳性。处理函数逼近可能带来的估计误差。在动作空间巨大或连续时补充 OIV 可能覆盖不全的问题。
总结
积极初始值乐观初始值的核心思想是通过故意将价值函数Q 值的初始估计设置得显著高于真实值人为制造一种“所有选项最初看起来都很棒”的假象。 这种高估会导致智能体在尝试任何一个动作后都会经历“失望”Q 值下降而那些尚未尝试的动作由于保持着高昂的初始估值会自然成为后续决策的首选目标。这种机制自动驱动智能体在早期系统地探索所有可能的动作无需依赖外部探索概率ε。一旦所有动作被初步探索Q 值开始收敛到真实水平策略就会自然地过渡到利用阶段。它是一种简单、巧妙且有效的解决早期探索不足问题的方法尤其适用于离散动作空间和平稳环境。常与 ε-Greedy 结合以提供持续探索能力。 5-UCB动作选择方法Upper Confidence Bound, UCB
探索/利用困境的优化方案中Upper Confidence BoundUCB动作选择方法的核心思想是在动作选择时综合考虑动作的估计价值和其不确定性即该动作被探索的次数。其核心思想如下
核心思想 动作价值评估的不确定性 对于每个动作UCB方法不仅关注其估计的平均奖励值还考虑了该动作的不确定性。不确定性由该动作被选择的次数来衡量即动作被选择的次数越少其不确定性越高。这种不确定性反映了智能体对动作价值的了解程度被选择次数少的动作其估计价值可能并不准确存在较大的偏差或方差。 奖励上限的计算 UCB为每个动作计算一个奖励上限该上限由动作的估计平均奖励和一个与不确定性相关的项组成。具体公式为 U C B i ( t ) X ˉ i c ln t N i ( t ) UCB_i(t) \bar{X}_i c \sqrt{\frac{\ln t}{N_i(t)}} UCBi(t)XˉicNi(t)lnt 其中 X ˉ i \bar{X}_i Xˉi 是动作 i i i 的平均奖励估计值。 N i ( t ) N_i(t) Ni(t) 是到时间步 t t t 为止动作 i i i 被选择的次数。 c c c 是一个常数用于控制探索的程度。 ln t \ln t lnt 是时间步 t t t 的自然对数表示时间的推移。 ln t N i ( t ) \sqrt{\frac{\ln t}{N_i(t)}} Ni(t)lnt 是与不确定性相关的项反映了动作 i i i 的不确定性。 选择具有最高奖励上限的动作 在每个时间步智能体选择具有最高UCB值的动作进行执行。这个选择策略既考虑了动作的估计价值利用又考虑了动作的不确定性探索。
对于被选择次数较少的动作其不确定性项较大即使其估计平均奖励较低也可能因为较高的不确定性而具有较高的UCB值从而被选择执行探索。相反对于已经被充分探索的动作其不确定性项较小只有当其估计平均奖励较高时才会被选择利用。
平衡探索与利用 随着时间的推移被选择次数较少的动作会逐渐被探索其不确定性项会减小。当某个动作的估计平均奖励较高且不确定性较低时它将更有可能被选择利用。这种动态调整机制使得UCB方法能够在探索和利用之间实现有效的平衡。
关键点解析 不确定性驱动的探索 UCB方法通过引入不确定性项鼓励智能体去尝试那些被探索较少的动作。这种探索策略不是随机的而是基于对动作不确定性的度量因此能够更高效地发现潜在的高奖励动作。 奖励上限的动态调整 随着时间的推移和动作选择次数的增加每个动作的奖励上限会动态调整。这反映了智能体对动作价值认识的不断深化以及对探索和利用策略的动态优化。 参数 c c c 的作用 常数 c c c 控制了探索的程度。较大的 c c c 值会增加不确定性项的影响导致更多的探索较小的 c c c 值则会使智能体更倾向于选择估计平均奖励较高的动作减少探索。
示例说明
考虑一个多臂老虎机问题有三个老虎机分别标记为A、B和C。初始时三个老虎机的平均奖励估计值均为0选择次数均为0。假设常数 c 1 c 1 c1 。
第一次选择时由于所有老虎机的选择次数均为0不确定性项趋于无穷大因此三个老虎机的UCB值也均为无穷大。智能体可以随机选择一个老虎机进行第一次尝试。假设第一次选择了老虎机A并获得了奖励5。此时老虎机A的平均奖励估计值为5选择次数为1。其他两个老虎机的选择次数仍为0。第二次选择时计算三个老虎机的UCB值 老虎机A的UCB值为 5 1 × ln 2 1 ≈ 5 1 × 0.832 5.832 5 1 \times \sqrt{\frac{\ln 2}{1}} \approx 5 1 \times 0.832 5.832 51×1ln2 ≈51×0.8325.832老虎机B和C的UCB值仍为无穷大 智能体再次随机选择一个未被尝试的老虎机比如B。随着时间的推移每个老虎机的UCB值会根据选择次数和平均奖励进行动态调整。智能体会逐渐集中选择那些具有较高估计奖励且不确定性较低的老虎机从而实现探索和利用的平衡。
UCB方法通过这种方式在探索和利用之间取得平衡能够有效提高智能体在强化学习任务中的性能。 5-OIV积极初始值VS动作选择UCB
UCB 动作选择和OIV积极初始值这两种解决方案并非互斥它们也不是简单的演进关系而是在解决探索 - 利用困境上相互补充、各有侧重下面为你详细分析
两者没有直接的演进关系
核心思想差异 积极初始值其核心在于通过赋予所有动作一个较高的初始估计价值激励智能体在学习初期更积极地去尝试不同动作因为每个动作看起来都有很大的潜在价值从而实现广泛探索避免过早陷入局部最优。例如在多臂老虎机问题中一开始将每个老虎机的初始收益估计都设为一个较大的值促使玩家去尝试各个老虎机。UCB 动作选择主要是基于动作估计价值的置信上界来做决策它不仅考虑动作的估计价值还考虑估计的不确定性。通过置信上界公式 U C B ( a ) Q ( a ) c ln t n ( a ) UCB(a)Q(a)c\sqrt{\frac{\ln t}{n(a)}} UCB(a)Q(a)cn(a)lnt 平衡了对已知高价值动作的利用和对未知动作的探索。比如在多臂老虎机场景下它会综合考虑每个老虎机的平均收益和被尝试的次数来选择下一次拉动的老虎机。 作用阶段不同 积极初始值侧重于在学习的起始阶段发挥作用通过初始的高估值推动探索。UCB 动作选择在整个学习过程中都起作用它根据每个时间步的动作价值估计和尝试次数动态调整动作选择以实现探索与利用的平衡。
两者并非互斥可相互补充
结合使用增强效果 可以将积极初始值和 UCB 动作选择结合起来使用以更好地解决探索 - 利用困境。在使用 UCB 算法时先采用积极初始值来初始化动作的估计价值。这样在学习初期由于积极初始值的作用智能体会更积极地探索不同动作而 UCB 算法会在后续过程中根据动作的尝试情况和估计价值动态调整探索和利用的程度。举例说明 在美食广场选择餐厅的案例中一开始可以给每家餐厅一个较高的初始评分积极初始值然后在每次选择餐厅时使用 UCB 公式计算每家餐厅的置信上界选择置信上界最高的餐厅。这样既能在开始时鼓励对不同餐厅的探索又能在后续根据实际体验和尝试次数做出更合理的选择。 6-OIV积极初始值VS动作选择UCB
UCBUpper Confidence Bound动作选择和积极初始值Optimistic Initial Values, OIV是两种独立的解决探索/利用困境的方案它们并非互斥也不是演进关系而是基于不同的核心思想设计的正交方法。两者可以单独使用也可以结合使用。 1. 核心思想对比
方案核心思想驱动探索的机制积极初始值 (OIV)通过高估初始Q值人为制造乐观偏差让未尝试的动作“看起来更优”初始高估值吸引探索 → 尝试后估值下降 → 转向其他高估值动作UCB动作选择通过置信区间上界公式显式量化不确定性直接选择“潜力最大”的动作价值不确定性数学公式动态平衡已知价值Q和不确定性探索项 2. 关键区别
(1) 作用维度不同
OIV 是初始化策略仅在训练开始时通过设置初始值影响早期行为。本质是对Q值的欺骗性初始化。UCB 是动作选择策略在每一步决策时动态计算并选择动作替代了ε-greedy的随机选择。
(2) 探索驱动力来源不同
OIV 依赖价值更新机制如 Q Q α(r - Q)带来的“失望效应”未尝试动作保持高估值已尝试动作估值下降。UCB 依赖数学构造的置信上界公式 UCB(a) Q(a) c * √(ln(t) / N(a)) 其中 Q(a)当前平均奖励利用√(ln(t) / N(a))不确定性度量探索c调节探索强度的超参数
(3) 对非平稳环境的适应性
OIV 仅在早期强制探索无法应对环境变化后期不再探索新动作。UCB 天然适应非平稳环境 长期未选择的动作 N(a) 会变小 → 不确定性项增大 → 重新被探索。奖励分布变化会导致 Q(a) 波动 → 通过更新机制自动调整。 3. 为何两者不是演进关系
设计哲学不同 OIV 是“投机取巧”的初始化技巧利用算法更新机制的副作用。UCB 是严谨的基于置信区间的统计决策理论源自概率论。 无依赖关系 UCB 的提出无需以 OIV 为基础两者从不同角度解决探索问题。可独立实现 UCB 可直接替代 ε-greedy如 UCB1 算法。OIV 可搭配任意价值学习算法如 Q-learning OIV。 4. 两者能否结合
可以且效果可能更好尤其在需要强驱动早期探索的场景。
结合方式示例
# 初始化乐观初始值 (OIV)
Q {action: Q_optimistic for all actions}
N {action: 0 for all actions} # 动作计数器for t in range(total_steps):# UCB动作选择结合当前Q值可能已被OIV影响和不确定性ucb_values {a: Q[a] c * np.sqrt(np.log(t 1) / (N[a] 1e-5)) for a in actions}action argmax(ucb_values) # 执行动作获得奖励rr env.step(action) # 更新Q值和计数器N[action] 1alpha 1 / N[action] # 或固定学习率Q[action] Q[action] alpha * (r - Q[action])结合后的优势
早期探索更强 OIV 的高初始值 UCB 的不确定性项 → 未尝试动作的UCB值极高确保被优先探索。 后期稳定性更佳 UCB 的动态探索机制 → 持续监控环境变化避免OIV的后期探索不足问题。 规避OIV缺陷 UCB 的探索由数学公式控制不再依赖“失望效应”的被动探索。 5. 典型应用场景对比
场景推荐方案原因离散动作空间 环境平稳OIV (简单高效)快速覆盖初始探索后期无需持续探索动作空间大 非平稳环境UCB动态不确定性驱动探索自动跟踪环境变化需要极致早期探索如安全关键OIV UCB双保险确保所有动作被快速尝试深度强化学习DQN等UCB变种如Bootstrapped DQNOIV难以在神经网络中实现全局高估 总结
OIV 和 UCB 是独立且正交的技术分别从初始化欺骗和决策公式的角度解决探索问题。无演进关系UCB 不需要以 OIV 为基础两者数学原理不同。可组合使用OIV 确保早期强探索UCB 提供动态不确定性平衡适合高鲁棒性场景。优先选择建议 追求简单 → 用 OIV需理论保障/非平稳环境 → 用 UCB不介意复杂度 → OIV UCB效果最佳 7-GB梯度赌博算法执行过程
场景设定
假设你经常去一家有多种菜品的餐厅每次去只能点一道菜你希望通过多次尝试找到最喜欢即收益最高的菜品。这里的每道菜就相当于多臂老虎机问题中的一个“臂”而Gradient Bandit Algorithm梯度赌博算法能帮助你在尝试不同菜品探索和选择已知好吃的菜品利用之间找到平衡。
初始状态
偏好分数一开始你对所有菜品都没有任何经验为每道菜设置一个初始偏好分数 H ( a ) H(a) H(a) 初始值可以都设为 0这里 a a a 代表不同的菜品。选择概率根据这些偏好分数使用 softmax 函数计算选择每道菜的概率 π ( a ) π(a) π(a) 。softmax 函数会将偏好分数转化为概率分布公式为 π ( a ) e H ( a ) ∑ b 1 n e H ( b ) π(a)\frac{e^{H(a)}}{\sum_{b 1}^{n}e^{H(b)}} π(a)∑b1neH(b)eH(a) 其中 n n n 是菜品的总数。例如餐厅有 5 道菜初始时所有 H ( a ) H(a) H(a) 都为 0那么每道菜被选择的概率都是 e 0 5 × e 0 1 5 0.2 \frac{e^{0}}{5\times e^{0}}\frac{1}{5}0.2 5×e0e0510.2 。
执行过程
第一次用餐
菜品选择根据计算出的选择概率随机选择一道菜。假设你选择了宫保鸡丁。收益评估吃完后你根据自己的满意度给这道菜一个收益评分 R R R 比如你觉得味道不错给了 8 分满分 10 分。平均收益由于这是第一次用餐目前的平均收益 R ‾ \overline{R} R 就是这次的收益 8 分。梯度更新更新宫保鸡丁这道菜的偏好分数 H ( 宫保鸡丁 ) H(宫保鸡丁) H(宫保鸡丁) 更新公式为 H ( 宫保鸡丁 ) H ( 宫保鸡丁 ) α ( R − R ‾ ) ( 1 − π ( 宫保鸡丁 ) ) H(宫保鸡丁)H(宫保鸡丁)\alpha(R - \overline{R})(1 - π(宫保鸡丁)) H(宫保鸡丁)H(宫保鸡丁)α(R−R)(1−π(宫保鸡丁)) 其中 α \alpha α 是学习率假设 α 0.1 \alpha 0.1 α0.1 。则 H ( 宫保鸡丁 ) 0 0.1 × ( 8 − 8 ) × ( 1 − 0.2 ) 0 H(宫保鸡丁)0 0.1\times(8 - 8)\times(1 - 0.2)0 H(宫保鸡丁)00.1×(8−8)×(1−0.2)0 。其他菜品的偏好分数更新公式为 H ( a ) H ( a ) − α ( R − R ‾ ) π ( a ) H(a)H(a)-\alpha(R - \overline{R})π(a) H(a)H(a)−α(R−R)π(a) 所以其他菜品的偏好分数也不变依然是 0。然后重新计算选择每道菜的概率由于偏好分数都没变化每道菜的选择概率还是 0.2。
第二次用餐
菜品选择再次根据新的选择概率选择菜品。假设这次选择了鱼香肉丝。收益评估你觉得鱼香肉丝味道一般给了 5 分。平均收益更新此时平均收益 R ‾ 8 5 2 6.5 \overline{R}\frac{8 5}{2}6.5 R2856.5 分。梯度更新更新鱼香肉丝的偏好分数 H ( 鱼香肉丝 ) H ( 鱼香肉丝 ) α ( R − R ‾ ) ( 1 − π ( 鱼香肉丝 ) ) 0 0.1 × ( 5 − 6.5 ) × ( 1 − 0.2 ) − 0.12 H(鱼香肉丝)H(鱼香肉丝)\alpha(R - \overline{R})(1 - π(鱼香肉丝))00.1\times(5 - 6.5)\times(1 - 0.2) - 0.12 H(鱼香肉丝)H(鱼香肉丝)α(R−R)(1−π(鱼香肉丝))00.1×(5−6.5)×(1−0.2)−0.12 。其他菜品的偏好分数更新为 H ( a ) H ( a ) − α ( R − R ‾ ) π ( a ) H(a)H(a)-\alpha(R - \overline{R})π(a) H(a)H(a)−α(R−R)π(a) 例如宫保鸡丁的 H ( 宫保鸡丁 ) 0 − 0.1 × ( 5 − 6.5 ) × 0.2 0.03 H(宫保鸡丁)0-0.1\times(5 - 6.5)\times0.2 0.03 H(宫保鸡丁)0−0.1×(5−6.5)×0.20.03 。然后重新计算每道菜的选择概率此时宫保鸡丁的选择概率会增加鱼香肉丝的选择概率会降低。
后续用餐
重复上述过程随着用餐次数的增加每次用餐后都会根据当次选择的菜品收益和平均收益来更新偏好分数进而更新选择概率。如果某道菜的收益高于平均收益它的偏好分数会增加被选择的概率也会增加如果某道菜的收益低于平均收益它的偏好分数会降低被选择的概率也会降低。收敛情况经过多次用餐后算法会逐渐收敛你会更频繁地选择那些收益较高的菜品同时也会偶尔尝试其他菜品进行探索以确保不会错过可能更好的选择。
总结
Gradient Bandit Algorithm 通过不断更新菜品的偏好分数和选择概率根据每次用餐的收益反馈来调整后续的选择策略在探索新菜品和利用已知好吃的菜品之间找到一个动态的平衡最终帮助你找到最符合自己口味的菜品。 8-GB梯度赌博算法
梯度赌博算法Gradient Bandit Algorithms 是解决探索/利用困境的一种独特方案其核心思想是直接优化动作选择概率分布而非像传统方法那样先估计动作价值Q值再基于此选择动作。它通过随机梯度上升Stochastic Gradient Ascent 动态调整动作概率将探索机制自然地融入概率分布的更新过程中。 核心思想拆解
1. 抛弃价值估计转向概率优化 传统方法如ε-greedy、UCB 先估算每个动作的价值Q值再根据Q值决定选择策略贪婪/探索。 问题 依赖Q值估计的准确性在非平稳环境中可能不稳定。 梯度赌博算法 直接维护并优化一组动作偏好Action Preferences H t ( a ) H_t(a) Ht(a) 通过Softmax函数将这些偏好值转换为动作选择概率 π t ( a ) \pi_t(a) πt(a) 。 目标 通过调整 H t ( a ) H_t(a) Ht(a) 使得高奖励动作的概率增大低奖励动作的概率减小。 公式 π t ( a ) e H t ( a ) ∑ b e H t ( b ) (Softmax) \pi_t(a) \frac{e^{H_t(a)}}{\sum_{b} e^{H_t(b)}} \quad \text{(Softmax)} πt(a)∑beHt(b)eHt(a)(Softmax)
2. 基于奖励基准的梯度更新 更新规则 执行动作 A t A_t At 获得奖励 R t R_t Rt 后对所有动作的偏好 H t ( a ) H_t(a) Ht(a) 更新 H t 1 ( a ) { H t ( a ) α ( R t − R ˉ t ) ( 1 − π t ( a ) ) if a A t H t ( a ) − α ( R t − R ˉ t ) π t ( a ) if a ≠ A t H_{t1}(a) \begin{cases} H_t(a) \alpha (R_t - \bar{R}_t) (1 - \pi_t(a)) \text{if } a A_t \\ H_t(a) - \alpha (R_t - \bar{R}_t) \pi_t(a) \text{if } a \neq A_t \end{cases} Ht1(a){Ht(a)α(Rt−Rˉt)(1−πt(a))Ht(a)−α(Rt−Rˉt)πt(a)if aAtif aAt 其中 α \alpha α 学习率步长。 R ˉ t \bar{R}_t Rˉt 当前时刻前的平均奖励基准用于标准化奖励。 ( R t − R ˉ t ) (R_t - \bar{R}_t) (Rt−Rˉt) 奖励与基准的偏差正偏差鼓励当前动作负偏差惩罚。 直观解释 当前动作 a A t a A_t aAt ) 若奖励 R t R ˉ t R_t \bar{R}_t RtRˉt 优于历史平均则增加其偏好 H t ( a ) H_t(a) Ht(a) → 提高下次选择概率 π t ( a ) \pi_t(a) πt(a) 。 反之则减少偏好。其他动作 a ≠ A t a \neq A_t aAt ) 若 R t R ˉ t R_t \bar{R}_t RtRˉt 当前动作表现好则降低其他动作的偏好 → 抑制探索其他动作。 若 R t R ˉ t R_t \bar{R}_t RtRˉt 当前动作表现差则增加其他动作偏好 → 鼓励探索。
3. 奖励基准 R ˉ t \bar{R}_t Rˉt 的关键作用
动态基准 通常设置为历史奖励的指数移动平均 R ˉ t R ˉ t − 1 β ( R t − R ˉ t − 1 ) \bar{R}_t \bar{R}_{t-1} \beta (R_t - \bar{R}_{t-1}) RˉtRˉt−1β(Rt−Rˉt−1) β \beta β 为基准更新率意义 将奖励中心化使算法关注相对表现奖励是否高于平均而非绝对值。适应非平稳环境基准随奖励分布变化自动调整。避免偏好值 H t ( a ) H_t(a) Ht(a) 因奖励尺度不同而发散。 与其他方案的对比
特性梯度赌博算法ε-greedy / UCB核心对象动作偏好 H t ( a ) H_t(a) Ht(a) → 概率 π t ( a ) \pi_t(a) πt(a)动作价值 Q ( a ) Q(a) Q(a)探索机制概率分布的自然多样性 梯度更新规则显式探索随机/置信区间非平稳环境适应性⭐⭐⭐⭐ (基准动态调整)⭐⭐ (需衰减或UCB动态探索)计算复杂度较高需维护偏好和概率分布较低超参数敏感性学习率 α \alpha α 、基准更新率 β \beta βε / c / 衰减参数 工作流程示例餐厅选择场景
假设小王用梯度赌博算法选餐厅动作A/B/C初始偏好 H ( A ) H ( B ) H ( C ) 0 H(A)H(B)H(C)0 H(A)H(B)H(C)0 α 0.1 \alpha0.1 α0.1 β 0.1 \beta0.1 β0.1 Day 1: 初始概率 π ( A ) π ( B ) π ( C ) 1 / 3 \pi(A)\pi(B)\pi(C)1/3 π(A)π(B)π(C)1/3随机选 B获得奖励 R 1 − 3 R_1 -3 R1−3 难吃更新基准 R ˉ 1 0 0.1 × ( − 3 − 0 ) − 0.3 \bar{R}_1 0 0.1 \times (-3 - 0) -0.3 Rˉ100.1×(−3−0)−0.3更新偏好 H ( B ) 0 0.1 × ( − 3 − ( − 0.3 ) ) × ( 1 − 1 / 3 ) ≈ 0 ( − 0.27 ) × 0.67 ≈ − 0.18 H(B) 0 0.1 \times (-3 - (-0.3)) \times (1 - 1/3) ≈ 0 (-0.27) \times 0.67 ≈ -0.18 H(B)00.1×(−3−(−0.3))×(1−1/3)≈0(−0.27)×0.67≈−0.18 H ( A ) 0 − 0.1 × ( − 3 − ( − 0.3 ) ) × ( 1 / 3 ) ≈ 0 − ( − 0.27 ) × 0.33 ≈ 0.09 H(A) 0 - 0.1 \times (-3 - (-0.3)) \times (1/3) ≈ 0 - (-0.27) \times 0.33 ≈ 0.09 H(A)0−0.1×(−3−(−0.3))×(1/3)≈0−(−0.27)×0.33≈0.09 H ( C ) H(C) H(C) 同理更新为 0.09 0.09 0.09 Day 2: 新概率 π ( B ) \pi(B) π(B) ↓ π ( A ) \pi(A) π(A) ↑ π ( C ) \pi(C) π(C) ↑选 C获得奖励 R 2 3 R_2 3 R23 好吃更新基准 R ˉ 2 − 0.3 0.1 × ( 3 − ( − 0.3 ) ) ≈ 0 \bar{R}_2 -0.3 0.1 \times (3 - (-0.3)) ≈ 0 Rˉ2−0.30.1×(3−(−0.3))≈0更新偏好 H ( C ) H(C) H(C) 大幅增加奖励显著高于基准 H ( A ) , H ( B ) H(A), H(B) H(A),H(B) 小幅减少因当前动作表现好 后续 若C持续高奖励 → π ( C ) \pi(C) π(C) 迅速升高至接近1利用若C奖励偶然下降 → π ( C ) \pi(C) π(C) 适度降低其他动作概率回升探索恢复 优势与适用场景 优势 隐式探索 通过Softmax概率分布天然支持探索无需ε等参数。奖励标准化 动态基准 R ˉ t \bar{R}_t Rˉt 提升对奖励尺度/偏移的鲁棒性。适配非平稳环境 偏好值持续更新自动跟踪最优动作变化。 适用场景 奖励分布非平稳或尺度未知的问题。需要随机策略的场景如部分可观测环境。动作空间离散且规模中等Softmax计算成本可控。 局限性
计算开销大 每步需更新所有动作的偏好值并计算Softmax动作空间大时效率低。超参数调优复杂 α \alpha α 学习率和 β \beta β 基准更新率需精细调节。不适用确定性策略 天然输出概率分布若需完全确定性策略需额外处理如取argmax。 总结
梯度赌博算法的核心思想是 通过随机梯度上升直接优化动作选择概率分布利用
**偏好函数 H t ( a ) H_t(a) Ht(a) → Softmax概率 π t ( a ) \pi_t(a) πt(a) **基于奖励基准 R ˉ t \bar{R}_t Rˉt 的梯度更新规则 将探索/利用的平衡内化到概率分布的动态调整中。其本质是一种策略优化方法而非价值估计方法特别适合非平稳环境和需要自适应随机策略的场景。 9-GB梯度赌博算法
我们用「小王餐厅选择」的例子来详细说明梯度赌博算法Gradient Bandit Algorithm的执行过程。假设小王每周工作日周一至周五需要选择餐厅用餐我们将跟踪算法5天的完整执行流程。
场景设定
候选餐厅A日料、B西餐、C中餐奖励基准初始值 R ˉ 0 0 \bar{R}_0 0 Rˉ00学习率 α 0.2 \alpha 0.2 α0.2偏好更新强度基准更新率 β 0.1 \beta 0.1 β0.1奖励基准调整速度初始偏好值 H ( A ) H ( B ) H ( C ) 0 H(A)H(B)H(C)0 H(A)H(B)H(C)0 执行过程
周一探索启动 计算选择概率 π ( a ) e H ( a ) e 0 e 0 e 0 1 3 ∀ a \pi(a) \frac{e^{H(a)}}{e^0 e^0 e^0} \frac{1}{3} \quad \forall a π(a)e0e0e0eH(a)31∀a → π ( A ) 33.3 % , π ( B ) 33.3 % , π ( C ) 33.3 % \pi(A)33.3\%, \pi(B)33.3\%, \pi(C)33.3\% π(A)33.3%,π(B)33.3%,π(C)33.3% 选择动作 随机选择 B餐厅西餐 获得奖励 体验差 → R 1 − 2 R_1 -2 R1−2满分3最低-3 更新奖励基准 R ˉ 1 0 0.1 × ( − 2 − 0 ) − 0.2 \bar{R}_1 0 0.1 \times (-2 - 0) -0.2 Rˉ100.1×(−2−0)−0.2 更新偏好值 H ( B ) 0 0.2 × ( − 2 − ( − 0.2 ) ) × ( 1 − 0.333 ) − 0.2 × ( − 1.8 ) × 0.667 ≈ 0.24 H(B) 0 0.2 \times (-2 - (-0.2)) \times (1 - 0.333) -0.2 \times (-1.8) \times 0.667 \approx \textcolor{red}{0.24} H(B)00.2×(−2−(−0.2))×(1−0.333)−0.2×(−1.8)×0.667≈0.24 (实际奖励低于基准但更新量为正异常修正说明见底部) H ( A ) 0 − 0.2 × ( − 2 − ( − 0.2 ) ) × 0.333 − 0.2 × ( − 1.8 ) × 0.333 ≈ − 0.12 H(A) 0 - 0.2 \times (-2 - (-0.2)) \times 0.333 -0.2 \times (-1.8) \times 0.333 \approx \textcolor{blue}{-0.12} H(A)0−0.2×(−2−(−0.2))×0.333−0.2×(−1.8)×0.333≈−0.12 H ( C ) 0 − 0.2 × ( − 1.8 ) × 0.333 ≈ − 0.12 H(C) 0 - 0.2 \times (-1.8) \times 0.333 \approx \textcolor{blue}{-0.12} H(C)0−0.2×(−1.8)×0.333≈−0.12 修正说明计算中发现符号错误正确更新应为 H ( B ) 0 0.2 × ( − 2 − ( − 0.2 ) ) × ( 1 − 0.333 ) 0.2 × − 1.8 × 0.667 ≈ − 0.24 H(B) 0 0.2 \times (\textcolor{red}{-2} - (-0.2)) \times (1-0.333) 0.2 \times \textcolor{red}{-1.8} \times 0.667 \approx \textcolor{red}{-0.24} H(B)00.2×(−2−(−0.2))×(1−0.333)0.2×−1.8×0.667≈−0.24 H ( A ) 0 − 0.2 × − 1.8 × 0.333 ≈ 0.12 H(A) 0 - 0.2 \times \textcolor{red}{-1.8} \times 0.333 \approx 0.12 H(A)0−0.2×−1.8×0.333≈0.12 H ( C ) 0.12 H(C) 0.12 H(C)0.12 → 新偏好值 H ( A ) 0.12 , H ( B ) − 0.24 , H ( C ) 0.12 H(A)0.12, H(B)-0.24, H(C)0.12 H(A)0.12,H(B)−0.24,H(C)0.12 周二探索转向 计算选择概率 e 0.12 ≈ 1.127 , e − 0.24 ≈ 0.787 , e 0.12 ≈ 1.127 e^{0.12}≈1.127, e^{-0.24}≈0.787, e^{0.12}≈1.127 e0.12≈1.127,e−0.24≈0.787,e0.12≈1.127 Σ 3.041 \Sigma 3.041 Σ3.041 π ( A ) 37.1 % , π ( B ) 25.9 % , π ( C ) 37.1 % \pi(A)37.1\%, \pi(B)25.9\%, \pi(C)37.1\% π(A)37.1%,π(B)25.9%,π(C)37.1% 选择动作 选择 C餐厅中餐 获得奖励 体验极佳 → R 2 3 R_2 3 R23 更新奖励基准 R ˉ 2 − 0.2 0.1 × ( 3 − ( − 0.2 ) ) − 0.2 0.32 0.12 \bar{R}_2 -0.2 0.1 \times (3 - (-0.2)) -0.2 0.32 0.12 Rˉ2−0.20.1×(3−(−0.2))−0.20.320.12 更新偏好值 H ( C ) 0.12 0.2 × ( 3 − 0.12 ) × ( 1 − 0.371 ) 0.12 0.2 × 2.88 × 0.629 ≈ 0.48 H(C) 0.12 0.2 \times (3 - 0.12) \times (1 - 0.371) 0.12 0.2 \times 2.88 \times 0.629 ≈ \textcolor{green}{0.48} H(C)0.120.2×(3−0.12)×(1−0.371)0.120.2×2.88×0.629≈0.48 H ( A ) 0.12 − 0.2 × 2.88 × 0.371 ≈ 0.12 − 0.21 − 0.09 H(A) 0.12 - 0.2 \times 2.88 \times 0.371 ≈ 0.12 - 0.21 \textcolor{red}{-0.09} H(A)0.12−0.2×2.88×0.371≈0.12−0.21−0.09 H ( B ) − 0.24 − 0.2 × 2.88 × 0.259 ≈ − 0.24 − 0.15 − 0.39 H(B) -0.24 - 0.2 \times 2.88 \times 0.259 ≈ -0.24 - 0.15 \textcolor{red}{-0.39} H(B)−0.24−0.2×2.88×0.259≈−0.24−0.15−0.39 → 新偏好值 H ( A ) − 0.09 , H ( B ) − 0.39 , H ( C ) 0.48 H(A)-0.09, H(B)-0.39, H(C)0.48 H(A)−0.09,H(B)−0.39,H(C)0.48 周三利用开始 计算选择概率 e − 0.09 ≈ 0.91 , e − 0.39 ≈ 0.68 , e 0.48 ≈ 1.62 e^{-0.09}≈0.91, e^{-0.39}≈0.68, e^{0.48}≈1.62 e−0.09≈0.91,e−0.39≈0.68,e0.48≈1.62 Σ 3.21 \Sigma 3.21 Σ3.21 π ( A ) 28.3 % , π ( B ) 21.2 % , π ( C ) 50.5 % \pi(A)28.3\%, \pi(B)21.2\%, \pi(C)50.5\% π(A)28.3%,π(B)21.2%,π(C)50.5% 选择动作 选择 C餐厅中餐 获得奖励 体验良好 → R 3 2 R_3 2 R32 更新奖励基准 R ˉ 3 0.12 0.1 × ( 2 − 0.12 ) 0.12 0.19 0.31 \bar{R}_3 0.12 0.1 \times (2 - 0.12) 0.12 0.19 0.31 Rˉ30.120.1×(2−0.12)0.120.190.31 更新偏好值 H ( C ) 0.48 0.2 × ( 2 − 0.31 ) × ( 1 − 0.505 ) 0.48 0.2 × 1.69 × 0.495 ≈ 0.65 H(C) 0.48 0.2 \times (2 - 0.31) \times (1 - 0.505) 0.48 0.2 \times 1.69 \times 0.495 ≈ \textcolor{green}{0.65} H(C)0.480.2×(2−0.31)×(1−0.505)0.480.2×1.69×0.495≈0.65 H ( A ) − 0.09 − 0.2 × 1.69 × 0.283 ≈ − 0.09 − 0.10 − 0.19 H(A) -0.09 - 0.2 \times 1.69 \times 0.283 ≈ -0.09 - 0.10 \textcolor{red}{-0.19} H(A)−0.09−0.2×1.69×0.283≈−0.09−0.10−0.19 H ( B ) − 0.39 − 0.2 × 1.69 × 0.212 ≈ − 0.39 − 0.07 − 0.46 H(B) -0.39 - 0.2 \times 1.69 \times 0.212 ≈ -0.39 - 0.07 \textcolor{red}{-0.46} H(B)−0.39−0.2×1.69×0.212≈−0.39−0.07−0.46 → 新偏好值 H ( A ) − 0.19 , H ( B ) − 0.46 , H ( C ) 0.65 H(A)-0.19, H(B)-0.46, H(C)0.65 H(A)−0.19,H(B)−0.46,H(C)0.65 周四探索反弹 计算选择概率 e − 0.19 ≈ 0.83 , e − 0.46 ≈ 0.63 , e 0.65 ≈ 1.92 e^{-0.19}≈0.83, e^{-0.46}≈0.63, e^{0.65}≈1.92 e−0.19≈0.83,e−0.46≈0.63,e0.65≈1.92 Σ 3.38 \Sigma 3.38 Σ3.38 π ( A ) 24.6 % , π ( B ) 18.6 % , π ( C ) 56.8 % \pi(A)24.6\%, \pi(B)18.6\%, \pi(C)56.8\% π(A)24.6%,π(B)18.6%,π(C)56.8% 选择动作 小概率选中 A餐厅日料 获得奖励 体验中等 → R 4 1 R_4 1 R41 更新奖励基准 R ˉ 4 0.31 0.1 × ( 1 − 0.31 ) 0.31 0.07 0.38 \bar{R}_4 0.31 0.1 \times (1 - 0.31) 0.31 0.07 0.38 Rˉ40.310.1×(1−0.31)0.310.070.38 更新偏好值 H ( A ) − 0.19 0.2 × ( 1 − 0.38 ) × ( 1 − 0.246 ) − 0.19 0.2 × 0.62 × 0.754 ≈ − 0.10 H(A) -0.19 0.2 \times (1 - 0.38) \times (1 - 0.246) -0.19 0.2 \times 0.62 \times 0.754 ≈ \textcolor{blue}{-0.10} H(A)−0.190.2×(1−0.38)×(1−0.246)−0.190.2×0.62×0.754≈−0.10 H ( C ) 0.65 − 0.2 × 0.62 × 0.568 ≈ 0.65 − 0.07 0.58 H(C) 0.65 - 0.2 \times 0.62 \times 0.568 ≈ 0.65 - 0.07 \textcolor{green}{0.58} H(C)0.65−0.2×0.62×0.568≈0.65−0.070.58 H ( B ) − 0.46 − 0.2 × 0.62 × 0.186 ≈ − 0.46 − 0.02 − 0.48 H(B) -0.46 - 0.2 \times 0.62 \times 0.186 ≈ -0.46 - 0.02 \textcolor{red}{-0.48} H(B)−0.46−0.2×0.62×0.186≈−0.46−0.02−0.48 → 新偏好值 H ( A ) − 0.10 , H ( B ) − 0.48 , H ( C ) 0.58 H(A)-0.10, H(B)-0.48, H(C)0.58 H(A)−0.10,H(B)−0.48,H(C)0.58 周五收敛利用 计算选择概率 e − 0.10 ≈ 0.90 , e − 0.48 ≈ 0.62 , e 0.58 ≈ 1.79 e^{-0.10}≈0.90, e^{-0.48}≈0.62, e^{0.58}≈1.79 e−0.10≈0.90,e−0.48≈0.62,e0.58≈1.79 Σ 3.31 \Sigma 3.31 Σ3.31 π ( A ) 27.2 % , π ( B ) 18.7 % , π ( C ) 54.1 % \pi(A)27.2\%, \pi(B)18.7\%, \pi(C)54.1\% π(A)27.2%,π(B)18.7%,π(C)54.1% 选择动作 选择 C餐厅中餐 获得奖励 体验稳定 → R 5 2 R_5 2 R52 最终状态 H ( C ) H(C) H(C) 持续领先 0.58 → 0.70 0.58 → 0.70 0.58→0.70 π ( C ) \pi(C) π(C) 稳定在50% R ˉ 0.38 0.1 × ( 2 − 0.38 ) ≈ 0.54 \bar{R} 0.38 0.1 \times (2-0.38) ≈ 0.54 Rˉ0.380.1×(2−0.38)≈0.54奖励基准提升 关键动态分析
时间核心事件偏好变化概率变化算法行为周一首尝B餐厅负奖励 H ( B ) ↓ ↓ H(B)\downarrow\downarrow H(B)↓↓ π ( B ) ↓ \pi(B)\downarrow π(B)↓探索失败惩罚周二发现C餐厅高奖励 H ( C ) ↑ ↑ H(C)\uparrow\uparrow H(C)↑↑ π ( C ) ↑ \pi(C)\uparrow π(C)↑探索成功奖励周三巩固C餐厅正奖励 H ( C ) ↑ , H ( A ) ↓ H(C)\uparrow, H(A)\downarrow H(C)↑,H(A)↓ π ( C ) 50 % \pi(C)50\% π(C)50%利用强化周四小概率探索A中奖励 H ( A ) H(A) H(A)微调 H ( C ) H(C) H(C)略降 π ( C ) \pi(C) π(C)暂降探索反弹周五回归C餐厅正奖励 H ( C ) H(C) H(C)恢复领先 π ( C ) \pi(C) π(C)稳居高位收敛到利用 算法特点体现 概率驱动的探索 即使周三 π ( C ) \pi(C) π(C)已达50.5%周四仍有24.6%概率探索A餐厅实际发生无需外部ε参数 奖励基准的自适应 基准 R ˉ \bar{R} Rˉ从 − 0.2 → 0.54 -0.2→0.54 −0.2→0.54动态跟踪奖励水平变化 竞争性抑制机制 当C获得高奖励时 H ( A ) H(A) H(A)和 H ( B ) H(B) H(B)被主动降低周二、周三当A获得中奖励时 H ( C ) H(C) H(C)被轻微抑制周四 非平稳环境适应性 若某天C餐厅质量下降如换厨师奖励 R ↓ R↓ R↓将导致 H ( C ) H(C) H(C)更新值降低 π ( C ) \pi(C) π(C)自动下降其他餐厅概率回升 → 自然触发重新探索 与ε-greedy对比
场景梯度赌博算法ε-greedy (ε0.3)周三后行为概率自主分配C约55%A/B约45%70%选C30%完全随机探索质量更倾向探索潜力股A概率B可能浪费探索在已知很差的B奖励变化响应通过基准 R ˉ \bar{R} Rˉ和概率分布自动适应需手动调整ε或依赖价值估计周四选择A概率机制自然触发24.6%仅当30%随机探索触发且选中A 总结
梯度赌博算法通过偏好值→概率映射和基于奖励基准的竞争性更新将探索/利用平衡转化为概率分布的动态优化问题。在餐厅选择中
探索通过Softmax概率分布自然实现利用高奖励动作偏好值持续增长提升其概率自适应奖励基准 R ˉ t \bar{R}_t Rˉt动态校准使算法适应不同奖励尺度鲁棒性不依赖绝对价值估计对非平稳环境如餐厅质量变化表现优异
这种「概率优化」范式提供了一种完全不同于ε-greedy或UCB的探索哲学特别适合奖励尺度未知或动态变化的环境。 10-UCB动作选择方法算法的执行过程
以下是一个关于选择工作日午餐餐厅的真实生活案例详细说明强化学习中针对探索/利用优化方案中使用UCBUpper Confidence Bound动作选择方法算法的执行过程
案例背景
假设在一条美食街上有5家餐厅餐厅A、餐厅B、餐厅C、餐厅D、餐厅E每家餐厅的食物口味和品质各有特色。你每天中午都需要选择一家餐厅用餐但一开始对每家餐厅的具体口味和满意度不了解需要通过不断尝试来找到最优的午餐选择。在这个过程中你决定使用UCB动作选择方法来平衡探索新餐厅和利用已知好餐厅之间的关系。
算法执行过程
1. 初始化参数
对于每个餐厅ii A, B, C, D, E 初始化选择次数 N i 0 N_i 0 Ni0初始化平均奖励 X ˉ i 0 \bar{X}_i 0 Xˉi0 初始化常数 c c c 控制探索程度这里假设 c 1 c 1 c1 初始化总时间步 t 0 t 0 t0
2. 每天午餐选择过程 **时间步 t 1 t 1 t1 ** 对于每个餐厅i计算UCB值 U C B i ( 1 ) X ˉ i c ln t N i UCB_i(1) \bar{X}_i c \sqrt{\frac{\ln t}{N_i}} UCBi(1)XˉicNilnt 由于所有 N i 0 N_i 0 Ni0 所以每个餐厅的UCB值理论上为无穷大。随机选择一个餐厅假设选择了餐厅A。在餐厅A用餐获得奖励 R 1 R_1 R1 例如满意度评分为8。更新餐厅A的选择次数和平均奖励 N A 1 N_A 1 NA1 X ˉ A ( 0 × 0 ) 8 1 8 \bar{X}_A \frac{(0 \times 0) 8}{1} 8 XˉA1(0×0)88总时间步 t 1 t 1 t1 结束。 **时间步 t 2 t 2 t2 ** 对于每个餐厅i计算UCB值 U C B i ( 2 ) X ˉ i c ln 2 N i UCB_i(2) \bar{X}_i c \sqrt{\frac{\ln 2}{N_i}} UCBi(2)XˉicNiln2 餐厅A的UCB值 U C B A ( 2 ) 8 1 × ln 2 1 ≈ 8 0.832 8.832 UCB_A(2) 8 1 \times \sqrt{\frac{\ln 2}{1}} \approx 8 0.832 8.832 UCBA(2)81×1ln2 ≈80.8328.832其他餐厅的UCB值仍为无穷大因为它们的选择次数仍为0。随机选择一个未尝试的餐厅假设选择了餐厅B。在餐厅B用餐获得奖励 R 2 R_2 R2 例如满意度评分为6。更新餐厅B的选择次数和平均奖励 N B 1 N_B 1 NB1 X ˉ B 6 \bar{X}_B 6 XˉB6总时间步 t 2 t 2 t2 结束。 **时间步 t 3 t 3 t3 ** 对于每个餐厅i计算UCB值 U C B i ( 3 ) X ˉ i c ln 3 N i UCB_i(3) \bar{X}_i c \sqrt{\frac{\ln 3}{N_i}} UCBi(3)XˉicNiln3 餐厅A的UCB值 U C B A ( 3 ) 8 1 × ln 3 1 ≈ 8 1.098 9.098 UCB_A(3) 8 1 \times \sqrt{\frac{\ln 3}{1}} \approx 8 1.098 9.098 UCBA(3)81×1ln3 ≈81.0989.098餐厅B的UCB值 U C B B ( 3 ) 6 1 × ln 3 1 ≈ 6 1.098 7.098 UCB_B(3) 6 1 \times \sqrt{\frac{\ln 3}{1}} \approx 6 1.098 7.098 UCBB(3)61×1ln3 ≈61.0987.098其他餐厅的UCB值仍为无穷大。随机选择一个未尝试的餐厅假设选择了餐厅C。在餐厅C用餐获得奖励 R 3 R_3 R3 例如满意度评分为7。更新餐厅C的选择次数和平均奖励 N C 1 N_C 1 NC1 X ˉ C 7 \bar{X}_C 7 XˉC7总时间步 t 3 t 3 t3 结束。 **时间步 t 4 t 4 t4 ** 对于每个餐厅i计算UCB值 U C B i ( 4 ) X ˉ i c ln 4 N i UCB_i(4) \bar{X}_i c \sqrt{\frac{\ln 4}{N_i}} UCBi(4)XˉicNiln4 餐厅A的UCB值 U C B A ( 4 ) 8 1 × ln 4 1 ≈ 8 1.386 9.386 UCB_A(4) 8 1 \times \sqrt{\frac{\ln 4}{1}} \approx 8 1.386 9.386 UCBA(4)81×1ln4 ≈81.3869.386餐厅B的UCB值 U C B B ( 4 ) 6 1 × ln 4 1 ≈ 6 1.386 7.386 UCB_B(4) 6 1 \times \sqrt{\frac{\ln 4}{1}} \approx 6 1.386 7.386 UCBB(4)61×1ln4 ≈61.3867.386餐厅C的UCB值 U C B C ( 4 ) 7 1 × ln 4 1 ≈ 7 1.386 8.386 UCB_C(4) 7 1 \times \sqrt{\frac{\ln 4}{1}} \approx 7 1.386 8.386 UCBC(4)71×1ln4 ≈71.3868.386餐厅D和E的UCB值仍为无穷大。随机选择一个未尝试的餐厅假设选择了餐厅D。在餐厅D用餐获得奖励 R 4 R_4 R4 例如满意度评分为9。更新餐厅D的选择次数和平均奖励 N D 1 N_D 1 ND1 X ˉ D 9 \bar{X}_D 9 XˉD9总时间步 t 4 t 4 t4 结束。 **时间步 t 5 t 5 t5 ** 对于每个餐厅i计算UCB值 U C B i ( 5 ) X ˉ i c ln 5 N i UCB_i(5) \bar{X}_i c \sqrt{\frac{\ln 5}{N_i}} UCBi(5)XˉicNiln5 餐厅A的UCB值 U C B A ( 5 ) 8 1 × ln 5 1 ≈ 8 1.609 9.609 UCB_A(5) 8 1 \times \sqrt{\frac{\ln 5}{1}} \approx 8 1.609 9.609 UCBA(5)81×1ln5 ≈81.6099.609餐厅B的UCB值 U C B B ( 5 ) 6 1 × ln 5 1 ≈ 6 1.609 7.609 UCB_B(5) 6 1 \times \sqrt{\frac{\ln 5}{1}} \approx 6 1.609 7.609 UCBB(5)61×1ln5 ≈61.6097.609餐厅C的UCB值 U C B C ( 5 ) 7 1 × ln 5 1 ≈ 7 1.609 8.609 UCB_C(5) 7 1 \times \sqrt{\frac{\ln 5}{1}} \approx 7 1.609 8.609 UCBC(5)71×1ln5 ≈71.6098.609餐厅D的UCB值 U C B D ( 5 ) 9 1 × ln 5 1 ≈ 9 1.609 10.609 UCB_D(5) 9 1 \times \sqrt{\frac{\ln 5}{1}} \approx 9 1.609 10.609 UCBD(5)91×1ln5 ≈91.60910.609餐厅E的UCB值仍为无穷大。选择餐厅E。在餐厅E用餐获得奖励 R 5 R_5 R5 例如满意度评分为7。更新餐厅E的选择次数和平均奖励 N E 1 N_E 1 NE1 X ˉ E 7 \bar{X}_E 7 XˉE7总时间步 t 5 t 5 t5 结束。
3. 后续迭代过程
随着时间的推移继续使用UCB方法选择餐厅。每次选择餐厅时计算每个餐厅的UCB值选择UCB值最高的餐厅。每次用餐后根据实际获得的奖励更新对应餐厅的平均奖励和选择次数。随着选择次数的增加餐厅的UCB值会逐渐稳定选择具有较高平均奖励的餐厅的概率会增加。
总结
通过UCB动作选择方法你在探索新餐厅和利用已知好餐厅之间取得了平衡。在初始阶段由于对所有餐厅都不了解频繁地探索新餐厅随着对各餐厅的了解逐渐加深选择那些经过验证满意度较高的餐厅的频率增加。这种方法能够帮助你在长期的午餐选择中获得较高的满意度有效地解决了探索与利用的困境。 11-UCB动作选择方法算法的执行过程
真实生活案例在线视频平台的「视频推荐系统」
背景某视频平台如YouTube需在用户首页推荐3个视频A/B/C目标是最大化用户观看时长。
动作选择推荐哪个视频A/B/C奖励用户观看时长分钟挑战 视频A高质量但小众真实平均时长8分钟视频B中等质量但稳定真实平均时长5分钟视频C低质量标题党真实平均时长2分钟 目标用UCB算法平衡探索新视频与利用已知优质视频 UCB算法执行过程
参数设置
探索因子 c2平衡探索强度初始值 Q(A)Q(B)Q(C)0初始平均奖励N(A)N(B)N(C)0展示次数t0总推荐次数 第1轮强制探索t1
问题所有N(a)0 → UCB值无限大解决方案每个视频轮流展示一次初始探索 动作结果更新推荐A观看9分钟N(A)1, Q(A)9/19推荐B观看4分钟N(B)1, Q(B)4/14推荐C观看1分钟N(C)1, Q(C)1/11 总次数t3 第4轮UCB决策起点t4
计算UCB值c2, ln(3)≈1.1UCB(A) 9 2×√(1.1/2) ≈ 9 2×1.05 **11.1**
UCB(B) 4 2×√(1.1/1) ≈ 4 2.1 **6.1**
UCB(C) 1 2×√(1.1/1) ≈ 1 2.1 **3.1** 选择动作推荐UCB值最大的视频A利用结果观看7分钟接近真实值8更新 N(A)2, Q(A)(97)/28 t4 第5轮探索信号出现t5
计算UCB值ln(4)≈1.39UCB(A) 8 2×√(1.39/2) ≈ 8 2×√0.695 ≈ 8 2×0.83 **9.66**
UCB(B) 4 2×√(1.39/1) ≈ 4 2×1.18 **6.36**
UCB(C) 1 2×√(1.39/1) ≈ 1 2.36 **3.36** 选择动作仍然推荐视频A利用结果观看8分钟更新 N(A)3, Q(A)(168)/38 t5 第6轮系统触发探索t6
计算UCB值ln(5)≈1.61UCB(A) 8 2×√(1.61/3) ≈ 8 2×√0.537 ≈ 8 2×0.73 **9.46**
UCB(B) 4 2×√(1.61/1) ≈ 4 2×1.27 **6.54**
UCB(C) 1 2×√(1.61/1) ≈ 1 2×1.27 **3.54** 关键变化 B的探索项 √(ln(t)/N(B)) 从1.18→1.27因t↑但N(B)未增B的UCB值首次超过A的探索项6.54 9.46-81.46 选择动作推荐视频B探索结果观看5分钟符合真实值更新 N(B)2, Q(B)(45)/24.5 t6 第7轮验证探索结果t7
计算UCB值ln(6)≈1.79UCB(A) 8 2×√(1.79/3) ≈ 8 2×0.77 **9.54**
UCB(B) 4.5 2×√(1.79/2) ≈ 4.5 2×√0.895 ≈ 4.5 2×0.95 **6.4**
UCB(C) 1 2×√(1.79/1) ≈ 1 2×1.34 **3.68** 选择动作推荐视频AUCB值仍最高结果观看6分钟正常波动更新 N(A)4, Q(A)(246)/47.5 t7 第10轮压制低价值探索t10
当前状态 N(A)6, Q(A)≈7.8稳定高质量N(B)3, Q(B)4.3中等质量N(C)1, Q(C)1低质量 计算UCB值ln(10)≈2.3UCB(A) 7.8 2×√(2.3/6) ≈ 7.8 2×0.62 **9.04**
UCB(B) 4.3 2×√(2.3/3) ≈ 4.3 2×0.88 **6.06**
UCB(C) 1 2×√(2.3/1) ≈ 1 2×1.52 **4.04** ← 探索项激增 选择动作推荐视频C因长期未探索UCB探索项飙升结果观看0.5分钟用户快速跳过更新 N(C)2, Q(C)(10.5)/20.75 t10 第15轮收敛到最优解t15
最终状态 N(A)10, Q(A)7.9N(B)4, Q(B)4.5N(C)2, Q(C)0.75 UCB值计算UCB(A) 7.9 2×√(2.7/10) ≈ 7.9 2×0.52 **8.94**
UCB(B) 4.5 2×√(2.7/4) ≈ 4.5 2×0.82 **6.14**
UCB(C) 0.75 2×√(2.7/2) ≈ 0.75 2×1.16 **3.07** 策略结果 推荐A的概率 80%最优解偶尔推荐B约15%几乎不推荐C5% UCB的核心机制分析
1. 动态探索项公式
探索强度 c × √(㏑t / N(a))
N(a)↓展示少→ 探索项↑ → 强制探索如第6轮选Bt↑总次数增→ 探索项↑ → 防遗忘如第10轮选C
2. 智能探索分配
视频真实质量UB策略效果A高高利用为主偶尔验证B中适量探索占15%C低快速压制探索5%
3. 非平稳环境自适应
假设视频B质量提升新编剧→平均时长从5→7分钟
第20轮当B的Q(B)随新数据上升UCB变化Q(B)↑ 探索项↑因t↑→ 重新增加B的曝光 对比ε-greedy的劣势场景
假设使用ε0.2的贪婪算法
第10轮时 80%概率推荐A正确20%概率完全随机 → 可能浪费1/3探索在已知低质的C上 B质量提升时 依赖随机探索发现改进 → 响应速度慢 UCB在实际系统的优化
衰减机制# 降低旧数据权重适应内容变化
Q(a) (1 - α) * Q(a) α * r # α≈0.1~0.3上下文扩展Contextual BanditUCB(a) θ·x(a) c√(x(a)ᵀA⁻¹x(a)) # 加入用户特征分布式计算 全局统计t和N(a)局部计算用户个性化UCB 总结UCB的核心价值
通过数学公式量化不确定性 UCB ( a ) Q ( a ) ⏟ 利用项 c ln t N ( a ) ⏟ 探索项 \text{UCB}(a) \underbrace{Q(a)}_{\text{利用项}} \underbrace{c \sqrt{\frac{\ln t}{N(a)}}}_{\text{探索项}} UCB(a)利用项 Q(a)探索项 cN(a)lnt
探索自动分配给尝试不足或久未验证的动作利用优先选择置信上界最高的动作收敛证明总遗憾regret增长率为O(√T)
在视频推荐案例中UCB实现了
✅ 快速锁定优质视频A利用✅ 智能探索潜力视频B避免过早放弃✅ 压制低质视频C减少资源浪费✅ 自适应内容变化通过探索项响应质量波动
