Reinforcement Learning
Markov Decision Processes (MDP)
马尔科夫决策过程是强化学习的理论基础。不管我们是将强化学习应用于五子棋游戏、星际争霸还是机器人行走，我们都假设背后存在了一个马尔科夫决策过程。只不过有的时候我们知道马尔科夫决策过程所有信息(状态集合，动作集合，转移概率和奖励)，有的时候我们只知道部分信息(状态集合和动作集合)，还有些时候马尔科夫决策过程的信息太大无法全部存储 (比如围棋的状态集合总数为 319×19 )。强化学习算法按照上述不同情况可以分为两种: 基于模型 (Model-based) 和非基于模型 (Model-free)。基于模型的强化学习算法是知道并可以存储所有马尔科夫决策过程信息，非基于模型的强化学习算法则需要自己探索未知的马尔科夫过程。[3]
Reinforcement Learning与 其他的Machine Learning的区别 马尔科夫决策过程(Markov Decision Processes)非监督的：我们通常只得到 reward signal。每次系统的 action 只能得到代表这次行为的好坏的标量，比如是 10 points，但是我们不知道他的最好的值是多少。
延迟性：得到的结果很可能延迟于我们做出决策一段时间，有些糟糕的影响并不完全因为当前的决策错误导致的，可能由于前面某一个步骤造成了一个不可逆的错误。
每个样本 非独立同分布 的：我们得到的决策过程，我们获取的每一次信息都不是独立同分布(i.i.d) 的，他是一个有先后顺序的序列，我们并不是简单的将一堆的训练集放进去就行了。
action 对之后的结果能够产生影响：每一次的 action 都会对 environment 产生影响，从而导致下一次得到完全不同的输入样本。比如，作为一个机器人，这个步骤我们继续前进和向左转，将导致我们接下来收集到完全不一样的数据。
在
MDP中，immediate reward R不是 只取决于 $ s $ ，而是取决于 $ s $ 和 $ a $ ；在MRP中，immediate reward R只取决于 $ s $ 。强化学习的目标：找到能够使得累积回报的期望最大的最优策略 $ \pi $ 。
state value function是指在某个状态下，综合考虑所有可能的 action 后，得到的期望 reward；action value function是指在某个状态下，首先采取 action ，然后遵循策略 $ \pi $ 得到的期望 reward。$$
\begin{align*}
v(s) &= \sum \pi (a|s) \cdot q_{\pi} (s,a) \\
q_{\pi}(s,a) &= \sum P_{ss’}^{a} \cdot [ R_{ss’}^{a} + v_{\pi} (s’) ]
\end{align*}
$$可以认为给定的某个状态 $ s $ 的
action value function的期望就是state value function。
参考
Dynamic Programming
Basis
DP主要解决的是Planning的问题。MDP需要解决的问题有两种：Prediction
已知
MDP的 $ S,A,P,R,\gamma $ 以及 policy，目标是算出在每个状态下收敛的的value function，即处于每个状态下能够获得的期望 reward 是多少。方法：
Iterative Policy Evaluation(针对问题不断迭代计算Bellman Expectation Equation)。Control
已知
MDP的 $ S,A,P,R,\gamma $，但是 policy 未知，因此它的目标不仅是计算出最优的收敛的value function，而且要给出最优的 Policy。方法：
Policy Iteration，Value Iteration
Iterative Policy Evaluation
Policy Evaluation：基于当前的 Policy 计算出每个状态的
value function。计算方法见上方。计算公式如下：
$$
\begin{align*}
V_{k+1}(s) &= \sum_{\alpha \in A} \pi(a|s) \cdot q_{\pi}(s,a) \\
&= \sum_{\alpha \in A} \pi(a|s) \cdot \left( {\cal R}{s}^{a} + \gamma \sum{s’ \in S}{\cal P}{ss’}^{a}V_k(s’)\right) \\
&= \sum{\alpha \in A} \pi(a|s) \cdot \sum_{s’, r} {\cal P}(s’,r|s,a) \left(r + \gamma V_k(s’)\right)
\end{align*}
$$
Policy Improvment
Policy Improvment：基于当前的
value function，采用 贪心算法 来找到当前最优的 Policy。One step look ahead ?
Policy Iteration
Policy Iteration就是在Iterative Policy Evaluation的基础上加入一个选择 policy 的过程，即：Policy Iteration=Policy Evaluation+Policy Improvement。
Value Iteration
另外，
Value Iteration虽然在迭代的过程中没有显式计算出 policy，但是在得到最优的 value function 之后就能推导出最优的 policy，因此也能用做解决control问题。Value Iteration把 求和（求新的 state value 的时候，把所有可能的 action 的得到的 action value 加起来）换成了 取max（求新的 state value 的时候，从所有可能的 action 的得到的 action value 中取 max），可以看两个的算法描述。（这点类似HMM中的前向算法和维特比算法的区别）。
Policy Iteration vs Value Iteration
相同
- 两者计算的都是
state value： $ v(s), \forall s \in S $ 。
- 两者计算的都是
不同
Policy Iteration计算的是给定的状态下的所有可能 action 的 期望（所以对不同的 $ q(s,a) $ 求加权和，权重就是此状态下采取这个 action 的概率）。Value Iteration计算的是给定的状态下的所有可能 action 的 最大值。（两者的关系类似HMM中的 “前向算法” 和 “维特比算法” 的关系）。Value Iteration在更新 $ v(s) $ 的时候不会用到 policy。Policy Iteration中每得到一个收敛的 $ v(s) $ ，就会通过one step lookahead的方法进行一次Policy Improvement。Value Iteration是在得到 最终 收敛的 $ v(s) $ 之后，只通过一次one step lookahead的方法即可得到最优的 policy。(参考那个 github 的 jupyter notebook)
参考
参考
Model-Free Prediction / Control
Prediction 就是计算 state values （也就是 $ V(s) $ )。
Control 就是计算 action values (the values of state-action pairs) （也就是 $ Q(s,a) $ )。
1. 蒙特卡洛方法
1.1 Prediction
蒙特卡罗方法是利用经验平均来估计值函数。无模型的方法充分评估策略值函数的前提是每个状态都能被访问到。因此，在蒙特卡洛方法中必须采用一定的方法保证每个状态都能被访问到。其中一种方法是探索性初始化。
无偏估计，方差大
第一次访问蒙特卡罗方法
$$
v(s) = \frac{G_{11}(s) + G_{21}(s) + \cdots } {N(s)}
$$每次访问蒙特卡罗方法
$$
v(s) = \frac{G_{11}(s) + G_{12}(s) + \cdots + G_{21}(s) + \cdots } {N(s)}
$$递增的计算经验平均的方法：
$$
\begin{align*}
v_{k}(s) & = \frac{1}{k} \sum_{i=1}^{k} G_i(s) = \frac{1}{k} \left(G_{k}(s) + \sum_{i=1}^{k-1} G_i(s) \right) \\
& = \frac{1}{k} \left(G_k(s) + (k-1) v_{k-1}(s) \right) \\
& = v_{k-1}(s) + \frac{1}{k} \left(G_k(s) - v_{k-1}(s) \right)
\end{align*}
$$
1.2 Control
On-Policy Monte-Carlo由policy evaluation + ϵ−Greedy Policy Improvement组成。
1.3 参考
【David Silver强化学习公开课之四】Model-Free Learning(解决未知Environment下的Prediction问题) | 听见下雨的声音
【David Silver强化学习公开课之五】Model-Free Control(解决未知Environment下的Control问题) | 听见下雨的声音
2. 时间差分方法
2.1 Related concept
相比于动态规划的方法，蒙特卡罗的方法需要等到每次试验结束，所以学习速度慢，学习效率不高。从两者的比较我们很自然地会想，能不能借鉴动态规划中 boot’strapping 的方法，在不等到试验结束时就估计当前的值函数呢？于是就出现了时间差分法。
TD 算法的 value function 更新公式。
$$
V(S_t) = V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))
$$
其中 $ R_{t+1}+\gamma V(S_{t+1}) $ 称为 TD target， $ \delta_t = R_{t+1}+\gamma V(S_{t+1})-V(S_t) $ 称为 TD error 。
2.1 SARSA
- On policy TD Control
2.2 Q-Learning
- Off policy TD Control
2.3 参考
参考
Value Function Approximation
Basics
基于动态规划的方法，基于蒙特卡罗的方法和基于时间差分的方法。这些方法有一个基本的前提条件，那就是状态空间和动作空间是离散的，而且状态空间和动作空间不能太大。
注意，这时的值函数其实是一个表格。对于状态值函数，其索引是状态；对于行为值函数，其索引是状态-行为对。值函数迭代更新的过程实际上就是对这张表进行迭代更新。因此，之前讲的强化学习算法又称为表格型强化学习。
若状态空间的维数很大，或者状态空间为连续空间，此时值函数无法用一张表格来表示。这时，我们需要利用函数逼近的方法对值函数进行表示。
传统的表格方法的弊端
状态空间非常大的时候
状态空间为连续空间的时候
MC 中，target 是 $ G_t $ ； TD(0) 中，target 是 $ R_t+\gamma V’(S_{t+1},w) $ ； TD(λ) 中，target 是 $ G_t^\lambda $ 。
而且因为它的 target 值也不是 $ v_{\pi}(S_t) $ 的无偏估计，因此 TD(0) 方法的梯度下降版本中也就不能保证收敛。
DQN
参考
Policy Gradient
REINFORCE
SCST
cd
在 time step t ，生成了一个 vocabulary size 大小的向量，向量中的每个元素表示每个 word 是 target 输出的概率，这里就把这个概率当做是 take action 的概率。
tf.multinomial就会根据这个概率进行采样，概率越大，越容易被采样到。这样就把
每个时刻 word 的生成转换成了每个时刻的 take action，就可以当做是 RL 来做了。在每个时刻，根据概率的大小，来决定下一个时刻生成的单词（也就是：根据概率的大小，来决定下一个时刻 take 哪个 action，概率越大，对应的那个 action 就越容易被 take。因为policy 的定义就是：在某个状态下采取 action 的概率）。
更新模型的参数，就会改变每个时刻、生成某个 word 的概率（也就是改变采取某个 action 的概率），这就是直接对 policy 进行建模，也就是
Policy Gradient。这时候 reward 的作用是：根据reward，手动的改变梯度的 大小 和 方向（作用类似 ground truth）。reward 大就增加它的梯度（改变梯度方向，使得 take 这个 action 的概率变大），否则就降低它的梯度（改变梯度方向，使得 take 这个 action 的概率变小）。
从中也可以看出，在每一个 time step 采取 action 后，并不知道这个 action 的好坏，而是在最后通过计算 BLEU 之后才知道（BLEU 越高，这次采取的
action 序列越好，但是并不能说某一个单独的 action 好）。
VFA vs PG
相同点：
- 都可以通过神经网络来进行建模。
不同点：
VFA是回归问题，target 就是 reward（MC中是，TD中是TD-target。）PG是分类问题，只不过这里最看重的是最终输出的概率（传统的分类问题中，输出概率后，要计算 argmax，这里不用）。也就是说：输出的概率就是 take 各个 action 的概率，这时候 reward 的作用是：根据reward，手动的改变梯度的 大小 和 方向（作用类似 ground truth）。reward 大就增加它的梯度（改变梯度方向，使得 take 这个 action 的概率变大），否则就降低它的梯度（改变梯度方向，使得 take 这个 action 的概率变小）。