OMSCS-RL课程笔记05-AAA

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

Value Iteration

价值迭代(value iteration, VI)是我们介绍的第一个强化学习算法。可以证明使用策略迭代算法总是可以在多项式时间内寻找到最优策略：

另一种求解MDP的方法是使用线性规划(linear programming)。根据Bellman方程，价值函数的递归形式为：

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

显然Bellman方程不是一个线性方程，不过我们可以利用 $max$ 运算的性质把它转换为一个线性方程。具体来说可以把上式等价地表示为一个约束优化问题：

\begin{aligned} min & \sum_{s} V (s) \\ s.t. V (s) & \geq R (s, a) + γ \cdot \sum_{s^{'}} T (s, a, s^{'}) V (s^{'}) \end{aligned}

这样求解Bellman方程就转换为了一个线性规划问题。此外我们还可以利用对偶性转而求解原始问题的对偶问题：

\begin{aligned} max & \sum_{s} \sum_{a} q_{s, a} R (s, a) \\ s.t. & 1 + γ \sum_{s} \sum_{a} q_{s, a} T (s, a, s^{'}) = \sum_{a} q_{s^{'}, a}, \forall s^{'} \\ q_{s, a} \geq 0 \end{aligned}

策略迭代(policy iteration, PI)也是一种常用的求解MDP的算法。与VI不同的是，在每次迭代中PI会先更新当前的策略，然后利用新的策略再更新价值函数：

为了比较学习到的策略，我们需要引入一些相关的数学概念：

在此基础上则可以证明PI的收敛性：