马尔可夫决策过程的经典五元组，我们再来看看。

$${T, S, A(i), p(*|i,a), r(i,a)}$$

这就是构成马尔可夫决策过程的环境，当你在业务问题找到这些变量的关系的，就能够使用马尔可夫决策构造一个经典的模型。本章节我们来讲解有限阶段模型。

最优准则

我们先来介绍报酬效用函数的定义，也可以称之为值函数

$$V_{N}(i,\pi)=\sum_{t=0}^{N-1} E_{\pi}^{i}[r(Y_{t}, \Delta_{t})]+E_{\pi}^{i}[r(Y_{N})]$$

上面的效用函数表示0时刻从状态i出发，直到N时刻结束的总报酬。其中$\Delta_{t}$表示当前时刻的动作，$Y_{N}$表示终止时刻的收益，$r(Y_{t}, \Delta_{t})$表示在决策时刻t说处于的$Y_{t}$使用动作$\Delta_{t}$后取得的报酬。顺理成章的最优的值函数一定符合的条件是

$$V_{N}^{*}(i)=sup\ V_{N}(i,\pi)$$

现实中我们希望每个时刻都采用系统的最优决策，但是实际问题中，可能只需要知道一些特定的初始状态就行啦，也就是只要极大化$\sum_{i \in S} V_{N}(i,\pi) \mu(Y_{i}=i)$,其中$\mu(Y_{i}=i)$表示初始状态的概率分布。也就是在$\mu(Y_{i}=i)>0$的那些i极大化我们的效用函数$V_{N}(i,\pi)$就可以啦。

有限阶段的策略迭代和最优方程

有限阶段的建模方式通常是使用动态规划方式递归求取报酬的期望值，这里有些晕晕，咱们先往后看。

当决策时刻的是表示为$h_{t}=(i_{0}, a_{0},..,i_{t})$, 那么从t时刻到n时刻的总报酬为

$$\mu_{t}^{\pi}=E_{\pi}\{\sum_{t}^{N-1}R_{n}(\pi)+R_{n}(T_{n})|h_{t},Y_{t}=i_{t}\}$$

这里$V_{N}(i,\pi)$和$\mu_{t}^{\pi}(i)$的区别在于$V_{N}(i,\pi)$表示的是决策从0时刻到N时刻的总报酬，而$\mu_{t}^{\pi}(i)$表示的是t时刻以后的总报酬。
下面我们就来看看有限阶段迭代算法。

step1, t=N, $\mu_{N}^{\pi}(h_{N})=r_{N}(i_{N})$
step2, 如果t=0停止，否则t-=1
step3, 对于每个状态i和每个历史的$h_{t}=(h_{t-1},a_{t-1},i_{t})$，计算

$$\mu_{t}^{\pi}(h_{t})=r_{t}(i_{t},a_{t}(h_{t}))+\sum_{j \in S} p_{t}(j|i_{t},a_{t}(h_{t})) \mu_{t+1}^{\pi}(h_{t},a_{t}(h_{t}), j)$$

这里$a_{t}(h_{t})$表示这个行动选取依赖的历史$h_{t}$， $p_{t}(j|i_{t},a_{t}(h_{t}))$表示在状态i下，采用动作a后到达j的概率。

根据上面这个算法，就能计算任意一个策略的有限阶段值函数啦，但是这个是十分不方便的，因为每次都需要根据以前所有的历史计算。所以我们一般定义最优方程为

$$\mu_{t}^{\pi}(h_{t})=sup|r_{t}(i_{t},a)+\sum_{j \in S} p_{t}(j|i_{t},a) \mu_{t+1}^{\pi}(h_{t},a, j)|$$

通过最优方程的定义，带来了好处是对每个时刻t，最优方程的解就是从时刻t到结束阶段的最优报酬值。

举个例子

咱们就来列举经典的秘书问题，话说有这么一场面试，有N个候选人，面试的规则是面试完一个人以后有两种动作，要么你就是放弃当前面试者并且继续面试，要么就是选择当前面试者，那么以什么样的策略能够选择到所有面试者中最优秀的人呢？ 很明显这也是一个序列决策问题，下面我们就要用马氏方式定义这个问题。

决策时刻

$$T=\{1,2,..,N\}$$

可能的状态

$$S=\{0,1,\Delta \}$$

0表示没有选择当前的候选人，1表示选择当前候选人，使用$\Delta$表示过程停止。

行动集合

\begin{equation} A(i)=\left\{ \begin{array}{ll} \{C,Q\} ,i \in S \\ \{C\} , i=\Delta \\ \end{array}\right. \end{equation}

C表示拒绝当前候选人，Q表示接受当前候选人。

报酬

\begin{equation} r(i,a)=\left\{ \begin{array}{ll} 0 , a=C \\ \frac{t}{N}, a=Q \\ 0, i=\Delta \\ \end{array}\right. \end{equation} \right.

这里需要好好解释一下，当我们拒绝当前候选人的时候，我们的收益就是0，当时当我们选择当前候选人的时候，它的收益是$\frac{t}{N}$,这里表示选中的候选人是在所有候选人中最优秀的概率。这里我们这样看待这个概率问题。
以上的概率P这样定义

$$P=\frac{从N个候选人中选取t个人且包含最优秀的候选的取法}{从N个人中取t个人的所有取法}=\frac{C_{N-1}^{t-1}}{C_{N}^{t}}=\frac{t}{N}$$

转移概率

\begin{equation} p_{t}(j|i,a)=\left\{ \begin{array}{ll} \frac{1}{t} , a=C,j=1 \\ \frac{t-1}{t}, a=C, j=0 \\ 1, a=Q, j=\Delta \\ 1, i=j=\Delta, a=C \\ 0, 其他 \\ \end{array}\right. \end{equation}

咱们来看看上面这个转移概率，从这个问题中我们能了解到，转移概率是不依赖当前状态i的，并且只要采取C过程就会继续下去，在t时刻恰好选到前t个人中最优秀的概率是$\frac{1}{t}$,那么未选中的就是$1-\frac{1}{t}$。这样转移概率就基本明确啦。到这里，整个的马氏过程就构建出来啦。

这里抽象出两个变量，$\mu_{t}^{*}(1)$表示刚刚面试的人是最优秀的候选人，从当前时段到过程结束能够面试到最好候选人的概率，$\mu_{t}^{*}(0)$表示当前时刻面试的不是最好候选人，在剩下的过程中能够面试到最好的候选人的概率。

$$\mu_{t}^{*}(1)=max\{r(1, Q)+\mu_{t+1}^{*}(\Delta), p_{t}(1|1,C)\mu_{t+1}^{*}(1)+p_{t}(0|1,C)\mu_{t+1}^{*}(0)\} \\ =max\{\frac{t}{N}, \frac{1}{t+1}\mu_{t+1}^{*}(1)+\frac{t}{t+1}\mu_{t+1}^{*}(0)\}\\$$

$$\mu_{t}^{*}(0)=max\{r(0, Q)+\mu_{t+1}^{*}(\Delta), p_{t}(1|0,C)\mu_{t+1}^{*}(1)+p_{t}(0|0,C)\mu_{t+1}^{*}(0)\} \\ =max\{0, \frac{1}{t+1}\mu_{t+1}^{*}(1)+\frac{t}{t+1}\mu_{t+1}^{*}(0)\}\\$$

当$\mu_{t+1}^{*}>0$的时候，化简一下

$$\mu_{t}^{*}(0)=\frac{1}{t+1}\mu_{t+1}^{*}(1)+\frac{t}{t+1}\mu_{t+1}^{*}(0) \\ \mu_{t}^{*}(1)=max\{\frac{t}{N}, \mu_{t}^{*}(0)\} \\$$

这里需要解释一下，$\mu_{t}^{*}(1)$的化简是使用t时刻的效用函数态度t+1时刻的效用函数。从$\mu_{t}^{*}(1)$可以知道，最优策略具有这样的结构，在t时刻如果是状态1，就有$\frac{t}{N}>\mu_{t}^{*}(0)$,那么就是最优动作就停止啦，如果$\frac{t}{N}<\mu_{t}^{*}(0)$,最优行动就是继续面试下一个候选人，如果相等就怎么做都可以。
定义$T=max\{\frac{t}{N}<\mu_{t}^{*}(0)\}+1$,假设对于某个t，$\frac{t}{N}<\mu_{t}^{*}(0)$，那么$\mu_{t}^{*}(0)=\mu_{t}^{*}(1)，\mu_{t-1}^{*}(0)=\frac{1}{t}\mu_{t}^{*}(1)+\frac{t+1}{t}\mu_{t}^{*}(0)=\mu_{t}^{*}(0)>\frac{t}{N}>\frac{t-1}{N}$,也就是说存在t<T-1,均有$\frac{t}{N}<\mu_{t}^{*}(0)$,又因为T的定义对存在的t>T,均有$\frac{t}{N}>\mu_{t}^{*}(0)$,说明策略的结构应该是连续面试T个人，然后录用第一个好过前面所有面试人的候选人。如何确定T呢？

如果存在$t>T$,由于$\frac{t}{N}>\mu_{t}^{*}(0)$，知道$\mu_{t}^{*}(1)=\frac{t}{N}$，因此存在t>T-1,有$\mu_{t}^{*}(0)=\frac{1}{t+1}\mu_{t+1}^{*}(1)+\frac{t}{t+1}\mu_{t+1}^{*}(0)=\frac{1}{N}+\frac{t}{t+1}\mu_{t+1}^{*}(0)$,注意到$\mu_{N}^{*}(0)=0$，那么$\frac{\mu_{t}^{*}(0)}{t}=\frac{\mu_{t+1}^{*}(0)}{t+1}+\frac{1}{tN}=\frac{1}{N} \sum_{k=t}^{N-1} \frac{1}{k}$.

综上，$T=\sum_{k=t}^{N-1} \frac{1}{k}$, $\int_{T}^{N} \frac{1}{x} dx=log(\frac{N}{T}), T=\frac{N}{e}$.
也就是说，先面试三分之一的人，然后发现面试人比前面面试人优秀就马上录用，就是以最大概率获得优秀的面试人。所以先面试未必是好事哦。