A Bayesian Reinforcement Learning framework Using Relevant Vector Machines

Nikolaos Tziortziotis, Konstantinos BlekasAAAI 2011 · DOI

Abstract

In reinforcement learning (RL), estimating value functions accurately and efficiently is critical for agent performance. While Bayesian methods like Gaussian Process Temporal Difference (GPTD) learning offer principled uncertainty quantification, they suffer from high computational complexity and sensitivity to kernel hyperparameters. This paper introduces a novel Bayesian RL framework leveraging Relevance Vector Machines (RVMs). By reformulating the Bellman equation as a sparse linear regression problem, the proposed method automatically selects essential states and optimizes kernel parameters through a multi-kernel scheme. Experimental results across classic control tasks and real-world robotic platforms demonstrate that this approach achieves superior asymptotic performance and greater robustness compared to traditional GPTD and SARSA methods.

Introduction

Reinforcement Learning (RL) involves an agent learning to make decisions by interacting with an environment to maximize cumulative rewards. Central to this process is the value function, which estimates the expected long-term return from a given state. Bayesian approaches to value function approximation have gained traction because they provide a probabilistic framework that accounts for uncertainty, which is vital for efficient exploration and robust learning.

However, existing Bayesian RL techniques, particularly those based on Gaussian Processes (GPs), face significant scalability and usability hurdles. As the number of observed states grows, the computational cost of GP-based methods increases cubically, making them impractical for long-running tasks or high-dimensional spaces. Furthermore, the performance of kernel-based methods is often tethered to the manual tuning of hyperparameters, such as kernel width, which limits their "out-of-the-box" applicability. This paper addresses these challenges by integrating Relevance Vector Machines (RVMs) into the RL loop.

Problem Statement: Complexity and Sensitivity

The authors identify two primary flaws in standard Gaussian Process Temporal Difference (GPTD) learning:

  1. Computational Complexity: Non-parametric Bayesian methods typically require storing and processing all visited states. This leads to a "memory explosion" where matrix inversions become prohibitively expensive as the agent's experience grows.
  2. Hyperparameter Sensitivity: The effectiveness of a kernel function depends heavily on its parameters (e.g., the scale $\lambda$). In practice, finding the optimal $\lambda$ often requires extensive trial and error or domain-specific expertise, which undermines the goal of autonomous learning.

The RVM-RL Framework

The proposed framework introduces several innovations to overcome the limitations of traditional Bayesian RL.

Sparse Bayesian Learning via RVMs

Unlike Gaussian Processes, which utilize the entire dataset to make predictions, Relevance Vector Machines employ a sparse prior. This mathematical constraint encourages the model to represent the value function using only a small subset of the observed data—the "relevance vectors." By discarding redundant or non-informative states, the RVM maintains a compact model that remains computationally efficient even as the agent continues to learn.

Bellman Equation as Regression

To apply RVMs to RL, the authors reformulate the Bellman equation—the fundamental recursive relationship in RL—into a generalized linear regression problem. By treating the discounted return as a target variable in a probabilistic regression context, the agent can leverage standard Bayesian inference techniques to update its value function estimates.

Automated Multi-Kernel Scheme

To eliminate the need for manual hyperparameter tuning, the authors implement a multi-kernel scheme. Instead of relying on a single kernel with a fixed width, the model uses a mixture of multiple kernels with varying parameters. The framework then employs a convex quadratic programming approach to automatically learn the optimal weights for these kernels during the training process. This allows the algorithm to adapt to the specific geometry of the state space without human intervention.

Online State Dictionary

To facilitate real-time operation, the system utilizes a "dictionary" approach for state management. A new state is only added to the model's active memory if it provides significant novel information that cannot be accurately approximated by the existing set of relevance vectors. This ensures the model's complexity is governed by the underlying task difficulty rather than the duration of the experiment.

Experimental Evaluation

The framework was rigorously tested against standard benchmarks and real-world hardware:

  • Classic Control: In the Cart-pole and Mountain Car environments, the RVM-based approach consistently outperformed Sparse GPTD and SARSA($\lambda$). It achieved higher cumulative rewards and demonstrated faster convergence rates.
  • Robotic Deployment: The algorithm was deployed on a Pioneer/PeopleBot (P3-DX) mobile robot. The framework successfully navigated noisy, real-world conditions, proving that the computational efficiency gained through sparsity is sufficient for real-time robotic control.

Key Insights

The research highlights that sparsity is synonymous with efficiency in Bayesian RL. By focusing only on relevant states, the agent avoids the computational bottlenecks that plague other non-parametric methods. Furthermore, the automated tuning provided by the multi-kernel scheme represents a significant step toward more robust, "plug-and-play" RL algorithms that do not require expert-level parameter adjustment.

Conclusion and Future Work

The RVM-based Bayesian RL framework provides a powerful alternative to GP-based methods, offering a principled way to handle uncertainty while maintaining computational tractability. While the current work focuses on discrete action spaces and value estimation, future research could extend this framework to continuous action spaces and integrate it with uncertainty-aware exploration strategies to further accelerate the learning process. Additionally, optimizing the iterative RVM training process for high-dimensional inputs like raw imagery remains a promising avenue for scaling this technology to more complex domains.

Summary updated

BibTeX
@inproceedings{tziortziotis2011bayesian,
  author = {Nikolaos Tziortziotis and Konstantinos Blekas},
  title = {{A Bayesian Reinforcement Learning framework Using Relevant Vector Machines}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.1609/aaai.v25i1.8031},
}
Figure