BasicRL(2)-蒙特卡洛(MC)方法和时序微分(TD)方法

之前用Bellman方程求全局最优的核心是我们知道完整的环境模型, 所有的 $P(s', r|s, a)$ 和 $R(s, a)$ 都是已知的. 但在现实问题中, 我们通常是不知道环境模型的, 也就是说我们不知道 $P(s', r|s, a)$ 和 $R(s, a)$ , 这时我们就需要用到蒙特卡洛(MC)方法和时序差分(TD)方法来对环境模型进行采样(Sample).

采样的核心是大数定律, 即样本均值收敛到期望值. 一般来说, 我们不一定能得到完整的函数(分布) $P(s', r|s, a)$ 和 $R(s, a)$ , 但我们总可以在一次实验之中得到 $s,a \to s'$ 和 $r$ (否则啥都不知道也不用做了), 对于这样的 $s,a \to s', r$ 的序列, 我们称之为一次采样, 也就是一次实验. 我们可以通过多次实验来估计 $P(s', r|s, a)$ 和 $R(s, a)$ , 这就是蒙特卡洛方法.

在实际算法之中, 为了简化, 我们通常估价的是Q和V, 而不是 $P(s', r|s, a)$ 和 $R(s, a)$

假设我们有一条实际实验的采样轨迹(trajactory)为 $s_1, a_1, r_1, ..., s_{T}, a_{T},r_{T}$ , 那么我们可以用这个轨迹来估计 $Q(s, a)$ 和 $V(s)$ .

$Q(s_1,a_1) \approx r_1 + \gamma r_2 + ...$

$V(s_1) \approx Q(s_1,a_1)$

蒙特卡洛(MC)方法

我们把 Bellman 方程之中,

$v_{k+1}=r_{\pi}+\gamma P_{\pi}v_k$ 称为Policy Evaluation(PE), 也就是策略评估, 用来评估一个策略的价值函数.

$\pi_{k+1}=argmax_{\pi}(r_{\pi}+\gamma P_{\pi}v_k)$ 称为Policy Improvement(PI), 也就是策略改进, 用来改进一个策略.

我们没有实际的环境模型, 那我们不知道 $v$ 和 $q$ , 但正如上面说的, 我们可以用采样轨迹来估计 $v$ 和 $q$ , 这就是蒙特卡洛方法.

$\pi_{k+1}=argmax_{\pi}(\sum_a \pi(a|s)q_{\pi}(s,a))$ ，用采样去估计这个 $q_{\pi}(s,a) = E(U_t|S_t=s,A_t=a) \approx \frac{1}{N}\sum_{i=1}^{N}u^{(i)}(s,a)$ ，其中 $u^{(i)}(s,a)$ 是第i次实验的采样值= $\sum_{t=1}^{T}r_t$ ，N是实验次数。

以上这个方法不妨叫做MC-Basic, 有几个问题

我们每次更新 $\pi$ ，都需要进行 $N$ 次完整的采样
随着 $\pi$ 逐渐趋近于最优策略, 每次采样的结果会越来越趋于重复, 一些边缘数据如果在前期没有出现, 那么在后期也不会出现, 这样会导致我们并不能得到全局最优

针对这两个问题，下面讲对应的方法

问题1：

MC Exploring Starts: MC-ES

对于一条轨迹 $s_1, a_1, r_1, ..., s_{T}, a_{T},r_{T}$ ，我们不仅可以用它来更新 $q_{\pi}(s_1,a_1)$ ，也可以用它来更新 $q_{\pi}(s_2,a_2)$ ， $q_{\pi}(s_3,a_3)$ ，...， $q_{\pi}(s_{T},a_{T})$ ，这大大增加了采样的效率

其伪代码如下

def MC_ES():
    for i in range(N):
        # 1. 生成一个随机的初始状态和动作
        s = random.choice(states)
        a = random.choice(actions)
        # 2. 生成一条轨迹
        traj = generate_traj(s, a)
        # 3. 用这条轨迹来更新Q, 一个eposide之中的每个(s,a)都会被更新
        for t in range(len(traj)):
            s, a, r = traj[t]
            # 平均值更新 new_avg = (old_avg * n + new_val)/(n+1) 
            q[s][a] = (q[s][a]*n[s][a] + r)/(n[s][a]+1)
            n[s][a] += 1
    return q

问题2：

MC $\epsilon$ -greedy

我们定义这样一个概率性策略

$\pi(a|s) = \begin{cases} \epsilon/m + 1-\epsilon & \text{if } a = argmax_{a}q(s,a) \\ \epsilon/m & \text{otherwise} \end{cases}$ ，其中m是动作的个数 $m=|A(s)|$

这样我们就可以保证每个动作都有一定的概率( $\epsilon/m$ )被选择到，从而保证了每个(s,a)都有可能被更新到，这样就可以一定程度上缓解问题2

MC算法还有一个问题就是不是所有的问题都能比较好地定义一个“终止”, 导致我们无法得到完整的轨迹, 这时我们可以用截断轨迹(truncated trajectory)来估计 $v$ 和 $q$ , 也就是说我们只用一部分的轨迹来估计 $v$ 和 $q$ , 这样会引入一定的偏差, 但一般来说这个偏差是可以接受的

时序差分(TD)方法

MC算法的核心在于用完整的trajactory估计Q,V, 而TD算法的核心在于用单步的r更新对Q,V的估计

具体来说， $r_{t+1} + \gamma v(s_{t+1})$ 比 $v(s_t)$ 更接近真实的 $v(s_t)$ （因为 $r_{t+1}$ 是真实环境的采样），所以我们可以用 $r_{t+1} + \gamma v(s_{t+1})$ 来更新 $v(s_t)$

我们把 $r_{t+1} + \gamma v(s_{t+1})$ 称为TD target，把 $v(s_t)$ 称为TD prediction, 两者的差值称为TD error $\delta_{\pi,t}$

如果TD error的期望趋于0, 就等效于我们的策略 $\pi$ 趋于最优策略 $\pi^{*}$

一个更高的overview是, 我们展开 $V(\pi)$

$V_{\pi}(s) = E_{\pi}(U_t | S_t=s) = E_{\pi}(r_t+\gamma r_{t+1}+...|S_t=s) = E_{\pi}(r_t+\gamma V_{\pi}(S_{t+1})|S_t=s)$ (这里的符号遵循一般约定，大写字母表示随机变量, 小写字母表示具体的值)

TD方法就是对最后一个等式进行估计，MC方法就是对前一个等式进行估计

在实际算法之中, 我们也是采用迭代式更新的方法

$v_{k+1}(s_t) = v_{k}(s_t) + \alpha_k \delta_{\pi,t}$

这个 $\alpha_{k}$ 也有人做过理论分析, 一般来说, $\alpha_{k}$ 是一个递减的函数, 也就是说, 随着迭代次数的增加, $\alpha_{k}$ 会逐渐减小, 这样可以保证我们的估计不会发散

更具体取值上, 收敛需要 $\sum_t \alpha_t = +\inf, \sum_t \alpha_t^{2} <+inf$

但实际上取 $\alpha$ 为一个小常数也是常见的做法

但是这两个方法虽然期望是一样的，方差却不一样, MC方法每一次更新是使用整条轨迹上的数据, 方差会比TD方法大很多, 更不容易收敛

而TD方法每一次更新只使用一步的数据, 方差会比MC方法小很多, 更容易收敛, 但有自举的问题(bootstraping) 这点在后续可以见到

TD方法	MC方法
online	offline
采样后立即更新	需要走过整个episode之后才能更新
自举	非自举
方差较小，收敛稳定	方差较大，收敛不问
依赖于初始值	不依赖于初始值

TD方法的一个典型算法是Sarsa算法, 也就是State-Action-Reward-State-Action算法

其核心在

用TD算法更新Q值, 也就是用 $r_{t+1} + \gamma q(s_{t+1},a_{t+1})$ 来更新 $q(s_t,a_t)$
用 $\epsilon$ -greedy算法保证探索

Sarsa算法的伪代码如下

def Sarsa():
    for i in range(N):
        # 1. 生成一个随机的初始状态
        s = random.choice(states)
        # 2.用e-greedy选择动作
        while not is_terminal(s):
            a = e_greedy(s, q)
            s_, r = step(s, a) # 环境的反馈
            a_ = e_greedy(s_, q)
            q[s][a] = q[s][a] + alpha*(r + gamma*q[s_][a_] - q[s][a])
            s = s_
            a = a_
    return q
def e_greedy(s, q):
    if random.random() < epsilon:
        return random.choice(actions)
    else:
        return argmax(q[s])

TD算法的一个问题是它是自举的，是有偏的，后续在讲解DQN的改进的时候也可以看到, TD的自举会导致在求解Bellman最优的时候对max操作产生不均匀放大，使得策略更偏向与采样到次数多的(s,a)

MC算法是无偏的, 但它方差大

结合两种算法, 我们可以一种折中的方案，称为n-step TD

$Q(s,a) \leftarrow r_1+\gamma r_2 + ... + \gamma^{n-1}r_n + \gamma^{n}Q(s_n,a_n)$

n=1时，这个n-step TD就是Sarsa算法，n->inf时, 这个n-step TD就是MC算法

BasicRL(2)-蒙特卡洛(MC)方法和时序微分(TD)方法

蒙特卡洛(MC)方法​

时序差分(TD)方法​

蒙特卡洛(MC)方法

时序差分(TD)方法