Approximate Kalman Filter Q-Learning for Continuous State-Space MDPs

Charles Tripp, Ross D. ShachterUAI 2013

TL;DR

This paper introduces Approximate Kalman Filter Q-Learning (AKFQL), a novel algorithm for learning optimal policies in Markov Decision Processes (MDPs) with continuous state spaces. AKFQL offers a significant speedup over existing methods by simplifying the Kalman filter update, achieving linear complexity while maintaining competitive performance.

What Problem Does This Paper Address?

Learning optimal policies for Markov Decision Processes (MDPs) is a fundamental challenge in artificial intelligence, especially when dealing with continuous state spaces. Traditional Q-learning methods struggle with continuous states, often requiring discretization or complex function approximation. While Kalman Filter Q-Learning (KFQL) offers a principled Bayesian approach to estimate Q-values using basis functions, its quadratic complexity per update makes it computationally expensive. This paper aims to bridge this gap by developing a more efficient approximate version of KFQL that retains the benefits of Bayesian estimation while reducing computational cost.

Methods

The core contribution is the Approximate Kalman Filter Q-Learning (AKFQL) algorithm. It builds upon the Kalman Filter Q-Learning (KFQL) framework, which models the weights of basis functions as a multivariate Gaussian distribution. KFQL uses a Kalman filter to update the mean and covariance of this distribution based on observed Q-learning updates.

The key innovation in AKFQL is the simplification of the Kalman filter update by ignoring the off-diagonal elements of the covariance matrix. This approximation reduces the update complexity from quadratic to linear in the number of basis functions. This makes AKFQL computationally comparable to Projected TD-Learning (PTD) methods, which are known for their linear complexity but lack the Bayesian uncertainty estimation of KFQL.

The paper also discusses various heuristic methods for computing the sensor noise, which plays a role similar to the learning rate in TD learning. These include "max," "average," and "policy" methods, with the average and policy methods showing slightly better performance in experiments.

Datasets

The paper evaluates its methods on three standard benchmarks:

  • Cart-Pole: A classic control problem involving balancing a pole on a cart.
  • Cashier's Nightmare: An extension of the multi-armed bandit problem with a queueing structure.
  • Car-Hill: A continuous state space control problem where a car needs to reach a mountain summit.

The authors note that these are standard benchmarks and do not introduce new datasets.

Key Insights and Ideas

  • The trade-off between Bayesian uncertainty and computational complexity: KFQL provides a rich probabilistic model but is computationally expensive. AKFQL strikes a balance by approximating the covariance, achieving linear complexity while still leveraging some of the Bayesian benefits.
  • AKFQL's surprising long-term performance: Despite its approximation, AKFQL often outperforms KFQL in the long run, suggesting that KFQL might be overfitting due to its more complex model.
  • Sensor noise selection matters: While the choice of sensor noise heuristic has a small effect, some methods (average and policy) appear to perform slightly better than others (max and Boltzmann) on the Cart-Pole task.
  • Linear complexity is key for practical performance: AKFQL's linear update complexity, similar to PTD, allows for more updates within a given time budget, often leading to better policies than KFQL, which has quadratic complexity.

Key Results

  • Cart-Pole: AKFQL provides a significant speedup (100-5000 times) over PTD.
  • Cashier's Nightmare and Car-Hill: KFQL suffered from numerical instability, likely due to underestimating variance, leading to slow policy changes. AKFQL, however, performed well on these tasks, often outperforming KFQL.
  • General Performance: AKFQL consistently shows large benefits over PTD across all tested applications.

Limitations and Future Work

  • Numerical Instability in KFQL: The paper notes that KFQL can suffer from numerical instability, particularly on the Cashier's Nightmare and Car-Hill problems, possibly due to underestimating variance. Increasing sensor noise can mitigate this but not always eliminate it.
  • Approximation in AKFQL: AKFQL's approximation of ignoring off-diagonal covariance elements is a simplification. The authors suggest that further research could explore other approximation techniques for the Kalman filter, such as fixed-rank approximations or particle filtering.
  • Policy Iteration: The authors suggest that a similar Kalman filter model could be applied to perform policy iteration directly, rather than Q-learning.
  • Dependence on Basis Functions: Like other basis function methods, the performance of AKFQL is dependent on the choice of basis functions. The paper mentions that finding a good set of basis functions remains a challenge.
  • Exploration vs. Exploitation: The paper focuses on policy generation rather than on-line performance, meaning exploration strategies are not a primary concern. Future work could investigate how AKFQL performs in true on-line learning scenarios.

Summary updated

BibTeX
@inproceedings{tripp2013approximate,
  author = {Charles Tripp and Ross D. Shachter},
  title = {{Approximate Kalman Filter Q-Learning for Continuous State-Space MDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
}
Figure