决策者在整个决策阶段收到一系列的报酬折现以后累加起来就是具体的效用函数，我们称之为无限阶段的折扣模型。具体的表达如下

$$ V_{\beta}(i,\pi)=\sum_{0}^{\infty} \beta^{t} E_{\pi}^{i}[r(Y_{t}, \Delta_{t})] $$

从上面的表达式折扣因子就是$\beta$, $\Delta_{t}$表示采用不同的动作，$Y_{t}$表示状态的变换。这里给出一个定理

$$\begin{gathered}V_{\beta}(i,\pi)=\sum_{0}^{\infty} \beta^{t} E_{\pi}^{i}[r(Y_{t}, \Delta_{t})] \\ =\sum_{a \in A(i)} \pi_{0}(a|i)[r(i,a)+\beta \sum_{j \in S} p(j|i,a)V_{\beta}(j,\pi')]\end{gathered}$$

其中$p(j|i,a)$表示在状态i下采用动作a后到状态j的概率分布。这里和强化学习里的转移概率是一致的。$\pi'$表示终止报酬的和。

这里我们直接列举一个MDP的问题，看下面的表格。

由于状态空间和行动集合都是有限的，我们知道存在最优的平稳策略（这是一个定理，要记住的）。且平稳策略有两个

$$\begin{gathered}f=(a_{1}, a_{3}) \\ g=(a_{2}, a_{3})\end{gathered}$$

此时的最优方程为

$$\begin{gathered}v(1)=max\{5+0.5\beta v(1)+0.5\beta v(2), 10+\beta v(2) \} \\ v(2)=-1+\beta v(2)\end{gathered}$$

以上方程的v(1)和v(2)表示除以1状态和2状态的效用函数
直接解上面的第二个方程， $v(2)=\frac{-1}{1-\beta}$,将其带入第一个方程。

$$ v(1)=max\{5-0.5\frac{\beta}{1-\beta}+0.5\beta v(1), 10-\frac{\beta}{1-\beta}\}=Tv(1) \tag{1.1} $$

对$\beta=0,0.5,0.9$分别解1.1,得到的最优值函数分别为

$$\begin{gathered}V_{0}=(10,1) \\ V_{0.5}=(9,-2) \\ V_{0.9}=(1,10) \\\end{gathered}$$

策略迭代算法

从上面一个例子我们面对一个确定性问题如何求解，那么当我们使用算法的时候怎么表达的，下面就看看迭代策略如何来做。这里需要补充一下，上面那个手算过程可以通过一个方程来表达。
下面我们来看一个定理，如果状态空间S是离散且使用策略是平稳策略，的那么会有如下的一些关系。

$$ v_{\beta}(f^{\infty})=f(f)+\beta P(f) v $$

也就是说当前的效用函数等于策略回报和折扣指数与效用函数和概率分布的乘积的和。上面的表达式使用矩阵的表达方式如下

$$ v_{\beta}(f^{\infty})=(I-\beta P(f))^{-1} r(f) \tag{1.2} $$

策略迭代算法
使用当前策略$f_{n}$, 通过公式1.2能够求得当前策略的效用函数$v_{\beta}(f_{n}^{\infty})$

策略改进选用新的策略$f_{n+1}$,为一个$v_{\beta}(f_{n}^{\infty})$的改进策略，当满足

$$ f_{n+1} \in arg\ max\{r(f)+\beta P(f)V_{\beta}(f_{n}^{\infty})\} $$

如果$f_{n+1}=f_{n}$策略停止，选取最优策略完成，否则n+=1

算法中往往求解以上表达式后，再通过策略更新后比较两个策略的最优解，同样的下面我们也来看一个例子。对于一下的MDP过程，如何求解最优策略,其中$\beta=0.9$。

以上决策过程有4个平稳策略

$$\begin{gathered}f_{1}=(1,1) \\ f_{2}=(1,2) \\ f_{3}=(2,1) \\ f_{4}=(2,2) \\ \end{gathered}$$

第一个迭代过程求$f_{1}$为初始策略作为求值运算，就是解以下方程组

$$\begin{gathered}v(1)=6+0.9[0.5v(1)+0.5v(2)] \\ v(2)=-3+0.9[0.4v(1)+0.6v(2)] \\\end{gathered}$$

求得 $v(1)=V_{0.9}(1, f_{1}^{\infty})=15.49$ $v(2)=V_{0.9}(2, f_{1}^{\infty})=5.6$.表示在不同的状态下，使用动作1，对应的状态1和2的效用函数。这里$V_{0.9}(1, f_{1}^{\infty})$表示在0.9折扣回报下，所有的策略在处在状态1下的期望总共的回报和。

下一步进行策略迭代。对于状态1而言

$$ max_{a \in (1,2)}\{r(1,a)+0.9 \sum_{j \in S} p(j|1,a) v_{0.9}(j,f_{1}^{\infty})\}=max(15.49, 16.16) $$

这里就是在状态1下分别采用1和2动作下取得的收益

$$\begin{gathered}15.49=6+0.9(0.5*15.49+0.5*5.6) \\ 16.16=4+0.9(0.8*15.49+0.2*5.6)\end{gathered}$$

因此在状态1下行动2是最大值，所以改进策略在状态1应该采用行动2，同样对状态2进行策略改进。

$$ max_{a \in (1,2)}\{r(2,a)+0.9 \sum_{j \in S} p(j|2,a) v_{0.9}(j,f_{1}^{\infty})\}=max(5.6, 6.27) $$

说明状态2，行动2是最大值，故改进策略在状态2应该采用行动2，这样得到改进策略$f_{4}$.

第二次迭代过程，对$f_{4}$重复第一个迭代过程。解方程$v(1)=V_{0.9}(1,f_{4}^{\infty})=22.2$, $v(2)=V_{0.9}(2,f_{4}^{\infty})=12.31$.并且发现现在策略满足停止条件，这样最优策略就是目前的策略。最优的值函数就是(22.2,12.31).到这里我们的值函数就求解完成，下节会介绍一些求解值函数的算法。