1. 什么是MAB问题

A. 一个赌徒，进入赌场，在他面前的老虎机有多个杆，每个杆吐钱的概率都不一样。他应该拉哪几个杆才能获得最大收益呢？这就是多臂赌博机问题（Multi-armed bandit problem，K-armed banditproblem，MAB）。

B. 以下这些场景都会遇到MAB问题：

i. 新用户进入系统，如何得知他对哪个类别更感兴趣程度更高呢？

ii. 我们有若干广告库物料，如何给用户展示广告，才能获得最大收益呢？是一直展示收益最高的那个吗？

iii. 算法工程师上线了新算法，如何得知它和旧模型哪个更好而且风险可控呢？

以上都是关于选择的问题，只要是关于选择的问题，都可以简化为MAB问题。

2. 如何应对MAB问题

MAB问题在推荐系统里都可归结为EE问题（探索与利用）。EE问题的解决方案是bandit算法。Bandit算法的思想是：看看每次选择会带来多少遗憾，遗憾越少越好。计算公式：

image

Wopt代表每次选择运气好，选择了最好的选择得到的收益，WB(i)每一次实际选择得到的收益，两者差值是遗憾的量化，T次选择之后，就有了累积遗憾。

1）汤普森采样算法

原理：每次选择，每个臂都会出一个随机数（每个臂背后的概率分布是beta分布），然后按照随机数排序，输出产生最大随机数的臂对应的物品。

Beta分布特点：

• a+b的值越大，分布曲线越窄，分布越集中，产生的随机数越靠近中心位置。

• a/(a+b)的值越大，分布的中心位置越靠近1，否则越靠近0.这样产生的随机数也更容易靠近1或0.

如何将该算法应用在推荐系统中呢？

可以把beta分布的a参数看成推荐后用户点击的次数，b参数看做用户没有点击的次数。则汤普森采样过程为：

1. 取出每一个候选对应的参数a和b。

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

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

4. 根据用户反馈，用户点击则a加1，否则b加1。

2）Epsilon贪婪算法

1. 选(0,1)之间较小的数，叫epsilon（这也是算法名字的来历）

2. 每次以概率epsilon在所有候选臂中随机选一个，以1-epsilon的概率选择平均收益最大的那个臂

3）UCB算法

UCB全称Upper Confidence Bound，即置信区间上界。它为每个臂评分，选择评分最高的侯选臂。输出后观察用户反馈，更新候选臂。

image

Xj即第j个臂的平均收益，Tjt是j臂的选择次数，t是目前的总选择次数。由公式可知，一个候选被选择次数越少，Tjt越小，则它的Bonus就越大，排序越靠前。

该公式和汤普森公式共同的特点是：

a. 选择倾向那些收益好的候选

b. 对选择次数不足的给予照顾

3. 解决冷启动问题

Banit算法不仅可以用于EE问题，还可以用于冷启动问题。

1. 用分类或Topic表示每个用户兴趣，我们通过几次实验，刻画出新用户心目中对每个topic感兴趣程度。

2. 如果用户对某个Topic感兴趣，则表示我们得到了收益，如果推给他不感兴趣的Topic，推荐系统表示遗憾。

3. 当新用户来了，针对该用户，采用汤普森采样为每一个Topic采样一个随机数，排序后，输出采样值TopN的推荐item（一次选择TopN的候选臂）。

4. 然后获取用户的行为反馈，没反馈则更新对应Topic的b值，点击了则更新对应Topic的a值。

import math
import pymc
import numpy as np
import matplotlib.pyplot as plt

class Bandits:
    def __init__(self):
        self.number_of_bandits = 10 # 老虎机的个数
        self.number_of_arms = 5 # 每个老虎机臂的个数
        self.number_of_pulls = 10000 # 拉10000次臂
        self.strategies = ["random", "epsilon-greedy", "thompson", "ucb"]
        
        # epsilon参数
        self.epsilon = 0.3
        self.decay_rate = 0.999
        self.min_temp = 0.1
        
    def pick_arm(self, strategy, q_values, counts, success, failure):
        '''
        Args:
            strategy: 策略
            q_values: 每个臂的收益率
            success: 记录收益
            failure: 记录遗憾
        '''
        if strategy == "random":
            return np.random.randint(0, len(q_values)) # 随机返回0~4号杆
        elif strategy == "epsilon-greedy":
            """ 类似模拟退火，epsilon==0.1，将10%机会用在探索上，90%的机会用在开发上 """
            epsilon = max(self.epsilon*self.decay_rate, self.min_temp)
            if np.random.random() > epsilon: # 开发，一直选择收益最高的那个
                best_arms_value = np.max(q_values)
                best_arms = np.argwhere(q_values == best_arms_value).flatten()
                return best_arms[np.random.randint(0, len(best_arms))]
            else: # 探索
                return np.random.randint(0, len(q_values))
        elif strategy == "thompson":
            """ 利用beta分布选择杆 """
            sample_means = np.zeros(len(counts))
            for i in range(len(counts)):
                sample_means[i] = np.random.beta(success[i]+1, failure[i]+1)
            return np.argmax(sample_means)
            
        elif strategy == "ucb":
            """ 置信区间上界 
                q_values_ucb = 收益率 + sqrt(2*lnt/Tjt)
            """
            total_counts = np.sum(counts)
            q_values_ucb = q_values + np.sqrt(np.reciprocal(counts+0.001)*2*math.log(total_counts+1.0))
            best_arms_value = np.max(q_values_ucb)
            best_arms = np.argwhere(q_values_ucb == best_arms_value).flatten()
            return best_arms[np.random.randint(0, len(best_arms))]
        
    def plot_result(self):
        fig = plt.figure()
        ax = fig.add_subplot(111)
        # 采用不同的策略
        for st in self.strategies:
            # 10个老虎机，每个拉10000次杆
            best_arm_counts = np.zeros((self.number_of_bandits, self.number_of_pulls))
            for i in range(self.number_of_bandits):
                # 每个杆是最大收益的概率 [0.36918711, 0.20232965, 0.04067879, 0.4484904 , 0.44567583]
                arm_rand = np.random.rand(self.number_of_arms)
                # 是最大收益的杆
                best_arm = np.argmax(arm_rand)
                # 收益率是多少
                q_values = np.zeros(self.number_of_arms) # [0, 0, 0, 0, 0]
                # 统计每个拉杆的次数
                counts = np.zeros(self.number_of_arms) # [0, 0, 0, 0, 0]
                success = np.zeros(self.number_of_arms) # [0, 0, 0, 0, 0]
                failure = np.zeros(self.number_of_arms) # [0, 0, 0, 0, 0]
                
                # 拉10000次杆
                for j in range(self.number_of_pulls):
                    # 根据不同策略，选择臂a
                    a = self.pick_arm(st, q_values, counts, success, failure)
                    # 当前臂获得的收益0或1
                    reward = np.random.binomial(1, arm_rand[a])
                    # 拉杆次数统计
                    counts[a] += 1
                    # 更新收益
                    # v = v + (reward - q_values[a]) / n
                    q_values[a] += (reward-q_values[a]) / counts[a]
                    # 成功的收益
                    success[a] += reward
                    # 失败的收益
                    failure[a] += (1-reward)
                    # 随着拉杆次数增多，几乎要找到有最大收益的杆
                    best_arm_counts[i][j] = counts[best_arm] * 100.0 / (j+1)
                
            # 横纵坐标
            ys = np.mean(best_arm_counts, axis=0)
            xs = range(len(ys))
            print("st: ", st)
            ax.plot(xs, ys, label=st)
            ax.legend(loc=0)
            
        plt.xlabel('steps')
        plt.ylabel('Optimal pulls')
        plt.tight_layout()
        plt.ylim((0, 110))
        plt.show()
        
bandits = Bandits()
bandits.plot_result()

image

random采用五个杆中随机选一个杆的方式，选择到收益最高的杆的概率趋近于0.2。thompson采样能够快速找到最大收益的杆，其次是epsilon-greedy、thompson等。