OMSCS-RL课程笔记04-Convergence

这个系列是Gatech OMSCS 强化学习课程(CS 7642: Reinforcement Learning)的同步课程笔记。课程内容涉及强化学习算法的理论和相关应用，本节讨论TD learning的收敛性。

Bellman Equations with Actions

对于不考虑智能体决策行为的情况，Bellman方程给出了价值函数的递归关系：

V (s) = R (s) + γ \sum_{s^{'}} T (s, s^{'}) V (s^{'})

而TD(0)则给出了价值函数的在线估计方法：

V_{t} (s_{t - 1}) = V_{t - 1} (s_{t - 1}) + α_{t} [r_{t} + γ V_{t - 1} (s_{t}) - V_{t - 1} (s_{t - 1})]

我们把TD(0)的思路拓展到需要进行决策的情况，可以得到Q-learning算法：

Q (s, a) = R (s, a) + γ \cdot \sum_{s^{'}} T (s, a, s^{'}) max_{a^{'}} Q (s^{'}, a^{'})

Q_{t} (s_{t - 1}, a_{t - 1}) = Q_{t - 1} (s_{t - 1}, a_{t - 1}) + α_{t} [r_{t} + γ \cdot max_{a^{'}} Q_{t - 1} (s_{t}, a^{'}) - Q_{t - 1} (s_{t - 1}, a_{t - 1})]

实际上我们可以使用算子的角度来认识Bellman方程。我们定义Bellman算子 $B$ 是一个价值函数到价值函数的映射：

[B Q] (s, a) = R (s, a) + γ \cdot \sum_{s^{'}} T (s, a, s^{'}) max_{a^{'}} Q (s^{'}, a^{'})

利用Bellman算子，我们可以重写Bellman方程和TD(0)更新：

Q^{*} = B Q^{*}

Q_{t} = B Q_{t - 1}

Bellman算子的一个重要性质是它是一个压缩映射(contraction mapping)。所谓压缩映射是指对于任意函数 $F$ 和 $G$ ，存在 $0 \leq γ < 1$ 使得对于算子 $B$ 满足：

‖ B F - B G ‖_{\infty} \leq γ ‖ F - G ‖_{\infty}

直观理解，压缩映射会不断减少两个函数之间的距离。压缩映射有很多有用的性质，比如说对于压缩映射 $B$ 一定存在一个唯一的函数 $F^{*}$ 满足方程：

B F^{*} = F^{*}

同时，我们可以从任意函数 $F$ 开始利用 $B$ 进行迭代，最终一定能收敛到 $F^{*}$ 上：

F_{t} = B F_{t - 1} \Rightarrow F_{t} \to F^{*}

容易验证Bellman算子满足压缩映射的定义：

\begin{aligned} ‖ B Q_{1} - B Q_{2} ‖_{\infty} & = max_{s, a} | γ \sum_{s^{'}} T (s, a, s^{'}) [max_{a^{'}} Q_{1} (s^{'}, a^{'}) - max_{a^{'}} Q_{2} (s^{'}, a^{'})] | \\ \leq γ max_{s^{'}} | max_{a^{'}} Q_{1} (s^{'}, a^{'}) - max_{a^{'}} Q_{2} (s^{'}, a^{'}) | \\ \leq γ ‖ Q_{1} - Q_{2} ‖_{\infty} \end{aligned}

Bellman算子作为一个压缩映射的直接推论是证明价值迭代算法的正确性。实际上存在如下定理保证了使用Bellman算子进行迭代的价值函数一定可以收敛到最优价值函数：

更进一步，我们可以证明TD learning算法能够收敛到最优价值函数：

除此之外，我们还可以对MDP以及Bellman方程的概念进行推广：