马尔科夫决策过程(MDP)
1.1 MDP介绍
MDP是马尔科夫链的一种扩展。提供了一个用于对决策情景建模的数学框架。
MDP可以由5个关键要素表示：
- 智能体能够真正处于的一组状态（S)。
- 智能体从一种状态转移到另一种状态所执行的一组行为（A）。
- 转移概率（\(P_{ {ss}’}^{a}\)）,这是执行某一个行为\(a\),从一个状态\(s\)转移到另一个状态\({s}'\)的概率。
- 奖励概率（\(R_{ {ss}'}^a\)），这是执行某一个行为\(a\),状态转移后获得奖励的概率。
- 折扣因子(\(\gamma\)),控制着即时奖励和未来奖励的重要性。
1.1.1 奖励和回报
智能体试图使得从环境中获得的总奖励最大化，而不是及时奖励。智能体获得的奖励总额可计算如下：
\[ R_t=r_{t+1}+r_{t+2}+r_{t+3}+\cdots+r_T \tag {1} \]1.1.2 情景和连续任务
情景任务是具有一个终端状态的任务，在强化学习中，情景可以看做从初始状态到最终状态中智能体与环境的交互。
在连续任务中，没有终端状态。
1.1.3 折扣因数
已知智能体的任务是使得汇报最大化。对于一个情景任务，可以定义回报为\(R_t=r_{t+1}+r_{t+2}+r_{t+3}+\cdots+r_T\),其中，T是情景的最终状态，且试图使得回报\(R_t\)最大化。
在连续任务中没有最终状态，根据上式的定义，其回报会为\(\infty\)。
所以引入折扣因数，重新定义回报如下：
\[ R_t=r_{t+1}+\gamma r_{t+2}+\gamma ^2r_{t+3}+\cdots = \sum_{k=0}^{\infty}{\gamma ^k r_{t+k+1}} \tag {2} \] 折扣因数\(\gamma\)的最优值在\(0.2\sim0.8\)1.1.4 策略函数
表示将状态映射到行为，记为\(\pi\)
1.1.5 状态值函数
状态值函数也称值函数，该函数是确定一个智能体在策略\(\pi\)下处于某一个特定状态的最佳程度。值函数通常记为\(V(S)\)，表示执行该策略后状态的值。
定义状态值函数为：
\[ V^{\pi}(S)=E_{\pi} \left[ R_t|s_t=s \right ] \] 将式\((2)\)代入上式中的\(R_t\)值，可得：\[ V^{\pi}(s)=E_{\pi} \left [ \sum_{k=0}^{\infty} \gamma ^kr_{t+k+1}|s_t=s \right ] \]1.1.6 状态——行为值函数（Q函数）
状态——行为值函数也称Q函数，是用来表明智能体遵循策略\(\pi\)在某一状态所执行的特性行为的最佳程度。Q函数记为\(Q(s)\)。表明遵循策略\(\pi\)在某一状态下采取行为的值。
Q函数定义如下：
\[ Q^{\pi}(s,a)=E_{\pi}[R_t|s_t=s,a_t=a] \] 将式\((2)\)代入上面的公式，可得：\[ Q^{\pi}(s,a)=E_{\pi}[\sum_{k=0}^{\infty} \gamma ^kr_{t+k+1}|s_t=s,a_t=a] \] 值函数与Q函数的区别在于值函数是确定状态的最佳程度，而Q函数是确定某一状态下行为的最佳程度1.2 Bellman方程和最优性
Bellman方程用于求解MDP问题，也就是解决寻找最优策略和值函数。根据不同的策略，存在许多不同的值函数。最优值函数\(V^*(s)\) 就是与所有值函数相比，能够产生最大值的值函数：
\[ V^*(s)=max_{\pi}V^{\pi}(s) \] 同理，最优策略就是能够产生最优值函数的策略。由于最优值函数\(V^*(s)\) 是与所有其他值函数相比，具有最大值的函数，因此也是Q函数的最大值。为此，通过取Q函数最大值可以计算最优值函数。
\[ V^*(s)=max_aQ^*(s,a) \tag {3} \] 值函数的Bellman方程可以表示为：\[ V^{\pi}(s)= \sum_a \pi (s,a) \sum_{s^`}p_{ss^`}^a[R_{ss^`}^a + \gamma V^{\pi}(s^`)] \] 上式表示一个状态的值与其下一状态的值之间以及所有可能状态平均值之间的递归关系。同理，Q函数的Bellman方程可表示为：
\[ Q^{\pi}(s,a)=\sum_{s'}p_{ss'}^a[R_{ss'}^a + \gamma \sum_{a'}Q^{\pi}(s',a')] \tag {4} \] 将式(4)代入式(3)，可得：\[ V^*(s)=max_a\sum_{s'}p_{ss'}^a[R_{ss'}^a + \gamma \sum_{a'}Q^{\pi}(s',a')] \]