本系列是学习《动手学强化学习》 过程中做的摘抄。
1.1 问题介绍#
多臂老虎机（multi-armed bandit, MAB）问题中，有一个拥有 \(K\) 根拉杆的老虎机，拉动每一根拉杆都对应一个奖励的概率分布 \(\mathcal{R}\)。 多臂老虎机问题可以表示为一个元组 \(<\mathcal{A}, \mathcal{R}>\)，其中：
- \(\mathcal{A}\) 为动作集合
- \(\mathcal{R}\) 为奖励分布
对于每一个动作 \(a\)，定义其期望奖励为 \(\text{E}_{r \sim \mathcal{R}(\cdot | a)} [r]\)。 最优期望奖励表示为 \(\mathcal{Q}^{*} = \max_{a \in \mathcal{A}} \mathcal{Q}(a)\)，懊悔 \(\mathcal{R}(a) = \mathcal{Q}^{*} - \mathcal{Q}(a)\)。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np
class BernoulliBandit:
def __init__(self, K):
"""伯努利多臂老虎机, 输入 K 为拉杆个数"""
self.probs = np.random.uniform(size=K) # 随机生成K个0-1之间的数，作为每个拉杆的获奖概率
self.best_idx = np.argmax(self.probs) # 获奖概率最大的拉杆
self.best_prob = self.probs[self.best_idx] # 最大的获奖概率
self.K = K
def step(self, k):
# 当玩家选择了k号拉杆后，根据该老虎机k号拉杆获得奖励的概率返回 1（获奖）或 0（未获奖）
if np.random.rand() < self.probs[k]:
return 1
else:
return 0
class Solver:
def __init__(self, bandit: BernoulliBandit):
"""多臂老虎机算法基本框架"""
self.bandit = bandit
self.counts = np.zeros(self.bandit.K) # 每个拉杆的尝试次数
self.regret = 0.0 # 当前步的累积懊悔
self.actions = list() # 维护一个列表，记录每一步的动作
self.regrets = list() # 维护一个列表，记录每一步的累积懊悔
def update_regret(self, k):
# 计算累积懊悔并保存，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):
# 运行一定次数，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 上置信界算法#
不确定性度量 \(U(a)\)，它会随着一个动作被尝试次数的增加而减小。直观地说，UCB 算法在每次选择拉杆前，先估计拉动每根拉杆的期望奖励上界，使得拉动每根拉杆的期望奖励只有一个较小的概率 \(p\) 超过这个上界，接着选出期望奖励上界最大的拉杆，从而选择最优可能获得最大期望奖励的拉杆。
class UCB(Solver):
def __init__(self, bandit, coef, init_prob=1.0):
"""UCB算法, 继承Solver类"""
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.0 / (self.counts[k] + 1) * (r - self.estimates[k])
return k
1.3 汤普森采样算法#
假设每根拉杆的奖励服从一个特定的概率分布，然后根据拉动每根拉杆的期望奖励来进行选择。但是由于计算所有拉杆的期望奖励的代价比较高，汤普森采样算法使用采样的方式，即根据当前每个动作 a 的奖励概率分布进行一轮采样，得到一组各根拉杆的奖励样本，再选择样本中奖励最大的动作。
class ThompsonSampling(Solver):
def __init__(self, bandit):
"""汤普森采样算法, 继承Solver类"""
super(ThompsonSampling, self).__init__(bandit)
self._a = np.ones(self.bandit.K) # 列表，表示每个拉杆奖励为1的次数
self._b = np.ones(self.bandit.K) # 列表，表示每个拉杆奖励为0的次数
def run_one_step(self):
samples = np.random.beta(self._a, self._b) # 按照Beta分布采样一组奖励
k = np.argmax(samples) # 选出采样数值最大的拉杆
r = self.bandit.step(k)
self._a[k] += r # 更新Beta分布的第一个参数
self._b[k] += 1 - r # 更新Beta分布的第二个参数
return k