强化学习基础概念

强化学习（Reinforcement Learning，RL），是指一类从（与环境）交互中不断学习的问题以及解决这类问题的方法. 强化学习问题可以描述为一个智能体从与环境的交互中不断学习以完成特定目标（比如取得最大奖励值）. 和深度学习类似，强化学习中的关键问题也是贡献度分配问题，每一个动作并不能直接得到监督信息，需要通过整个模型的最终监督信息（奖励）得到，并且有一定的延时性.

强化学习的两个基本对象是 智能体(Agent) 和 环境(Environment) 。智能体可以感知环境的 状态(State) ，执行动作获取反馈的 奖励(Reward) ，并在这个过程中进行学习。而环境是智能体外部的所有事物，受智能体动作的影响并改变其状态，并反馈给智能体奖励。

强化学习的基本概念有：

1. 状态，记为 $s$ ，是对当前环境的描述，可以是离散或连续的。我们记所有状态的集合为 $S$ ，称为 状态空间 。
2. 动作，记为 $a$ ，是对智能体行为的描述，同样可以是离散或连续的。们记所有动作的集合为 $\mathcal{A}$ ，称为 动作空间 。
3. 策略函数 $\pi$ ，描述了智能体在某一状态下所选择的动作。策略可以分为：
   1. 随机策略。$\pi (a|s)$ 描述了在状态 $s$ 下，选择动作 $a$ 的概率。
   2. 确定策略。$\pi (s)$ 描述了在状态 $s$ 下，应该选择什么策略。
      相比于确定策略，随机策略能增加动作的多样性，以更好地探索环境。
4. 奖励函数 $r$ ，描述了在某状态下智能体采取了某动作后，环境给予的奖励。这是一个标量函数。
5. 状态转移概率函数 $p$ ，描述了当智能体在一个状态下采取某动作后，下一个状态的概率分布。

多臂老虎机

多臂老虎机（Multi-Armed Bandit，MAB）是强化学习的入门问题，它的内容为：假设有一台拥有 $K$ 个拉杆的老虎机，第 $i$ 个拉杆拉下后有 $p_i$ 的概率获得 $1$ 单位的奖励 。我们需要设计一个算法，使得在进行 $T$ 次操作后总奖励 $\sum r_t$ 尽量高。

我们定义动作空间 $\mathcal{A}=\{a_1,a_2,...,a_K\}$ ，其中 $a_i$ 表示拉动拉杆 $i$ 。

懊悔

懊悔是执行最优策略时的奖励期望和实际奖励的差值总和：

$$Regre{t}_T=\sum _T[V^{\ast }(s_t)-V^{\pi }(s_t)]$$

其中，$V^{\ast }(s_t)$ 代表 在执行最优策略时奖励的期望，而 $V^{\pi }(s_t)$ 代表在执行策略 $\pi$ 时的奖励。

通过观察懊悔随时间的变化，可以看出一个策略的好坏。

奖励期望的估计

根据概率学知识，拉动某摇杆的期望奖励可以用之前结果的均值来估计。因此在拉动若干次拉杆后，我们可以得到关于每一个拉杆期望奖励的估计（在最初，我们认为所有拉杆的奖励期望都是 $0$ ）。

MAB经典算法

接下来的任务是设计一个策略，以便在每次行动中选择一个拉杆拉下。我们可以将行动分为两类：利用与探索。利用类行动会根据现有的对奖励期望的估计，选取期望奖励最高的摇杆拉下；而探索类行动则会选择其它摇杆拉下，其意义在于更新我们对奖励期望的估计。

下面算法的核心则是平衡利用与探索，以便在得到尽量精确的估计的同时累计更高的奖励。

$ϵ$-贪婪算法

$ϵ$-贪婪算法的核心是，每次以 $ϵ$ 的概率在 $\mathcal{A}$ 中随机选择一个动作，以对环境进行探索；以 $1-ϵ$ 的概率选取奖励期望最高的动作：

$$a_t=\{\begin{array}{ll}\arg max\hat{Q}(a)& ,\mathrm{概}\mathrm{率}\mathrm{为}ϵ\\ \mathrm{从}\mathcal{A}\mathrm{中}\mathrm{随}\mathrm{机}\mathrm{选}\mathrm{择}& ,\mathrm{概}\mathrm{率}\mathrm{为}1-ϵ\end{array}$$

但以恒定的概率 $ϵ$ 进行探索并不是一个好的策略，因为在进行了足够多的探索后，我们对奖励期望的估计会趋于真实值，这时进行探索的概率应该比原来更低。换句话说，探索的概率应该随时间增长而下降；这就引出了 随时间衰减的 $ϵ$-贪婪算法 。相比于原始算法，随时间衰减的 $ϵ$-贪婪算法仅仅将 $ϵ$ 换成了一个关于时间的递减函数，例如 $ϵ=\frac{1}{t}$ 。

上置信界算法

上置信界算法的核心是将一个拉杆被 “利用” 和被 “探索” 的价值进行量化：如果一个拉杆的平均奖励较高，那么显然它被利用的价值就较高；而若一个拉杆被拉动的次数少，说明对它奖励期望的估计就不准确，那么它被探索的价值就高。上置信界算法利用这两个量化的量为每个拉杆打分，并每次选择评分最高的拉杆，以平衡探索与利用。

为了量化 “探索” 的价值，第一个问题是如何定义一个拉杆奖励期望的不确定性。假设拉动了一个拉杆 $n$ 次，其中 $n_r$ 次得到了奖励，那么得到奖励概率的估计就是 $\hat{p}=\frac{n_r}{n}$ ，那么我们定义这个不确定性就是使得 $P(|\hat{p}-p|\ge \delta )$ 足够小的 $\delta$ ，其中 $p$ 是真实的概率。换句话说，我们定义不确定性是使得 $|\hat{p}-p|\le \delta$ 成立的最小的 $\delta$ ，但由于这个式子恒成立不可能，因此我们退而求其次，让 $\delta$ 是使得这个式子成立的概率足够大的 $\delta$ 。

那么如何求出 $\delta$ 呢？我们首先介绍概率论中著名的 霍夫丁不等式：

设 $X_1,X_2,...,X_n$ 是 $n$ 个独立同分布的随机变量，他们的均值 $\bar{X}=\frac{1}{n}\sum _{i=1}^n{X}_i$ 也是一个随机变量，那么 $P(|\bar{X}-E(\bar{X})|\ge \delta )\le 2e^{-2n{\delta }^2}$

将上面的不等式稍稍变形，就得到了：

$$P(|\bar{X}-E(\bar{X})|\le \delta )\ge 1-2e^{-2n{\delta }^2}$$

为了计算 $\delta$ ，我们还需要设定一个概率的上界，也就是前文所说的 “足够大” 的概率。不妨设这个概率是 $\frac{n-1}{n}$ ，其中 $n$ 是拉杆被拉动的次数，那么代入可得：

$$1-2e^{-2n{\delta }^2}=\frac{n-1}{n}$$

解得 $\delta =\sqrt{\frac{\ln 2n}{2n}}$ 。结合上面对奖励期望的估计，可以得到每个拉杆的得分表达式为 $Score=\frac{n_r}{n}+\sqrt{\frac{\ln 2n}{2n}}$ 。而为了更好地平衡探索与利用，我们还可以在 $\delta$ 项前面加上一个可调的超参数系数来加权。同时，为了防止在 $n=0$ 时分母为 $0$ ，我们可以将分母加上 $1$ ，最后得到的表达式为：

$$Score=\frac{n_r}{n+1}+C\sqrt{\frac{\ln 2n}{2n+1}}$$

根据这个表达式，每次选出得分最高的拉杆拉下即可。

汤普森采样

汤普森采样是另一个MAB的经典算法，它使用 $Beta$ 分布来为每个拉杆获得奖励的概率建模，并在每次获得反馈后更新 $Beta$ 分布的参数。在选择拉杆时，汤普森采样从每个拉杆的 $Beta$ 分布中采样，并选择采样结果最高的拉杆拉下。

为什么汤普森采样能平衡利用和探索呢？若一个拉杆被拉下的次数较少，它对应的 $Beta$ 分布的曲线就会比较宽；反之，对应的曲线就会比较窄。这样，曲线的宽和窄就自然地度量了一个拉杆不确定性的多少。汤普森采样的 “探索” 方面提现在，探索较少的拉杆会有更大可能采样到高于获得奖励概率的期望的概率，因此提高了它被选中的概率；而它的 “利用” 方面则体现在，如果一个拉杆成功率高，那么对它的 $Beta$ 分布进行采样时就更可能得到高概率。