上界置信算法
设想这样一种情况：对于一台双臂老虎机，其中第一根拉杆只被拉动过一次，得到的奖励为 ；第二根拉杆被拉动过很多次，我们对它的奖励分布已经有了大致的把握。这时你会怎么做？或许你会进一步尝试拉动第一根拉杆，从而更加确定其奖励分布。这种思路主要是基于不确定性，因为此时第一根拉杆只被拉动过一次，它的不确定性很高。一根拉杆的不确定性越大，它就越具有探索的价值，因为探索之后我们可能发现它的期望奖励很大。我们在此引入不确定性度量\(U(a)\) ，它会随着一个动作被尝试次数的增加而减小。我们可以使用一种基于不确定性的策略来综合考虑现有的期望奖励估值和不确定性，其核心问题是如何估计不确定性。
上界置信算法
- 霍夫丁不等式
- 在霍夫丁不等式中，令\(X_1,X_2,X_3,...,X_n\)为n个独立同分布的随机变量，取值范围为\([0,1]\)，其经验期望为\(\bar{x_n}=\frac{1}{n}\sum^{n}_{j=1}X_j\)，则有(\(P(E[X]\ge \bar{x_n}+u)\le e^{-2nu^2}\)\)
独立同分布：独立同分布（Independent Identically Distribution）在概率统计理论中，指随机过程中，任何时刻的取值都为随机变量，如果这些随机变量服从同一分布，并且互相独立，那么这些随机变量是独立同分布。独立同分布最早应用于统计学，随着科学的发展，独立同分布已经应用数据挖掘，信号处理等不同的领域。
- 在霍夫丁不等式中，令\(X_1,X_2,X_3,...,X_n\)为n个独立同分布的随机变量，取值范围为\([0,1]\)，其经验期望为\(\bar{x_n}=\frac{1}{n}\sum^{n}_{j=1}X_j\)，则有(\(P(E[X]\ge \bar{x_n}+u)\le e^{-2nu^2}\)\)
在多臂老虎机问题中的应用
- 将\(\hat{Q}(a_t)\)代入\(\bar{x_t}\)，不等式中的参数\(u=\hat{Q}(a_t)\)代表不确定性度量
- 不确定性度量会随着一个动作被尝试的次数而减小
- 给定一个概率\(p=e^{-2N(a_t)U(a_t)^2}\)
- 根据上述不等式，\(Q_{t}(a)<\hat{Q}_{t}(a)+\hat{U}_{t}(a)\)至少以概率\(1-p\)成立
- 当p很小的时候，\(Q_{t}(a)<\hat{Q}_{t}(a)+\hat{U}_{t}(a)\)就有很大概率成立
- \(\hat{Q}_{t}(a)+\hat{U}_{t}(a)\)即期望奖励上界
- 根据上述不等式，\(Q_{t}(a)<\hat{Q}_{t}(a)+\hat{U}_{t}(a)\)至少以概率\(1-p\)成立
- 此时，上界置信算法便选取期望奖励上界最大的动作，即\(a=\underset{a \in \mathcal{A}}{\operatorname{argmax}}[\hat{Q}(a)+\hat{U}(a)]\)
- 由\(p=e^{-2N(a_t)U(a_t)^2}\)得，\(\hat{U}_{t}(a)=\sqrt{\frac{-\log p}{2 N_{t}(a)}}\)
[!直观解释] UCB在每一次选择拉杆前，先估计拉动每根拉杆的期望奖励上界，使得拉动每根拉杆的期望奖励只有较小的概率能超过这个期望奖励上界，接着选出期望奖励上界最大的拉杆，从而选择最有可能获得最高期望奖励的拉杆，
- 由\(p=e^{-2N(a_t)U(a_t)^2}\)得，\(\hat{U}_{t}(a)=\sqrt{\frac{-\log p}{2 N_{t}(a)}}\)