The configurable tree graph (CT-graph): measurable problems in partially observable and distal reward environments for lifelong reinforcement learning

Andrea Soltoggio, Eseoghene Ben-Iwhiwhu, Christos Peridis, Pawel Ladosz, Jeffery Dick, Praveen K. Pilly, Soheil KolouriarXiv 2023 · DOI · arXiv

Reinforcement Learning (RL) has seen incredible success in video games and simulations, but moving from a high-score in Montezuma’s Revenge to solving real-world robotics or lifelong learning problems remains a massive leap. A new paper introduces the Configurable Tree graph (CT-graph), a "white-box" benchmark designed to bridge this gap by providing mathematically precise, tunable challenges for RL agents.

The Problem: Opaque Benchmarks

Standard RL benchmarks, like the Atari 2600 suite, are popular but opaque. If an agent fails to learn a complex game, it is often unclear if the failure stems from sparse rewards, a massive state space, or an inability to handle partial observability. In these environments, variables are "baked in" and difficult to isolate.

Furthermore, real-world problems are rarely Markovian. They are filled with "distractors" (irrelevant stimuli) and "distal rewards" (consequences occurring long after an action). The CT-graph provides a laboratory where researchers can turn specific "difficulty knobs"—such as noise, memory requirements, and reward distance—to identify exactly where algorithms break.

Methods: Tunable Complexity

The core of the environment is a multi-branch tree graph. An agent starts at a "Home" (H) state and must navigate through nodes to reach a "Leaf" (E) node where a reward might be hidden.

The CT-graph architecture, showing the minimal unit (left) and a depth-2 tree (right).

The graph uses three mechanisms to simulate complexity:

  1. Decision States (D): Nodes where the graph forks. The agent must choose the correct branch based on an observation.
  2. Wait States (W): "Corridor" nodes where the agent must perform a default action. A parameter $p$ defines the probability of staying in a wait state, effectively stretching the time between decisions and making rewards more distal.
  3. Observability Modes: The environment can be configured as a simple MDP (unique state IDs) or a challenging POMDP (identical-looking states or random noise in wait states).

By adjusting the branching factor ($b$), depth ($d$), and wait probability ($p$), researchers can create "needle in a haystack" scenarios where the probability of finding a reward by chance is effectively zero.

Key Insights: Measuring the Impossible

The CT-graph is a synthetic environment generator offering both 1D (one-hot vectors) and 2D (synthetic 12x12 images) observations. This flexibility allows for testing everything from basic tabular RL to complex convolutional neural networks.

A complex task configuration demonstrating the scalability of the environment for lifelong learning tests.
  • Measurable Sparsity: The authors provide exact formulas for the probability of reaching a reward. For example, in a graph with $b=2, d=4, p=0.9$, a random-walking agent has only a 1 in 83,000 chance of success, allowing for precise quantification of exploration strategies.
  • Navigation vs. Optimal Policy: The paper distinguishes between "Navigation" (avoiding Fail states) and "Optimal Policy" (reaching the goal). This hierarchy is crucial for testing how agents reuse skills across different tasks.
  • Lifelong Learning Playground: Because the reward location can be moved while keeping the graph structure identical, it is an ideal testbed for catastrophic forgetting. An agent can be tested on its ability to find a new reward at Leaf B without forgetting how to navigate the corridors it learned for Leaf A.

Key Results and Limitations

Previous studies using the CT-graph highlight that popular Meta-RL algorithms like MAML often struggle with high memory requirements and adversarial tasks. Conversely, modular approaches using neuroevolutionary memory units tend to perform better by isolating task-specific knowledge from general navigation skills.

Currently, the CT-graph is limited to discrete action spaces and single optimal paths. Future work aims to expand the environment to include more complex data streams and continuous control, further closing the gap between synthetic benchmarks and real-world application.

Summary updated

Abstract

This paper introduces a set of formally defined and transparent problems for reinforcement learning algorithms with the following characteristics: (1) variable degrees of observability (non-Markov observations), (2) distal and sparse rewards, (3) variable and hierarchical reward structure, (4) multiple-task generation, (5) variable problem complexity. The environment provides 1D or 2D categorical observations, and takes actions as input. The core structure of the CT-graph is a multi-branch tree graph with arbitrary branching factor, depth, and observation sets that can be varied to increase the dimensions of the problem in a controllable and measurable way. Two main categories of states, decision states and wait states, are devised to create a hierarchy of importance among observations, typical of real-world problems. A large observation set can produce a vast set of histories that impairs memory-augmented agents. Variable reward functions allow for the easy creation of multiple tasks and the ability of an agent to efficiently adapt in dynamic scenarios where tasks with controllable degrees of similarities are presented. Challenging complexity levels can be easily achieved due to the exponential growth of the graph. The problem formulation and accompanying code provide a fast, transparent, and mathematically defined set of configurable tests to compare the performance of reinforcement learning algorithms, in particular in lifelong learning settings.
BibTeX
@misc{soltoggio2023configurable,
  author = {Andrea Soltoggio and Eseoghene Ben-Iwhiwhu and Christos Peridis and Pawel Ladosz and Jeffery Dick and Praveen K. Pilly and Soheil Kolouri},
  title = {{The configurable tree graph (CT-graph): measurable problems in partially observable and distal reward environments for lifelong reinforcement learning}},
  year = {2023},
  eprint = {2302.10887},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.10887},
}
Figure