Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning
This is an incremental contribution that highlights a theoretical gap for researchers in reinforcement learning and kernel methods.
The paper identifies the lack of order optimal regret bounds for kernel-based reinforcement learning as an open problem, noting that existing theoretical results do not adequately address performance guarantees for this non-linear function approximation approach.
Reinforcement Learning (RL) has shown great empirical success in various application domains. The theoretical aspects of the problem have been extensively studied over past decades, particularly under tabular and linear Markov Decision Process structures. Recently, non-linear function approximation using kernel-based prediction has gained traction. This approach is particularly interesting as it naturally extends the linear structure, and helps explain the behavior of neural-network-based models at their infinite width limit. The analytical results however do not adequately address the performance guarantees for this case. We will highlight this open problem, overview existing partial results, and discuss related challenges.