Emergent Tangled Program Graphs in Multi-Task Learning

Stephen Kelly, Malcolm I. HeywoodIJCAI 2018 · DOI

TL;DR

This paper introduces Tangled Program Graphs (TPGs), a novel Genetic Programming framework for Multi-Task Reinforcement Learning (MTRL) that learns a single, adaptive policy for multiple Atari games simultaneously. TPGs achieve state-of-the-art results, matching or exceeding deep learning approaches, while being remarkably simple, efficient, and free from the need for specialized hardware.

What Problem Does This Paper Address?

Reinforcement Learning (RL) has seen significant success in training agents to play individual games, particularly within the Atari suite, which serves as a benchmark for domain-independent RL. However, training agents for multiple tasks (Multi-Task RL or MTRL) presents a significant challenge: how to develop a single agent that can effectively learn and perform well across diverse environments without forgetting previously learned skills or requiring extensive task-specific engineering. Existing approaches often focus on game-specific agents, leading to a proliferation of models. This paper tackles the problem of learning a single, unified policy for multiple, distinct Atari games simultaneously, aiming for emergent modularity and adaptability.

Methods

The core contribution is the Tangled Program Graph (TPG) framework, an extension of the Symbiotic Bid-Based (SBB) algorithm. TPGs build upon a "team" of programs, where each program is a simple register machine capable of performing arithmetic operations and conditional logic.

  • Teams: A team represents a single decision-making entity. Programs within a team compete by outputting a "bid" (the value of a specific register), and the team selects the action corresponding to the highest bid.
  • Tangled Program Graphs: TPGs evolve from teams by allowing programs to reference other teams as actions, creating a hierarchical, graph-like structure. Each node in the graph is a team, and edges represent either atomic actions (like joystick movements) or transitions to other teams.
  • Emergent Modularity: The TPG framework is designed for bottom-up evolution. Initially, programs are simple, and as evolution progresses, teams self-organize into collective decision-making entities. Programs can reference other teams, leading to the emergence of complex, multi-level policy graphs.
  • Multi-Task Learning: The TPG framework is applied to MTRL by introducing task switching during evolution. The active game title is switched periodically, forcing the TPG to adapt and maintain competence across different games. Fitness is evaluated on the currently active game, but the overall survival of a policy depends on its performance across all tasks.

Datasets

The paper uses the Arcade Learning Environment (ALE), which provides an emulator for Atari 2600 games. The specific games used for evaluation are:

  • Game Group A: Centipede, Frostbite, Ms. Pac-Man
  • Game Group B: Asteroids, Battle Zone, Zaxxon

These games were chosen because TPGs had previously achieved state-of-the-art results on them individually. The raw Atari pixel matrices are preprocessed by quantizing them into 1344 decimal state variables.

Key Insights and Ideas

  • Emergent Modularity and Adaptability: TPGs demonstrate that complex behaviors and multi-task competence can emerge from simple, evolving components without explicit architectural design. The policies start simple and adaptively complexify based on environmental interaction.
  • Efficiency and Real-Time Performance: TPG policies are remarkably efficient, operating in real-time without specialized hardware like GPUs. This is a significant advantage over many deep learning approaches.
  • State Space Selectivity: Each program within a TPG indexes only a small portion of the state space. As the policy graph grows, it incrementally indexes more of the state space, allowing for specialized decision-making in different regions without incurring prohibitive computational costs per decision.
  • Avoiding Catastrophic Forgetting: The hierarchical structure of TPGs, where lower-level teams are not modified once subsumed into a policy graph, appears to help mitigate catastrophic forgetting during continual learning with task switching.

Key Results

  • State-of-the-Art Performance: TPGs achieved performance matching or exceeding state-of-the-art deep reinforcement learning (DQN) results on individual Atari games.
  • Multi-Task Competence: A single TPG policy was evolved to play three different Atari games simultaneously, achieving competent performance across all games. While not initially matching DQN on all games, the multi-task policies showed significant improvement and competence by specific generation milestones.
  • Complexity vs. Performance: The complexity of TPG policies (number of teams, instructions, state space indexed) is an emergent property and is significantly lower than that of deep learning models like DQN, which perform millions of weight computations per decision. For example, the Group A multi-task champion required between 588 and 1064 instructions per decision.

Limitations and Future Work

  • Initial Policy Degeneracy: In some cases, TPGs can start with degenerate but high-scoring policies (e.g., selecting "up-right-fire" in Centipede). While these policies improve to become more interesting, the initial state can be uninformative.
  • Task Switching Strategy: The paper uses a simple uniform probability task switching strategy. Future work could explore more sophisticated or adaptive task-switching mechanisms.
  • Generalization to More Tasks: While successful with three tasks, scaling TPGs to a much larger number of diverse tasks remains an open question.
  • Exploration of Program Complexity: The paper notes that the complexity of the program representation itself could be further explored.

Summary updated

BibTeX
@inproceedings{kelly2018emergent,
  author = {Stephen Kelly and Malcolm I. Heywood},
  title = {{Emergent Tangled Program Graphs in Multi-Task Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/740},
}

Loading related content...

Figure