分类目录：《深入理解强化学习》总目录

在文章《深入理解强化学习——马尔可夫决策过程：马尔可夫奖励过程-[价值函数]》中，我们知道即时奖励的期望正是奖励函数的输出，即：$E[R_t|S=s]=r(s)$。另一方面，等式中剩余部分$E[\gamma V(S_{t+1})|S_t=s]$可以根据从状态出发的转移概率得到，即可以得到：
$$V(s)=r(s)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s)V(s^{\prime })$$

上式就是马尔可夫奖励过程中的贝尔曼方程（Bellman Equation），对每一个状态都成立。若一个马尔可夫奖励过程一共有$n$个状态，即 S = { s 1 , s 2 , ⋯   , s n } S=\{s_1, s_2, \cdots, s_n\} S={s1​,s2​,⋯,sn​}，我们将所有状态的价值表示成一个列向量$V=[V(s_1),V(s_2),\cdots ,V(s_n){]}^T$，同理，将奖励函数写成一个列向量。于是我们可以将贝尔曼方程写成矩阵的形式：
$$\begin{gathered} V=R+\gamma PV \\ \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}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_n)\end{array}\right]\left[\begin{array}{ccc}p(s_1|s_1)& \cdots & p(s_n|s_1)\\ ⋮& \ddots & ⋮\\ p(s_1|s_n)& \cdots & p(s_n|s_n)\end{array}\right]\left[\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_n)\end{array}\right] \end{gathered}$$

我们可以直接根据矩阵运算求解，得到以下解析解：
$$V=(I-\gamma P{)}^{-1}R$$

以上解析解的计算复杂度是$O(n^3)$，其中$n$是状态个数，因此这种方法只适用很小的马尔可夫奖励过程。求解较大规模的马尔可夫奖励过程中的价值函数时，可以使用动态规划（Dynamic Programming）算法、蒙特卡洛方法（Monte-Carlo Method）和时序差分（Temporal Difference），这些方法将在后面的文章。

def compute(P, rewards, gamma, states_num):
    ''' 利用贝尔曼方程的矩阵形式计算解析解,states_num是MRP的状态数 '''
    rewards = np.array(rewards).reshape((-1, 1))  #将rewards写成列向量形式
    value = np.dot(np.linalg.inv(np.eye(states_num, states_num) - gamma * P),
                   rewards)
    return value

参考文献：
[1] 张伟楠, 沈键, 俞勇. 动手学强化学习[M]. 人民邮电出版社, 2022.
[2] Richard S. Sutton, Andrew G. Barto. 强化学习（第2版）[M]. 电子工业出版社, 2019
[3] Maxim Lapan. 深度强化学习实践（原书第2版）[M]. 北京华章图文信息有限公司, 2021
[4] 王琦, 杨毅远, 江季. Easy RL：强化学习教程 [M]. 人民邮电出版社, 2022