模型基础

强化学习和监督学习，非监督学习

强化学习只有奖励值，但是这个奖励值和监督学习的输出值不一样，它不是事先给出的，而是延后给出的。
强化学习的每一步与时间顺序前后关系紧密。而监督学习的训练数据之间一般都是独立的，没有这种前后的依赖关系。
非监督学习是没有输出值也没有奖励值的，它只有数据特征。同时和监督学习一样，数据之间也都是独立的，没有强化学习这样的前后依赖关系。

强化学习基本要素

环境的状态 $S$，$t$ 时刻的状态为 $S_t$
个体的动作 $A$，$t$ 时刻采取的动作为 $A_t$
环境的奖励 $R$，$t$ 时刻在状态 $S_t$ 采取的动作 $A_t$ 对应的奖励 $R_{t+1}$ 会在 $t+1$ 时刻得到
个体的策略 (policy) $\pi$ 代表个体采取动作的依据，即个体会根据策略来选择动作。常见的策略表达方式是一个条件概率分布 $\pi(a|s)$ 表示在状态 $s$ 采取动作 $a$ 的概率，即 $\pi(a|s)=P(A_t=a|S_t=s)$，此时概率大的动作可能就被采取
个体在策略 $\pi$ 和状态 $s$ 时，采取动作后的价值(value) $v_{\pi}(s)$，这个价值一般是一个期望函数。需要综合考虑当前的延时奖励和后续的延时奖励

$$ v_{\pi}(s) = E_{\pi}(R_{t+1}+\gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t=s) $$

$\gamma$ 是衰减因子，如果是 $0$，则是贪婪法，只关注当前延时奖励；如果是 $1$，则后续所有奖励和当前一直同仁。通常选择一个 $0$ 到 $1$ 之间的数使得当前延时奖励的权重比后续奖励要大。
环境的状态转化模型，即在状态 $s$ 下采取动作 $a$ 转到下一状态 $s’$ 的概率，记为 $P_{s s’}^a$
探索率 $\epsilon$ 表示我们在训练最优动作时有一定概率不选择当前迭代价值最大的动作，而选择其他的动作，避免错过一些较好但是没有被执行过的动作。

马尔可夫决策过程 (MDP)

Why

环境的状态转化模型既与上一个状态有关，还与上上个状态，以及上上上个状态有关，这样会导致环境转化模型过于复杂难以建模。因此需要简化！简化的方法就是假设状态转化的马尔科夫性，也就是假设转化到下一个状态 $s’$ 的概率仅与上一个状态 $s$ 有关，与之前的状态无关。

$$ P_{ss'}^a = E(S_{t+1}=s'|S_t=s,A_t=a) $$

除了对于环境的状态转化模型这个因素做马尔科夫假设外，我们还对强化学习第四个要素个体的策略 (policy) $\pi$ 也做了马尔科夫假设。即在状态 $s$ 时采取动作 $a$ 的概率仅与当前状态 $s$ 有关，与其他的要素无关。

$$ \pi(a|s) = P(A_t=a|S_t=s) $$

同时，价值函数也仅依赖于当前的状态

$$ v_{\pi}(s) = E_{\pi}(G_t|S_t=s) = E_{\pi}(R_{t+1}+\gamma R_{t+2} + ... |S_t = s) $$

其中 $G_t$ 代表收获，是一个MDP从某一个状态开始采样直到终止状态时所有衰减奖励之和。

MDP的价值函数和贝尔曼方程

先前的价值函数没有考虑到所采用的动作 $a$ 带来的价值影响，因此引入了动作价值函数 $q_{\pi}(s,a)$，即

$$ q_{\pi}(s,a) = E_{\pi}(G_t|S_t=s, A_t=a) $$

根据价值函数的表达式，可以推到出价值函数基于状态的递推关系

\begin{align} v_{\pi}(s) &= E_{\pi}(R_{t+1} + \gamma R_{t+2} + ...|S_t=s)\\ &= E_{\pi}(R_{t+1} +\gamma(R_{t+2}+ \gamma R_{t+3}...)|S_t=s)\\ &= E_{\pi}(R_{t+1}+\gamma G_{t+1}|S_t=t)\\ &= E_{\pi}(R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t=s) \end{align}

也就是说 $t$ 时刻的状态和 $t+1$ 时刻的状态是满足递推关系的，这个递推式子也称为贝尔曼方程。一个状态的价值由该状态的奖励以及后续状态价值按一定的衰减比例联合组成。

同理也可以得到动作价值函数的贝尔曼方程。

$$ q_{\pi}(s,a) = E_{\pi}(R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1})|S_t=s, A_t=a) $$

状态价值函数与动作价值函数的递推关系

根据定义可以得到

$$ v_{\pi}(s) = \sum_{a\in A}\pi(a|s)q_{\pi}(s,a) $$

也就是说，状态价值函数是所有动作价值函数基于策略 $\pi$ 的期望。通俗说就是某状态下所有状态动作价值乘以该动作出现的概率，最后求和，就得到了对应的状态价值。

利用贝尔曼方程，可以得到从状态价值函数表示动作价值函数

$$ q_{\pi}(s,a) = R_{s}^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') $$

通俗说就是状态动作价值有两部分相加组成，第一部分是即时奖励，第二部分是环境所有可能出现的下一个状态的概率乘以该下一状态的状态价值，最后求和，并加上衰减。

把上面两个式子结合起来可以得到

$$ v_{\pi}(s) = \sum_{a \in A} \pi(a|s) (R_s^a + \gamma \sum_{s' \in S}P_{ss'}^a v_{\pi}(s'))\\ q_{\pi}(s,a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \sum_{a' \in A} \pi(a'|s') q_{\pi}(s',a') $$

最优价值函数

解决强化学习问题意味着要寻找一个最优策略让个体在与环境交互过程中获得始终比其它策略都要多的收获

如何比较策略的优劣呢？一般是通过对应的价值函数来比较的

$$ v_*(s) = \max_{\pi} v_{\pi}(s) $$

也可以定义最优动作价值函数是所有策略下产生的众多动作状态价值函数中的最大者

$$ q_*(s,a) = \max_{\pi} q_{\pi}(s,a) $$

对于最优的策略，基于动作价值函数我们可以定义为

$$ \pi_*(a|s) = 1, \quad if \quad a = \arg \max_{a\in A} q_*(s,a) $$

只要我们找到了最大的状态价值函数或者动作价值函数，对应的策略就是强化学习的解。且最大的状态价值函数和最大的动作价值函数满足

$$ v_*(s) = \max_a q_*(s,a)\\ q_*(s,a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_*(s') $$

动态规划求解强化学习

DP 和 RL 的关系

动态规划的关键点有两个：

问题的最优解可以由若干小问题的最优解构成，即通过寻找子问题的最优解来得到问题的最优解。
可以找到子问题状态之间的递推关系，通过较小的子问题状态递推出较大的子问题的状态。

而强化学习的问题恰好是满足这两个条件的。

RL 两个基本问题

预测：给定策略求解该策略下的状态价值函数
控制：求解最优的价值函数和策略

策略评估求解预测问题

求解给定策略的状态价值函数通常叫做策略评估 (Policy Evaluation)。假设我们在第k轮迭代已经计算出了所有的状态的状态价值，那么在第 $k+1$ 轮我们可以利用第k轮计算出的状态价值计算出第 $k+1$ 轮的状态价值。这是通过贝尔曼方程来完成的，即：

$$ v_{k+1}(s) = \sum_{a\in A}\pi(a|s) (R_s^a + \gamma \sum_{s'\in S} P_{ss'}^a v_k(s')) $$

每一轮可以对计算得到的新的状态价值函数再次进行迭代，直至状态价值的值改变很小(收敛)，那么我们就得出了预测问题的解，即给定策略的状态价值函数。

策略迭代求解控制问题

一种可行的方法就是根据我们之前基于任意一个给定策略评估得到的状态价值来及时调整我们的动作策略，这个方法我们叫做策略迭代 (Policy Iteration)。

最简单的方法就是贪婪法。考虑一种如下的贪婪策略：个体在某个状态下选择的行为是其能够到达后续所有可能的状态中状态价值最大的那个状态。在策略迭代过程中，我们循环进行两部分工作:

Step 1. 是使用当前策略 $\pi_{opt}$ 评估计算当前策略的最终状态价值 $v_{opt}$，

Step 2. 根据状态价值 $v_{opt}$ 根据一定的方法（比如贪婪法）更新策略 $\pi_{opt}$，接着回到第一步，一直迭代下去，最终得到收敛的策略 $\pi_{opt}$ 和状态价值 $v_{opt}$。

价值迭代求解控制问题

每次等待状态价值收敛再去更新策略是不必要的，可以随着状态价值的迭代及时调整策略，这样可以大大减少迭代次数。

$$ v_{k+1}(s) = \max_{a\in A} (R_s^a + \gamma \sum_{s' \in S}P_{ss'}^a v_k(s')) $$

现在价值每次更新倾向于贪婪法选择的最优策略对应的后续状态价值，这样收敛更快。

动态规划求解强化学习问题小结

主要就是利用贝尔曼方程来迭代更新状态价值，用贪婪法之类的方法迭代更新最优策略。但是当问题规模很大的时候，动态规划算法将会因贝尔曼维度灾难而无法使用。

蒙特卡罗法 (MC) 求解强化学习

由于动态规划法需要在每一次回溯更新某一个状态的价值时，回溯到该状态的所有可能的后续状态。导致对于复杂问题计算量很大。同时很多时候，我们连环境的状态转化模型 $P$ 都无法知道，这时动态规划法根本没法使用。

不基于模型的强化学习问题定义

当模型状态转化概率矩阵 $P$ 始终是已知的，即 MDP 已知，对于这样的强化学习问题，我们一般称为基于模型的强化学习问题。不过有很多强化学习问题，我们没有办法事先得到模型状态转化概率矩阵 $P$，这时如果仍然需要我们求解强化学习问题，那么这就是不基于模型的强化学习问题了。

蒙特卡罗法

蒙特卡罗法通过采样若干经历完整 (这个序列必须是达到终点的) 的状态序列 (episode) 来估计状态的真实价值。和动态规划比，它不需要依赖于模型状态转化概率。二是它从经历过的完整序列学习，完整的经历越多，学习效果越好。

蒙特卡罗法求解强化学习预测问题

一个给定策略 $\pi$ 的完整状态序列如下：

$$ S_1,A_1,R_2,S_2,A_2,…,R_T,S_T $$

根据价值函数的定义可以看出每个状态的价值函数等于所有该状态收获的期望，同时这个收获是通过后续的奖励与对应的衰减乘积求和得到。那么对于蒙特卡罗法来说，如果要求某一个状态的状态价值，只需要求出所有的完整序列中该状态出现时候的收获再取平均值即可近似求解。

$$ G_t = R_{t+1} + \gamma R_{t+2} +... \gamma ^{T-t-1} R_T\\ v_{\pi}(s) = average(G_t),\quad s.t. S_t =s $$

有几个点可以优化考虑:

同样一个状态可能在一个完整的状态序列中重复出现:首次访问 (first visit) 和每次访问 (every visit) 蒙特卡罗法
累进更新平均值（incremental mean) 避免保存所有该状态的收获值。因为上面预测问题的求解里有一个 average 公式，意味着要保存所有该状态的收获值之和最后求平均。一个较好的方式是在迭代计算收获均值，即每次保存上一轮迭代得到的收获均值和次数。

$$ \mu_k = \frac{1}{k} (x_k + \sum_{j=1}^{k-1}x_j) = \mu_{k-1} + \frac{1}{k}(x_k - \mu_{k-1}) $$

蒙特卡罗法求解强化学习控制问题

和动态规划比，蒙特卡罗法不同之处体现在三点：

预测问题策略评估的方法不同。
蒙特卡罗法一般是优化最优动作价值函数 $q_{opt}$，而不是状态价值函数 $v_{opt}$。
动态规划一般基于贪婪法更新策略。而蒙特卡罗法一般采用 $\epsilon$−贪婪法更新。为了使算法可以收敛，一般 $\epsilon$ 会随着算法的迭代过程逐渐减小，并趋于0。这样在迭代前期，我们鼓励探索，而在后期，由于我们有了足够的探索量，开始趋于保守，以贪婪为主，使算法可以稳定收敛。

算法流程 输入：状态集 $S$，动作集 $A$，即时奖励 $R$，衰减因子 $\gamma$，探索率 $\epsilon$

输出：最优的动作价值函数和最优策略

Step 1. 初始化所有动作价值 $Q(s,a)=0$，状态次数 $N(s,a)=0$，采样次数 $k=0$，随机初始化一个策略 $\pi$ Step 2. $k=k+1$，基于策略 $\pi$ 进行第 $k$ 次蒙特卡洛采样，得到一个完整的状态序列： $$ S_1,A_1,R_2,A_2,…,R_T,S_T $$ Step 3. 对于该状态序列里出现的每一状态行为对 $(S_t,A_t)$ 计算其收获 $G_t$，更新其计数 $N(s,a)$ 和行为价值函数 $Q(s,a)$

$$ G_t = R_{t+1} + \gamma R_{t+2} + ... \gamma^{T-t-1}R_T\\ N(S_t,A_t)=N(S_t,A_t)+1\\ Q(S_t,A_t) = Q(S_t,A_t) + \frac{1}{N(S_t,A_t)}(G_t - Q(S_t,A_t)) $$

Step 4. 基于新计算出的动作价值，更新当前的 $\epsilon$ 贪婪策略: $$ \epsilon = \frac{1}{k} $$ 且

\begin{equation} \pi(a | s)=\left\{\begin{array}{ll}\epsilon / m+1-\epsilon & \text { if } a^{*}=\arg \max _{a \in A} Q(s, a) \\ \epsilon / m & \text { else }\end{array}\right. \end{equation}

其中 $m$ 为可选行为的个数。

Step 5. 如果所有的 $Q(s,a)$ 收敛则达到最优，否则返回第二步。

小结

蒙特卡罗法是不基于模型的强化问题求解方法。它可以避免动态规划求解过于复杂，同时还可以不事先知道环境转化模型，因此可以用于海量数据和复杂模型。但是它也有自己的缺点，这就是它每次采样都需要一个完整的状态序列。如果我们没有完整的状态序列，或者很难拿到较多的完整的状态序列，这时候蒙特卡罗法就不太好用了。

用时序差分法（TD）求解强化学习

时序差分简介

时序差分法和蒙特卡罗法类似，都是不基于模型的强化学习问题求解方法。并且它不需要使用完整状态序列求解强化学习问题。

由于我们没有完整的状态序列，需要近似求出某个状态的收获。根据贝尔曼方程

$$ v_{\pi}(s)=E_{\pi}(R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t = s) $$

我们可以用 $R_{t+1}+\gamma v_{\pi}(S_{t+1})$ 来近似收获 $G_t$。一般我们把它称作 TD 目标值。

时序差分 TD 的预测问题求解

时序差分的预测问题和蒙特卡罗法相似，主要有两点不同：

收获 $G_t$ 的表达式不同

$$ G(t)=R_{t+1} + \gamma V(S_{t+1}) $$

迭代的系数不同（没有完整的序列，因此没有对应的次数$N(S_t)$）

$$ V(S_t) = V(S_t) + \alpha (G_t - V(S_t))\\ Q(S_t,A_t) = Q(S_t,A_t) + \alpha (G_t - Q(S_t,A_t)) $$

时序差分法在知道结果之前就可以学习，而蒙特卡罗则需要等到最后结果才能学习；时序差分是基于即时奖励和下一状态的预估价值来代替当前状态在状态序列结束时可能得到的收获，是当前状态价值的有偏估计（蒙特卡罗是无偏估计），但是方差比蒙特卡罗要低。现在主流的强化学习求解方法都是基于时序差分的。

n 步时序差分

我们也可以使用多步近似收获 $G_t$

$$ G_{t}^{(n)} = R_{t+1} + \gamma R_{t+2} + ... \gamma^n V(S_{t+n}) $$

当 $n$ 越来越大也就是说趋于使用完整的状态序列，就等价于蒙特卡罗法了。

时序差分的控制问题

时序差分的在线控制 (on-policy) 算法最常见的是 SARSA 算法，离线控制 (off-policy) 最常见的是 Q-Learning 算法。

SARSA 算法概述

作为SARSA算法的名字本身来说，它实际上是由S,A,R,S,A几个字母组成的。而S,A,R分别代表状态，动作，奖励。在迭代的时候，我们首先基于 $\epsilon$−贪婪法在当前状态 $S$ 选择一个动作 $A$，这样系统会转到一个新的状态 $S’$, 同时给我们一个即时奖励 R, 在新的状态 $S’$，我们会基于 $\epsilon$−贪婪法在状态 $S’$ 选择一个动作 $A’$，但是注意这时候我们并不执行这个动作 $A’$，只是用来更新的我们的价值函数，价值函数的更新公式是：

$$ Q(S,A)= Q(S,A) + \alpha(R+\gamma Q(S',A') - Q(S,A)) $$

这里和蒙特卡罗法求解在线控制问题的迭代公式的区别主要是，收获 $G_t$ 的表达式不同。

算法流程

算法输入：迭代轮数 $T$，状态集 $S$, 动作集 $A$, 步长 $\alpha$，衰减因子 $\gamma$, 探索率$\epsilon$

输出：所有的状态和动作对应的价值 $Q$

Step 1. 随机初始化所有的状态和动作对应的价值 $Q$，对于终止状态其 $Q$ 值初始化为0.

Step 2. for i from 1 to T，进行迭代。

　　a) 初始化 $S$ 为当前状态序列的第一个状态。设置 $A$ 为 $\epsilon$−贪婪法在当前状态 $S$ 选择的动作。

　　b) 在状态 $S$ 执行当前动作 $A$, 得到新状态 $S’$ 和奖励 $R$

　　c) 用 $\epsilon$−贪婪法在状态 $S’$ 选择新的动作 $A’$

　　d) 更新价值函数 $𝑄(𝑆,𝐴)$:

$$ Q(S,A)= Q(S,A) + \alpha(R+\gamma Q(S',A') - Q(S,A)) $$

　　e) $𝑆=𝑆′, 𝐴=𝐴′$

　　f) 如果 $S’$ 是终止状态，当前轮迭代完毕，否则转到步骤b)

这里有一个要注意的是，步长 $\alpha$ 一般需要随着迭代的进行逐渐变小，这样才能保证动作价值函数 $Q$ 可以收敛。

Q-Learning 算法概述

时序差分法的控制问题，可以分为两类，一类是在线控制，即一直使用一个策略来更新价值函数和选择新的动作，比如 SARSA, 而另一类是离线控制，会使用两个控制策略，一个策略用于选择新的动作，另一个策略用于更新价值函数。这一类的经典算法就是Q-Learning。

对于Q-Learning，我们会使用 $\epsilon$−贪婪法来选择新的动作，这部分和SARSA完全相同。但是对于价值函数的更新，Q-Learning使用的是贪婪法，而不是SARSA的 $\epsilon$−贪婪法。这一点就是 SARSA 和 Q-Learning 本质的区别。

基于状态 $S$，用 $\epsilon$−贪婪法选择到动作$A$, 然后执行动作 $A$，得到奖励 $R$，并进入状态 $S’$，此时，如果是SARSA，会继续基于状态 $S’$，用 $\epsilon$−贪婪法选择 $A’$, 然后来更新价值函数。但是Q-Learning则不同, 它基于状态 $S’$，没有使用 $\epsilon$−贪婪法选择 $A’$，而是使用贪婪法选择 $A’$，也就是说，选择使 $𝑄(𝑆′,𝑎)$ 最大的 $a$ 作为 $A’$ 来更新价值函数。此时选择的动作只会参与价值函数的更新，不会真正的执行。价值函数更新后，新的执行动作需要基于状态 $S’$，用 $\epsilon$−贪婪法重新选择得到。这一点也和SARSA稍有不同。对于SARSA，价值函数更新使用的 $A’$ 会作为下一阶段开始时候的执行动作。