Bellman方程
推导过程
Bellman 方程可用于求解 MDP 问题，能够找到最优策略及其对应的价值函数。
当前状态 s 下 Agent 能获得的期望回报与后续状态之间的关联。
推导过程：
expert discounted return:
$\displaystyle{ \begin{equation} \begin{split} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\ &= R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3}) + \cdots \\ &= R_{t+1} + \gamma G_{t+1} \end{split} \end{equation} }$
价值函数（策略（$\displaystyle{ \pi }$ ）。当 Agent 位于 s，一直以策略 $\displaystyle{ \pi }$ 运行，s 回报的期望：）
$\displaystyle{ \begin{equation} \begin{split} v_\pi(s) &= E_\pi[G_t|S_t=s] \\ &= E_\pi[R_{t+1}+\gamma G_{t+1}|S_t=s] \\ &= \sum_{a} \pi(a|s) E_\pi[R_{t+1}+\gamma G_{t+1}|S_t=s, A_t=a] \end{split} \end{equation} }$
根据期望性质：$\displaystyle{ E(\sum_{i}a_iX_i)= \sum_{i}a_i E(X_i) }$
$\displaystyle{ \begin{equation} \begin{split} v_\pi(s) &= \sum_{a} \pi(a|s) E_\pi[R_{t+1}+\gamma G_{t+1}|S_t=s, A_t=a] \\ &= \sum_{a} \pi(a|s) E_\pi[R_{t+1}|S_t=s, A_t=a]+\sum_{a} \pi(a|s) E_\pi[\gamma G_{t+1}|S_t=s, A_t=a] \end{split} \end{equation} }$
第一项，根据期望的定义式 $\displaystyle{ E(X) = \sum_x xf(x) }$ ：
$\displaystyle{ \begin{equation} \begin{split} E_\pi[R_{t+1}|S_t=s, A_t=a] &= \sum_r rp(r|s, a) \\ &= \sum_r r \sum_{s'}p(s', r|s, a) \\ &= \sum_r \sum_{s'} p(s', r|s, a)r \end{split} \end{equation} }$
第二项，其中：
$\displaystyle{ E_\pi[\gamma G_{t+1}|S_t=s, A_t=a] = \sum_{s'}p(s'|s, a)E_\pi[\gamma G_{t+1}|S_t=s, A_t=a, S_{t+1}=s'] }$
根据 Markov Property，$\displaystyle{ G_{t+1} }$ 只与 t+1 时刻的状态和动作有关，与 t 时刻及之前的状态与动作无关：
$\displaystyle{ E_\pi[\gamma G_{t+1}|S_t=s, A_t=a, S_{t+1}=s'] = \sum_{s'}E_\pi[\gamma G_{t+1}|S_{t+1}=s']=\gamma v_\pi(s') }$
第二项推导：
$\displaystyle{ \begin{equation} \begin{split} \sum_{a} \pi(a|s) E_\pi[\gamma G_{t+1}|S_t=s, A_t=a] &= \sum_a \pi(a|s) \sum_{s'} p(s'|s,a) \gamma v_\pi(s') \\ &= \sum_a \pi(a|s) \sum_{s'} \sum_r p(s', r|s, a)\gamma v_\pi(s') \\ \end{split} \end{equation} }$
对两项进行替换：
$\displaystyle{ \begin{equation} \begin{split} v_\pi(s) &= \sum_{a} \pi(a|s) E_\pi[R_{t+1}+\gamma G_{t+1}|S_t=s, A_t=a] \\ &= \sum_{a} \pi(a|s) E_\pi[R_{t+1}|S_t=s, A_t=a]+\sum_{a} \pi(a|s) E_\pi[\gamma G_{t+1}|S_t=s, A_t=a]\\ &=\sum_{a} \pi(a|s)\sum_r \sum_{s'} p(s', r|s, a)r+ \sum_a \pi(a|s) \sum_{s'} \sum_r p(s', r|s, a)\gamma v_\pi(s')\\ &=\sum_{a} \pi(a|s)\sum_r \sum_{s'}p(s', r|s, a)[r+\gamma v_\pi(s')] \end{split} \end{equation} }$
矩阵形式和求解
矩阵形式：
$\displaystyle{ v = R + \gamma Pv }$
将矩阵和向量元素展示出来：
$\displaystyle{ \begin{bmatrix} v(1)\\ \vdots \\ v(n) \end{bmatrix} = \begin{bmatrix} R(1)\\ \vdots \\ R(n) \end{bmatrix} + \gamma \begin{bmatrix} p_{11}& \dots & p_{1n}\\ \vdots & & \vdots\\ p_{n1}& \dots & p_{nn} \end{bmatrix} \begin{bmatrix} v(1)\\ \vdots \\ v(n) \end{bmatrix} }$
Bellman方程是一个线性方程组，因此理论上解可以直接求解：
$\displaystyle{ \begin{equation} \begin{split} v&=R+\gamma Pv \\ (1-\gamma P)v&=R \\ v &= (1-\gamma P)^{-1}R \end{split} \end{equation} }$
这个解的计算复杂度是 $\displaystyle{ O(n^3) }$ ，n 是状态数量。因此直接求解仅适用于小规模的MRPs。
大规模MRP的求解通常使用迭代法。常用的迭代方法有：
- 动态规划 Dynamic Programming
- 蒙特卡洛评估 Monte-Carlo evaluation
- 时序差分学习 Temporal-Difference