Bandit 算法与推荐系统

0. 导语

推荐系统里面有两个经典问题：EE 问题和冷启动问题。前者涉及到平衡准确和多样，后者涉及到产品算法运营等一系列东西。bandit 算法是一种简单的在线学习算法，常常用于尝试解决这两个问题，本文为你介绍基础的 bandit 算法及一系列升级版，以及对推荐系统这两个经典问题的思考。

1. 什么是 bandit 算法

1.1 为选择而生

我们会遇到很多选择的场景。上哪个大学，学什么专业，去哪家公司，中午吃什么，等等。这些事情，都让选择困难症的我们头很大。那么，有算法能够很好地对付这些问题吗？

当然有！那就是 bandit 算法！

bandit 算法来源于历史悠久的赌博学，它要解决的问题是这样的 1：

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

怎么解决这个问题呢？最好的办法是去试一试，不是盲目地试，而是有策略地快速试一试，这些策略就是 bandit 算法。

这个多臂问题，推荐系统里面很多问题都与他类似：

1. 假设一个用户对不同类别的内容感兴趣程度不同，那么我们的推荐系统初次见到这个用户时，怎么快速地知道他对每类内容的感兴趣程度？这就是推荐系统的冷启动。

2. 假设我们有若干广告库存，怎么知道该给每个用户展示哪个广告，从而获得最大的点击收益？是每次都挑效果最好那个么？那么新广告如何才有出头之日？

3. 我们的算法工程师又想出了新的模型，有没有比 A/B test 更快的方法知道它和旧模型相比谁更靠谱？

4. 如果只是推荐已知的用户感兴趣的物品，如何才能科学地冒险给他推荐一些新鲜的物品？

这些问题本质上全都是关乎如何选择。只要是关于选择，都可以简化成一个多臂赌博机问题，毕竟小赌怡情嘛，人生何处不赌博。

Bandit 算法与推荐系统