Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm
This work addresses the challenge of efficient and reliable function approximation in reinforcement learning for scenarios requiring long-term average rewards, offering theoretical guarantees that could benefit algorithm design in continuous or high-dimensional state spaces.
The paper tackles the problem of reinforcement learning in the infinite horizon average reward setting using kernel-based function approximation, proposing an optimistic algorithm that achieves no-regret performance guarantees and derives a novel confidence interval for kernel-based value function prediction.
Reinforcement learning utilizing kernel ridge regression to predict the expected value function represents a powerful method with great representational capacity. This setting is a highly versatile framework amenable to analytical results. We consider kernel-based function approximation for RL in the infinite horizon average reward setting, also referred to as the undiscounted setting. We propose an optimistic algorithm, similar to acquisition function based algorithms in the special case of bandits. We establish novel no-regret performance guarantees for our algorithm, under kernel-based modelling assumptions. Additionally, we derive a novel confidence interval for the kernel-based prediction of the expected value function, applicable across various RL problems.