前言

我在学习Playing Atari with Deep Reinforcement Learning这篇论文时，文章中引用到了马尔可夫决策过程的相关概念，为此特意学习了马尔可夫决策过程的相关知识。

马尔可夫过程(MP)的基本概念

状态遵循马尔可夫是指

P[S

t+1

|S

t

]=P[S

t+1

|S

t

,⋯,S

1

]

P[St+1|St]=P[St+1|St,⋯,S1]

既未来与过去无关只与现在有关

⟨S,P⟩

⟨S,P⟩是马尔可夫过程是指S为有限状态集合并且遵循马尔可夫，P是状态转移概率矩阵P

s,s

′

=P[S

t+1

=s

′

|S

t

=s]

Ps,s′=P[St+1=s′|St=s]

马尔可夫奖赏过程(MRP)的基本概念

⟨S,P,R,γ⟩

⟨S,P,R,γ⟩是马尔可夫奖赏过程是指S为有限状态集合，P为状态转移矩阵, R：S⟶R

R：S⟶R为奖赏函数R

s

=E[R

t+1

|S

t

=s]

Rs=E[Rt+1|St=s]，γ

γ是折扣率

MRP的价值函数

R

t

Rt定义为从状态s

t−1

st−1到达状态s

t

st所得到的奖励，那么时刻0所能得到的回报可以写为

G

=R

1

+γR

2

+γ

2

R

3

+⋯

G0=R1+γR2+γ2R3+⋯

t时刻在某一状态下的回报可以如下式子表示：

G

t

=R

t+1

+γR

t+2

+γ

2

R

t+3

+⋯

Gt=Rt+1+γRt+2+γ2Rt+3+⋯

因为从某一状态到达另一个状态是根据一定的概率，所以真实的G

t

Gt的可能有很多种，所以定义在某一状态下的价值函数

v(s)=E[G

t

|S

t

=s]

v(s)=E[Gt|St=s]

其中S

t

St表示在t时刻的状态Bellman方程

v(s)

=E[G

t

|S

t

=s]

=E[R

t+1

+γR

t+2

+γ

2

R

t+3

+⋯|S

t

=s]

=E[R

t+1

+γ(R

t+2

+γR

t+3

+⋯)|S

t

=s]

=E[R

t+1

+γv(S

t+1

)|S

t

=s]

=R

s

+γ∑

s

′

∈S

P

s,s

′

v(s

′

)

v(s)=E[Gt|St=s]=E[Rt+1+γRt+2+γ2Rt+3+⋯|St=s]=E[Rt+1+γ(Rt+2+γRt+3+⋯)|St=s]=E[Rt+1+γv(St+1)|St=s]=Rs+γ∑s′∈SPs,s′v(s′)

这个公式就是Bellman方程的基本形态，得到线性方程组

v=R+γPv

v=R+γPv

可以求得每个状态的价值。

马尔可夫决策过程(MDP)的基本概念

马尔可夫决策过程由五个关键元素{S,A,P,R,γ}

{S,A,P,R,γ}组成

S

S代表状态集合

A

A代表动作集合

P

P是三维概率矩阵

P

a

s,s

′

=P[S

t+1

=s

′

|A

t

=a,S

t

=s]

Ps,s′a=P[St+1=s′|At=a,St=s]

R

R是回报函数，R:S×A→R

R:S×A→R，有时R

R与A

A无关，R:S→R

R:S→RR

a

s

=E[R

t+1

|A

t

=a,S

t

=s]

Rsa=E[Rt+1|At=a,St=s]

γ

γ表示学习随着时间推移的折扣率

这里有确定的概率矩阵，所以也就给出了状态转移的模型，所以这里的MDP是基于模型的（Model-based），很多时候概率是不确定的，这就是不基于模型的（Model-free）

马尔可夫决策过程如下

s

−

→

a

s

1

−

→

a

1

s

2

−

→

a

2

⋯

s0→a0s1→a1s2→a2⋯

状态s

s0在动作a

a0作用下根据概率分布P

s

a

Ps0a0到s

1

s1，然后执行动作a

1

⋯

a1⋯，得到的回报如下

R(s

,a

)+γR(s

1

,a

1

)+γ

2

R(s

2

,a

2

)+⋯

R(s0,a0)+γR(s1,a1)+γ2R(s2,a2)+⋯

为了方便解释，把r

t

rt定义为从状态s

t−1

st−1执行行为a

t−1

at−1根据一定概率到达状态s

t

st所得到的奖励策略

π(a|s)=P[A

t

=a|S

t

=s]

π(a|s)=P[At=a|St=s]

策略是指在各个特定的状态下执行不同动作的概率分布

给定一个MDPM=⟨S,A,P,R,γ⟩

M=⟨S,A,P,R,γ⟩和一个策略π

π，那么⟨S,P

π

⟩

⟨S,Pπ⟩是一个MP，⟨S,P

π

,R

π

,γ⟩

⟨S,Pπ,Rπ,γ⟩是一个MRP，其中

P

π

s,s

′

=∑

a∈A

π(a|s)P

a

s,s

′

R

π

s

=∑

a∈A

π(a|s)R

a

s

Ps,s′π=∑a∈Aπ(a|s)Ps,s′aRsπ=∑a∈Aπ(a|s)Rsa

MDP的价值函数

给定一个MDPM=⟨S,A,P,R,γ⟩

M=⟨S,A,P,R,γ⟩和一个策略π

π，因为⟨S,P

π

,R

π

,γ⟩

⟨S,Pπ,Rπ,γ⟩是一个MRP，所以可以求出这个MRP的价值函数

v

π

(s)

=E

π

[G

t

|S

t

=s]

=E

π

[R

t+1

+γv

π

(S

t+1

)|S

t

=s]

vπ(s)=Eπ[Gt|St=s]=Eπ[Rt+1+γvπ(St+1)|St=s]

动作价值函数

考虑某个状态下不同动作的价值

q

π

(s,a)

=E

π

[r

t+1

+γr

t+2

+γ

2

r

t+3

+⋯|A

t

=a,S

t

=s]

=E

π

[G

t

|A

t

=a,S

t

=s]

=E

π

[R

t+1

+γq

π

(S

t+1

,A

t+1

)|A

t

=a,S

t

=s]

qπ(s,a)=Eπ[rt+1+γrt+2+γ2rt+3+⋯|At=a,St=s]=Eπ[Gt|At=a,St=s]=Eπ[Rt+1+γqπ(St+1,At+1)|At=a,St=s]

价值函数和动作价值函数的关系

∵

∴

v

π

(s)=∑

a∈A

π(a|s)q

π

(s,a)

q

π

(s,a)=R

a

s

+γ∑

s

′

∈S

P

a

s,s

′

v

π

(s

′

)

v

π

(s)=∑

a∈A

π(a|s)(R

a

s

+γ∑

s

′

∈S

P

a

s,s

′

v

π

(s

′

))

v

π

=R

π

+γP

π

v

π

v

π

=(1−γP

π

)R

π

∵ vπ(s)=∑a∈Aπ(a|s)qπ(s,a)qπ(s,a)=Rsa+γ∑s′∈SPs,s′avπ(s′)∴ vπ(s)=∑a∈Aπ(a|s)(Rsa+γ∑s′∈SPs,s′avπ(s′))vπ=Rπ+γPπvπvπ=(1−γPπ)Rπ

所以在给定的策略下可以求出价值函数和动作价值函数最优价值函数和最优动作价值函数

定义最优价值函数v

∗

:S⟶R

v∗:S⟶R

v

∗

(s)=max

π

v

π

(s)

v∗(s)=maxπvπ(s)

定义最优动作价值函数q

∗

:S⟶R

q∗:S⟶R

q

∗

(s,a)=max

π

q

π

(s,a)

q∗(s,a)=maxπqπ(s,a)

策略的偏序关系

π

′

≥π⟺v

π

′

(s)≥v

π

(s),∀s∈S

π′≥π⟺vπ′(s)≥vπ(s),∀s∈S

定理

对于任意一个MDP

• 存在一个最优策略π
• ∗
• 使得对于∀π，π
• ∗
• ≥π
• π∗使得对于∀π，π∗≥π
• 所有的最优策略对应的价值函数就是最优价值函数v
• π
• ∗
• (s)=v
• ∗
• (s)
• vπ∗(s)=v∗(s)
• 所有的最优策略对应的动作价值函数就是最优动作价值函数q
• π
• ∗
• (s,a)=q
• ∗
• (s,a)
• qπ∗(s,a)=q∗(s,a)

根据这个定理，可以得到Bellman最优方程

v

∗

(s)=max

a

q

∗

(s,a)

q

∗

(s,a)=R

a

s

+γ∑

s

′

∈S

P

a

s,s

′

v

∗

(s

′

)

v∗(s)=maxaq∗(s,a)q∗(s,a)=Rsa+γ∑s′∈SPs,s′av∗(s′)

策略迭代(Policy Iteration)

Policy Iteration的目的是通过迭代计算value function 价值函数的方式来使policy收敛到最优。

Policy Iteration本质上就是直接使用Bellman方程而得到的：

v

k+1

(s)

=E

π

[R

t+1

+γv

k

(S

t+1

)|S

t

=s]

=∑

a∈A

π(a|s)(R

a

s

+γ∑

s

′

∈S

P

a

s,s

′

v

k

(s

′

))

vk+1(s)=Eπ[Rt+1+γvk(St+1)|St=s]=∑a∈Aπ(a|s)(Rsa+γ∑s′∈SPs,s′avk(s′))

Policy Iteration一般分为两步:

1. 策略评估 Policy Evaluation： 更新v

π

vπ

2. 策略改进 Policy Improvement： π

′

=greedy(v

π

)

π′=greedy(vπ)

直至收敛到π

∗

π∗考虑一个决定性的策略，a=π(s)既π(a|s)=1

a=π(s)既π(a|s)=1可以通过贪婪的方法改进策略

π

′

(s)=

q

π

(s,π

′

(s))=

≥

∴v

π

(s)≤q

π

(s,π

′

(s))=

≤

≤

≤

=

argmax

a∈A

q

π

(s,a)

max

a∈A

q

π

(s,a)

q

π

(s,π(s))=v

π

(s)

E

π

′

[R

t+1

+γv

π

(S

t+1

)|S

t

=s]

E

π

′

[R

t+1

+γq

π

(S

t+1

,π

′

(S

t+1

))|S

t

=s]

E

π

′

[R

t+1

+γR

t+2

+γ

2

q

π

(S

t+2

,π

′

(S

t+2

))|S

t

=s]

⋯≤E

π

′

[R

t+1

+γR

t+2

+γ

2

R

t+3

+⋯|S

t

=s]

v

π

′

(s)

π′(s)=argmaxa∈Aqπ(s,a)qπ(s,π′(s))=maxa∈Aqπ(s,a)≥qπ(s,π(s))=vπ(s)∴vπ(s)≤qπ(s,π′(s))=Eπ′[Rt+1+γvπ(St+1)|St=s]≤Eπ′[Rt+1+γqπ(St+1,π′(St+1))|St=s]≤Eπ′[Rt+1+γRt+2+γ2qπ(St+2,π′(St+2))|St=s]≤⋯≤Eπ′[Rt+1+γRt+2+γ2Rt+3+⋯|St=s]=vπ′(s)

如果改进结束，那么

v

π

(s)=q

π

(s,π

′

(s))=max

a∈A

q

π

(s,a)

vπ(s)=qπ(s,π′(s))=maxa∈Aqπ(s,a)

满足Bellman最优方程，因此

v

π

(s)=v

∗

(s) ∀s∈S

vπ(s)=v∗(s) ∀s∈S

得多了最优策略π

∗

π∗

值迭代(Value Iteration)

根据Bellman最优方程，得到

v

∗

(s)=max

a∈A

(R

a

s

+γ∑

s

′

∈S

P

a

s,s

′

v

∗

(s

′

))

v∗(s)=maxa∈A(Rsa+γ∑s′∈SPs,s′av∗(s′))

有以下迭代公式

v

k+1

(s)=max

a∈A

(R

a

s

+γ∑

s

′

∈S

P

a

s,s

′

v

k

(s

′

))

v

k+1

=max

a∈A

(R

a

+γP

a

v

k

)

v

1

→v

2

→v

3

→⋯→v

∗

π

∗

(s)=argmax

a∈A

(R

a

s

+γ∑

s

′

∈S

P

a

s,s

′

v

∗

(s

′

))

vk+1(s)=maxa∈A(Rsa+γ∑s′∈SPs,s′avk(s′))vk+1=maxa∈A(Ra+γPavk)v1→v2→v3→⋯→v∗π∗(s)=argmaxa∈A(Rsa+γ∑s′∈SPs,s′av∗(s′))