Policy invariance under reward transformations: Theory and application to reward shaping

这篇文章是奖励塑造的重要理论基础，对奖励函数的设计具有指导作用，作者有吴恩达，地址http://luthuli.cs.uiuc.edu/~daf/courses/games/AIpapers/ng99policy.pdf

主要内容：

奖励塑造是强化学习中常用的人为设计附加的奖励来指导智能体训练的方法，但是一些问题中人为设计的奖励函数常常导致智能体学习到非最优的策略。

文章主要研究保证reward shaping最优策略不变的条件，结论是当附加奖励值可以表示为任意一个状态的势函数（Potential-based functino，势函数被定义为状态到实数的映射 $\phi: S \rightarrow R$ϕ:S→R ）的差分形式的时候，能保证最优策略不变。

文章最后设计了基于距离和基于子目标的启发式奖励函数，并实验证明了其对缩减训练时间有很大作用。

两个典型问题：

（1）自动车从A到B的问题，当智能体向B走就给予正奖励，其余奖励0，可能会导致智能体学到在A附近“兜圈”的策略，原因是智能体远离B没有给予负奖励，当智能体“兜圈”时，凭借靠近B的部分就能持续获得奖励；
（2）为了学会足球控球，当智能体碰到球就给予正奖励，可能导致智能体学习到在球附近“震荡”，快速靠近球然后远离再靠近，这样智能体也能持续不断获得奖励。

从问题（1）我们可以知道，如果智能体远离目标给予负奖励的话，就不会出现这个问题。联想到**物理知识中势能的概念**，当物体运动回到原位置时势能不变，于是引出了势函数（Potential-based function）的概念——势函数被定义为状态到实数的映射 $\phi: S \rightarrow R$ϕ:S→R。同理当物体运动回原位置时势函数值不变，那么运动中的奖励函数就可以表示为势函数的差分形式，保证累积奖励值不变。

理论证明

首先需要知道强化学习中一些基本概念的含义，比如MDP五元组（S，A，R，P， $\gamma$γ）、值函数、策略，以及在强化学习中五元组一旦确定，最优策略就确定了（确定但不唯一）。记原MDP问题为M，新的MDP问题为M‘，可以通过M的奖励值加上附加奖励函数的值得到M’的奖励值。
本文主要证明了，附加值函数表示为势函数的差分形式 $F(s,a,s')=\gamma \Phi(s') - \Phi(s)$F(s,a,s′)=γΦ(s′)−Φ(s)时，是最优策略不变的充分必要条件，其中必要性是在不了解状态转移概率矩阵和原奖励函数的基础上，证明在附录，我在这里不介绍。充分性证明：

根据贝尔曼方程，最优值函数具有如下形式：

两边减去势能函数，作简单变换有：

引入新的变量做替换，后面将证明新引入的变量也是值函数：

然后根据 $F(s,a,s')=\gamma \Phi(s') - \Phi(s)$F(s,a,s′)=γΦ(s′)−Φ(s)，得到：

也就是新的变量 $\hat Q$Q^​就是M‘的动作值函数。
当达到M‘的最优策略时，满足如下等式：

注意上式第二行到第三行成立是因为势能函数只跟状态s有关，对同一状态下选择动作没影响，因此不影响最优策略。也就是说，M‘下的最优策略和M的相同，充分性得证。

两个推论

1. 鲁棒性：注意到不仅对贝尔曼最优方程有以上结论，对贝尔曼方程同样有类似的结论，也就是当策略接近最优策略时，值函数接近最优值函数；
2. 当原奖励函数也具有势能函数差分形式的时候，也就是R=0+F，最优策略与奖励值为0的问题相同，也就是所有策略均为最优策略。

另外，当F（s，a，s‘）=V*（s），为最优值函数的时候，M’的值函数均为0，只需要学习不为0的动作值函数Q（s，a），能明显降低学习难度，因此能加快学习速度。

实验

实验主要证明在格子任务中按势能函数设计附加奖励函数能加快学习速度。

实验设计了这样的问题，如下图所示，需要从左下角走到右上角。

实验一根据曼哈顿距离设计了附加奖励函数F，极大加快了巡训练速度，使用0.5*F的实验组比F的慢一些。对照组的曲线不太清楚。

实验二设计了需要按照格子上数字的顺序访问到终点，设计了没访问一个子目标就给予一部分奖励的附加奖励函数，我在这里不详细说明。

总结

总的来说本文证明主干很简洁明了，得到的结果很优美，建议大家都看一看原论文。