马尔可夫决策过程——智能体和环境的交互
- 马尔可夫过程/马尔卡夫链
-
- 马尔可夫过程的定义和性质
- 马尔可夫过程的描述
- 采样
- 马尔可夫奖励过程（
M
R
P
MRP
MRP） -
- 马尔可夫奖励过程（
M
R
P
MRP
MRP）的定义 - 马尔可夫奖励过程（
M
R
P
MRP
MRP）的价值量化 -
- 回报
G
t
(
R
e
t
u
r
n
)
G_t(Return)
Gt(Return) - 价值函数
V
(
s
)
(
v
a
l
u
e
f
u
n
c
t
i
o
n
)
V(s)(value\\text{ } function)
V(s)(value function) -
- 价值
- 价值函数
- 回报
- 马尔可夫奖励过程（
- 马尔可夫决策过程（
M
D
P
MDP
MDP） -
- 马尔可夫决策过程（
M
D
P
MDP
MDP）的表征 - 策略（Policy）
- MDP中具体策略的价值量化
-
- 状态价值函数（state-value function）
- 动作价值函数（action-value function）
- 状态访问分布与占用度量
-
- 状态访问分布（state visitation distribution）
- 占用度量（occupancy measure）
- 最优策略（optimal policy）
- 马尔可夫决策过程（
马尔可夫过程/马尔卡夫链
马尔可夫过程的定义和性质
定义：任意时刻的状态只取决于上一个相邻状态的无外部动作干预的自发的随机过程。 数学表示为：
P
(
S
t
+
1
∣
S
1
,
S
2
,
.
.
.
,
S
t
)
=
P
(
S
t
+
1
∣
S
t
)
P(S_{t+1}\\mid S_1,S_2,…,S_t)=P(S_{t+1}\\mid S_t)
P(St+1∣S1,S2,…,St)=P(St+1∣St) 等式左边意味着该过程是依赖于历史上状态。等式右边则意味着该随机过程只依赖于上一个相邻的状态，也即具有马尔卡夫性质。因此称该自发的随机过程为马尔卡夫过程，也称为马尔卡夫链。 要求任意时刻的状态只取决于上一个相邻状态的马尔卡夫性质实质上是在假设任意时刻的状态包含之前所有状态的“信息”。只有如此，一旦我们知道
S
t
S_t
St，更早的状态不再提供任何额外的信息。
马尔可夫过程的描述
根据马尔可夫过程的定义，我们不难看出这个过程关注的重点在于状态转移。因此，我们通常用元组
<
S
,
P
>
<S,P>
<S,P>描述一个马尔可夫过程，其中
S
S
S是有限数量的状态集合，
P
P
P 是状态转移矩阵（
s
t
a
t
e
t
r
a
n
s
i
t
i
o
n
m
a
t
r
i
x
state transition matrix
statetransitionmatrix）。假设一共有
n
n
n个状态，此时
S
=
S
1
,
S
2
,
.
.
.
,
S
n
S={S_1,S_2,…,S_n}
S=S1,S2,…,Sn。状态转移矩阵
P
P
P定义了所有状态对之间的转移概率，即
P
=
∣
p
(
s
1
∣
s
1
)
p
(
s
2
∣
s
1
)
.
.
.
p
(
s
n
∣
s
1
)
p
(
s
1
∣
s
2
)
p
(
s
2
∣
s
2
)
.
.
.
p
(
s
n
∣
s
2
)
.
.
.
.
.
.
.
.
.
.
.
.
p
(
s
1
∣
s
n
)
p
(
s
2
∣
s
n
)
.
.
.
p
(
s
n
∣
s
n
)
∣
P=\\begin{vmatrix} p(s_1|s_1) & p(s_2|s_1)& …& p(s_n|s_1)\\\\ p(s_1|s_2)& p(s_2|s_2) &…&p(s_n|s_2)\\\\ … & … &…&…\\\\ p(s_1|s_n)& p(s_2|s_n) &…&p(s_n|s_n) \\end{vmatrix}
P=
p(s1∣s1)p(s1∣s2)…p(s1∣sn)p(s2∣s1)p(s2∣s2)…p(s2∣sn)…………p(sn∣s1)p(sn∣s2)…p(sn∣sn)
矩阵
P
P
P中第
i
i
i行第
j
j
j列元素
P
(
s
j
∣
s
i
)
=
P
(
S
t
+
1
=
s
j
)
∣
S
t
=
s
i
)
P(s_j|s_i)=P(S_{t+1}=s_j)|S_t=s_i)
P(sj∣si)=P(St+1=sj)∣St=si)示从状态
s
i
s_i
si到状态
s
j
s_j
sj的概率，我们称
P
(
s
′
∣
s
)
P(s^{'}|s)
P(s′∣s)为状态转移函数。从某个状态出发，到达其他状态的概率和必须为 1，即状态转移矩阵
P
P
P的每一行的和为 1。 下图是一个马尔卡夫过程的例子： 
采样
给定一个马尔可夫过程，我们就可以从某个状态出发，根据它的状态转移矩阵生成一个状态序列（episode），这个步骤也被叫做采样（sampling）。 马尔可夫过程是一个随机过程，描述了从任何一个状态出发后能自发转化状态的所有可能性。而采样则是在确定初始状态后其能自发转换状态的其中一条可能性。
马尔可夫奖励过程（
M
R
P
MRP
MRP）
马尔可夫奖励过程（
M
R
P
MRP
MRP）的定义
是在马尔可夫过程的基础上，增加了奖励函数 R(s) 和折扣因子γ，用于量化长期累积奖励。其中奖励函数定义了“在当前状态下能获得多少即时奖励”，折扣因子决定了“未来奖励的现值”。MRP是刻画无干预环境下长期回报的数学模型。
马尔可夫奖励过程（
M
R
P
MRP
MRP）的价值量化
回报
G
t
(
R
e
t
u
r
n
)
G_t(Return)
Gt(Return)
在一个马尔可夫奖励过程中，从第t时刻状态S_t
开始，直到终止状态时，所有奖励的衰减之和称为
开始，直到终止状态时，所有奖励的衰减之和称为
开始，直到终止状态时，所有奖励的衰减之和称为G_t(Return)$，公式如下：
G
t
=
R
t
+
γ
R
t
+
1
+
γ
2
R
t
+
2
+
.
.
.
G_t=R_t+\\gamma R_{t+1}+\\gamma^2R_{t+2}+…
Gt=Rt+γRt+1+γ2Rt+2+…
=
∑
k
=
0
∞
γ
k
R
t
+
k
(2.1)
=\\sum_{k=0}^{\\infty}\\gamma^kR_{t+k}\\text{ (2.1)}
=k=0∑∞γkRt+k (2.1)
=
R
t
+
γ
∑
k
=
1
∞
γ
k
−
1
R
t
+
k
=
R
t
+
γ
G
t
+
1
(2.2)
\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }=R_t+\\gamma\\sum_{k=1}^{\\infty}\\gamma^{k-1}R_{t+k}=R_t+\\gamma G_{t+1}\\text{ (2.2)}
=Rt+γk=1∑∞γk−1Rt+k=Rt+γGt+1 (2.2) 第一个等式说明了自初始时刻后的每一时刻按次序对状态的奖励以进行指数方式助剂折减后再加入回报的量化体系中。 第二个等式说明的任意马尔可夫奖励过程在t时刻的回报等于初始状态的奖励加上t+1时刻回报的折减。这暗示着奖励 r(s) 是环境的固有属性，一个状态的奖励值不会直接改变另一个状态的奖励值。但回报
G
t
G_t
Gt通过递推关系在时间上前后耦合。
价值函数
V
(
s
)
(
v
a
l
u
e
f
u
n
c
t
i
o
n
)
V(s)(value\\text{ } function)
V(s)(value function)
价值
回报
G
t
(
R
e
t
u
r
n
)
G_t(Return)
Gt(Return)描述的是从第t时刻状态S_t
开始一个马尔可夫奖励过程（从第
t
时刻状态
S
t
开始一个马尔可夫奖励过程（从第t时刻状态S_t
开始一个马尔可夫奖励过程（从第t时刻状态St开始的马尔可夫奖励过程中的一种可能性）的奖励累计方式。然而从第t时刻状态
S
t
S_t
St开始的马尔可夫奖励过程可能不止一条。根据前文所提到的回报定义可知：初始状态的奖励加上t+1时刻回报的折减。 因此，即使从同一时刻状态出发经过不同路径的回报值都不同。为了综合考虑从特定时刻状态开始的马尔可夫奖励过程回报，我们提出了价值概念：在马尔可夫奖励过程中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值（value）。
价值函数
价值综合考虑了从特定状态出发的马尔可夫奖励过程的回报。但是马尔可夫奖励过程可以理论上可以从状态集合中任意状态出发。未来将所有状态的价值（value）纳入同一量化体系，我们又提出了价值函数（value function）。价值函数的输入为某个状态，输出为这个状态的价值。可以认为一个状态的价值是价值函数的其中一个解析解。 我们将价值函数写成：
V
(
s
)
=
E
[
G
t
∣
S
t
=
s
]
(2.3)
V(s)=\\mathbb{E}[G_t|S_t=s]\\text{ (2.3)}
V(s)=E[Gt∣St=s] (2.3) 代入（2.2）展开得：
V
(
s
)
=
E
[
R
t
+
γ
G
t
+
1
∣
S
t
=
s
]
V(s)=\\mathbb{E}[R_t+\\gamma G_{t+1}|S_t=s]
V(s)=E[Rt+γGt+1∣St=s]
=
E
[
R
t
∣
S
t
=
s
]
+
γ
E
[
G
t
+
1
∣
S
t
=
s
]
(2.4)
\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }=\\mathbb{E}[R_t|S_t=s]+\\gamma \\mathbb{E}[G_{t+1}|S_t=s]\\text{ (2.4)}
=E[Rt∣St=s]+γE[Gt+1∣St=s] (2.4)
根据前文的阐述： r(s) 是环境的固有属性，一个状态的奖励值不会直接改变另一个状态的奖励值。任意状态的奖励之间相互独立，互不干涉。因此，
给定St的奖励Rt是一个常数，等于
r
(
S
t
=
s
)
因此，
E
[
R
t
∣
S
t
=
s
]
=
r
(
s
)
(2.5)
\\text{给定St的奖励Rt是一个常数，等于}r(S_t=s)\\text{因此，}\\mathbb{E}[R_t|S_t=s]=r(s)\\text{ (2.5)}
给定St的奖励Rt是一个常数，等于r(St=s)因此，E[Rt∣St=s]=r(s) (2.5)
在马尔可夫过程的状态集合S的个数为n时，给定
S
t
=
s
S_t=s
St=s的情况下，
∀
s
′
∈
S
且
P
(
s
′
∣
s
)
≠
0
,
S
t
+
1
=
s
′
\\forall s^{'}\\in S且P(s^{'}|s)\\ne0,S_{t+1}=s^{'}
∀s′∈S且P(s′∣s)=0,St+1=s′。给定
S
t
=
s
S_t=s
St=s下等价于给定t+1时刻所有状态的可能取值。又因为价值函数可以输出以任何状态为输入的价值（回报的期望）。则：在给定
S
t
=
s
S_t=s
St=s下的
V
(
S
t
+
1
)
V(S_{t+1})
V(St+1)可以输出
S
t
=
s
S_t=s
St=s下第t+1时刻的所有价值（回报的期望）。对输出的所有价值求期望即可得到在给定
S
t
=
s
S_t=s
St=s下第t+1时刻的价值期望。 我们不难发现：在给定
S
t
=
s
S_t=s
St=s下的t+1时刻的回报本身是包含多个状态开始的回报。因此，对t+1时刻其中的一个状态的回报求期望本质上就是t+1时刻可能出现的某种状态回报的期望，即某种状态的价值。对t+1时刻所有可能状态的价值求期望就是给定
S
t
=
s
S_t=s
St=s下第t+1时刻的价值期望。 因此可以推理出：
E
[
G
t
+
1
∣
S
t
=
s
]
=
E
[
V
(
S
t
+
1
)
∣
S
t
=
s
]
\\mathbb{E}[G_{t+1}|S_t=s]=\\mathbb{E}[V(S_{t+1})|S_t=s]
E[Gt+1∣St=s]=E[V(St+1)∣St=s]
数学证明过如下：
E
[
G
t
+
1
∣
S
t
=
s
]
=
E
s
′
E
G
[
G
(
s
′
)
∣
S
t
=
s
,
S
t
+
1
=
s
′
]
\\mathbb{E}[G_{t+1}|S_t=s]=\\mathbb{E}_{s^{'}}\\mathbb{E}_{G}[G(s^{'})|S_t=s,S_{t+1}=s^{'}]
E[Gt+1∣St=s]=Es′EG[G(s′)∣St=s,St+1=s′]
E
s
′
E
G
[
G
(
s
′
)
∣
S
t
=
s
,
S
t
+
1
=
s
′
]
=
E
s
′
[
E
G
[
G
(
s
′
)
∣
S
t
+
1
=
s
′
]
∣
S
t
=
s
]
\\mathbb{E}_{s^{'}}\\mathbb{E}_{G}[G(s^{'})|S_t=s,S_{t+1}=s^{'}]=\\mathbb{E}_{s^{'}}[\\mathbb{E}_{G}[G(s^{'})|S_{t+1}=s^{'}]|S_t=s]
Es′EG[G(s′)∣St=s,St+1=s′]=Es′[EG[G(s′)∣St+1=s′]∣St=s] 根据价值函数的定义可得：
E
s
′
[
E
G
[
G
(
s
′
)
∣
S
t
+
1
=
s
′
]
∣
S
t
=
s
]
=
E
s
′
[
V
(
s
′
)
∣
S
t
=
s
]
\\mathbb{E}_{s^{'}}[\\mathbb{E}_{G}[G(s^{'})|S_{t+1}=s^{'}]|S_t=s]=\\mathbb{E}_{s^{'}}[V(s^{'})|S_t=s]
Es′[EG[G(s′)∣St+1=s′]∣St=s]=Es′[V(s′)∣St=s] 综上所述：
E
[
G
t
+
1
∣
S
t
=
s
]
=
E
[
V
(
S
t
+
1
)
∣
S
t
=
s
]
(2.6)
\\mathbb{E}[G_{t+1}|S_t=s]=\\mathbb{E}[V(S_{t+1})|S_t=s]\\text{ (2.6)}
E[Gt+1∣St=s]=E[V(St+1)∣St=s] (2.6)
由（2.4）（2.5）（2.6）以及期望的定义可得：
V
(
s
)
=
r
(
s
)
+
γ
∑
s
′
∈
S
P
(
s
′
∣
s
)
V
(
s
′
)
(2.7)
V(s)=r(s)+\\gamma\\sum_{s^{'}\\in S}P(s^{'}|s)V(s^{'}) \\text{ (2.7)}
V(s)=r(s)+γs′∈S∑P(s′∣s)V(s′) (2.7) 上式就是马尔可夫奖励过程中非常有名的贝尔曼方程（Bellman equation）。我们将所有状态的价值表示成一个列向量V；将奖励函数写成一个列向量。于是我们可以将贝尔曼方程写成矩阵的形式：
V
=
R
+
γ
P
V
(2.8)
V=R+\\gamma PV \\text{ (2.8)}
V=R+γPV (2.8) 求解所有状态的价值的解析解为：
V
=
(
I
−
γ
P
)
−
1
R
(2.9)
V=(I-\\gamma P)^{-1}R \\text{ (2.9)}
V=(I−γP)−1R (2.9)
马尔可夫决策过程（
M
D
P
MDP
MDP）
MRP是自发的随机过程，环境属性 P,R,γ 决定了状态演化规律。MDP引入了动作 a，它是智能体与环境交互的唯一接口。策略π 通过控制动作序列来引导环境状态的演化，智能体的行为可以全映射为轨迹分布——在所有可能状态-动作序列上的概率分布。后者才是强化学习。 
马尔可夫决策过程（
M
D
P
MDP
MDP）的表征
- S：状态的集合；
- A：动作的集合；
-
γ
\\gamma
γ：折扣因子； -
r
(
s
,
a
)
r(s,a)
r(s,a)：是奖励函数，此时奖励可以同时取决于状态s和动作a -
P
(
s
′
∣
s
,
a
)
P(s^{'}|s,a)
P(s′∣s,a):是状态转移函数，表示在状态s执行动作a之后到达状s
′
s^{'}
s′态的概率。
策略（Policy）
策略描述的是智能体在接收到环境的状态
S
t
S_t
St时做出某种动作a的可能性。数学表示为：
π
(
a
∣
s
)
=
P
(
A
t
=
a
∣
S
t
=
s
)
\\pi(a|s)=P(A_t=a|S_t=s)
π(a∣s)=P(At=a∣St=s) 由该式子可以看出策略可以视为；同一时刻从状态到动作的同步映射。使用同一套策略说明状态-动作映射规则完全相同。 当一个策略是确定性策略（deterministic policy）时，它在每个状态时只输出一个确定性的动作，即只有该动作的概率为 1，其他动作的概率为 0；当一个策略是随机性策略（stochastic policy）时，它在每个状态时输出的是关于动作的概率分布，然后根据该分布进行采样就可以得到一个动作。
由于马尔可夫性质的存在,
S
t
S_t
St蕴含了之前所有状态的信息，因此，策略只需要与当前状态有关，不需要考虑历史状态。
综上，MDP的环境由状态空间 S、状态转移概率 P、奖励函数 R 和折扣因子 γ 定义，动作空间 A 是智能体与环境的接口。智能体的本质是一个 (s,a) 控制器，其核心是策略 π(a∣s)——从状态到动作的映射规则。
MDP中具体策略的价值量化
状态价值函数（state-value function）
定义为从状态s出发遵循策略
π
\\pi
π能获得的期望回报，数学表达为：
V
π
(
s
)
=
E
[
G
t
∣
S
t
=
s
]
(3.1)
V^{\\pi}(s)=\\mathbb{E}[G_t|S_t=s]\\text{ (3.1)}
Vπ(s)=E[Gt∣St=s] (3.1)
=
E
a
E
G
[
G
t
∣
S
t
=
s
,
A
t
=
a
]
\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }=\\mathbb{E}_{a}\\mathbb{E}_{G}[G_t|S_t=s,A_t=a]
=EaEG[Gt∣St=s,At=a]
=
∑
a
′
∈
A
π
(
a
′
∣
s
)
(
E
G
[
G
t
∣
S
t
=
s
,
A
t
=
a
′
]
)
\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }=\\sum_{a^{'}\\in A}\\pi(a^{'}|s)(\\mathbb{E}_{G}[G_t|S_t=s,A_t=a^{'}])
=a′∈A∑π(a′∣s)(EG[Gt∣St=s,At=a′])
=
∑
a
′
∈
A
π
(
a
′
∣
s
)
(
E
G
[
R
t
+
γ
V
(
S
t
+
1
)
∣
S
t
=
s
,
A
t
=
a
′
]
]
)
=\\sum_{a^{'}\\in A}\\pi(a^{'}|s)(\\mathbb{E}_{G}[R_t+\\gamma V(S_{t+1})|S_t=s,A_t=a^{'}]])
=a′∈A∑π(a′∣s)(EG[Rt+γV(St+1)∣St=s,At=a′]])
=
∑
a
′
∈
A
π
(
a
′
∣
s
)
(
r
(
s
,
a
)
+
γ
∑
s
′
∈
S
p
(
s
′
∣
s
,
a
′
)
V
(
s
′
)
)
(3.2)
=\\sum_{a^{'}\\in A}\\pi(a^{'}|s)(r(s,a)+\\gamma \\sum_{s^{'}\\in S}p(s^{'}|s,a^{'})V(s^{'}))\\text{ (3.2)}
=a′∈A∑π(a′∣s)(r(s,a)+γs′∈S∑p(s′∣s,a′)V(s′)) (3.2) 最后一步则为：状态价值函数的贝尔曼期望方程（Bellman Expectation Equation）
动作价值函数（action-value function）
在 MDP 遵循策略时，对当前状态执行动作得到的期望回报：
Q
π
(
s
,
a
)
=
E
[
G
t
∣
S
t
=
s
,
A
t
=
a
]
(3.3)
Q^{\\pi}(s,a)=\\mathbb{E}[G_t|S_t=s,A_t=a]\\text{ (3.3)}
Qπ(s,a)=E[Gt∣St=s,At=a] (3.3) 由（3.1）（3.3）可知：
V
π
(
s
)
=
∑
a
∈
A
π
(
a
∣
s
)
Q
π
(
s
,
a
)
(3.4)
V^{\\pi}(s)=\\sum_{a\\in A}\\pi(a|s)Q^{\\pi}(s,a)\\text{ (3.4)}
Vπ(s)=a∈A∑π(a∣s)Qπ(s,a) (3.4) 对（3.3）展开得到：
Q
π
(
s
,
a
)
=
r
(
s
,
a
)
+
γ
E
[
V
π
(
S
t
+
1
)
∣
S
t
=
s
,
A
t
=
a
]
Q^{\\pi}(s,a)=r(s,a)+\\gamma \\mathbb{E}[V^{\\pi}(S_{t+1})|S_t=s,A_t=a]
Qπ(s,a)=r(s,a)+γE[Vπ(St+1)∣St=s,At=a]
=
r
(
s
,
a
)
+
γ
∑
s
′
∈
S
p
(
s
′
∣
s
,
a
)
V
π
(
s
′
)
=r(s,a)+\\gamma\\sum_{s^{'}\\in S}p(s^{'}|s,a)V^{\\pi}(s^{'})
=r(s,a)+γs′∈S∑p(s′∣s,a)Vπ(s′)
=
r
(
s
,
a
)
+
γ
∑
s
′
∈
S
p
(
s
′
∣
s
,
a
)
∑
a
′
∈
A
π
(
a
′
∣
s
′
)
Q
π
(
s
′
,
a
′
)
(3.5)
\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }=r(s,a)+\\gamma\\sum_{s^{'}\\in S}p(s^{'}|s,a)\\sum_{a^{'}\\in A}\\pi(a^{'}|s^{'})Q^{\\pi}(s^{'},a^{'})\\text{ (3.5) }
=r(s,a)+γs′∈S∑p(s′∣s,a)a′∈A∑π(a′∣s′)Qπ(s′,a′) (3.5) 最后一步则为：动作价值函数的贝尔曼期望方程（Bellman Expectation Equation）
通过价值函数和动作价值函数的贝尔曼期望方程我们可知道，MDP中所能获得的价值一部分由环境固有属性，如：折扣因子、转化矩阵以及奖励函数；一部分由状态分布/动作-状态分布。而智能体与环境的唯一接口是动作。因此，可以认为智能体通过策略
π
\\pi
π驱动来动作的决策来“控制”状态分布/动作-状态分布，使其价值函数/动作价值达到最大。 因此，需要根据智能体能控制状态/动作-状态的能力来评价智能体的优劣。这就是为什么状态访问分布与占用度量被提出的原因。
状态访问分布与占用度量
状态访问分布（state visitation distribution）
在MRP中，状态的奖励会以指数衰减的方式逐级折扣。因此，智能体控制一个状态的能力也以指数衰减的方式逐级折扣，数学上表示为：
∑
t
=
0
∞
γ
t
P
t
π
(
s
)
\\sum_{t=0}^{\\infty}\\gamma^{t}P_{t}^{\\pi}(s)
∑t=0∞γtPtπ(s) 若以这种方式作为状态访问分布，当我们对所有状态的状态访问求和会发现：
∑
s
∑
t
=
0
∞
γ
t
P
t
π
(
s
)
=
∑
t
=
0
∞
γ
t
∑
s
P
t
π
(
s
)
=
∑
t
=
0
∞
γ
t
=
1
1
−
γ
\\sum_{s}\\sum_{t=0}^{\\infty}\\gamma^{t}P_{t}^{\\pi}(s)=\\sum_{t=0}^{\\infty}\\gamma^{t}\\sum_{s}P_{t}^{\\pi}(s)=\\sum_{t=0}^{\\infty}\\gamma^{t}=\\frac{1}{1-\\gamma}
∑s∑t=0∞γtPtπ(s)=∑t=0∞γt∑sPtπ(s)=∑t=0∞γt=1−γ1 所有状态的状态访问之和不为1。为了将它变成概率分布，则需要乘以
1
−
γ
1-\\gamma
1−γ。 状态访问分布定义为：
v
π
(
s
)
=
(
1
−
γ
)
∑
t
=
0
∞
γ
t
P
t
π
(
s
)
(3.1)
v^{\\pi}(s)=(1-\\gamma)\\sum_{t=0}^{\\infty}\\gamma^{t}P_{t}^{\\pi}(s)\\text{ (3.1)}
vπ(s)=(1−γ)t=0∑∞γtPtπ(s) (3.1) 状态访问分布度量了策略驱使环境趋向状态s 的能力。
状态访问概率表示一个策略和 MDP 交互会访问到的状态的分布。需要注意的是，理论上在计算该分布时需要交互到无穷步之后，但实际上智能体和 MDP 的交互在一个序列中是有限的。不过我们仍然可以用以上公式来表达状态访问概率的思想，状态访问概率有如下性质：
v
π
(
s
)
=
(
1
−
γ
)
v
0
(
s
)
+
(
1
−
γ
)
∑
t
=
1
∞
γ
t
P
t
π
(
s
)
v^{\\pi}(s)=(1-\\gamma)v_0(s)+(1-\\gamma)\\sum_{t=1}^{\\infty}\\gamma^{t}P_{t}^{\\pi}(s)
vπ(s)=(1−γ)v0(s)+(1−γ)t=1∑∞γtPtπ(s)
P
t
π
(
s
)
=
∫
P
(
s
∣
s
′
,
a
)
π
(
a
∣
s
′
)
P
t
−
1
π
(
s
′
)
d
s
d
a
P_{t}^{\\pi}(s)=\\int P(s|s^{'},a)\\pi (a|s^{'})P^{\\pi}_{t-1}(s^{'})dsda
Ptπ(s)=∫P(s∣s′,a)π(a∣s′)Pt−1π(s′)dsda 代入
(
1
−
γ
)
∑
t
=
1
∞
γ
t
P
t
π
(
s
)
=
(
1
−
γ
)
∑
t
=
1
∞
γ
t
∫
P
(
s
∣
s
′
,
a
)
π
(
a
∣
s
′
)
P
t
−
1
π
(
s
′
)
d
s
d
a
(1-\\gamma)\\sum_{t=1}^{\\infty}\\gamma^{t}P_{t}^{\\pi}(s)=(1-\\gamma)\\sum_{t=1}^{\\infty}\\gamma^{t}\\int P(s|s^{'},a)\\pi (a|s^{'})P^{\\pi}_{t-1}(s^{'})dsda
(1−γ)∑t=1∞γtPtπ(s)=(1−γ)∑t=1∞γt∫P(s∣s′,a)π(a∣s′)Pt−1π(s′)dsda 令k=t-1代入可得：
(
1
−
γ
)
∑
t
=
1
∞
γ
t
P
t
π
(
s
)
=
(
1
−
γ
)
∑
k
=
0
∞
γ
k
+
1
∫
P
(
s
∣
s
′
,
a
)
π
(
a
∣
s
′
)
P
k
π
(
s
′
)
d
s
d
a
(1-\\gamma)\\sum_{t=1}^{\\infty}\\gamma^{t}P_{t}^{\\pi}(s)=(1-\\gamma)\\sum_{k=0}^{\\infty}\\gamma^{k+1}\\int P(s|s^{'},a)\\pi (a|s^{'})P^{\\pi}_{k}(s^{'})dsda
(1−γ)t=1∑∞γtPtπ(s)=(1−γ)k=0∑∞γk+1∫P(s∣s′,a)π(a∣s′)Pkπ(s′)dsda
=
γ
∫
P
(
s
∣
s
′
,
a
)
π
(
a
∣
s
′
)
[
(
1
−
γ
)
∑
k
=
0
∞
γ
k
P
k
π
(
s
)
]
=\\gamma\\int P(s|s^{'},a)\\pi (a|s^{'})[(1-\\gamma)\\sum_{k=0}^{\\infty}\\gamma^{k}P^{\\pi}_k(s)]
=γ∫P(s∣s′,a)π(a∣s′)[(1−γ)k=0∑∞γkPkπ(s)] 则：
v
π
(
s
)
=
(
1
−
γ
)
v
0
(
s
)
+
γ
∫
P
(
s
∣
s
′
,
a
)
π
(
a
∣
s
′
)
v
π
(
s
′
)
d
s
d
a
(3.2)
v^{\\pi}(s)=(1-\\gamma)v_0(s)+\\gamma\\int P(s|s^{'},a)\\pi(a|s^{'})v^{\\pi}(s^{'})dsda \\text{ (3.2)}
vπ(s)=(1−γ)v0(s)+γ∫P(s∣s′,a)π(a∣s′)vπ(s′)dsda (3.2) 从（3.2）可知：状态分布本身是一个迭代的过程。
占用度量（occupancy measure）
如果说状态访问分布将智能体从某一初始状态出发在策略π指引下，控制状态使之往某一特定状态s趋向的“控制”能力表征为智能体从某一初始状态出发在策略π指引下访问s概率。那么，占用度量则更进一步，描述了智能体从某一初始状态出发在策略π指引下，通过特定动作a，控制环境使之趋向状态s的能力。 将占用度量数学描述为：
ρ
π
(
s
,
a
)
=
(
1
−
γ
)
∑
t
=
0
∞
γ
t
P
t
π
(
s
)
π
(
a
∣
s
)
(3.3)
\\rho^{\\pi}(s,a)=(1-\\gamma)\\sum_{t=0}^{\\infty}\\gamma^{t}P^{\\pi}_{t}(s)\\pi(a|s) \\text{ (3.3)}
ρπ(s,a)=(1−γ)t=0∑∞γtPtπ(s)π(a∣s) (3.3) 由
P
t
π
(
s
)
π
(
a
∣
s
)
=
P
t
π
(
s
,
a
)
P^{\\pi}_{t}(s)\\pi(a|s)=P^{\\pi}_{t}(s,a)
Ptπ(s)π(a∣s)=Ptπ(s,a)可以看出，占用度量实质上是在描述智能体用一种特定动作a，控制环境使之维持在状态s的能力。 由（3.1）（3.3）易知：
ρ
(
s
,
a
)
=
v
π
(
s
)
π
(
a
∣
s
)
(3.4)
\\rho(s,a)=v^{\\pi}(s)\\pi(a|s) \\text{ (3.4)}
ρ(s,a)=vπ(s)π(a∣s) (3.4) 由式（3.4）可知：占用度量可以理解为状态访问分布对动作方向的投影。而该投影规则则是使用的策略。 由前文分析可知：占用度量有且仅描述了MDP中除了环境属性外的所有要素。因此，在同一环境中，占用度量和策略全映射。 基于此，我们可推出定理1：
ρ
π
1
=
ρ
π
2
⇔
π
1
=
π
2
(3.5)
\\rho^{\\pi_1}=\\rho^{\\pi_2}\\Leftrightarrow \\pi_1=\\pi_2 \\text{ (3.5)}
ρπ1=ρπ2⇔π1=π2 (3.5) 同理可推定理2： 给定一合法占用度量，可生成该占用度量的唯一策略是:
π
ρ
=
ρ
(
s
,
a
)
∑
a
′
ρ
(
s
,
a
′
)
(3.6)
\\pi_{\\rho}=\\frac{\\rho(s,a)}{\\sum_{a^{'}}\\rho(s,a^{'})}\\text{ (3.6)}
πρ=∑a′ρ(s,a′)ρ(s,a) (3.6)
最优策略（optimal policy）
强化学习的目标通常是找到一个策略，使得智能体从初始状态出发能获得最多的期望回报。我们首先定义策略之间的偏序关系：当且仅当对于任意的状态s都有
V
π
(
s
)
≥
V
π
′
(
s
)
V^{\\pi}(s)\\ge V^{\\pi^{'}}(s)
Vπ(s)≥Vπ′(s)，记；
π
≥
π
′
\\pi \\ge \\pi^{'}
π≥π′。于是在有限状态和动作集合的 MDP 中，至少存在一个策略比其他所有策略都好或者至少存在一个策略不差于其他所有策略，这个策略就是最优策略（optimal policy）。最优策略可能有很多个，我们都将其表示为
π
∗
(
s
)
\\pi^{*}(s)
π∗(s)。 最优策略都有相同的状态价值函数，我们称之为最优状态价值函数，表示为：
V
∗
(
s
)
=
max
π
V
π
(
s
)
，
∀
s
∈
S
(3.7)
V^{*}(s)=\\max_{\\pi } V^{\\pi}(s)，\\forall s\\in S\\text{ (3.7)}
V∗(s)=πmaxVπ(s)，∀s∈S (3.7) 同理，我们定义最优动作价值函数:
Q
∗
(
s
,
a
)
=
max
π
Q
π
(
s
,
a
)
，
∀
s
∈
S
,
a
∈
A
Q^{*}(s,a)=\\max_{\\pi}Q^{\\pi}(s,a)，\\forall s\\in S,a\\in A
Q∗(s,a)=πmaxQπ(s,a)，∀s∈S,a∈A 综上，最优策略
π
∗
\\pi^{*}
π∗是所有策略中能使长期累积回报期望最大化的策略。执行该策略所获得的价值函数，即为最优价值函数。其中，最优状态价值是执行最优策略时从状态s出发的期望回报，它等于在该状态下选择最优动作所能获得的期望回报. 因此，最优策略、最优状态价值和最优动作价值三者是统一的：最优策略通过贪心地选择最大化 的动作，来达到最优状态价值。 数学表示为：
Q
∗
(
s
,
a
)
=
r
(
s
,
a
)
+
γ
∑
s
′
∈
S
P
(
s
′
∣
s
,
a
)
V
∗
(
s
′
)
Q^{*}(s,a)=r(s,a)+\\gamma \\sum_{s^{'}\\in S}P(s^{'}|s,a)V^{*}(s^{'})
Q∗(s,a)=r(s,a)+γs′∈S∑P(s′∣s,a)V∗(s′) 由前文分析可知：占用度量可以理解为状态访问分布对动作方向的投影。而该投影规则则是使用的策略。因此，在最优策略之下：
V
∗
=
max
a
∈
A
Q
∗
(
s
,
a
)
V^{*}=\\max_{a\\in A}Q^{*}(s,a)
V∗=a∈AmaxQ∗(s,a)
