Efficient Planning under Partial Observability with Unnormalized Q Functions and Spectral Learning

Tianyu Li, Bogdan Mazoure, Doina Precup, Guillaume Rabusseau

Abstract

Learning and planning in partially-observable domains is one of the most difficult problems in reinforcement learning. Traditional methods consider these two problems as independent, resulting in a classic two-stage paradigm: first learn the environment dynamics and then compute the optimal policy accordingly. This approach, however, disconnects the reward information from the learning of the environment model and can consequently lead to representations that are sample inefficient and time consuming for planning purpose. In this paper, we propose a novel algorithm that incorporate reward information into the representations of the environment to unify these two stages. Our algorithm is closely related to the spectral learning algorithm for predicitive state representations and offers appealing theoretical guarantees and time complexity. We empirically show on two domains that our approach is more sample and time efficient compared to classical methods.

Introduction

In Reinforcement Learning (RL), agents often operate under the assumption of full observability. However, real-world applications typically involve Partially Observable Markov Decision Processes (POMDPs), where agents must make decisions based on noisy or incomplete observations. Planning in these environments is plagued by the "curse of history," where optimal decision-making requires accounting for the entire sequence of past events.

Traditional approaches tackle this through a two-stage process: unsupervised model learning followed by planning (e.g., Value Iteration). This separation is fundamentally inefficient. Because the model-learning stage is agnostic to rewards, it may expend significant computational resources modeling environmental details that are irrelevant to the agent's specific task. This paper introduces a unified approach that leverages reward information directly during the representation learning phase.

Methodology: Unnormalized Q Functions and Spectral Learning

The core innovation of this work is the Unnormalized Q Function (UQF). Unlike standard Predictive State Representations (PSRs) that model probability distributions over future observations, the UQF ($ ilde{Q}$) is defined to be proportional to the standard action-value function ($Q$).

Weighted Finite Automata (WFA) Representation

The authors prove that the UQF can be represented as a Weighted Finite Automaton (WFA). While PSRs are restricted to modeling probabilities, WFAs can represent any real-valued function over sequences. This allows the agent to treat "expected future reward" as a sequence function to be learned directly from data.

Spectral Learning via SVD

To learn this representation, the algorithm employs Spectral Learning. By performing Singular Value Decomposition (SVD) on a "Hankel matrix"—a matrix capturing the relationships between histories and future tests—the method finds a consistent, closed-form solution. This avoids the iterative convergence issues and hyperparameter sensitivity common in gradient-based methods like Deep Q-Networks (DQN). To scale to high-dimensional observation spaces, the authors utilize Matrix Compressed Sensing (Johnson-Lindenstrauss projections) to reduce data dimensionality before the SVD step.

Experimental Evaluation

The proposed method was evaluated on two distinct benchmarks designed to test sample efficiency and scalability:

  1. Grid World: A navigation task with three difficulty levels (Close, Middle, and Far) based on the distance to the goal. The agent's observations are limited to the immediate surrounding walls.
  2. S-PocMan: A large-scale "Stochastic PocMan" domain featuring $10^{56}$ possible states, providing a rigorous test for the algorithm's ability to handle complex, partially observable environments.

Key Results: Efficiency and Speed

In the Grid World experiments, the UQF method demonstrated superior sample efficiency. As shown in the performance plots, the algorithm (labeled "Ours") reaches near-optimal performance with significantly fewer training trajectories than TPSR, CPSR, or DQN baselines.

Performance comparison on Grid World variants. The proposed UQF method (Ours) achieves near-optimal returns with significantly fewer training samples than baselines.

The most dramatic results appeared in the S-PocMan domain. The UQF approach achieved a massive computational speedup, performing planning in just 2 seconds—approximately 200 times faster than the CPSR baseline using 400 fitted-Q iterations, while also yielding higher returns.

Performance and time comparison on the S-PocMan domain. UQF demonstrates a massive speedup and superior returns compared to the CPSR baseline.

Discussion and Future Work

By unifying model learning and planning through reward-aware representations, this approach offers a more stable and theoretically grounded alternative to traditional POMDP solvers. The use of linear algebra (SVD) rather than iterative Bellman updates provides a clear path toward more efficient RL in complex domains.

However, some constraints remain. The current theory requires the spectral radius of transition matrices to be less than 1 to ensure bounded value functions. Additionally, while the UQF learns the value of a fixed sampling policy efficiently, finding the optimal policy still requires an outer loop of policy iteration. Future research may focus on integrating "Q-learning" style updates directly into the spectral framework and exploring the framework's potential for multitask learning.

Summary updated

Abstract

Learning and planning in partially-observable domains is one of the most difficult problems in reinforcement learning. Traditional methods consider these two problems as independent, resulting in a classic two-stage paradigm: first learn the environment dynamics and then compute the optimal policy accordingly. This approach, however, disconnects the reward information from the learning of the environment model and can consequently lead to representations that are sample inefficient and time consuming for planning purpose. In this paper, we propose a novel algorithm that incorporate reward information into the representations of the environment to unify these two stages. Our algorithm is closely related to the spectral learning algorithm for predicitive state representations and offers appealing theoretical guarantees and time complexity. We empirically show on two domains that our approach is more sample and time efficient compared to classical methods.
BibTeX
@inproceedings{li2020efficient,
  author = {Tianyu Li and Bogdan Mazoure and Doina Precup and Guillaume Rabusseau},
  title = {{Efficient Planning under Partial Observability with Unnormalized Q Functions and Spectral Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=6MeqwMphLU},
}
Figure