Multi-armed bandit.
1. 模型介绍
多臂老虎机（Multi-Armed Bandit，MAB）是统计学中一个经典问题。设想一个赌徒面前有$N$个老虎机，事先他不知道每台老虎机的真实盈利情况，他如何根据每次玩老虎机的结果来选择下次拉哪台或者是否停止赌博，来最大化自己的从头到尾的收益。
❀关于多臂老虎机问题名字的来源，是因为老虎机在以前是有一个操控杆，就像一只手臂(arm)，而玩老虎机的结果往往是口袋被掏空，就像遇到了土匪(bandit)一样。
假设共有$K$台arm，进行$T$轮实验。对于第$t$轮实验，代理（agent）根据给定的策略（policy）采取行动（action）选择一台arm $a_t$，并获得奖励（reward） $r_t$。
若记最优的arm能够得到奖励$μ$，则目标是使所有实验中的累计遗憾（regret）最小化：
\[R(T) = μT-\frac{1}{T} \sum_{t=1}^{T} {r_t(a_t)}\]实际中假设状态空间有限但非常大，因此遍历所有arm是不现实的，因此需要权衡探索和利用(Exploration and Exploitation,EE)。
- 探索(Exploration)指的是每次优先选择之前没有选择过的arm；
- 利用(Exploitation)指的是优先选择已知奖励高的arm，利用当前已有的信息来最大化收益。
⚪ε-greedy 算法
当$K$台arm的reward已知或已经被估计出来时，可以通过ε-greedy算法进行搜索。
- 以$ε$的概率在$K$台arm之间等概率随机选择；
- 以$1-ε$的概率在已经探索过的arm中选择reward最高的。
⚪UCB(Upper Confidence Bound)算法
实际中$K$台arm的reward是未知的，需要进行估计。假设每台arm的reward服从某个概率分布，对reward的置信区间进行估计。
UCB算法是在利用阶段时，选择reward估计的置信上界最大的arm。
2. Contextual MAB
Contextual MAB需要结合上下文信息（context），即每台arm在每一时刻的reward是变化的。
对于第$t$轮实验，agent能够观察到当前context $x_t$，根据policy选择一个arm $a_t$，目标是使所有实验中的累计遗憾（regret）最小化：
\[R(T) = \mathop{\max}_{\pi \in \Pi} \frac{1}{T} \sum_{t=1}^{T} {r_t(\pi (x_t))}-\frac{1}{T} \sum_{t=1}^{T} {r_t(a_t)}\]⚪Disjoint Linear Model
在Contextual MAB问题中，每台arm的reward与context相关。一种简单的模型假设每台arm在第$t$轮的特征$x_{t,a}$与其奖励$r_{t,a}$呈线性关系：
\[E[r_{t,a} \mid x_{t,a}] = x^T_{t,a}θ_a\]其中参数$θ_a$可以通过岭回归等算法进行学习。
