Research map / Reinforcement learning / MDPs and planning

Reward-Free Kernel-Based Reinforcement Learning

ICML 2024 · Reinforcement learning › MDPs and planning · approach: Policy optimization theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a reward-free RL algorithm for kernel-based MDPs with polynomially decaying kernel eigenvalues (Matérn, NT), using an uncertainty-based hypothetical reward and adaptive domain partitioning to get order-optimal sample complexity in epsilon.

Problem

Sample-efficient exploration for reward-free RL when transition models lie in an RKHS with non-smooth kernels (e.g., Matérn, Neural Tangent), where prior kernel results only covered very smooth, exponentially decaying eigenvalue kernels.

Approach

Explore using a hypothetical reward equal to kernel-regression posterior standard deviation, run optimistic least-squares value iteration with kernel ridge regression restricted to adaptively partitioned state-action subdomains, and plan with the tightest-confidence partition per point.

Key results

• Achieves exploration sample complexity of Õ((H^3/ε)^(2+2d/α)) for kernels with polynomial eigendecay, covering Matérn and NT kernels.
• For Matérn kernels the sample complexity becomes Õ((H^3/ε)^(2+d/ν)), matching the Ω((1/ε)^(2+d/ν)) kernel-bandit lower bound up to log factors in ε.
• Prior work (Qiu et al., 2021) yields unbounded sample complexity for many Matérn parameters, e.g., when ν < d(d+1)/2.

Limitations

• Dependence on episode length H is not shown to be optimal; left unresolved.
• Runtime is high (O(HN^4 + H|A|N^3)), with no empirical experiments reported.
• Analysis is theoretical only; no experimental validation.

Experimental setup

Metrics: sample complexity (exploration episodes for epsilon-optimal

Baselines: Qiu et al. (2021) Yeh et al. (2023) Wagenmaker et al. (2022) Ménard et al. (2021)

Builds on: Vakili & Olkhovskaya (2023) domain partitioning Qiu et al. (2021) kernel reward-free RL Yeh et al. (2023) generative oracle kernel RL Janz et al. (2020) partitioned kernel bandits

Closest papers by meaning

• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game (ICML 2021 · similarity 0.94)
• Provably Efficient Reinforcement Learning with Kernel and Neural Function Approximations (NeurIPS 2020 · similarity 0.93)
• Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm (NeurIPS 2024 · similarity 0.92)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis (ICML 2021 · similarity 0.91)
• Reward-Free Exploration for Reinforcement Learning (ICML 2020 · similarity 0.91)
• Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization (ICML 2024 · similarity 0.89)