RL-Ch3-基于表格方法求解RL
本文不太完善，待寻到时间再细细修改。
前情回顾
MDP为(S,A,P,R,$\gamma$)五元组，在上一状态$s_t$采取动作$a_t$，会以一定的概率分布p进入下一状态$s_{t+1}$，同时产生一定的收益$r_t$。
与环境交互过程会学习到P(transimision Probability matrix)函数$p(s_{t+1},r_t|s_t,a_t)$和R(Reward)函数$r(s_t,a_t)$，以此作为环境的描述。若事先通过虚拟环境获知了P和R函数，再应用于现实进行决策，则称这个系统是Model-Based的，反之则称该系统是Model-Free的。
- Model-Based：P/R函数已知（图1中的黑色主体图+红色部分）
- Model-Free：P/R函数未知（图1中的黑色主体图+绿色部分）
Q(Action-value)-table
在不同的状态采取不一样的行动会产生不一样的效果，而Q-func就是用于度量这种效果，由此也产生了Q-table的说法。
有限步Markov Chain的当前Q(动作状态)值为
$$
G_t=R_1+…+R_T
$$
无限步Markov Chain的当前Q(动作状态)值为
$$
\begin{align} G_t=R_{t+1}+\gamma R_{t+2}+…=\sum_{k=0}^\inf\gamma R_{t+k+1}=R_{t+1}+\gamma\sum_{k=0}^\inf\gamma^kR_{t+k+2}=R_{t+1}+\gamma G_{t+1}\end{align}
$$
以Cliff Walker这一经典游戏为例，讲解如何对实际情况建立Q表格。将地点划分为网格区域，每个方格有一个坐标位置，以左上角为原点，建立x、y轴正方向，则可得到一系列坐标，即状态state。上下左右为可采取的动作action。通过全部取零的操作完成Q表的初始化。然后通过一系列新算法进行后续Q表的更新。
时序差分学习（单步更新）
时许差分学习(Time Difference Learning)就是用下一时间步的V/Q值去近似当前时间步的V/Q值，不断迭代，得到最终的Q表。可分为在线策略(on-policy)和离线策略(off-policy)两类。
On Policy
图片来源CSDN
使用策略$\pi$学习，并与环境进行交互产生经验，因为需要兼顾探索，所以$\pi$并不稳定。典型的算法是Sarsa。
目标：用$Q(s_t,a_t)$逼近$G_t$
更新公式：
$$
q(s_t,a_t)<–q(s_t,a_t)+\alpha[R_{t+1}+\gamma q(s_{t+1},a_{t+1})-q(s_t,a_t)]
$$
$R_{t+1}+\gamma Q(s_{t+1},a_{t+1})$为$G_t$的真值
$Q(s_t,a_t)$为$G_t$的待更新值
式子中涉及的参数$(s_t,a_t,R_{t+1},s_{t+1},a_{t+1})$，故称此为Sarsa算法。
算法示意图：
Sarsa的伪代码
代码实操见RL-Code-Sarsa
Off Policy
典型的算法是Q-Learning。
目标策略：$\pi$–>用于学习最优策略
行为策略：$\mu$–>探索，与环境交互产生经验轨迹
Q-Learning伪代码
Q-Learning更新公式：
$$
q(s_t,a_t)<–q(s_t,a_t)+\alpha[r_{t+1}+\gamma \max_aq(s_{t+1},a)-q(s_t,a_t)]
$$
代码实操见RL-Code-QLearning