Improved Switching among Temporally Abstract Actions

Richard S. Sutton, Satinder P. Singh, Doina Precup, Balaraman RavindranNeurIPS 1998 · OpenReview

In robotics and complex control applications, it is common to rely on a pre-existing set of controllers—or "options"—to solve subtasks. However, deciding exactly when to switch between these controllers to optimize overall performance remains a difficult challenge.

This paper introduces the Interruption Theorem, a framework demonstrating that reinforcement learning (RL) agents can significantly improve their performance by flexibly switching between high-level subtasks rather than blindly following them to completion. By re-evaluating goals at every step using existing value functions, agents can "cut corners" and adapt to dynamic changes with negligible computational overhead.

The Problem with Rigid Subroutines

In Reinforcement Learning, complex tasks are often broken down into "temporally abstract actions" or options. Think of these as pre-programmed subroutines, such as a robot's instruction to "navigate to the kitchen" or "pick up the cup."

The standard approach, modeled via Semi-Markov Decision Processes (SMDPs), treats these options as "black boxes." Once an agent initiates an option, it is locked in until a pre-defined termination condition is met. This rigidity breeds inefficiency. If a robot is halfway to the kitchen and realizes it is already standing next to the trash can (its subsequent goal), it shouldn't be forced to finish the "go to kitchen" routine first. The authors address how to break out of these rigid high-level plans to achieve more fluid, optimal behavior.

The Interruption Theorem

The authors build upon the Options Framework, where an option consists of an initiation set (where it can start), a policy (what to do), and a termination condition (when to stop).

The core contribution is Theorem 1 (Interruption). The authors propose a simple, instantaneous rule: at every single time step, the agent compares the value of continuing its current option against the value of stopping and picking a new option. If the value of switching is higher, the agent interrupts the current option and selects the new one.

Crucially, this does not require traditional "re-planning." The agent simply leverages the value functions it already calculated during the high-level planning phase to make these instantaneous switching decisions, resulting in a "free" performance boost.

Experimental Validation

The paper evaluates this theory using two simulated environments, demonstrating massive efficiency gains and state-space reductions.

1. The "Corner-Cutting" Effect in 2D Navigation

In a continuous 2D navigation task, an agent must move from a start point to a goal using seven "landmark" controllers. Standard SMDP planning forces the agent to hit every landmark exactly, treating the subtasks as opaque, indivisible units.

Trajectories comparing SMDP and Interrupted solutions

By applying the interruption rule, the agent is allowed to "cut corners." It transitions to the next landmark's controller as soon as it becomes mathematically efficient to do so. The standard SMDP-optimal policy took 600 steps to reach the goal. The interrupted policy reached the goal in just 474 steps—approaching the theoretical global optimum of 425 steps without ever needing to plan at the computationally heavy low level.

2. Mission Planning and State-Space Reduction

The second task is a complex flight simulation where a plane must visit observation sites, account for randomly changing weather, and return to base before running out of fuel.

By planning at the level of options rather than primitive actions, the authors reduced the complexity of the mission planning task from 24.3 billion state-action pairs to just 874,800 state-controller pairs—a reduction of over 99.99%.

Expected reward per mission comparing planning methods

Furthermore, the interrupted policy proved highly resilient to the stochastic nature of the environment. Because it re-evaluates its commitment at every tick of the clock, it significantly outperformed both the standard SMDP policy and a "static planner" (which plans a full tour and only re-plans when weather changes), especially under constrained conditions like low fuel.

Limitations and Future Work

While the Interruption Theorem offers a powerful, zero-cost improvement for hierarchical planning, the paper notes a few limitations:

  • Tabular Methods: The examples rely on exact, tabular methods to represent value functions. Real-world, high-dimensional problems require function approximation (like neural networks), and combining this switching logic with function approximation is a necessary next step.
  • Model Dependency: The method assumes the agent has access to a model of the options' consequences. In model-free RL, these values would need to be learned through experience, potentially introducing estimation errors.
  • Option Discovery: The framework assumes the options are already provided (hand-crafted or previously learned). It does not solve the "Option Discovery" problem of how an agent should define its own subtasks from scratch.

Summary updated

Abstract

In robotics and other control applications it is commonplace to have a preexisting set of controllers for solving subtasks, perhaps hand-crafted or previously learned or planned, and still face a difficult problem of how to choose and switch among the controllers to solve an overall task as well as possible. In this paper we present a framework based on Markov decision processes and semi-Markov decision processes for phrasing this problem, a basic theorem regarding the improvement in performance that can be obtained by switching flexibly between given controllers, and example applications of the theorem. In particular, we show how an agent can plan with these high-level controllers and then use the results of such planning to find an even better plan, by modifying the existing controllers, with negligible additional cost and no re-planning. In one of our examples, the complexity of the problem is reduced from 24 billion state-action pairs to less than a million state-controller pairs.
BibTeX
@inproceedings{sutton1998improved,
  author = {Richard S. Sutton and Satinder P. Singh and Doina Precup and Balaraman Ravindran},
  title = {{Improved Switching among Temporally Abstract Actions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
  url = {https://openreview.net/forum?id=S1ZdED-_br},
}
Figure