论文解读：Policy Transfer in Reinforcement Learning: A Selective Exploration Approach

论文题目：Policy Transfer in Reinforcement Learning: A Selective Exploration Approach

论文链接：

http://www.aaai.org/ocs/index.php/AAAI/AAAI17/paper/download/14729/14228

https://ala2019.vub.ac.be/papers/ALA2019_paper_16.pdf

论文出处：AAAI 2017, AAMAS 2019（两个版本）

了解迁移学习的小伙伴们都知道，迁移学习将任务分为源任务（source task）和目标任务（target task），为了让模型在数据量有限的情况下很好地学习目标任务，需要将源任务中学习好的模型充分利用，通过一些先验知识等将源任务迁移到目标任务。这种设定主要是考虑到两点：1）目标任务数据量小，或者样本空间大，难学；2）源任务已经学好了，并且源任务和目标任务之间有关联。

今天要介绍的这篇论文，是将迁移学习和强化学习结合，提出一种策略迁移算法，使得智能体在目标任务的求解过程中，能够高效、有选择地在状态空间中探索。因此，所提出的算法名叫SEAPoT：Selective Exploration and Policy Transfer Algorithm。下面，我们来详细了解算法是如何设计并实现的。

对于一个马尔科夫决策过程（MDP），其状态空间、动作空间、奖励设置等环境因素的变化，都会使得环境发生变化。源任务和目标任务的区别也往往针对这些不同而展开。本文研究的源任务和目标任务，其区别主要体现在状态转移概率和（或）奖励函数上。而作者是通过计算相应状态-动作转移概率分布的距离，来定义不同任务之间的相似度。不同任务之间的区别可以由导致状态-动作转移概率分布发生变化的环境参数来表征。

从源任务到目标任务，智能体首先通过change-detection机制，并根据一定的先验知识来侦测环境发生了哪些变化。然后智能体会构建一个包含这些变化区域的子空间来适应目标任务的场景，并且在这些子空间中学习一个局部的策略。SEAPoT算法主要组成部分是Bayesian change detection和selective exploration。

Bayesian change detection：

这里需要提出一个概念，叫change point（变点），即一个时间序列信号前后服从不同的分布模型，其边界点就是change point。作者在这里使用贝叶斯变点检测技术来分析源任务和目标任务不同分布的数据[1, 2]。作者引用了文献[1]中的product partition approach，利用这种方法将观测到的时间序列数据分割成不同的部分，每个部分服从不同的概率模型。

例如一个智能体在某个时刻的状态为 $s=(<x,y, \theta>, \delta)$ ，其中 $<x, y, \theta>$ 分别为智能体的横坐标、纵坐标和角度， $\delta$ 为智能体上的传感器测量出来的距离。下图是在一个5*5网格环境中的传感器观测数据，红色曲线表示在一个特定的位置 $<x, y, \theta>$ ，传感器所测得的 $\delta$ 值。当环境发生变化的时候，例如出现了一个障碍物，或者障碍物消失，则change detection算法将在该点计算得出较高的似然概率，从而推断出此处就是change point。这种Bayesian change detection算法对环境中每个状态都计算一遍，得到所有状态下可能的change points。

观测数据的变点检测：出现一个障碍物（左图），障碍物消失（右图）

Selective exploration：

该部分分为三步：1）子空间构建；2）子空间策略求解；3）策略整合。

子空间构建：利用breadth-first机制构建子空间，也就是将前面检测到的change point所在的状态作为起点，向后扩展 $n$ 步，围绕该状态的局部空间就构成一个子空间，相应地其决策过程称为一个微型的子空间MDP。作者通过定义adjacency of state（相邻状态）、reachability（可达性）、n-step closure（n步可达）、frontier states（边界状态）和子空间（其定义和文献[3]中关于子空间的定义类似）来进行子空间选择性的搜索，从父任务中构建子空间的MDP。详细定义请参考原文，其实就是将这些直观上的概念用数学化的语言进行严谨地定义。根据这些定义，作者得出几个结论：

引理3.6 （Local goal states）所有的边界状态的集合，组成子MDP的目标状态。

引理3.7 （Goal preference）对每个目标状态 $G$ ，其奖励函数设置为 $r^\prime = r + \Phi(G)$ ，其中 $\Phi$ 是一个potential function， $r$ 是父任务的奖励函数。则子空间的奖励函数为 $R^\prime=\{r\prime\}$ ，并且 $R^\prime$ 创建了目标状态的优先顺序。

关于potential function（ $\Phi$ ）的选择，作者参考了文献[4]，也就是Andrew Ng的那篇reward shaping的名作。在网格环境中，可以定义为智能体到目标点的曼哈顿距离。

定理3.8 （Sub-space extraction）存在 $G\in\mathcal{F}$ ，使得 $(C^n(s_i), G)$ 构成一个子空间。

根据以上定义，将会得到一个子空间MDP， $M^\prime=<S^\prime, A^\prime, T^\prime, R^\prime>$ 。有了这个MDP，下一步就是状态空间探索和策略求解。

子空间探索：每个子空间MDP看成是一个子任务。这里，作者使用 $R_{MAX}$ 探索机制在子空间中探索（其它任何合适的探索机制也可以）。此外，还要将子空间中的状态和父任务的状态一一对应（这里，作者使用表格索引）。对于子空间的动作空间，可能和父任务的动作空间不一样，例如子空间如果只是导航任务，则不需要抓取、安放等动作。

策略整合：子空间学习出来的policy最终还是为了解决target task。因此，需要将该policy和源任务中的policy整合起来。整合的方法很多，最简单的就是通过判断状态是否在子空间中，然后切换策略。这种方法的缺陷是，在目标任务的其它状态没有探索，只在子空间中探索，这将可能导致整合出来的策略在目标任务中是次优的。作者使用的方法是类似 $\epsilon-greedy$ 的方法，在目标任务中探索的时候以一定的概率强制建立子空间，即使该状态不是change point，也建立子空间MDP。最后学出来的策略作为目标任务的最优策略。

后悔值计算（Regret calculation）：这里的智能体累积后悔值和n-step closure步长有关。

定义3.9（Diameter）假设每个动作的执行需要一个固定的时间单位，则diameter的定义就是从状态 $s$ 到状态 $s^\prime$ 所需要的时间步数[5]。即 $D(M)=\max_{s\neq s\in \mathcal{S},}\min_{\pi:\mathcal{S}\rightarrow \mathcal{A}}\mathbb{E}[T(s^\prime|M, \pi, s)]$ 。

定义3.10（Regret）智能体在第T步执行策略 $\pi$ 的后悔值定义为 $\Delta(s)=T\mu^*-\sum_{t=1}^{T}r^t$ （其中 $\mu^*$ 是平均最优奖励）。

定理3.11（Regret as a function of n）智能体在目标任务中使用SEAPoT算法获得的策略，所积累的Regret值只和步长 $n$ 有关，被用于构建子空间。

以上所有引理、定理的证明，请各位参考原文。（比较枯燥）

算法细节：

1. Algo SEAPoT:

2. while Target task NOT solved:

3. With probability $\epsilon$ explore target;

4. while NOT ChangeDetect():

5. $s^\prime \leftarrow \boldsymbol{f}(s, \pi^{\mathcal{S}}(s))$ ; //execute policy

6. Extract sub-space MDP();

7. Explore sub-space MDP();

8. Compose policy $\pi^T$ .

9. Proc Explore sub-space MDP:

10. Input: subSpaceMDP

11. Explore using R-MAX until $g^\prime \in G^\prime$ reached;

12. Proc Extract sub-space MDP:

13. // identify n-step closure

14. $S^\prime \leftarrow C^n(s)$ // According to Defn 3.3

15. // identify the local goal

16. $G^\prime \leftarrow \mathcal{F}(S^\prime)$ // According to Lem 3.6

17. Define $R^\prime$ // According to Lem 3.7

18. Construct $M^\prime$ //According to Thm 3.8

19. Proc ChangeDetect:

20. Input: Time series data D

21. if Change detected:

22. Return True

总结：

个人认为对每个状态都计算change detection，其计算量对稍微大一点规模的问题都是无法想象的。此外，子空间的状态和父任务的状态一一对应关系没有描述清楚，如果用查表的方法做的话，又限制了问题的规模。论文的整体思路，个人认为最值得借鉴的地方是change point的识别，然后建立子空间MDP进行selective exploration，从而找到source task和target task的关系。至于下一步怎么解决，并不是最主要的贡献。

【参考文献】

[1] Barry, Daniel, and John A. Hartigan. "A Bayesian analysis for change point problems." Journal of the American Statistical Association 88.421 (1993): 309-319.

[2] Erdman, Chandra, and John W. Emerson. "bcp: an R package for performing a Bayesian analysis of change point problems." Journal of Statistical Software 23.3 (2007): 1-13.

[3] Bowling, Mike, and Manuela Veloso. "Reusing learned policies between similar problems." in Proceedings of the AI* AI-98 Workshop on New Trends in Robotics. 1998.

[4] Ng, Andrew Y., Daishi Harada, and Stuart Russell. "Policy invariance under reward transformations: Theory and application to reward shaping." ICML. Vol. 99. 1999.

[5] Auer, Peter, Thomas Jaksch, and Ronald Ortner. "Near-optimal regret bounds for reinforcement learning." Advances in neural information processing systems. 2009.