Abstract Kernel methods have been successfully applied to reinforcement learning problems to address some challenges such as high dimensional and continuous states, value function approximation and state transitions. However, most existing kernel-based reinforcement learning algorithms are batch-based, which can be computationally expensive and lack the ability to adapt to changes in the environment in real-time. This paper introduces an online version of the Relative Entropy Policy Search (REPS) algorithm using Reproducing Kernel Hilbert Space (RKHS) embeddings. By leveraging Reduced Rank Approximation and recursive update techniques, the proposed algorithm significantly reduces computational complexity while maintaining the stability and flexibility of the original REPS-RKHS framework.
Introduction
Reinforcement Learning (RL) in high-dimensional, continuous state spaces is notoriously difficult due to two major hurdles: function approximation and update stability. Representing complex value functions without manual feature engineering is a challenge, and greedy policy updates often lead to performance oscillations or "catastrophic forgetting."
Relative Entropy Policy Search (REPS) mitigates these issues by constraining policy updates via KL-divergence, ensuring the agent's behavior does not change too drastically between iterations. While REPS-RKHS further enhances this by using kernels to represent functions implicitly, its original batch formulation suffers from a cubic computational cost ($O(n^3)$). This paper proposes an online REPS-RKHS algorithm that enables continuous learning from individual interactions with a significantly reduced computational footprint.
Methodology
The core innovation of Online REPS-RKHS is the transition from batch processing to incremental updates using two primary techniques:
- Reduced Rank Approximation (RRA): Instead of utilizing the full set of $n$ samples for the kernel matrix, the algorithm selects a smaller subset of $m$ "regressors" ($m \ll n$). This reduces the dimensionality of the optimization problem.
- Recursive Updates: By applying the Woodbury Matrix Identity and LU decomposition, the authors derived a method to update model parameters (the $\Pi$ and $\Xi$ matrices) incrementally. This allows the model to be updated in constant time relative to the total number of samples upon receiving a new $(s, a, s', R)$ tuple.
- Non-parametric Policy Generation: A Gaussian Process-based approach (Subset of Regressors) is used to derive a generalized policy applicable to previously unvisited states.
Experimental Evaluation
The algorithm was benchmarked against the standard batch REPS-RKHS on three classic RL tasks: the Toy MDP (a 1D Markov chain), the Mountain Car problem, and the Under-powered Pendulum Swing-Up. Notably, the pendulum task was tested in both low-dimensional (angles/velocities) and high-dimensional (raw images) configurations to test the kernel's ability to handle raw sensory input.
Key Results and Discussion
The online formulation demonstrated superior performance across several metrics. Most notably, the computational scaling was drastically improved. As shown in Figure 3, the batch version's running time grows cubically with sample size, while the online version maintains a much more manageable growth rate, especially when the number of regressors $m$ is kept small.
In terms of learning efficiency, the online algorithm reached near-optimal rewards significantly faster than its batch counterpart. In the Toy MDP and Mountain Car tasks, the continuous adaptation allowed the agent to capture dynamics and improve its policy with fewer total roll-outs. As seen in Figure 1, the online version achieves a stable, high average reward much earlier than the batch method.
Furthermore, the algorithm proved robust to high-dimensional sensory input. In the pendulum swing-up task using raw images, the RKHS embeddings successfully extracted relevant features for control without manual engineering, outperforming the batch version which often failed to converge within the sample limit.
Conclusion and Future Work
Online REPS-RKHS provides a scalable and stable framework for reinforcement learning in continuous domains. By reducing complexity from $O(n^3)$ to $O(m^2)$, it enables real-time adaptation and feature-free learning from high-dimensional data. While the current implementation uses a fixed subset of regressors, future work will focus on adaptive regressor selection to ensure the basis functions remain relevant as the agent explores new regions of the state space.
Summary updated