2. Multi-armed Bandits

2.1 A $k$-armed Bandit Problem

Exploiting
Exploring

We care only about balancing them at all.

我们更关心要不要去平衡exploiting && exploring

2.2 Action-value Methods

2.2.1 sample-average

Natural way：计算实际收益的平均值，估计动作的价值

$Q_t(a) = \frac { \text { sum of rewards when } a \text { taken prior to } t } { \text { number of times } a \text { taken prior to } t } = \frac { \sum ^ { t - 1 } _ { i = 1 } R_i \cdot \mathbb { 1 }_{ A_i = a } } { \sum^{ t - 1 }_{ i = 1 } \mathbb{ 1 }_{ A_i = a } }$

$\text { sum of rewards when } a \text { taken prior to } t$：$t$时刻前通过执行动作$a$得到的收益总和
$\text{ number of times } a \text{ taken prior to } t$：$t$时刻前执行动作$a$的次数
$\mathbb{ 1 }_{ \text { predicate } }$：随机变量，predicate为真时取1，反之为0

分母为0时直接定义为$ Q_t( a ) = 0$

By the law of large number，分母趋于$\infin$，$Q_t( a )$收敛到$q_*( a )$

Which is called ==sample-average==.

2.2.2 $\varepsilon - $Greedy

优点：

足够长的采样中，每个动作都会被无限次采样
选择最优动作的概率收敛到大于$1 - \varepsilon$，接近确定性选择

为什么大于？(get)

在每一步的选择中：
- 每个动作被选择的概率为$\varepsilon / |A|$
- 选择某个贪心动作的概率为$1 - \varepsilon$
  - 即某个贪心策略被选中的概率为$1 - \varepsilon + \varepsilon / |A|$

2.3 The 10-armed Testbed

Reduce $\varepsilon$ over time to get the best of both high and low values
$\varepsilon - $greedy对于greedy的优势与任务有关
- 对于一个确定性任务，greedy更好
- 对于非确定性、非平稳的任务，显然$\varepsilon - $greedy更好

2.4 Incremental Implementation

$\begin{aligned} Q_{ n + 1 } & \dot{ = } \frac{ R_1 + R_2 + \cdots + R_{ n - 1 } } { n - 1 } \\ & = \frac{ 1 }{ n } \sum_{ i = 1 }^n R_i \\ & = \frac{ 1 }{ n } \left( R_n + \sum_{ i = 1 }^{ n - 1 } R_i \right ) \\ & = \frac{ 1 }{ n } \left( R_n + ( n - 1 ) \frac{ 1 } { n - 1 } \sum_{ i = 1 }^{ n - 1 } R_i \right) \\ & = \frac{ 1 }{ n } \left( R_n + ( n - 1 ) Q_n \right) \\ & = \frac{ 1 }{ n } \left( R_n + n Q_n - Q_n \right) \\ & = Q_n + \frac{ 1 }{ n } \left[ R_n - Q_n \right] \end{aligned}$

General form

$\text{NewEstimate } \leftarrow \text{ OldEstiamate + StepSize [ Target - Old Estimate]}$

$\text{[ Target - Old Estimate]}$：error in the estimate
$\text{Target}$：“目标”，存在噪声
$\text{StepSize}$：Change from time step to time step. Action $a$ 对应的第$n$个收益的步长为$\frac{1}{n}$，将步长记为$\alpha_t(a)$

Simple bandit algorithm
Initialize, for $a = 1$ to $k$:
$Q(a) \leftarrow 0$
$N(a) \leftarrow 0$
Loop forever:
$A \leftarrow\left\{\begin{array}{lll}\operatorname{argmax}_a Q(a) & \text { with probability } 1-\varepsilon & \text { (breaking ties randomly) } \\ \text { a random action } & \text { with probability } \varepsilon \end{array}\right.$
$R \leftarrow bandit(A)$
$N(A) \leftarrow N(A) + 1$
$Q(A) \leftarrow Q(A) + \frac{1}{N(A)}[R - Q(A)]$

2.5 Tracking a Nonstationary Problem

对于非平稳问题，give more weight to recent rewards than to long-past rewards.

Most popular way：use a constant step-size parameter
对于公式(2):

$\begin{aligned} Q_{n + 1} & \dot{=} Q_n + \alpha[R_n - Q_n] \\ & = \alpha R_n + (1 - \alpha) Q_n \\ & = \alpha R_n + (1 - \alpha) [\alpha R_{n - 1} +(1 - \alpha) Q_{n - 1}] \\ & = \alpha R_n + (1 - \alpha) \alpha R_{n - 1} + (1 - \alpha)^2 Q_{n - 1} \\ & = \alpha R_n + (1 - \alpha) \alpha R_{n - 1} + (1 - \alpha)^2 R_{n - 2} + \\ & \cdots + (1 - \alpha)^{n - 1} \alpha R_1 + (1 - \alpha)^n Q_1 \\ & = (1 - \alpha)^n Q_1 + \sum^n_{i = 1}{\alpha(1 - \alpha)^{n - i}R_i} \end{aligned}$

此时$Q_{n + 1}$成为过去收益 && 初始估计值$Q_1$的加权平均

加权和为$(1 - \alpha)^n + \sum^n_{i = 1}{\alpha(1 - \alpha)^{n - i}} = 1$

权值递减

如果$\alpha = 1$，则所有加权都赋值给$R_n$

如果$\alpha_t(a) = \frac{1}{n}$就是采样平均法

==Stochastic approximation==: $\alpha_t(a)$必须满足以下条件，才能保证$Q_n$收敛到真值

$\begin{aligned} \sum^{\infty}_{n = 1} \alpha_n(a) & = \infty \\ \sum^{\infty}_{n = 1} \alpha^2_n(a) & < \infty \end{aligned}$

条件1：保证有足够大的步长，最终克服任何初始条件和随机波动
条件2：步长最终变小，保证收敛

$\alpha_t(a) = \frac{1}{n}$满足两个条件

收敛很慢，需要大量调试，在理论中常用，在实际应用中很少

常数步长$\alpha$不满足

即永远无法完全收敛，而是随着近期收益变化（这正是非平稳环境的需要）

Exercise 2.4:

$\begin{aligned} Q_{n + 1} & = Q_n + \alpha_n[R_n - Q_n] \\ & = \alpha_n R_n + (1 - \alpha_n)Q_n \\ & = \alpha_n R_n + (1 - \alpha_n)[\alpha_{n - 1} R_{n - 1} + (1 - \alpha_{n - 1}) Q_{n - 1}] \\ & = \alpha_n R_n + (1 - \alpha_n) \alpha_{n - 1} R_{n - 1} + (1 - \alpha_n)(1 - \alpha_{n - 1}) \alpha_{n - 2} R_{n - 2} + \\ & + (1 - \alpha_n)(1 - \alpha_{n - 1})(1 - \alpha_{n - 2})Q_{n - 2} \\ & = \alpha_n R_n + (1 - \alpha_n) \alpha_{n - 1} R_{n - 1} + (1 - \alpha_n)(1 - \alpha_{n - 1}) \alpha_{n - 2} R_{n - 2} + \\ & \cdots + \prod^{n}_{i = 2}(1 - \alpha_i) \alpha_1 R_1 + \prod^n_{i = 1}(1 - \alpha_i) Q_1 \\ & = \prod^n_{i = 1} (1 - \alpha_i) Q_1 + \sum^n_{i = 1}\alpha_i R_i \prod^n_{k = i + 1}(1 - \alpha_k) \end{aligned}$

2.6 Optimistic Initial Values

An useful trick!

从统计学的角度来说，选择的初始值$Q_0$都是有偏的

如果选择采样平均法，当所有动作都被至少选择一次之后，偏差消失
对于常数步长$\alpha$来说，偏差只会减小，不会消失

初始action-value的选择，提供了一种试探方式

假设在10-armed平台中，设置所有的初始值都为$+5$，而$q_*(a)$是按照正态分布选择的，因此无论选择哪个，reward都会小于当前收益，所以会转向其他动作

在平稳问题中很有效，只有暂时的试探驱动力。实际上，所有关注初始值的方法，对非平稳问题的效果很一般。

2.7 Upper-Confidence-Bound Action Selection

UCB置信上界

2.8 Gradient Bandit Algorithms

2.9 Associative Search（Contextual Bandits）

2.10 Summary

Greedy：exploiting && exploring，在控制问题中对应的是辨识（或估计）与控制之间的冲突，称为对偶控制问题，即在控制具有不确定性的系统时，需要同时解决辨识和控制两个问题
Gradient