简介

时序差分（Temporal-Difference，TD）算法结合了前面讲到的动态规划和蒙特卡洛算法。如蒙特卡洛算法一样，它不需要知道具体的环境模型，可以直接从经验中学习；另一方面，继承了DP算法的自举（bootstrap）方法，可以利用学到的估计值来更新，而不用等到一个episode结束后再更新。

三种算法对于控制问题（即找到最优策略），都是使用广义的策略迭代的某个变种；主要不同在于预测问题，即如何对于一个给定策略估计价值函数。

1. 时序差分预测

TD算法和MC算法都是基于经验去解决预测问题。

蒙特卡洛

给定策略 $\pi$ 的一些经验以及这些经验中非终止状态$S_t$，一个适用于非平稳环境的简单的每次访问型蒙特卡洛方法可以表示为：

$V(S_t) \gets V(S_t) + \alpha[G_t-V(S_t)]$

其中$G_t$回报， $\alpha$常量步长参数，称之为常量$\alpha$MC。

问题：需要等到一幕结尾才能确定对$V(S_t)$的增量，只有这时 $G_t$才是已知的。

时序差分

TD 则只需要等到下一个时刻即可。在 t+1 时刻，TD 使用观察到的收益 $R_{t+1}$和估计值 $V(S_{t+1})$ 来进行一次有效更新：

$V(S_t) \gets V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1})-V(S_t)]$

TD(0)算法

也叫做单步TD

由于 TD(0) 的更新在某种程度上基于已存在的估计，类似于 DP 我们也称它为一种自举法

三种方法的简要比较

$\begin{aligned} v_{\pi}(s) &\doteq \mathbb{E}_{\pi}[G_t|S_t=s] \\ &= \mathbb{E}_{\pi}[R_{t+1}+\gamma G_{t+1}|S_t=s] \\ &= \mathbb{E}_{\pi}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s] \end{aligned}$

• (1)蒙特卡洛方法利用样本回报代替实际的期望回报
• (3)DP方法假设环境模型完整地提供期望，用估计值 $V(S_{t+1})$ 代替真实的$v_{\pi}(S_{t+1})$
• (2)TD方法结合了MC采样方法和DP自举方法

TD(0)回溯图

该图为表格型TD(0)回溯图，其顶部状态节点价值的估计值根据一个直接后继状态节点的单次样本转移更新。

采样更新：通过采样获得新的后继状态，使用后继状态的价值和沿途得到的收益计算回溯值，然后相应地改变原始状态价值的估计值。（MC和TD采用的方法）

与DP方法中期望更新的不同在于：

采样更新的计算基于采样得到的单个后继节点样本；期望更新则需要考虑所有可能后继节点的完整分布

TD误差

$\delta_{t} \doteq R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$

衡量 $S_t$的估计值与更好的估计 $R_{t+1} + \gamma V(S_{t+1})$之间的差异

• 蒙特卡洛误差

可以看作是价值函数数组V在一幕内没有发生改变，即可写作TD误差之和

$\begin{aligned} G_t-V(S_t) &= R_{t+1} + \gamma G_{t+1} - V(S_t) + \gamma V(S_{t+1}) - \gamma V(S_{t+1}) \\ &= \delta_t + \gamma(G_{t+1} - V(S_{t+1}))\\ &= \delta_t + \gamma \delta_{t+1} + \gamma^2(G_{t+2} - V(S_{t+2}))\\ &= \delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+1} +…+\gamma^{T-t}(G_T - V(S_T))\\ &= \delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+1} +…+\gamma^{T-t}(0 - 0)\\ &= \sum_{k=t}^{T-1} \gamma^{k-t} \delta_k \end{aligned}$

需要注意的是：V在该幕中变化了，等式将不准确；若当前时刻的步长较小可近似成立。

练习

TD误差公式： $\delta_{t} \doteq R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$

TD更新公式： $V_{t+1}(S_t) = V_t(S_t) + \alpha[R_{t+1} + \gamma V_{t}(S_{t+1})-V_t(S_t)]$

此时新的推导公式：

$u_{t+1} = V_{t+1}(S_t)-V_t(S_t) = \alpha[R_{t+1} + \gamma V_{t}(S_{t+1})-V_t(S_t)]$

$\begin{aligned} G_t-V_t(S_t) &= R_{t+1} + \gamma G_{t+1} - V_t(S_t) + \gamma V_t(S_{t+1}) - \gamma V_t(S_{t+1}) \\ &= \delta_t + \gamma(G_{t+1} - V_t(S_{t+1}))\\ &= \delta_t + \gamma(G_{t+1} - V_{t+1}(S_{t+1})) + \gamma u_{t+1}\\ &= \delta_t + \gamma \delta_{t+1} + \gamma^2(G_{t+2} - V_{t+1}(S_{t+2})) + \gamma u_{t+1} + \gamma^2 u_{t+2}\\ &= \sum_{k=t}^{T-1} [\gamma^{k-t} \delta_k + \gamma^{k-t+1} u_{k+1}] \end{aligned}$

额外项：

$\sum_{k=t}^{T-1} \gamma^{k-t+1} u_{k+1}$

2. 时序差分预测方法的优势

• 能够自举
• 相比于DP，不需要一个环境模型
• 相比于MC，是一种在线、完全递增的方法（由于一些场景是持续性任务，无法划分出”幕“的概念）
• 扎实的理论基础：
• 对于任何固定的策略$\pi$,TD(0)已经被证明能够收敛到 $v_{\pi}$
• 步长参数足够小，则均值能够收敛到 $v_{\pi}$
• 大多数收敛证明仅适用于基于表格的算法，也有部分使用与使用广义线性函数近似的情况
• 收敛速度
• TD在随机任务上通常比常量 $\alpha$MC方法收敛更快

例6.2随机游走

比较TD(0)和常量 $\alpha$MC方法在马尔可夫收益过程的预测能力

马尔可夫收益过程（MRP）：不包含动作的马尔科夫决策过程。

由于当前任务没有折扣，因此每个状态的真实价值就是从这个状态开始并终止于最右侧的概率。当前状态A~E的真实价值：$\frac{1}{6},\frac{2}{6},\frac{3}{6},\frac{4}{6},\frac{5}{6}$

上述实验中近似价值函数 V(s)均初始化为0.5.

图一：

• 100个episode之后估计值已经十分接近真实值。
• 由于当前采用了常数步长参数 $\alpha=0.1$，所以估计值会反映较近的若干幕结果，其不规律的上下波动。

图二：

• 针对不同的 $\alpha$的学习曲线
• 显示的是5个状态上的平均误差，并100次运行的结果
• TD方法当前要优于MC方法

代码实现

## 初始化设置
VALUES = np.zeros(7)
VALUES[1:6] = 0.5
## For convenience, we assume all rewards are 0
## and the left terminal state has value 0, the right terminal state has value 1
## This trick has been used in Gambler's Problem
VALUES[6] = 1

## set up true state values
TRUE_VALUE = np.zeros(7)
TRUE_VALUE[1:6] = np.arange(1, 6) / 6.0
TRUE_VALUE[6] = 1

ACTION_LEFT = 0
ACTION_RIGHT = 1

## TD和MC方法实现
def temporal_difference(values, alpha=0.1, batch=False):
    ## 起点位置
    state = 3
    trajectory = [state]
    rewards = [0]
    while True:
        old_state = state
        if np.random.binomial(1, 0.5) == ACTION_LEFT:
            state -= 1
        else:
            state += 1
        ## Assume all rewards are 0
        reward = 0
        trajectory.append(state)
        ## TD update
        if not batch:
            values[old_state] += alpha * (reward + values[state] - values[old_state])
        ## 终止条件
        if state == 6 or state == 0:
            break
        rewards.append(reward)
    return trajectory, rewards

def monte_carlo(values, alpha=0.1, batch=False):
    state = 3
    trajectory = [state]

    ## if end up with left terminal state, all returns are 0
    ## if end up with right terminal state, all returns are 1
    while True:
        if np.random.binomial(1, 0.5) == ACTION_LEFT:
            state -= 1
        else:
            state += 1
        trajectory.append(state)
        if state == 6:
            returns = 1.0
            break
        elif state == 0:
            returns = 0.0
            break

    if not batch:
        for state_ in trajectory[:-1]:
            ## MC update
            values[state_] += alpha * (returns - values[state_])
    return trajectory, [returns] * (len(trajectory) - 1)

练习

说明第一个episode在状态A停止了；因为在此过程中并没有获取任何关于中间过渡的信息；由于 V(s) 均初始化为0.5，常数步长参数$\alpha=0.1$，那么此时被改变了 $0.5*(-\alpha)=-0.05$

不会；不存在；足够小的步长参数是这两种方法的收敛要求，因此更小的参数在长期来看能够比更大的步长参数达到更好的效果并且能够达到其性能极限即最小误差，而图示则充分的展现了不同常数步长参数$\alpha$下不同方法能够达到的性能极限。

• $\alpha$还不够小
• 初始化可能不够理想

• 直接采用DP算法准确计算结果
• 根据概率计算

$\begin{aligned} P_E(R) &= 1- P_E(L) \\ &= 1- P_E(D)*P_D(L) \\ &= 1- P_E(D)*[P_D(C)*P_C(L) + P_D(E)*P_E(L)] \\ \end{aligned}$

根据对称：

$P_C(L) = P_C(R) = 0.5$

$\begin{aligned} P_E(R) &= 1- 0.5*[0.5*0.5 + 0.5*P_E(L)] \\ &= 1- P_E(L) \\ \end{aligned}$

$P_E(L) = 0.5*[0.5*0.5 + 0.5*P_E(L)],P_E(L) = \frac{1}{6},P_E(R) = \frac{5}{6}$

3. TD(0)的最优性

TD(0)方法可以分为批处理和非批处理的。对于批处理更新，首先固定值函数，将一个片段中每一个时间点的值函数累计更新相加，在片段结束时，统一对值函数进行一次更新。而非批处理的方式，则如上一节中所述，每一时刻都进行值函数更新。

批量更新

给定近似价值函数V ，在访问非终止状态的每个时刻t ，计算相应的增量，但是价值函数仅根据所有增量的和改变一次。然后，利用新的值函数再次处理所有可用的经验，产生新的总增量，依此类推，直到价值函数收敛。我们称这种方法为批量更新，因为只有在处理了整批的训练数据后才进行更新。

在批量更新下，只要选择足够小的步长参数$\alpha$， TD(0) 就能确定地收敛到与$\alpha$无关的唯一结果；

常数 $\alpha$MC方法在相同条件下也能确定地收敛，但是会收敛到不同的结果

代码实现

def batch_updating(method, episodes, alpha=0.001):
    ## perform 100 independent runs
    runs = 100
    total_errors = np.zeros(episodes)
    for r in tqdm(range(0, runs)):
        current_values = np.copy(VALUES)
        current_values[1:6] = -1
        errors = []
        ## track shown trajectories and reward/return sequences
        trajectories = []
        rewards = []
        for ep in range(episodes):
            if method == 'TD':
                trajectory_, rewards_ = temporal_difference(current_values, batch=True)
            else:
                trajectory_, rewards_ = monte_carlo(current_values, batch=True)
            trajectories.append(trajectory_)
            rewards.append(rewards_)
            while True:
                ## keep feeding our algorithm with trajectories seen so far until state value function converges
                updates = np.zeros(7)
                for trajectory_, rewards_ in zip(trajectories, rewards):
                    for i in range(0, len(trajectory_) - 1):
                        if method == 'TD':
                            updates[trajectory_[i]] += rewards_[i] + current_values[trajectory_[i + 1]] - current_values[trajectory_[i]]
                        else:
                            updates[trajectory_[i]] += rewards_[i] - current_values[trajectory_[i]]
                updates *= alpha
                if np.sum(np.abs(updates)) < 1e-3:
                    break
                ## perform batch updating
                current_values += updates
            ## calculate rms error
            errors.append(np.sqrt(np.sum(np.power(current_values - TRUE_VALUE, 2)) / 5.0))
        total_errors += np.asarray(errors)
    total_errors /= runs
    return total_errors

例子6.4

对于状态B两种方法都可以得到答案 $V(B)=\frac{3}{4}$,而两种方法将会获得不一样的V(A) ：

1. 当采用批量MC方法可以直接得到 V(A)=0
2. 采用批量TD(0)方法，根据当前数据可以得出，状态A将以100%概率转移到B，所以 $V(A)=\frac{3}{4}$

结合以上例子，我们可以发现两种方法的批量更新的效果的不同：

• MC：找出最小化训练集上均方误差的估计。
• TD(0)：找出完全符合马尔可夫过程模型的极大似然估计参数。(一个参数的极大似然估计是使得生成训练数据的概率最大的参数值，即$\hat{\theta} = \argmax_{\theta} p(\theta|x)$）

确定性等价估计：

由于当前的极大似然估计不是某个具体的参数，而是基于观测数据形成的马尔可夫过程模型。具体而言包含状态转移概率的估计值、期望收益，当这些信息是正确的就可以正确估计出价值函数。

由于这种估计等价于假设潜在过程参数的估计是确定性的而不是近似的，因此又被称为确定性等价估计。

TD方法比MC方法更快收敛。

练习

直接根据章节5.6中的离轨策略，将其中更新部分的G改成V，并给V赋予合适的下标t即可

4. Sarsa：同轨策略下的时序差分控制

在面对exploration和exploitation的两难时，算法又分为了两类：on-policy和off-policy算法。Sarsa是一种on-policy TD算法。我们去学习一个最优的动作-状态值函数而不是状态值函数。

$Q(S_t,A_t)←Q(S_t,A_t)+α[R_{t+1}+γQ(S_{t+1},A_{t+1})−Q(S_t,A_t)]$

Sarsa算法的原始策略和更新策略是一致的，而其更新策略和MC不一样的是其策略更新不需要采样一个完整的轨迹，在执行完一个动作后就可以更新其值函数。如果 $S_{t+1}$是终止状态，则 $Q(S_{t+1},A_{t+1})$ 定义为0。之所以叫Sarsa是因为迭代算法中的五个元素 $S_t,A_t,R_{t+1},S_{t+1},A_{t+1}$.其伪代码如下图：

Sarsa算法的收敛性取决于策略对于Q的依赖程度。例如，我们可以采用 ε-贪心或软性策略。只要所有”状态-动作”二元组都被无限多次地访问到，并且贪心策略在极限情况下能够收敛(这个收敛过程可以通过令 $\epsilon = \frac{1}{t}$来实现)，Sarsa 就能以1 的概率收敛到最优的策略和动作价值函数.

例6.5有风的网格世界

每一列的风力如表格数字所示，会将智能体上吹这个数字的格数。当前任务是不带折扣的分幕式任务，并且达到目标前每步收益为-1。图示曲线，采用的是 $\epsilon$-贪心的Sarsa算法的结果，其中$\epsilon=0.1,\alpha=0.5$,并对所有s,a初始化 Q(s,a)=0.(MC方法不适用)

代码实现

## world height
WORLD_HEIGHT = 7

## world width
WORLD_WIDTH = 10

## wind strength for each column
WIND = [0, 0, 0, 1, 1, 1, 2, 2, 1, 0]

## possible actions
ACTION_UP = 0
ACTION_DOWN = 1
ACTION_LEFT = 2
ACTION_RIGHT = 3

## probability for exploration
EPSILON = 0.1

## Sarsa step size
ALPHA = 0.5

## reward for each step
REWARD = -1.0

START = [3, 0]
GOAL = [3, 7]
ACTIONS = [ACTION_UP, ACTION_DOWN, ACTION_LEFT, ACTION_RIGHT]

def step(state, action):
    i, j = state
    if action == ACTION_UP:
        return [max(i - 1 - WIND[j], 0), j]
    elif action == ACTION_DOWN:
        return [max(min(i + 1 - WIND[j], WORLD_HEIGHT - 1), 0), j]
    elif action == ACTION_LEFT:
        return [max(i - WIND[j], 0), max(j - 1, 0)]
    elif action == ACTION_RIGHT:
        return [max(i - WIND[j], 0), min(j + 1, WORLD_WIDTH - 1)]
    else:
        assert False

## play for an episode
def episode(q_value):
    ## track the total time steps in this episode
    time = 0

    ## initialize state
    state = START

    ## choose an action based on epsilon-greedy algorithm
    if np.random.binomial(1, EPSILON) == 1:
        action = np.random.choice(ACTIONS)
    else:
        values_ = q_value[state[0], state[1], :]
        action = np.random.choice([action_ for action_, value_ in enumerate(values_) if value_ == np.max(values_)])

    ## keep going until get to the goal state
    while state != GOAL:
        next_state = step(state, action)
        if np.random.binomial(1, EPSILON) == 1:
            next_action = np.random.choice(ACTIONS)
        else:
            values_ = q_value[next_state[0], next_state[1], :]
            next_action = np.random.choice([action_ for action_, value_ in enumerate(values_) if value_ == np.max(values_)])

        ## Sarsa update
        q_value[state[0], state[1], action] += \
            ALPHA * (REWARD + q_value[next_state[0], next_state[1], next_action] -
                     q_value[state[0], state[1], action])
        state = next_state
        action = next_action
        time += 1
    return time

练习6.8-6.10

$\begin{aligned} G(S_t,A_t)-Q(S_t,A_t) &= R_{t+1} + \gamma G(S_{t+1},A_{t+1}) - Q(S_t,A_t) + \gamma Q(S_{t+1},A_{t+1}) - \gamma Q(S_{t+1},A_{t+1}) \\ &= \delta_t + \gamma(G(S_{t+1},A_{t+1}) - Q(S_{t+1},A_{t+1}))\\ &= \delta_t + \gamma \delta_{t+1} + \gamma^2[G(S_{t+2},A_{t+2}) - Q(S_{t+2},A_{t+2})] \\ &= \sum_{k=t}^{T-1} \gamma^{k-t} \delta_k \end{aligned}$

ex6.9.ipynb

ex6.10.ipynb

Q学习：离轨策略下的时序差分控制

跟SARSA在具体操作上非常类似。

$Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha[{R_{t+1}} + \gamma {Q(S_{t+1},A_{t+1})}-Q(S_t,A_t)]$

$A_{t+1}$不依据原本策略b选取

在Q-table中有值，比如说：

$Q(S_{t+1},a_1)=1\\ Q(S_{t+1},a_2)=2\\ Q(S_{t+1},a_3)=3\\$

直接用贪心策略$a^*=\pi(S_{t+1})=\underset{a}{\arg\max}{Q(S_{t+1},a)}$

策略$\pi$是另外一个策略，显然$\pi\ne b$

b是软性策略，而$\pi$是确定性策略，在状态$S_{t+1}$肯定选择动作$a_3$

$Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha[{R_{t+1}} + \gamma \underset{a}\max{Q(S_{t+1},a)}-Q(S_t,A_t)]$

离轨策略

在公式中用于更新的动作为$\underset{a}{\arg\max}{Q(S_{t+1},a)}$，而下一步却未必是$\underset{a}{\arg\max}{Q(S_{t+1},a)}$

举例

【问题描述】：这是一个标准的不含折扣的分幕式任务，包含起点和目标状态，可以执行上下左右四个动作。掉下悬崖会得到-100的收益，其他的转移得到的收益都是-1，同时把智能体送回起点。

【RL任务】：Agent从起始点S开始，寻找最优路径，避开悬崖，走到终点G。（走入悬崖或者走到终点，都将返回到起点，开始新的episode）

【训练结果】：

Q-Learning学到了Optimal path，Sarsa则学到了Safer path。

【结果分析】：

截取前面几个状态来分析Sarsa和Q-Learning的不同之处。

Q-Learning：在已知$Q(S_2,down)$很小的情况下，在$S_1$时，若选到了动作$right$，产生$s’=S_2$，目标策略将根据$S_2$产生具有最大动作值函数对应的动作$a’$（$\underset{a}\arg\max Q(S_2,a)$），$Q(S_2,down)$很小这件事不会影响到$Q(S_1,right)$。

Sarsa：在已知$Q(S_2,down)$很小的情况下，在$S_1$时，若选到了动作$right$，由于行为策略和目标策略是一体的，若接下来在$S_2$选中动作$down$，则目标策略会跟着变差。$Q(S_2,down)$会直接影响到$Q(S_1,right)$大幅下降。

期望Sarsa

行动策略b：

Q-table

SARSA：$Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha[{R_{t+1}} + \gamma {\underset{80}{\underline{Q(S_{t+1},A_{t+1})}}}-Q(S_t,A_t)]$

Q-Learning：$Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha[{R_{t+1}} + \gamma \underset{100}{\underline{\underset{a}\max{Q(S_{t+1},a)}}}-Q(S_t,A_t)]$

期望SARSA：$Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha[{R_{t+1}} + \gamma {\underset{100\cdot 0.7+80\cdot 0.3=93}{\underline{\mathbb{E_{b(=\pi)}}[Q(S_{t+1},A_{t+1})\mid S_{t+1}]}}}-Q(S_t,A_t)]$

$\boldsymbol{1}$：更新的时候一方面参考行动策略b的概率分布，另一方面不去真的采样出一个具体的action，有可能是$a_1$有可能是$a_6$，至少在更新的时候没有采样采出来。具体操作是求期望。

在期望SARSA的更新中，我们使用的实际上还是b这个策略，所以默认情况下$\pi =b$，是同轨的。

考虑用另外一个策略，不用行动策略b，但还是求期望。

若$\pi$是贪心策略，即$\pi(S_{t+1})=\underset{a}{\arg\max}{Q(S_{t+1},a)}=a^*$，期望SARSA为离轨策略，此时不是一个$\mathbb{E_{\pi}}[Q(S_{t+1},A_{t+1})\mid S_{t+1}]=Q(S_{t+1},a^*)=\max_a{Q(S_{t+1},a)}$，期望SARSA退化为Q-Learning.

Q-Learning是期望SARSA的特例

最大化偏差与双学习

最大化偏差：在估计值的基础上进行最大化，可以被看作隐式地对最大值进行估计，会产生一个显著的正偏差。

举例：在状态$s$时，可以选择多个动作$a$。真实价值$q(s,a)=0$，但估计值$Q(s,a)$不确定，估计值的最大值可能是正数，因此产生正偏差。

$E(\max{(X_1,X_2,\ldots)})\geq\max{(E(X_1),E(X_2),\ldots)}$

最优值函数$Q$的更新依赖于$\underset{a}{\max}Q(s,a)$:

$Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha[{R_{t+1}} + \gamma \underset{a}\max{Q(S_{t+1},a)}-Q(S_t,A_t)]$

而最优动作值函数为：$Q^*(s,a)=\sum_{s’}p(s’\mid s,a)(r(s,a,s’)+\gamma \underset{a}{\max}Q^*(s’,a))$

我们希望对回报的期望求max，顺序应该是$\max{\mathbb{E}(\cdot)}$，但是Q-Learning的做法是采样$a$时取max，然后多次采样求平均值来估计，顺序是$\mathbb{E}(\max{(\cdot)})$，因此是高估了Q值。

举例

【问题描述】：

以上MDP有两个非终止节点A和B。每幕都从A开始并选择向左或向右的动作。选择向右的动作会立刻转移到终止状态并获得0收益。选择向左的动作则会使状态转移到B，并获得0奖赏。对于状态B有多个动作，所有动作被选择后都会立刻终止，每个动作的奖赏值服从均值为-0.1，方差为1的正态分布。

【Q-Learning求解】：

假设状态B下有10个动作，则当Q-Learning从状态A开始采样，并更新$Q(A,left)$时，会先分别计算状态B下的所有动作对应的Q值，然后选取最大的Q值和奖赏作为A-left的更新：

$Q(A,left)\gets Q(A,left)+\alpha [0+\gamma\max{[Q(B,a_1),Q(B,a_2)],\ldots,Q(B,a_{10})}]-Q(A,left)]$

由于B的所有动作奖赏是一个服从$\mu=-0.1<0$的正态分布，所以$Q(A,left)$的真实值应该是：

$Q^*(a,left)=\gamma\cdot\mathbb{E}[Q(B,a)]=\gamma\cdot\mu=-0.1\gamma<0=Q(A,right)$

而由于噪声的存在，使得少量的$Q(B,a_i)>0$，从而有：

$Q(A,left)=\gamma\cdot\max{[Q(B,a_1),Q(B,a_2),\ldots,Q(B,a_{10})}]>0=Q(A,right)$

因此，状态A在初期计算出大部分最优动作为$A^*=left$，直到状态B下的大部分$Q(B,a_i)<0$时，$Q(A,left)$才逐渐降低到0以下。

采样初期，状态$A$选择$left$的次数先是越来越多，随后逐步降低。

问题出现在Q-Learning的更新公式中的max操作导致了最大化偏差，因此想要消除偏差要让更新与max操作解耦合，并且要让最接近真实价值的$Q(B,a)$来更新$Q(A,left)$。

由于噪声的存在，最优值一般不来自某个固定的动作，因此思路应该从找到这个最优价值，转变为找到最有可能出现最有价值的动作。

双学习

问题根源在于确定价值最大的动作和估计它的价值，这两个过程采用了同样的样本。

$Q(S,A^*)$，估计action的Q值

$A^*=\underset{a}{\arg\max}{Q(S,a)}$，根据Q值选择最优action

针对这个原因，双学习的思想是用2份独立样本去做估计，对应到Q-Learning中就是用2个独立的$Q$表做估计。其中，$Q_1$表根据$Q_1$值选择最优动作$a^*$，$Q_2$表根据$Q_1$采样出的$a^*$在$Q_2$中的值来更新$Q_1$表。

代码

import numpy as np
import random

class Env():                   
    '''构造一个环境类'''        
    def __init__(self, mu, sigma, nB):  
        self.mu = mu
        self.sigma = sigma
        self.STATE_A = self.left = 0
        self.STATE_B = self.right = 1
        self.Terminal = 2
        self.nS = 3   ## 加上Terminal即3个状态
        self.nA = 2
        self.nB = nB  ## 状态B的动作数
        self.state = self.STATE_A 

    def reset(self):
        self.state = self.STATE_A
        return self.state

    def step(self, action):
        ## A--left
        if self.state == self.STATE_A and action == self.left:
            self.state = self.STATE_B
            return self.state, 0, False  ## next_state, reward, done
            ## A--right
        elif self.state == self.STATE_A and action == self.right:
            self.state = self.Terminal
            return self.state, 0, True
            ## B--all_actions
        elif self.state == self.STATE_B:
            self.state = self.Terminal
            reward = random.normalvariate(self.mu, self.sigma)
            return self.state, reward, True 

def init_Q_table(env):
    '''初始化Q表'''
    Q = {env.STATE_A:{action:0 for action in range(env.nA)},
         env.STATE_B:{action:0 for action in range(env.nB)},
         env.Terminal:{action:0 for action in range(env.nA)}}
    return Q

def select_action_behavior_policy(action_value_dict, epsilon):
    '''使用epsilon-greedy采样action'''
    if random.random() > epsilon:   
        max_keys = [key for key, value in action_value_dict.items() if value == max( action_value_dict.values() )]
        action = random.choice(max_keys)
    else:  
        ## 从Q字典对应state中随机选取1个动作,由于返回list,因此通过[0]获取元素
        action = random.sample(action_value_dict.keys(), 1)[0]
    return action

def get_Q1_add_Q2(Q1_state_dict, Q2_state_dict):
    '''返回Q1[state]+Q2[state]'''
    return {action: Q1_value + Q2_state_dict[action] for action, Q1_value in Q1_state_dict.items()}

def double_Q_learning(env, alpha=0.2, epsilon_scope=[0.2,0.05,0.99], num_of_episode=1000, gamma=0.9):
    '''
    双Q学习算法; 其中epsilon_scope由高到低衰减,从左到右分别是[最高值,最低值,衰减因子]
    '''
    epsilon = epsilon_scope[0]
    ## 1. 初始化Q1表和Q2表
    Q1 = init_Q_table(env)
    Q2 = init_Q_table(env)
    for num in range(num_of_episode):
        state = env.reset()  ## Init S=A 初始状态为状态A
        while True:
            ## 2.通过behavior policy采样action
            add_Q1_Q2_state = get_Q1_add_Q2(Q1[state], Q1[state])    #get Q1(A,left)+Q2(A,left) & Q1(A,right)+Q2(A,right)
            action = select_action_behavior_policy(add_Q1_Q2_state, epsilon)  #根据epsilon-greedy选择Q值最大的action
            ## 3.执行action并观察R和next state
            next_state, reward, done = env.step(action)
            ## 4.更新Q(S,A),使用max操作更新
            if random.random() >= 0.5:
                ## 从Q1表中的下一步state找出状态价值最高对应的action视为Q1[state]的最优动作
                A1 = random.choice( [action for action, value in Q1[next_state].items() if value == max( Q1[next_state].values() )] )
                ## 将Q1[state]得到的最优动作A1代入到Q2[state][A1]中的值作为Q1[state]的更新
                Q1[state][action] += alpha * (reward + gamma*Q2[next_state][A1] - Q1[state][action])
            else:
                A2 = random.choice( [action for action, value in Q2[next_state].items() if value == max( Q2[next_state].values() )] )
                Q2[state][action] += alpha * (reward + gamma*Q1[next_state][A2] - Q2[state][action])
            if done: break
            state = next_state
        ## 对epsilon进行衰减
        if epsilon >= epsilon_scope[1]: epsilon *= epsilon_scope[2]
    return Q1

env = Env(-0.1, 1, 10)   
## Double Q-learning学习出Q1≈Q2表
Q_table = double_Q_learning(env, alpha=0.2, epsilon_scope=[0.2,0.05,0.99], num_of_episode=300, gamma=0.9)  

分析中间的某一个episode：

episode 25：$S=A$，$A=left$，$S’=B$

$Q_2(A,left) \gets Q_2(A,left) + \alpha[{R} + \gamma Q_1(B,a_3)-Q_2(A,left)]$

从episode25到episode26的更新过程中，$Q_1[A][left]$没有更新，而$Q_2[A][left]$降低了，由此可以断定此处是用$Q_2[B]$中的action对应于$Q_1[B]$的值来更新$Q_2$。

此处$\underset{a}{\arg\max}Q_2(B,a)=a_3$，而$Q_2(B,a_3)=0.43>0$，明显是噪声。用来更新$Q(A,left)$会增加$left$动作的价值。但噪声在整体$Q(B)$中的数量很少，只要避开固定最大$Q$值对应的action即可极大的增加估计准确率。

Double Q-Learning的做法是：在$Q_2[B]$中选出最优动作$a_3$，然后带入到$Q_1(B,a_3)$（大概率小于0）来更新$Q_2(A,left)$，以尽可能真实地评估$Q(A,left)$的值。

游戏、后位状态和其他特殊例子

后位状态价值函数

传统的状态价值函数估计的是在某个状态中，智能体选择执行一个动作时这个状态的价值。

$S_1$ $a_1$ $S_2$ $a_2$

在井字棋中，不同的棋局和下法会产生相同的局面，因此它们的价值也必须是相同的。

传统的价值函数会分别评估$Q(S_1,a_1)$和$Q(S_2,a_2)$，但是后位状态价值函数会将这两种情况看作是一样的，能够缩小计算量。

参考资料

https://www.bilibili.com/video/BV15L411T7LM/?spm_id_from=333.788

https://zhuanlan.zhihu.com/p/269870048

https://zhuanlan.zhihu.com/p/377938399

书本链接

《强化学习 第2版》.pdf

http://incompleteideas.net/book/RLbook2020.pdf

https://rl.qiwihui.com/zh_CN/latest/partI/chapter6/temporal_difference_learning.html

https://laddie132.github.io/Reinforcement-Learning-Notes/chapter/chapter6.html

参考讲解链接

https://zhuanlan.zhihu.com/p/34747205

https://leovan.me/cn/2020/07/model-free-policy-prediction-and-control-temporal-difference-learning/

https://zhuanlan.zhihu.com/p/51091335

https://github.com/LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions

Latex 公式表

https://www.cnblogs.com/wuliytTaotao/p/9714070.html

https://blog.csdn.net/xovee/article/details/107733398

代码链接

https://github.com/ShangtongZhang/reinforcement-learning-an-introduction

https://github.com/PiperLiu/Reinforcement-Learning-practice-zh