Using PCA to Efficiently Represent State Spaces

William Curran, Tim Brys, Matthew E. Taylor, William D. SmartarXiv 2015 · OpenReview

TL;DR

This paper tackles the "curse of dimensionality" in reinforcement learning by using Principal Component Analysis (PCA) to project high-dimensional state spaces into lower-dimensional manifolds. They demonstrate that this approach significantly speeds up learning convergence in the Mario game benchmark, even achieving better performance than full-dimensional learning in some cases, by finding a sweet spot in the convergence-performance trade-off.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents often struggle with high-dimensional state spaces, a problem known as the "curse of dimensionality." This is particularly prevalent in robotics, where the number of joints can lead to an exponential explosion in the state space. Learning optimal control in such environments becomes computationally intractable. While transfer learning and learning from demonstration offer some solutions, they have their own complexities. This paper focuses on a core challenge: how to efficiently represent and learn in these large state spaces.

Methods

The authors propose using Principal Component Analysis (PCA) to reduce the dimensionality of the state space. The core idea is to learn a linear transform from the high-dimensional state space to a lower-dimensional manifold. This transform is learned from demonstration trajectories. During each learning iteration, the agent's current state is projected down to this low-dimensional space. The RL algorithm (a Q(λ)-learner) then operates entirely within this reduced space. This process is illustrated in a flowchart (Figure 1), showing the projection of states down to a low-dimensional representation for learning. The key innovation here is not PCA itself, which is a standard technique, but its direct application during the RL learning cycle to represent states, rather than just for feature extraction.

Datasets

The primary dataset used for evaluation is the "Mario Benchmark Problem," based on an reimplementation of Super Mario Bros. The paper describes the state representation used for Mario, which includes variables like Mario's abilities (jump, shoot), direction, enemy positions, and obstacles. The authors generated procedurally generated levels for their experiments, varying difficulty and Mario's starting mode to ensure generalizability. They also mention using demonstration trajectories to learn the PCA transform.

Key Insights and Ideas

  • The Convergence-Performance Trade-off: The paper highlights a critical trade-off: projecting states to a low-dimensional manifold speeds up learning convergence but might discard important information, potentially leading to suboptimal policies if the manifold is too small.
  • Finding the "Sweet Spot": The research suggests there's an optimal dimensionality where learning is fast and performance is good. They found that learning in as few as 4 dimensions could outperform learning in the full 9-dimensional space, achieving better performance at a faster convergence rate.
  • Feature Importance: Analysis of the principal components revealed that fundamental skills like jumping, ground status, and current direction are heavily represented in the first few components, while features related to specific enemy interactions are in the later components. This suggests that focusing on core skills in lower dimensions is crucial for initial learning.

Key Results

The experiments in the Mario domain showed that:

  • Projecting the state to very low-dimensional manifolds (less than 4 dimensions) led to quick convergence to bad policies.
  • Using manifolds of 4 dimensions or greater resulted in quick convergence to much better policies.
  • Crucially, learning in a 4-dimensional manifold (instead of the full 9 dimensions) not only converged faster but also achieved better performance than learning in the full state space, as shown in Figure 4.
  • Dimensions greater than 5 performed similarly to the full state space.

Limitations and Future Work

The authors acknowledge that their current algorithm assumes all states are important, even if they have high variance but are not crucial for learning. They also stop learning once convergence is reached in the lower-dimensional space, which means that, given infinite time, the higher-dimensional space would eventually converge to better performance.

Future work includes:

  • Performing additional analysis on the current results, varying the amount of training data for PCA and exploring random demonstration data.
  • Improving the converged performance of low-dimensional state representations. They propose an "iterative learning approach" where learning first occurs in an n-dimensional space and then knowledge is transferred to an n+1 dimensional space, hypothesizing this will converge faster than learning entirely in the full space.
  • Investigating mixed resolution function approximation techniques, similar to work by Grzes and Kudenko, to combine fast initial learning with high-quality policy learning.

Summary updated

Abstract

Reinforcement learning algorithms need to deal with the exponential growth of states and actions when exploring optimal control in high-dimensional spaces. This is known as the curse of dimensionality. By projecting the agent's state onto a low-dimensional manifold, we can represent the state space in a smaller and more efficient representation. By using this representation during learning, the agent can converge to a good policy much faster. We test this approach in the Mario Benchmarking Domain. When using dimensionality reduction in Mario, learning converges much faster to a good policy. But, there is a critical convergence-performance trade-off. By projecting onto a low-dimensional manifold, we are ignoring important data. In this paper, we explore this trade-off of convergence and performance. We find that learning in as few as 4 dimensions (instead of 9), we can improve performance past learning in the full dimensional space at a faster convergence rate.
BibTeX
@misc{curran2015using,
  author = {William Curran and Tim Brys and Matthew E. Taylor and William D. Smart},
  title = {{Using PCA to Efficiently Represent State Spaces}},
  year = {2015},
  eprint = {1505.00322},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1505.00322},
}
Figure