贝尔曼方程是强化学习中的核心概念，它描述了一个状态的价值与其后续状态价值之间的关系。下面我用一种直观的方式来解释它的推导过程。高中生都能看懂~

关键概念

想象一个智能体在环境中做决策，比如玩一个棋盘游戏。有两个关键概念 回报 和 价值

回报

它从当前时刻 $t$ 开始，直到游戏结束，获得的所有 奖励 用 $R$ 表示 集合起来，形成一个总收益，这就是 ​​回报​ ​, 用 $G_t$ 表示。由于未来的奖励不如眼前的奖励“实在”，我们会用一个 ​折扣因子​ ​( $\gamma$ ，通常取一个小于1的数，比如0.9 ) 给未来的奖励打折。所以，折扣回报的计算公式是

$$G_t=R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\cdots =\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k}$$

可以理解为，每一步都存在一个奖励，当前状态下总回报是所有后续步骤奖励的总和，并且通过折扣因子反应及时奖励最“值钱”，越往后奖励价值越低。

价值函数

一局游戏的胜负有时靠运气，单次游戏的回报（总收益）偶然性很大。要客观衡量一个状态（比如棋盘上的某个局面）的 真正价值，我们需要看很多次游戏，计算这个状态出发所能获得的回报 期望，用高中知识来讲就是 当前状态 下，所有策略中能获得的 平均回报 。这个 期望(平均值) 就是该 状态 的 价值 。用公式表示就是:

$$V(s)=\mathbb{E}[G_t|S_t=s]$$

其中：
$V(s)$ ：表示价值函数
$\mathbb{E}$ ：表示期望
$G_t|S_t=s$ ：表示在 $s$ 状态下的回报 $G_t$

建立状态间的联系

贝尔曼方程的巧妙之处在于，它把一个大问题（计算整个游戏的总价值）分解成了眼前的一步和之后的所有步。这就像把整盘棋的价值，看作是你走下一步棋立刻得到的分数，加上你走完这步棋后新局面的价值（但新局面的价值要打点折）

1. 分解回报
   我们把总回报 $G_t$ 拆为两部分

$$\begin{array}{rl}{G}_t& =R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\dots \\ & =R_t+\gamma (R_{t+1}+\gamma R_{t+2}+\dots )& (\mathrm{其}\mathrm{中}{G}_{t+1}=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots )\\ & =R_t+\gamma G_{t+1}\end{array}$$

2. 带入价值函数
   价值函数是回报的期望（平均值），所以我们将上面这个关系式代入价值函数的定义中

$$V(s)=\mathbb{E}[G_t|S_t=s]=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]$$

根据期望的运算法则，和的期望等于期望的和，所以上式可以拆开：

$$V(s)=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]=\mathbb{E}[R_{t+1}||S_t=s]+\gamma \mathbb{E}[G_{t+1}|S_t=s]$$

3. 理解等号右边两项
   • 第1项：$\mathbb{E}[R_t||S_t=s]$ 这是在状态 $s$ 下，能获得的​​即时奖励的期望​​，即时奖励的期望正是奖励函数的输出，即 $R(s)$
   • 第2项：$\gamma \mathbb{E}[G_{t+1}|S_t=s]$，这一项有点 tricky。它的意思是：​​在当前状态是 $s$ 的前提下，下一个状态 $s^{\prime }$ 的价值是多少？​​ 这需要考虑从 $s$ 出发，所有可能到达的下一个状态 $s^{\prime }$，以及到达每个 $s^{\prime }$ 的概率。然后，对每个可能的 $s^{\prime }$，乘以它本身的价值 $V(s^{\prime })$，最后再求平均。这个过程可以借助 ​​全概率公式​ ​来理解。
4. 利用马尔可夫性质
   为了简化计算，我们假设环境具有“马尔可夫性”，即​​未来只取决于现在，与过去无关​​。这意味着，从 $s$ 转移到 $s^{\prime }$ 的概率只取决于 $s$ 本身，和我们之前是怎么走到 $s$ 的没关系。这个假设使得第二项可以清晰地写成

$$\gamma \sum _{s^{\prime }}P(s^{\prime }|s)V(s^{\prime })$$

即对所有可能的下一个状态，用转移概率加权其价值

最终结论：贝尔曼方程

将上面的分析组合起来，我们就得到了著名的贝尔曼方程：

$$V(s)=R(s)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s)V(s^{\prime })$$

这个公式非常直观地告诉我们：

​​任何一个状态 $s$ 的价值，都由两部分组成 ：​
1. ​​即时奖励​​：离开这个状态时立刻能获得的平均收益 $R(s)$。
2. ​​未来奖励的折扣价值​​：考虑所有可能到达的下一个状态 $s^{\prime }$，用到达 $s^{\prime }$ 的概率 $P(s^{\prime }|s)$ 进行加权，再乘以 $s^{\prime }$ 本身的价值 $V(s^{\prime })$。因为这是未来的收益，所以整体要乘以一个折扣因子 $\gamma$

矩阵形式

若一个马尔可夫奖励过程一共有 $n$ 个状态，即 $$\begin{gathered} S= \\ {s}_1,s_2,\dots \end{gathered}$$，当我们考虑所有状态

$$\{\begin{array}{lr}V(s_1)& =R(s_1)+\gamma [P(s_1|s_1)V(s_1)+P(s_2|s_2)V(s_2)+\cdots +P(s_n|s_1)V(s_n)],\\ V(s_2)& =R(s_2)+\gamma [P(s_1|s_2)V(s_1)+P(s_2|s_2)V(s_2)+\cdots +P(s_n|s_2)V(s_n)],\\ ⋮& \\ V(s_n)& =R(s_n)+\gamma [P(s_1|s_n)V(s_1)+P(s_2|s_n)V(s_2)+\cdots +P(s_n|s_n)V(s_n)]\end{array}$$

我们将所有状态的价值表示成一个列向量$\mathcal{V}=[V(s_1),V(s_2),\dots {]}^T$ ，同理，将奖励函数写成一个列向量$\mathcal{R}=[R(s_1),R(s_2),\dots {]}^T$ 。于是我们可以将贝尔曼方程写成矩阵的形式：

$$\mathcal{V}=\mathcal{R}+\gamma \mathcal{P}\mathcal{V}$$

展开矩阵形式

$$\left\{\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_n)\end{array}\right\}=\left\{\begin{array}{c}R(s_1)\\ R(s_2)\\ ⋮\\ R(s_n)\end{array}\right\}+\gamma \left\{\begin{array}{cc}P(s_1|s_1)& P(s_2|s_1)\dots P(s_n|s_1)\\ P(s_2|s_1)& P(s_2|s_2)\dots P(s_n|s_2)\\ ⋮& ⋮\\ P(s_n)& P(s_2|s_n)\dots P(s_n|s_n)\end{array}\right\}\left\{\begin{array}{cc}P(s_1|s_1)& P(s_2|s_1)\dots P(s_n|s_1)\\ P(s_2|s_1)& P(s_2|s_2)\dots P(s_n|s_2)\\ ⋮& ⋮\\ P(s_n)& P(s_2|s_n)\dots P(s_n|s_n)\end{array}\right\}$$

得到

$$\begin{array}{r}\mathcal{V}-\gamma \mathcal{P}\mathcal{V}=\mathcal{R}\\ (\mathcal{I}-\gamma \mathcal{P})\mathcal{V}=\mathcal{R}\end{array}$$

其中 $\mathcal{I}$ 是 $n\times n$ 的单位矩阵。如果 $(\mathcal{I}-\gamma \mathcal{P})$ 可逆，则价值向量的解析解为：

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

以上解析解的计算复杂度是 $O(n{)}^3$，其中是状态个数，因此这种方法只适用很小的马尔可夫奖励过程
求解较大规模的马尔可夫奖励过程中的价值函数时，可以使用动态规划（dynamic programming）算法、蒙特卡洛方法（Monte-Carlo method）和时序差分（temporal difference）

一个简单例子

假设一个状态 $s$ 的即时奖励是 2（$R(s)=2$），折扣因子 $\gamma =0.9$ 。从 $s$ 出发，有 70% 的概率去到一个价值为 10 的状态 $s1$，有 30% 的概率去到一个价值为 1 的状态 $s2$。

那么状态 $s$的价值计算如下：

$$V(s)=2+0.9\ast (0.7\ast 10+0.3\ast 1)=2+0.9\ast (7+0.3)=2+0.9\ast 7.3=2+6.57=8.57$$