原理

思想和动机

在 Markov 决策过程中，我们定义了状态价值函数 Q(s, a) 为：

Q(s, a) = \mathbb{E}(G_t \, | \, S_t = s, A_t = a),

当状态空间和动作空间都有限时，我们可以使用一个表格估计状态价值函数的值，称为 Q 表（Q table）。在学习算法中，Q 表实际上记录的是状态价值的估计值，我们将反复更新 Q 表直到算法收敛。

思路 1：统计量的估计

对于前 n 个数的均值 \bar{x}_n，我们可以使用增量式更新，即

\begin{aligned} \bar{x}_{n} &= \frac{x_1 + \cdots + x_{n - 1} + x_n}{n} \\ &= \frac{(n - 1) \bar{x}_{n - 1} + x_n}{n} \\ &= \bar{x}_{n - 1} + \frac{1}{n} (x_n - \bar{x}_{n - 1}). \end{aligned}

或者写为

\Delta \bar{x}_{n} = \bar{x}_n - \bar{x}_{n - 1} = \frac{1}{n} (x_n - \bar{x}_{n - 1}).

这对应编程中的增量赋值运算符 +=。

根据状态价值函数 Q(s, a) 的定义，我们可以让智能体反复地在环境中进行探索，得到许多轨迹。取出 n 个当状态为 s、动作为 a 下的回报 g_{t_1}^{(1)}, \dots, g_{t_n}^{(n)}，可以做出如下估计：

\hat{Q}(s, a) = \frac{g_{t_1}^{(1)} + \cdots + g_{t_n}^{(n)}}{n}.

换成增量式更新，则为

\Delta \hat{Q}(s, a) = \frac{1}{n}\left[g_t - \hat{Q}(s, a)\right].

其中，当 t \neq T 时，第 t 步的回报为 g_t 可以递归地表示为：

\begin{aligned} g_t &= r_t + \gamma r_{t + 1} + \gamma^2 r_{t+2} + \cdots \\ &= r_t + \gamma (r_{t+1} + \gamma r_{t + 2} + \cdots) \\ &= r_t + \gamma g_{t + 1}. \end{aligned}

于是更新为

\Delta \hat{Q}(s, a) = \frac{1}{n}\left[r_t + \gamma g_{t+1} - \hat{Q}(s, a)\right].

为了使上述公式不依赖于未来的收益，我们再近似地认为 g_{t + 1} \approx \max_{a'} \hat{Q}(s', a')，其中 s' 表示智能体在状态 s 执行动作 a 后下一次转移到的状态。再使用一个常数 \alpha 代替和步数有关的 \frac{1}{n}，最终就得到公式：

\Delta \hat{Q}(s, a) = \alpha\left[r_t + \gamma \max_{a'} \hat{Q}(s', a') - \hat{Q}(s, a)\right].

这个公式就是 Q-Learning 的 Q 表参数更新公式。

提示

上式中 r_t + \gamma \max_{a'} \hat{Q}(s', a') - \hat{Q}(s, a) 也称为 TD 误差，其中 TD 是时序差分（temporal difference）的缩写。Q-Learning 根据 TD 误差更新了表格中的参数。

思路 2：价值迭代

在 Markov 决策过程和 RL 动态规划中，我们可以了解以下的数学直觉：

一个策略满足 Bellman 最优方程时，它就是最优策略；如果一个策略下 Bellman 方程近似成立，则这是一个很好的策略。策略越靠近 Bellman 方程，则策略越好。
直接进行动态规划需要知道精确的状态转移 p(s' | s, a)，而一般情况下我们并不知道这个函数，只能对其采样。

如果我们使用 DP 进行动作价值的迭代，则由 Bellman 最优方程，迭代公式为：

Q_{k + 1}(s, a) \leftarrow r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s' | s, a) \max_{a' \in \mathcal{A}} Q_k (s', a').

上式的右边中，p(s' | s, a) 未知，但可以注意到

\sum_{s' \in \mathcal{S}} p(s' | s, a) \max_{a' \in \mathcal{A}} Q_k(s', a')

是一个加权平均，是 S_t = s, A_t = a 条件下 \max_{a' \in \mathcal{A}} Q_k(S_{t + 1}, a') 的数学期望。既然是数学期望，我们可以直接采样一个点 (s, a, r, s')，用这个点作为这个期望的容量为 1 的点估计：

Q_{k + 1}(s, a) = r(s, a) + \gamma \max_{a' \in \mathcal{A}} Q_k(s', a').

单样本估计虽然是无偏的，但方差波动非常大，所以我们改用指数移动平均（EMA）的方法来更新 Q 的预测值：

Q_{k + 1}(s, a) = Q_k(s, a) + \alpha \left[ r(s, a) + \gamma \max_{a' \in \mathcal{A}} Q_k(s', a') - Q_k(s, a) \right].

这从另一个角度导出了 Q 表的更新公式，并且更能解释最大值的意义。

算法过程

伪代码如下：

初始化 Q 表
for epoch:
    初始化状态 s
    结束状态 done = false
    while not done:
        由 epsilon greedy 得到动作 a
        r, s', done = step(s, a) # 与环境交互得到奖励和下一个状态
        a' = argmax Q[s, :]
        Q[s, a] += alpha * (r + gamma * Q[s', a'] - Q[s, a])
        s = s'

原理

思想和动机

思路 1：统计量的估计

思路 2：价值迭代

算法过程

读完了，有什么想法？

继续阅读