Contextual Multi-armed Bandit算法学习笔记

2018-01-02

1. multi-armed bandit问题定义

multi-arm-bandit

多臂老虎机问题的定义如下：
1. 一排K个老虎机$a_i\{i=1,2,…,K\}$；
2. 每个老虎机对应有回报$r_i\{i=1,2,…,K\}$，事先并不知道；
3. 在每一个时间t拉动一个老虎机会产生一个回报$r_{t}$；
4. 目标：根据特定的策略选择$a$，从而最小化累计遗憾值$L_{T}=E[\sum \limits_{\tau=1}^{T}r^{\star}-r_{\tau}]$。这里的$r^{\star}$是最优策略产生的回报。这里的最小化累积遗憾值相当于最大化累积回报值。
5. 这里就会产生一个强化学习中经典的exploration&exploitation问题，即每次贪婪地选择当前最优回报值的臂，还是探索潜在的新臂以期获得更高价值。
6. 常见场景：推荐系统中的冷启动问题、广告系统中的广告选择、金融衍生品设计
针对这里的策略选择方法，Richar Sutton在《Reinforcement Learning: An Introduction》一书中提到了如下contextual free的方案:
- $\epsilon-greedy$: 每一次以概率$\epsilon$选择当前最优策略，以概率$1-\epsilon$选择其他策略。这里的$\epsilon$可以灵活的控制模型的偏好程度。但这样做没有利用到探索各个臂时获得的信息，仍然不做区分的exploration效果不佳。
- UCB(Upper Confidence Bound): 采取一种乐观的态度，根据每个臂的预期回报的不确定性的上界来选择。对于每个臂尝试的次数越多，预期回报的置信区间越窄；某个臂的尝试次数越少，置信区间越宽。对于某个臂$a_{i}$，其期望回报上界为$\bar{x}_{i}=\sqrt{\frac{2lnn}{n_{i}}}$，$\bar{x}_{i}$为臂$i$的平均回报，$n_{i}$为臂$i$的选择次数，$n$为总的选择次数。UCB不需任何参数，需要遍历所有的臂，比较耗时；并且在刚开始各个臂选择次数比较少时，结果波动比较大。
- Thompson Smapling: 采用贝叶斯思想，每个臂有一个beta(win, lose)分布来估计产生回报的概率；不断试验，每次选一个臂，有回报则win增加1，否则lose增加1，不断调整beta分布的参数。每次选择臂时，每个分布随机产生一个数b，然后根据最大的b选择相应的臂。

2. contextual multi-armed bandit

每个arm包含特定的随时间而变化的上下文特征$x_{t}$，并且其回报$r_{t}$和上下文特征$x_{t}$直接相关，即存在一个函数$f$，使得$r_{t}=f(x_{t})$。这里的$x_{t}$即为实际应用中抽象出的辅助选择每个arm的特征，针对不同的互联网推荐系统场景，可产生不同的用户和物品的特征。针对不同的有关函数$f$的假设，会得到不同的模型，下面的LinUCB就是其中的典型一类。

2.1 LinUCB(Linear Upper Confidence Bound)

LinUCB由前雅虎的研究员Lihong Li(现就任微软)等在2010年提出，被应用到雅虎首页的个性化新闻推荐中。这里假设每个臂的预期回报$r_{t,a}$和上下文$x_{t}$之间存在线性关系, 即$E[r_{t,a}|x_{t,a}]=x_{t,a}^{t}\theta_{a}$.

考虑在新闻推荐的场景中，回报$r_{t,a}$可以简单的看成是否点击(0/1)，arm即为需要推荐的新闻。此时，可以给出一个对模型参数$\theta_{a}$的如下岭回归估计： $\hat{\theta_{a}}=(D_{a}^{T}D_{a}+I_{d})^{-1}D_{a}^{T}c_{a}$
这里的$D_{a}$是m个维度为d的训练样本构成的矩阵，$c_{a}$是标签向量。
此外，这里有$|x_{t,a}^{T}\hat{\theta_{a}}-E[r_{t,a}|x_{t,a}]| \leq \alpha \sqrt{x_{t,a}^{T}D_{a}^{T}D_{a}+I_{d})^{-1}x_{t,a}}$。
注意到这里arm的选择策略：$a_{t} = \arg\max\limits_{a \in A_{t}}(x_{t,a}^{T}+\alpha \sqrt{x_{t,a}^{T}A_{a}^{-1}x_{t,a}})$。
实际使用中，arm的选择通常存在一个Exploration&Exploitation的问题，这里采用的是UCB的方案，并且将置信上界的计算直接融入到模型优化中，实际算法如下图所示：

LinUCB

2.2 Hybrid LinUCB

上面的模型中各个arm的参数$\theta$互不影响，分开计算；但实际中可能有一些特征是所有arm共享的。因此，衍生出了如下模型：

$E[r_{t,a}|x_{t,a}] = z_{t,a}^{T}\beta^{*}+x_{t,a}^{T}\theta_{a}^{*}$

这里的参数$\beta^{*}$由所有的arm共享。实际算法如下图所示：

Hybrid-LinUCB

2.3 LinUCB算法的优点

考虑了上下文特征，可以处理动态的推荐资源池，在资源池增大时，效果更好。
收敛速度比UCB快，但需要合适的特征工程方案，这是实际使用中工程人员需要发挥的地方。

3. 参考资料

[1] A Contextual-Bandit Approach to Personalized News Article Recommendation
[2] 推荐系统的EE问题及Bandit算法
[3] Bandit算法与推荐系统