David silver 的 reinforcement learning 课程笔记（二）：马尔科夫决策过程

2019-11-06 09:09:56

字体：大中小

来源：转载

供稿：网友

最近在学增强学习，边看课程视频编写的总结。希望和大家一起讨论学习…

Markov PRocess

状态 s $s$ 是马尔科夫的但且仅当: P(S(t+1)|St）=P(St+1|S1,...,St) $P(S_{(t+1)}|S_t）=P(S_{t+1}|S_1,...,S_t)$ 一个马尔科夫过程可以用一个二元组(S,P) $(S,P)$ 定义，其中S为有限的状态的集合，P为转移矩阵。对于一个马尔科夫过程一个样本(sample)为一个随机采样的序列(sequence)。

Markov Reward Process

没有价值的判断就无法生成有效的策略。因此，引入了reward这样一个概念。一个markov reward process 是一个四元组(S,P,R,γ $S,P,R,/gamma$ )，其中R $R$ 为reward function，定义为 Rs=E(Rt+1|St=s) $R_s=E(R_{t+1}|S_t=s)$

γ $/gamma$ 为折扣系数,此处的reward可以理解为离开当前状态得到的奖赏。而我们所关心的是一个样本（sequence）在某个时刻所带来的回报，即累计奖赏（accumulated reward）return。 Gt=Rt+1+γRt+2+...=∑k=0∞γkRt+k+1 $G_t=R_{t+1}+/gamma R_{t+2}+...=/sum_{k=0}^{/infty}/gamma^kR_{t+k+1}$

这里引入折扣的原因一是因为未来的不确定性且为了避免无穷大的return。而对于金融领域，立即的奖赏明显比延后的奖赏更加诱人。 State value function 评分函数 v(s) $v(s)$ 表示从当前状态s $s$ 出发能够得到的奖赏的期望，描述的是状态v(s) $v(s)$ 的长期价值。 v(s)=E(Gt|St=s) $v(s)=E(G_t|S_t=s)$

Bellman Equation

将Gt $G_t$ 带入可得 v(s)=E(Rt+1+γv(St+1)|St=s)=Rs+γ∑s,∈SPss,v(s,) $v(s)=E(R_{t+1}+/gamma v(S_t+1)|S_t=s)// =R_s+/gamma/sum_{s^,/in S}P_{ss^,}v(s^,)$ 即可得到bellman 方程 v=R+γPv $v=R+/gamma Pv$ 其中v,R $v,R$ 为列向量，P $P$ 为转移概率矩阵。其计算开销巨大O(n3) $O(n^3)$ 。迭代求取的方法有：动态规划，时序差分学习，蒙特卡洛评价等方式

Markov Dicision Process

一个马尔科夫决策过程可有一个5元组(S,A,P,R,γ) $(S,A,P,R,/gamma)$ 描述其中A $A$ 为动作action的集合，P $P$ 则被定义为 Pass,=P(St+1=s,|St=s,At=a) $P^{a}_{ss^,}=P(S_{t+1}=s^,|S_t=s,A_t=a)$ 即状态s $s$ 经动作a $a$ 转移到状态s, $s^,$ 的概率 R $R$ 的定义类似于此前，Ras=E(Rt+1|St=s,At=a) $R^a_s=E(R_{t+1}|S_t=s,A_t=a)$

policy

一个策略π $/pi$ 指的是对于一个状态对应的可能执行的动作的分布 π(a|s)=P(At=a|St=s) $/pi(a|s)=P(A_t=a|S_t=s)$ 且其不随时间的改变而改变有了策略后，可以根据value state function 定义 action value function。 qπ=Eπ(Gt|St=s,At=a)=Eπ(Rt+1+γqπ(St+1,At+1)|St=s,At=a) $q_/pi=E_/pi(G_t|S_t=s,A_t=a)// =E_/pi(R_{t+1}+/gamma q_/pi(S_{t+1},A_{t+1})|S_t=s,A_t=a)$ 同时可得以下方程 vπ(s)=∑a∈Aπ(a|s)qπ(s,a) $v_/pi(s)=/sum_{a /in A}/pi(a|s)q_/pi(s,a)$ qπ(s,a)=Ras+γ∑s,∈SPass,vπ(s,) $q_/pi(s,a)=R^a_s+/gamma /sum_{s^, /in S}P^a_{ss^,}v_/pi(s^,)$

Optimal Value Function

v∗(s)=maxπvπ(s) $v_*(s)=max_/pi v_/pi(s)$ q∗(s,a)=maxπqπ(s,a) $q_*(s,a)=max_/pi q_/pi(s,a)$ 一个最优策略可以由q∗(s,a) $q_*(s,a)$ 得到： π∗(s,a)={10a=argmaxa∈Aq∗(s,a)otherwise $/pi_*(s,a)=/begin{cases}1&a=argmax_{a/in A}q_*(s,a)//0&otherwise/end{cases}$