本文将介绍值函数 (Value function) 与马尔可夫决策过程(Markov Decision Processes, MDP)。
1 前言
上一节介绍了马尔可夫过程和马尔可夫奖励过程 (Markov Reward Processes, MRP)，这一节我们将介绍值函数 (Value function) 与马尔可夫决策过程。
2 值函数
值函数 $v(s)$ 定义为回报 $G_t$ 的数学期望，即
$$
v(s)=\mathbb{E}[G_t|S_t=s]
$$
$v(s)$ 的意义为从状态 $s$ 开始，获得的 $G_t$ 的数学期望。回顾一下，$G_t$ 的计算公式为
$$
G_t=R_{t+1}+\gamma R_{t+2}+…=\sum_{k=0}^{\infty}{\gamma ^kR_{t+k+1}}
$$
上一节中提到，某学生的学习过程可以有很多种，如下所示：
- C1 C2 C3 Pass Sleep，$G_1=-2.25$
- C1 FB FB C1 C2 Sleep，$G_1=-3.125$
- C1 C2 C3 Pub C2 C3 Pass Sleep，$G_1=-3.41$
- C1 FB FB C1 C2 C3 Pub C1 … ，$G_1=-3.20$
- … …
令 $\gamma=\frac{1}{2}$ ，可计算出每种学习过程的 $G_1$ 。理论上，根据 $v(s)$ 的定义，将所有 $G_1$ 求平均即可得到 $v(s)$。但实际上上述学习过程有无穷多个，因此需要采用其他方法计算 $v(s)$，该方法将在后面介绍。
3 马尔可夫决策过程
简单回顾一下，马尔可夫过程建模了环境的变化，可以用数学语言描述该过程；为了让智能体从环境中学习又引入了奖励，有了马尔可夫奖励过程；而智能体需要与环境交互，在前面的模型中，再引入智能体对环境的影响，就有了马尔可夫决策过程，MDP。智能体对环境的影响就通过动作 $\mathcal{A}$ 进行的。
3.1 定义
马尔可夫决策过程是可以进行决策的马尔可夫奖励过程，用元组 $<\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma>$ 描述，其中
- $\mathcal{S}$ 是状态集合
- $\mathcal{A}$ 是动作集合
- $\mathcal{P}$ 是状态转移矩阵 (与之前稍有不同)
- $\mathcal{R}$ 是奖励 (与之前稍有不同)
- $\gamma$ 是折损因子
前面提到，MDP 与 MRP 的不同就是引入了 $\mathcal{A}$，即智能体可以对环境产生影响。那么这个影响体现在哪里呢，就体现在 $\mathcal{P}$ 和 $\mathcal{R}$ 上。MDP 中的 $\mathcal{P}$ 和 $\mathcal{R}$ 不再只和状态有关，还和动作 $a\in \mathcal{A}$ 有关。智能体执行了不同的动作，会使环境的状态转移概率不同，也会收到不同的奖励值。
如下图所示，是一个描述学生学习的 MDP，其中的红色字体代表动作。现在，学生采取不同的动作，会进入不同的状态，也会获得不同的奖励。例如，在 Class 1 继续学习会获得 $-2$ 的奖励，并进入状态 Class 2；而在 Class 1 采取动作 Facebook 则会获得 $-1$ 的奖励，并进入状态 Facebook。采取同一动作也可能进入不同的状态，如在 Class 3 采取动作 Pub，则有 0.2 的概率进入 Class 1，0.4 的概率进入 Class 2，0.4 的概率进入 Class 3。
3.2 策略 (policy)
MDP 中的一个重要概念是策略，一个策略 $\pi$ 是关于状态的概率分布，定义为
$$
\pi(a|s)=\mathbb{P}{A_t=a|S_t=s}
$$
其意义为在状态 $s$ 采取每个动作的概率，有以下性质
- 一个策略完全定义了智能体的行为
- MDP 中的策略完全取决于当前状态
- 策略与时间无关
