11&12.md

# Lecture 11&12 Exploration and Exploitation

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

## 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$ 动作值 $Q(a)=\mathbb{E}[r|a]$

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