从零开始强化学习（三）——表格型方法

三. 表格型方法(Tabular Methods)

强化学习的三个重要的要素：状态、动作和奖励。强化学习智能体跟环境是一步一步交互的，就是先观察一下状态，然后再输入动作。再观察一下状态，再输出动作，拿到这些reward。它是一个跟时间相关的序列决策的问题

这样的一个状态转移概率是具有马尔可夫性质的(系统下一时刻的状态仅由当前时刻的状态决定，不依赖于以往任何状态)。因为这个状态转移概率，它是下一时刻的状态是取决于当前的状态，它和之前的 $s_{t-1}$ 和 $s_{t-2}$ 都没有什么关系。然后再加上这个过程也取决于智能体跟环境交互的这个 $a_t$ ，所以有一个决策的一个过程在里面，就称这样的一个过程为马尔可夫决策过程(Markov Decision Process,MDP)

MDP就是序列决策这样一个经典的表达方式。MDP也是强化学习里面一个非常基本的学习框架。状态、动作、状态转移概率和奖励 $(S,A,P,R)$ ，这四个合集就构成了强化学习MDP的四元组，后面也可能会再加个衰减因子构成五元组

3.1 无环境交互(model-base)

状态转移概率函数+奖励函数=>已知的马尔可夫决策过程(环境已知)=>策略迭代+价值迭代=>最佳策略

把可能的动作和可能的状态转移的关系画成一个树状图。它们之间的关系就是从 $s_t$ 到 $a_t$ ，再到 $s_{t+1}$ ，再到 $a_{t+1}$ ，再到 $s_{t+2}$ 这样子的一个过程

跟环境交互，只能走完整的一条通路。这里面产生了一系列的一个决策的过程，就是跟环境交互产生了一个经验。使用概率函数(probability function)和奖励函数(reward function)来去描述环境。概率函数就是状态转移的概率，概率函数实际上反映的是环境的一个随机性。当知道概率函数和奖励函数时，这个MDP就是已知的，可以通过策略迭代(policy iteration)和价值迭代(value iteration)来找最佳的策略。如果知道这些状态转移概率和奖励函数的话，就说这个环境是已知的，因为我们是用这两个函数去描述环境的，如果是已知的话，其实可以用动态规划去计算说，很多强化学习的经典算法都是model-free的，就是环境是未知的

3.2 有环境交互(model-free)

价值函数+Q函数=>评价=>选取最大奖励的动作

在一个未知的环境里的，也就是这一系列的决策的概率函数和奖励函数是未知的，这就是model-based跟model-free的一个最大的区别。强化学习就是可以用来解决用完全未知的和随机的环境。强化学习要像人类一样去学习，人类学习的话就是一条路一条路地去尝试一下，先走一条路，看看结果到底是什么。多试几次，只要能活命的。可以慢慢地了解哪个状态会更好：

用价值函数 $V(s)$ 来代表这个状态是好的还是坏的
用Q函数来判断说在什么状态下做什么动作能够拿到最大奖励，用Q函数来表示这个状态-动作值

3.3 model-base与model-free的本质区别

当使用概率转移函数 $p[s_{t+1},r_t|s_t,a_t]$ 和奖励函数 $r[s_t,a_t]$ 来描述环境

model-base
- 当我们知道概率函数和奖励函数时，马尔可夫决策过程已知，可以采用策略迭代或价值迭代获得智能体的最优策略，这个过程Agent没有与环境进行交互
- 在很多实际的问题中，MDP的模型有可能是未知的，也有可能模型太大了，不能进行迭代的计算。比如Atari游戏、围棋、控制直升飞机、股票交易等问题，这些问题的状态转移太复杂了
model-free
- 当概率函数和奖励函数时，处于未知的环境中，让智能体与环境进行交互，采集很多轨迹数据，Agent从轨迹中获取信息改进策略，从而获得更多的奖励，目前大部分领域的AI应用都是model-free模式

3.4 Q表格(Q-table)

如果Q表格是一张已经训练好的表格的话，那这一张表格就像是一本生活手册

这张表格里面Q函数的意义就是选择了这个动作之后，最后面能不能成功，就是需要去计算在这个状态下，选择了这个动作，后续能够一共拿到多少总收益。如果可以预估未来的总收益的大小，就知道在当前的这个状态下选择哪个动作，价值更高，选择某个动作是因为未来可以拿到的那个价值会更高一点。所以强化学习的目标导向性很强，环境给出的奖励是一个非常重要的反馈，它就是根据环境的奖励来去做选择

但有的时候把目光放得太长远不好，因为如果事情很快就结束的话，考虑到最后一步的收益无可厚非。如果是一个持续的没有尽头的任务，即持续式任务(Continuing Task)，把未来的收益全部相加，作为当前的状态价值就很不合理

在这个环境当中，去计算状态动作价值(未来的总收益)可使用 $γ$ 折扣因子：考虑累积收益，并且对于未来的收益也做考虑，但是越后面的收益对当前价值影响越小，因此 $γ∈[0,1]$

State	Aciton 1	Aciton 2	Aciton 3	Aciton 4
(1,1)	0	0	0	0
(1,2)	0	0	0	0
(2,1)	0	0	0	0
(2,2)	0	0	0	0

类似于上表，最后我们要求解的就是一张Q表格

它的行数是所有的状态数量，一般可以用坐标来表示格子的状态，也可以用1、2、3、4、5、6、7来表示不同的位置
Q表格的列表示四个动作Action space

最开始这张Q表格会全部初始化为零，然后agent会不断地去和环境交互得到不同的轨迹，当交互的次数足够多的时候，就可以估算出每一个状态下，每个行动的平均总收益去更新这个Q表格。怎么去更新Q表格就是接下来要引入的强化概念。

强化就是可以用下一个状态的价值来更新当前状态的价值，其实就是强化学习里面bootstrapping的概念。在强化学习里面，可以每走一步更新一下Q表格，然后用下一个状态的Q值来更新这个状态的Q值，这种单步更新的方法叫做时序差分

3.5 无模型交互预测(model-free Prediction)

在没法获取MDP的模型情况下，可以通过以下两种方法来估计某个给定策略的价值：

(蒙特卡罗策略评估)Monte Carlo policy evaluation
(时序差分策略评估)Temporal Difference(TD) learning

3.5.1 蒙特卡罗(Monte-Carlo，MC)

思想：基于采样的方法，通过让agent跟环境进行交互，就会得到很多轨迹。每个轨迹都有对应的 return：
$G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots$

蒙特卡洛是用经验平均回报(emmpirical mean return)的方法来估计的，即把每个轨迹的return进行平均，就可以知道某一个策略下面对应状态的价值

算法步骤：

在时间步 $t$ ，状态 $s$ 被访问：

状态s的访问数增加1： $N(s)=N(s)+1$
状态s的总的回报 $S(s)$ 增加 $G_t$ ： $S(s)←S(s)+G_t$

通过回报的平均估计状态s的价值： $v(s)=S(s)/N(s)$

假设现在有样本 $x_1,x_2,\cdots$ ，可以把经验均值(empirical mean)转换成增量均值(incremental mean)的形式，如下式所示：
$\begin{aligned} \mu_{t} &=\frac{1}{t} \sum_{j=1}^{t} x_{j} \\ &=\frac{1}{t}\left(x_{t}+\sum_{j=1}^{t-1} x_{j}\right) \\ &=\frac{1}{t}\left(x_{t}+(t-1) \mu_{t-1}\right) \\ &=\frac{1}{t}\left(x_{t}+t \mu_{t-1}-\mu_{t-1}\right) \\ &=\mu_{t-1}+\frac{1}{t}\left(x_{t}-\mu_{t-1}\right) \end{aligned}$
通过这种转换，就可以把上一时刻的平均值跟现在时刻的平均值建立联系，即：
$\mu_t = \mu_{t-1}+\frac{1}{t}(x_t-\mu_{t-1})$
其中：

$x_t- \mu_{t-1}$ 是残差
$\frac{1}{t}$ 类似于学习率(learning rate)

当得到 $x_t$ ，就可以用上一时刻的值来更新现在的值：
$v(s_t)\leftarrow v(s_{t-1})+\alpha(G_t-v(s_{t-1}))$
比较动态规划法和蒙特卡洛方法的差异：

动态规划法：通过上一时刻的值的值。不断迭代，直到达到收敛： $v_t(s) \leftarrow \sum\limits_{a \in A} \pi(a|s)(R(s,a)+\gamma \sum\limits_{s' \in S}P(s'|s,a)v_{i-1}(s'))$ ，动态规划也是常用的估计价值函数的方法。在动态规划里面，我们使用了bootstrapping的思想。bootstrapping的意思就是基于之前估计的量来估计一个

蒙特卡洛方法：通过一个回合的经验平均回报进行更新： $v(s_t)\leftarrow v(s_{t-1})+\alpha(G_t-v(s_{t-1}))$ ，MC是通过empirical mean return(实际得到的收益)来更新它，对应树上面蓝色的轨迹，得到是一个实际的轨迹，实际的轨迹上的状态已经是决定的，采取的行为都是决定的。MC得到的是一条轨迹，这条轨迹表现出来就是这个蓝色的从起始到最后终止状态的轨迹。现在只是更新这个轨迹上的所有状态，跟这个轨迹没有关系的状态都没有更新

结论：

蒙特卡洛可以在未知环境中使用，而动态规划是model-based
蒙特卡洛只需要更新一条轨迹的状态，动态规划需要更新所有的状态。状态数量很多的时候，DP这样去迭代的话，速度是非常慢的。这也是sample-based的方法MC相对于DP的优势

3.5.2 时序差分学习(Temporal-Difference Learning，TD)

思想：时序差分(TD)学习是蒙特卡洛思想和动态规划思想的完美结合。一方面，像蒙特卡洛方法一样，时序差分不需要知道环境的动力学模型，可以从经历的回合中直接学习；另一方面，像动态规划一样，时序差分更新估计值基于部分已知的估计值，不需要等到最后的结果(完整的回合)，这就是引导bootstrapping的思想。因此，TD是无模型的，通过引导，从不完整的回合中学习，用一个估计来更新另一个估计。

目的：对于给定策略 $\pi$ ，在线地算出它的价值函数 $v^\pi$ ，即对于某个给定的策略，在线(online)地算出它的价值函数：
$v(s_t)←v(s_t)+α(G_t^n−v(s_t))$
最简单的算法是TD(0)，每往前走一步，就做一步bootstrapping，用得到的估计回报(estimated return)来更新上一时刻的值。估计回报 $R_{t+1}+\gamma v(S_{t+1})$ 被称为 TD目标(TD target)，TD目标是带衰减的未来收益的总和。TD目标由两部分组成：

走了某一步后得到的实际奖励： $R_{t+1}$
利用bootstrapping的方法，通过之前的估计来估计 $v(S_{t+1})$ ，然后加了一个折扣系数，即 $\gamma v(S_{t+1})$ ，具体过程如下式所示：

$\begin{aligned} v(s)&=\mathbb{E}\left[G_{t} \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}|s_t=s\right] +\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+\gamma^{2} R_{t+4}+\ldots \mid s_{t}=s\right]\\ &=R(s)+\gamma \mathbb{E}[G_{t+1}|s_t=s] \\ &=R(s)+\gamma \mathbb{E}[v(s_{t+1})|s_t=s]\\ \end{aligned}$

TD目标是估计有两个原因：它对期望值进行采样，并且使用当前估计 $v$ 而不是真实 $v_{\pi}$

TD误差(TD error)： $\delta=R_{t+1}+\gamma v(S_{t+1})-v(S_t)$

可以类比于Incremental Monte-Carlo的方法，写出如下的更新方法：
$v\left(S_{t}\right) \leftarrow v\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma v\left(S_{t+1}\right)-v\left(S_{t}\right)\right)$
时序差分目标是带衰减的未来收益的总和。对于n步时序差分：
$G_t^1=R_{t+1}+γv(S_{t+1})\\ G_t^2=R_{t+1}+γR_{t+2}+γv(S_{t+2})\\ ⋮\\ G_t^n=R_{t+1}+γR_{t+2}+⋯+γ^{n−1}R_{t+n}+γ^nv(S_{t+n})$
即当 $n\rightarrow \infty$ 时，时序差分变成了蒙特卡罗

3.5.3 比较蒙特卡洛和时序差分法

蒙特卡洛增量式:
$v(s_t) \leftarrow v(s_t)+\alpha(G_t-v(s_t))\\ G_t = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^k R_{t+1+k}$
时序差分增量式:
$v(s_t) \leftarrow v(s_t)+\alpha(G_t^n-v(s_t)) \\ TD(0): G_t^0=R_{t+1}+\gamma v(s_{t+1}) \\ TD(n):G_t^n = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^n v(s_{t+n})$

时序差分可以在不完整的序列上学习，蒙特卡洛只能在完整的序列上学习

时序差分可以在连续的环境下（无终止）学习，蒙特卡洛只能在有终止的情况下学习

时序差分可以在线学习，每走一步就可以更新。蒙特卡洛必须等到序列结束才能学习

3.6 无模型交互控制(model-free comtrol)

把policy iteration进行一个广义的推广，使它能够兼容MC和TD的方法，即Generalized Policy Iteration(GPI) with MC and TD

策略迭代：

Policy iteration由两个步骤组成：

根据给定的当前的policy $\pi$ 来估计价值函数
得到估计的价值函数后，通过greedy的方法来改进它的算法

这两个步骤是一个互相迭代的过程，由于不知道奖励函数和状态转移，无法使用策略迭代进行优化。因此我们引入广义策略迭代的方法

广义策略迭代(蒙特卡洛估计Q函数)：

用蒙特卡洛方法代替动态规划估计Q函数： $Q(s_t,a_t) \leftarrow Q(s_t,a_t)-\frac{1}{N(s_t,a_t)}(G(t)-Q(s_t,a_t))$
假设每一个回合都有一个探索性开始 $\ \epsilon$ ，保证所有的状态和动作都在无限步的执行后能被采样到

蒙特卡洛求Q表的过程：

在每一个策略迭代回合中

采用蒙特卡洛策略估计
- 首先采集数据，获得一条新的轨迹，计算轨迹上各个状态的真实回报 $G(t)=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^k R_{t+1+k}$
- 采用增量的方法更新Q： $Q(s_t,a_t) \leftarrow Q(s_t,a_t)-\frac{1}{N(s_t,a_t)}(G(t)-Q(s_t,a_t))$
基于贪心思想进行策略更新：
- $\pi(s)=\arg \max\limits_a q(s,a)$
一个策略迭代回合结束，采样数据进入新的一回合。当Q函数趋于收敛后，迭代过程结束，即获得了每个状态的Q函数

3.6.1 基于ε-贪心探索的蒙特卡罗算法(ε-greedy)

ε-贪心(ε-greedy)搜索：有1-ε的概率会按照Q-function来决定action，通常ε就设一个很小的值，1-ε可能是90%，也就是90%的概率会按照Q-function来决定action，但是有10%的机率是随机的。通常在实现上ε会随着时间递减。在最开始的时候。因为还不知道那个action是比较好的，所以会花比较大的力气在做exploration。接下来随着训练的次数越来越多。已经比较确定说哪一个Q是比较好的。就会减少exploration，把ε的值变小，主要根据Q-function来决定action，比较少做random，这是ε-greedy

算法流程如下：

因为时序差分相比于蒙特卡洛方法有如下优势：低方差，能够在线学习，能够从不完整序列中学习。因此可以把时序差分放到控制循环中估计Q表格，再采用ε-greedy改进探索

3.6.2 同策略时序差分控制(Sarsa)

特点

将时序差分更新V的过程，变成了更新Q：

$Q(s_t,a_t) \leftarrow Q(s_t,a_t)+\alpha[R_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]$

每次更新值函数都需要知道当前状态、当前动作、奖励、下一步状态、下一步动作A’，即 $(s_t,a_t,R_{t+1},s_{t+1},a_{t+1})$ 之后，就可以做一次更新。A’是下一步骤一定会执行的动作

更新公式
单步更新法：
每执行一个动作，就会更新以此价值和策略。单步Q收获为：
$q_t=R_{t+1}+\gamma Q(s_{t+1},a_{t+1})$
其中 $a_{t+1}$ 为下一步骤一定会执行的动作。单步Sarsa更新公式为：
$Q(s,a) \leftarrow Q(s,a)+\alpha[R_{t+1}+\gamma Q(s',a')-Q(s,a)]$

n步Sarsa（n-step Sarsa）:
在执行n步之后再来更新Q函数和策略。n步Q收获为：
$q_t^n=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^n$
如果给 $q_t^{(n)}$ 加上折扣因子 $\gamma$ 并进行求和，即可得到 $Sarsa(λ)$ 的Q收获：
$q_t^\lambda=(1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}q_t^{(n)}$
综上所述，将Q收获带入增量公式可得，n步 $Sarsa(λ)$ 更新公式为：
$Q(s_t,a_t) \leftarrow Q(s_t,a_t)+\alpha(q_t^\lambda-Q(s_t,a_t))$

Sarsa所作出的改变很简单，就是将原本TD更新V的过程，变成了更新Q，就是说可以拿下一步的Q值 $Q(S_{t+_1},A_{t+1})$ 来更新这一步的Q值 $Q(S_t,A_t)$ 。Sarsa是直接估计Q-table，得到Q-table后，就可以更新策略。该算法由于每次更新值函数需要知道当前的状态(state)、当前的动作(action)、奖励(reward)、下一步的状态(state)、下一步的动作(action)，即 $(S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})$ 这几个值，由此得名Sarsa算法。它走了一步之后，拿到了 $(S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})$ 之后，就可以做一次更新

代码演示：

class Sarsa(object):
    def __init__(self, n_actions,cfg,):
        self.n_actions = n_actions  
        self.lr = cfg.lr  
        self.gamma = cfg.gamma  
        self.sample_count = 0 
        self.epsilon_start = cfg.epsilon_start
        self.epsilon_end = cfg.epsilon_end
        self.epsilon_decay = cfg.epsilon_decay 
        self.Q  = defaultdict(lambda: np.zeros(n_actions)) # Q table
    def choose_action(self, state):
        self.sample_count += 1
        self.epsilon = self.epsilon_end + (self.epsilon_start - self.epsilon_end) * math.exp(-1. * self.sample_count / self.epsilon_decay) # The probability to select a random action, is is log decayed
        best_action = np.argmax(self.Q[state])
        action_probs = np.ones(self.n_actions, dtype=float) * self.epsilon / self.n_actions
        action_probs[best_action] += (1.0 - self.epsilon)
        action = np.random.choice(np.arange(len(action_probs)), p=action_probs) 
        return action
    def predict_action(self,state):
        return np.argmax(self.Q[state])
    def update(self, state, action, reward, next_state, next_action,done):
        Q_predict = self.Q[state][action]
        if done:
            Q_target = reward  # terminal state
        else:
            Q_target = reward + self.gamma * self.Q[next_state][next_action] 
        self.Q[state][action] += self.lr * (Q_target - Q_predict)

3.6.3 Q学习(Q-Learing)

Sarsa是一种同策略on-policy策略。Sarsa优化的是它实际执行的策略，它直接拿下一步会执行的action来去优化Q表格，所以on-policy在学习的过程中，只存在一种策略，它用一种策略去做action的选取，也用一种策略去做优化。所以Sarsa知道下一步的动作有可能会跑到悬崖那边去，所以它就会在优化它自己的策略的时候，会尽可能的离悬崖远一点。这样子就会保证说，它下一步哪怕是有随机动作，它也还是在安全区域内

而异策略off-policy在学习的过程中，有两种不同的策略:

第一个策略是需要去学习的策略，即target policy(目标策略)，一般用 $\pi$ 来表示，target policy就像根据自己的经验来学习最优的策略，不需要去和环境交互
另外一个策略是探索环境的策略，即behavior policy(行为策略)，一般用 $\mu$ 来表示。 $\mu$ 可以大胆地去探索到所有可能的轨迹，然后把采集到的数据喂给target policy去学习。而且喂给目标策略的数据中并不需要 $A_{t+1}$ ，而Sarsa是要有 $A_{t+1}$ 的。Behavior policy可以在环境里面探索所有的动作、轨迹和经验，然后把这些经验交给目标策略去学习。比如目标策略优化的时候，Q-learning不会管你下一步去往哪里探索，它就只选收益最大的策略

Off-policy learning有很多好处：

可以利用exploratory policy来学到一个最佳的策略，学习效率高
可以学习其他agent的行为，学习人或者其他agent产生的轨迹
重用老的策略产生的轨迹。探索过程需要很多计算资源，这样的话，可以节省资源。

Q-learning有两种policy：behavior policy和target policy：

Target policy $\pi$ 直接在Q-table上取greedy，就取它下一步能得到的所有状态，如下式所示：

$\pi\left(S_{t+1}\right)=\underset{a^{\prime}}{\arg \max}~ Q\left(S_{t+1}, a^{\prime}\right)$

Behavior policy $\mu$ 可以是一个随机的policy，但采取 ε-greedy，让behavior policy不至于是完全随机的，它是基于Q-table逐渐改进的

于是可以构造Q-learning target，Q-learning的next action都是通过argmax操作来选出来的，于是可以代入argmax操作，可以得到下式：
$\begin{aligned} R_{t+1}+\gamma Q\left(S_{t+1}, A^{\prime}\right) &=R_{t+1}+\gamma Q\left(S_{t+1},\arg \max ~Q\left(S_{t+1}, a^{\prime}\right)\right) \\ &=R_{t+1}+\gamma \max _{a^{\prime}} Q\left(S_{t+1}, a^{\prime}\right) \end{aligned}$
接着可以把Q-learning更新写成增量学习的形式，TD target就变成max的值，即
$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right]$