摘要： 一条线上包含起点和终点共有6个格子，起点在左终点在右。假设智能体已经学到了最优的策略，并且在每一步行动时，以 $0.9$ 的概率选择最优策略（也就是往右），以 $0.1$ 的概率选择随机策略。各个概念的定义见文末参考链接，本文举实际的数值例子帮助理解。

定义

  智能体要从最左边的第一个格子走到最右边的终点一次走一步。把6个格子分别记作状态 $s_1,s_2,\cdots ,s_6$，动作有两种，分别记作 $L$ 和 $R$。如果不特别说明，一般随机变量为大写字母，具体数值为小写字母。$L$ 和 $R$ 表示动作，不是随机变量。

• 策略函数 (Policy Function) $\pi (a|s)$：在一个状态 $s_i$ 处采取每个动作 $a_i$ 的概率。简单记作 $\pi (L|s)=0.1,\pi (R|s)=0.9$，严谨写法为
  $$\{\begin{array}{ll}\pi (A=L|S=s_i)=0.1,\pi (A=R|S=s_i)=0.9,& i\ne 1\\ \pi (A=L|S=s_i)=0,\pi (A=R|S=s_i)=1,& i=1\end{array}$$
  如果在起点处往左走，环境给的反馈是智能体保持在起点不动。
    奖励 (Reward）： 智能体在状态 $s_i$ 处采取动作 $a_i$ 后，环境给的奖励 $r(s,a)$。$r(s=s_5,a=R)=6$（便于区分），其余的 $r(s,a)$ 都是0。
    (折扣)回报（Return）： 从第 $t$ 个回合开始计算的每个回合奖励的总和
  $$\begin{array}{rl}& U_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\cdots \\ & U_t=r_t+\gamma U_{t+1}\end{array}$$
  下面都能达到终点的的几个动作和对应的回报分别为
• RRRRR: $0+0\gamma +0{\gamma }^2+0{\gamma }^3+6{\gamma }^4$
• RRRLRRR: $0+0\gamma +0{\gamma }^2+0{\gamma }^3++0{\gamma }^4+0{\gamma }^5+6{\gamma }^6$
• RLRRRRLRR: $0+0\gamma +0{\gamma }^2+0{\gamma }^3++0{\gamma }^4+0{\gamma }^5+0{\gamma }^6++0{\gamma }^7+6{\gamma }^8$

  状态价值函数（State-Value Function）： 在状态 $s_i$ 处，采用当前策略 $\pi$ 时回报的期望。$V_{\pi }(s)=\mathbb{E}(U_t|s=s_i)$。
  动作价值函数（Action-Value Function）： 在状态 $s_i$ 处采取动作 $a_i$ 后，继续保持当前的总体策略 $\pi$ 时（也就是以 $0.9$ 的概率选择最优策略），回报的期望。$Q_{\pi }(s,a)=\mathbb{E}(U_t|s=s_i,a=a_i)$。
  最优动作价值函数（Optimal Action-Value Function）： 总是选择最优策略时回报的期望。$Q^{\ast }(s,a)=\mathbb{E}(U_t|s=s_i,a=a_i)$
  下面计算状态价值函数和最优动作价值函数。在这一个例子中，最优动作价值函数就是一直往右走，比较好计算。
$$\begin{array}{rl}& Q^{\ast }(s=s_1,a=R)=6{\gamma }^4\\ & Q^{\ast }(s=s_2,a=R)=6{\gamma }^3\\ & ⋮\\ & Q^{\ast }(s=s_5,a=R)=6\end{array}$$
下面计算当前策略下每个状态的状态价值函数。这里用到了一个简单的公式
$$V_{\pi }(s)=\mathbb{E}(U_t|s)=\mathbb{E}(r_t|s)+\gamma \mathbb{E}(U_{t+1}|s)=r_t(s)+\gamma V_{\pi }(s_{t+1})$$
其中 $\mathbb{E}(r_t|s)=r_t(s)$ 表示在状态 $s$ 时的期望奖励，$s_{t+1}$ 表示 $s$ 的下一个状态。在这个例子中，
$$\mathbb{E}(r_t|s)=\sum _a\mathbb{P}(a|s)r(s,a)=0.9r(s,R)+0.1r(s,L)$$
于是可以算出每个状态的期望奖励
$$\begin{array}{rl}& r(s_5)=0.9\cdot 6+0.1\cdot 0\\ & r(s_4)=R(s_3)=(s_2)=R(s_1)=0\end{array}$$
此时每个状态的状态价值函数为 （已知 $V_{\pi }(s_6)=6$）
$$\begin{array}{rl}& V_{\pi }(s_5)=r(s_5)+\gamma (0.9\cdot 6+0.1V_{\pi }(s_4))\\ & V_{\pi }(s_4)=r(s_4)+\gamma (0.9V_{\pi }(s_5)+0.1V_{\pi }(s_3))\\ & V_{\pi }(s_3)=r(s_3)+\gamma (0.9V_{\pi }(s_4)+0.1V_{\pi }(s_2))\\ & V_{\pi }(s_2)=r(s_2)+\gamma (0.9V_{\pi }(s_3)+0.1V_{\pi }(s_1))\\ & V_{\pi }(s_1)=r(s_1)+\gamma (0.9V_{\pi }(s_2)+0.1V_{\pi }(s_1))\end{array}$$
设 $\gamma =0.8$，可以解得
$$\begin{array}{rl}& V_{\pi }(s_5)=4.602433406284881\\ & V_{\pi }(s_4)=3.5304175785610044\\ & V_{\pi }(s_3)=2.708319075448633\\ & V_{\pi }(s_2)=2.080230236058876\\ & V_{\pi }(s_1)=1.6280062716982504\end{array}$$
求解的python代码如下

import numpy as np
A = np.array([[0.0, 0.08, 0.0, 0.0, 0.0],[0.72, 0.0, 0.08, 0.0, 0.0],[0.0, 0.72, 0.0, 0.08, 0.0],[0.0, 0.0, 0.72, 0.0, 0.08],[0.0, 0.0, 0.0, 0.72, 0.08]])
B = np.eye(5) - A
C = np.array([4.32, 0, 0, 0, 0])
D = np.matmul(np.linalg.inv(B) , C.T)
for n in range(5):print(D[n])

动作价值函数可以采用类似的方法计算。

贝尔曼方程

参考

1. 王树森 张志华，《深度强化学习（初稿）》
2. Mathematical Foundation of Reinforcement Learning -GitHub