Permutation based task transfer for genetic programming

这项研究建议的一般背景是，遗传编程（GP）适用于学习决策政策的代理人在延迟支付（或强化学习）的环境中运行。该提案的具体重点在于开发一个框架，以系统地扩展GP到比以前考虑的更困难的延迟回报任务版本。特别是，我们感兴趣的场景中，一个简单的初始“源”任务的解决方案，然后“转移”到一个更困难的，但相关的（目标）任务;或一种形式的迁移学习。这项工作的见解是利用GP的能力，以确定解决方案，利用状态变量的子集。然后，这为重新部署在源任务下发现的解决方案提供了基础，这样就可以解决更困难的任务。采用这种方法的潜在好处是：1）没有必要从头开始不断地重新发现策略; 2）增加最终目标任务的成功/或更好的解决方案;以及3）如针对找到每个任务的解决方案所测量的更低的计算开销。 两个特定的目标域将被用来说明的方法：1）学习策略，踢足球的连续值模拟2D世界的RoboCup keepaway; 2）学习一般政策，解决3 × 3魔方。keepway足球任务代表了多智能体学习的基准，因此具有先前结果的历史以及逐渐增加难度的任务。魔方任务作为任何形式的学习算法的基准之前都没有什么历史。相反，解决方案采取了部署某种形式的穷举搜索的形式。这两个任务都代表了复杂任务域的示例，这些复杂任务域具有非常大的状态空间（潜在的法律的状态数量），但是具有GP应该能够发现其特定实例的底层属性（潜在属性）。本研究的基本假设是，一旦一个实例的上下文相关的策略被确定为解决初始任务的一些子集，那么我们应该能够使用这个作为基础，通过一个确定性的变化过程中的政策的引用状态变量的任务推广到更多的实例。当然，为了扩大这个过程，我们需要避免人为地将病理学引入搜索。简而言之，最初的政策之和（后来的政策是从这些政策中构建出来的）需要超过其各部分之和。 这些目标的成功将提供一个总体框架，用于将GP扩展到广泛的延迟回报任务。此类任务引起了GP社区的广泛兴趣，因为它们代表了应用GP的一些最昂贵（如果不是最昂贵）的任务域集。此外，这两个任务领域被广泛认为具有特别的挑战性。

The general context for this research proposal is that of genetic programming (GP) as applied to learning decision making policies for agents operating in environments with delayed payoff (or reinforcement learning). The specific focus of the proposal lies in developing a framework for systematically scaling GP to more difficult versions of tasks with delayed payoff than have previously been considered. In particular we are interested in scenarios in which solutions for a simpler initial `source' task are then `transferred' to a more difficult but related (target) task; or a form of transfer learning. The insight of this work is to make use of the capability of GP to identify solutions that make use of subsets of state variables. This then provides the basis for redeploying solutions discovered under the source task such that more difficult tasks can be solved. The potential benefits of adopting such an approach are that: 1) it is not necessary to continuously rediscover policies from scratch; 2) increased success in / or better solutions to the ultimate target task; and 3) lower computational overhead as measured against finding solutions to each task. Two specific target domains will be used to illustrate the approach: 1) learning policies to play soccer in the continuous valued simulated 2D world of RoboCup keepaway; 2) learning general policies for solving the 3 by 3 Rubik cube. The keepway soccer task represents a benchmark for multi-agent learning, hence has a history of previous results as well as posing tasks of incrementally increasing difficulty. The Rubik cube task has had little previous history as a benchmark for learning algorithms of any form. Instead solutions have taken the form of deploying some form of exhaustive search. Both tasks represent examples of complex task domains that have very large state-spaces (potential number of legal states), but possess underlying properties (regularities) that GP should be able to discover specific instances of. The basic hypothesis of this research is that once an instance of a context dependent strategy is identified for solving some subset of an initial task, then we should be able to use this as the basis for generalizing to many more instances of the task through a deterministic process of variation in the policy's references to the state variables. Naturally, for the process to scale, we need to avoid artificially introducing pathologies into the search. In short, the sum of initial policies from which a later policy is constructed needs to exceed the mere sum of its parts. Success in these objectives would provide a general framework for scaling GP to a wide range of tasks with delayed payoff. Such tasks are of widespread interest to the GP community because they represent some of the most expensive, if not the most expensive, set of task domains for applying GP to. Moreover, the two task domains are widely acknowledged to be of a particularly challenging nature.