Bandit算法与系统推荐

在推荐系统里比较经典的问题，就是EE和用户冷启动问题

什么是EE，两个单词的简称，分别是exploit和explore
前者代表挖矿收获，后者代表探险探测。对应到软件里，一个新来的用户我们对他的兴趣一无所知，我们就要来挖掘他的兴趣（这就叫做explore），然后投其所好的给他喂他喜欢的东西（exploit）。但是老是吃同一个东西也不行啊，吃腻了怎么办？这时还需要再继续探索他其它的兴趣(explore)，然后再喂他喜欢的东西(exploit)。

冷启动
就是说我们软件面对一个新用户时，一维不知道他的喜好，应该采取怎样的步骤呢？其实很简单，就是前面说的explore，但是explore是有技巧的，Bandit算法就是解决冷启动的。

那么什么是bandit算法呢？
用分类或者Topic来表示每个用户的兴趣，也就是MAB问题中的ARM，我们通过几次实验，来探测出用户对每个Topic的兴趣。如果用户对某个Topic感兴趣（用户提供了显示或者隐式的防窥），就表示我们得到了收益，如果推荐给了它不感兴趣的Topic，推荐系统就表示遗憾(regret)。如此经历“选择-观察-更新-选择“的循环，理论上最终能得到用户真正感兴趣的Topic。

bandit算法的核心问题是：错误的选择到底有多大的遗憾？以及如何减少遗憾。
遗憾积累：衡量遗憾的算法：在解决躲避问题上的效果？
Rt = sum(Wopt-Wb(i)) i=[1,T]
= Tw* - sum(Wb(i)) i=[1,T]

Wb(i) 是选择第i只臂的期望收益，W* 是所有臂中最佳的那个，但是关键问题是这个最佳并不知道，所以要依靠Bandit算法