Multi-time Models for Temporally Abstract Planning

Doina Precup, Richard S. SuttonNeurIPS 1997 · OpenReview

Introduction

Traditional Reinforcement Learning (RL) operates on a strict, discrete "tick-tock" time scale. An agent observes a state, takes a single primitive action (like "move north"), and receives a reward. While this works for simple tasks, it fails to capture how humans and intelligent systems actually plan. We don't plan a trip to Denver by thinking about individual footsteps; we think in terms of high-level "abstract actions" like "drive to the airport" or "board the plane."

The challenge in AI is that standard planning algorithms, such as Value Iteration, rely on Bellman equations that are traditionally built for one-step transitions. If you try to mix "one-step" actions with "multi-step" actions haphazardly, the underlying mathematics break down.

This paper introduces multi-time models, a mathematical framework that allows RL agents to plan using high-level, multi-step actions (e.g., "exit the room") rather than just one-step primitives. By proving these abstract models are compatible with standard Bellman equations, the authors show how agents can achieve massive speedups in planning without sacrificing mathematical rigor.

Methods: Formalizing Temporal Abstraction

The authors introduce Multi-time Models to generalize previous concepts like $n$-step models and $\beta$-models. This framework allows temporal abstractions—actions that take varying amounts of time—to be treated with the same mathematical consistency as primitive actions.

Key technical contributions include:

  • Homogeneous Coordinates: The reward vector ($g$) and state transition matrix ($P$) are represented as a single unified matrix ($M$). This allows complex models to be built using simple matrix operations: composition (multiplying matrices to sequence actions) and averaging (weighting different possible outcomes).
  • Mathematical Criteria for Planning: The authors define two critical properties a model must have to be useful for planning:
  • Validity: The model must correctly converge to the value function of its underlying policy.
  • Non-Overpromising (NOP): The model must not "promise" a higher value than what is actually achievable by the optimal policy.
  • Random Weighting Sequences: The core of the multi-time model is a sequence of random weights ($w_t$) that sum to 1. These weights determine how much "importance" is given to each time step along a trajectory, allowing the model to represent actions that terminate at different times or under different conditions.

Experimental Setup: The Stochastic Gridworld

To evaluate their framework, the authors used a simulated Stochastic Gridworld environment.

Stochastic Gridworld Environment
  • Environment: A grid of cells divided into four rooms connected by hallways.
  • Dynamics: Actions are "unreliable" (stochastic). If an agent tries to move in a direction, there is only a 67% chance of success; otherwise, it moves in one of the other three directions.
  • Abstract Actions: The authors defined eight abstract actions (two for each room) representing the policy of "traveling to the nearest hallway."

Key Insights and Results

The "aha moment" of this research is that a complex, closed-loop policy (like navigating a room) can be mathematically compressed into a single transition matrix and reward vector. Once compressed, the planning algorithm doesn't care that the action took 20 steps; it treats it as a single "jump" in time. Multi-time models act as a unifying theory for temporal abstraction in RL, showing that $n$-step returns (fixed time) and $\beta$-models (probabilistic termination) are just special cases of this more general weighting framework.

The primary result is a dramatic speedup in planning convergence:

  • Value Iteration Speed: In the gridworld task, using only primitive actions requires many iterations for the "value" of the goal to propagate back to distant starting cells.
  • Rapid Propagation: With abstract actions, the agent can propagate value across entire rooms in a single iteration. The authors demonstrated that an optimal policy for the entire environment was found in just 6 iterations when using abstract actions, whereas primitive-only planning was still localized near the goal.
  • Learning from Experience: These abstract models don't need to be hand-coded by humans. The models were successfully learned during a 1,000,000-step random walk, proving that the "knowledge" required for high-level planning can be extracted directly from raw experience.

Limitations and Future Work

While groundbreaking, the paper acknowledges several open challenges:

  • Discovery of Abstractions: The paper explicitly notes that it does not address how to discover these abstract actions automatically. The "room-to-hallway" actions were pre-defined by the researchers. Finding these "bottleneck" states or useful subgoals automatically remains a major open challenge, often referred to as the "Option Discovery" problem.
  • Discrete State Spaces: The theory presented assumes discrete, finite states. Extending this to continuous state spaces (common in robotics) would require function approximation, which adds significant complexity to the proofs of validity and NOP-ness.
  • Computational Overhead: While planning is faster, building and storing the $m \times m$ transition matrices for many abstract actions could become memory-intensive in very large environments.

Summary updated

Abstract

title> <meta name="citation_title" content="Multi-time Models for Temporally Abstract Planning" /> <meta name="citation_author" content="Precup, Doina" /> <meta name="citation_author" content="Sutton, Richard S." /> <meta name="citation_journal_title" content="Advances in Neural Information Processing Systems" /> <meta name="citation_volume" content="10" /> <meta name="citation_pdf_url" content="https://proceedings.neurips.cc/paper/1997/file/a9be4c2a4041cadbf9d61ae16dd1389e-Paper.pdf" /> <meta name="citation_publication_date" content="1997" /><!-- Bootstrap CSS --> <!-- https://codepen.io/surjithctly/pen/PJqKzQ --> <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.4.1/css/bootstrap.min.css" integrity="sha384-Vkoo8x4CGsO3+Hhxv8T/Q5PaXtkKtu6ug5TOeNV6gBiFeWPGFN9MuhOf23Q9Ifjh" crossorigin="anonymous" /> <link href="/static/menus/css/menus.css" rel="stylesheet" id="bootstrap-css" /> <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.8.1/css/all.css" integrity="sha384-50oBUHEmvpQ+1lW4y57PTFmhCaXp0ML5d60M1M7uH2+nqUivzIebhndOJK28anvf" crossorigin="anonymous" /> <script type="text/javascript" async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/latest.js?config=TeX-MML-AM_CHTML"></script> <script type="text/x-mathjax-config"> <![CDATA[ MathJax.Hub.Config({ "tex2jax": { "inlineMath": [["$","$"], ["\\(","\\)"]], "displayMath": [["\\[","\\]"]], "processEscapes": true } } ); ]]> </script> <style> <![CDATA[ @media (prefers-color-scheme: dark) { body { background-color: #333; color: #eee; } } .btn-spacer { margin: 2px; } .footer { position: fixed; left: 0; bottom: 0; width: 100%; background-color: #eee; color: black; } ]]> </style> <nav class="navbar navbar-expand-md navbar-light bg-light"> <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarToggler6" aria-controls="navbarToggler6" aria-expanded="false" aria-label="Toggle navigation"><span class="navbar-toggler-icon"></span></button> <div class="collapse navbar-collapse" id="navbarToggler6"> <a class="navbar-brand" href="/">NeurIPS Proceedings</a> <ul class="navbar-nav mr-auto mt-2 mt-md-0"> <li class="nav-item"> <a class="nav-link" href="/admin/login/?next=/admin/"><i class="fas fa-sign-in-alt" title="Login"></i></a> <li class="nav-item"> <a class="nav-link" href="/admin/logout/?nextp=/admin"><i class="fas fa-sign-out-alt" title="Logout"></i></a> <form class="form-inline my-2 my-lg-0" method="get" role="search" action="/papers/search"> <input class="form-control mr-sm-2" type="text" name="q" placeholder="Search" aria-label="Search" id="navsearch" /> <button class="btn btn-outline-success my-2 my-sm-0" type="submit">Search</button>
BibTeX
@inproceedings{precup1997multi,
  author = {Doina Precup and Richard S. Sutton},
  title = {{Multi-time Models for Temporally Abstract Planning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
  url = {https://openreview.net/forum?id=HJbKQububH},
}
Figure