有限马尔可夫MDP是序列决策的经典形式化表达，其动作不仅影响当前的即时收益，还影响后续的状态，以及未来的收益。【即时收益和延迟收益之间权衡的需求】
3.1 智能体-环境 交互接口
智能体【agent】:进行学习及实施决策的机器
环境【environment】:智能体之外所有能与其相互作用的实物
通过环境状态，智能体选择动作，环境对动作做出相应的响应，并向智能体呈现新的状态，同时环境也产生一个收益，通常是特定的数值，这是智能体在动作选择过程中想要最大化的目标
即\(S_0,A_0,R_1,S_1,A_1,R_2.S_2,A_2,R_3...\)【S是状态，A是动作，R是收益】
3.1.1 一些概率分布
1 \(R_t,S_t\)离散概率分布
随机变量\(R_t,S_t\)具有明确定义的离散概率分布，并且只依赖于\(S_{t-1},A_{t-1}\)
\[
p(s',r|s,a)=P\{S_t=s',R_t=r|S_{t-1}=s,A_{t-1}=a\}
\]
显然
\[
\sum_{s'\in \mathcal{S} }\sum_{r\in \mathcal{R} }p(s',r|s,a)=1,\forall s \in \mathcal{S} ,a\in \mathcal{A} (s)
\]
这就是说\(R_t,S_t\)的概率只取决于前一个状态和前一个动作，并且与更早之前的状态和动作完全无关。该限制不是针对决策过程，而是针对状态。状态必须包括过去智能体和环境交互之间的各种信息，这些信息对未来产生一定影响，这样，状态就被认为具有马尔可夫性。
2 状态转移概率
\[
p(s'|s,a)=P\{S_t=s'|S_{t-1}=s,A_{t-1}=a\}=\sum_{r\in\mathcal{R}}p(s',r|s,a)
\]
状态-动作二元组的期望收益
\[
r(s,a)=E[R_t|S_{t-1}=s,A_{t-1}=a]=\sum_{r\in \mathcal{R}}r\sum_{s'\in \mathcal{S}}p(s',r|s,a)
\]
状态-动作-后续状态三元组的期望收益
\[
r(s,a,s')=E[R_t|S_{t-1}=s,A_{t-1}=a,S_t=s']=\sum_{r\in \mathcal{R}}r\frac{p(s',r|s,a)}{p(s'|s,a)}
\]
3.1.2 动作、状态的定义
动作可以是任何我们想要做的决策，而状态则可以是任何对决策有所帮助的事情。
3.1.3 智能体与环境的界限
智能体和环境的界限通常与机器人或动物身体的物理边界不同，如果我们将MDP框架应用到人或动物上，肌肉、骨骼和感知器官也应视为环境的一部分，类似，收益发生在自然或人工学习系统的物理结构之内【物理边界内】，但却在智能体之外
遵循的一般规则：智能体不能改变的事物都被认为在外部的，即环境的一部分。智能体通常会知道如何通过一个动作和状态的函数来计算所得到的的收益，因为它定义了智能体的任务。因此，智能体不能随意改变它。智能体和环境的界限划分仅仅决定智能体进行绝对控制的边界，而不是知识的边界。
3.1.4 MDP框架是目标导向的交互式学习问题的一个高度抽象
MDP框架提出，任何目标导向的行为学习问题都可以概况为智能体及环境来回传递的三个信号：1.智能体做出的选择【行动】2.做出该选择的基础【状态】3.定义智能体的目标【利益】
不同的任务，特定的状态和动作的定义差异很大，且其性能极易受其表征方式的影响。
3.2 目标和收益
我们所有的目标或目的可以归结为：最大化智能体接收到的标量信号(称之为收益)累计和的概率期望值
我们提供收益的方式必须要使智能体在最大化利益的同时也实现我们的目标。因此，至关重要的一点就是，我们设立收益的方式要能真正表明我们的目标。例如，国际象棋智能体只有当最终获胜时才能得到收益，而非某个子目标，比如吃掉对方的子或控制中心区域，如果把这些作为收益，智能体可能会找到某种即使输掉也实现这些子目标的方式。因此，这些先验知识最好的办法是设置初始的策略，或初始价值函数。
收益信号只能传达什么是你要实现的目标，而不是如何实现这个目标
3.3 回报和分幕
智能体的目标就是最大限额地提高长期受益。时刻t后接受的收益序列\(R_{t+1},R_{t+2},...\),Wimbledon寻求的是最大化期望回报，即为\(G_t\),它被定义为收益序列的一些特定函数，最简单情况，回报是收益的总和
3.3.1 有最终时刻【分幕式任务】
\[
G_t=R_{t+1}+R_{t+2}+...R_{T}
\]
这种情况下，智能体和环境的交互能被自然的分为一系列子序列(每个子序列都存在最终时刻),我们称每一个子序列为幕(episodes),每一幕都以一种特殊状态结束，称之为终结状态。具有这种分幕重复性的任务被称为分幕式任务，我们有时需要区分非终结状态集，记为\(\mathcal{S}\),和包含终结与非终结状态的所有状态集\(\mathcal{S}^+\),终结的时间T是一个随机变量，通常随幕的不同而不同。
3.3.2 持续性任务
因为\(T=+\infty\)，所以按照如上方式，回报也为趋向于无穷，因此我们通常用一种在概念上稍显复杂，但数学上更为简单的回报定义。即引入折扣的概念，使得其在未来收到经过折扣系数加权后的收益总和是最大化的，
\[
G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\gamma^3 R_{t+4}+...=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}=R_{t+1}+\gamma G_{t+1}
,0\le\gamma\le 1
\]
3.4 分幕式和持续性任务的统一表示方法
分幕式的情况，我们把幕的终止当作一个特殊的吸收状态的入口，它只会转移到自己并只产生零收益。
\[
G_t=\sum_{k=t+1}^{T}\gamma^{k-t-1}R_{k}
\]
T包括无穷的情况
3.5 策略和价值函数
价值函数是状态(或状态-动作二元组)的函数，用来评估当前智能体在给定状态(或给定状态和动作)下又多好【回报的期望值有多高】。智能体期望未来能得的收益取决于智能体所选择的动作，因此，价值函数与特定的行为方式有关，我们称之为策略
策略是状态到每个动作选择概率之间的映射。策略\(\pi,\pi(a|s)\)就是当\(S_t=s,A_t=a\)的概率。强化学习方法规定智能体的策略如何随其经验而发生改变。
状态价值函数
我们把策略\(\pi\)下状态s的价值函数记为\(v_\pi(s)\),即从状态s开始，智能体按照策略\(\pi\)进行决策所获得的回报的概率期望值
\[
v_\pi(s)=E_\pi[G_t|S_t=s]=E_\pi[\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}|S_t=s]
\]
动作价值函数
我们把策略\(\pi\)下载状态s时所采取的动作a的价值记为\(q_\pi(s,a)\)
\[
q_\pi(s,a)=E_\pi[G_t|S_t=s,A_t=a]=E_\pi[\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}|S_t=s,A_t=a]
\]
3.5.1 蒙特卡洛估算方法
智能体遵循策略\(\pi\),并对每一个遇到的状态都记录该状态后的实际回报的平均值，那么状态出现次数趋向于无穷，这个平均值也会收敛到状态价值\(v_\pi(s)\)。动作价值函数也是类似
3.5.2动态规划方法
\(v_\pi\)的贝尔曼方程
\[
\begin{aligned}
v_\pi(s) &=E_\pi[G_t|S_t=s]=E_\pi[R_{t+1}+\gamma G_{t+1}|S_t=s]\\
&=\sum_{a} \pi(a|s)\sum_{s'}\sum_{r} p(s',r|s,a)[r+\gamma E_\pi[G_{t+1}|S_{t+1}=s']]\\
&=\sum_{a} \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]\\
\end{aligned}
\]
3.6 最优策略和最优价值函数
$$
\begin{aligned}
v_* (S)&=\mathop{\max}_ {\pi} v_\pi(s)=\mathop{\max}_ {a} E_{\pi_* }[G_t|S_t=s,A_t=a]\
&=\mathop{\max}_ {a} E_{\pi_* }[R_{t+1} +\gamma G_{t+1}|S_t=s,A_t=a]\
&=\mathop{\max}_ {a} \sum_{s',r} p(s',r|s,a)[r+\gamma v_* (s')]\
q_* (s,a)&=\mathop{\max}_ {\pi} q_\pi(s,a)=E[R_{t+1}+\gamma v_* (S_{t+1})|S_t=s,A_t=a]\
&=\sum_{s',r}p(s',r|s,a)[r+\gamma \mathop{\max}_ {a'} q_* (s',a')]
\end{aligned}
$$
贝尔曼最优方程：最优策略下各个状态的价值一定等于这个状态下最有动作的期望回报
状态最优价值就是取其下面动作期望回报的最大值
动作最优价值取该动作下所有状态的期望【状态价值函数的变化引起了动作价值函数的变化】
3.7 最优性和近似计算
由于算力、存储容量等影响，我们不得不认真面对近似的问题，需要设计实现有用的近似算法，近似最优行为中，智能体可能有大量的状态，每个状态出现概率都很低，这使得选择次优的动作对整个智能体所获得的收益影响很小。