强化学习：基本概念，马尔可夫，贝尔曼方程，动态规划

燕双嘤

6036人浏览 · 2022-03-13 17:41:41

燕双嘤 · 2022-03-13 17:41:41 发布

1，强化学习

1.1，基本概念

强化学习起源于动物心理学的相关原理，模仿人类和动物学习的试错机制，是一种通过与环境交互，学习状态到行为的映射关系，以获得最大积累期望回报的方法。强化学习包含环境，动作和奖励三部分，其本质是 agent 通过与环境的交互，使得其作出的 action 所得到的决策得到的总的奖励达到最大，或者说是期望最大。

DL/ML 中的 loss function 目的是使预测值和真实值之间的差距最小。

RL 中的 loss function 是是奖励和的期望最大。

在机器学习范畴内，根据反馈的不同，学习技术可以分为监督学习、非监督学习和强化学习三大类。强化学习是处于完全监督和完全缺乏预定义标签之间，又称为增强学习、加强学习和激励学习，是一种从环境状态到行为映射的学习，目的是使动作从环境中获得的累计回报（奖励）值最大。强化学习主要是智能体（Agent）与环境（Environment）的交互过程。强化学习有一个很大的优势，它可能是超越人类的。

强化学习的训练样本（智能体与环境交互产生的数据）没有任何标记，仅有一个延迟的回报信号。强化学习可以在环境中探索，最终可能超过人类。

在监督学习和无监督学习中，数据是静态的，不需要与环境进行交互，如分类聚类，只要将训练数据输入算法中进行训练即可。最好的结果就是人类的标注水平，这是一个上界。

强化学习特点：

智能体不会被告知要采取哪些行动，而是必须通过尝试来发现哪些行动产生的回报最大。

试错探索（探索与利用之间的平衡）：探索就是去一个新的餐馆。利用就是在去过的餐馆中挑一个最好吃的。探索有可能找到一个更好吃的，但也有不好吃的风险。

没有管理者，只有一个奖励信号，会被延迟（延迟奖励）。

智能体的操作会影响其接收的后续数据（智能体的操作会改变环境）。

1.2，术语

（1）智能体（Agent）：通过外界环境的状态（Sate）和奖励反馈（Reward）进行学习，并根据外界的状态来做出不同的动作（Action），而学习功能是指根据外界环境的奖励来调整策略，经过数次迭代之后，智能体最终学到完成相应任务的最优动作（即最优策略）。

（2）环境（Environment）：环境（Environment）是智能体（Agent）外部的所有事物，随着智能体（Agent）所做的不同动作（Action），环境的状态（State）会改变，并反馈给智能体（Agent）相应的奖励（Reward）。区分智能体和环境：不能被智能体随意改变的东西被认为是该智能体的外部环境。

（3）状态（State）：状态（State）是对环境的描述。动作（Action）是对智能体的描述。

（4）基本原理：如果Agent的某个行为导致了环境对Agent正的奖励，则Agent以后采取这个行为策略的趋势会加强。反之，若某个行为策略导致了负的奖赏，那么Agent此后采取这个动作的趋势会减弱。

（5）策略：策略是决定智能体行为的机制，是状态到行为的映射，其目的是在长期运行过程中接收的累计回报最大，用 $\pi(a|s)$ 表示，它定义了智能体在各个状态下的各种可能的行为概率，分为确定性策略与随机性策略。

确定性策略会根据具体状态输出一个动作，如 $\mu(s)=a$ 。

随机性策略则会根据状态输出每个动作的概率分布（概率值大于等于0，小于等于1），输出值为一个概率分布。

策略描述针对状态集合S中的每一个状态 $s$ ，Agent应完成动作集 $A$ 中的一个动作 $a$ ，策略 $\pi(a|s)$ ： $S\rightarrow A$ 是一个从状态到动作的映射。关于任意状态所能选择的策略组成的集合 $F$ ，称为允许策略集合 $\pi \in F$ 。在 $F$ 中找出使问题具有最优效果的策略 $\pi^{*}$ ，称为最优策略。

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

（6）状态转移概率：状态转移概率 $P_{ss^{'}}^a=P(s^{'}|s,a)$ 是在智能体根据当前状态做出一个动作后，环境在下一状态为 $s'$ 的概率。

（7）总回报：总回报是给定策略 $\pi$ 后，智能体与环境交互作用结束后所得到的累计奖励Return：

$G(\pi )=\sum_{t=0}^{T-1}R_{t+1}=\sum_{t=0}^{T-1}R(s_t,a_t,s_{t+1})$

如果没有终止情况，即 $T=\infty$ ，则利用折扣率 $\gamma\in [0,1]$ ，Return定义为：

$G(\pi )=\sum_{t=0}^{\infty }\gamma ^tR_{t+1}$

$G$ 是从初始时刻计算得到的总回报，而从 $t$ 时刻开始的总回报定义为：

$G_t(\pi)=\sum_{k=0}^{\infty }\gamma ^kR_{t+k+1}$

（8）目标函数：目标函数是总回报的期望值。由于每次状态转移都是随机性的，所以学习的目标是 agent 执行一系列动作来获得尽可能多的平均汇报：

$J(\theta )=E_{\pi \sim F}(G(\pi ))$

（9）状态值函数：值函数代表智能体在给定状态下的表现，或者给定状态下采取某个行为的好坏程度。从状态 $s$ 开始，遵循当前策略 $\pi$ 所获得的期望回报；这个值可以用来评价一个状态的好坏，指导智能体选择动作，使得其转移到具有较大值函数的状态上去。

$V^{\pi}(s)=E_{\pi}[G_t|S_t=s]=E_{\pi}\left [ \sum_{k=0}^{\infty } \gamma ^kr_{t+k+1}|S_t=s\right ]$

其中， $r_t$ 和 $s_t$ 分别为在时刻 $t$ 的立即奖赏和状态，衰减系数 $\gamma (\gamma\in[0,1])$ 使得临近的奖赏比未来的奖赏更重要。这里有一个期望 $E_{\pi}$ ，这里有个小角标是 $\pi$ 函数，这个 $\pi$ 函数就是说在已知某一个策略函数的时候，到底可以得到多少的奖励。

（11）状态-行为值函数 $Q^{\pi}(s,a)$ ：该指标表示针对当前状态 $s$ 执行某一具体行为 $a$ 后，继续执行策略 $\pi$ 所获得的的期望回报；也表示遵循策略 $\pi$ 时，对当前状态 $s$ 执行行为 $a$ 的价值大小。

$Q^{\pi}(s,a)=E_{\pi}[G_t|S_t=s,A_t=a]=E_{\pi}\left [ \sum_{k=0}^{\infty } \gamma ^kr_{t+k+1}|S_t=s,A_t=a\right ]$

可以认为 $Q$ 值是对奖赏的一种预测，如果状态 $s$ 的奖赏值低，并不意味着它的 $Q$ 值就低，因为如果 $s$ 的后续状态产生较高的奖赏，仍然可以得到较高的 $Q$ 值。

1.3，方法分类

随机性策略和确定性策略：

随机性策略：就是 $\pi$ 函数 $\pi(a | s)=P\left[A_{t}=a | S_{t}=s\right]$ 。当你输入一个状态 $s$ 的时候，输出是一个概率。这个概率就是你所有行为的一个概率，然后你可以进一步对这个概率分布进行采样，得到真实的你采取的行为。比如说这个概率可能是有 70% 的概率往左，30% 的概率往右。通常情况下，强化学习一般使用随机性策略。

确定性策略：就是说你这里有可能只是采取它的极大化，采取最有可能的动作，即 $a^{*}=\arg \underset{a}{\max}\, \,\pi(a \mid s)$ 。你现在这个概率就是事先决定好的。

无模型和有模型：

无模型：在实际的强化学习任务中，很难知道环境的反馈机制，如状态转移概率、环境反馈的回报等。这时候只能使用不依赖环境模型的方法，这种方法叫做无模型方法，如蒙特卡洛、时序差分法都属于此类方法。

有模型（需要建模）：假定智能体与环境交互过程中，环境的反馈机制已知，或者假定智能体已经对环境进行了建模，能在智能体内部模拟出于环境相同或近似的状况。即：知道环境在任一状态 $s$ ，接受任一行为 $a$ ，转移到任一状态 $s^{'}$ 的概率，和在任一状态 $s$ ，接收任意行为 $a$ 得到的回报 $r$ ，如动态规划。

基于值函数和基于策略函数：

基于值函数：求解时仅估计状态函数，不去估计策略函数，最优策略在对值函数进行迭代求解时间接得到。如：动态规划、蒙特卡罗、时序差分、值函数逼近法。

基于策略函数：最优行为或策略直接通过求解策略函数产生，不去求解各状态值的估计函数。所有的策略函数逼近方法都属于基于策略的方法，包括蒙特卡罗策略梯度、时序差分策略梯度等。

on-policy和off-policy：本质的区别是更新 $Q$ 值使用的方法是使用既定的策略（on-policy）还是使用新策略（off-policy）。

在线策略是指产生数据与要评估改进的策略是同一个策略。遵循一个已有策略进行采样，根据样本数据中的回报更新值函数。

离线策略是指产生数据的策略与评估改进的策略不是同一个策略。其基本思想上，虽然已有一个原始策略，但是并不针对这个原始策略进行采样，而是基于另一个策略进行采样。这另一个策略可以是先前学习到的策略，也可以是人类的策略等一些较为成熟的策略。观察这类策略的行为和回报，并根据这些回报评估和改进原始策略，以此达到学习的目标。

2，马尔可夫决策

2.1，马尔可夫过程

如果某一状态信息蕴含了所有相关的历史信息，只要当前状态可知，所有的历史信息都不再需要，即当前状态可以决定未来，则认为该状态具有马尔可夫性。例如，围棋未来的走法只和当前棋面有关，知道历史棋面信息对于当前该怎么走没有多大帮助。因此围棋的棋面是马尔可夫的，它已经涵盖了导致这种局面的所有重要信息。

$P[s_{t+1}|s_t]=P[s_{t+1}|s_1,...,s_t]$

即下一个状态只取决于当前状态，而不会受到过去状态的影响。

凡是具有马尔可夫性的随机过程都叫马尔可夫过程，又叫马尔可夫链。它是一个无记忆的随机过程，可以用一个元组 $<S,P>$ 表示，其中 $S$ 是有限数量的状态集， $P$ 是状态转移概率矩阵。假设一共有 $n$ 个状态，此时 $S=\left \{ s_1,s_2,...,s_n \right \}$ 。状态转移矩阵 $P$ 定义了所有状态对之间的转移概率，即

$P=\begin{bmatrix} p(s_1|s_1) &... &p(s_n|s_1) \\ ... & & ...\\ p(s_1|s_n) & ... & p(s_n|s_n) \end{bmatrix}$

矩阵中第 $i$ 行第 $j$ 列元素 $p(s_j|s_i)=P(S_{t+1}=s_j|S_t=s_i)$ 表示从状态 $s_t$ 转移到状态 $s_j$ 的概率，称 $p(s^{'}|s)$ 为状态转移函数。从某个状态出发，到达其他状态的概率和必须为 1，即状态转移矩阵 $P$ 的每一行的和为 1。

强化学习问题的关键假设就是 Agent 与环境间的交互可以被看成一个马尔可夫决策过程（MDP），因此强化学习的研究主要集中于对马尔可夫问题的处理。马尔可夫决策过程的本质：当前状态向下一状态转移的概率和奖赏值只取决于当前状态和选择的动作，而与历史状态和历史动作无关。

例如天气，马尔可夫性限制的模型仅表示晴天可以跟着雨天的情况下，具有相同概率，无论过去的天气是晴还是阴。系统模型符合马尔可夫性，可以用使用转换矩阵捕获转换概率：

晴天雨天

晴天 0.8 0.2

雨天 0.1 0.9

在这种情况下，如果有一个晴天，那么第二天将有 80% 的可能性是晴天，20% 的可能性是雨天。如果观察到一个雨天，那么天气变好的概率为 10%，第二天下雨的可能性为 90%。

2.2，马尔可夫奖励过程

为了引入奖励，需要扩展马尔可夫过程模型。首先，需要从状态到状态的过渡增加一个标量，表示奖励值。其次就是在模型中添加折扣因子 $\gamma \in[0,1]$ 。使用折扣因子是为了在计算当前状态的累计回报时，将未来时刻的立即回报也考虑进来。这种做法类似于人类追求眼前利益的同时，也会考虑具有不确定性的远期利益。

马尔可夫过程中将观察到一系列状态转换，马尔可夫奖励过程仍是如此，但对每次转换，都有一定奖励值的损失。所以现在，所有的观察都有一个奖励值附加到系统的每个转换。对于每一个 episode，这里定义时间 $t$ 的收益为：

$G_t=R_{t+1}+\gamma R_{t+2}+...=\sum_{k=0}^{\infty }\gamma ^kR_{t+k+1}$

对于每个时间点，都将收益计算为后续奖励的总和，但是更远的奖励乘以在时间 $t$ 离开起点的步数增加的折扣因子。折扣因子代表智能体的前瞻性，如果 $\gamma$ 等于1，则收益 $G_t$ 恰好等于所有后续奖励的总和，表明偏重考虑远期的利益，对应于任何后续奖励的完全可见性的智能体（会导致奖励无限制）。如果 $\gamma$ 等于0，收益 $G_t$ 将只是立即奖励而没有任何后续状态并且对应于绝对短视。

有些马尔可夫过程是带环的，它并没有终结，可以避免这个无穷的奖励。

并没有建立一个完美的模拟环境的模型，也就是说，对未来的评估不一定是准确的，不一定完全信任的模型，因为这种不确定性，所以对未来的预估增加一个折扣。

如果这个奖励是有实际价值的，可能是更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。

【折扣因子例子】我现在给你100和1年后给你100，你肯定选择现在100；但是现在给你80，未来给你120，选择就可能持平了，未来的100不如现在的100好，但是未来的120可能跟现在的80一样，这就是为啥需要折扣因子。

这个回报量 $G_t$ 在实践中并不是很有用，因为它从马尔可夫奖励过程中观察到的每个特定链条所定义的，因此即使对于同一个状态，它也可以有很大的不同。但是，如果分析一个极端情况，计算任何状态的回报的数学期望（评估平均大量的链），状态值：

$V_t(s)=E[G_t|S_t=s]=E[R_{t+1}+\gamma R_{t+2}+...+\gamma^{T-t-1}R_T|S_t=s]$

对于每个状态 $s$ ，值 $V(s)$ 是通过按马尔可夫奖励过程得到的平均（或预期）回报。

状态值函数还有另外一种形式（推导过程在贝尔曼方程）：

$V(s)=r(s)+\gamma\sum_{s^{'}\in S}p(s^{'}|s)V(s^{'})$

写成矩阵的形式： $V=R+\gamma PV$

求解： $(I-\gamma P)V=R$

$V=(I-\gamma P)^{-1}R$

但实际上，解析解的计算复杂度是 $O(n^3)$ ， $n$ 是状态个数，所以这种方法只适用很小的马尔可夫奖励过程。

下图是一个具有 6 个状态的马尔可夫过程的简单例子。其中每个绿色圆圈表示一个状态，每个状态都有一定概率（包括概率为零）转移到其他状态，其中 $s_6$ 通常被称为终止状态（terminal state），因为它不会再转移到其他状态，可以理解为它永远以概率 1 转移到自己。状态之间的虚线箭头表示状态的转移，箭头旁的数字表示该状态转移发生的概率。从每个状态出发转移到其他状态的概率总和为 1。比如说， $s_1$ 有 90%概率保持不变，有 10%概率转移到 $s_2$ ，而在 $s_2$ 又有 50%概率回到 $s_1$ ，有 50%概率转移到 $s_3$ 。

可以写出这个马尔可夫过程的状态转移矩阵：

$P=\begin{bmatrix} 0.9 & 0.1 &0 &0 &0 & 0\\ 0.5& 0& 0.5 & 0& 0 & 0\\ 0 &0 &0 & 0.6 &0 &0.4 \\ 0& 0& 0& 0 & 0.3 & 0.7\\ 0& 0.2 &0.3 &0.5 &0 &0 \\ 0& 0 & 0 & 0& 0 & 1 \end{bmatrix}$

如果我们选取 $s_1$ 为起始状态，设置 $\gamma=0.5$ ，采样到一条状态序列为 $s_1-s_2-s_3-s_6$ ，就可以计算 $s_1$ 的回报 $G_1$ ，得到：

$G_1=-1+0.5*(-2)+0.5^2*(-2)=-2.5$

2.3，马尔可夫决策过程

首先，添加一组必须是有限的动作（A），这是智能体的动作空间。然后需要用动作来调节这里的转换矩阵，这基本意味着该矩阵需要一个额外的动作维度，将它变成三维。智能体不再被动地观察状态转换，而是可以每次都主动选择要采取的动作。因此，对于每个状态，没有数字列表，而是一个矩阵，它的深度维度包含智能体可以采取的动作，另一个维度是目标状态系统将在执行此动作后跳转到的状态，它通过智能体来执行。

策略是一组控智能体行为的规则。即使对于相当简单的环境，也可以制定各种策略，策略的不同进而导致访问不同的状态集，得到不同收益。RL中智能体的主要目标是尽可能多地收集收益（定义为折扣累计奖励）。因此，找到一个好的策略变得很重要。形式上，策略被定义为每种可能状态的动作上的概率分布：

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

如果策略是固定的而不是动态的，那么马尔可夫决策过程就变成了马尔可夫奖励过程，因此可以通过策略的概率减少转换和奖励矩阵并摆脱动作维度。

3，贝尔曼方程

3.1，概述

马尔可夫决策过程为强化学习问题提供了基本的理论框架，几乎所有的强化学习问题都可以用马尔可夫决策过程（MDP）进行建模，而贝尔曼方程则是用来求解马尔可夫决策过程问题时用到的最基础的方程。贝尔曼方程也称为动态规划方程，其基本思想是将待求解问题分解成若干个子问题，从这些问题的解得到原问题的解。

【例1】根据策略计算值

智能体总是向下： $V(s)=2*1=2$

智能体总是向右： $V(s)=1*1=1$

智能体 50% 向右，50% 向下： $V(s)=1*0.5+2*0.5=1.5$

智能体 10% 向右，90% 向下： $V(s)=1*0.1+2*0.9=1.9$

上面例子中，可能会产生错误的想法，即应该始终采取最高奖励的动作。一般来说，并非如此简单。

智能体总是向下： $V(s)=2*1-20*1=-18$

智能体总是向右： $V(s)=1*1=1$

智能体 50% 向右，50% 向下： $V(s)=1-0.5+[2-20]*0.5=-8.5$

智能体 10% 向右，90% 向下： $V(s)=1*0.1+[2-20]*0.9=-16.1$

3.2，贝尔曼期望方程

状态值函数 $V_{\pi}(s)$ ：表示从状态 $s$ 开始，遵循当前策略 $\pi$ 时所获得的的期望回报：

$V_{\pi}(s)=E_{\pi}\left [ G_t |S_t=s\right ]=E_{\pi}\left [ R_{t+1}+\gamma R_{t+2}+\gamma ^{2} R_{t+3}+...|S_t=s \right ]$

$=E_{\pi}\left [ R_{t+1}+\gamma( R_{t+2}+\gamma R_{t+3}+...)|S_t=s \right ]$

$=E_{\pi}\left [ R_{t+1}+\gamma G_{t+1}|S_t=s \right ]$

$=E_{\pi}\left [ R_{t+1}+\gamma V(S_{t+1})|S_t=s \right ]$

$=R(s)+\gamma E_{\pi}\left [ V(S_{t+1})|S_t=s \right ]$

$=R(s)+\gamma \sum_{s^{'}\in S}P(s^{'}|s)V(s^{'})$

其中， $s^{'}=S_{t+1}$

$G_{t+1}$ 变成 $V(S_{t+1})$ ，因为回报的期望等于回报期望的期望。

即，证明： $E[V(s_{t+1})|S_t]=E[E[G_{t+1}|S_t]|S_t]=E[G_{t+1}|S_t]$

$E[E[G_{t+1}|S_t]|S_t]=E[E[G_{t+1}|S_{t+1}|S_t]]$

$=E\left [ \sum_{G_{t+1}}G_{t+1}P(G_{t+1}|S_{t+1})|S_t \right ]$

$=\sum_{S_{t+1}}\sum_{G_{t+1}}G_{t+1}P(G_{t+1}|S_{t+1},S_t)P(S_{t+1}|S_t)$

$=\sum_{S_{t+1}}\sum_{G_{t+1}}\frac{\sum_{G_{t+1}}G_{t+1}P(G_{t+1}|S_{t+1},S_t)P(S_{t+1}|S_t)P(S_t)}{P(S_t)}$

$=\sum_{S_{t+1}}\sum_{G_{t+1}}\frac{\sum_{G_{t+1}}G_{t+1}P(G_{t+1}|S_{t+1},S_t)P(S_{t+1},S_t)}{P(S_t)}$

$=\sum_{S_{t+1}}\sum_{G_{t+1}}\frac{\sum_{G_{t+1}}G_{t+1}P(G_{t+1},S_{t+1},S_t)}{P(S_t)}$

$=\sum_{S_{t+1}}\sum_{G_{t+1}}G_{t+1}P(G_{t+1},S_{t+1}|S_t)$

$=\sum_{G_{t+1}}\sum_{S_{t+1}}G_{t+1}P(G_{t+1},S_{t+1}|S_t)$

$=\sum_{G_{t+1}}G_{t+1}P(G_{t+1}|S_t)$

$=E[G_{t+1}|S_t]$

从结果来看， $V_{\pi}(s)$ 分解成了两部分，第一部分是该状态下的立即回报奖励，该项是常数项，因此立即回报期望等于立即回报 $R_{t+1}$ 本身；第二部分是下一时刻状态函数的折扣期望。

状态行为值函数 $Q_{s,a}$ ：它等于通过在状态 $s$ 中执行动作 $a$ 可以获得的总奖励期望。

$Q_{\pi}(s,a)=E_{\pi}\left [ G_t|S_t=s,A_t=a \right ]$

$=E_{\pi}\left [ R_{t+1} +\gamma G_{t+1}| S_t=s,A_t=a\right ]$

$=E[R_{t+1}|S_t=s,A_t=a ]+E_{\pi}\left [ \gamma G_{t+1}| S_t=s,A_t=a\right ]$

$=R(s,a)+\gamma E_{\pi}\left [ G_{t+1}| S_t=s,A_t=a\right ]$

$=R(s,a)+\gamma E_{\pi}\left [ V(S_{t+1})| S_t=s,A_t=a\right ]$

$=R(s,a)+\gamma \sum_{s^{'}\in S}P(s^{'}|s,a)V(s^{'})$

（1）基于状态 $s$ ，采取动作 $a$ ，求 $V_{\pi}(s)$

在遵循策略 $\pi$ 时，状态 $s$ 的值函数体现在为该状态下采取所有可能行为的价值 $Q_{\pi}(s,a)$ 与行为发生概率 $\pi(a|s)$ 的乘积的和（通过定义可以直接理解）。

$V_{\pi}(s)=\sum_{a\in A}\pi(a|s)Q_{\pi}(s,a)$

（2）采取行为 $a$ ，状态转变至 $s^{'}$ ，求 $Q_{\pi}(s,a)$

在遵循策略 $\pi$ 时，行为状态价值 $Q_{\pi}(s,a)$ 体现为两项之和。第一项是取行为 $a$ 后，获得的立即回报 $R_s^a$ ，第二项是所有可能的状态值 $V_{\pi}(s^{'})$ 乘以状态转移概率 $P_{ss^{'}}^a$ 代衰减求和。

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

（3）基于状态 $s$ ，采取行为 $a$ ，状态转变至 $s^{'}$ ，求 $V_{\pi}(s)$

结合（1）（2）可得：

$V_{\pi}(s)=\sum_{a\in A}\pi(a|s)Q_{\pi}(s,a)=\sum_{a\in A}\pi(a|s)\left ( R_{s}^a+\gamma \sum_{s^{i}\in S}P_{ss^{'}}^aV_{\pi}(s^{'}) \right )$

由于 $\sum_{a\in A}\pi(a|s)R_s^a=r(s)$

$r(s)$ 是即时奖励，与状态和动作有关

$p(s^{'}|s)=\sum_{a\in A}\pi(a|s)P_{ss^{'}}^a$ 表示从 $s$ 到 $s^{'}$ 的总转移概率

等价： $V(s)=r(s)+\gamma\sum_{s^{'}\in S}p(s^{'}|s)V(s^{'})$

（4）采取行为 $a$ ，状态转变至 $s^{'}$ ，采取行动 $a^{'}$ ，求 $Q_{\pi}(s,a)$

结合（1）（2）可得：

$Q_{\pi}(s,a)=R_{s}^a+\gamma \sum_{s^{i}\in S}P_{ss^{'}}^aV_{\pi}(s^{'})=R_{s}^a+\gamma \sum_{s^{i}\in S}P_{ss^{'}}^a\left ( \sum_{a\in A}\pi(a|s)Q_{\pi}(s,a) \right )$

$=R_{s}^a+\gamma \sum_{s^{i}\in S}P_{ss^{'}}^a\sum_{a^{'}\in A}\pi(a^{'}|s^{'})Q_{\pi}(s^{'},a^{'})$

3.3，贝尔曼方程求解

假设存在如下求职马尔可夫决策过程：

【步骤一】求解状态值：设 $V_1,V_2,V_3,V_4,V_5$ 分别表示（Java开发，人工智能，机器学习，强化学习，深度学习），折扣因子为 1， $P_{ss^{'}}^a=1$ ，根据状态值公式（3）：

$V_{\pi}(s)=\sum_{a\in A}\pi(a|s)\left ( R_{s}^a+\gamma \sum_{s^{i}\in S}P_{ss^{'}}^aV_{\pi}(s^{'}) \right )$

可列出：

$\left\{\begin{matrix} V_1=0.5*(0+1*1*V_1)+0.5*(10+1*1*V_3)\\ V_2=1*(0+1*1*0)\\ V_3=\frac{1}{3}*(-10+1*1*V_1)+\frac{1}{3}*(4+1*1*V_2)+\frac{1}{3}*(-2+1*1*V_4) \\ V_4= \frac{1}{3}*(-10+1*1*V_1)+\frac{1}{3}*(8+1*1*V_2)+\frac{1}{3}*(-2+1*1*V_5) \\ V_5=0.5*(10+1*1*V_2)+0.5*(1+1*0.2*V_3+1*0.2*V_4+1*0.6*V_5) \end{matrix}\right.$

求解方程组可得：

$V_1=14.28125,V_2=0,V_3=4.28125,V_4=6.5625,V_5=9.40625$

【步骤二】求解状态值：折扣因子为 1， $P_{ss^{'}}^a=1$ ，根据状态值公式（2）：

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

$Q_{11}=0+1*1*V_1=0+1*1*14.28125=14.28125$

$Q_{12}=10+1*1*V_3=10+1*1*4.28125=14.28125$

$Q_{31}=-10+1*1*V_1=-10+1*1*14.28125=4.28125$

.......

$Q_{52}=1+1*0.6*V_5+1*0.2*V_4+1*0.2*V_3=8.812496$

可以通过矩阵求逆把这个 $V$ 的这个价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是 $O(n^3)$ 。所以当状态非常多的时候，比如说从十个状态到一千个状态，到一百万个状态。那么当有一百万个状态的时候，这个转移矩阵就会是个一百万乘以一百万的矩阵，这样一个大矩阵的话求逆是非常困难的，所以这种通过解析解去求解的方法只适用于很小量的 MRP。

3.4，最优的Bellman方程

贝尔曼最优方程表达的是当前最优值函数（或最优行为值函数）和它后继最优值函数（或最优行为值函数）的关系，以及最优值函数和最优行为值函数之间的关系。

其中，最优值函数 $V^{*}(s)$ 是指在所有策略中最大的值函数，即：

$V^{*}(s)=\underset{\pi}{max}\, V_{\pi}(s),s\in S$

相应地，最优行为值函数 $Q^{*}(s,d)$ 是指所有策略中最大的行为值函数：

$Q^{*}(s,a)=\underset{\pi}{max}\, Q_{\pi}(s,a),s\in S$

（1）基于状态 $s$ ，采取动作 $a$ ，求取 $V^{*}(s)$

当前状态的最优值函数 $V^{*}(s)$ 等于从该状态 $s$ 出发，采取的所有行为中对应的那个最大的行为为值函数。

$V^{*}(s)=\underset{a}{max}\, Q^{*}(s,a)$

最佳价值函数的定义为： $v^* (s)=\max_{\pi} v^{\pi}(s)$ 即去搜索一种 policy $\pi$ 来让每个状态的价值最大。 $v^*$ 就是到达每一个状态，它的值的极大化情况。在这种极大化情况上面，得到的策略就可以说它是最佳策略，即 $\pi^{*}(s)=\underset{\pi}{\arg \max }~ v^{\pi}(s)$ 。

（2）基于状态 $a$ ，采取动作 $s$ ，求取 $Q^{*}(s,a)$

在某个状态 $s$ 下，采取某个行为的最优价值 $Q^{*}(s,a)$ 由两部分组成，部分是离开状态 $s$ 的立即回报 $R_s^a$ ，另一部分则是所有能达到的状态 $s^{'}$ 的最优状态价值 $V^{*}(s^{'})$ 按出现的概率求和：

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

（3）基于状态 $s$ ，采取行为 $a$ ，状态转变至 $s^{'}$ ，求 $V^{*}(s)$

结合（1）（2）：

$V^{*}(s)=\underset{a}{max}\left [ R_s^a +\gamma \sum_{s^{'}\in S}P_{ss^{'}}^aV^{*}(s^{'})\right ]$

（4）采取行为 $a$ ，状态转变至 $s^{'}$ ，采取行动 $a^{'}$ ，求 $Q^*_{\pi}(s,a)$

结合（1）（2）：

$Q^*_{\pi}(s,a)=R_{s}^a+\gamma \sum_{s^{i}\in S}P_{ss^{'}}^a\, \underset{a^{'}}{max}\, Q^{*}_{\pi}(s^{'},a^{'})$

3.5，最优策略求解

强化学习：定一个一离散时间的折扣马尔可夫决策过程 $M=<S,A,P,R,\gamma>$ ，其中 $S$ 为状态集， $A$ 为动作集， $P$ 是转移概率， $R$ 为回报函数， $\gamma$ 为折扣因子。 $T$ 为时间步， $\tau$ 为一个轨迹序列， $\tau =(s_0,a_0,r_0,s_1,a_1,r_1,...)$ ，对应的累计回报为 $R=\sum_{t=0}^{T}\gamma ^kr_t$ 。则强化学习的目标是：找到最优策略 $\pi$ ，使得该策略下的累计回报期望最大，即 $\pi=arg \, \, \underset{\pi}{max}\, \, R(\tau)d\tau$

最优策略：对于任何状态 $s$ ，当且仅当遵循策略 $\pi$ 的价值不小于遵循策略 $\pi^{'}$ 的价值时，则称策略 $\pi$ 优于策略 $\pi^{'}$ ，即：

$\pi \geqslant \pi^{'}\, \, ,\, \, \forall s,V_{\pi}(s)\geqslant V_{\pi^{'}}(s)$

对于任何MDP（马尔可夫过程），存在一个最优策略，即满足如下公式：

$\forall \pi\, ,\, \pi^{*}\geqslant \pi$

每个策略对应着一个状态价值函数，最优策略自然对应着最优状态值函数。

求解最优策略：根据策略最优定理可知，当值函数最优时采取的策略也是最优的；反过来，策略最优时值函数也最优，所以可以通过求取最优值函数 $V^{*}$ 或 $Q^{*}$ 来求取最优策略。

如果拥有（后续：值迭代法） $V^{*}$ ，基于每一个状态 $s$ ，做一步搜索，一步搜索之后，出现的最优行为将会是最优的，对应的最优行为集合就是最优策略。

$\pi^{*}(a|s)=arg\, \underset{a\in A}{max}\left [ R_s^{a}+\gamma \sum_{s^{'}\in S}P_{ss^{'}}^aV^{*}(s^{'}) \right ]$

如果拥有最优行为值函数 $Q^{*}$ ，则求解最优策略将变得更为方便。对于任意的状态 $s$ ，直到找到最大化 $Q^{*}(s,a)$ 对应的行为，最优策略求取公式：

$Q^{*}(a|s)=\left\{\begin{matrix} 1 &a=arg\, \underset{a\in A}{max}Q^{*}(s,a) \\ 0& other \end{matrix}\right.$

对于任何MDP问题，总存在一个确定性的最优策略，找到最优行为价值函数，就相当于找到了最优策略。

4，动态规划

4.1，基本原理

使用动态规划算法求解马尔可夫决策过程（MDP）模型，也就是在清楚模型结构（包括状态转移率、回报率等）的基础上，用动态规划方法来进行策略评估和策略改进，最终获得最优策略。

策略评估（预测）：给定一个马尔可夫决策过程模型MDP： $<S,A,P,R,\gamma>$ 和一个策略 $\pi$ ，要求输出基于当前策略 $\pi$ 的所有状态的值函数 $V$ 。

策略改进（控制）：给定一个马尔可夫决策过程模型MDP： $<S,A,P,R,\gamma>$ 和一个策略 $\pi$ ，要求确定最优值函数 $V^{*}$ 和最优策略 $\pi^{*}$ 。

4.2，策略评估

策略评估要解决的问题是，给定一个策略 $\pi$ ，如何计算在该策略下的值函数 $V_{\pi}$ 。因为实际中涉及的马尔可夫模型规模一般比较大，直接求解效率低，因此可使用迭代法进行求解。考虑应用贝尔曼期望方程进行迭代：

$V_{\pi}(s)=\sum_{a\in A}\pi(a|s)\left ( R_s^a + \gamma \sum_{s^{'}\in S}P_{ss^{'}}^aV_{\pi}(s^{'}) \right )$

状态 $s$ 处的值函数 $V_{\pi}(s)$ ，可以利用后继状态 $s^{'}$ 的值函数 $V_{\pi}(s^{'})$ 来表示，依次类推。

初始所有状态值函数（ $V$ ）全部为： $0$ ，第 $k+1$ 次迭代求解 $V_{\pi}(s)$ 时，使用第 $k$ 次计算出来的值函数 $V_k(s^{'})$ 更新计算 $V_{k+1}(s)$ 。迭代时使用公式如下：

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

对于模型已知的强化学习算法，概率和回报都是已知数，唯一的未知数是值函数，因此该方法通过反复迭代最终将收敛。

4.3，策略改进

计算值函数的目的是利用值函数找到最优策略。既然值函数已经获得，接下来要解决的问题是如何利用值函数进行策略改善，从而得到最优策略。

一个很自然的方法是针对每个状态采用贪心策略对当前策略进行改进，即：

$\pi_{l+1}(s)\in arg \, \, \underset{a}{max}\, \, Q_{\pi_{l}}(s,a)$

其中， $Q_{\pi}(s,a)=R_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^aV_{\pi}(s^{'})$

在当前策略 $\pi$ 的基础上，利用贪心算法选取行为，直接将所选择的动作改变为当前最优的动作。因为贪心策略公式中的值函数 $V_{\pi}(s),Q_{\pi}(s,a)$ 已经考虑了未来的回报。因此在策略改进时，可以放心使用贪心算法求得全局最优解。

令动作改变后对应的策略 $\pi^{'}$ ， $a^{'}$ 为在状态 $s$ 下遵循策略 $\pi^{'}$ 选取的动作，同理 $a^{''}$ 为在状态 $s^{'}$ 下遵循策略 $\pi^{'}$ 选取的动作。改变动作的条件是 $Q_{\pi}(s,a^{'})\geqslant V_{\pi}(s)$ （蒙特卡洛章节会证明），则可得到：

$\large V_{\pi}(s)\leqslant Q_{\pi}(s,a^{'})=R_s^{a^{'}}+\sum_{s^{'}\in S}\gamma P_{ss^{'}}^{a^{'}}V_{\pi}(s^{'})\leqslant R_s^{a^{'}}+\sum_{s^{'}\in S}\gamma P_{ss^{'}}^{a^{'}}Q_{\pi}(s^{'},a^{''})=...=V_{\pi^{'}}(s)$

可见，值函数对于策略的每一点改进都是单调递增的，因此对于当前策略 $\pi$ ，可以放心地将其改进。

$\large \pi^{'}= arg \, \, \underset{a \in A}{max}\, \, Q_{\pi}(s,a)$

直到 $\pi^{'}$ 与 $\pi$ 一致，不再变化，收敛至最优策略。

4.4，策略迭代

将策略评估算法和策略改进算法合起来便有了策略迭代算法。策略迭代算法通常由策略评估和策略改进两部分构成：

在策略评估中，根据当前策略计算值函数。

在策略改进中，通过贪心算法选择最大值函数对应的行为。

策略评估和策略改进两部分交替进行不断迭代：

假设我们有一个初始策略 $\pi_1$ ，策略迭代算法首先评估该策略的价值（用 $E$ 表示），得到该策略的价值函数 $V_{\pi_1}$ 或 $Q_{\pi_1}$ ，

下一步，策略迭代算法会借助贪心算法对初始策略 $\pi_1$ 进行改进（用 $I$ 表示），得到 $\pi_2$ 。接着对改进后的策略 $\pi_2$ 进行评估，在进一步改进当前策略，如此循环迭代，直到策略收敛至最优。

$\pi_1\overset{E}{\rightarrow }V_{\pi_1},Q_{\pi_1} \overset{I}{\rightarrow }\pi_2 \overset{E}{\rightarrow }V_{\pi_2},Q_{\pi_2} \overset{I}{\rightarrow }...\pi^* \overset{E}{\rightarrow }V^*,Q^* \overset{I}{\rightarrow } \pi^*$

其中， $\pi_1$ 为初始策略， $E$ 表示策略评估， $I$ 表示策略改进。

在策略评估过程中，往往需要等到值函数收敛之后才能进行策略改进，这其实是没有必要的。可以在进行一次策略评估之后就开始策略改进，如此循环往复执行这两个过程，最终会收敛到最优值函数和最优策略。

策略评估过程中，对于任意的策略 $\pi_k$ ，通过贝尔曼方程进行迭代计算得到 $V_{\pi_k},Q_{\pi_k}$ 。

$V_{\pi_k}(s)=V_k^{\pi_k}(s)=\sum_{a\in A}\pi_k(a|s)\left ( R_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^aV_{k-1}^{\pi_k}(s^{'}) \right )$

策略改进部分，用贪心算法得到更新策略：

$\pi^{'}(s)=arg\, \, \underset{a\in A}{max}Q_{\pi_k}(s,a)$

或

$\pi^{'}(s)=arg \, \, \underset{a\in A}{max}\left [ R_s^a +\gamma \sum_{s^{'}\in S}P_{ss^{'}}^aV_{\pi_k}(s^{'})\right ]$

4.5，策略迭代（案例）

当智能体位于网格世界边缘时，任何使其离开网格世界的行为都会使其停留在当前位置。当智能体位于宝藏区时，则无论采取何种行为，均会产生0回报，且位置不变。使用策略迭代法对此问题求解，假设初始策略为均匀随机策略：

$\pi(UP|\cdot )=0.25;\pi(RIGHT|\cdot )=0.25;\pi(DOWN|\cdot )=0.25;\pi(LEFT|\cdot )=0.25$

（1）首先评估给定随机策略下的值函数，使用贝尔曼期望方程迭代计算直至值函数收敛。初始化所有状态值函数为0，使用如下公式进行迭代值函数：

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

注意， $R_s^a$ 表示当前状态的期望，而不是目标状态的期望。

$V_k(s^{'})$ 表示目标状态的状态值。

$V_1(s=0)=0.5(-1+1*1*0)+0.25(-1+1*1*0)+0.25(-1+1*1*0)=-1$

$V_1(s=1)=0.25(-1+1*1*0)+0.5(-1+1*1*0)+0.25(-1+1*1*-1)=-1.25$

$V_1(s=2)=0.75(-1+1*1*0)+0.25(-1+1*1*(-1.25))=-1.3125$

$V_1(s=3)=0.5(-1+1*1*0)+0.25(-1+1*1*(-1.3125))+0.25(-1+1*1*0)=-1.328125$

......

（2）使用如下公式：

$\large \pi^{*}(a|s)=arg \, \, \underset{a\in A}{max}\left [ R_s^a +\gamma \sum_{s^{'}\in S}P_{ss^{'}}^aV^*(s^{'})\right ]$

对收敛的值函数 $V_{338}^{\pi}(s)$ ，使用贪心算法进行策略改进，求取 $V_{338}^{\pi}(s)$ 对应的改进后策略 $\pi_1$ ，则有 $\pi_1$ ：

$\pi(a=UP\, or\, LEFT|s=0)=-1+1*1*(-47.13614306)=-48.13614306$

$\pi(a=RIGHT|s=0)=-1+1*1*(-41.72708685)=-42.13614306$

$\pi(a=DOWN|s=0)=-1+1*1*(-48.54523094)=-49.54523094$

$\pi^{*}(s=0)=\pi^{*}(a=RIGHT|s=0)=-42.13614306$

......

继续使用贝尔曼期望方程求取当前策略 $\pi_1$ 下的值函数，直至值函数收敛，过程同（1）：

针对值函数 $V_5^{\pi_1}(s)$ 进行第二次策略改善，得到 $\pi_2$

继续求取 $\pi_2$ 对应的值函数（策略评估），针对收敛的值函数 $V_5^{\pi_2}(s)$ 进行改进，得到 $\pi_3$ ：

4.6，值迭代

策略迭代算法在每次进行策略评估时，采用贝尔曼期望方程更新值函数。而值迭代算法借助的是贝尔曼最优方程，直接使用行为回报的最大值更新原来的值。

$V_{k+1}(s)=\underset{a\in A}{max}\left ( R_s^a +\gamma \sum_{s^{'}\in S}P_{ss^{'}}^aV_k(s^{'}) \right )$

值迭代算法将策略改进视为值函数的改善，每一步都求取最大的值函数，即：

$V_1\rightarrow V_2\rightarrow V_3\rightarrow ...\rightarrow V^*$

假设在状态 $s$ 下，有一个初始值函数 $V_1(s)$ ，基于当前状态，有多个可选行为 $a$ 。每个行为 $a$ 会引发一个立即回报 $R_s^a$ ，一个或多个状态转移，如从状态 $s$ 转换至状态 $s^{'}$ 。不同状态 $s^{'}$ 对应有不同的值函数 $V_1(s^{'})$ 整个的 $R_s^a+\gamma \sum_{s^{'}\in S}P_{ss^{'}}^aV_1(s)$ 称为 $a$ 的回报。值迭代直接使用所有行为引发的行为回报中取值最大的那个值来更新原来的值，得到 $V_2(s)$ 。如此迭代下去，直至值函数收敛，整个过程没有遵循任何策略。

虽然算法中没有给出明确的策略，但是根据公式：

$V_{t+1}(s)\leftarrow \underset{a\in A}{max}Q_{t+1}(s,a)$

可以看出策略迭代改进是隐含在值迭代过程中执行的。

4.7，值迭代（案例）

在进行一次策略评估（即求出当前策略下的值函数）之后就进行策略改进，这种方法被称为值函数迭代算法。即，在每次进行值函数计算时，直接选择那个是的值函数最大的行为。

$V_{k+1}(s)=\underset{a}{max}\,Q_{k+1}(s,a)$

天工造物局

更多推荐

SWE-RL进阶实战：如何将奖励函数集成到你自己的强化学习训练框架

SWE-RL是首个利用开源软件演进数据与规则奖励来扩展LLM推理能力的强化学习开源项目，其官方仓库中的核心奖励函数实现堪称"即插即用"的宝藏。本文将带你完整掌握SWE-RL奖励函数的集成方法，手把手教你如何把这套基于序列相似度的奖励机制迁移到自己的强化学习训练框架中，让大模型学会像人类工程师一样修改真实代码。## 为什么你需要SWE-RL的奖励函数？在传统的RLHF训练中，奖励信号往往来自

天工造物局

告别局域网：VisionProTeleop 外部网络模式实现跨地域机器人遥操作

想让机器人遥操作摆脱同一 WiFi 的限制？开源项目 VisionProTeleop 从 v2.5 版本起推出**外部网络模式**，用一组房间码就能让 Vision Pro 与远在实验室的机器人跨地域连接，实现在家远程操控机械臂的终极体验。本文将带你快速理解其原理，并手把手完成配置。[![VisionProTeleop 状态窗口展示跨地域遥操作连接信息](https://raw.gitcode