发表于更新于

字数总计:1.6k阅读时长:6分钟 新加坡

强化学习-1-多臂老虎机

强化学习的笔记、理解、感悟及代码实现,仅按个人思维进行精华总结和记录，使用的教程：动手学强化学习

1
2
import numpy as np
import matplotlib.pyplot as plt

问题描述

在多臂老虎机（multi-armed bandit，MAB）问题中，K根拉杆均对应一个奖励概率**R**,从而获得对应的奖励r.目标是在在各根拉杆的奖励概率分布未知的情况下，操作T次拉杆后获得尽可能高的累积奖励。

这是一种无状态的强化学习，只存在动作和奖励。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class BernoulliBandit:
    """ 伯努利多臂老虎机,输入K表示拉杆个数 """
    def __init__(self, K):
        self.probs = np.random.uniform(size=K)  
        self.best_idx = np.argmax(self.probs)  
        self.best_prob = self.probs[self.best_idx]  
        self.K = K

    def step(self, k):
        
        if np.random.rand() < self.probs[k]:
            return 1
        else:
            return 0

方法分析

算法需要根据某种策略决定每一步选择哪根拉杆，获得尽可能高的累积奖励。最大化累积奖励等价于最小化累积懊悔（regret即每一步选择杆与最优杆的获奖概率差）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solver:
    """ 多臂老虎机算法基本框架 """
    def __init__(self, bandit):
        self.bandit = bandit
        self.counts = np.zeros(self.bandit.K)  
        self.regret = 0.  
        self.actions = []  
        self.regrets = []  

    def update_regret(self, k):
        
        self.regret += self.bandit.best_prob - self.bandit.probs[k]
        self.regrets.append(self.regret)

    def run_one_step(self):
        
        raise NotImplementedError

    def run(self, num_steps):
        
        for _ in range(num_steps):
            k = self.run_one_step()
            self.counts[k] += 1
            self.actions.append(k)
            self.update_regret(k)

可视化：

1
2
3
4
5
6
7
8
9
10
11
def plot_results(solvers, solver_names):
    """生成累积懊悔随时间变化的图像。输入solvers是一个列表,列表中的每个元素是一种特定的策略。
    而solver_names也是一个列表,存储每个策略的名称"""
    for idx, solver in enumerate(solvers):
        time_list = range(len(solver.regrets))
        plt.plot(time_list, solver.regrets, label=solver_names[idx])
    plt.xlabel('Time steps')
    plt.ylabel('Cumulative regrets')
    plt.title('%d-armed bandit' % solvers[0].bandit.K)
    plt.legend()
    plt.show()

策略选择

ϵ-贪心算法

在每一步选择拉杆时，根据历史经验选择一个均值（期望）奖励最高的拉杆，同时引入ϵ作为噪声概率进行随机选择。

  • ϵ随着各拉杆的奖励估值越来越准确，可以逐渐减小，将优于固定值的ϵ
  • 每个拉杆的期望奖励估值采用增量式更新，减少复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class DecayingEpsilonGreedy(Solver):
    """ epsilon值随时间衰减的epsilon-贪婪算法,继承Solver类 """
    def __init__(self, bandit, init_prob=1.0):
        super(DecayingEpsilonGreedy, self).__init__(bandit)
        self.estimates = np.array([init_prob] * self.bandit.K)
        self.total_count = 0

    def run_one_step(self):
        self.total_count += 1
        if np.random.random() < 1 / self.total_count:  
            k = np.random.randint(0, self.bandit.K)
        else:
            k = np.argmax(self.estimates)

        r = self.bandit.step(k)
        self.estimates[k] += 1. / (self.counts[k] + 1) * (r -self.estimates[k])

        return k

sample ：

1
2
3
4
5
6
7
np.random.seed(1)
bandit_10_arm = BernoulliBandit(10)
np.random.seed(1)
decaying_epsilon_greedy_solver = DecayingEpsilonGreedy(bandit_10_arm)
decaying_epsilon_greedy_solver.run(50000)
print('epsilon值衰减的贪婪算法的累积懊悔为：', decaying_epsilon_greedy_solver.regret)
plot_results([decaying_epsilon_greedy_solver], ["DecayingEpsilonGreedy"])
alt text

上置信界算法(upper confidence bound，UCB)

在每一步选择拉杆时，根据每根杆的期望奖励上界来选取拉杆。每根拉杆即一个动作被尝试次数越少，其不确定性越高，其期望奖励上界越大。

  • UCB算法认为每根拉杆的不确定性随着尝试次数的增加而减小，因此会更倾向于选择尝试次数较少的拉杆。

  • 不确定性度量： ,其中为当前动作的获奖概率，为动作在时间t内的尝试次数,+1是为了避免除数为0,可设p=1/t。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class UCB(Solver):
    """ UCB算法,继承Solver类 """
    def __init__(self, bandit, coef, init_prob=1.0):
        super(UCB, self).__init__(bandit)
        self.total_count = 0
        self.estimates = np.array([init_prob] * self.bandit.K)
        self.coef = coef

    def run_one_step(self):
        self.total_count += 1
        ucb = self.estimates + self.coef * np.sqrt(
            np.log(self.total_count) / (2 * (self.counts + 1)))  
        k = np.argmax(ucb)  
        r = self.bandit.step(k)
        self.estimates[k] += 1. / (self.counts[k] + 1) * (r - self.estimates[k])
        return k

sample ：

1
2
3
4
5
6
np.random.seed(1)
coef = 1  
UCB_solver = UCB(bandit_10_arm, coef)
UCB_solver.run(5000)
print('上置信界算法的累积懊悔为：', UCB_solver.regret)
plot_results([UCB_solver], ["UCB"])
alt text

汤普森采样算法

汤普森采样算法（Thompson Sampling，TS）是一种基于概率采样的强化学习算法。它通过对每个动作的奖励分布进行采样，从而估计出每个动作的概率分布，并根据这些概率分布进行动作选择。通常用 Beta 分布对当前每个动作的奖励概率分布进行建模

  • 汤普森采样是一种计算所有拉杆的最高奖励概率的蒙特卡洛采样方法
  • Beta 分布:若某拉杆被选择了k次，其中m1次奖励为 1，m2次奖励为 0，则该拉杆的奖励服从参数为 的 Beta 分布。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class ThompsonSampling(Solver):
    """ 汤普森采样算法,继承Solver类 """
    def __init__(self, bandit):
        super(ThompsonSampling, self).__init__(bandit)
        self._a = np.ones(self.bandit.K)  
        self._b = np.ones(self.bandit.K)  

    def run_one_step(self):
        samples = np.random.beta(self._a, self._b)  
        k = np.argmax(samples)  
        r = self.bandit.step(k)

        self._a[k] += r  
        self._b[k] += (1 - r)  
        return k

sample ：

1
2
3
4
5
np.random.seed(1)
thompson_sampling_solver = ThompsonSampling(bandit_10_arm)
thompson_sampling_solver.run(5000)
print('汤普森采样算法的累积懊悔为：', thompson_sampling_solver.regret)
plot_results([thompson_sampling_solver], ["ThompsonSampling"])
alt text

头像头像

FrWalker

a blog for sharing my thoughts and experiences

打赏作者

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 FrWalker Blog！