我正在用C++实现一个SARSA(lambda)模型，以克服动态规划（DP）模型的一些限制（DP模型需要大量的时间和空间）。希望这能减少计算时间（目前类似研究需要几个小时）和所需空间，从而使模型能够增加更多的复杂性。

我们确实有明确的转移概率，这些概率确实会产生影响。那么，我们应该如何在SARSA模型中加入这些概率呢？

只是根据概率本身来选择下一个状态吗？显然，SARSA模型并不完全期望你使用概率——或许是我读错了书。

PS- 有没有办法知道算法是否正确实现了？这是我第一次使用SARSA。

回答：

动态规划（DP）和强化学习（RL）之间的根本区别在于，前者假设环境的动态是已知的（即一个模型），而后者可以直接从过程获得的数据中学习，这些数据可以是一组样本、一组过程轨迹或单一轨迹。由于这一特性，当构建模型困难或成本高时，RL方法非常有用。然而，应该注意的是，这两种方法共享相同的工作原理（在Sutton的书中称为广义策略迭代）。

由于它们相似，这两种方法也共享一些限制，即维度灾难。根据Busoniu的书（第三章是免费的，可能对你的目的有用）：

DP和RL领域的一个核心挑战是，在它们原始形式（即表格形式）下，DP和RL算法无法用于一般问题。它们只能在状态和动作空间由有限数量的离散元素组成时实现，因为（除其他原因外）它们需要精确表示价值函数或策略，这对于具有无限数量元素的状态空间通常是不可能的（或者当状态数量非常高时成本太高）。

即使状态和动作取有限多个值，表示价值函数和策略的成本也会随着状态变量（以及Q函数的动作变量）的数量呈指数增长。这个问题被称为维度灾难，使得经典的DP和RL算法在有许多状态和动作变量时变得不实用。为了应对这些问题，必须使用近似表示价值函数和/或策略的经典算法版本。由于大多数实际问题具有大或连续的状态和动作空间，近似在DP和RL中是必不可少的。

在你的情况下，似乎很明显你应该采用某种函数近似。然而，鉴于你知道转移概率矩阵，你可以选择基于DP或RL的方法。在RL的情况下，转换只是用来根据动作计算下一个状态。

使用DP还是RL更好？实际上我不知道答案，最佳方法可能取决于你的具体问题。从直觉上看，以计划的方式采样一组状态（DP）似乎更安全，但也许你的状态空间中有很大一部分与找到最优策略无关。在这种情况下，采样一组轨迹（RL）在计算上可能更有效。无论如何，如果这两种方法都正确应用，应该能达到相似的解决方案。

注意：在使用函数近似时，收敛特性更加脆弱，在迭代过程中发散并不罕见，特别是当近似器是非线性的（如人工神经网络）与RL结合时。