为什么要学习Bandit算法？

今年上半年和Hong还有Marco一起组了个Bandit Study Group，在Multi-armed Bandit门前轻轻留了一圈，虽然没学精，但好在开了头，知道了这玩意儿是干嘛的以及我对它有没有兴趣博士论文用不用得上。

为什么要学习Bandit算法？

答：因为决策问题大多伴随着不确定性，Bandit模型可以帮助我们更好地面对不确定性带来的决策困境，作出收益最大的选择/决定。

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

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

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

于是接下来我们会面临两个问题：

1. 奖励以什么方式产生？

我们有很多种方式产生奖励，但最主要的是这三大类：

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

1. 如何测量策略的好坏

简单的以总奖励作为测量策略好坏的标准是不切实际的。所以我们定义遗憾(Regret)作为策略好坏的指标，“遗憾”指的是我们可以达到的最理想总奖励与实际得到的总奖励之差。

Referece:

1. http://mlyixi.byethost32.com/blog/?p=155
2. Lattimore, T., & Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.