Finding Structure in Reinforcement Learning

Sebastian Thrun, Anton SchwartzNeurIPS 1994 · OpenReview

Introduction

Reinforcement Learning (RL) often struggles with the "curse of dimensionality." In large, real-world environments, an agent must make thousands of micro-decisions—such as individual motor torques or grid movements—before receiving a sparse reward. Standard RL treats every task as a blank slate, forcing the agent to learn fine-grained actions from scratch every time.

To scale RL effectively, agents must discover the underlying structure of the world. For instance, if an agent is learning to navigate a house, "going through a door" is a sequence of actions that remains useful regardless of whether the final destination is the kitchen or the bedroom. The core challenge addressed by Sebastian Thrun and Anton Schwartz is how an agent can automatically recognize which action sequences are "important" enough to be abstracted into reusable skills without human intervention.

The SKILLS algorithm offers a solution by discovering "skills"—reusable, partially defined action policies shared across multiple related tasks. By balancing a trade-off between performance loss and the "description length" (complexity) of the policy, the system automatically identifies useful behavioral building blocks.

The SKILLS Algorithm

The paper treats skill discovery as an optimization problem. The central idea is to minimize a cost function, $E$, that balances two competing objectives:

$$E = \text{PERFORMANCE LOSS} + \eta \cdot \text{DESCRIPTION LENGTH}$$

  1. Performance Loss: Using a generic "skill" instead of a task-specific optimal action usually results in a slight drop in efficiency. The algorithm attempts to keep this loss to a minimum.
  2. Description Length (DL): Borrowing from information theory, DL measures how many "bytes" are needed to describe the agent's policies. If ten different tasks all use the same "skill" for a specific region of the state space, the total description length of the system decreases because the policy is shared rather than repeated.
  3. $\eta$ (Gain Parameter): This parameter allows the user to tune the trade-off. A high $\eta$ favors very compact, broadly applicable skills, while a low $\eta$ favors high-performance, task-specific actions.

The algorithm is interleaved with standard Q-Learning. As the agent learns the value of actions, it simultaneously adjusts three variables for its skills:

  • Skill Actions: What the skill actually executes in a given state.
  • Skill Domain: The specific subset of the environment where the skill is applicable (e.g., near a door).
  • Skill Usages: How much a specific task relies on a specific skill.

Experimental Setup

As a foundational RL paper, the authors utilized simulated environments to test their approach:

  • Simple 3-Room Grid World: A navigation task where an agent must move between rooms. There are four tasks (starting in different corners) and two available skill slots.
  • Complex Grid World: A larger environment featuring 20 different tasks with varying start/goal positions and door configurations (open or closed), utilizing 25 available skill slots.

Key Insights and Results

Skills as Bottlenecks: The algorithm naturally identifies "bottleneck" areas of the state space. In the 3-room experiment, the discovered skills centered perfectly on the doorways. This occurs because the doorway is the one place where many different navigation tasks must agree on a common policy.

Two distinct skills discovered in the 3-room grid world, centering on the left and right doorways.

Successful Abstraction: After 30,000 training steps per task in the 3-room environment, the algorithm successfully "carved out" two distinct skills that led the agent to the left and right doors, respectively. When the number of available skills was increased to six, the agent partitioned the space even more effectively, creating specific skills for "exiting a corner" that were shared across three out of four tasks.

MDL for RL: Applying the Minimum Description Length (MDL) principle to action policies provides a novel way to define "structure." It suggests that "useful" behavior is that which allows for the most compressed representation of multiple solutions. Furthermore, unlike earlier rigid "macro-action" approaches, SKILLS uses a probabilistic selection rule, allowing the agent to smoothly transition between using a shared skill and task-specific fine-tuning.

A skill domain discovered in the complex grid world environment.

Scaling: The algorithm demonstrated it could find modular skills even in the complex grid world with 20 tasks, though the stability of these skills decreased as the environment's complexity grew.

Limitations and Future Directions

While groundbreaking, the SKILLS algorithm has several notable limitations:

  • Learning Speed: Finding skills is significantly harder than learning control. Discovering useful skills took an order of magnitude longer than finding a close-to-optimal policy using standard RL.
  • The "Cold Start" Problem: SKILLS requires reasonably accurate Q-tables (value functions) to be available before it can start identifying meaningful structure. It cannot discover skills entirely "in the dark."
  • State Space Generalization: In this version, skills generalize across tasks but not across states. For example, the agent cannot recognize that "climbing a staircase" is the same skill regardless of which floor it is on; it treats every staircase as a unique location.
  • Function Approximation: The paper relies on lookup tables for states. Moving to neural networks (function approximators) would require redefining how "description length" is calculated for a network's weights.

Summary updated

Abstract

Reinforcement learning addresses the problem of learning to select actions in order to maximize one's performance in unknown environments. To scale reinforcement learning to complex real-world tasks, such as typically studied in AI, one must ultimately be able to discover the structure in the world, in order to abstract away the myriad of details and to operate in more tractable problem spaces. This paper presents the SKILLS algorithm. SKILLS discovers skills, which are partially defined action policies that arise in the context of multiple, related tasks. Skills collapse whole action sequences into single operators. They are learned by minimizing the com(cid:173) pactness of action policies, using a description length argument on their representation. Empirical results in simple grid navigation tasks illustrate the successful discovery of structure in reinforcement learning.
BibTeX
@inproceedings{thrun1994finding,
  author = {Sebastian Thrun and Anton Schwartz},
  title = {{Finding Structure in Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1994},
  url = {https://openreview.net/forum?id=B1bqLdZOWB},
}
Figure