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