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
