Research map / Bandits and online learning / RL theory and MDPs
No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes
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.
Proves a no-regret bound O~(sqrt(KH Gamma(KH))) for Thompson sampling in episodic finite-horizon MDPs with joint multi-output GP priors over rewards and transitions, and validates it on synthetic GP-sampled and sparse navigation tasks.
Problem
Theoretical regret guarantees for Thompson sampling in continuous-state episodic reinforcement learning, where the recursive structure of value functions and correlated reward/transition outputs complicate analysis.
Approach
Runs TS in episodic MDPs by sampling reward and transition functions jointly from a multi-output GP posterior and acting greedily w.r.t. the sampled proxy value; the analysis adds high-probability confidence bounds for compositions v(f(z)) via Taylor expansion, recursive UCB/LCB value bounds, and a multi-output elliptical potential lemma with delayed updates.
Key results
- Cumulative regret grows sublinearly across RBF and Matern kernels in GP-sampled MDPs (K=1000 episodes, H=20, 200 trials), with RBF lowest regret.
- In sparse navigation and maze tasks, RBF accumulates regret faster than Matern kernels, and Matern 1.5 with LMC substantially reduces regret vs. without LMC in the maze.
- Theoretical regret bound O(log(Td/delta) sqrt(T Gamma(T))) with Matern giving T^((nu+d)/(2nu+d)) and RBF giving sqrt(T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RBF instead of Matérn kernels (ablation) | RL-GPS · GP-sampled synthetic MDPs | cumulative regret | Helped |
| Use a smoother kernel (RBF or Matérn ν=2.5) instead of Matérn ν=1.5 (ablation) | RL-GPS · GP-sampled synthetic MDPs | cumulative regret | Helped |
| Use Matérn kernels instead of RBF (ablation) | RL-GPS · Sparse navigation and sparse maze | cumulative regret | Helped |
| Add LMC output-correlation modeling (ablation) | RL-GPS with Matérn 1.5 · Sparse maze | cumulative regret | Helped |
Limitations
- Relies on Gaussian joint prior assumption over rewards and transitions, which may not hold in general.
- Requires value functions to be twice differentiable with bounded gradients and Hessians; excludes discontinuous or non-smooth dynamics.
- Restricted to finite-horizon episodic MDPs; infinite-horizon extension left open.
Experimental setup
Datasets: synthetic GP-sampled MDPs (LMC sampled) sparse navigation grid and maze environments
Benchmarks: synthetic GP-sampled MDPs sparse navigation task sparse maze
Metrics: cumulative regret
Baselines: RBF kernel Matern 2.5 kernel Matern 1.5 kernel Matern 1.5 without LMC
Builds on: posterior sampling for reinforcement learning kernelized Thompson sampling regret analysis linear model of coregionalization
Closest papers by meaning
- On Regret Bounds of Thompson Sampling for Bayesian Optimization (ICML 2026 · similarity 0.92)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.89)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.89)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.89)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.88)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.