Representation Discovery in Sequential Decision Making

Sridhar MahadevanAAAI 2010 · OpenReview

Abstract

Automatically constructing novel representations of tasks from analysis of state spaces is a longstanding fundamental challenge in AI. I review recent progress on this problem for sequential decision making tasks modeled as Markov decision processes. Specifically, I discuss three classes of representation discovery problems: finding functional, state, and temporal abstractions. I describe solution techniques varying along several dimensions: diagonalization or dilation methods using approximate or exact transition models; reward-specific vs reward-invariant methods; global vs. local representation construction methods; multiscale vs. flat discovery methods; and finally, orthogonal vs. redundant representation discovery methods. I conclude by describing a number of open problems for future work.

Introduction

In the development of Reinforcement Learning (RL) systems, a significant portion of success is often attributed to the "art" of feature engineering. Human designers typically spend considerable effort manually constructing state spaces, features, and task hierarchies that enable learning algorithms to function effectively. However, this reliance on human-provided knowledge structures creates a bottleneck, particularly as agents encounter increasingly complex and novel environments.

The Representation Discovery Problem addresses this limitation by asking how an agent can autonomously analyze its environment to discover the underlying structures—such as bottlenecks, symmetries, or topological smoothness—that allow for efficient problem compression. This paper provides a comprehensive framework for automating the discovery of functional, state, and temporal abstractions within Markov Decision Processes (MDPs).

A Taxonomy of Abstractions

Representation discovery can be categorized into three primary dimensions based on the type of abstraction being sought:

  1. Functional Abstraction: This involves finding basis functions (e.g., Fourier series or wavelets) that allow a value function to be represented as a linear combination of features. The goal is to find a compact set of functions that can approximate the value of any state.
  2. State Abstraction: This focuses on partitioning the state space into equivalence classes. States are grouped together if they exhibit similar behavior regarding transition dynamics or reward outcomes, effectively reducing the cardinality of the state space.
  3. Temporal Abstraction: This identifies hierarchies of skills or sub-tasks (often referred to as "options"). By discovering meaningful sequences of actions—such as "exiting a room"—an agent can plan over longer time horizons rather than focusing solely on primitive, step-by-step actions.

Mathematical Engines for Discovery

The paper distinguishes between two primary mathematical approaches to generating these representations:

Dilation (Krylov Subspace Methods)

Dilation methods are typically reward-specific. They begin with a specific reward function and "expand" it using successive powers of the transition matrix. This process tracks how rewards "flow" through the state space, identifying features that are highly optimized for a specific goal but potentially less useful if the objective changes.

Diagonalization (Spectral Methods)

Diagonalization methods focus on the intrinsic geometry of the environment, making them reward-invariant. By calculating the eigenvectors of the transition matrix or the Graph Laplacian, these methods reveal the topological structure of the state space. This approach identifies corridors, rooms, and clusters based on the environment's connectivity, providing a foundation for learning any task within that specific domain.

Key Insights and Methodologies

The Geometry of the State Space

A central theme of this research is treating state spaces as graphs or manifolds. By applying spectral graph theory, researchers can derive Proto-Value Functions (PVFs). These are basis functions that are naturally smooth over the environment's topology, ensuring that states that are "close" in terms of transition dynamics have similar representational values.

Multiscale Discovery

Just as signal processing uses wavelets to analyze data at different resolutions, MDPs can be analyzed using diffusion wavelets. This allows for the discovery of structure at multiple spatial and temporal scales, enabling the agent to understand both local nuances and global environmental trends.

Representation Policy Iteration (RPI)

Mahadevan discusses the Representation Policy Iteration framework, which creates a virtuous cycle of improvement. In this framework, an agent alternates between two phases: discovering an improved representation based on its current experience and using that new representation to derive a more effective policy.

Results and Implications

The synthesis of these methods marks a shift from heuristic-based feature design to mathematically rigorous discovery. Key results in the field demonstrate that:

  • Compression: Automated methods can reduce a massive state space $|S|$ to a significantly smaller set of $k$ basis functions ($k \ll |S|$) while maintaining the ability to derive optimal policies.
  • Hierarchy Generation: Identifying "bottleneck" states (such as doorways in a navigation task) provides a sound mathematical basis for automatically generating hierarchical skills.

Challenges and Future Directions

While significant progress has been made, several "grand challenges" remain for the field of representation discovery:

  • Scaling: Spectral methods often involve computationally intensive matrix operations, making them difficult to apply to massive or continuous state spaces without further approximation.
  • Partial Observability: Most current frameworks assume the agent has full knowledge of its state (MDP). Extending these discovery methods to Partially Observable MDPs (POMDPs) remains a complex frontier.
  • Transfer Learning: A major goal is determining how a representation discovered in one environment can be effectively transferred to a different but related domain.
  • Relational Representations: Future work must move beyond vector-based representations to those that can capture the relationships between objects and entities within an environment.

Summary updated

Abstract

Automatically constructing novel representations of tasks from analysis of state spaces is a longstanding fundamental challenge in AI. I review recent progress on this problem for sequential decision making tasks modeled as Markov decision processes. Specifically, I discuss three classes of representation discovery problems: finding functional, state, and temporal abstractions. I describe solution techniques varying along several dimensions: diagonalization or dilation methods using approximate or exact transition models; reward-specific vs reward-invariant methods; global vs. local representation construction methods; multiscale vs. flat discovery methods; and finally, orthogonal vs. redundant representation discovery methods. I conclude by describing a number of open problems for future work.
BibTeX
@inproceedings{mahadevan2010representation,
  author = {Sridhar Mahadevan},
  title = {{Representation Discovery in Sequential Decision Making}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  url = {https://openreview.net/forum?id=SkXdbCldbS},
}
Figure