TeXDYNA: Hierarchical Reinforcement Learning in Factored MDPs ⋆

Olga Kozlova, Olivier Sigaud, Christophe Meyer2014

TL;DR

This paper introduces TeXDYNA, a novel algorithm that tackles the complexity of large-scale reinforcement learning problems by combining hierarchical abstraction with factored representations. TeXDYNA efficiently learns hierarchical policies by simultaneously discovering options and building a factored model of the environment, demonstrating significant improvements in learning speed and representation size compared to existing methods.

What Problem Does This Paper Address?

Reinforcement learning (RL) is a powerful paradigm for learning adaptive behaviors, but standard RL algorithms struggle with the "curse of dimensionality" inherent in large state spaces. This paper addresses this challenge by tackling two key issues:

  1. Scalability of RL: Real-world problems often involve a vast number of states, making it computationally infeasible for traditional RL algorithms to explore and learn effectively.
  2. Exploiting Structure: Many RL problems possess inherent structure, both in their state representation (e.g., factored MDPs) and in their decision-making processes (e.g., hierarchical tasks). Effectively leveraging this structure is crucial for efficient learning.

The authors highlight two main research directions for addressing these issues: Factored MDPs (FMDPS) that represent states using variable assignments and Hierarchical Reinforcement Learning (HRL) that decomposes tasks into subtasks. However, a significant challenge is that the structure of these problems is often unknown in practice. TeXDYNA aims to bridge this gap by learning both the factored structure and the hierarchical decomposition simultaneously.

Methods

TeXDYNA integrates two key concepts:

  • Factored Reinforcement Learning (FRL): This approach leverages the structure of the state space by representing it as a set of variables. Algorithms like Structured Dynamic Programming (SDP) and Structured-DYNA (SDYNA) exploit dependencies between these variables for more compact representations and efficient computation. TeXDYNA builds upon the SDYNA framework.
  • Hierarchical Reinforcement Learning (HRL): This paradigm decomposes complex tasks into simpler subtasks, often represented as "options" (temporally extended actions). This allows for learning and planning at different levels of abstraction. TeXDYNA uses an "exit-oriented" option representation, where options are defined by their exit states, inspired by prior work like HEXQ and VISA.

TeXDYNA's novelty lies in its simultaneous learning of options and the FMDP model. It works by:

  1. Discovering Options: TeXDYNA learns the overall FMDP transition function as a decision tree. When an action modifies a variable's value, it can trigger the discovery of a new option. Options are defined by their exit conditions (variable change, action, context) and initiation sets.
  2. Hierarchical Policy Construction: It builds a hierarchy of options, where higher-level options are composed of lower-level options or primitive actions. This hierarchy is dynamically constructed based on the learned transition structure.
  3. Incremental Learning and Planning: TeXDYNA uses a modified version of the SPITI algorithm for planning. This involves an "acting" phase (e-greedy exploration), a "learning" phase (updating local FMDP models for each option), and a "planning" phase (updating value and policy functions). The upward update mechanism ensures that the learned models incorporate changes from incremental learning.
  4. Local Models: A key advantage is that each option learns a local model of its sub-FMDP, which is significantly smaller than the global model, accelerating learning.

Datasets

The paper evaluates TeXDYNA on the LIGHT BOX problem. This is a benchmark problem described as consisting of twenty binary "lights" (ON/OFF states) with complex dependencies. The problem has a large state space (2^20 ≈ 1 million states) and a correspondingly large number of state-action pairs (≈ 20 million). The authors note that the problem has both deterministic and stochastic versions.

Key Insights and Ideas

  • Simultaneity is Key: The most significant insight is that learning the factored structure of the environment and discovering hierarchical options can and should happen simultaneously. This allows the discovered options to directly inform the model learning and vice-versa.
  • Local Models for Scalability: By decomposing the problem into options, each with its own local model, TeXDYNA dramatically reduces the computational burden. This is a crucial step for tackling large-scale RL problems.
  • Bottom-Up Option Discovery: The hierarchical structure of options emerges naturally from the learned transition trees, providing a bottom-up approach to discovering subgoals.
  • Exploration through Hierarchy: The option selection mechanism, which favors higher-level options initially and then explores lower levels, provides a structured way to explore the state space, leading to faster convergence.
  • Factored Representation for Options: Integrating factored representations within the options framework allows for more compact and efficient representation of sub-problems.

Key Results

The paper presents experimental results on the LIGHT BOX problem, comparing TeXDYNA to DYNA-Q and SPITI.

  • Convergence Speed: TeXDYNA shows significantly faster convergence in terms of episodes required to complete an episode compared to DYNA-Q, especially in the stochastic version of the problem.
  • Representation Size: TeXDYNA builds much smaller representations (policy and value function sizes) than its competitors. For instance, in the stochastic LIGHT BOX problem, TeXDYNA's transition function size is 780 ± 14 nodes, while SPITI's is > 15000. Similarly, policy and value function sizes are considerably smaller.
  • Efficiency: TeXDYNA achieves a much lower time per step (0.04 seconds) compared to SPITI (> 100 seconds) in the stochastic setting.
  • Goal Achievement: TeXDYNA effectively navigates the complex dependencies in the LIGHT BOX problem, achieving subgoals to reach the final goal of turning on the red light, whereas SPITI struggles due to its memory requirements.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Exploration Strategy: The current e-greedy exploration strategy could be improved. Future work could explore more sophisticated methods like "optimism in the face of uncertainty" or incorporate intrinsic motivation mechanisms (e.g., artificial curiosity).
  • Option Discovery Granularity: The assumption of at most one option per variable value change simplifies computation but could be relaxed. This might lead to an excessive number of options in problems where one action affects multiple variables.
  • Strict Hierarchy: The current strict ordering of the option hierarchy might not be suitable for all problems. Relaxing this could allow for more complex structures, such as synchronic arcs or post-action variable dependencies, which currently lead to cross-dependencies and cycles.
  • Internal Reward: The use of "internal reward" to propagate external rewards to local policies is a heuristic. Future work could explore task-specific knowledge to identify more useful or challenging subroutines.
  • Robotics Application: The authors suggest that applying TeXDYNA to a robotics problem would be a valuable next step for more experimental validation.
  • Stochasticity and Determinism: While TeXDYNA handles stochastic problems, further comparisons and analysis across different levels of stochasticity would be beneficial.

Summary updated

Abstract

Reinforcement learning is one of the main adaptive mechanisms that is both well documented in animal behaviour and giving rise to computational studies in animats and robots. In this paper, we present TeXDYNA, an algorithm designed to solve large reinforcement learning problems with unknown structure by integrating hierarchical abstraction techniques of Hierarchical Reinforcement Learning and factorization techniques of Factored Reinforcement Learning. We validate our approach on the LIGHT BOX problem. 1
BibTeX
@misc{kozlova2014texdyna,
  author = {Olga Kozlova and Olivier Sigaud and Christophe Meyer},
  title = {{TeXDYNA: Hierarchical Reinforcement Learning in Factored MDPs ⋆}},
  year = {2014},
}
Figure