有限马尔科夫决策过程（有限MDP）
- 前言
- 3.1 The Agent–Environment Interface(“智能体-环境”交互接口
- 3.2 Goals and Rewards（目标和收益）
- 3.3 Returns and Episodes（回报和分幕）
- 3.4 Unified Notation for Episodic and Continuing Tasks （分幕式和持续性任务的统一表示法）
- 3.5 Policies and Value Functions（策略和价值函数）
- 3.6 Optimal Policies and Optimal Value Functions（最优策略和最优价值函数）
- 3.7 Optimality and Approximation（最优性和近似算法）
前言
- 评估性反馈
- 发散联想(associative aspect)–不同情景下选择不同的动作。
- 当前收益与延迟收益的权衡
- q ∗ ( s , a ) q_*(s,a) q∗(s,a)， v ∗ ( a ) v_*(a) v∗(a)
3.1 The Agent–Environment Interface(“智能体-环境”交互接口
智能体（agent）–学习以及实施决策的机器
环境（environment）–智能体之外所有一切与之相互作用的事物。
动作（action）：智能体选择执行动作。
a
=
A
t
∈
A
(
s
)
a=A_t\in\mathcal{A}(s)
a=At∈A(s)
状态（state）：环境对智能体动作做出相应，并呈现新的状态。
S
t
∈
S
S_t\in \mathcal{S}
St∈S
收益（reward）：环境给智能体动作产生的一个收益
R
t
+
1
∈
R
⊂
R
R_{t+1}\in\mathcal{R}\subset \mathbb{R}
Rt+1∈R⊂R
上图表面了智能体与环境的交互过程，由此产生一个轨迹（trajectory）：
S
0
,
A
0
,
R
1
,
S
1
,
A
1
,
R
2
,
S
2
,
A
2
,
R
3
,
.
.
.
S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, . . .
S0,A0,R1,S1,A1,R2,S2,A2,R3,...
由马尔科夫属性（当前状态s’以及收益R只有上一时刻的状态s和动作a有关），我们可以定义MDP的动态特性：
p
(
s
′
,
r
∣
s
,
a
)
=
P
r
{
S
t
+
1
=
s
′
,
R
t
+
1
=
r
∣
S
t
=
s
,
A
t
=
a
}
p(s', r | s, a) = Pr \{S_{t+1} = s', R_{t+1} = r | S_t = s, A_t = a \}
p(s′,r∣s,a)=Pr{St+1=s′,Rt+1=r∣St=s,At=a}
这里通过下围棋的例子来解释：如果对手是环境，棋面是当前状态，根据当前状态选择这一手棋的动作，状态和动作确定后，“对手”环境也会下一手棋，状态改变，并且如果吃掉我们的子，就有负收益，如果我们的一手棋吃掉对手的子，就有正收益。因为“对手”的下法会有很多，就有很多可能出现的状态。p函数就描述了某一种的概率。
通过动态函数p，我们还可以计算出关于环境的信息：
- 转移到某一状态的概率–在状态s执行动作a转移到状态s‘的概率’： p ( s ′ ∣ s , a ) = P r { S t = s ′ ∣ S t = s , A t = a } = ∑ r ∈ R p ( s ′ , r ∣ s , a ) p(s'|s,a)=Pr\{S_t=s'| S_t = s, A_t = a \}=\sum_{r \in \mathcal{R}}p(s',r|s,a) p(s′∣s,a)=Pr{St=s′∣St=s,At=a}=r∈R∑p(s′,r∣s,a)
- 状态-动作二元组的期望收益，状态s执行动作a的回报期望值： r ( s , a ) = E [ R t ∣ S t − 1 = s , A t − 1 = a ] = ∑ r ∈ R r ∑ s ′ ∈ S p ( s ′ , r ∣ s , a ) r(s,a)=\mathbb{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)=E[Rt∣St−1=s,At−1=a]=r∈R∑rs′∈S∑p(s′,r∣s,a)
- 状态-动作-后继状态三元组的期望收益，状态s执行动作a状态转移到s’的期望回报： r ( s , a , s ′ ) = E [ R t ∣ S t − 1 = s , A t − 1 = a , S t = s ′ ] = ∑ r ∈ R r p ( s ′ , r ∣ s , a ) p ( s ′ ∣ s , a ) r(s,a,s')=\mathbb{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)} r(s,a,s′)=E[Rt∣St−1=s,At−1=a,St=s′]=r∈R∑rp(s′∣s,a)p(s′,r∣s,a)
MDP框架：
任何目标导向的行为学习问题可以概括为智能体和环境之间来回传递的三个信号：
- 行动
- 状态
- 收益
3.2 Goals and Rewards（目标和收益）
强化学习中，智能体的目标被形式化成收益，其目标就是最大化其受到的总收益，也就是说比如说我们想让智能体学会玩游戏，我们就通过衡量智能体在游戏中的最终得分来考察其是否达成目标。这就要求我们提供收益的方式必须使智能体在最大化收益的同时也实现我们的目标——也就是收益能够很好表明我们的目标。
收益假设：我们所有的目标可以归纳为：最大化智能体所接受到的标量信号（收益）累积和的概率期望值。
3.3 Returns and Episodes（回报和分幕）
定义时刻t后接受的收益序列表示为：
R
t
+
1
,
R
t
+
2
,
R
t
+
2
,
.
.
.
.
.
R_{t+1},R_{t+2},R_{t+2},.....
Rt+1,Rt+2,Rt+2,.....
期望回报
G
t
G_t
Gt:
- 最简单情况：
G
t
=
R
t
+
1
+
R
t
+
2
+
R
t
+
3
+
⋯
+
R
T
G_t=R_{t+1}+R_{t+2}+R_{t+3}+\cdots+R_T
Gt=Rt+1+Rt+2+Rt+3+⋯+RT
若T为最终时刻且有限（ T ≠ ∞ T\neq\infty T=∞），由最终时刻划分交互过程为多个episode（幕），可以类比多局游戏中的每一局。这种就称为episodic tasks-分幕式任务 - 另外一种情况-最终时刻
T
=
∞
T=\infty
T=∞，则称为continuing tasks-持续性任务。这样我们试图最大化的回报也容易趋于无穷。此时我们引入折扣因子
γ
\gamma
γ，即对未来的收益打一个折扣，更看重当前的收益：
G
t
=
R
t
+
1
+
γ
R
t
+
2
+
γ
2
R
t
+
3
+
⋯
=
∑
k
=
0
∞
γ
k
R
t
+
k
+
1
,
γ
∈
[
0
,
1
]
G
t
=
R
t
+
1
+
γ
G
t
+
1
G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1},\gamma \in[0,1]\\ G_t=R_{t+1}+\gamma G_{t+1}
Gt=Rt+1+γRt+2+γ2Rt+3+⋯=k=0∑∞γkRt+k+1,γ∈[0,1]Gt=Rt+1+γGt+1
可以看到，如果 γ < 1 \gamma <1 γ<1,只要收益序列 { R k } \{R_k\} {Rk}是有界的， G t G_t Gt就是一个有限值。
3.4 Unified Notation for Episodic and Continuing Tasks （分幕式和持续性任务的统一表示法）
把幕episode的终止当做一个特殊的absorbing state -吸收态的入口——只会转移到自己并且只产生零收益。如下图所示。
这样在每一幕中T也可以取
∞
\infty
∞,
G
t
G_t
Gt就可以统一的被定义为
G
t
=
R
t
+
1
+
γ
R
t
+
2
+
γ
2
R
t
+
3
+
⋯
=
∑
k
=
0
∞
γ
k
R
t
+
k
+
1
,
γ
∈
[
0
,
1
]
G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1},\gamma \in[0,1]
Gt=Rt+1+γRt+2+γ2Rt+3+⋯=k=0∑∞γkRt+k+1,γ∈[0,1]
3.5 Policies and Value Functions（策略和价值函数）
价值函数： 状态or(状态+动作)
→
\rightarrow
→状态or (状态+动作)的未来预期的收益（回报的期望值）—‘有多好’。
策略函数
π
(
s
)
\pi(s)
π(s)： 特定的行为方式，与价值函数关联。是状态到动作选择的概率的映射—在某一个状态下有多大概率选择某一个特定动作。即
π
(
a
∣
s
)
\pi(a|s)
π(a∣s)是当
S
t
=
s
S_t=s
St=s时
A
t
=
a
A_t=a
At=a的概率。
定义：
- 状态价值方法 - state-value function： 策略 π \pi π下状态s的价值函数记为 v π ( s ) v_{\pi}(s) vπ(s)–—从状态s出发，按照策略 π \pi π进行决策所获得的回报的概率期望值。在MDP中定义式如下 v π ( s ) ≐ E [ G t ∣ S t = s ] = E π [ ∑ k = 0 ∞ γ k R t + k + 1 ∣ S t = s ] v_{\pi}(s) \doteq \mathbb{E}[G_t | S_t = s] = \mathbb{E}_{\pi} \left [ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s \right ] vπ(s)≐E[Gt∣St=s]=Eπ[k=0∑∞γkRt+k+1∣St=s]
- 行动价值方法 - action-value function : 状态s时采取动作a的所有可能决策序列的期望价值： q π ( s , a ) ≐ E [ G t ∣ S t = s , A t = a ] = E π [ ∑ k = 0 ∞ γ k R t + k + 1 ∣ S t = s , A t = a ] q_{\pi}(s,a) \doteq \mathbb{E}[G_t | S_t = s, A_t = a] = \mathbb{E}_{\pi} \left [ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s, A_t = a \right ] qπ(s,a)≐E[Gt∣St=s,At=a]=Eπ[k=0∑∞γkRt+k+1∣St=s,At=a]
-
迭代状态价值方法 - iterative state-value function:
v π v_{\pi} vπ的贝尔曼方程（左图为回溯图）
q π ( s , a ) q_{\pi}(s,a) qπ(s,a)的贝尔曼方程（右图为回溯图）：
q π ( s , a ) q_{\pi}(s,a) qπ(s,a)与 v π ( s ) v_{\pi}(s) vπ(s)的关系：
3.6 Optimal Policies and Optimal Value Functions（最优策略和最优价值函数）
-
optimal state-value function-最优动作价值函数：
v
∗
(
s
)
≐
m
a
x
π
v
π
(
s
)
,
∀
s
∈
S
v_*(s) \doteq \underset{\pi}{max} \ v_{\pi}(s), \forall s \in \mathcal{S}
v∗(s)≐πmax vπ(s),∀s∈S
其中 v ∗ ( s ) v_*(s) v∗(s)表示最优策略（可能不止一个） - optimal action-value function-最优动作价值函数： q ∗ ( s , a ) ≐ m a x π q π ( s , a ) , ∀ s ∈ S a n d a ∈ A ( s ) q_*(s, a) \doteq \underset{\pi}{max} \ q_{\pi}(s, a), \ \forall s \in \mathcal{S} \ and \ a \in \mathcal{A}(s) q∗(s,a)≐πmax qπ(s,a), ∀s∈S and a∈A(s)
- 用
v
∗
v_*
v∗表示
q
∗
q_*
q∗：
q ∗ ( s , a ) = E [ R t + 1 + γ v ∗ ( S t + 1 ) ∣ S t = s , A t = a ] q_*(s,a) = \mathbb{E}[R_{t+1} + \gamma v_* (S_{t+1}) \ | \ S_t = s, A_t = a] q∗(s,a)=E[Rt+1+γv∗(St+1) ∣ St=s,At=a] -
v
∗
v_*
v∗的贝尔曼方程：
-
q
∗
q_*
q∗的贝尔曼方程：
对于有限MDP，
v
π
v_{\pi}
vπ 的贝尔曼方程有唯一解。
确定
v
∗
v_*
v∗之后，可以通过单步搜索来确定最优动作。局部最优即全局最优。
确定
q
∗
q_*
q∗之后，可以直接根据状态s选取$q_*(s,a)最大的动作a。