UCL-DRL-02-MDP
Markov Process
Introduction to MDPs
马尔可夫决策过程：
环境完全可观测
当前状态能完整的描述这个过程
绝大多数 RL 问题都可以形式化为 MDPs:
优化控制问题
部分可观测问题可转化为 MDPs
Bandits（老虎机问题）
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
UCL-DRL-02-MDP