MAB问题

Wiki定义

- A Problem in which a fixed limited set of resources must be allocated between competing (alternative) choices in a way that maximizes their expected gain, when each choice's properties are only partially known at the time of allocation, and may become better understood as time passes or by allocating resources to the choice.[1]

- 经典的强化学习算法（Reinforcement Learning(RL)），用于处理Exploration-Exploitation（EE） trade-off dilemma。

- 名字来源于casino中赌博机slot machine（or one armed bandit)

一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么每次该选择哪个老虎机可以做到最大化收益呢？这就是多臂赌博机问题。[2]

- MAB问题也在stochastic scheduling领域范畴中。Stochastic scheduling problems can be classified into three broad types: problems concerning the scheduling of a batch of stochastic jobs, multi-armed bandit problems, and problems concerning the scheduling of queueing systems.

基本问题

1. 有K台machine，每次选取其中一台pull the lever，该machine提供一个random的reward，每一台machine的reward服从特定的概率分布。

2. 一个gambler有N次lever pulls的机会，他的目标是使得回报reward最大化，那么他要确定这N次pull 的arm的顺序。显然，作为一个聪明的赌徒，他会记录下每一次得到的reward，试图找出能给出最大reward的那台machine，尽量多次数的去pull这台machine 的arm。

3. 对于每一轮选择，主要面对的问题是Exploitation-Exploration.

Exploitation: to pull the arm with Highest expected payoff OR

Exploration: to play other machines to get more information about the expected payoffs of them.

4. 得到的收益称为reward，一般假设为伯努利分布，即0或1。得到的收益与真实的最大收益（上帝视角，假设一开始就知道哪个payoff最大，那我肯定pull那个arm）之间的差值称为regret。

应用场景

Online service that benefits from adapting the service to the individual sequence of requests, Ad placement, website optimization, and packeting route.

1. 推荐系统领域，领域有两个经典问题：EE问题和用户冷启动问题。[2]

EE问题：上面提到过的exploit-explore问题；比如已知某用户对A产品感兴趣，那么在大多数时间要给他推送A的链接才能赚钱，这就是exploit；但是为了赚更多的钱，就需要知道他还对哪些产品感兴趣，那么在有些时候就可以尝试一下给他推送B，C，D，E等选择看用户的反应，这就是explore。

用户冷启动问题：面对新用户时如何用尽量少的次数，猜出用户的大致兴趣。[2]

2. 临床测试场景clinical trials

假设有一批用于治疗某种疾病的新药需要进行测试，目标肯定是在尽量少的测试体上进行尝试，找出效果最好的那一种然后应用于其他病患。由于测试需要等待并观察，尽早找出效果最好的药物类型也有利于救助更多的病患；同时，该方法也有助于减少承受不良药物副作用的测试体数量/增加病患存活率。[3]

Algorithms for MAB

问题类型

在讨论算法之前，首先要明确几种bandit model。根据对于reward过程的不同假设，主要可以分为三种类型：Stochastic ，Adversarial and Markovian。几种经典的策略与之对应， UCB algorithm for the stochastic case， Exp3 randomized algorithm for theadversarial case， so-called Gittins indices for the Markovian case.[4]

本文目前主要讨论Stochastic bandits problem（另外两种待以后补充），以下为[4]对其定义：

Stochastic bandits

常用算法

针对MAB问题常用的基本算法有： $\epsilon$ -greedy， Boltzmann exploration(Softmax), pursuit, reinforcement comparisonm, UCB1, UCB1-Tuned, Thompson Sampling(TS) [3]

符号说明：

arm $i = 1,2,3,...,K$ 共K个arm

round $t = 1,2,3,...,N$ 共N次机会

$\hat{u_i}(t)$ ： The empirical mean of arm i after t rounds

$p_i(t)$ : The probability of picking arm i at round t

$\epsilon$ -greedy

核心思路：以概率在所有K个arm中随机选取一个(Explore); 以（1- $\epsilon$ ）概率选取具有highest empirical mean的arm。

实际操作：每一轮在[0，1]生成一个随机数，如果小于\epsilon，则在K个arm中随机选一个；否则选平均收益最大的那个（如果多个则随机选一个）。

- 为了不记录n歌reward，更高效的办法是对均值做增量式计算，每一轮只记录两个变量：已经尝试的次数和最近的平均reward。

epsilon-greedy

对于constant \epsilon，regret的bound是linear的。

如果\epsilon随着时间减小，regret的bound是poly-logarithmic的。

若摇臂奖赏的不确定性较大，比如概率分布较宽，则需要更多的explore，对应较大的\epsilon。若摇臂奖赏的不确定性较小，比如概率分布集中，则少量的尝试就能很好的近似真实奖赏，只需要较小的\epsilon。

通常让epsilon为一个较小的数如0.1或0.01。不过，如果尝试次数很大，在一段时间后各个arm的奖赏都能很好近似出来，不需要再explore，这种情况下可以让epsilon随时间逐渐减小，例如 $\epsilon = 1 \sqrt{t}$

Boltzmann Exploration(Softmax)

核心思路：选取某个arm的概率与它的平均reward有关。Softmax方法基于Boltzmann分布选取arm。

Softmax

随机系数 $\tau$ ，称为“温度”。 tau越小则平均奖赏高的摇臂被选取的概况更高；趋于0的时候-〉仅利用exploit；趋于无穷大的时候-〉仅探索explore

Pursuit Algorithms

核心思路：每次依据平均实验回报对选取各个arm的概率独立进行更新。

Pursuit Algorithmxs

Reinforcement Comparison

与Pursuit Algorithm类似，RC方法的行为也不是直接由empirical means计算而来。该方法同时还保留一个平均预期回报（average expected reward） $\bar{r}(t)$ ，将平均回报和预期回报作比较。

- 如果 empirical mean 〉average expected reward，选该arm的概率上升。

- 如果empirical mean〈 average expected reward，选该arm的概率下降。

- 对于arm i 存在偏好（preference） $\pi_i(t)$ , 每一轮preference会根据结果进行更新：

Update Process

每一轮各arm的概率计算：

Reinforcement Comparison

Upper Confidence Bounds(UCB)

核心思路：利用目前的收益均值+置信区间来对arm进行选择，play的次数越多，第二项置信区间就越小，目前的收益均值就越可信。最后稳定选择的就是收益大，并且置信区间小的那个arm。

该系列中最简单的算法UCB1：

含有参数： $\hat{u}_i(t)$ (The empirical mean of arm i after t rounds

$n_i(t)$ the number of times that arm i has been played after t rounds

1、初始化: 所有arm都被play一次。

2、选择arm j(t)：

UCB1

3、观察选择结果，更新t和ni。其中加号前面是这个臂到目前的收益均值，后面的叫做bonus，本质上是均值的标准差

这个公式反映一个特点：均值越大，标准差越小，被选中的概率会越来越大。被选次数较少的臂虽然可能均值不大，但根号那一项会比较大，也会得到试验机会。

UCB1 的bound：

Bound of UCB1

UCB1-Tuned

将每个arm的variance引入了考虑

Thompson Sampling(TS)

核心思想：[2]

1. 假设每个arm产生收益的概率p符合 Beta（wins，lose）分布，两个参数wins和lose。

2. 每个arm 维护（maintain）一对beta分布的参数。每次实验选一个arm摇一下，有收益该arm的wins+=1 ，否则 lose+=1

3. 每次选arm的方式：用每个arm的beta分布产生一个随机数b，选择所有arm产生的随机书最大的那个arm去摇。

import numpy as np

import pymc

#wins 和 trials 是一个N维向量，N是赌博机的臂的个数

choice = np.argmax(pymc.rbeta(1 + wins, 1 + trials - wins))

wins[choice] += 1

trials += 1

Beta分布：[5]

beta（a，b）有a和b两个参数，两个参数决定了分布形状。

a+b的值越大，分布曲线就越集中，反之则越疏远（两边大中间小）

当a/(a+b)的值越大，分布集中位置的中心越靠近1，反之越靠近0，这样产生的随机数位置也相应更容易靠近1或0

因此，Beta分布总体有三种情况，曲线很窄靠近1、曲线很窄靠近0、曲线很宽

由此，若把Beta分布的参数a看做推荐后得到用户点击的次数，把b看做未得到用户点击的次数，如下：

取出每一个候选对应的a和b

为每个候选用a和b作为参数，用Beta分布产生一个随机数

按照随机数排序，输出最大值对应的候选

观察用户反馈，如果用户点击则将对应候选的a增加1，反之b增加1

因此在推荐系统中，为每个用户都保存一套参数，每个用户对应每个物品都保存一份a和b

- 为什么有效？

如果候选被选中次数很多，那么a+b分布变窄，换句话说这个候选的收益已经确定，用它产生随机数，基本就在分布的中心位置附近，接近这个分布的平均收益

如果一个候选不但a+b很大，且a/(a+b)也很大，那么就是一个好的候选项，平均收益很好，每次选择占据优势，就进入利用阶段，反之则几乎再无出头之日

如果一个候选项的a+b很小，分布很宽，就是没有给充分的探索次数，此时不能确定好坏，那么这个较宽的分布有可能得到一个较大的随机数，在排序时被优先输出，给予次数做探索

关于Regret，Expected regret，Pseudo-regret：

[Notes]Regret Analysis of Stochastic and Nonsto... - 简书

小白都能看懂的softmax详解 - bitcarmanlee的博客 - CSDN博客

bandit算法原理及Python实现 - 新颜_USTC - CSDN博客

Contextual Bandit算法在推荐系统中的实现及应用 - 知乎（比较详细介绍了LinUCB的思想和实现）

在线学习(MAB)与强化学习(RL)[1]：引言 - 知乎

这个系列太值得读了！从整体框架到细节，还有各种资源！比之前看到的都好多了！

Reference

[1] https://en.wikipedia.org/wiki/Multi-armed_bandit

[2] Bandit算法与推荐系统： https://blog.csdn.net/heyc861221/article/details/80129310

[3] Kuleshov，Precup. Algorithms for the multi-armed bandit problem. Journal of Machine Learning Research.

[4] Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit

[5] https://blog.csdn.net/lyx_yuxiong/article/details/81237416