目录
（2）上置信界（Upper Confidence Bound，UCB）
一、问题描述
多臂老虎机（MAB，muti-armed bandit）
K个拉杆，中奖概率分布未知，如何在T次拉杆后获得尽可能高的累计奖励？（也就是在有限的尝试次数里，让中奖次数尽可能多）
二、问题分析和解决
最简的RL系统，只有reward，没有state，更能体现纯粹的探索利用权衡。
关键就在于找到一个合适的exploration和exploitation的比例。
1、ε-greedy算法
大概率选目前中奖概率高的，小概率随机探索
1、如何判断中奖？
因为获奖概率是在 [ 0, 1 ) 中随机生成的数，假设为 x，
所以可以用随机投点模拟，落在区间 [ 0, x ) 为中奖，落在区间 [ x, 1 )为不中奖。
可不可以是 [ 0, x ] 中奖？不可以。
如果中奖概率x是0，按照左闭右闭的说法，则随机投点落在 [0 , 0]就中奖，即点数0可以中奖，但是实际上和中奖概率为0矛盾。所以不能是<=，只能是<。
2、计算历史中奖概率时，如果该拉杆从未被访问过，中奖概率赋值为0.1比0更好。为什么？
如果不设置为0.1，就很有可能，有些拉杆一直很难被选上。因为大概率是exploit的，而exploit又是选择历史中奖率最高的，而一直没被选中过的拉杆，如果设置概率为0，就不可能被选到（除了全为0时，迫不得已会选一个）。设置0.1可以鼓励初始阶段有更多的探索。
import numpy as np
from click.testing import Result
# 模拟K个拉杆的老虎机
K=10
probs = np.random.uniform(size=K) # 各个拉杆对应的获奖概率，为在[0,1)内随机生成的浮点数（均匀分布）
rewards = [[] for _ in range(K)] # 初始化各个拉杆的历史获奖记录，大数组内包含K个小数组，先设为空
# 选择哪个拉杆（贪婪算法）
def choose_one():
# 小概率（0.01）explore 随机挑选一个拉杆
if np.random.uniform()<0.01:
return np.random.randint(0,10)
else:
# 大概率（0.99）exploit 选择历史中奖概率最大的拉杆
rewards_mean = [np.mean(i) if i else 0.1 for i in rewards]
return np.argmax(rewards_mean)
# 玩一次
def play_once():
i = choose_one()
# 生成结果
cur_reward = 1 if np.random.uniform()<probs[i] else 0
# 记录结果
rewards[i].append(cur_reward)
if __name__=="__main__":
# 总共T次拉杆机会
T = 5000
for _ in range(T):
play_once()
# 真实中奖次数
true_result = np.sum([np.sum(i) for i in rewards])
# 理论中奖次数
theory_result = np.max(probs) * T
print(f"true_result: {true_result}")
print(f"theory_result: {theory_result}")2、改进的ε-greedy算法
（1）衰减的探索概率
随着经验的积累增加，我们的探索欲望是可以减弱的。
只需要修改小概率探索部分的代码：
# 玩的总次数（积累的经验有多少）
played_count = np.sum([len(i) for i in rewards])
# 探索概率随次数增加而下降
if np.random.uniform()<1/(played_count + 1): # +1避免除以0
return np.random.randint(0,10)（2）上置信界（Upper Confidence Bound，UCB）
多探索玩得少的机器。此时不是针对所有老虎机一概而论的，而是针对每台老虎机来说的，各自有各自的“探索欲望值”。玩得多的少探索，玩得少的仍想去多探索。
对于老虎机的场景：
动作a当前的平均奖励，即某拉杆对应的历史中奖次数的平均（中奖概率）
动作a被选择的次数，即某拉杆被play的次数
总时间步数，即所有拉杆被play次数的总和
特点：
不再显式区分探索（Explore）和利用（Exploit），而是通过一个统一的数学公式动态平衡二者。即UCB算法里面的explore和exploit不是分开的，不是小概率explore大概率exploit，而是综合考虑一个UCB值。
1、关于探索：
分母n小，即该拉杆的尝试次数少时，探索项大，UCB大，越有可能选择这个动作；
分子会随着时间缓慢增大（增长速度比分母慢），即总体的探索充足时，探索欲望会下降，UCB值会更倾向于平均奖励项，注重exploit。
超参数c越大，探索越激进；c越小，探索越保守。
def choose_one():
# 各个老虎机玩的次数
played_counts = np.array([len(i) for i in rewards])
# 优先探索未尝试过的拉杆（也是处理分母可能为0的情况）
if np.any(played_counts == 0):
return np.argmin(played_counts)
# 当所有拉杆都尝试过后，进入UCB算法
a = np.log(np.sum(played_counts)) # 分子是各台玩的次数求和的对数值，增长较慢
b = played_counts # 分母是每一台玩的次数，增长较快
# 对每一台老虎机，玩的次数越多，分母很快会超过分子，分数就越小，探索欲望就越低
rewards_mean = [np.mean(i) for i in rewards]
c = 2**0.5
ucb = rewards_mean + c * np.sqrt(a/b)
return np.argmax(ucb) # 选择UCB最大的拉杆（3）汤普森采样（Thompson Sampling）
根据历史成功次数和失败次数来生成Beta分布，该分布描述了“成功概率的概率分布”。
1、什么是Beta分布？
这里仅从直观上理解：它是“成功概率的概率分布”，所以必然是限制在[0,1)上的。
假设
- a：为 “成功次数 + 1”（+1 是为了避免初始值为 0 导致的极端情况）。
- b：为 “失败次数 + 1”。
a和b越大，分布越集中（因为尝试的次数越多，结果越明显，不确定性越低）；
a和b越小，分布越分散（不确定性越高）。
初始时，a=b=1，成功概率的期望是0.5，但是是均匀分布（完全分散状态）；
随着实验次数增多，a=b时，成功概率的期望仍然是0.5，但是会呈现峰值在0.5的对称分布（更集中）。
a>b，成功的次数多于失败，则成功概率会偏向1的一边；
a<b，失败的次数多于成功，则成功概率会偏向0的一边。
np.random.beta(a, b)会返回随机数，它是在beta分布上采的样值。
2、汤普森采样是怎么隐式平衡exploit和explore的？
在MAB问题中，该算法根据“中奖概率的Beta概率分布”来生成一个随机数，当作中奖概率。然后选取中奖概率最大的拉杆来拉。
关键在于它是用随机数来模拟概率，并不是用准确的历史中奖概率，或者是Beta峰值对应的数（其实就是接近
成功次数/(成功次数+失败次数)，即历史中奖概率）。这种随机采样是 “带着不确定性做决策”，既优先选择当前看起来好的拉杆（利用），又给不确定的拉杆留了机会（探索）。
对于历史表现好（a>b）且稳定的（不确定性低），随机数很可能落在高概率区，易被选中（exploit）；
对于不确定性高的，随机数的概率分布较分散，仍有一定可能采到高值，导致被选中（explore）。
通过概率分布的 “不确定性” 自动把握探索与利用的比例，无需人工设定参数。
3、和UCB对比
汤普森采样：更像 “凭直觉的赌徒”，通过概率猜测拉杆好坏，灵活性高、实践效果好，适合复杂或实时场景。
探索力度可以动态自适应，计算简单，对奖励噪声更稳健（因为概率分布天然平滑了随机波动），理论保证相对较弱，但在实践中往往表现更好
UCB：更像 “严谨的统计学家”，通过公式严格计算每个拉杆的潜力，理论扎实，适合对可解释性和收敛性要求高的场景。
探索力度由公式强制，计算复杂，对极端值较敏感，有严格的理论证明解释
def choose_one():
# 每个拉杆中奖的次数
counts_1 = [sum(i)+1 for i in rewards]
# 每个拉杆不中奖的次数
counts_0 = [sum(1-np.array(i))+1 for i in rewards]
# 对每个拉杆，根据 beta 分布随机生成中奖概率
beta = np.random.beta(counts_1,counts_0)
return np.argmax(beta)