LinUCB

• 1. UCB
• 2. LinUCB

1. UCB

上一篇文章中介绍了一种context-free的方法，$\epsilon-greedy$。

其能够很好地完成对未知商品的exploration，同时完成对奖励的exploitation。

但是在后期，假如所有的商品都已经探索完毕，并且没有新商品加进来

显然此时并不需要做exploration，$\epsilon$概率对应部分的奖励就拿不到了

在此，介绍一种新的方法，Upper Confidence Bound

这里仅简单介绍一下基本思想

假如有一个老虎机，玩了10次，奖励是2，那么可以认为其奖励均值是2，此时设定其均值的95%置信区间为[0,4]

而另一个老虎机，玩了100词，奖励均值是3，那么可以设定其均值的95%置信区间为[2.9,3.1]

UCB在此时的决策是选择置信区间上界最大的一个老虎机

很容易发现

• 对于未知商品，尽管其均值可能很低，但是由于其不确定性会导致置信区间的上界会很大，从而触发exploration
• 对于已经很熟悉的商品，如果其均值很高，会触发exploitation

UCB的难点在于如何设定置信上界，设定方法有很多种，这里不介绍

设定的方法通常会满足如下性质

• 随着迭代轮数的增长，上界会远离均值
• 随着被选择次数的增长，上界会靠近均值

2. LinUCB

上一篇文章中提到了Contextual Bandit，在Multi-Armed Bandit的基础上每次做决策时还会有一个特征向量

LinUCB是处理Contextual Bandit的一个方法，在LinUCB中，设定

\begin{align} E\left[r_{t,a}|x_{t,a}\right] = x_{t,a}^T\theta_a \end{align}

$\theta_a$是LinUCB模型的参数，维度为$d$

每个arm维护一个$\theta_a$

对于单个arm，以其前m个context向量为行向量组成的矩阵称为$D_a$

前m个reward组成的向量称为$c_a$

使用ridge regression，可以得到$\theta_a$的概率分布为高斯分布

\begin{align} \theta_a \sim N \left((D_a^TD_a + I)^{-1}D_a^Tc_a, (D_a^TD_a + I)^{-1}\right) \end{align}

为了符号简洁，令

\begin{align} \hat{\theta}_a &= (D_a^TD_a + I)^{-1}D_a^Tc_a \\ A_a &= D_a^TD_a + I \end{align}

于是$\theta_a$的概率分布可表示为$\theta_a \sim N(\hat{\theta}_a, A_a^{-1})$

于是在第t次时可以得到$x_{t,a}^T\theta_a \sim N(x_{t,a}^T\hat{\theta}_a, x_{t,a}^TA_a^{-1}x_{t,a})$，也就是$r_{t,a} \sim N(x_{t,a}^T\hat{\theta}_a, x_{t,a}^TA_a^{-1}x_{t,a})$

根据高斯分布的性质，得到置信上界后就可以使用普通UCB规则了

需要注意的是，$A_a与D_a^Tc_a$可以增量更新，于是标准流程如下

• 设定$\alpha$
• For t = 1,2,3,…
  • 对所有的arm获得本次的context向量
  • For all $a$
    • if $a$ is new
      • 设置$A_a$为单位矩阵
      • 设置$b_a$为$d$维0零向量
    • 计算$\hat{\theta}_a = A_a^{-1}b_a$
    • 计算上界
  • 选择最大上界对应的arm即$a_t$，并得到对应的$r_t$
  • 更新$A_{a_t} = A_{a_t} + x_{t,a_t}x_{t,a_t}^T$
  • 更新$b_{a_t} = b_{a_t} + r_tx_{t,a_t}$