Learning and Planning with Timing Information in Markov Decision Processes

Pierre-Luc Bacon, Borja Balle, Doina PrecupUAI 2015 · OpenReview

Introduction

In traditional reinforcement learning (RL), defining an agent's "state" is a fundamental challenge. Most systems rely on high-dimensional sensor data or hand-crafted coordinates, such as GPS or joint angles. However, these representations are often computationally expensive to process and difficult to learn from raw data, especially for low-power devices like simple vacuum robots or smartphones.

This paper proposes a paradigm shift: instead of modeling the objective world, an agent can model its own capabilities through a "subjective" representation. Specifically, the authors introduce Option Duration Models (ODMs), which use the predicted duration of extended actions as a compact proxy for the environment's state. By focusing on how long an action takes to complete, an agent can effectively navigate and plan without traditional spatial sensors.

The Framework: Option Duration Models

The research combines two established frameworks to create a novel approach to state representation:

  1. The Options Framework: This allows for "temporally extended actions" or macro-actions. Instead of primitive steps (e.g., "move forward 1cm"), the agent uses options like "move North until hitting a wall."
  2. Predictive State Representations (PSRs): Unlike Hidden Markov Models that rely on latent states, PSRs represent the current state as a vector of predictions about future observations.

In an ODM, the "observations" are the durations of these options. The authors prove that the probability distribution of option durations can be represented as a linear PSR. This means that if a robot knows that moving "North" usually takes five seconds before a collision, that duration itself serves as a powerful indicator of its current location relative to the environment's boundaries.

Methodology: Spectral Learning and Planning

To learn these models from data, the authors employ a spectral learning algorithm. This process involves several key steps:

  • Hankel Matrices: The agent constructs a matrix of joint probabilities between "past" sequences of durations and "future" sequences.
  • Singular Value Decomposition (SVD): By applying SVD to the Hankel matrix, the agent finds a low-rank representation of the dynamics. This ensures the model is both statistically consistent and computationally efficient.
  • Fitted-Q Iteration (FQI): Once the ODM is learned, the resulting state vectors are used as features for a standard RL algorithm. FQI allows the agent to derive an optimal policy based on the timing-based state representation.

Experimental Evaluation

The researchers evaluated ODMs in two distinct environments to test both theoretical consistency and practical robustness:

Synthetic Gridworld

This 4-connected grid served as a proof-of-concept. The agent moved in cardinal directions, with options defined as moving until an obstacle was reached. The results confirmed that the spectral learning algorithm could successfully recover environment dynamics. Notably, the model's rank was found to be approximately $O(\sqrt{n})$, where $n$ is the number of physical states, suggesting that timing models are significantly more compact than full environment models.

Simulated Robot (Box2D)

A more rigorous test was conducted using a circular differential wheeled robot in a continuous Box2D physics environment. This setup included non-linear dynamics, collisions, and friction. Despite the noise inherent in continuous physics and imperfect controllers, the ODM-based planner recovered a near-optimal navigation policy using only 1,000 episodes. This demonstrated that timing information alone is sufficient for complex navigation tasks.

Key Insights

  • Computational Efficiency: Measuring time requires virtually no specialized hardware and minimal processing power compared to LIDAR or computer vision.
  • Affordances as State: The model treats state as a set of "affordances." If an option is predicted to last a significant amount of time, it is considered "available." This mirrors psychological theories of how biological agents perceive their surroundings.
  • Model Compactness: The size of an ODM is independent of the number of primitive actions, making it highly scalable for complex systems.

Conclusion and Future Work

The paper demonstrates that timing information provides a robust, low-cost, and compact representation for learning and planning in MDPs. While the current results are promising, the authors identify several avenues for future research, including tightening the theoretical bounds on the number of states required and developing specialized planning algorithms that can further exploit the unique structure of ODMs. Ultimately, this work suggests that for many robotic applications, the clock may be a more important sensor than the camera.

Summary updated

BibTeX
@inproceedings{bacon2015learning,
  author = {Pierre-Luc Bacon and Borja Balle and Doina Precup},
  title = {{Learning and Planning with Timing Information in Markov Decision Processes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=a5sMVkOT8f},
}
Figure