![[CH01]老虎机问题](https://d-sketon.top/img/_backwebp/bg20.webp)
零、写在前面
感觉绕不开这一块了，严肃学习人类智慧。
我们以老虎机问题为例，有多台老虎机，每台的中奖概率不同，且一开始不知道哪台最好。可玩的次数有限，怎样一边获得奖励、一边逐渐找到更好的机器？
这看似只是“选机器”，但这已经包含了强化学习最核心的困难：
- 反馈是随机的，一次赢或输不能说明一台机器的真实水平；
- 只有被自己选中的行动才会产生数据；
- 只利用当前看来最好的选择，可能永远错过真正最好的选择；
- 若环境会变化，过去的数据不能永远和新数据同等重要。
一、老虎机问题
1.1 机器学习的分类与强化学习
1.1.1 监督学习
监督学习使用成对数据：
$$ (x, y) $$其中 $x$ 是输入，$y$ 是正确答案标签。以你熟悉的图像分类为例，图像是 $x$，类别标签是 $y$；神经网络通过损失函数，让预测逐渐接近标签。
监督学习的关键条件是：即使模型当前预测错了，训练数据仍然直接提供正确答案。
1.1.2 无监督学习
无监督学习通常只有数据 $x$，没有对应的正确答案 $y$。它试图发现数据内在的结构，例如聚类、特征提取或降维。
它并不回答“这次选择对不对”，而是回答“这些数据本身有什么模式”。
1.1.3 强化学习
强化学习不是先拿到一张固定的数据表再训练。它的训练数据由智能代理和环境的互动不断产生：
$$ \text{智能代理} \xrightarrow{\text{行动}} \text{环境} \xrightarrow{\text{奖励（以及一般情形下的新状态）}} \text{智能代理}. $$| 术语 | 含义 | 机器人行走例子 |
|---|---|---|
| 智能代理（agent） | 作出行动的主体 | 机器人 |
| 环境（environment） | 接受行动并给出反馈的外部系统 | 真实世界或模拟器 |
| 行动（action） | 代理当前作出的选择 | 控制四肢运动 |
| 奖励（reward） | 环境对已执行行动的数值反馈 | 前进的距离 |
| 状态（state） | 代理据以决策的环境情形 | 机器人周围情况、姿态等 |
强化学习的目标是学习一套行动方式，使长期得到的奖励尽可能大。
和监督学习最容易混淆的地方
奖励不是“正确行动的标签”。假设机器人向左迈了一步并得到较小奖励，环境只告诉它这一步的结果较差；环境没有同时告诉它“向右迈一步一定最好”。代理要通过自己不断试错来获得经验。
如果一条训练样本只包含“你刚才选的行动及其奖励”，为什么它不能直接成为所有其他行动的标签？
因为其他行动根本没有被执行，环境没有给出它们在当前轮次的反馈。
1.2 老虎机问题
1.2.1 什么是老虎机问题
多臂老虎机问题可以理解为：面对多台单臂老虎机，每次选一台并拉动拉杆。不同机器有不同但未知的奖励分布；可玩次数有限，目标是使总奖励尽可能大。
用前面的术语来做对应的话：
| 老虎机故事 | 术语 |
|---|---|
| 玩家 | 智能代理 |
| 多台老虎机的集合 | 环境 |
| 选择一台机器 | 行动 |
| 得到的硬币数 | 奖励 |
| 某台机器反复试玩后的结果 | 经验数据 |
设总共可以玩 $T$ 次。每次选择行动 $A_t$，获得奖励 $R_t$。直观目标是让
$$ R_1+R_2+\cdots+R_T $$尽可能大。
不过这里是因为没有建模啊，所以这个式子这么写了。因为每一轮都面对同一组机器，当前选择不会改变下一轮可面对的机器，暂时不需要建模状态。后面章节才会遇到处理“行动改变状态、状态又影响未来行动”的一般情形。
1.2.2 什么是好的老虎机
老虎机有随机性，所以不能用一次结果判断好坏。合理的判断标准是奖励的期望值。
假设有：
于是：
$$ \begin{aligned} \mathbb{E}[R\mid a] &= 0\times0.70+1\times0.15+5\times0.12+10\times0.03=1.05,\\ \mathbb{E}[R\mid b] &= 0\times0.50+1\times0.40+5\times0.09+10\times0.01=0.95. \end{aligned} $$如果这些分布已经完全已知，而且要玩很多次，机器 a 更好。注意：机器 a 仍可能在某一次得到 0，机器 b 仍可能偶尔得到 10；“更好”指长期平均意义上的更好。
在强化学习中，给定行动后奖励的期望值称为行动价值（action value）。
1.2.3 数学表示
| 符号 | 含义 |
|---|---|
| $R$ | 随机变量：奖励 |
| $R_t$ | 第 $t$ 次互动中得到的奖励 |
| $A$ | 随机变量：行动 |
| $\mathbb{E}[\cdot]$ | 期望 |
| $\mathbb{E}[R\mid A]$ | 已知采取行动 $A$ 时的奖励期望 |
对一个具体行动 $a$，真实但未知的行动价值写作：
$$ q(a)=\mathbb{E}[R_t\mid A_t=a] $$行动价值既可以用 $q(a)$ 表示，也可以用 $Q(a)$ 表示。
- $q$ 表示环境真正的、代理看不见的价值；
- $Q_t(a)$ 表示代理在第 $t$ 轮时从有限经验中得到的估计。例如，$Q_t(a)$ 是“目前认为机器 a 有多好”，不等于机器 a 的真实 $q(a)$。为减轻符号负担，后文不强调时会简写为 $Q(a)$ 或 $Q$。
1.3 老虎机算法
问题现在很清楚：若已知每台机器的 $q$，直接选最大的即可；但 $q$ 未知，只能由亲自得到的奖励来估计。
1.3.1 价值的估计方法
若某个行动得到过奖励 $R_1,R_2,\ldots,R_n$，最自然的估计是样本均值：
$$ Q_n=\frac{R_1+R_2+\cdots+R_n}{n}. $$例如，对某台机器的三次奖励为 $0,1,5$，则当前估计为：
$$ Q=\frac{0+1+5}{3}=2. $$这不是对真实期望的保证，只是目前最合理的经验总结。样本数量增大时，样本均值会更稳定；在稳态分布下，大数定律说明它会趋近真实期望。
这里有一个强化学习特有的限制：只要你没有去玩另一台机器，就没有它的新样本。也就是说，数据收集策略本身会影响学到什么。
1.3.2 求平均值的实现
我们可以把均值估计写成增量式。由
$$ R_1+\cdots+R_{n-1}=(n-1)Q_{n-1} $$可得：
$$ \begin{aligned} Q_n &=\frac{(n-1)Q_{n-1}+R_n}{n}\\ &=Q_{n-1}+\frac{1}{n}(R_n-Q_{n-1}). \end{aligned} $$这个好处，可以从下面的代码实现中体现出，我们可以O(1)更新，而非每次O(n)计算：
import numpy as np
np.random.seed(0)
rewards = []
for n in range(1, 11):
reward = np.random.rand()
rewards.append(reward)
Q = sum(rewards) / n
print(Q)
print('---')
np.random.seed(0)
Q = 0
for n in range(1, 11):
reward = np.random.rand()
Q = Q + (reward - Q) / n
print(Q)
当然也可以把它读成：
$$ \text{新估计}
\text{旧估计} + \text{步长} \times (\text{新奖励}-\text{旧估计}). $$
其中 $(R_n-Q_{n-1})$ 是新观测与当前估计之间的差，而 $1/n$ 决定本次朝新观测移动多远。
不难发现，随着样本的增加，单个新奖励只会带来很小更新。这正适合“真实价值不变”的稳态问题。
1.3.3 玩家的策略
如果始终选择当前 $Q$ 最大的行动，这叫作贪婪行动（greedy action），也叫利用（exploitation）。它充分使用已有经验，却可能因早期的偶然结果而把真正最优的机器永久忽略。
主动尝试不一定是当前最优的行动，叫作探索（exploration）。探索会牺牲眼前的一部分奖励，却能减少“我目前的判断是否只是巧合”的不确定性。
| 做法 | 当前一步的倾向 | 长期风险或收益 |
|---|---|---|
| 利用 | 选择当前 $Q$ 最大的行动 | 可能过早锁定错误行动 |
| 探索 | 尝试其他行动 | 发现更好行动、改进估计 |
我们采用最基础的 ε-greedy 策略：
$$ A_t= \begin{cases} \text{随机行动}, & \text{概率为 }\varepsilon,\\ \arg\max_a Q(a), & \text{概率为 }1-\varepsilon. \end{cases} $$当 $\varepsilon=0.1$ 时，约 10% 的决策进入探索分支，约 90% 的决策利用当前估计。
1.4 老虎机算法的实现
本节把抽象符号落实为两个对象：环境 Bandit 和智能代理 Agent。
1.4.1 老虎机的实现
每台机器的奖励只取 0 或 1。若第 \(a\) 台机器的胜率是 $p_a$，则：
$$ R= \begin{cases} 1, & \text{概率 }p_a,\\ 0, & \text{概率 }1-p_a. \end{cases} \qquad \mathbb{E}[R\mid A=a]=p_a. $$我们封装成类：
class Bandit:
def __init__(self, arms=10):
self.rates = np.random.rand(arms)
def play(self, arm):
rate = self.rates[arm]
return 1 if rate > np.random.rand() else 0
1.4.2 智能代理的实现
Agent 有两组长度为行动数的数组：
| 成员 | 第 $a$ 个元素的含义 |
|---|---|
| Qs[a] | 对第 $a$ 台机器行动价值的当前估计 |
| ns[a] | 第 $a$ 台机器已被选择的次数 |
更新某个行动时，只改该行动对应的一个位置。
class Agent:
def __init__(self, epsilon, action_size=10):
self.epsilon = epsilon
self.Qs = np.zeros(action_size)
self.ns = np.zeros(action_size)
def update(self, action, reward):
self.ns[action] += 1
self.Qs[action] += (reward - self.Qs[action]) / self.ns[action]
def get_action(self):
if np.random.rand() < self.epsilon:
return np.random.randint(0, len(self.Qs))
return np.argmax(self.Qs)
我们完全按照 1.3.2 的增量均值公式来实现，只是每台机器都要维护自己的 $Q$ 和自己的计数 $n$。更准确地写为：
$$ N(a)\leftarrow N(a)+1, \qquad Q(a)\leftarrow Q(a)+\frac{R-Q(a)}{N(a)}. $$1.4.3 尝试运行
一次强化学习互动可以拆成三个步骤：
action = agent.get_action() # ① 选择行动
reward = bandit.play(action) # ② 环境给出奖励
agent.update(action, reward) # ③ 用经验更新估计
我们写一个测试程序：
if __name__ == '__main__':
steps = 1000
epsilon = 0.1
bandit = Bandit()
agent = Agent(epsilon)
total_reward = 0
total_rewards = []
rates = []
for step in range(steps):
action = agent.get_action()
reward = bandit.play(action)
agent.update(action, reward)
total_reward += reward
total_rewards.append(total_reward)
rates.append(total_reward / (step + 1))
print(total_reward)
plt.ylabel('Total reward')
plt.xlabel('Steps')
plt.plot(total_rewards)
plt.show()
plt.ylabel('Rates')
plt.xlabel('Steps')
plt.plot(rates)
plt.show()
输出的总奖励是：908。效果还可以。
1.4.4 算法平均的特性
强化学习含有多个随机来源：隐藏机器的胜率随机生成，探索动作随机选择，奖励本身也随机采样。因此，比起一次运行，比较算法的多次运行平均更可靠。
这里沿用之前做过的玩 1000 次老虎机的实验，重复 200 次，然后对结果进行平均。代码如下所示：
import numpy as np
import matplotlib.pyplot as plt
from bandit import Bandit, Agent
runs = 200
steps = 1000
epsilon = 0.1
all_rates = np.zeros((runs, steps)) # (2000, 1000)
for run in range(runs):
bandit = Bandit()
agent = Agent(epsilon)
total_reward = 0
rates = []
for step in range(steps):
action = agent.get_action()
reward = bandit.play(action)
agent.update(action, reward)
total_reward += reward
rates.append(total_reward / (step + 1))
all_rates[run] = rates
avg_rates = np.average(all_rates, axis=0)
plt.ylabel('Rates')
plt.xlabel('Steps')
plt.plot(avg_rates)
plt.show()
从 0.5 左右的胜率开始，随着迭代的进行，胜率迅速提高。从大约第 600 次迭代开始胜率逐渐趋于稳定，最终胜率达到 0.83 左右。
我们也可以测一下不同的ε：
1.5 非稳态问题
1.5.1 解决非稳态问题前的准备工作
到目前为止，Bandit 在初始化后不再改变 rates，因此奖励分布固定。这是稳态问题。
| 问题类型 | 隐藏价值会不会随时间变化 | 合理的历史数据处理方式 |
|---|---|---|
| 稳态 | 不变 | 所有样本可同等对待 |
| 非稳态 | 会漂移 | 新样本应比很久以前的样本更重要 |
样本均值给所有历史奖励同样的权重 $1/n$：
$$ Q_n=\frac{1}{n}R_1+\frac{1}{n}R_2+\cdots+\frac{1}{n}R_n $$这在稳态时很合理；但若当前环境已变化，十分钟前的数据不应和刚获得的数据具有同样影响。
我们修改之前老虎机的实现，让 rates 每次游戏中都发生变化：
class NonStatBandit:
def __init__(self, arms=10):
self.arms = arms
self.rates = np.random.rand(arms)
def play(self, arm):
rate = self.rates[arm]
self.rates += 0.1 * np.random.randn(self.arms) # Add noise
if rate > np.random.rand():
return 1
else:
return 0
为了应对非稳态问题，我们可以把递减步长 $1/n$ 改成固定步长 $0<\alpha<1$：
$$ Q_n=Q_{n-1}+\alpha(R_n-Q_{n-1}). $$它可改写为：
$$ Q_n=\alpha R_n+(1-\alpha)Q_{n-1}. $$继续展开可得：
$$ Q_n =\alpha R_n +\alpha(1-\alpha)R_{n-1} +\alpha(1-\alpha)^2R_{n-2} +\cdots +(1-\alpha)^nQ_0. $$离当前越近的奖励，权重越大；每往前退一步，权重乘一次 $1-\alpha$。这就是指数移动平均（也常称指数加权移动平均）。
这样我们的权重分布就变成了这样：
固定 α 的直觉：
- α 较大：迅速跟随新奖励，也更容易受随机噪声影响；
- α 较小：曲线较平滑，但对环境变化反应较慢；
- 样本均值相当于步长持续减小，最后几乎不再适应变化。
固定 α 并非只能用于非稳态问题；它是在“持续适应新数据”和“保留更多稳定样本信息”之间的一种选择。
本章中它更适合非稳态环境，是因为该环境确实会漂移。与样本均值不同，固定 α 的展开式仍含有 $(1-\alpha)^nQ_0$，所以初始化值会在一段时间内造成偏置。样本均值则在第一次更新后不再保留初始 $Q_0$ 的影响。
1.5.2 解决非稳态问题
先写一个指数移动平均的Agent：
class AlphaAgent:
def __init__(self, epsilon, alpha, actions=10):
self.epsilon = epsilon
self.Qs = np.zeros(actions)
self.alpha = alpha
def update(self, action, reward):
self.Qs[action] += (reward - self.Qs[action]) * self.alpha
def get_action(self):
if np.random.rand() < self.epsilon:
return np.random.randint(0, len(self.Qs))
return np.argmax(self.Qs)
然后跑一下：
runs = 200
steps = 1000
epsilon = 0.1
alpha = 0.8
agent_types = ['sample average', 'alpha const update']
results = {}
for agent_type in agent_types:
all_rates = np.zeros((runs, steps)) # (200, 1000)
for run in range(runs):
if agent_type == 'sample average':
agent = Agent(epsilon)
else:
agent = AlphaAgent(epsilon, alpha)
bandit = NonStatBandit()
total_reward = 0
rates = []
for step in range(steps):
action = agent.get_action()
reward = bandit.play(action)
agent.update(action, reward)
total_reward += reward
rates.append(total_reward / (step + 1))
all_rates[run] = rates
avg_rates = np.average(all_rates, axis=0)
results[agent_type] = avg_rates
# plot
plt.figure()
plt.ylabel('Average Rates')
plt.xlabel('Steps')
for key, avg_rates in results.items():
plt.plot(avg_rates, label=key)
plt.legend()
plt.show()
在这个非稳态设定下，样本均值早期可以工作，但随着时间推移越来越难跟上变化；固定 α 更新更重视新奖励，长期平均胜率更好。
值得注意的是：
NonStatBandit 的 rates 是未裁剪的随机游走参数，代码没有把它们限制在 \([0,1]\)。当某个 rate 漂移出这个区间时，它已不再是严格意义上的胜率；比较式等价于把实际中奖概率压到 0 或 1 的边界。这里的重点是展示估计目标会漂移，而不是构造一个严格校准的概率模型；所以不要把它和稳态 Bandit 中始终合法的“胜率”混为一谈。
1.6 小结
本章的核心不止是 ε-greedy，而是一条可重复使用的思考方式：
| 问题 | 本章答案 |
|---|---|
| 什么是要学的量？ | 行动价值，即给定行动时奖励的期望 |
| 真值未知怎么办？ | 用实际奖励的平均值估计 |
| 如何不保存全部历史？ | 用增量式更新 Q |
| 为什么不能总选当前最好？ | 早期估计有不确定性，需要探索 |
| 如何平衡探索和利用？ | ε-greedy：ε 概率探索，其他时间利用 |
| 为什么一次曲线不可信？ | 随机性大，应多次独立运行并取平均 |
| 环境会变怎么办？ | 用固定 α 的指数移动平均提高新数据权重 |
说些什么吧！