11&12.md

# Lecture 11&12 Exploration and Exploitation

# 课时11&12 探索与利用 2019.02.20 & 2019.02.25 & 2019.02.27

## 1. 介绍（Introduction）

我们之前讨论过强化学习算法的设计，特别地，除了渐近收敛之外，我们还希望获得良好的性能。在教育、医疗或机器人等许多实际应用中，渐近收敛速度并不是比较强化学习算法的有效指标。为实现良好的现实世界中的表现，我们希望能够快速收敛到好的策略，这有赖于良好的策略探索。

在线决策涉及到探索（exploration）与利用（exploitation）之间的基本权衡。利用（通过最大化未来收益来）制定最佳的可能的策略，而探索则采取次优动作来收集信息。虽然次优动作必然会导致近期的奖励减少，但它可能使得我们学习更好的策略，从长远来看能够改进策略。

## 2. （Multi-Armed Bandits）

我们首先讨论在（multi-armed bandits, MABs）背景下，而非完全 MDPs 背景下的探索。MAB 是元组 $(A,R)$，这里 $A$ 表示动作的集合，$R$ 为每个动作对应奖励的概率分布 $R^{a}(r)=P(r|a)$。在每个时间步，行为体选择一个动作 $a_{t}$。像在 MDPs 中那样，行为体的目的是最大化累积的奖励。但由于不存在状态转移，所以不存在延迟的奖励或结果的概念。

令 $Q(a)=\mathbb{E}[r|a]$ 表示采取动作 $a$ 的真实期望奖励。我们考虑估计 $\hat{Q}_{t}(a)\approx Q(a)$ 的算法，该值通过蒙特卡洛评估来估计：

$$
\hat{Q}_ {t}(a) = \frac{1}{N_{t}(a)}\sum_{t=1}^{T} r_{t} {\bf{1}} (a_{t}=a) = \hat{Q}_ {t-1}(a)+\frac{1}{N_{t}(a)}(r_{t}-\hat{Q}_ {t-1}(a))，
\tag{1}
$$

这里 $N_{t}(a)$ 为动作 $a$ 在时间 $t$ 被采用过的次数。第二个等式用于递增地计算 $\hat{Q}_{t}$。

贪婪策略（greedy algorithm）选择有最大估计价值的动作，$a_{t}^{\ast}=\mathop{\arg\max}_ {a\in A} \hat{Q}_ {t}(a)$。然而，贪婪的做法可能使得次优的动作永远无法被采用。像在 MDPs 中那样，我们也可以使用（固定的）$\epsilon$-贪婪算法（$\epsilon$-greedy algorithm），即以 $1-\epsilon$ 的概率选择贪婪动作，以 $\epsilon$ 的概率选择随机动作。另一个算法是衰减 $\epsilon_{t}$-贪婪算法（decaying $\epsilon_{t}$-greedy algorithm），这里 $\epsilon_{t}$ 按照一定规律衰减。

一个简单的基于 $\epsilon$-贪婪算法的方法是乐观初始化（optimistic initialization），它讲所有 $a\in A$ 的 $\hat{Q}_ {0}(a)$ 初始化为大于真值 $Q(a)$ 的某个值，也就是说，我们开始时对所有的动作选择“非常乐观”。在每一步我们可以使用贪婪（或 $\epsilon$-贪婪）的方法来选择动作，由于真正的奖励都低于我们的初始估计，所以被采用过的动作的估计值 $\hat{Q}$ 就会减小，这就鼓励了行为体对那些未被采用过的、$\hat{Q}$ 值仍旧大的动作进行探索。因此，所有的动作都会被至少尝试一次，可能多次。此外，我们可以初始化 $N_{0}(a)>0$ 以调整乐观初始化向真值收敛的速度。

### 2.1 遗憾（Regret）

这些探索策略自然会产生一个问题，即我们应该使用哪种标准来比较它们。可能的标准包括经验性的表现（尽管这依赖于环境）、渐近收敛的保证、有限采样的保证或 PAC 的保证。在 MAB 文献中的标准通常是遗憾（regret），我们现在定义遗憾以及相关的量。

$\bullet$ 动作值（action-value）$Q(a)=\mathbb{E}[r|a]$

$\bullet$ 最优值（optimal value）$V^{\ast}=Q(a^{\ast})=\mathop{\max}_{a\in A}Q(a)$

$\bullet$ 差距（gap）$\Delta_{a}=V^{\ast}-Q(a)$

$\bullet$ 遗憾（regret）$l_{t}=\mathbb{E}[V^{\ast}-Q(a_{t})]$

$\bullet$ 总遗憾（total regret）$L_{t}=\mathbb{E}[\sum_{\tau=1}^{t}(V^{\ast}-Q(a_{\tau}))]=t\cdot V^{\ast} - \mathbb{E}[\sum_{\tau=1}^{t}Q(a_{\tau})]$

因此，最小化总遗憾等价于最大化累积的奖励。如果我们定义 $\overline{N}_{t}(a)$ 为动作 $a$ 的期望选择次数，那么总遗憾就是差距和动作选择次数的函数：

$$
L_{t} = \mathbb{E}[\sum_{\tau=1}^{t}(V^{\ast}-Q(a_{\tau}))]
\tag{2}
$$

$$
= \sum_{a\in A} \mathbb{E}[N_{t}(a)] (V^{\ast}-Q(a))
\tag{3}
$$

$$
= \sum_{a\in A} \overline{N}_ {t}(a) \Delta_{a}
\tag{4}。
$$

高质量的算法可以保证对于大的差距，动作选择次数比较小。然而，差距并不能被事先知道，而且必须通过与 MAB 交互被习得。

### 2.2 遗憾界限（Regret Bounds）

我们希望保证某些算法的遗憾是可以量化并且有界的。遗憾界限有两种类型：与问题相关的遗憾界限和与问题无关的遗憾界限。与问题相关的遗憾界限是动作选择次数与差距的函数，与问题无关的遗憾界限是 $T$ 的函数，这里 $T$ 为算法执行的总步骤数。

永远探索或永远选择次优操作的算法都会经历线性遗憾（linear regret）。因此，达到次线性遗憾（sublinear regret）是可取的。前面讨论过的算法的遗憾界限如下：

$\bullet$ 贪婪（greedy）：线性总遗憾

$\bullet$ 常值 $\epsilon$-贪婪（constant $\epsilon$-greedy）：线性总遗憾

$\bullet$ 衰减 $\epsilon$-贪婪（decaying $\epsilon$-greedy）：次线性遗憾但 $\epsilon$ 的衰减进度需要差距的知识

$\bullet$ 乐观初始化（optimistic initialization）：如果初始值足够乐观则为次线性遗憾，否则为线性遗憾

为了解问题的严重性，我们先来探讨遗憾的下界。一般来说，任何算法的性能都取决于最优动作与其他动作的相似性。困难的问题会有相似的动作，但方式略有不同，这可以由差距 $\Delta_{a}$ 和分布的相似性（通过 KL 散度）$KL(R^{a}\lVert R^{a^{\ast}})$ 来描述，然后，我们可以对渐近总遗憾建立一个界限。

**定理 1**（Lai and Robbins，1985）对于 MAB，任何算法在总遗憾上的渐近下界至少为

$$
\lim_{t\to\infty} L_{t}\geq \log t \sum_{a|\Delta_{a}>0}\frac{\Delta_{a}}{KL(R^{a}\lVert R^{a^{\ast}})}。
$$

### 2.3 乐观面对不确定性（Optimism in the Face of Uncertainty）

**图 1**

考虑图 1，它显示了一些动作的估计分布。我们应该选择哪个动作？面对不确定性时的乐观原则是，我们应该把选择偏向于可能是好的的动作。直觉上，这将使我们了解到这个动作要么的确会带来高额回报，要么并不如我们期望的那么好，而且也会使我们了解到关于我们的问题的有价值的信息。

在这个方法的基础上，置信上界算法产（Upper Confidence Bound Algorithm）生了，其过程如下。首先，我们对每个动作值估计一个置信上界 $\hat{U}_ {t}(a)$ 使得大概率 $Q(a)\leq\hat{Q}_ {t}(a)+\hat{U}_ {t}(a)$ 成立，这依赖于动作 $a$ 被选择的次数。然后我们选择最大化置信上界的动作

$$
a_(t)=\mathop{\arg\max}_ {a\in A}(\hat{Q}_ {t}(a)+\hat{U}_ {t}(a))，
\tag{5}
$$

这可以由 Hoeffding 不等式（Hoeffding's inequality）推导得出。

<span id="thm2">**定理 2**</span>（Hoeffding 不等式）令 $X_{1},...,X_{t}$ 为在区间 $[0,1]$ 中的独立同分布（i.i.d.）随机变量，$\overline{X}=\frac{1}{t}\sum_{\tau=1}^{t}X_{\tau}$ 为平均值，$u$ 为一个常量。那么，

$$
P[ \mathbb{E}[x]>\overline{X}_{t}+u] \leq e^{-2tu^{2}}。
$$

对 MAB 问题应用[定理 2](#thm2)，我们得到：

$$
P[Q(a)>\hat{Q}_ {t}(a)+U_ {t}(a)] \leq e^{-2N_{t}(a)U_{t}(a)^{2}}。
\tag{6}
$$