强化学习
强化学习
- 基本概念
- 智能体(agent)和环境(environment)：强化学习研究的问题是智能体与环境交互的问题，智能体把它的动作输出给环境，环境取得这个动作后会进行下一步，把下一步的观测与这个动作带来的奖励返回给智能体，这样的交互会产生很多观测，智能体的目的就是从这些观测之后学到能最大化奖励的策略。
- 序列决策： 智能体的目的就是选取一系列的动作带来最大化奖励，所以这些选取的动作必须有长期的影响。与环境交互的过程中，智能体会获得很多观测，针对每一个观测，智能体会采取一个动作，也会得到一个奖励，所以历史是观测、动作、奖励的序列。
- 奖励：奖励是由环境给的一种标量的反馈信号，这种信号可显示智能体在某一部采取某个策略的表现如何。强化学习的目的就是最大化智能体可以活得的奖励，智能体在环境里面存在的目的就是最大化它的期望的累积奖励。
- 状态是对世界的完整描述，不会隐藏世界的信息，观测是对状态的部分描述。
对于一个强化学习智能体，它可能有一个或多个如下的组成成分：
- 策略。智能体会用策略来选取下一步的动作，是一个函数，用于把输入的状态变成动作。分为随机性策略和确定性策略。随机性策略就是 \(\pi\) 函数，输入一个状态，输出一个概率，这个概率是智能体所有动作的概率，然后对这个概率分布进行采样，可得到智能体将采取的动作，确定性策略就是智能体直接采取最有可能的动作。通常情况下，强化学习一般使用随机性策略，随机性策略有很多优点。
- 价值函数。用价值函数对当前状态进行评估。价值函数用于评估智能体进入某个状态后，价值函数用于评估稚嫩git进入某个状态后，可以对后面的奖励带来多大的影响。价值函数越大，说明智能体进入这个状态越有利。价值函数的值是对未来奖励的预测，我们用它评估状态的好坏。价值函数的定义为：
\[V_\pi(s)\doteq\mathbb{E}_\pi\left[G_t\mid s_t=s\right]=\mathbb{E}_\pi\left[\sum_{k=0}^\infty\gamma^kr_{t+k+1}\mid s_t=s\right],\text{对于所有的}s\in S\]
还有一种价值函数，Q函数，Q函数里面包含两个变量：动作和状态，定义为：
\[Q_\pi(s,a)\doteq\mathbb{E}_\pi\left[G_t\mid s_t=s,a_t=a\right]=\mathbb{E}_\pi\left[\sum_{k=0}^\infty\gamma^kr_{t+k+1}\mid s_t=s,a_t=a\right]\]
- 模型。模型表示智能体对环境的状态进行理解，它决定了环境中世界的运行方式。模型决定了下一步的状态，下一步的状态取决于当前的状态以及当前采取的动作。它由状态转移概率和奖励函数两个部分组成。状态转移概率即：
\[p_{ss^{\prime}}^a=p\left(s_{t+1}=s^{\prime}\mid s_t=s,a_t=a\right)\]
奖励函数是指在当前状态采取了某个动作，可以得到多大的奖励，
\[R(s,a)=\mathbb{E}\left[r_{t+1}\mid s_t=s,a_t=a\right]\]
当有了策略、价值函数和模型3个组成部分后，就形成了一个马尔可夫决策过程。
根据智能体学习的事物不同，可以把智能体进行归类。基于价值的智能体显式地学习价值函数，隐式地学习它的策略,策略是其从学到的价值函数里面推算出来的，基于策略的智能体直接学习策略，给它一个状态，它就会输出对应动作的概率。基于策略的智能体并没有学习价值函数。把基于价值的智能体和基于策略的智能体结合起来就有了演员-评论员智能体(actor-critic agent)。这一类智能体把策略和价值函数都学习了，然后通过两者的交互得到最佳的动作。
强化学习可以划分为基于策略的方法和基于价值的方法。决策方式是智能体在给定状态下 从动作集合中选择一个动作的一句，它是静态的，不随状态变化而变化。在基于策略的强化学习方法中，智能体会制定一套动作策略，并根据这个策略进行操作。强化学习算法直接对策略进行优化，是制定的策略能够获取最大的奖励。而在基于价值的强化学习方法中，智能体不需要指定显示的策略，它维护一个价值表格和价值函数，并通过这个价值表格或价值函数来选取价值最大的动作。基于价值迭代的方法只能应用在不连续的、离散的环境下，对于动作集合规模庞大、动作连续的场景，很难学到较好的结果。基于价值的强化学习算法由Q学习等，而基于策略的强化学习算法有策略梯度算法等。此外，演员-评论员算法同时使用策略和价值评估来做出决策。其中，智能体会根据策略做出动作，而价值函数会对做出的动作给出价值，这样可以取得更好的效果。
我们可以通过智能体到底有没有学习环境模型来对智能体进行分类：有模型(model-based)强化学习智能体通过学习状态的转移来采取动作，免模型(model-free)强化学习智能体没有去直接估计状态的转移，也没有得到环境的具体转移变量，通过学习价值函数和策略函数进行决策。针对是否需要对真实环境建模，强化学习可以分为有模型强化学习和免模型强化学习。有模型强化学习是指根据环境中的经验，构建一个虚拟世界，同时在真实环境中和虚拟世界中学习，免模型强化学习是指不对环境进行建模，直接与真实环境进行交互来学习到最优策略。
单步强化学习任务对应于一个理论模型，即"K" 臂赌博机，也成为多臂赌博机，有K个摇臂，赌徒在投入下一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率突出硬币，探索和利用两者是牟敦的，因为尝试次数有限，这是强化学习面临的探索利用窘境。
马尔可夫性质：指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。将来的状态和过去状态是独立的，只取决于现在。马尔可夫过程是一组具有马尔可夫性质的随机变量序列。离散时间的马尔可夫过程也成为马尔科夫链。马尔可夫奖励过程是马尔科夫链加上奖励函数。
贝尔曼方程: 定义了当前状态与未来状态之间的关系，未来奖励的折扣总和加上即时奖励，就组成了贝尔曼方程： \[V(s)=\underbrace{R(s)}_{\text{即时奖励}}+\underbrace{\gamma\sum_{s^{\prime}\in S}p\left(s^{\prime}\mid s\right)V\left(s^{\prime}\right)}_{\text{未来奖励的折扣总和}}\]。贝尔曼方程就是当前状态与未来状态的迭代关系。表示当前状态的价值函数可以通过下个状态的价值函数来计算。
\[\begin{aligned} \mathrm{V} & =R+\gamma PV \\ \mathrm{IV} & =R+\gamma PV \\ (I-\gamma P)V & =R \\ \mathrm{V} & =(I-\gamma\boldsymbol{P})^{-1}\boldsymbol{R} \end{aligned}\]
\[V=(I-\gamma P)^{-1}R\]
可以将迭代的方法应用于状态非常多的马尔可夫奖励过程，例如动态规划、蒙特卡洛、时序差分(动态规划和蒙特卡洛结合)。动态规划的方法是基于后继状态价值估计来更新现在状态价值的估计，一直迭代贝尔曼方程，指导价值函数收敛。
马尔可夫决策过程：智能体与环境交互进行学习最终实现目标的过程就是马尔可夫决策过程(Markov Decision Process,MDP)：智能体与环境交互的过程：在t时刻，智能体在当前状态\(S_t\)采取动作 \(A_t\)。在下一时刻 \(t+1\)，智能体接收到环境反馈的对于动作 \(A_t\)的奖励 \(R_{t+1}\)，以及该时刻状态 \(S_{t+1}\)。从而，MDP和智能体共同给出一个轨迹： \[S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, S_3, A_3, ...\] \(S_t\)是有限状态的集合，\(A_t\)是有限动作的集合，\(P\)是基于环境的状态转移矩阵：其中每一个项为智能体在某个状态下\(s\)下，采取动作 \(a\)后，与环境交互后转移到其它状态 \(s'\)的概率值，表示为 \(P(S_{t+1}=s'|s_t = s, a_t = a)\)。
R是奖励函数：智能体在某个状态\(s\)下，采取动作a后，与环境交互后所获得的奖励，表示为\(R(s_t = s, a_t = a)\)。 \(\gamma\)是折扣因子(discounted factor), 取值区间为[0,1]。
所以MDP过程可以表示为 \((S,A,P,R,\gamma)\)，如果该过程中的状态转移矩阵\(P\)和奖励 \(R(s,a)\)对智能体都是可见的，称这样的Agent为Model-based Agent，否则称为Model-free Agent。
备份图定义了未来下一时刻的状态价值函数与上一时刻的状态价值函数之间的关联。策略评估：已知马尔可夫决策过程以及要采取的策略\(\pi\)，计算价值函数 \(V_\pi(s)\)的过程就是策略评估。预测和控制是马尔可夫决策过程里面的核心问题。预测的输入是马尔可夫决策过程和策略 \(\pi\)。输出是价值函数。
策略梯度定理：策略函数的参数化可表示为 \(\pi_{\theta}(s,a)\)，其中\(\theta\)为一组参数，函数取值表示在状态 \(s\)下选择动作a的概率。为了优化策略函数，首先需要有一个对策略函数优劣进行衡量的标准。假设强化学习问题的初始状态为 \(s_0\)，则希望达到最大化的目标为： \[J(\theta):=V_{\pi_\theta}(s_0)\] 其中, \(v_{\pi_theta}\)是在策略 \(\pi_{\theta}\)下的真实价值函数，这个价值函数代表衡量一个状态的价值，即一个状态采取所有行为后的一个价值的期望值。如果能求出梯度\(\nabla_{\theta}J(\theta)\)，就可以用梯度上升法求解这个问题，即求解价值函数的最大值。
在这个函数中，\(J(\theta)\)既依赖于动作的选择，又依赖于动作选择时所处状态的分布。给定一个状态，策略参数对动作选择及收益的影响可以根据参数比较直观地计算出来，但因为状态分布和环境有关，所以策略参数对动作选择及收益的影响可以根据参数比较直观地计算出来，但因为状态分布和环境有关，所以策略对状态分布的影响一般很难确切知道。\(J(\theta)\)对模型参数的梯度却依赖于这种未知的影响，那么如何估计这个梯度呢。Sutton 等人在文献中给出了这个梯度的表达式： \[\nabla_\theta J(\theta)\propto\sum_s\mu_{\pi_\theta}(s)\sum_aq_{\pi_\theta}(s,a)\nabla_\theta\pi_\theta(s,a)\] 其中，\(\mu_{\pi_\theta}(s)\)称为策略 \(\pi_{theta}\) 的策略分布。在持续问题中，\(\mu_{\pi_\theta}(s)\)为算法 \(s_0\)出发经过无限多步后位于状态 \(s\)的概率。
强化是指我们可以用下一个状态的价值来更新当前的状态的价值，其实就是强化学习里面的自举的概念。在强化学习里，可以每走一步，更新一次Q表格，用下一个状态的Q值来更新当前状态的Q值，这种单步更新的方法称为时序差分方法。
免模型预测：在无法获取马尔科夫决策过程的模型情况下，可以通过蒙特卡洛方法和时序差分来估计某个给定策略的价值。
- 蒙特卡洛策略评估：蒙特卡洛方法是基于采样的方法，给定策略 \(\pi\)，让智能体和环境进行交互，可以得到很多轨迹，每个轨迹都有对应的回报。求出所有轨迹的汇报的平均值，就可以知道某一个策略对应状态的价值。
- 时序差分是介于蒙特卡洛和动态规划之间的方法，它是免模型的，不需要马尔可夫决策过程的转移矩阵和奖励函数，此外，时序差分方法可以从不完整的回合中学习，结合了自举的思想。
- 差别：
自举是指更新时使用了估计，蒙特卡洛没有使用自举，因为它根据实际的回报进行更新。动态规划方法和时序差分方法使用了自举。采样是指更新时通过采样得到一个期望，蒙特卡洛是纯采样的方法。动态规划没有使用采样，是直接用贝尔曼方程来更新状态价值。时序差分使用了采样。时序差分目标由两部分组成：一部分是采样，一部分是自举。
REINFORCE算法：根据一个确定好的策略模型来输出每一个可能动作的概率，对于所有动作的概率，使用采样方法(或者随机的方法)选择一个动作与环境进行交互，同时环境会给我们反馈整个回合的数据，将此数据输入学习函数中，并根据回合数据进行损失函数的构造，通过Adam等优化器的优化，再更新策略模型。
蒙特卡洛策略梯度定理：更具策略梯度定理表达式计算策略梯度并不是一个简单的问题，其中对\(\mu_{\pi_\theta}\)和 \(q{\pi_\theta}\)的准确比较难。用蒙特卡洛法能用来估计这类问题的取值。
REINFORCE算法：REINFORCE（蒙特卡洛策略梯度）算法是一种策略参数学习方法，其中策略参数 \(\theta\) 的更新方法为梯度上升法，它的目标是为了最大化性能指标 \(J(\theta)\)，其更新公式为：
\[\theta_{t+1}=\theta_t+\alpha\widehat{\nabla J(\theta_t)}\] 根据蒙特卡洛定理中对 \(\nabla_\theta J(\theta)\) 的计算，则有：
\[\nabla_\theta J(\theta)=\mathbb{E}_{s,a\sim\pi}[G_t\nabla_\theta\ln\pi_\theta(s,a)]\] 根据上述梯度更新公式，得到蒙特卡洛策略梯度更新公式：
\[\theta=\theta+\eta\gamma^{'}G\nabla_\theta\ln\pi_\theta(s_t,a_t)\] 其中， \(\Eta\)为学习率，\(\gamma'\)为衰减率，在REINFORCE算法中，暂不考虑衰减问题，设置\(\gamma'=1\)。
REINFOCE算法流程： 输入：马尔可夫决策过程\(MDP=(S,A,P,R,\gamma)\)，即状态，智能体，决策，奖励和折现系数。输出：策略 \(\pi(a|s,\theta)\)。即在状态为\(s\)，参数为\(\theta\)的条件下，选择动作a的概率，具体流程如下：
- 随机初始化；
- repeat
- 根据一个策略\(\pi_{\theta}\)采样一个片段(episode，即智能体由初始状态不断通过动作与环境交互，直至终止状态的过程)，得到\(s_0,a_0,R_1,s_1,a_1,r_2,...,s_{T-1},a_{T-1},R_T\)；
- for t \(\leftarrow\) 0 to \(T-1\) do \(G =\sum_{k=t}^{T-t}\gamma_{k-t}R_{t+k}\)；G是对回报的计算，回报是奖励随时间步的积累，这里 \(\gamma=1\)。 \(\theta=\theta+\eta \gamma' G\nabla_\theta\ln\pi_\theta(s_t,a_t)\)；其中\(\eta\)是学习率，策略梯度采用神经网络来拟合策略梯度函数，计算策略梯度用于优化策略网络。
- end for
- until 收敛；
SARSA(State-Action-Reward-State-Action)是一个学习马尔可夫决策过程策略的算法，通常用于机器学习和强化学习领域中。其学习更新函数依赖的5个值：**当前状态S1，当前状态选中的动作A1，获得的奖励Reward，S1状态下执行A1后取得的状态S2及S2状态下将会执行的动作A2。核心思想简化为： \[Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]\]
其中， \(Q(S_{t+1},A_{t+1})\) 是下一时刻的状态和实际采取的行动对应的Q值，\(Q(S_{t},A_{t})\)是当前时刻的状态和实际采取的行动对应的Q值，折扣因子\(\gamma\)的取值范围为[0,1]，其本质是一个衰减值，如果gamma更接近0，agent趋向于只考虑瞬时奖励值；反之如果接近1，则agent为延迟奖励赋予更大的权重，侧重于延迟奖励；奖励值\(R_{t+1}\)为 t+1时刻得到的奖励值，\(\alpha\)是学习率。
Q-Learning：Q-Learning属于值函数近似算法中，蒙特卡洛方法和时间差分法结合的算法。Q-Learning假设可能出现的动作a和状态S是有限多 ，这时a和S的全部组合也是有限多个，并且引入价值量Q表示智能体认为做出某个a时所能够获得的利益。在这种假设下，智能体收到S，选择可以产生最大的Q的a。
- Q-learning的训练过程就是Q表的Q值逐渐调整的过程，其核心是根据已经知道的Q值，当前选择行动a作用于环境获得的回报R，和下一轮\(S_{t+1}\)对应可以获得的最大利益Q，总共3个量，进行加权求和算出新的Q值，来更新Q表： \[Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma max Q(S_{t+1},a)-Q(S_t,A_t)]\]
其中，\(Q(S_{t+1},a)\)是在\(t+1\)时刻的状态和采取的行动(并不是实际行动，所以公式采用了所有可能采取行动的Q的最大值)对应的Q值，\(Q(S_{t},a_t)\) 是当前时刻的状态和实际采取的行动对应的Q值，折扣因子 \(\gamma\)的取值范围为[0,1]。
Q-Learning的缺点是有限且离散的状态。
DQN：当状态比较多的时候，Q表格很难进行存储。为了解决这个问题，一种解决方案是将Q表格参数化，使用深度神经网络拟合动作价值函数\(q_{\pi}\)。参数化可以解决无限状态下的动作价值函数的存储问题，因为算法只需记住一组参数，动作价值函数的具体值可根据这一组参数算出。
但是，动作价值函数的参数化也会带来一些新的问题：因为相邻样本来自同一条轨迹，会导致样本间关联性过强，而集中优化关联性过强的样本会导致神经网络处理其他样本时无法取得较好的结果。有人提出了深度Q网络(Deep Q-Network,DQN)，其本质是Q-learning算法，但使用深度学习网络拟合Q函数，解决了无线状态下的动作价值函数存储问题，同时采用经验重现(Experience Replay)和固定Q目标(Fixed-Q-Target)两个创新点来解决上述问题。
- 经验重现(Experience Replay)：使用一个经验池存储多条经验\(s,a,r,s'\)，再从中随机抽取一批用于训练，很好地解决了样本关联性的问题，同时，因为经验池里的经验可以得到重复利用，也提升了效率。
- 固定Q目标(Fixed-Q-target)：复制一个和原来Q网络结构一样的Target Q网络，用于计算Q目标值，这样在原来的Q网络中，target Q就是一个固定的数值，不会再产生优化目标不明确的问题。
流程：再DQN算法中，智能体会在与所处环境中\(environment\)进行交互后，获得一个环境提供的状态 \(s_t\)。接受状态后，智能体会根据深度学习网络预测出在该状态下不同行动\(action\)对应的Q值，并给出一个行动\(a_t\)，当行动反馈给环境后，环境会给出对应的奖励\(r_t\)、新的状态\(s_{t+1}\)，以及是否触发终止条件\(done\)，每一次交互完成后，DQN算法都会将 \(s_t, a_t, r_t, s_{t+1}, done\)作为一条经验存储在经验池中，每次会从经验池中抽取一定量的经验作为输入数据训练神经网络。
具体流程：
- 初始化经验池，随机初始化Q网络；
- for episode=1,M do:
- 重置环境，获得第一个状态；
- for t=1, T do:
用 \(\epsilon- greedy\)策略生成一个action；其中有 \(\epsilon\) 的概率会随机选择一个action，即为探索模式；其它情况下，则 \(a_t = max_a Q(s_t,a;\theta)\)，选择在 \(s_t\)状态下使得Q最大的action，即为经验模式；
根据动作与环境的交互，获得反馈的reward \(r_t\)、下一个状态 \(s_{t+1}\)和是否触发终止条件done。
将经验 \(s_t, a_t, r_t, s_{t+1},done\) 存入经验池；
从经验池中随机获取一个minibatch的经验；
\(\left.Qtarget_t=\left\{\begin{array}{c}r_t,\quad if done\\r_t+\gamma max_{a^{\prime}}Qtarget(s_{t+1},a^{'};\theta),\quad if not done\end{array}\right.\right.\)
根据\(Qpred_t\)和 \(Qtarget_t\)求loss，梯度下降法更新Q网络。
- end for
- 每隔固定个episode，更新Qtarget网络
- end for
Actor-Critic：在REINFORCE算法中，每次需要根据一个策略采集一条完整的轨迹，并计算这条轨迹上的回报，这种采样的方式的方差比较大，学习效率比较低。可以借鉴时序差分学习的思路，使用动态规划来提高采样的效率，即从状态s开始的总回报可以通过当前动作的即时奖励\(r(s,a,s')\)和下一个状态\(s'\)的值函数来近似估计。 演员-评论家算法(Actor-Critic)是一种结合策略梯度和时序差分学习的强化学习算法，包括：演员(Actor)和评价者(Critic)，跟生成对抗网络(GAN)的流程类似：
- 演员(Actor)是指策略函数 \(\pi_{\theta}(a|s)\)，即学习一个策略来得到尽量高的回报，用于生成动作(Action)并和环境交互。
- 评论家(Critic)是指值函数\(V^{\pi}(s)\)，对当前策略的值函数进行估计，即评估演员的好坏。用于评估Actor的表现，并指导Actor下一阶段的动作。
借助于值函数，演员-评论家算法可以进行单步更新参数，不需要等到回合结束才进行更新。 在Actor-Critic算法里，最知名的方法就是A3C(Asynchronous Advantage Actor-Critic)。
- 如果去掉Asynchronous,只有Advantage Actor-Critic，就叫做A2C。
- 如果加上了Asynchronous，变成Asynchronous Advantage Actor-Critic，就变成A3C。
Actor-Critic是Q-learning和Policy Gradient的结合，为了导出Actor-Critic算法，必须先了解Policy Gradient算法是如何一步步优化策略的。
参考链接
https://paddlepedia.readthedocs.io/en/latest/tutorials/reinforcement_learning/index.html, PaddlePaddle 强化学习
