在强化学习问题中，探索和利用(Exploitation & Exploration)是一对矛盾：探索选择现在不确定的，但未来可能会有高效益的方案；利用则是选择现在可能最佳的方案。如何平衡探索和利用是强化学习领域的一个课题。

后悔值的理解

在多臂老虎机(multi-arm bandit)问题中，定义动作价值$Q(a)=\mathbb{E}[r\mid a])$为采取行为获得的奖励期望，则当前环境中的最优价值可定义为$V^*=Q(a^*)=maxQ(a)$。据此，我们可以定义前$T$步的累积后悔值(regret)为：

需要注意的是，最优价值是一个假设值，是用于理论分析的工具。在模拟实验中，我们可以“提前知道”哪个臂是最优的比如：我们做实验时，设定某个臂的奖励分布是 $\mathcal{N}(0.8, 0.1^2)$，其他臂奖励低一点。在实际应用中，后悔值可以被“近似评估”或作为理论参考，比如可以用 A/B test 或历史数据近似构建基准、采用 pseudo-regret（伪后悔，即用即已知奖励中当前看来最好的臂来代替最优价值）、只看实际获得的 reward。
可以看出，后悔值随着$t$的增加在不断增加，而bandit问题的解决实际上就是希望累积后悔值在$T$周期内增长得尽可能慢， 在最小后悔值前提下，尽早识别最优策略。而bandit算法的核心挑战就是在探索与利用之间找到最优平衡。

经典探索策略

Epsilon-Greedy

以1-$\epsilon$的概率选取当前收益最大的臂，以$\epsilon$的概率随机选取一个臂。在实际应用中，可以在一开始选择较大的$\epsilon$，随着reward的持续升高，再使其逐渐减小。

UCB

$\epsilon$-Greedy的探索“过于”随机：当有足够的样本表现出两个动作之间的优劣时，依然随机的对这两个动作进行采样。这种做法似乎很不合理，而UCB算法则可以解决这个问题。

基本思想

UCB算法的核心思想是乐观面对不确定性（Optimism in the Face of Uncertainty）。具体来说：

• **利用：选择当前平均奖励高的臂。
• 探索：选择那些被尝试次数较少的臂，因为它们的奖励估计不确定性较高，可能有更高的潜在奖励。

UCB通过数学上的置信区间来量化这种不确定性，并在每一步选择具有最高**上置信界（Upper Confidence Bound）的臂。

数学表述

假设我们有$K$个臂，每个臂$i$在时间$t$的以下信息：

• $n_i(t)$：到时间$t$为止，臂$i$被选择的次数。
• $\hat{\mu}_i(t)$：到时间$t$为止，臂$i$的平均奖励。

UCB算法在时间$t$选择臂$I_t$如下：

其中：

• $\hat{\mu}_i(t)$ 是臂$i$的平均奖励，代表利用部分。
• $\sqrt{\frac{2 \ln t}{n_i(t)}}$ 是置信区间半径，代表探索部分。随着$n_i(t)$的增加，这一项减小，表示对臂$i$的估计越来越确定。

推导

UCB算法的设计基于Hoeffding不等式，该不等式为有界随机变量的和提供了置信区间。假设每个臂的奖励$X_i$在$[0,1]$之间（可以通过缩放适应其他区间），Hoeffding不等式告诉我们：

其中$\mu_i$是臂$i$的真实期望奖励。我们希望这个概率很小，比如$\delta = t^{-4}$：

因此，以高概率：

UCB算法选择上界$\hat{\mu}_i(t) + \sqrt{\frac{2 \ln t}{n_i(t)}}$最大的臂，即在最乐观的估计下可能最好的臂。

步骤

以下是UCB算法的详细步骤：

1. 初始化：对每个臂$i$，尝试一次，更新$n_i$和$\hat{\mu}_i$。
2. 循环：对于每个时间步$t = K+1, K+2, \dots, T$：
   • 对每个臂$i$，计算UCB值：
     $$ \text{UCB}_i = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}} $$
   • 选择具有最大UCB值的臂$I_t$。
   • 观察奖励$r_t$。
   • 更新臂$I_t$的统计信息：
     • $n_{I_t} \leftarrow n_{I_t} + 1$
     • $\hat{\mu}_{I_t} \leftarrow \hat{\mu}_{I_t} + \frac{r_t - \hat{\mu}_{I_t}}{n_{I_t}}$ （增量式更新平均奖励）

性能分析

UCB算法的遗憾定义为与始终选择最优臂相比的累积奖励损失。UCB算法的遗憾是对数增长的，即：

其中$\Delta_i = \mu^* - \mu_i$是臂$i$与最优臂的奖励差距。这表明UCB在长期表现良好，因为遗憾的增长速度远慢于时间$T$。

Python实现

以下是一个简单的UCB算法的Python实现：

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import numpy as np  
import math  
  
def ucb(K, T, rewards):  
    # K: number of arms  
    # T: time horizon  
    # rewards: function to generate reward for arm i at time t  
      
    # Initialize  
    n = np.zeros(K)  # number of pulls for each arm  
    mu = np.zeros(K)  # empirical mean of each arm  
      
    # Initial phase: pull each arm once  
    for i in range(K):  
        reward = rewards(i, n[i])  
        mu[i] = reward  
        n[i] += 1  
      
    # Main loop  
    for t in range(K, T):  
        # Compute UCB for each arm  
        ucb_values = mu + np.sqrt(2 * np.log(t) / n)  
        # Select arm with highest UCB  
        i = np.argmax(ucb_values)  
        # Pull the arm and observe reward  
        reward = rewards(i, n[i])  
        # Update statistics  
        mu[i] = (mu[i] * n[i] + reward) / (n[i] + 1)  
        n[i] += 1  
      
    return mu, n  
  
# Example usage  
K = 5  # number of arms  
T = 1000  # time horizon  
# Define a reward function (e.g., each arm has a Bernoulli reward with mean p_i)  
true_means = [0.1, 0.3, 0.5, 0.7, 0.9]  
def rewards(i, t):  
    return np.random.binomial(1, true_means[i])  
  
mu, n = ucb1(K, T, rewards)  
print("Estimated means:", mu)  
print("Number of pulls:", n)  

Thompson Sampling

Thompson Sampling（TS）是一种基于贝叶斯方法的多臂老虎机算法，与UCB不同，TS采用概率采样的方式选择最优臂，适用于伯努利奖励（如点击率优化）和更一般的概率分布问题。

基本思想

TS的核心思想是：

1. 维护每个臂的奖励概率分布（如Beta分布）。
2. 从分布中采样一个估计值，选择当前采样值最大的臂。
3. 根据观测到的奖励更新分布，逐步逼近真实概率。

这种方法自然地平衡了探索和利用：

• 利用（Exploitation）：如果某个臂的估计概率较高，则更可能被选择。
• 探索（Exploration）：即使某个臂当前估计较低，但由于其不确定性（方差大），仍可能被采样选中。

数学表述

假设每个臂的奖励服从伯努利分布（如点击率问题），即：

其中，$\mu_i$ 是臂 $i$ 的真实成功概率。

TS使用Beta分布作为$\mu_i$的共轭先验分布：

• $\alpha_i$：臂 $i$ 成功的次数。
• $\beta_i$：臂 $i$ 失败的次数。

算法流程：

1. 初始化：对所有臂 $i$，设 $\alpha_i = 1$, $\beta_i = 1$（即均匀先验）。
2. 循环（每一步 $t$）：
   • 对每个臂 $i$，从 $\text{Beta}(\alpha_i, \beta_i)$ 采样一个值 $\theta_i$。
   • 选择 $\theta_i$ 最大的臂 $I_t = \arg\max_i \theta_i$。
   • 观察奖励 $r_t \in \{0,1\}$。
   • 更新分布：
     • 如果 $r_t=1$（成功）：$\alpha_{I_t} \leftarrow \alpha_{I_t} + 1$
     • 如果 $r_t=0$（失败）：$\beta_{I_t} \leftarrow \beta_{I_t} + 1$

有效性分析

• 贝叶斯更新：每次试验后，用观测数据更新分布，使估计越来越准。
• 概率匹配：选择臂的概率等于它是当前最优臂的概率。
• 自动探索：由于采样机制，即使当前估计较低的臂，只要不确定性高（$\alpha_i + \beta_i$ 小），仍可能被选中。

与UCB的对比

Python实现（伯努利奖励）

 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
27
28
29
30
31
32
33

import numpy as np  
from scipy.stats import beta  
  
def thompson_sampling(K, T, true_means):  
    # K: 臂数量, T: 时间步, true_means: 各臂的真实概率  
    alpha = np.ones(K)  # 成功次数初始化为1  
    beta_ = np.ones(K)   # 失败次数初始化为1  
    rewards = np.zeros(K)  
      
    for t in range(T):  
        # 从每个臂的Beta分布采样  
        theta_samples = np.random.beta(alpha, beta_)  
        # 选择采样值最大的臂  
        chosen_arm = np.argmax(theta_samples)  
        # 模拟伯努利奖励（1=成功，0=失败）  
        reward = np.random.binomial(1, true_means[chosen_arm])  
        # 更新分布参数  
        alpha[chosen_arm] += reward  
        beta_[chosen_arm] += (1 - reward)  
        rewards[chosen_arm] += reward  
      
    return alpha, beta_, rewards  
  
# 示例：5个臂，真实概率=[0.1, 0.3, 0.5, 0.7, 0.9]  
K = 5  
T = 1000  
true_means = [0.1, 0.3, 0.5, 0.7, 0.9]  
alpha, beta_, rewards = thompson_sampling(K, T, true_means)  
  
print("Alpha (成功次数):", alpha)  
print("Beta (失败次数):", beta_)  
print("总奖励:", rewards)  
print("估计概率:", alpha / (alpha + beta_))  

参考

Exploration Strategies in Deep Reinforcement Learning | Lil’Log

《强化学习》第九讲 探索与利用 - 知乎