强化学习-UCB示例

强化学习-UCB示例

1-UCB动作选择方法算法-示例1

场景设定

假设你来到一家有多种菜品的餐厅，每次去只能点一道菜，你希望通过多次尝试找到最合自己口味（即收益最高）的菜品。这里每道菜就相当于多臂老虎机问题中的一个“臂”，UCB（Upper Confidence Bound，置信上限）动作选择方法可以帮助你在尝试不同菜品（探索）和选择已知好吃的菜品（利用）之间找到平衡。

初始状态

餐厅有 $$n$$ 道菜，一开始你对所有菜品都没有任何体验。对于每道菜 $$i$$ ，需要记录两个值：

• **尝试次数 $$n_i$$ **：初始时，每道菜的尝试次数 $$n_i=0$$ 。
• **累计收益 $$R_i$$ **：初始时，每道菜的累计收益 $$R_i=0$$ 。
• **总尝试次数 $$N$$ **：初始时 $$N=0$$ 。

执行过程

前 $$n$$ 次用餐（探索阶段）

• 菜品选择：为了对每道菜都有一定的了解，在前 $$n$$ 次用餐中，你会依次选择不同的菜品。即第一次选择第一道菜，第二次选择第二道菜，以此类推，直到把 $$n$$ 道菜都尝试一遍。
• 收益评估：每次用餐后，你根据自己对这道菜的满意度给出一个收益评分 $$r$$ ，例如满分为 10 分。假设你第一次选择了宫保鸡丁，吃完后觉得味道不错，给了 7 分。此时，宫保鸡丁的尝试次数 $$n_{宫保鸡丁}=1$$ ，累计收益 $$R_{宫保鸡丁}=7$$ ，总尝试次数 $$N=1$$ 。第二次选择鱼香肉丝，给了 6 分，那么鱼香肉丝的 $$n_{鱼香肉丝}=1$$ ， $$R_{鱼香肉丝}=6$$ ，总尝试次数 $$N=2$$ 。
• 平均收益计算：每道菜的平均收益 $${\overline{R}}_i=\frac{R_i}{n_i}$$ 。例如宫保鸡丁的平均收益 $${\overline{R}}_{宫保鸡丁}=\frac{7}{1}=7$$ 分，鱼香肉丝的平均收益 $${\overline{R}}_{鱼香肉丝}=\frac{6}{1}=6$$ 分。

第 $$n+1$$ 次及以后的用餐（探索与利用平衡阶段）

• 计算 UCB 值：从第 $$n+1$$ 次用餐开始，每次选择菜品前，需要为每道菜计算 UCB 值。UCB 值的计算公式为 $$UC{B}_i={\overline{R}}_i+c\sqrt{\frac{\ln N}{n_i}}$$ ，其中 $$c$$ 是一个常数，用于控制探索和利用的平衡， $$c$$ 值越大，越倾向于探索； $$c$$ 值越小，越倾向于利用。假设 $$c=1$$ 。
  • 以宫保鸡丁和鱼香肉丝为例，假设已经尝试了 3 次（ $$N=3$$ ），宫保鸡丁尝试了 2 次（ $$n_{宫保鸡丁}=2$$ ），累计收益 $$R_{宫保鸡丁}=13$$ （第二次吃宫保鸡丁给了 6 分），平均收益 $${\overline{R}}_{宫保鸡丁}=\frac{13}{2}=6.5$$ 分；鱼香肉丝尝试了 1 次（ $$n_{鱼香肉丝}=1$$ ），累计收益 $$R_{鱼香肉丝}=6$$ 分，平均收益 $${\overline{R}}_{鱼香肉丝}=6$$ 分。
  • 计算宫保鸡丁的 UCB 值： $$UC{B}_{宫保鸡丁}=6.5+1\times \sqrt{\frac{\ln 3}{2}}\approx 6.5+0.73=7.23$$ 。
  • 计算鱼香肉丝的 UCB 值： $$UC{B}_{鱼香肉丝}=6+1\times \sqrt{\frac{\ln 3}{1}}\approx 6+1.09=7.09$$ 。
• 菜品选择：选择 UCB 值最大的菜品。在上述例子中，因为 $$UC{B}_{宫保鸡丁}>UC{B}_{鱼香肉丝}$$ ，所以第 4 次用餐你会选择宫保鸡丁。
• 收益评估与数据更新：用餐后，根据满意度给出这道菜的收益评分 $$r$$ 。假设这次吃宫保鸡丁给了 7 分，那么宫保鸡丁的累计收益 $$R_{宫保鸡丁}=13+7=20$$ ，尝试次数 $$n_{宫保鸡丁}=3$$ ，总尝试次数 $$N=4$$ ，平均收益 $${\overline{R}}_{宫保鸡丁}=\frac{20}{3}\approx 6.67$$ 分。然后在下一次选择时，重新计算每道菜的 UCB 值，重复上述过程。

总结

UCB 动作选择方法在前期会对所有菜品进行探索，以获取基本的收益信息。之后，通过计算每道菜的 UCB 值，综合考虑菜品的平均收益和其不确定性（尝试次数），在探索新菜品和利用已知好吃的菜品之间找到平衡。随着用餐次数的增加，会逐渐倾向于选择那些平均收益高且相对稳定（尝试次数多）的菜品，但也会偶尔尝试其他菜品，以避免错过可能更好的选择。

---

2-UCB动作选择方法算法-示例2

在UCB（Upper Confidence Bound，置信上限）动作选择方法中，确实会自动分配更多机会给尝试不足或久未验证的动作，下面结合餐厅用餐的例子详细解释其原理及证明。

UCB值公式体现探索性

UCB值的计算公式为 $$UC{B}_i={\overline{R}}_i+c\sqrt{\frac{\ln N}{n_i}}$$ ，其中：

• $${\overline{R}}_i$$ 是动作 $$i$$ （对应餐厅里的某道菜）的平均收益，代表了目前对该动作的已知收益情况。
• $$N$$ 是总的尝试次数。
• $$n_i$$ 是动作 $$i$$ 被尝试的次数。
• $$c$$ 是一个常数，用于调节探索和利用的平衡。

公式中的 $$c\sqrt{\frac{\ln N}{n_i}}$$ 这一项体现了对动作不确定性的估计，也就是鼓励对尝试不足或久未验证的动作进行探索。

尝试不足的菜品优先被选择

• 数学原理：当某道菜 $$i$$ 的尝试次数 $$n_i$$ 较小时， $$\frac{\ln N}{n_i}$$ 的值会较大，从而使得 $$c\sqrt{\frac{\ln N}{n_i}}$$ 这一项的值较大，那么 $$UC{B}_i$$ 的值就会相对较大。
• 结合例子：假设餐厅有宫保鸡丁、鱼香肉丝和麻婆豆腐三道菜。前几次用餐后，宫保鸡丁尝试了 10 次，平均收益是 7 分；鱼香肉丝只尝试了 2 次，平均收益是 6 分；麻婆豆腐尝试了 1 次，收益是 8 分。此时总尝试次数 $$N=13$$ ，设 $$c=1$$ 。
  • 计算宫保鸡丁的 UCB 值： $$UC{B}_{宫保鸡丁}=7+1\times \sqrt{\frac{\ln 13}{10}}\approx 7+0.52=7.52$$ 。
  • 计算鱼香肉丝的 UCB 值： $$UC{B}_{鱼香肉丝}=6+1\times \sqrt{\frac{\ln 13}{2}}\approx 6+1.47=7.47$$ 。
  • 计算麻婆豆腐的 UCB 值： $$UC{B}_{麻婆豆腐}=8+1\times \sqrt{\frac{\ln 13}{1}}\approx 8+1.86=9.86$$ 。
  • 可以看到，虽然麻婆豆腐只尝试了 1 次，但由于其尝试次数少，不确定性大，导致 $$c\sqrt{\frac{\ln N}{n_i}}$$ 这一项的值较大，使得它的 UCB 值最大，因此下一次就会优先选择麻婆豆腐进行尝试。

久未验证的菜品有机会被再次选择

• 数学原理：随着总尝试次数 $$N$$ 的增加， $$\ln N$$ 会不断增大。对于久未验证（即尝试次数 $$n_i$$ 没有随着 $$N$$ 同步增加）的动作， $$\frac{\ln N}{n_i}$$ 会逐渐增大，从而使得 $$c\sqrt{\frac{\ln N}{n_i}}$$ 增大， $$UC{B}_i$$ 也可能增大。
• 结合例子：假设经过多次用餐，大部分时候都选择了宫保鸡丁和鱼香肉丝，麻婆豆腐很久没有被选择了。此时总尝试次数 $$N$$ 变得很大，而麻婆豆腐的尝试次数 $$n_{麻婆豆腐}$$ 没有增加太多。那么 $$c\sqrt{\frac{\ln N}{n_{麻婆豆腐}}}$$ 这一项会随着 $$N$$ 的增大而增大，有可能使得麻婆豆腐的 $$UC{B}_{麻婆豆腐}$$ 超过其他菜品，从而在下一次被选择，即对其进行再次验证。

综上所述，UCB动作选择方法通过UCB值的计算，能够自动分配更多机会给尝试不足或久未验证的动作，在餐厅用餐的例子中，会优先选择那些尝试次数少的菜品，或者在总尝试次数增加后再次选择久未尝试的菜品。

---

3-UCB动作选择方法算法-示例3

真实生活案例：在线视频平台的「视频推荐系统」

背景：某视频平台（如YouTube）需在用户首页推荐3个视频（A/B/C），目标是最大化用户观看时长。

• 动作：选择推荐哪个视频（A/B/C）
• 奖励：用户观看时长（分钟）
• 挑战：
  • 视频A：高质量但小众（真实平均时长=8分钟）
  • 视频B：中等质量但稳定（真实平均时长=5分钟）
  • 视频C：低质量标题党（真实平均时长=2分钟）
    目标：用UCB算法平衡探索新视频与利用已知优质视频

---

UCB算法执行过程

参数设置：

• 探索因子 c=2（平衡探索强度）
• 初始值：
  • Q(A)=Q(B)=Q(C)=0（初始平均奖励）
  • N(A)=N(B)=N(C)=0（展示次数）
  • t=0（总推荐次数）

---

第1轮：强制探索（t=1）

• 问题：所有N(a)=0 → UCB值无限大
• 解决方案：每个视频轮流展示一次（初始探索）

  动作	结果	更新
  推荐A	观看9分钟	N(A)=1, Q(A)=9/1=9
  推荐B	观看4分钟	N(B)=1, Q(B)=4/1=4
  推荐C	观看1分钟	N(C)=1, Q(C)=1/1=1

• 总次数：t=3

---

第4轮：UCB决策起点（t=4）

• 计算UCB值（c=2, ln(3)≈1.1）：

  UCB(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)=(9+7)/2=8
t=4

---

第5轮：探索信号出现（t=5）

• 计算UCB值（ln(4)≈1.39）：

  UCB(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)=(16+8)/3=8
t=5

---

第6轮：系统触发探索（t=6）

• 计算UCB值（ln(5)≈1.61）：

  UCB(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-8=1.46）
• 选择动作：推荐视频B（探索）
• 结果：观看5分钟（符合真实值）
• 更新：
  N(B)=2, Q(B)=(4+5)/2=4.5
t=6

---

第7轮：验证探索结果（t=7）

• 计算UCB值（ln(6)≈1.79）：

  UCB(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**  
  

• 选择动作：推荐视频A（UCB值仍最高）
• 结果：观看6分钟（正常波动）
• 更新：
  N(A)=4, Q(A)=(24+6)/4=7.5
t=7

---

第10轮：压制低价值探索（t=10）

• 当前状态：
  • N(A)=6, Q(A)≈7.8（稳定高质量）
  • N(B)=3, Q(B)=4.3（中等质量）
  • N(C)=1, Q(C)=1（低质量）
• 计算UCB值（ln(10)≈2.3）：

  UCB(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)=(1+0.5)/2=0.75
t=10

---

第15轮：收敛到最优解（t=15）

• 最终状态：
  • N(A)=10, Q(A)=7.9
  • N(B)=4, Q(B)=4.5
  • N(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%）
  • 几乎不推荐C（<5%）

---

UCB的核心机制分析

1. 动态探索项公式

探索强度 = c × √(㏑t / N(a))

• N(a)↓（展示少）→ 探索项↑ → 强制探索（如第6轮选B）
• t↑（总次数增）→ 探索项↑ → 防遗忘（如第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的贪婪算法：

1. 第10轮时：
   • 80%概率推荐A（正确）
   • 20%概率完全随机 → 可能浪费1/3探索在已知低质的C上
2. B质量提升时：
   • 依赖随机探索发现改进 → 响应速度慢

---

UCB在实际系统的优化

1. 衰减机制：

   # 降低旧数据权重（适应内容变化）
   Q(a) = (1 - α) * Q(a) + α * r  # α≈0.1~0.3
   

2. 上下文扩展（Contextual Bandit）：

   UCB(a) = θ·x(a) + c√(x(a)ᵀA⁻¹x(a))  # 加入用户特征
   

3. 分布式计算：
   • 全局统计t和N(a)
   • 局部计算用户个性化UCB

---

总结：UCB的核心价值

通过数学公式量化不确定性：
$$\text{UCB}(a)=\underset{\text{利用项}}{\underbrace{Q(a)}}+\underset{\text{探索项}}{\underbrace{c\sqrt{\frac{\ln t}{N(a)}}}}$$

1. 探索：自动分配给尝试不足或久未验证的动作
2. 利用：优先选择置信上界最高的动作
3. 收敛证明：总遗憾（regret）增长率为O(√T)

在视频推荐案例中，UCB实现了：

• ✅ 快速锁定优质视频A（利用）
• ✅ 智能探索潜力视频B（避免过早放弃）
• ✅ 压制低质视频C（减少资源浪费）
• ✅ 自适应内容变化（通过探索项响应质量波动）