DQN原理

Posted on Edited on In Valine:

详细讲解一下DQN算法的原理

QTABLE

什么是 Q 表（Q-Table）？

在强化学习中，Q 表 是一种表格形式的数据结构，用于存储每个状态和动作对的 Q 值（即动作值函数）。Q 值表示在某个状态下采取某个动作后，能够获得的预期累积奖励。

定义

  • Q(s, a): 表示在状态 \(s\) 下执行动作 \(a\) 后，智能体在未来可以获得的期望累积奖励。
  • Q 表是一个二维表格，行表示状态 \(s\)，列表示动作 \(a\)，表中的每个元素存储的是对应的 Q 值。

例如，在一个简单的网格世界环境中： - 状态 \(s\) 可能是智能体所在的网格位置（如 (0, 0), (0, 1) 等）。 - 动作 \(a\) 可能是上、下、左、右四个方向的移动。 - Q 表的形式可能如下：

状态 \(s\) 动作 \(a = \text{上}\) 动作 \(a = \text{下}\) 动作 \(a = \text{左}\) 动作 \(a = \text{右}\)
(0, 0) 0.5 0.3 0.2 0.4
(0, 1) 0.6 0.7 0.1 0.8

在这个表格中，每个单元格的值就是对应的 Q 值，表示在某个状态下采取某个动作后的预期累积奖励。

Q 表的作用

Q 表的核心作用是帮助智能体选择最优的动作。通过 Q 表，智能体可以找到在每个状态下能够最大化未来奖励的动作。

  • 在给定状态下 \(s\)，智能体可以通过以下方式选择动作：
    • 贪心策略（Greedy Policy）: 选择具有最大 Q 值的动作： \[ a^* = \arg\max_a Q(s, a) \]
  • ε-greedy 策略: 以概率 \(1-\epsilon\) 选择贪心动作，以概率 \(\epsilon\) 随机选择动作（用于探索）。

Q 表的迭代更新

Q 表的更新是基于 Q-Learning 或 SARSA 等算法完成的。这些算法利用 Bellman 方程来逐步优化 Q 值，直到收敛到最优 Q 值。

Q-Learning 的更新公式

Q-Learning 是一种离策略（off-policy）算法，其核心思想是通过 Bellman 最优方程来更新 Q 值。更新公式如下： \[ Q(s, a) \leftarrow Q(s, a) + \alpha \cdot \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right] \] 其中： - \(Q(s, a)\): 当前状态 \(s\) 和动作 \(a\) 的 Q 值。 - \(\alpha\): 学习率（learning rate），控制更新步长。 - \(r\): 执行动作 \(a\) 后获得的即时奖励。 - \(\gamma\): 折扣因子（discount factor），用于权衡当前奖励和未来奖励的重要性。 - \(s'\): 执行动作 \(a\) 后转移到的下一个状态。 - \(\max_{a'} Q(s', a')\): 在下一个状态 \(s'\) 中，所有可能动作的最大 Q 值。

更新过程解释

  1. 初始化 Q 表:
    • 初始时，Q 表中的所有值通常设为 0 或其他小的随机值。
  2. 采样经验:
    • 智能体与环境交互，获得一个四元组 \((s, a, r, s')\)，表示从状态 \(s\) 执行动作 \(a\) 后获得奖励 \(r\) 并转移到状态 \(s'\)。
  3. 计算目标值:
    • 目标值（Target Value）是根据 Bellman 方程计算的： \[ \text{Target} = r + \gamma \max_{a'} Q(s', a') \]
  • 这个目标值表示在当前策略下，从状态 \(s\) 执行动作 \(a\) 后的预期累积奖励。
  1. 更新 Q 值:
    • 使用目标值更新当前的 Q 值： \[ Q(s, a) \leftarrow Q(s, a) + \alpha \cdot \left[ \text{Target} - Q(s, a) \right] \]
  • 这里的 \(\text{Target} - Q(s, a)\) 称为 TD 误差（Temporal Difference Error），表示当前估计值与目标值之间的差距。
  1. 重复迭代:
    • 不断重复上述步骤，直到 Q 表收敛（即 Q 值的变化小于某个阈值）。

SARSA 的更新公式

SARSA 是一种在策略（on-policy）算法，其更新公式与 Q-Learning 类似，但目标值有所不同： \[ Q(s, a) \leftarrow Q(s, a) + \alpha \cdot \left[ r + \gamma Q(s', a') - Q(s, a) \right] \] 区别在于： - 在 Q-Learning 中，目标值使用的是下一个状态 \(s'\) 中的最大 Q 值 \(\max_{a'} Q(s', a')\)。 - 在 SARSA 中，目标值使用的是在策略下实际采取的动作 \(a'\) 的 Q 值 \(Q(s', a')\)。

因此，SARSA 的更新依赖于当前策略（即 ε-greedy 策略），而 Q-Learning 的更新则不依赖于当前策略。

Q 表的优点和缺点

优点

  1. 简单易懂:
    • Q 表是一种直观的方法，特别适合小规模的状态空间和动作空间。
  2. 易于实现:
    • 只需要维护一个二维表格即可。
  3. 保证收敛:
    • 在有限状态和动作空间的情况下，Q-Learning 和 SARSA 都能保证收敛到最优策略。

缺点

  1. 维度灾难:
    • 当状态空间和动作空间较大时，Q 表会变得非常庞大，难以存储和更新。
    • 例如，在连续状态空间中，Q 表无法直接应用。
  2. 适用性有限:
    • 对于复杂环境（如 Atari 游戏或机器人控制任务），Q 表无法扩展，需要使用函数逼近方法（如深度 Q 网络 DQN）。

示例：Q 表更新过程

假设我们有一个简单的 Grid World 环境，状态空间为 \(\{(0, 0), (0, 1), (1, 0), (1, 1)\}\)，动作空间为 \(\{\text{上}, \text{下}, \text{左}, \text{右}\}\)。

初始化 Q 表

初始 Q 表为全零矩阵： | 状态 \(s\) | 动作 \(a = \text{上}\) | 动作 \(a = \text{下}\) | 动作 \(a = \text{左}\) | 动作 \(a = \text{右}\) | | -------- | -------------------- | -------------------- | -------------------- | -------------------- | | (0, 0) | 0 | 0 | 0 | 0 | | (0, 1) | 0 | 0 | 0 | 0 |

更新 Q 表

  1. 智能体从状态 \((0, 0)\) 执行动作“右”，转移到状态 \((0, 1)\)，获得奖励 \(r = 1\)。
  2. 计算目标值： \[ \text{Target} = r + \gamma \max_{a'} Q(s', a') = 1 + 0.9 \cdot \max(0, 0, 0, 0) = 1 \]
  3. 更新 Q 值： \[ Q((0, 0), \text{右}) \leftarrow 0 + 0.1 \cdot (1 - 0) = 0.1 \] 更新后的 Q 表： | 状态 \(s\) | 动作 \(a = \text{上}\) | 动作 \(a = \text{下}\) | 动作 \(a = \text{左}\) | 动作 \(a = \text{右}\) | | -------- | -------------------- | -------------------- | -------------------- | -------------------- | | (0, 0) | 0 | 0 | 0 | 0.1 | | (0, 1) | 0 | 0 | 0 | 0 |

总结

Q 表是一种简单而有效的强化学习工具，适用于小规模状态空间和动作空间。通过不断迭代更新 Q 值，智能体可以逐步学习到最优策略。然而，对于大规模或连续状态空间，Q 表的扩展性较差，需要结合函数逼近方法（如 DQN）来解决实际问题。

SARSA 的更新公式

SARSA 是一种在策略（on-policy）的强化学习算法，其更新公式如下： \[ Q(s, a) \leftarrow Q(s, a) + \alpha \cdot \left[ r + \gamma Q(s', a') - Q(s, a) \right] \] 其中： - \(Q(s, a)\): 当前状态 \(s\) 和动作 \(a\) 的 Q 值。 - \(\alpha\): 学习率（learning rate），控制更新步长。 - \(r\): 执行动作 \(a\) 后获得的即时奖励。 - \(\gamma\): 折扣因子（discount factor），用于权衡当前奖励和未来奖励的重要性。 - \(s'\): 执行动作 \(a\) 后转移到的下一个状态。 - \(a'\): 在下一个状态 \(s'\) 中根据当前策略选择的动作。

SARSA 的核心思想

SARSA 的名字来源于它的更新过程涉及五元组：(S, A, R, S', A')。具体来说： 1. S: 当前状态 \(s\)。 2. A: 当前动作 \(a\)。 3. R: 执行动作 \(a\) 后获得的奖励 \(r\)。 4. S': 转移到的下一个状态 \(s'\)。 5. A': 在状态 \(s'\) 下根据当前策略选择的动作 \(a'\)。

SARSA 的特点是它使用当前策略来选择动作 \(a'\)，因此是一种在策略算法。

举例讲解

假设我们有一个简单的 Grid World 环境，智能体可以在网格中移动（上、下、左、右）。目标是让智能体从起点到达终点，并最大化累积奖励。

环境描述

  • 状态空间：\(s \in \{(0, 0), (0, 1), (1, 0), (1, 1)\}\)。
  • 动作空间：\(a \in \{\text{上}, \text{下}, \text{左}, \text{右}\}\)。
  • 奖励函数：每一步奖励为 \(-1\)（鼓励尽快到达终点）。
  • 终点：状态 \((1, 1)\) 是终点，进入后奖励为 \(+10\) 并终止。

初始化 Q 表

初始 Q 表为全零矩阵： | 状态 \(s\) | 动作 \(a = \text{上}\) | 动作 \(a = \text{下}\) | 动作 \(a = \text{左}\) | 动作 \(a = \text{右}\) | | -------- | -------------------- | -------------------- | -------------------- | -------------------- | | (0, 0) | 0 | 0 | 0 | 0 | | (0, 1) | 0 | 0 | 0 | 0 | | (1, 0) | 0 | 0 | 0 | 0 | | (1, 1) | 0 | 0 | 0 | 0 |

参数设置

  • 学习率 \(\alpha = 0.1\)。
  • 折扣因子 \(\gamma = 0.9\)。
  • 策略：ε-greedy 策略，\(\epsilon = 0.1\)（即 10% 的概率随机选择动作，90% 的概率选择贪心动作）。

更新过程示例

第一步

  1. 当前状态:
    • 智能体初始状态为 \(s = (0, 0)\)。
  2. 选择动作:
    • 根据 ε-greedy 策略，假设智能体选择了动作 \(a = \text{右}\)。
  3. 执行动作:
    • 执行动作 \(a = \text{右}\)，转移到状态 \(s' = (0, 1)\)，获得奖励 \(r = -1\)。
  4. 选择下一动作:
    • 根据 ε-greedy 策略，假设智能体在状态 \(s' = (0, 1)\) 下选择了动作 \(a' = \text{下}\)。
  5. 计算目标值: \[ \text{Target} = r + \gamma Q(s', a') = -1 + 0.9 \cdot Q((0, 1), \text{下}) = -1 + 0.9 \cdot 0 = -1 \]
  6. 更新 Q 值: \[ Q((0, 0), \text{右}) \leftarrow Q((0, 0), \text{右}) + \alpha \cdot (\text{Target} - Q((0, 0), \text{右})) \]

\[ Q((0, 0), \text{右}) \leftarrow 0 + 0.1 \cdot (-1 - 0) = -0.1 \] 更新后的 Q 表： | 状态 \(s\) | 动作 \(a = \text{上}\) | 动作 \(a = \text{下}\) | 动作 \(a = \text{左}\) | 动作 \(a = \text{右}\) | | -------- | -------------------- | -------------------- | -------------------- | -------------------- | | (0, 0) | 0 | 0 | 0 | -0.1 | | (0, 1) | 0 | 0 | 0 | 0 | | (1, 0) | 0 | 0 | 0 | 0 | | (1, 1) | 0 | 0 | 0 | 0 |

第二步

  1. 当前状态:
    • 智能体当前状态为 \(s = (0, 1)\)。
  2. 选择动作:
    • 根据 ε-greedy 策略，假设智能体选择了动作 \(a = \text{下}\)。
  3. 执行动作:
    • 执行动作 \(a = \text{下}\)，转移到状态 \(s' = (1, 1)\)，获得奖励 \(r = 10\)（因为到达终点）。
  4. 选择下一动作:
    • 因为 \(s' = (1, 1)\) 是终点，没有后续动作，设 \(a' = \text{无}\)。
  5. 计算目标值: \[ \text{Target} = r + \gamma Q(s', a') = 10 + 0.9 \cdot 0 = 10 \]
  6. 更新 Q 值: \[ Q((0, 1), \text{下}) \leftarrow Q((0, 1), \text{下}) + \alpha \cdot (\text{Target} - Q((0, 1), \text{下})) \]

\[ Q((0, 1), \text{下}) \leftarrow 0 + 0.1 \cdot (10 - 0) = 1.0 \] 更新后的 Q 表： | 状态 \(s\) | 动作 \(a = \text{上}\) | 动作 \(a = \text{下}\) | 动作 \(a = \text{左}\) | 动作 \(a = \text{右}\) | | -------- | -------------------- | -------------------- | -------------------- | -------------------- | | (0, 0) | 0 | 0 | 0 | -0.1 | | (0, 1) | 0 | 1.0 | 0 | 0 | | (1, 0) | 0 | 0 | 0 | 0 | | (1, 1) | 0 | 0 | 0 | 0 |

总结

通过上述两步更新，我们可以看到 SARSA 的更新过程是如何工作的： 1. SARSA 的特点: - 使用当前策略选择的动作 \(a'\) 来更新 Q 值，因此是一种在策略算法。 - 与 Q-Learning 不同，SARSA 的目标值依赖于实际采取的动作，而不是最大 Q 值。 2. 收敛性: - 随着迭代次数的增加，Q 表会逐渐收敛到最优值，智能体能够找到一条从起点到终点的最优路径。 3. 适用场景: - SARSA 更适合动态环境或需要考虑探索的场景，因为它始终基于当前策略进行更新。

希望这个例子能帮助你更好地理解 SARSA 的更新公式！如果有进一步的问题，请随时提问。