探索与利用

基本概念

• 探索（Exploration）：尝试新的动作，获得更多信息，以发现更好的策略
  • 简单探索（Heuristic Exploration）：不显式建模不确定性，通过随机性 “强行探索”，如 $\epsilon$ 贪心，Softmax，高斯噪声
  • 面对不确定性时保持乐观：评估不确定性，倾向于选择不确定性最高的状态 / 动作，如 Upper Confidence Bound（UCB）、乐观初始化、探索奖励
  • 信息状态搜索：将 Agent 的信息作为其状态的一部分，动作选择过程结合了前瞻性搜索，显式评估获取信息的长期价值
  • 从启发式随机探索，到基于置信界的乐观原则，再到以信息为状态的贝叶斯方法，探索策略逐步从经验技巧走向严格的决策理论
• 利用（Exploitation）：选择当前最好的动作，以获得最大的奖励

Regret：探索质量的度量标准

Regret 的定义

• 以多臂老虎机（Multi-Armed Bandit）为例：

  • 动作值：$Q (a)=\mathbb {E}[r|a]$
  • 最优价值：$V^*=Q (a^*)=\max_{a} Q (a)$

• 即时 Regret：指在某个时间步 $t$，Agent 由于选择了次优动作而错失的最大累积奖励

  $$I_t=\mathbb {E}[V^*-Q (a_t)]$$

• 累积 Regret

  • 衡量整个学习过程中因探索造成的总代价
  • 最大累积奖励 = 最小累积 Regret
  $$L_t=\mathbb {E}\left [\sum_{\tau=1}^tV^*-Q (a_\tau)\right]$$

• Regret 如何计算

  $$\begin {align*} L_{t} & =\mathbb {E}\left [\sum_{\tau=1}^tV^*-Q (a_\tau)\right] \\ & =\sum_{a}\mathbb {E}\left [N_t (a)\right](V^*-Q (a)) \\ & =\sum_{a}\mathbb {E}\left [N_t (a)\right]\Delta_a \end {align*}$$
  • $N_t (a)$：动作 $a$ 被选择的次数
  • $\Delta_a$ 表示动作 $a$ 与最优动作 $a^*$ 之间的差异（Gap）

各种策略的 Regret

• 贪心策略（Greedy）

  • 动作值函数估计：

    $$\hat {Q}_{t}(a)=\frac {1}{N_{t}(a)}\sum_{\tau=1}^{t} r_{\tau}\mathbf {1}(a_{\tau}=a)$$

  • 动作选择规则：

    $$a_t=\arg\max_a \hat {Q}_t (a)$$

  • Regret 行为：

    • 完全不探索，一旦早期采样噪声导致某个次优动作被高估，将永久锁死

    • 以正概率选不到最优动作

    • 累积 Regret 为线性增长：

      $$L_t=\Theta (t)$$

• 随机策略（Uniform Random）

  • 动作值函数估计：

    $$\hat {Q}_{t}(a)=\frac {1}{N_{t}(a)}\sum_{\tau=1}^{t} r_{\tau}\mathbf {1}(a_{\tau}=a)$$

  • 动作选择：

    $$\pi (a)=\frac {1}{|\mathcal {A}|},\quad \forall a$$

  • Regret 行为：

    • 每个动作被等概率选择，最优动作无法被集中利用

    • 单步期望 Regret 为常数：

      $$I_t=\mathbb {E}[V^*-Q (a_t)]>0$$

    • 累积 Regret 为线性增长

• $\epsilon$- 贪心策略（固定 $\epsilon$）

  • 动作选择规则：

    $$a_t= \begin {cases} \arg\max_a \hat {Q}_t (a), & \text{with prob.} 1-\epsilon \\ \text{uniform random}, & \text{with prob.} \epsilon \end {cases}$$

  • 单步 Regret 下界：

    $$I_t\ge \frac {\epsilon}{|\mathcal {A}|}\sum_{a}\Delta_a$$

  • Regret 行为：

    • 即使估计已充分收敛，仍以固定概率探索
    • 次优动作被无限次选择
    • 累积 Regret 为线性增长

• 衰减 $\epsilon$- 贪心策略（Decaying $\epsilon$）

  • 典型 $\epsilon$ 序列：

    $$\begin {align*} & c>0 \\ & d=\min_{a:\Delta_a>0}\Delta_a \\ & \epsilon_t=\min\left\{1,\frac {c|\mathcal {A}|}{d^2 t}\right\} \end {align*}$$

  • Regret 行为：

    • 初期充分探索，后期逐渐趋向贪心

    • 可实现对数阶累积 Regret：

      $$L_t=O (\log t)$$

  • 局限性：需要事先知道 Gap 下界 $d$，实际问题中通常不可得

• Softmax / Boltzmann 探索

  • 动作选择概率：

    $$\pi (a)=\frac {\exp (\hat {Q}_t (a)/\tau)}{\sum_{a'}\exp (\hat {Q}_t (a')/\tau)}$$

  • 温度参数 $\tau$：

    • $\tau\to 0$：趋近贪心
    • $\tau\to \infty$：趋近随机

  • Regret 特性：

    • 探索强度随价值差异自适应变化
    • 理论 Regret 分析复杂，通常无最优保证
    • 实践中常配合温度衰减使用

• Gaussian Noise（连续动作）

  • 动作选择：

    $$a_t=\mu (s_t)+\mathcal {N}(0,\sigma_t^2)$$

  • Regret 行为：

    • 本质是连续动作空间下的随机探索
    • 探索强度由 $\sigma_t$ 控制
    • 若 $\sigma_t$ 不衰减 → 线性 Regret
    • 若 $\sigma_t$ 合理衰减 → 可获得亚线性 Regret（缺乏严格最优性保证）

Regret 下界

• 渐近总 Regret 下界（Lai–Robbins Lower Bound）

  • 对于任意**一致有效（uniformly good）**的策略，其累积 Regret 不可能低于对数阶：

    $$\lim_{t\to\infty} L_t \ge \log t \sum_{a:\Delta_a>0} \frac {\Delta_a}{KL (\mathcal {R}^a \,\|\, \mathcal {R}^{a^*})}$$

  • 含义：

    • $\log t$ 是不可避免的时间尺度
    • 常数项由**Gap $\Delta_a$与分布可区分性（KL）**决定

• 为什么至少是 $\log t$

  • 要确认某个动作 $a$ 是次优的，必须以高置信度区分：

    $$\mathcal {R}^a \neq \mathcal {R}^{a^*}$$

  • 根据大数定律与信息论极限，区分两个分布至少需要由以下公式决定的次数的采样：

    $$\Omega\!\left (\frac {\log t}{KL (\mathcal {R}^a\|\mathcal {R}^{a^*})}\right)$$

  • 因此：每个次优动作都必须被探索至少对数次，“几乎不探索” 的策略在统计意义上不可能可靠

• 对探索频率的约束

  • 对任意 $\Delta_a>0$ 的动作：

    $$\mathbb {E}[N_t (a)] \gtrsim \frac {\log t}{KL (\mathcal {R}^a\|\mathcal {R}^{a^*})}$$

  • 否则，策略无法以足够高概率确认该动作是次优

• 与贪心策略的对比

  • 纯贪心策略：早期估计错误概率不随 $t$ 消失，某些次优动作可能被采样次数有限甚至为常数，导致：

    $$L_t=\Theta (t)$$

  • 因此贪心策略违背 Lai–Robbins 条件，无法达到对数 Regret 下界

• KL 散度的角色

  • $KL (\mathcal {R}^a\|\mathcal {R}^{a^*})$：
    • 衡量两个奖励分布的 “可区分性”
    • KL 越小 → 分布越相似 → 越难分辨 → 需要更多探索
  • 极端情况：
    • $\Delta_a$ 很小且 KL 很小
    • 即使是最优策略，也必须付出大量探索成本

• 二臂赌博机（2-armed bandit）示例

  • 设两个动作：

    • $a^*$：均值 $\mu^*$
    • $a$：均值 $\mu=\mu^*-\Delta$

  • 若奖励为高斯分布（方差 $\sigma^2$）：

    $$KL (\mathcal {N}(\mu,\sigma^2)\|\mathcal {N}(\mu^*,\sigma^2)) = \frac {\Delta^2}{2\sigma^2}$$

  • Regret 下界变为：

    $$\lim_{t\to\infty} L_t \ge \frac {2\sigma^2}{\Delta}\log t$$

  • Gap 越小 → 问题越难

  • 噪声越大 → 探索成本越高

• 对数阶 Regret 是多臂赌博机问题的信息论极限

• UCB、Thompson Sampling 等算法：在常数因子意义下逼近该下界

• 任何声称 “几乎不探索却能长期最优” 的算法：在随机环境中必然不成立

面对不确定性时保持乐观

Upper Confidence Bound（UCB）算法

• 在选择动作时，考虑估计均值 + 不确定性上界

• 对于每个动作值，估计上置信界 $\hat {U_t}(a)$，则 $Q (a)\le \hat {Q_t}(a)+\hat {U_t}(a)$ 出现的可能性较大

• UCB 值的计算

  $$Q_t (a)+c\sqrt {\frac {\ln t}{N_t (a)}}$$

• 选择具有最大 UCB 值的动作：

  $$a_t = \arg\max_a \left (\hat {Q}_t (a) + c\sqrt {\frac {\log t}{N_t (a)}} \right)$$

• 其中 $Q_t (a)$ 是动作 $a$ 的平均奖励，$N_t (a)$ 是动作 $a$ 被选择的次数，$c$​ 是一个探索参数

• UCB1 的 Regret 上界：

  $$L_t \le 8 \log t \sum_{a:\Delta_a>0} \Delta_a$$

Hoeffding’s Inequality

• 对于独立同分布的随机变量，其均值的估计值与真实均值之间的差异是以高概率收敛的

  $$\begin {align*} \mathbb {P}\left [\mathbb {E}\left [X\right]>\overline {X}_t+u\right]&\leq e^{-2tu^2}\\ \mathbb {P}\left [Q (a)>\hat {Q}_t (a)+U_t (a)\right]&\leq e^{-2N_t (a) U_t (a)^2}=p\\ U_t (a) & =\sqrt {\frac {-\log p}{2N_t (a)}} \end {align*}$$

• 取 $p=t^{-4}$，则

  $$U_t (a)=\sqrt {\frac {2\log t}{N_t (a)}}$$

• 此即，UCB1

• 动作选择

  $$a_t=\underset {a}{\operatorname*{\operatorname*{argmax}}} Q (a)+\sqrt {\frac {2\log t}{N_t (a)}}$$

• 对数渐进总 Regret

  $$\displaystyle\lim_{t\to\infty} L_t\leq8\log t\displaystyle\sum_{a|\Delta_a>0}\Delta_a$$

贝叶斯方法

• 基本思想
  • 假设已知奖励 $\mathcal {R}$ 的先验概率分布 $p [\mathcal {R}]$
  • 然后计算在历史 $h_r=a_1,r_1,\cdots,a_{t-1},r_{t-1}$ 下的后验概率分布 $p [\mathcal {R}|h_t]$
  • 利用后验概率指导探索
• 贝叶斯 UCB
• 概率匹配
  • 选择动作 $a$ 满足：$\pi (a\mid h_t)=\mathbb {P}\left [Q (a)>Q (a^{\prime}),\forall a^{\prime}\neq a\mid h_t\right]$
  • 将不确定性表示为概率分布，不确定的动作有更高的概率成为最大

Thompson Sampling 算法

• 按照成为最优动作的概率来选择动作

  $$\begin {align*} \pi (a\mid h_t)&=\mathbb {E}_{\mathcal {R}|h_t}\left [\mathbf {1}(a=\operatorname*{argmax}_{a} Q (a))\right]\\ &=\mathbb {P}\left (a = \arg\max_{a'} Q (a') \mid h_t \right) \end {align*}$$

• 算法流程

  • 从后验分布中采样一个奖励分布 $\mathcal {R}$
  • 计算状态值函数 $Q (a)=\mathbb {E}[\mathcal {R}_a]$，选择最大的动作 $a_t=\displaystyle\operatorname*{argmax}_{a} Q (a)$
  • 更新后验分布
  • 重复以上步骤

信息状态搜索

• 探索的本质不是 “随机”，而是：

  • 探索是为了获取信息，而信息具有长期价值
  • 那么如何定量信息的价值，量化该信息能够带来多少长期价值
  • 获取信息后长期奖励 - 即时奖励
  • 如果知道信息的价值，就可以最佳地权衡探索和利用

• 信息状态空间

  • 历史：$h_t = (a_1,r_1,\dots,a_{t-1},r_{t-1})$

  • 每一步均有其信息状态 $\tilde {s}$：$\tilde {s}$​ 是历史信息的统计，总结目前积累的所有信息

    $$\tilde {s}=f (h_t)$$

  • 信息状态空间是一个 MDP，即 $\mathcal {M}= \langle \mathcal {\tilde {S}}, \mathcal {A}, \mathcal {\tilde {P}}, \mathcal {R}, \gamma \rangle$

    • 状态：信息状态 $\tilde {s}$
    • 动作：选择动作 $a$
    • 状态转移：$\mathcal {\tilde {P}}(\tilde {s}^{\prime}|\tilde {s},a)$
    • 信息奖励函数：$\mathcal {\tilde {R}}$
    • 折扣因子：$\gamma$

  • 这是一个无限 MDP 问题，状态空间巨大（甚至无限），完全刻画探索–利用权衡

• 如何解决信息状态空间的 MDP 问题

  • Model-Free 强化学习（在信念空间）
  • 贝叶斯 Model-Based 强化学习
    • 贝叶斯适应强化学习
    • Gittins Index（bandit 场景最优解）