UCL-DRL-02-MDP

Markov Process

Introduction to MDPs

马尔可夫决策过程:

  • 环境完全可观测

  • 当前状态能完整的描述这个过程

  • 绝大多数 RL 问题都可以形式化为 MDPs:

    • 优化控制问题

    • 部分可观测问题可转化为 MDPs

    • Bandits(老虎机问题)

multi-armed bandits problems

Markov property

一旦当前状态确定后,所有的历史信息都可以扔掉了。这个状态足够去预测 future.

state transition matrix

状态转移矩阵定义了所有的从某一个状态到另一个状态的概率。所以每一行相加为 1.

Markov chain

马尔可夫链可以看做是 一个 tuple(S, P)

  • S 是有穷的状态的集合

  • P 是状态转移矩阵

$$P_{ss’}=P[S_{t+1}=s’|S_t=s]$$

example:

简单的马尔可夫链,没有 reward, action 等。

Markov reward process

在 Markov chain 基础上增加了 reward function.

return

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

越接近0, 意味着越短视

越接近1, 意味着有远见

Why discount

  • 数值计算方便

  • 避免无限循环

  • 对未来的不确定性

  • 如果reward是经济的,即刻的reward能获得更多的利益相比之后的reward

  • 动物/人更倾向于即刻的奖励

  • 有时候也会使用 undiscounted 马尔可夫奖励过程

value function

因为 future 有很多中不确定性,所以需要采样. sample 得到的 $G_t$ 的期望,也就是 value

$$v(s)=E[G_t|S_t=s]$$

上图中 $v_1$ 应该是 $g_1$.

$$G_1=R_2+\gamma R_3+…+\gamma^{T-2}R_T$$

也就是计算从 t 时刻开始到结束,整个过程可能的奖励值。因为未来可能有很多中情况,所以需要 sample. 印象中,好像 alpha go 就是用的蒙特卡洛模拟。

Bellman Equation for MRPs

动态规划。。

这里容易理解错的一点就是: $R_s$ 实际上就是 $R_{t+1}$, s 表示 v(s) 中的当前状态。

$P_{ss’}$ 是状态转移的概率, 从 s 到 后继状态 s’ 的概率。

所以:

$$\gamma v(S_{t+1}|S_t=s) = \gamma\sum_{s’\in S} P_{ss’}v(s’)$$

转换成矩阵形式:

事实上: 系数矩阵 P 就是 状态转移矩阵,有 n 中状态,那就是 $n\times n$ matrix.

solving bellman problems

直接计算是 $O(n^3)$, 因为 n 个状态,P 的计算就是 $O(n^2)$

对于很复杂的 MRPs,可以采用:

  • dynamic programming

  • monte-carlo evalution

  • temporal-difference learning

Markov Decision Process

想对于 Markov reward process 增加了 decision.

$P_{ss’}^a$ 是状态转移矩阵,但是这里的状态之间的转移概率不再是确定好了的。而是取决于 当前状态,以及当前状态下的 action.

$$P_{ss’}^a=P[S_{t+1=s’}|S_t=s, A_t=a]$$

因此 R reward function:

$$R_s^a=E[R_{t+1}|S_t=s,A_t=a]$$

可以发现,与之前的区别是,state 到 state 之间是通过 action 决定的。比如 第一个 state 下,可以是 study or facebook.

policy

这个决策就是想对于 Markov reward process 多出来的一部分,你需要自己去做决策。只不过在每一个状态下,其决策也是一个 distribution

$$\pi(a|s)=P[A_t=a|S_t=s]$$

事实上 Markov decision process 也可以转换成 Markov reward process, 从状态 s 到 s’ 的概率:

$$P_{s,s’}^{\pi}=\sum_{a\in A}\pi(a|s)P_{ss’}^a$$

value function

value 是当前状态 s 下的 reward $G_t$ 的期望。

Bellman expectation Equation

$v_{\pi}$ 基于 $q_{\pi}$ 的表示

state-value $v_{\pi}$ 是 action-value $q_{\pi}$ 基于 action 的期望。

$$v_{\pi}(s)=\sum_{a\in A}\pi(a|s)q_{\pi}(s, a)\quad \text{(1)}$$

$q_{\pi}$ 基于 $v_{\pi}$ 的表示

action-value:

$$q_{\pi}(s,a)=R_s^a+\gamma\sum_{s’\in S}P_{ss’}^av_{\pi}(s’)\quad \text{(2)}$$

从状态 s 到 s’, 基于 statetransition probability matrix $P_{ss’}^a$.

$v_{\pi}$ 基于 $v_{\pi}$ 的表示

将 (2)带入(1)可得:

$$v_{\pi}(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s’\in S}P_{ss’}^av_{\pi}(s’))\quad \text{(3)}$$

这里得到的是 state-value 的表达式。第二个类和符号是 从状态 s 到 s’ 所有可能的后继状态 s’。第一个类和符号是 状态 s 下所有可能的 action.

这里的类和都是表示期望。

$q_{\pi}$ 基于 $q_{\pi}$ 的表示

将 (1) 带入 (2)可得:

$$q_{\pi}(s,a) = R_s^a+\gamma\sum_{s’\in S}P_{ss’}^a\sum_{a\in A}\pi(a’|s’)q_{\pi}(s’,a’)$$

这里得到的是 action-value 的表达式。第一个类和符号是在 action a 下,所有可能的后继状态 s’ 的类和。i第二个类和符号是 后继状态 s’ 下所有的 action 的类和。

example:

Matrix form

类似于前面 Markov reward process 的表示,但是这里的状态转移矩阵变成了 $P^{\pi}$, reward 变成了 $R^{\pi}$.

个人理解: Markov decision process 与 reward process 的区别在于原本在一个 state s 到下一个 state s’ 的概率是给定了的。但是在 decision process,并不存在这个概率,而是取决于 action,而在当前 state s 下,每一个 action 的概率取决于 policy $\pi$.

optimal value function

optimal policy

Solving the Bellman Optimality Equation

最优 policy 就是找到 $v_{* }(s)$ 和 $q_{* }(s,a)$

推导过程与前面类似,通过 bellman optimally equation 得到:

$$v_*(s)=max_{a}q_*(s,a)$$

$$q_*(s,a)=R_s^a+\gamma\sum_{s’\in S}P_{ss’}^av_*(s’)$$

$$v_*(s)={max}{a}(R_s^a+\gamma\sum{s’\in S}P_{ss’}^av_*(s’))$$

$$q_*(s,a)=R_s^a+\gamma\sum_{s’\in S}P_{ss’}^aq_*(s’,a’)$$

state-value function optimal

action-value function optimal

Extension to MDP

作者

Xie Pan

发布于

2019-01-14

更新于

2021-06-29

许可协议

评论