强化学习：时序差分算法 TD-learning-Toy模板网

这篇具有很好参考价值的文章主要介绍了强化学习：时序差分算法 TD-learning。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

例子引入

首先，我们考虑简单的平均估计计算： $w = E [X]$ ，根据 RM算法计算过程如下：

强化学习：时序差分算法 TD-learning

接着上面的例子，我们现在考虑一个较为复杂的问题，估计函数 $v (X)$ 的平均值，根据 RM算法计算过程如下：
强化学习：时序差分算法 TD-learning

接着上面的例子，我们现在考虑一个更复杂的问题，有两个随机变量，根据 RM算法计算过程如下：
强化学习：时序差分算法 TD-learning

TD 算法介绍

TD-Learning 通常指的是广泛的一类RL算法，但此处的 TD-Learning 是指一种特定的算法：状态估计算。

TD算法是基于数据的，也就是说它不基于模型来实现强化学习的。那它要的数据是什么呢?是遵循给定的策略 $π$ 产生的，形式可以为一长串 $s_0,r_1,s_1....,s_{t},r_{t+1},s_{t+1}...)$ 或者写成集合 ${\{(s_{t},r_{t+1},s_{t+1})\}}_t$ ，TD算法是用这些数据来估计这个策略 $π$ 所对应的 state value，如下：
强化学习：时序差分算法 TD-learning
其中 $t = 0, 1, 2, ...$ ， $v_t(s_t)$ 是策略 $π$ 下状态 $s_t$ 的状态估计值； $\alpha_t (s_t)$ 是时间 $t$ 时刻 $s_t$ 的学习率。在 $t$ 时刻，只有访问的状态 $s_t$ 的值被更新，而未访问的状态 $s_t$ 的值保持不变。

我们来看详细的分析：
强化学习：时序差分算法 TD-learning

为什么 $\bar v_t$ 被称为 TD target ？这是因为 TD 算法将是将 $v(s_t)$ 朝着 $\bar v_t$ 改进，数学证明如下：
强化学习：时序差分算法 TD-learning

那么，TD error 是什么？两个相续时间变量的差值，这也是被叫做时序差分算法的原因，它实际反映了 $v_t$ 与 $v_π$ 之间的误差，数学证明如下：

强化学习：时序差分算法 TD-learning
如果 $v_t = v_π$ ，则 $δ_t$ 应该为零（在期望意义上）；因此，如果 $s_t$ 不为零，则 $v_t≠v_π$ 。TD error 可以解释为新息，也就是从经验 $s_t，r_{t+1}，s_{t+1})$ 中获得的新信息。
.
我们可以知道 TD算法仅估计给定策略的状态值，它不能估计动作值，也不能搜索最优策略，TD算法对于理解强化学习的核心思想至关重要。那么，TD算法从数学上做了什么？它求解给定策略 $π$ 的 Bellman 方程。

首先，我们引入一个新的贝尔曼公式，并用 RM 算法求解，如下：

强化学习：时序差分算法 TD-learning

可以发现，上述式子中RM 算法求解贝尔曼方程得到的式子与 TD 算法的式子相似，但有两个不同点值得特别注意，第一要反复采样得到集合 ${\{(s,r,s')}\}$ , $k = 1, 2, 3, \dots\dots$ ；第二，认为 $v_π(s')$ 是已知的。消除两个不同点的方法如下：1、将 ${\{(s,r,s')}\}$ 改为 ${\{(s_t，r_{t+1}，s_{t+1})}\}$ ，因为等式右边 $v_π$ 没办法很好估计，这样就只有通过一个 episode 循环迭代，即访问就更新不访问不更新。第二，用状态 $s^{'}$ 的估计值 $v_k(s')$ 取代 $v_π(s')$ 。

Saesa 算法

TD算法只能估计状态值而不能估计动作值，Sarsa算法是一种可以直接估计动作值的算法，我们来看看如何使用Sarsa来寻找最优策略。
首先，我们要估计给定策略 $π$ 下的动作值。假设我们有一些经验数据 ${\{(s_t, a_t,r_{t+1},s_{t+1},a_{t+1})}\}_t$ ，那么可以使用以下的Sarsa算法来估计动作值：
强化学习：时序差分算法 TD-learning
$q_t(s_t,a_t)$ 是对 $q_π(s_t, a_t)$ 的估计； $\alpha_t(s_t,a_t)$ 是学习率，它取决于 $s_t$ 和 $a_t$ 。

我们可以发现，Sarsa是用动作值估计 $q (s, a)$ 替换TD算法中的状态值估计 $v (s)$ ，Sarsa通过估计值函数来更新策略。因此，我们可以简单理解为 Sarsa是TD算法的动作值版本。与TD算法类似，不同之处在于，在Sarsa算法中，我们关注的是动作值函数 $q (s, a)$ ，而不是状态值函数 $v (s)$ 。Sarsa通过估计和更新动作值函数来学习最优策略。具体而言，Sarsa在每个时间步中观察到当前状态和动作，然后执行该动作并观察到奖励和下一个状态。然后，它使用新的观测值来更新动作值函数，以逐步改进对最优动作值的估计。因此，Sarsa是基于TD算法的一种变体，通过将状态值估计替换为动作值估计，使其成为一种动作值版本的TD算法。

RL的最终目标是找到最优策略。要做到这一点，我们可以将Sarsa与策略优化结合，这种组合算法也称为Sarsa。

强化学习：时序差分算法 TD-learning
这个算法在更新 $q(s_t, a_t)$ 之后，会立即更新 $s_t$ 的策略，策略更新采用 $ε - g ree d y$ 策略，以平衡利用和探索，这个核心思想是使用算法来解决给定策略的贝尔曼方程。

Expected Sarsa

强化学习：时序差分算法 TD-learning

在 Expected Sarsa 算法中，是将 Sarsa 算法的 $r_{t+1} + γq_t(s_{t+1},a_{t+1})]$ 替换成 $r_{t+1} + γE[q_t(s_{t+1},A)]$ ，其中 $γ$ 是折扣因子， $q_t(s_{t+1},a_{t+1})$ 是根据当前策略 $π$ 在下一个状态 $s_{t+1}$ 和动作 $a_{t+1}$ 的动作值估计，而在 Expected Sarsa 算法 $E[q_t(s_{t+1},A)]$ 是根据当前策略 $π$ 在下一个状态 $s_{t+1}$ 和所有可能的动作 $A$ 的动作值的期望。

换句话说，Expected Sarsa算法通过对下一个状态的所有可能动作的动作值进行期望，来计算 TD target，而不是像Sarsa算法那样只考虑下一个状态和选择的动作的动作值。这种改变使 Expected Sarsa 算法更加稳定，因为它对不同动作的期望值进行了考虑，而不仅仅是选择一个动作的值。这可以减少由于不精确的动作值估计而导致的波动性，并提供更准确的 TD target .

相对于Sarsa算法，Expected Sarsa算法需要更多的计算，因为随机变量减少了，随机变量从 $s_t, a_t,r_{t+1},s_{t+1},a_{t+1})$ 到 $s_t, a_t,r_{t+1},s_{t+1})$ ，Expected Sarsa算法考虑了所有可能的动作的期望值，它将 $a_{t+1}$ 从随机变量中移除。这样一来，估计值中的随机性减少了，因为不再依赖于选择的下一个动作的随机性。这种减少随机变量的做法有助于降低估计方差，使算法更加稳定。通过减少随机性的影响，Expected Sarsa可以提供更可靠和准确的动作值估计，从而改善学习过程。

n-step Sarsa

n-step Sarsa，是 Sarsa 与 MC 结合的算法，数学推导如下：
强化学习：时序差分算法 TD-learning

我们很容易知道 n-step Sarsa 需要的数据有 $s_t,a_t, r_{t+1},s_{t+1},a_{t+1},...,r_{t+n}, s_{t+n},a_{t+n})$ ，这样面临一个问题就是由于在时间步 $t$ 时尚未收集到 $r_{t+n}, s_{t+n}; a_{t+n})$ 的信息，我们无法在步骤 $t$ 中实现 n-step Sarsa，所以要等到时间步 $t + n$ 才来更新 $s_t, a_t)$ 的动作值.
$q_{t+n}(s_t,a_t)=q_{t+n-1}(s_t,a_t)-\alpha_{t+n-1}(s_t,a_t)[q_{t+n-1}(s_t,a_t)-[r_{t+1},γr_{t+2}+...+γ^nq_{t+n-1}(s_{t+n},a_{t+n})]]$

在n-step Sarsa算法中，我们需要等待n个时间步才能计算并更新 $s_t, a_t)$ 的动作值，通过等待 $n$ 个时间步来更新动作值，n-step Sarsa 算法能够更准确地估计动作值函数，并在学习过程中利用更长的时间序列信息。这有助于提高算法的性能和学习效果。由于n-step Sarsa包含了Sarsa和MC学习作为两种极端情况，它的性能是Sarsa和MC学习的综合体：当 $n$ 较大时，其性能接近MC学习，因此具有较大的方差但较小的偏差；当 $n$ 较小时，其性能接近Sarsa，因此由于初始猜测的存在具有相对较低的方差，相对较大的偏差。综上所述，n-step Sarsa是在Sarsa和MC学习之间取得平衡的一种方法。通过调整n的值，我们可以在偏差和方差之间进行权衡，从而获得更适合特定问题的性能表现。此外，n-step Sarsa还可以用于评估策略的价值，并与策略改进一起使用来搜索最优策略。

Q-learning

Q-learning 是最常用的强化学习算法之一，Sarsa可以估计给定策略下的动作值函数，但它必须与策略改进步骤结合使用才能找到最优策略，而 Q-learning 可以直接估计最优动作值函数，从而找到最优策略。其数学表达式如下：
强化学习：时序差分算法 TD-learning

通过上面式子我们知道 Q-learning 和 Sarsa非常相似，它们的区别仅在于 TD target 的计算方式：

Q-learning 中的 TD target 为 $r_{t+1} + γ max_{a∈A} q_t(s_{t+1}, a)$ 。
Sarsa中的 TD target 为 $r_{t+1} + γq_(s_{t+1}, a_{t+1})$ 。

在Q-learning中，TD target 采用了对下一个状态 $s_{t+1}$ 的所有可能动作 $a$ 的最大动作值函数。这意味着 Q-learning 在更新 Q 值时，考虑了在下一个状态中选择最优动作的情况。而在Sarsa中，TD target 采用了在下一个状态 $s_{t+1}$ 中根据当前策略选择的动作 $a_{t+1}$ 的动作值函数。这意味着Sarsa 在更新 Q 值时，是根据当前策略在下一个状态中选择了一个动作进行更新。因此，Q-learning 和 Sarsa在 TD target 的计算方式上有所不同，这也导致了它们在算法行为和性能上的差异。

Q-learning 在数学上求解的是一个贝尔曼最优方程：
强化学习：时序差分算法 TD-learning

在进一步学习Q学习之前，我们首先介绍两个重要的概念：on-policy 和 off-policy 。在 TD 算法中存在两种策略：

行为策略（behavior policy）：用于生成经验样本。
目标策略（target policy）：不断更新以朝向最优策略。

当行为策略与目标策略相同时，称为on-policy；当它们不同时，称为 off-policy

off-policy 可以使用其他策略生成的经验样本来搜索最优策略，行为策略可以选择为具有探索性质。例如，如果我们希望估计所有状态-动作的动作值，我们可以使用一个具有探索性质的策略生成足够多次访问每个状态-动作的轨迹。

如何判断一个TD算法是 on-policy 还是 off-policy？
首先，看算法在数学上是解决贝尔曼公式，还是是贝尔曼最优公式
其次，看实现该算法所需的条件

现在，我们来判断之前学的算法是 on-policy 还是 off-policy，第一个我们来判断Sarsa，第二个判断基于蒙特卡洛的方法，第三个判断Q-learning

Sarsa是一个on-policy算法。
首先，在数学上 Sarsa 是在求解给定策略 $π$ 的贝尔曼方程：
强化学习：时序差分算法 TD-learning

其次，看实现 Sarsa 算法所需的变量条件：
强化学习：时序差分算法 TD-learning
Sarsa 算法中，如果给定了 $s_t,a_t)$ ，那么 $r_{t+1}$ 和 $s_{t+1}$ 并不依赖于任何策略， $a_{t+1}$ 是遵循策略 $π_t(s_{t+1})$ 生成的，可以知道策略 $π_t$ 既是目标策略又是行为策略。
.