马尔可夫随机过程
马尔可夫随机过程(MDP)是强化学习的理论基础，跟马尔可夫链类似，MDP同样具有马尔可夫性质：下一个时刻的状态只取决于当前时刻的状态和动作，而与之前的状态和动作无关。MDP包括下列五个基本的组成部分：
状态集$S=\{ s_1,s_2, \ldots ,s_n \}$;
动作集$A=\{ a_1,a_2, \ldots ,a_m \}$;
状态转移分布$p(s' | s, a) = P(S_{t+1} = s' | S_t = s, A_t = a)$;
回报值 $r(s', s, a) = E[ R_{t+1} | S_t = s, A_t = a, S_{t+1} = s' ]$;
折扣因子 $\gamma$;
结合示意图图对上面几个概念进行说明。状态 $S_t$ 用于描述环境(environment)本身在时刻$t$时的动态属性，而智能体(agent)在时刻$t$根据当前环境状态$S_t$和策略$\pi$发出的动作$A_t$能够作用于环境并改变其动态属性(即状态$S_t$)，使得其状态变为$S_{t+1}$，环境返回智能体一个立即回报值$r(S_{t+1}, S_t, A_t)$。环境状态的转移概率(也称为one-step dynamics)通过$p(s' | s, a)$来描述，回报值$r(S_{t+1}, S_t, A_t)$用于描述在状态$S_t$下发出动作$A_t$后到达下一个状态$S_{t+1}$能够取得的期望回报值，代表了环境对于Transition（$S_{t+1}, S_t, A_t$）的渴望程度，也是对于动作$A_t$所产生的立即效果的衡量。在多数情况下，状态$S_t$下采取的动作$A_t$会影响后续的回报值，因此出于对动作$A_t$所产生的长期效果衡量的考虑，通过折扣因子$\gamma$进行权衡：立即回报权重为1，而后续的回报值权重为$\gamma^k，\gamma \in [0,1], k=0,1,2,\ldots $，其中k表示$t+k+1$时刻环境返回的回报值$R_{t+k+1}$的时间间隔索引。
强化学习
目标
强化学习要解决的问题是什么呢？ 在”马尔可夫随机过程”部分，注意到智能体有两个输入信息：上一动作的回报值和环境的最新状态，有一个输出信息：最新的动作。通过一个称为策略$\pi$的映射来描述状态和动作之间的关系：$\pi(s): S \rightarrow A$，也就是说策略$\pi(s)$表示当前状态为$s$时对应的输出动作。而上一动作的回报值作为环境对动作的反馈信息，用于调整之前动作所对应的那个策略，使得策略逐渐最优。所以，强化学习要解决的问题是：寻找最优的策略$\pi^{\star}$
值函数
在有监督的机器学习模型中，数据集的输出值列向模型提供了直观明显的指导信息：正确的输出值或类标签，然后通过损失函数$L(y, \hat f)$来衡量当前模型的结果$\hat f$与真实结果$y$之间的差距量，再通过优化方法来改变模型的参数，使得损失函数减小，直到最优。
在强化学习中，为了寻找到最优的策略$\pi^{\star}$，同样需要指导信息来提供寻优的方向。回报值$r(s’, s, a)$正是环境向智能体提供的指导信息，但是与有监督学习中提供正确输出值的方式不同之处在于：回报值不直接告诉智能体在某个状态下应该采取的正确动作是什么，而是提供衡量当前动作好坏程度的反馈信息，它代表了在状态$S_t$时采取动作$A_t$后处于新的状态的$S_{t+1}$的渴望程度（desirability）。强化学习通过值函数的方式，在考虑立即回报$r(s', s, a)$的基础上，同时权衡当前动作的长期影响（回报），向模型提供寻找最优策略的指导信息。
a.状态值函数
为了衡量当前策略$\pi(\cdot)$在状态$s, s \in S$下的长期影响，定义相应的值函数如下：
这里的期望是针对状态转移分布$p(s’ | s, a)$和策略分布$\pi(s)$取的。策略分两种，一种是随机性策略$\pi(s) \in [0, 1]$，即状态$s$下的输出动作是随机分布的；另一种是确定性策略$\pi(s)$的输出动作是确定的，同样可以看作是特殊的 0-1 二项分布。针对这两个分布$p, \pi(s)$，对(1)进行改写，具体过程可见参考文献[1]，结果如下：
表达式(2)具有两个作用：一是为我们计算当前策略下每个状态的值函数提供了方法；二是建立了前后两个状态值函数$v_{\pi}(s), v_{\pi}(s')$之间的联系，计算上提供了便利。
(2)式中的第一个求和项$\sum_a \pi(a | s)$告诉我们：$v_{\pi}(s)$会综合考察策略$\pi(s)$在状态$s$下表现的优异程度。它的关注点是在状态上，所以我们称$v_{\pi}(s)$为状态值函数。通过状态值函数可以比较策略的好坏，如果$v_{\pi_1}(s) \ge v_{\pi_2}(s), \forall s \in S$，则策略$v_{\pi_1}(s)$好于策略$v_{\pi_2}(s)$。
b. 动作值函数
为了考察策略$\pi$在状态$s$下的具体动作$a$上表现的优异程度，我们需要定义相应的动作值函数：
表达式(2)(3)称为Bellman方程，它的意义在于建立值函数在当前状态和后一个时刻状态上的联系。对比表达式(2)和(3)，我们发现唯一的不同在于：状态值函数中所有的动作是由策略决定的$p(s’ | s, \pi(x))$，而动作值函数中当前的动作是由我们自己决定的$p(s’ | s, a)$，时刻$t+k+1, k=0,1,2,\ldots$处的动作依旧根据策略$\pi$选择。比较(2)和(3)，显然有$v_{\pi}(s) = q_{\pi}(s, \pi(s))$成立。所以状态值函数实际上只考虑动作$\pi(s)$，而动作值函数则可以遍历所有可能取的动作，它们本质上是相同的，前者是后者的特殊情况。
有了状态值函数，为什么还需要动作值函数呢？ 我们来分析一下。将智能体在环境状态为$s$时能够采取的所有动作记为集合$A(s)$，则必定有$\pi(s) \in A(s)$，即根据策略输出的动作必定包含于所有可能取的动作里面，而对于$\forall a \in A(s), a \ne \pi(s)$，总能够找到对应的$q_{\pi}(s, a)$，来衡量该动作$a$对应的表现。所以，动作值函数的价值和意义在于探索和寻找策略$\pi(s)$之外是否存在更好的动作。如果$\exists a^{\star} = argmax_{a} q_{\pi}(s, a) $并且$a^{\star} \gt \pi(s)$，则我们找到了在状态$s$处更好的动作，也即可以进行策略改进$\pi(s) = a^{\star}$。
最优策略
a. 思路
Tabular Action-value Methods
对于状态空间和动作空间比较小的情况，可以根据Bellman计算或者通过采样估计出值函数，然后根据得到的最优值函数来找到最优策略$\pi^{\star}$。因为$S, A$状态数比较小，因此值函数的一般以表格的形式存储。
根据值函数寻找最优策略的思路有两种：一种是利用状态值函数评估当前策略表现的优异程度，称为策略评估，然后再根据动作值函数选择相同状态下更好的动作，称为策略改进。策略评估和策略改进过程统称为策略迭代，通过策略迭代找到最优动作值函数后根据Bellman最优方程寻找对应的最优策略。符合这种思路的算法包括动态规划、蒙特卡罗控制等；第二种思路不需要状态值函数，直接根据动作值函数以增量计算（incremental computation）的方式对策略进行更新，这种思路的算法包括Q-学习、SARSA学习等。
无论哪种思路，总是根据动作值函数进行最优策略的改进和选择，这一点由值函数的Bellman最优性方程来保证：
b. 性质
最优策略的等价条件为：$\pi^{\star} (s)= argmax_a q_{\star}(s, a), \forall s \in S$，它满足如下性质:
其中$\pi(s)$表示非最优策略。也就是说在所有状态上，最优策略的表现都不会比非最优策略差。
参考文献
- reinforcement learning an introduction. MIT press;