探索与利用：强化学习的核心困境

这份文档详细阐述了强化学习中的一个基本且至关重要的问题：探索与利用（Exploration vs. Exploitation）的权衡。为保证表述严谨与可渲染性，本文统一采用如下符号与术语。

符号与术语

• 动作与时间：$A_t$ 表示第 $t$ 步选择的动作，$t=1,\dots ,T$，$T$ 为总步数。

• 奖励：$r_t$ 表示第 $t$ 步获得的奖励；臂 $a$ 的期望奖励为 ${\mu }_a=\mathbb{E}[r\mid A=a]$；最优臂 $a^{\star }=\arg \underset{a}{max}{\mu }_a$，最优期望奖励 ${\mu }^{\star }=\underset{a}{max}{\mu }_a$。

• 经验均值与计数：$Q_t(a)$ 为到 $t-1$ 步为止对臂 $a$ 的经验平均奖励估计；$N_t(a)$ 为到 $t-1$ 步为止臂 $a$ 被选择的次数。

• 次优间隔：${\mathrm{\Delta }}_a={\mu }^{\star }-{\mu }_a\ge 0$。

• 遗憾：累积遗憾

  $$R_T=\sum _{t=1}^T({\mu }^{\star }-{\mu }_{A_t})=\sum _{a\ne a^{\star }}{\mathrm{\Delta }}_a\mathbb{E}[N_T(a)]$$

  期望遗憾记为 $\mathbb{E}[R_T]$。

1. 核心概念：序列决策中的基本问题

在强化学习中，智能体（Agent）的目标是最大化长期回报。为此，它必须在两种看似矛盾的策略之间权衡：

• 利用（Exploitation）：执行当前看来最能带来高收益的动作。
• 探索（Exploration）：尝试不确定的新动作，以获取信息、发现潜在更优解。

只利用不探索，可能陷入局部最优；只探索不利用，则难以稳定获得高回报。成功的智能体需在两者之间取得平衡，使得遗憾随时间以尽可能慢的速度增长。

2. 多臂老虎机问题（Multi-Arm Bandit）

多臂老虎机是阐释探索与利用困境的经典模型。设有多台老虎机，每台的中奖概率不同且未知，目标是在总步数 $T$ 内最大化总奖励。

• 利用：持续选择当前经验均值最高的臂。
• 探索：有意识地尝试选择次数少、估计不确定性高的臂。

衡量标准：遗憾（Regret）

遗憾定义为最优策略与所用策略之间的期望收益差。形式化地，累积遗憾为

$$R_T=\sum _{t=1}^T({\mu }^{\star }-{\mu }_{A_t}).$$

直观上：

• 若 $R_T$ 随 $T$ 线性增长，策略未趋近最优；
• 若 $R_T$ 次线性（如 $O(\log T)$）增长，策略逐步逼近最优。

3. 解决探索与利用困境的原则和策略

本文按“数学形式→直觉解释→优缺点→适用场景”的结构介绍常见策略。

3.1 朴素探索法：$ϵ$-greedy

数学形式：

• 以概率 $ϵ$ 随机选择任一动作（探索）；
• 以概率 $1-ϵ$ 选择 $\arg \underset{a}{max}{Q}_t(a)$（利用）。

直觉解释：保留固定比例的随机试探，避免过早陷入局部最优。

优缺点：

• 优点：实现简单、计算开销小。
• 缺点：探索对所有非最优臂一视同仁，效率不高；固定 $ϵ$ 会导致长期不必要探索。可用衰减 ${ϵ}_t$ 缓解。
  • 常见做法：${ϵ}_t=min\{1,c/t\}$ 或 ${ϵ}_t={ϵ}_0\cdot {\gamma }^t$，随时间减小探索强度。

适用场景：入门基线、计算预算有限的在线决策。

3.2 积极初始化（Optimistic Initialization）

数学形式：设较大的初始值 $Q_0(a)=Q_{\text{init}}$ 且 $N_0(a)=0$，使早期估计偏乐观，诱导对所有臂的尝试。

• 在线更新的常见形式为增量均值：$Q_{t+1}(a)\leftarrow Q_t(a)+{\alpha }_t(r_t-Q_t(a))$，其中 ${\alpha }_t\in (0,1]$；若使用纯频率均值，${\alpha }_t=1/N_{t+1}(a)$。

简要推导（增量均值）：设第 $t$ 轮选择了臂 $a$，则 $N_{t+1}(a)=N_t(a)+1$，由样本均值定义

$$Q_{t+1}(a)=\frac{\sum _{i\le t:A_i=a}{r}_i}{N_{t+1}(a)}=\frac{N_t(a)Q_t(a)+r_t}{N_t(a)+1}$$

故

$$Q_{t+1}(a)=Q_t(a)+\frac{r_t-Q_t(a)}{N_t(a)+1}.$$

记 ${\alpha }_t=1/N_{t+1}(a)$ 得到增量形式；更一般地，取任意 ${\alpha }_t\in (0,1]$ 得指数滑动平均，用以衰减旧数据的权重。

直觉解释：乐观先验促使“未试多试”，随着数据积累，估计回落至真实水平，算法自然过渡到利用阶段。

优缺点：

• 优点：无需额外随机性即可促探索；实现简单。
• 缺点：对初值敏感，初值过大可能拖慢收敛；在强噪声下可能引入较大方差。

适用场景：低噪声、可接受通过调参获得早期广泛探索的情形；与 UCB、TS 等可组合使用以加速冷启动。

3.3 基于不确定性的度量：UCB

评分分解：

$${\text{Score}}_t(a)=Q_t(a)+U_t(a).$$

UCB1 选择规则（常见形式）：

$$A_t=\arg \underset{a}{max}\{Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}\},$$

其中 $c>0$ 控制探索强度，$N_t(a)$ 越小，不确定性项越大。

直觉解释：基于置信上界的“乐观估计”，偏向选择上界较高的臂，从而平衡探索与利用。

Hoeffding 不等式直觉：对独立有界奖励，经验均值围绕期望的偏差概率呈指数衰减，据此构造置信区间上界；当 $N_t(a)$ 增大，上界收缩，探索力度自动减弱。

简要推导（UCB1 上界项）：设奖励取值于 $[0,1]$，Hoeffding 不等式给出

$$Pr({\mu }_a\ge Q_t(a)+ϵ)\le \exp (-2N_t(a){ϵ}^2).$$

令右侧至多为 $1/t$（或 $1/t^2$，常数与对数因子可吸收进系数），解得

$$ϵ\asymp \sqrt{\frac{\ln t}{N_t(a)}}.$$

据此取不确定性项 $U_t(a)=c\sqrt{\frac{\ln t}{N_t(a)}}$，其中 $c>0$ 吸收常数与松弛因子。

遗憾性质（结论级别）：若各臂奖励分布独立同分布且满足有界性条件，UCB1 的期望遗憾满足

$$\mathbb{E}[R_T]=O(\sum _{a\ne a^{\star }}\frac{\ln T}{{\mathrm{\Delta }}_a}),$$

为对数级次线性。

适用场景：需要稳健理论保证、希望自动调节探索强度的在线学习问题。

3.4 概率匹配：汤普森采样（Thompson Sampling, TS）

以 Bernoulli 奖励为例，对臂 $a$ 的成功率 $p_a$ 采用 Beta 先验：

$$p_a\sim \mathrm{Beta}({\alpha }_a,{\beta }_a).$$

每轮：

1. 采样 ${\tilde{p}}_a\sim \mathrm{Beta}({\alpha }_a,{\beta }_a)$；
2. 选择 $\arg \underset{a}{max}{\tilde{p}}_a$；
3. 观察 $r_t\in \{0,1\}$ 后更新

$${\alpha }_a\leftarrow {\alpha }_a+r_t,{\beta }_a\leftarrow {\beta }_a+(1-r_t).$$

简要推导（Beta–Bernoulli 共轭）：设先验 $p_a\sim \mathrm{Beta}({\alpha }_a,{\beta }_a)$，$n$ 次观测 $\{r_i{\}}_{i=1}^n$ 的似然为 $\prod _i{p}_a^{r_i}(1-p_a{)}^{1-r_i}$，则后验

$$\begin{array}{rl}p(p_a\mid r_{1:n})& \propto p_a^{{\alpha }_a-1}(1-p_a{)}^{{\beta }_a-1}\prod _{i=1}^n{p}_a^{r_i}(1-p_a{)}^{1-r_i}\\ & =p_a^{{\alpha }_a-1+\sum r_i}(1-p_a{)}^{{\beta }_a-1+n-\sum r_i},\end{array}$$

即 $\mathrm{Beta}({\alpha }_a+\sum r_i,{\beta }_a+n-\sum r_i)$。在线情形下，每到一步用 $r_t\in \{0,1\}$ 将 $({\alpha }_a,{\beta }_a)$ 分别加上 $(r_t,1-r_t)$ 即可。

直觉解释：选择概率与成为最优臂的后验概率相匹配；不确定性大的臂更可能被赋高样本值而得到探索。

性质与优缺点：

• 通常经验效果优良，计算简单；
• 具备良好的对数级遗憾特性（具体界依赖假设与设定）；
• 依赖先验设定，连续奖励需换相应共轭先验或采用采样近似。
  • 例如高斯奖励可用正态-正态共轭先验；未知方差时可用正态-逆伽马近似。

适用场景：在线点击率优化、推荐、A/B 测试等需要概率建模与贝叶斯更新的任务。

4. 遗憾分析（概要）

形式化定义与分解：

$$R_T=\sum _{t=1}^T({\mu }^{\star }-{\mu }_{A_t}),\mathbb{E}[R_T]=\sum _{a\ne a^{\star }}{\mathrm{\Delta }}_a\mathbb{E}[N_T(a)].$$

该分解揭示：控制次优臂的选择次数 $\mathbb{E}[N_T(a)]$ 即可控制总体遗憾。

简要推导（遗憾分解）：令 $\mathbb{1}\{A_t=a\}$ 为指示函数，则

$${\mu }^{\star }-{\mu }_{A_t}=\sum _a({\mu }^{\star }-{\mu }_a)\mathbb{1}\{A_t=a\}=\sum _a{\mathrm{\Delta }}_a\mathbb{1}\{A_t=a\}.$$

对 $t=1..T$ 求和并交换求和次序，得

$$R_T=\sum _{t=1}^T\sum _a{\mathrm{\Delta }}_a\mathbb{1}\{A_t=a\}=\sum _a{\mathrm{\Delta }}_a\underset{N_T(a)}{\underbrace{\sum _{t=1}^T\mathbb{1}\{A_t=a\}}}.$$

两侧取期望即可得到 $\mathbb{E}[R_T]=\sum _a{\mathrm{\Delta }}_a\mathbb{E}[N_T(a)]$。

常见上界（代表性结果，省略常数与次要项）：

• UCB1：

$$\mathbb{E}[N_T(a)]=O(\frac{\ln T}{{\mathrm{\Delta }}_a^2}),\Rightarrow \mathbb{E}[R_T]=O(\sum _{a\ne a^{\star }}\frac{\ln T}{{\mathrm{\Delta }}_a}).$$

• 汤普森采样（若满足相应独立、同分布及参数化条件）：

$$\mathbb{E}[R_T]=O(\sum _{a\ne a^{\star }}\frac{\ln T}{{\mathrm{\Delta }}_a}).$$

直觉推导要点（UCB1）：

1. 由 Hoeffding 不等式，经验均值 $Q_t(a)$ 偏离真实均值 ${\mu }_a$ 的概率随 $N_t(a)$ 指数衰减；
2. 将不等式改写为置信区间上界 $Q_t(a)+c\sqrt{\ln t/N_t(a)}$；
3. 当某次优臂被拉动太多次，其上界将低于最优臂的真实均值，从而不再被选择；
4. 由此可界定每个次优臂被选择的次数为 $O((\ln T)/{\mathrm{\Delta }}_a^2)$，得到对数级遗憾。

图示描述建议：

• 在双对数坐标下绘制 $\mathbb{E}[R_T]$ 随 $T$ 的曲线，对比线性、$\sqrt{T}$、$\log T$ 三类增长速率。
• 以条形图展示不同 ${\mathrm{\Delta }}_a$ 对 $\mathbb{E}[N_T(a)]$ 的影响：间隔越小，探索需求越大。

5. 应用与扩展

典型应用：

• 在线广告点击率优化：不同广告创意视作臂，奖励可取 $r_t\in \{0,1\}$（点击）或实值收益。
• 推荐与排序：候选内容为臂，优化点击、停留时长或转化率。
• A/B/n 测试：各变体为臂，采用自适应分流，提高总收益同时加速找到更优方案。
• 工业过程优化：不同工艺参数设定为臂，逐步逼近更优配置。

非平稳环境（奖励分布随时间变化）：

• 滑动窗口 UCB（SW-UCB）：以窗口 $W$ 内样本估计 $Q_t(a)$ 与不确定性；$W$ 越小，越敏感于近期变化。
• 折扣 UCB（Discounted-UCB）：样本加权 ${\gamma }^{\mathrm{\Delta }t}$，$\gamma \in (0,1)$；近期样本权重更大。
• 实践要点：选择合适的 $W$ 或 $\gamma$ 以平衡噪声与适应性；可与变化检测方法结合。

实践建议：

• 冷启动：可用较大的 $c$、乐观初始化或较大初期 $ϵ$；
• 延迟反馈：采用延迟补偿估计或离线反事实校正；
• 约束与合规：在探索时加入预算、安全或公平性约束，使用受限 bandit 变体。

总结

• 探索与利用是强化学习中的核心权衡；
• 多臂老虎机提供了理解该权衡的清晰抽象；
• 遗憾作为关键指标，理想目标是实现次线性增长，最好为对数级；
• $ϵ$-greedy、UCB 与汤普森采样各具特点，在不同约束与场景下均有实践价值与理论支撑。