David silver 强化学习 Lecture 2

课程主页: http://web.stanford.edu/class/cs234/index.html

这里回顾David silver 强化学习 Lecture2 的课程内容,这一讲简单介绍了马尔可夫决策过程。

马尔可夫过程

马尔可夫性

定义

状态$S_t$有马尔可夫性当且仅当

  • 状态从历史中捕获所有相关信息
  • 一旦知道状态后,历史可以被丢弃
  • 状态是未来的充分统计量
状态转移矩阵

对于马尔可夫状态$s$和后继状态$s’$,状态转移概率被定义为

状态转移矩阵$\mathcal P$定义了从所有状态$s$到后继状态$s’$的概率,

不难看出该矩阵每行的和为$1$。

马尔可夫过程

马尔可夫过程是无记忆的随机过程,即一系列具有马尔可夫性的随机状态$\mathcal S_1,\mathcal S_2,\ldots$。

定义

马尔可夫过程(马尔可夫链)是元组$\langle\mathcal{S}, \mathcal{P}\rangle$

  • $\mathcal S$是(有限)状态集合

  • $\mathcal P$是状态转移概率矩阵:

一个具体例子如下:

马尔可夫奖励过程

定义

马尔可夫奖励过程是元组$\langle\mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma\rangle$

  • $\mathcal S$是(有限)状态集合

  • $\mathcal P$是状态转移概率矩阵:

  • $\mathcal R$是奖励函数,$\mathcal{R}_{s}=\mathbb{E}\left[R_{t+1} | S_{t}=s\right]$

  • $\gamma$是折扣因子,$\gamma \in[0,1]$

一个具体例子如下:

Return

定义

return $G_t$是从时间$t$开始的总折扣奖励:

为什么需要折扣因子

大多数马尔可夫奖励和决策过程都有折扣因子。 为什么?

  • 数学上方便处理折扣奖励
  • 避免循环马尔可夫过程中的无限回报
  • 关于未来的不确定性可能无法完全体现
  • 如果奖励是经济奖励,则即时奖励可能比延迟奖励赚取更多的利息
  • 动物/人类行为显示出对即时奖励的偏好
  • 有时可能会使用未折扣的马尔可夫奖励过程(即$\gamma =1$)
价值函数

价值函数$v(s)$给出状态$s$的长期价值

定义

MRP的状态价值函数$v(s)$是从状态$s$出发的return期望

贝尔曼方程

由价值函数的定义,不难得到

上述等式表示价值函数可以被分解为两部分:

  • 即时奖励$R_{t+1}$
  • 后继状态的折扣奖励$\gamma v\left(S_{t+1}\right)$

利用状态转移矩阵,不难将上述方程改写为

上述方程组被称为贝尔曼方程。

矩阵形式的贝尔曼方程

利用矩阵符号,很容易将贝尔曼方程改写为矩阵形式:

马尔可夫决策过程

马尔可夫决策过程(MDP)是具有决策的马尔可夫奖励过程,环境中的所有状态都具有马尔可夫性。

定义

马尔可夫决策过程是元组$\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$

  • $\mathcal S$是(有限)状态集合

  • $\mathcal A$是有限动作集合

  • $\mathcal P$是状态转移概率矩阵:

  • $\mathcal R$是奖励函数,$\mathcal{R}_{s}^a=\mathbb{E}\left[R_{t+1} | S_{t}=s,A_t =a\right]$

  • $\gamma$是折扣因子,$y \in[0,1]$

策略

定义

策略$\pi$是动作关于状态的条件分布:

  • 策略完全定义了智能体的行动

  • MDP策略依赖于当前状态(不是历史)

  • 给定MDP $\mathcal{M}=\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$以及策略$\pi$

  • 状态序列$ S_1, S_2\ldots$是马尔可夫过程$\left\langle\mathcal{S}, \mathcal{P}^{\pi}\right\rangle$

  • 状态和奖励序列$S_{1}, R_{2}, S_{2}, \ldots$是马尔可夫奖励过程$\left\langle\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma\right\rangle$

  • 其中

价值函数

定义

MDP的状态价值函数$v_\pi(s)$是从状态$s$出发,按照策略$\pi $的期望return:

定义

动作价值函数$q_{\pi}(s, a)$是从状态$s$出发,采取动作$a$,然后按照策略$\pi $的期望return:

贝尔曼方程

类似前一部分,不难得到状态价值函数以及动作价值函数的贝尔曼方程:

另一方面,利用两者的关系,我们有:

将上述等式再次代入可以得到新的等式:

贝尔曼方程的矩阵形式

回顾方程

将其表示为矩阵形式可得

直接求解得到

最优价值函数

定义

最优状态价值函数$v_\star (s)$是关于所有策略的最大值

最优动作价值函数$q_\star(s, a)$是动作-价值函数关于所有策略的最大值

  • 最优价值函数指定了MDP中可能的最佳性能。
  • 当我们知道最优值$f_n$时,可以说MDP“已解决”。
最优策略

在策略上定义偏序

定理

对于任意马尔可夫决策过程

  • 存在不比其他策略差的最优策略$\pi_\star$,即$\pi_{*} \geq \pi, \forall \pi$
  • 所有最优策略达到最优价值函数,$v_{\pi_{}}(s)=v_{}(s)$
  • 所有最优策略达到最优动作价值函数,$q_{\pi_{}}(s, a)=q_{}(s, a)$
找到最优策略

最优策略可以通过最大化$q_{*}(s, a)$来求解,

  • 任何MDP始终都有确定性的最佳策略
  • 如果我们知道$q_{\star}(s, a)$,我们将立即获得最优策略
$v_\star,q_\star$的贝尔曼方程

最优价值函数通过Bellman最佳方程递归相关:

求解贝尔曼最优方程
  • 贝尔曼最优方程是非线性的
  • 没有封闭解(通常)
  • 许多迭代求解方法
    • 价值迭代
    • 策略迭代
    • Q-learning
    • Sarsa

MDP的拓展

  • 无限和连续的MDP
  • 部分可观察的MDP
  • 未折现的,平均奖励MDP

本文标题:David silver 强化学习 Lecture 2

文章作者:Doraemonzzz

发布时间:2019年11月20日 - 14:20:00

最后更新:2019年11月20日 - 14:37:16

原始链接:http://doraemonzzz.com/2019/11/20/David silver 强化学习 Lecture 2/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。