A Non-Parametric Approach to Approximate Dynamic Programming

Hadrien Glaude, Fadi Akrimi, Geist, Matthieu, Olivier Pietquin

TL;DR

This paper tackles the "curse of dimensionality" in Reinforcement Learning (RL) by proposing a novel combination of the Fitted-Q iteration algorithm with Locally Weighted Projection Regression (LWPR). This approach effectively handles high-dimensional state spaces and irrelevant input features, demonstrating competitive performance on challenging benchmarks.

What Problem Does This Paper Address?

Approximate Dynamic Programming (ADP), a powerful class of RL algorithms, aims to learn optimal control policies for dynamic systems by observing interactions. However, a major hurdle is the "curse of dimensionality," where the complexity of the state space grows exponentially with the number of dimensions, making it intractable to enumerate all possibilities. Existing RL methods struggle to scale to these high-dimensional, continuous state spaces, especially when many dimensions are irrelevant to the control problem. This paper seeks to overcome this scalability limitation.

Methods

The core contribution is the integration of Locally Weighted Projection Regression (LWPR) into the Fitted-Q iteration algorithm.

  • Fitted-Q Iteration: This is a batch-mode ADP algorithm that iteratively approximates the optimal Q-function (which estimates the expected future reward for taking an action in a given state). It uses a supervised learning approach to update the Q-function based on observed transitions (state, action, reward, next state).
  • Locally Weighted Projection Regression (LWPR): This is a non-parametric regression method designed for high-dimensional spaces with potentially redundant or irrelevant features. LWPR uses locally linear models and employs Partial Least Squares (PLS) regression to efficiently handle dimensionality reduction by focusing on a small number of selected input dimensions. It learns by creating "receptive fields" that represent local models, and predictions are made by a weighted combination of these local models.

The authors explore three main configurations:

  1. Fitted-Q + LWPR (constant D): LWPR's distance metric (D) is fixed.
  2. Fitted-Q + LWPR (learning D): LWPR's distance metric (D) is updated during training.
  3. Online Fitted-Q + LWPR (constant D): An online version where the Q-function is updated incrementally at each transition, with a constant D.

Datasets

The paper uses standard benchmarks modified to exhibit larger state spaces:

  • Inverted Pendulum: A classic RL problem where the goal is to balance a pendulum on a cart. The authors introduce noise components to the state space to simulate irrelevant dimensions.
  • Mountain Car: A problem where a car needs to gain momentum by moving back and forth to reach a goal on a hill. This problem is used to test scalability with higher dimensional state spaces.
  • Cartesian Product of Problems: Combinations of simpler problems, including those with noise, to specifically test LWPR's ability to handle irrelevant dimensions.

Key Insights and Ideas

  • LWPR's Dimensionality Reduction is Key: The paper's central idea is that LWPR's ability to locally select relevant input dimensions via PLS regression is crucial for scaling RL to high-dimensional state spaces. This allows the algorithm to effectively ignore irrelevant features.
  • Constant Distance Metric (D) for Stability: The authors found that keeping LWPR's distance metric (D) constant across Fitted-Q iterations led to more stable learning. Updating D introduced instability, likely due to changes in the approximation model's structure.
  • Online Learning Potential: The online version of Fitted-Q with LWPR showed promise for rapid learning but struggled with more complex problems requiring extensive reward propagation.
  • Performance on Noisy/Irrelevant Inputs: The approach demonstrated effectiveness in solving problems with irrelevant input dimensions, as shown by the inverted pendulum with noise components.

Key Results

  • Competitive Performance: The proposed approach achieved competitive results on the tested benchmarks, learning effective policies even with a relatively small training set.
  • Inverted Pendulum: All three versions of the algorithm performed well, with the constant D versions achieving stable learning. The online version was particularly fast.
  • Mountain Car: The "Fitted-Q + LWPR" with constant D showed good performance, achieving policies that solved the problem in a significantly lower number of steps compared to state-of-the-art methods. Learning D led to instability.
  • Noise Problems: The algorithm successfully solved the inverted pendulum problem with multiple noise components, demonstrating its ability to handle irrelevant dimensions.

Limitations and Future Work

  • Stability Issues with Learning D: The authors acknowledge that updating LWPR's distance metric (D) during Fitted-Q iterations can lead to instability. They suggest that fixing the structure of receptive fields after a certain number of iterations might mitigate this.
  • Online Version Challenges: While promising, the online version struggled with complex problems requiring long-term reward propagation, potentially due to competition between LWPR's and Fitted-Q's learning mechanisms.
  • Theoretical Convergence: A theoretical proof of convergence, especially for the case where D is not updated, is needed.
  • Continuous Actions: The current work focuses on discrete actions. Future work could explore including action dimensions in the regression for continuous action spaces or using action space clustering.
  • Initialization Heuristics: Developing better heuristics for initializing D and P (penalty term) could improve performance.
  • Real-World Applications: The authors express interest in testing this approach on more complex, real-world problems, particularly in robotics.

Summary updated

Abstract

Approximate Dynamic Programming (ADP) is a machine learning method aiming at learning an optimal control policy for a dynamic and stochastic system from a logged set of observed interactions between the system and one or several non-optimal controlers. It defines a class of particular Reinforcement Learning (RL) algorithms which is a general paradigm for learning such a control policy from interactions. ADP addresses the problem of systems exhibiting a state space which is too large to be enumerated in the memory of a computer. Because of this, approximation schemes are used to generalize estimates over continuous state spaces. Nevertheless, RL still suffers from a lack of scalability to multidimensional continuous state spaces. In this paper, we propose the use of the Locally Weighted Projection Regression (LWPR) method to handle this scalability problem. We prove the efficacy of our approach on two standard benchmarks modified to exhibit larger state spaces. I.
BibTeX
@inproceedings{glaude2011non,
  author = {Hadrien Glaude and Fadi Akrimi and Geist, Matthieu and Olivier Pietquin},
  title = {{A Non-Parametric Approach to Approximate Dynamic Programming}},
  booktitle = {ICMLA},
  year = {2011},
  url = {https://openreview.net/forum?id=nw51HSV2dDt},
}
Figure