引入马尔可夫决策过程(MDP)
在强化学习基础介绍的强化学习要素中，状态转移概率\(P_{ss'}^a\)不仅与上一个状态有关，也与之前所有状态形成的状态序列有关。为了减少建模的难度，我们假设状态的转移具有马尔可夫性，即转移到下一个状态的概率仅仅与上一个状态\(s\)有关，与以前的状态序列无关。以上假设可以使用公式表示：
\[ P_{ss'}^a = \mathbb{E}(S_{t+1}=s'|S_t=s, A_t=a) \]
除此之外，我们也对强化学习中的策略\(\pi\)进行了马尔可夫性的假设。即在状态\(s\)下采取的动作仅仅与当前状态有关，而与以前的状态序列无关。使用公式表示为：
\[ \pi(a|s) = P(A_t=a | S_t=s) \]
同样的，对于价值函数\(v_{\pi}(s)\)也有同样的操作：
\[ v_{\pi}(s) = \mathbb{E}_{\pi}(G_t|S_t=s ) = \mathbb{E}_{\pi}(R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3}+...|S_t=s) \]
其中\(G_t\)代表在状态\(s\)下的reward，它是一个马尔可夫过程中从状态\(s\)开始采样直到终止状态时所有即时奖励的有衰减的和。
MDP的价值函数与贝尔曼方程
MDP中除了状态价值函数\(v_{\pi}(s)\)以外，还有动作价值函数\(q_{\pi}(s,a)\),其表示的是动作\(a\)以及状态\(s\)联合对价值带来的影响。其计算公式为：
\[ q_{\pi}(s,a) = \mathbb{E}_{\pi}(G_t|S_t=s, A_t=a) = \mathbb{E}_{\pi}(R_{t+1} + \gamma R_{t+2}+...|S_t=s,A_t=a) \]
根据状态价值函数的表达式，我们可以得出状态价值函数的递推式：
\[ v_{\pi}(s) = \mathbb{E}_{\pi}(R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t=s) \]
这条方程被称为贝尔曼方程。它表示当前状态的价值可以由该状态的奖励以及后续状态的价值按照一定的衰减比例计算而成。
同样的方法，我们可以得到动作价值函数的贝尔曼方程:
\[ q_{\pi}(s,a) = \mathbb{E}_{\pi}(R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1}) | S_t=s, A_t=a) \]
状态价值函数与动作价值函数的递推关系
根据动作价值函数以及状态价值函数的定义，可以得到他们的转化关系公式：
\[ v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)q_{\pi}(s,a) \]
即状态价值函数是动作价值函数基于给定策略\(\pi\)的期望。
反过来，我们也可以使用状态价值函数表示动作价值函数：
\[ q_{\pi}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{\pi}(s') \]
即动作价值函数是即时奖励加上当前动作可能转移到的下一个状态的状态价值函数基于状态转移概率的有衰减的和。
根据以上公式，我们可以分别得到动作价值函数以及状态价值函数的递推式：
\[ v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{\pi}(s')) \]
\[ q_{\pi}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^a\sum\limits_{a' \in A} \pi(a'|s')q_{\pi}(s',a') \]
最优价值函数
寻找最优策略可以通过最优的价值函数来完成。可以定义最优状态价值函数是所有策略下产生的众多状态价值函数中的最大者。即\(v_{*}(s) = \max_{\pi}v_{\pi}(s)\)。
同理也可以定义最优动作价值函数是所有策略下产生的众多动作价值函数中的最大值：
\[ q_{*}(s,a) = \max_{\pi}q_{\pi}(s,a) \]
对于最优的策略，基于动作价值函数我们可以定义为：
\[ \pi_{*}(a|s)= \begin{cases} 1 & {a=\arg\max_{a \in A}q_{*}(s,a)}\\ 0 & {else} \end{cases} \]
此时利用状态价值函数与动作价值函数之间的关系，也可以得到：
\[ v_{*}(s) = \max_{a}q_{*}(s,a) \]