强化学习系列案例 | 多臂老虎机问题策略实现

原创

数据酷客

修改于 2020-04-22 18:05:40

4.3K0

修改于 2020-04-22 18:05:40

文章被收录于专栏：数据科学人工智能

查看本案例完整的数据、代码和报告请登录数据酷客（cookdata.cn）案例板块。

1.强化学习介绍

1.1 学习模式

试想这样一个问题：一只狗如何学会叼住飞盘？

人类的训练过程：当飞盘抛向空中后，如果狗叼住飞盘，此时给予狗一块肉作为奖励；如果狗没有叼住飞盘，就不给肉；狗的目标是希望自己得到更多的肉，于是当飞盘飞出后狗越来越展现叼住飞盘的动作以得到更多的肉；通过这样的过程，狗便学会了叼飞盘的动作

在人工智能领域中强化学习就是这样的学习模式，它是一种用于智能体在与环境交互过程中进行学习的方法，强化学习过程主要包含五个元素：智能体(agent)、环境(environment)、状态(state)、动作(action)、奖励(reward)。某一时刻下，智能体处于某一状态，执行一个动作后，环境接收到动作，促使智能体进入下一个状态，同时反馈奖励，智能体的目的是为了最大化累积奖励，根据奖励的多少调整动作以获得更大的奖励。

1.2 形式化为MDP问题

已经了解了强化学习模型的基本元素和模式，在计算机中通常使用马尔可夫决策过程(Markov Decision Process,MDP)将其转化为数学问题，然后进行求解，MDP通常定义为四元组(𝑺, 𝑨,𝑷,𝑹)：

2.多臂老虎机问题(Multi-Armed Bandit,MAB)

多臂老虎机问题(Multi-Armed Bandit,MAB)是强化学习的经典问题之一，常作为强化学习领域的入门问题，多臂老虎机(Multi-Armed Bandit)问题描述如下：

老虎机有K个摇臂，每个摇臂以一定的概率吐出金币，且概率是未知的
玩家每次只能从K个摇臂中选择其中一个，且相邻两次选择或奖励没有任何关系
玩家的目的是通过一定的策略使自己的奖励最大，即得到更多的金币

强化学习的核心要点是将待解决的问题转化为MDP(马尔可夫决策过程)问题，MAB问题是一个退化的MDP问题，它的MDP四元组(𝑺, 𝑨,𝑷,𝑹)表示如下：

通过怎样的策略能够使玩家在一定时间内得到的金币更多呢，这样的问题可以通过强化学习的方法解决，强化学习的重点之一是如何与环境交互、产生有足够价值的数据，MAB问题可以帮助我们更好地理解产生数据的方法,下边介绍四种强化学习策略实现多臂老虎机问题。

首先，设置本案例中摇臂个数为5，并规定每个摇臂的真实奖励概率。

# 设摇臂个数为5，编号为0到4
k = 5
# 每个摇臂的真实奖励概率
real_reward = [0.2, 0.4, 0.7, 0.5, 0.3]

其中2号摇臂的奖励概率最高，若我们一直操作这个摇臂进行1000次游戏，则最终期望奖励是700，我们可以将这个数值作为我们心目中最理想的累积奖励。

3.探索利用困境(Exploration-exploitation dilemma)

在上述多臂老虎机问题中，玩家怎样知道每个摇臂获得奖励的概率呢？

在强化学习中如果每个动作对应的奖励是一个确定的值，那每个动作只需尝试一次就可以知道奖励最大的动作；
但现实中每个动作的奖励不是确定的，每个动作的奖励通常是一个概率分布，仅一次尝试并不能真实的了解动作的奖励；
因此合理的做法是需要对每个动作进行多次的尝试，最终得出每个动作平均的奖励。

但是在现实环境中，游戏的次数往往是有限的，那么在有限的尝试次数内，如何使奖励最大化？

仅探索策略：所有尝试机会平均分配给每个动作，得到每个动作奖励的近似估计。
仅利用策略：只考虑目前奖励最大的动作。

探索策略能很好估计每个动作的奖励，但较难使奖励最大，但是利用策略又仅考虑当前已知的动作，并没有很好地估计每个动作的奖励，因此如何在探索和利用中进行平衡是强化学习面临的一个问题，这边是强化学习中的“探索利用困境”。

这样的问题就好比平时吃饭，假设你家附近有10家餐馆，每天只有一次在餐馆吃饭的机会，你已经去过其中的3家。现在你要去餐馆就餐，你为了让自己吃到最好的美食，你需要选出最好的餐馆。可问题是你只知道去过的三家餐馆中哪家最好，那剩下的7家餐馆呢？

选择剩下7家餐馆的其中一个，可能还不如自己去过的餐馆好，但是也有可能比自己去过的好，那该如何选择呢？你有两种做法

探索：在自己没去过的餐馆中选择一家进行就餐，这就是探索策略
利用：去自己去过的三家中最好的那家餐馆，这便是利用策略

下边我们通过具体的算法了解强化学习如何在多臂老虎机中解决这样的问题

4.使用四种策略解决MAB问题

我们将使用四种策略并对比四种策略的效果，这四种策略分别是：随机选择、ε-greedy、Boltzmann、UCB。

4.1 随机选择

随机选择策略是解决强化学习较为简单的策略，它的核心思想是对每个摇臂操作一定的次数，然后收集每个摇臂奖励的期望，基于此选择期望最大的摇臂作为最佳摇臂，每次游戏都选择最佳摇臂进行操作，接下来实现随机选择策略，并进行1000次游戏。

import numpy as np
import pandas as pd

def random_select(N):# N为游戏次数
    
    # 初始化各摇臂期望奖励估计
    expect_reward_estimate = [0] * k

    # 初始化各摇臂操作次数
    operation = [0] * k

    # 初始化总奖励
    total_reward = 0

    for i in range(N):
        # 随机选择一个摇臂进行操作
        arm = np.random.choice(k , size=1)[0]
    
        # 收集反馈的奖励数据
        arm_reward = np.random.binomial(1, real_reward[arm], size=1)[0]
    
        # 更新期望奖励估计
        expect_reward_estimate[arm] = (expect_reward_estimate[arm] * operation[arm] + arm_reward)/(operation[arm] + 1)
    
        # 更新摇臂操作次数
        operation[arm] += 1
    
        # 更新累积奖励
        total_reward += arm_reward
        
    return total_reward, expect_reward_estimate, operation

进行1000次游戏

N = 1000
total_reward,expect_reward,operation_times = random_select(N)

输出累积奖励和期望奖励估计表

print("随机选择的累积奖励：", total_reward)

# 期望奖励估计表
expect_reward_table = pd.DataFrame({
        '期望奖励':expect_reward,
        '操作次数':operation_times   
    })
expect_reward_table

通过上述结果可以看到，随机选择策略较为平均地分配操作次数给每个摇臂，累积奖励较低，距离我们理想的累积奖励相差较远。

4.2 ε-greedy

在之前的随机选择策略中并没有很好的均衡探索和利用的问题，为了解决探索利用的问题(exploration-exploitation dilemma)，下边我们尝试ε-greedy策略，它的核心思想是在游戏中设置一个探索率ε，以ε为概率进行探索，随机选择一个摇臂；以概率1−𝜀进行利用，即选择当前平均奖励最高的摇臂，其算法流程如下：

# 设定探索率
explorate_rate = 0.1

def epsilon_greedy(N, explorate_rate): # N为游戏次数
    
    # 初始化各摇臂期望奖励估计
    expect_reward_estimate = [0] * k

    # 初始化各摇臂操作次数
    operation = [0] * k

    # 初始化总奖励
    total_reward = 0

    for i in range(N):
    
        # 产生一个服从0到1之间均匀分布的随机数
        r = np.random.uniform(size=1)[0]
    
        # 选择“利用”
        if r > explorate_rate:
        
            # 选择当前最大期望奖励所对应的摇臂进行操作
            best_arm =  expect_reward_estimate.index(max(expect_reward_estimate))

        # 选择“探索”  
        else:
            
            # 随机选择摇臂进行操作
            best_arm = np.random.choice(k, size=1)[0]
    
        # 收集反馈的奖励数据
        best_arm_reward = np.random.binomial(1, real_reward[best_arm], size=1)[0]
    
        # 更新期望奖励估计
        expect_reward_estimate[best_arm] = (expect_reward_estimate[best_arm] * operation[best_arm] + best_arm_reward)/(operation[best_arm] + 1)
    
        # 更新摇臂操作次数
        operation[best_arm] += 1

        # 更新累积奖励
        total_reward += best_arm_reward    
    
    return total_reward, expect_reward_estimate, operation

使用ε-greedy策略进行1000次游戏

N = 1000
total_reward,expect_reward,operation_times = epsilon_greedy(N, explorate_rate)

print("ε-greedy策略的累积奖励：", total_reward))

# 期望奖励估计表
expect_reward_table = pd.DataFrame({
        '期望奖励':expect_reward,
        '操作次数':operation_times   
    })
expect_reward_table

上述结果可以看到，累积奖励有了明显提升，并且在1000次游戏中，80%的操作都集中在最好的2号摇臂上。下面我们设置不同的探索率，来观察累积奖是如何变化的。

import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']

# 在0到1之间生成100个探索率
explore_grad = np.arange(0.01, 1.01, 0.01)

# 在不同探索率下，ε-greedy策略的累积奖励
reward_result = [epsilon_greedy(N, i)[0] for i in explore_grad]

# 绘制折线图
plt.figure(figsize=(8, 6))
plt.plot(explore_grad,reward_result,c='deepskyblue')
plt.xlabel('探索率',fontsize=12)
plt.ylabel('累积奖励',fontsize=12)
plt.xlim(0,1)
plt.show()

由上图可以看到，累积奖励会随着探索率的增加而逐渐降低，趋近于1时变为“仅探索”。

4.3 Boltzmann

# sigma是Boltzmann的参数
sigma = 0.1

def boltzmann(N, sigma):
    
    # 初始化各摇臂期望奖励估计
    expect_reward_estimate = [0] * k

    # 初始化各摇臂操作次数
    operation = [0] * k

    # 初始化总奖励
    total_reward = 0
    
    for i in range(N):
        
        # 通过Boltzmann分布计算摇臂的奖励概率
        reward_prob = np.exp(np.array(expect_reward_estimate)/sigma)/np.exp(np.array(expect_reward_estimate)/sigma).sum()
        
        # 通过奖励概率的分布进行抽样，选择摇臂
        best_arm = np.random.choice(k, size=1, p=reward_prob)[0]
        
        # 收集反馈的奖励数据    
        best_arm_reward = np.random.binomial(1, real_reward[best_arm], size=1)[0]
        
        # 更新期望奖励估计
        expect_reward_estimate[best_arm] = (expect_reward_estimate[best_arm] * operation[best_arm] + best_arm_reward)/(operation[best_arm] + 1)
    
        # 更新摇臂操作次数
        operation[best_arm] += 1
            
        # 更新累积奖励
        total_reward += best_arm_reward    

    return total_reward, expect_reward_estimate, operation

使用Boltzmann策略进行1000次游戏

N = 1000
total_reward,expect_reward,operation_times = boltzmann(N,sigma)

print("Boltzmann策略的累积奖励：", total_reward)

# 期望奖励估计表
expect_reward_table = pd.DataFrame({
        '期望奖励':expect_reward,
        '操作次数':operation_times   
    })
expect_reward_table

上述结果可以看到，累积奖励已经十分接近我们的预期，并且在游戏中，操作基本都集中在最好的2号摇臂上，但由于对0、3、4号摇臂的操作次数较少，导致对其期望概率估计存在较大偏差。下面我们设置不同的参数sigma，来观察累积奖是如何变化的。

# 在0到1之间生成100个sigma
sigma_grad = np.arange(0.01, 1.01, 0.01)

# 得到在这100个sigma下，Boltzmann策略的累积奖励
reward_result = [boltzmann(N, i)[0] for i in sigma_grad]

# 绘制折线图
plt.figure(figsize=(8, 6))
plt.plot(sigma_grad, reward_result, c='firebrick')
plt.xlabel('探索率', fontsize=12)
plt.ylabel('累积奖励', fontsize=12)
plt.xlim(0, 1)
plt.show()

由上图可以看到，累积奖励会随着sigma的增加而逐渐降低，趋近于1时变为“仅探索”。

4.4 UCB

置信区间 (confidence interval) 可以度量估计的不确定性，可以根据一组样本求出期望的95%的置信区间，95%的置信区间表示进行100次抽样，有95个置信区间中会包含真实的期望，UCB以期望的95%的置信区间上限来进行摇臂的选择，其计算公式如下：

def ucb(N):

    # 初始化各摇臂期望奖励估计
    expect_reward_estimate = [0] * k

    # 初始化各摇臂操作次数
    operation = [0] * k

    # 初始化总奖励
    total_reward = 0

    for i in range(N):
    
        # 初始化最大置信区间上限
        max_upper_bound = 0
    
        # 遍历所有摇臂，根据UCB值选择最佳摇臂
        for j in range(k):
        
            if (operation[j] > 0):
            
                # 计算探索程度的大小
                delta_i = np.sqrt(2 * np.log(i + 1)/operation[j])
            
                # 计算UCB值
                upper_bound = expect_reward_estimate[j] + delta_i
            
            else:
            
                # 初始化UCB值
                upper_bound = 1e400
            
            if upper_bound > max_upper_bound:
            
                # 更新UCB值
                max_upper_bound = upper_bound
            
                # 选择最佳摇臂
                best_arm = j
            
        # 收集反馈的奖励数据    
        best_arm_reward = np.random.binomial(1, real_reward[best_arm], size=1)[0]
        
        # 更新期望奖励估计
        expect_reward_estimate[best_arm] = (expect_reward_estimate[best_arm] * operation[best_arm] + best_arm_reward)/(operation[best_arm] + 1)
    
        # 更新摇臂操作次数
        operation[best_arm] += 1
            
        # 更新累积奖励
        total_reward += best_arm_reward    

    return total_reward, expect_reward_estimate, operation

进行1000次游戏

N = 1000
total_reward,expect_reward,operation_times = ucb(N)

print("UCB策略的累积奖励：", total_reward)

# 期望奖励估计表
expect_reward_table = pd.DataFrame({
        '期望奖励':expect_reward,
        '操作次数':operation_times   
    })
expect_reward_table

上述结果可以看到，在1000次游戏中，70%的操作集中在最好的2号摇臂上，并且可以明显看到操作次数的多少是按照期望奖励估计的大小分配的。UCB策略在保证累积奖励的情况下，可以对每个摇臂的期望奖励进行更加准确的估计。

5. 各策略的稳定性对比

最后为了对比四种策略的效果，我们将四种策略各模拟100次，然后输出平均累积奖励，绘制出折线图，查看哪种策略是最稳定的。

# 进行模拟
random_select_simulate = [random_select(N)[0] for i in range(100)]
epsilon_greedy_simulate = [epsilon_greedy(N, 0.1)[0] for i in range(100)]
boltzmann_simulate = [boltzmann(N, 0.1)[0] for i in range(100)]
ucb_simulate = [ucb(N)[0] for i in range(100)]

print('随机选择策略的平均累积奖励：', np.array(random_select_simulate).mean())
print('ε-greedy策略的平均累积奖励：', np.array(epsilon_greedy_simulate).mean())
print('Boltzmann策略的平均累积奖励：', np.array(boltzmann_simulate).mean())
print('UCB策略的平均累积奖励：', np.array(ucb_simulate).mean())

# 绘制折线图
plt.figure(figsize=(10, 6))

plt.title('四种策略的对比',fontsize=18)

plt.plot(range(100), random_select_simulate, c='royalblue', label='random select') # 随机策略
plt.plot(range(100), epsilon_greedy_simulate, c='red', label='ε-greedy') # ε-greedy策略
plt.plot(range(100), boltzmann_simulate, c='teal', label='Boltzmann') # Boltzmann策略
plt.plot(range(100), ucb_simulate, c='g', label='UCB') # UCB策略

plt.xlabel('模拟次数', fontsize=18)
plt.ylabel('累积奖励', fontsize=18)

plt.grid(True)
plt.ylim(300, 750)
plt.legend(loc='lower right',fontsize=12)

plt.show()

从上述的折线图可以看到，随机选择策略的累积奖励最低，其它三种策略累积奖励变化相差不大，但UCB策略累积奖励波动较小，最为稳定。

6.总结

在本案例中，先介绍了强化学习和多臂老虎机问题，并通过四种不同的策略，实现了强化学习算法模拟多臂老虎机。

首先使用最简单的随机选择策略，这种方法较为平均地分配操作次数给每个摇臂，最终的效果并不理想；然后尝试使用ε-greedy策略，通过设置探索率均衡探索和利用的问题，结果发现效果明显提升，并且在1000次游戏中，80%的操作都集中在最好的2号摇臂上；接下来使用Boltzmann策略，它是根据Boltzmann分布进行摇臂的选择，结果发现最终的奖励已经非常接近理想的效果，而且在游戏中操作基本都集中在最好的摇臂上；最后使用UCB策略，结果显示操作次数是根据各摇臂奖励期望的估计分配的，这样的策略不仅能保证累计奖励，还可以对每个摇臂真实的奖励做准确的估计。在使用四种策略后，对这四种策略的稳定性进行对比，结果发现随机选择策略的效果最差，其它三种策略的累积奖励差距不大，但是UCB策略的波动更小，非常稳定。通过多臂老虎机的学习了解到强化学习的基本算法并了解不同算法的差异，为后续强化学习的实践做好基础。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

人工智能