本文收录在无痛的机器学习第二季目录。
从最优策略求解回报
求解回报的目标函数
在上一节反向增强学习入门1——基本概念，我们介绍了反向强化学习的基本概念，也介绍了它和强化学习的区别。对于一个强化学习的问题，如果状态和行动空间已知，状态转移概率确定，对于强化学习来，它是要通过回报函数求出最优策略；而对于反向强化学习来说，则通过最优策略或最优策略的行动采样，求出回报函数。本节将介绍反向强化学习中最简单的问题：已知最优策略，求回报函数。
如果我们已知了状态和行动空间、状态转移概率和最优策略 ，且状态和行动的空间都是离散的，那么我们该如何求解呢？读者初看这个问题，可能会觉得有点复杂。为了循序渐进地了解算法，我们首先会对问题做一定的限制，并给出解答，然后一步步地放开这些限制，看看求解方法该如何扩展。我们首先考虑表格式的策略与价值函数，这样每一个状态下的行动和表格中的一个值有关。根据最优策略的定义我们知道，最优策略和其他策略相比，对于每一个状态，其对应的价值函数都不弱于其他策略的价值函数。由此可以得到：
\pmb V_{\pi^*}(s) \geqslant \pmb V_{\pi}(s)
q_{\pi^*}(s,a) \geqslant q_{\pi}(s,a)
如果我们令S为所有的状态集合，A为所有的行动集合，那么对于任意的状态，我们可以得到：
\forall s \in \pmb S, q_{\pi^*}(s,\pi^*(s)) \geqslant q_{\pi}(s, \pi(s))
如果是看一步行动，我们知道最优策略的每一步行动都应该不弱于其他策略的行动，那么可以得到对于任意的状态，完全使用最优策略的价值，应该弱于"在当前时刻使用最优策略外的行动，此后使用最优策略进行决策"的价值。这个条件可以通过反证法得到，如果这一条件不能满足，那么实际上最优策略就不是最优了。上面的条件可以写作：
\forall s \in \pmb S,a \in \pmb A - \pi^*(s), \text{ } q_{\pi^*}(s,\pi^*(s)) \geqslant q_{\pi^*}(s, a)
我们可以利用Bellman公式将上面的不等式展开，可以得到：
\forall s \in \pmb S, a \in \pmb A - \pi^*(s), \text{ }\sum_{s'}\pmb P(s'|s,\pi^*(s)) \pmb V_{\pi^*}(s') \geqslant \sum_{s'}\pmb P(s'|s,a)\pmb V_{\pi^*}(s')
如果用列向量 \pmb P_{s,a} 表示由 \pmb P(s'|s,\pi^*(s)) 组成的向量，用列向量 \pmb V 表示由 \pmb V_{\pi^*}(s') 组成的向量，那么公式就可以变成：
\pmb P_{s,\pi^*(s)}\pmb V \geqslant \pmb P_{s,a}\pmb V
这个公式里面的价值函数V是未知的，但好在我们可以用Bellman公式进行求解：
\pmb V_{\pi^*}(s)=\sum_a \pmb P(a|s) \sum_{s'}\pmb P(s'|s,a)[\pmb R(s)+\gamma \pmb V_{\pi^*}(s')]
将这个公式转成矩阵和向量计算的形式，用 \pi 表示行动概率向量 \pmb P(a|s) ，就可以得到：
\pmb V=\pmb R+\pi \pmb P(\gamma \pmb V)
由于我们在考虑表格式策略的价值函数，所以策略是相对固定的，公式可以进一步化简为：
\pmb V=\pmb R+\pmb P_{:,\pi^*}(\gamma \pmb V)
当价值函数收敛时，公式中的两个价值向量是相等的，于是公式可以整理为关于价值向量的形式：
\pmb V=(\pmb I-\gamma \pmb P_{\pi^*})^{-1}\pmb R
把这个公式带回前面的不等式中，求得到了我们初步的目标函数：
\mathrm{max}(\pmb P_{s,\pi^*(s)} -\pmb P_{s,a})(\pmb I-\gamma \pmb P_{\pi^*})\pmb R
s.t. (\pmb P_{s,\pi^*(s)} -\pmb P_{s,a})(\pmb I-\gamma \pmb P_{\pi^*})\pmb R \geqslant 0
于是这个问题变成了一个线性规划问题，我们要找到合适的回报向量满足这个不等式。经过上面的推导，我们终于完成问题定义的第一步，通过最优策略的定义和Bellman公式，我们将其表达出来。
14.2.2 目标函数的约束
上面的目标函数虽然向我们清晰地阐述了求解的思路，但是由于这个目标只是一个不等式，对待求的回报向量来说，这个约束有点弱，因为我们显然可以找出很多种不同的回报函数组合可以满足这个不等式，其中还有一些是平凡解，例如全部为0回报函数，这样的解同样可以满足不等式，但是实际上它是没有意义的。于是我们需要思考如何增强问题的约束。
我们将为目标函数增强两个约束：1）限制回报的范围；2）只考虑最优策略和次优策略的差异。
首先是限制回报的范围。由于这是一个线性规划问题，回报向量可以在成比例扩大的同时满足约束条件，因此我们应该对回报数值的上界做一定的限制，于是就有了这样的约束：
|\pmb R| \leqslant \pmb R_{\mathrm{max}}
这种增加约束的方法在机器学习中普遍存在，这和L1、L2正则的功能比较相似，都是为了防止参数太大。由于这种方法在机器学习的很多算法上都得到了不错的效果，在这里的效果应该也不会差。
其次就是考虑最优策略的比较对象。在前面的目标不等式中，我们需要最优策略强于所有的策略，这个约束并没有错误。但是在实际中，如果我们以相同的权重考量其他策略和最优策略的差距，就显得不那么合理了。实际上最优策略和次优策略的价值差会显得更为重要，而最优策略和其他很差的策略的价值差并没有那么重要，所以实际上最优策略只要尽可能地比次优策略强就可以了，和其他的策略进行比较并不应该拥有很高的权重。
为了解释价值差异的权重问题，我们可以以一个棋类AI的表现为例。假设有两个策略，分别为A和B，它们分别和普通玩家和高级玩家进行对弈，最终的战绩如下表所示。
普通玩家高级玩家总得分A20020B224
这里的分数表示了两者的差距，分数为正表示AI最终胜利。可以看出，策略A获得了更高的分数，但是却和高级玩家打平；而策略B的总得分虽然不及策略A，但是它获得了两场胜利，这说明策略B与策略A相比，更像一个最优策略，即使它并不能从普通玩家手上获得太多的分数。
根据上面的分析，我们可以将目标函数改变为：
\mathrm{max}_R [\mathrm{min}_a\{(\pmb P_{s,\pi^*(s)} -\pmb P_{s,a})(\pmb I-\gamma \pmb P_{\pi^*})^{-1}\pmb R\}]
从公式中可以看出，我们先选出与最优策略差距最小的策略（内层的min运算），再通过求解Reward让最优策略与它的差距变大。这样Reward的求解就变得更明确了。
将两个约束加入原问题，此时完整的问题就变成了：
\mathrm{max}_R [\mathrm{min}_a\{(\pmb P_{s,\pi^*(s)} -\pmb P_{s,a})(\pmb I-\gamma \pmb P_{\pi^*})^{-1}\pmb R\} - \lambda|\pmb R|]
s.t.
-(\pmb P_{s,\pi^*(s)} -\pmb P_{s,a})(\pmb I-\gamma \pmb P_{\pi^*})\pmb R \leqslant 0
|\pmb R| \leqslant \pmb R_{\mathrm{max}}
这样我们就得到了这个问题的完整目标，下一节我们来看看这个问题的具体求解方式。
私货时间
《强化学习精要：核心算法与TensorFlow实现》(冯超)
深入浅出介绍强化学习框架概念与实践，欢迎了解！
