假想一个风投他想着他的收益最大化,这时他总会面临一个两难: 何时去投资那些已经成功的公司,何时去投资那些还没有成功但具有很大潜力的公司.这里套用股市里的一句话:收益总是伴随着风险的. 一个成功的风投必须处理好这个勘探-开发两难(exploration and exploitation tradeoff): 勘探过多意味着不能获得较高的收益,而开发过多意味着可能错过更高回报的机会.

在现实生活和商业中我们都会面对这种两难,而且没有正确的答案教你怎么去做–可能的原因是我们对世界的认识不够清楚(世界太复杂,我们太年轻!!!). 但是在数学领域, 这个问题已经被研究过,被称为多臂赌博机问题(multi-armed bandit problem),也称为顺序资源分配问题(sequential resource allocation problem). 它被广泛应用于广告推荐系统,源路由和棋类游戏中.

描述

假设有$K$个老虎机并排放在我们面前,我们首先给它们编号${1,…i,…,K}$,每一轮,我们可以选择一个老虎机来按,同时记录老虎机给出的奖励. 假设各个老虎机不是完全相同的,经过多轮操作后,我们可以勘探出各个老虎机的部分统计信息,然后选择那个看起来奖励最高的老虎机. 在多臂赌博机中,我们把老虎机称为臂.

这里有两个问题:

奖励以什么方式产生

我们可以想见有很多种方式产生这种奖励

  • 随机式(stochastic bandit): 臂$i$的奖励服从某种固定的概率分布$D_i$
  • 对抗式(adversarial bandit): 赌场老板使坏,会动态调整臂的奖励,比如让你选的臂的奖励很低,但是其它未选的臂奖励变高.注意这里赌场老板不能也不会使全部臂的奖励变为0,因为这样会使我们无法得到奖励,这时我们体验到的是任何策略都是无差别的.
  • 马尔可夫式(Markovian bandit): 臂奖励由马尔可夫链定义.

如何测量策略的好坏

简单的以总奖励作为测量策略好坏的标准是不切实际的. 所以我们定义*遗憾(regret)*作为策略好坏的指标,指的是我们可以达到的最理想总奖励与实际得到的总奖励.

随机式(stochastic bandit)

在本节中只讨论随机式多臂赌博机问题及UCB策略集,并假定各臂给出的奖励$X_i$是归一化到$[0,1]$之间的随机变量,其期望用$\mu_i$表示. 在第t轮的奖励用$X_{i,t}$表示.

同时,$X_i$和$X_j$独立,$X_{i,t}$ 和$X_{i,s}$独立.

我们把该问题数学化:

定义随机式多臂赌博机: 已知参数: 臂数$K$,轮数$T\ge K$ 未知参数: 在[0,1]区间上的各臂分布$D_i$ 过程: 每轮

  1. 从${1,…,K}$中选择一个臂$i_t$.
  2. 该臂独立地给出服从$D_{i_t}$的奖励

同时我们需要定义策略的好坏指标–累积遗憾:

定义: 给定一个策略$A$和一个动作集${1,…i,…,K}$,在$T$时间后 $A$的累积遗憾是最佳臂的期望奖励与$A$的期望奖励之差.

在上述随机变量$X_i$中,我们总可以找到一个期望最大的臂,使得: $$ \mu^*=\max_{1\le i\le K} \mu_i $$ 同时我们可以定义 $$ i^*=\sigma(1) $$ 其中$\sigma()$表示一个从大到小排序的置换.

一个选择策略$A$在T轮后获得的奖励定义为: $$ G_{A}(T)=\sum_{t=1}^T X_{i_t,t} $$ 所以,策略$A$的累积遗憾$R_A(T)$为: $$ R_A(T)=G_{i^*}(T)-G_A(T) $$ 其中$G_{i^*}(T)$为理想策略所获得的收益,该策略表示我们已知那个期望最大的臂并总选择那个臂.

所以一个好的策略是使 $$ \mathbb{E}(R_A(T))=\mathbb{E}(G_{i^*}(T))-\mathbb{E}(G_A(T))=\mu^*T-\mathbb{E}(G_A(T)) $$ 尽可能小.

UCB1算法

这里我们介绍一个最常见的bandit策略–UCB1算法,该算法的精神被认为是_乐观地面对不确定性_:我们首先猜测各臂可能给出的奖励,然后选择那个最高臂,如果实际的奖励较少,我们会尽快地降低对该臂的猜测,反之,我们就尽量多选择这个臂. 这里面的猜测,其实就是对各臂的奖励建立了一个指数,通过动态调整这个指数,我们最终将确定那个期望奖励最高的臂.

UCB1算法: 在前$K$轮,每臂各选择一次, 在$t=K,K+1…$轮:

  1. 选择指数$I_i$最大的臂,其中$I_i=\bar{x}_i+\sqrt{2\frac{\log t}{n_i}}$,其中$\bar{x}_i$是均值,$n_i$是臂$i$当前累积被选择的次数
  2. 记录获得的奖励,并更新$\bar{x}_i$和$n_i$

当UCB1算法被执行时,我们可以确定如下定理,其中$\Delta_i=\mu^{*}-\mu_i$:

定理: UCB1累积遗憾的期望不超过: $$ 8\sum_{i:\mu_i\lt \mu^{*}}\frac{\log T}{\Delta_i}+(1+\pi^2/3)(\sum_{j=1}^K \Delta_j) $$

定理的证明我就不在这里列出了,具体可以参考《Finite-time Analysis of the Multiarmed Bandit Problem》.

我们发现UCB1算法的累积遗憾期望是$O(\log T)$的,这是不是就足够了呢? 当然不是,如果最坏情况下的累积遗憾过高,该算法其实是没有意义的.

UCB1最坏情况

定理: 最坏情况下的UCB1累积遗憾不超过$O(\sqrt{KT\log T})$

我们通过累积遗憾期望函数分析对其进行简单的证明: 首先,我们对累积遗憾期望进行偏微分,得到 $$ \frac{\partial R}{\partial \Delta_i}=\frac{8\log T}{\Delta_i^2}+1+\frac{\pi^2}{3} $$ 让它等于0,则有$\Delta_i=\sqrt{\frac{8\log T}{1+\pi^2/3}}=O(\sqrt{\log T})$,但是这时是$R$的一个极小值点$R=O(K\sqrt{\log T})$.同时,如果我们让$\Delta_i$尽可能小的话,$R$将变得任意大,但是这时所有的奖励都差不多,所以些时还是极小值. 如果我们让$\Delta_i$等于1的话,我们还是得到$R=O(K\sqrt{\log T})$

其实,如果我们让$\Delta_i=\Delta$,这时,累积遗憾期望将会是$\Delta T$,代入公式可得最坏情况下的累积遗憾为$O(\sqrt{KT\log T})$

NEXT

下节我会对随机式bandit进行理论上的描述和其它UCB算法的总结.