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 classical two-stage paradigm: first learn the environment dynamics and then plan accordingly. This approach, however, disconnects the two problems and can consequently lead to algorithms that are sample inefficient and time consuming. In this paper, we propose a novel algorithm that combines learning and planning together. 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 in environments where they cannot observe the full state of the system, such as a robot with limited sensor range. These scenarios are modeled as Partially Observable Markov Decision Processes (POMDPs). Traditionally, solving POMDPs involves a two-stage process: first, learning a model of the environment's dynamics, and second, using that model to plan optimal actions.
This decoupled approach suffers from significant drawbacks. Learning the complete dynamics of an environment is computationally expensive and often ignores the reward signal until the planning phase. This leads to the "curse of dimensionality" and "curse of history," making planning in complex environments nearly impossible for classical methods.
Methodology: Unified Learning and Planning
The proposed approach shifts the focus from learning general dynamics to learning a goal-oriented representation.
Unnormalized Q Function (UQF)
Instead of calculating the standard Action-Value function ($Q$), which requires knowing the probability distribution over states, the authors define an Unnormalized Q Function ($\tilde{Q}$). This function is proportional to the standard $Q$ function but integrates reward information directly into the state representation, making it significantly easier to compute.
Spectral Learning and Weighted Finite Automata (WFAs)
The UQF is represented using Weighted Finite Automata (WFAs). Unlike standard models that only handle probabilities, WFAs can model arbitrary real-valued functions. The parameters of the WFA are learned using Spectral Learning—a non-iterative technique involving Singular Value Decomposition (SVD) of a "Hankel matrix" (a table of past histories and future tests). This allows for learning in a single step, avoiding the local optima issues common in iterative methods like Expectation-Maximization (EM).
Scalability via Compressed Sensing
To handle high-dimensional data in complex environments, the algorithm employs matrix compressed sensing (specifically Johnson-Lindenstrauss projections). This projects data into a smaller, manageable space while preserving the essential structure required for learning.
Experimental Evaluation
The researchers evaluated the UQF approach on two primary benchmarks: a Toy Grid World navigation task and a complex S-PocMan domain.
Toy Grid World
In the Grid World task, an agent must navigate to a goal while only observing adjacent walls. Three variants—Close, Middle, and Far—were tested to vary the difficulty based on the starting distance from the goal.
As shown in the figure above, the UQF method ("Ours") consistently outperforms baseline methods like TPSR and CPSR, reaching near-optimal performance with significantly fewer training samples.
S-PocMan
S-PocMan is a challenging version of Pacman with a massive state space ($10^{56}$ states) and sparse observations. In this domain, the UQF method demonstrated remarkable speed, running approximately 200 times faster than the CPSR + fitted-Q baseline. While the baseline required nearly 500 seconds to converge, the UQF method achieved results in just 2 seconds.
Key Insights and Conclusion
By treating the Q-function as a learnable entity via spectral methods, the UQF algorithm bypasses the need for explicit environment modeling. This reward-aware representation ensures that the agent's internal state is optimized for maximizing returns rather than just predicting future observations.
While the method shows great promise in discrete domains, future work includes establishing formal convergence guarantees for policy iteration and extending the framework to continuous control environments. The efficiency and sample-effectiveness of this unified approach represent a significant step forward in solving complex partially observable planning problems.
Summary updated