No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes

AI summary

Overview

• Research area: Reinforcement learning theory — regret analysis of Thompson sampling in continuous-state, finite-horizon episodic Markov Decision Processes (MDPs), with Gaussian process (GP) models of rewards and transitions.
• Technical level: Advanced. The paper is a theoretical machine learning paper relying on Gaussian process theory, Bellman recursion, confidence-bound arguments, and information gain.
• Scope in one sentence: It proves a high-probability sublinear regret bound of 𝒪̃(√(KH Γ(KH))) for a Thompson-sampling-style algorithm (RL-GPS) that jointly models rewards and transitions with a multi-output Gaussian process over K episodes of horizon H, and validates the scaling with synthetic and navigation-style experiments.
• Identifiers: arXiv:2510.20725v1 [cs.LG], 23 Oct 2025, license CC BY 4.0. Authors: Jasmine Bayrooti (University of Cambridge), Sattar Vakili (MediaTek Research), Amanda Prorok (University of Cambridge), Carl Henrik Ek (University of Cambridge and Karolinska Institutet).

What This Paper Is About

Thompson sampling is a widely used strategy for balancing exploration and exploitation: the agent samples a model from a posterior and acts optimally under that sampled model. Theory for Thompson sampling is well developed in bandit problems but remains limited in reinforcement learning, especially when the environment is continuous and the state-action space is not discrete. This paper closes part of that gap by analyzing Thompson sampling in episodic, finite-horizon MDPs where both the reward function and the state-transition function are modeled jointly as a single multi-output Gaussian process, and by proving that the resulting algorithm incurs regret that grows sublinearly in the total number of steps.

Key Contributions

1. A no-regret guarantee for RL-GPS. The authors introduce an approach they call Reinforcement Learning with GP Sampling (RL-GPS), a value-iteration-based form of Thompson sampling with a multi-output GP prior over the joint reward-and-transition function. They prove that, with probability 1 − δ, regret is 𝒪(log(Td/δ) √(T Γ(T))) with T = KH, where Γ(·) captures the complexity of the GP model. Sublinear regret in K means RL-GPS asymptotically matches the optimal policy.

2. Confidence bounds for composed and recursive GPs. Theorem 1 provides high-probability bounds on functions of the form g(z) = v(f(z)), where f is a multi-output GP and v is a twice-differentiable value function with bounded gradient norm u_G and bounded Hessian operator norm u_H. This addresses the fact that the optimal value function is a recursive composition of GPs and is therefore not itself a GP. Corollary 1 then turns these into high-probability confidence intervals for recursive value functions, linking the sampled proxy value functions used by Thompson sampling to the true value functions.

3. A multi-output elliptical potential lemma (Lemma 1). The classical elliptical potential lemma bounds the sum of sequential GP posterior variances by a log-determinant term. The authors generalize it to vector-valued functions, summing ||σ_{t−1}(z_t)||² over t = 1, …, T and bounding it by C·I_T with C = 2 / log(1 + λ⁻²). Applying the scalar version independently per output would make regret scale linearly with the state dimension d_S; the new lemma exploits inter-output correlations to avoid this. A further delayed-update lemma (Lemma 2) accounts for the fact that model updates happen at the end of episodes rather than at every step, improving the dependence on the horizon H.

4. Controlled empirical validation. Synthetic GP-sampled MDP experiments and sparse navigation/maze experiments confirm sublinear cumulative regret, and show that kernel smoothing affects learning speed in the direction the theory predicts.

Main Findings

• No-regret behavior: The main theorem (Theorem 2) gives Regret(T) = 𝒪(log(Td/δ) √(T Γ(T))) with probability 1 − δ, where Γ(T) = sup over the visited points z_{h,k}, h ∈ [H], k ∈ [K], of I_T and I_T = ½ log det(I_Td + (1/λ²) K_T). The bound holds uniformly across problem instances, because it is a high-probability bound rather than a Bayesian regret bound averaged over a prior.

• Concrete rates for common kernels: For a Matérn kernel with smoothness parameter ν > 1, the bound becomes 𝒪̃(T^{(ν+d)/(2ν+d)}); for the radial basis function (RBF) kernel it becomes 𝒪̃(√T).

• Bandit case is recovered: Setting H = 1 degenerates the episodic MDP to GP bandits, i.e., Bayesian optimization, with T = K. The bound then becomes 𝒪(log(T/δ) √(T Γ(T))), matching standard regret bounds in Bayesian optimization.

• Regret decomposition: The analysis splits per-step regret into an immediate regret term (which depends on Thompson sampling) plus a recursive term carrying uncertainty through the transition model. The recursive term is unrolled over h = 1, …, H and bounded via the confidence width ξ_k(s, a), which combines the reward posterior standard deviation σ_{R,k}(s,a), the transition posterior standard deviation norm ||σ_{S,k}(s,a)||, and its square.

• Kernel choice determines empirical regret in GP-sampled environments: In an experiment with K = 1000 episodes, H = 20, state space S = [0,1]² and action space A = [0,1] (each dimension discretized into 25 equally sized bins), the RBF kernel achieved the lowest cumulative regret, followed by Matérn with ν = 2.5, then Matérn with ν = 1.5. Results were averaged over 200 randomly sampled environments; cumulative regret grew sublinearly for all kernels.

• Sparse navigation: In a task with S = [0,1]² discretized into 25 bins per dimension and 9 discrete actions (cardinal, diagonal, or stationary), the agent received a reward of +1 when within 0.1 of the destination and a penalty of −0.01 otherwise. Across K = 1000 episodes over 200 trials, cumulative regret grew sublinearly, both for free movement in the grid and for constrained navigation through a maze.

• Tighter than a naive multi-output treatment: Because the elliptical potential lemma leverages correlation structure across output dimensions, the resulting regret guarantee is tighter than applying the standard scalar bound independently to each output.

• Milder assumptions than prior work: Unlike Posterior Sampling for Reinforcement Learning (PSRL), which assumes finite state and action spaces and gives Bayesian regret 𝒪̃(H√(SAT)), and unlike linear MDP methods that assume linearity in both rewards and transitions, or RKHS-based approaches that treat each transition component as a fixed independent function, this work assumes only a known matrix-valued kernel GP prior plus bounded first and second derivatives of the value functions (Assumption 2).

Methodology in Plain English

The authors study an agent that interacts with an environment in K episodes, each of length H. At the start of each episode, the agent samples a realization of the reward function and the transition function from a Gaussian process posterior built from everything it has observed so far. It then performs backward induction to compute value functions under that sampled model, and follows the greedy policy implied by those sampled values for the whole episode. At the end of the episode, the collected transitions and rewards are added to the data and the posterior is updated.

Regret is defined as the cumulative gap between the value of the optimal policy and the value of the policy actually executed, summed over episodes. To bound it, the authors:

1. Decompose per-step regret into an immediate part and a recursive part.
2. Build confidence bounds around the proxy value functions and the true value functions (Definition 1 and Corollary 1), so that sampled values can be compared against true values.
3. Use a Taylor expansion to handle the fact that value functions are compositions of the GP with a nonlinear value function, with the gradient bound u_G controlling the first-order term and the Hessian bound u_H controlling the second-order term.
4. Accumulate the confidence widths over all steps and episodes, then convert the sums of posterior variances into an information-gain term using a new multi-output elliptical potential lemma.
5. Account for the fact that within an episode all observations are added to the GP in a batch, by using tools from GP analysis with batch observations and delayed feedback.

Empirically, the authors build synthetic environments whose ground-truth reward and transition functions are themselves sampled from a sparse multi-output GP using the linear model of coregionalization (LMC), compute the optimal value function by finite-horizon value iteration, run the algorithm, and plot cumulative regret averaged across many random environments.

Why This Matters

• Impact on research: Thompson sampling is popular in practice but has weaker theoretical foundations than optimistic (upper-confidence-bound) methods in reinforcement learning. This paper supplies a no-regret guarantee for a Thompson-sampling method in continuous-state, finite-horizon MDPs under GP models, and contributes reusable technical tools — confidence bounds for composed GPs, a multi-output elliptical potential lemma, and a delayed-update lemma — that other analyses of GP-based RL can build on. It also shifts the guarantee from Bayesian regret (averaged over a problem prior) to a high-probability bound that holds uniformly.

• Real-world applications:

  • Robotics, where continuous state and action spaces and costly data collection make calibrated uncertainty and sample efficiency valuable.
  • Chip design and other engineering design loops, where sequential decisions under uncertainty drive expensive evaluations.
  • Bayesian optimization and experimental design pipelines, since the H = 1 case of this framework reduces directly to GP bandits.
  • Navigation and control tasks with sparse rewards, such as the sparse navigation and maze experiments in the paper.

• Industry relevance: The work was carried out with an industrial research affiliation (MediaTek Research) alongside academic groups, reflecting interest from industry in principled, uncertainty-aware sequential decision-making, particularly in settings with continuous inputs and limited interaction budgets.

Future Directions

• Sample and complexity dependence: The bound depends on Γ(T), which is a supremum of the information gain over visited points. Refining or removing this supremum, and tightening the polynomial dependence on dimensionality d, are natural follow-ups.
• Beyond the smoothness assumptions: Assumption 2 requires twice-differentiable value functions with bounded gradient and Hessian norms. Relaxing this to less smooth value functions, for example those arising from rougher kernels or discontinuous reward structures, is an open question.
• Broader MDP settings: The analysis is restricted to episodic, finite-horizon MDPs. Extending no-regret Thompson sampling guarantees to infinite-horizon discounted or average-reward settings with GP models is left open.
• Kernel and model selection in practice: The experiments show that performance depends strongly on kernel choice (RBF versus Matérn with ν = 2.5 or ν = 1.5, and smooth versus sparse environments). Developing practical selection or adaptation procedures for multi-output kernels, including the LMC structure used here, is a natural applied direction.
• Additional experimental detail: The provided paper content is truncated partway through the description of the multi-output kernel structure experiments, so the full reported results for the sparse navigation and maze settings beyond their sublinear regret growth are not available in this text.

Target Audience

This paper is aimed at theoretical machine learning researchers working on reinforcement learning theory, bandit algorithms, Gaussian process models, and Bayesian optimization. It is most useful to readers already comfortable with regret analysis, GP posterior computations, and information-gain arguments. Practitioners who apply Thompson sampling or GP-based model-based RL to continuous control problems will also benefit, particularly from the empirical findings on kernel choice, but the main content assumes an advanced mathematical background.

Authors’ abstract

Thompson sampling (TS) is a powerful and widely used strategy for sequential decision-making, with applications ranging from Bayesian optimization to reinforcement learning (RL). Despite its success, the theoretical foundations of TS remain limited, particularly in settings with complex temporal structure such as RL. We address this gap by establishing no-regret guarantees for TS using models with Gaussian marginal distributions. Specifically, we consider TS in episodic RL with joint Gaussian process (GP) priors over rewards and transitions. We prove a regret bound of $\mathcal{\tilde{O}}(\sqrt{KHΓ(KH)})$ over $K$ episodes of horizon $H$, where $Γ(\cdot)$ captures the complexity of the GP model. Our analysis addresses several challenges, including the non-Gaussian nature of value functions and the recursive structure of Bellman updates, and extends classical tools such as the elliptical potential lemma to multi-output settings. This work advances the understanding of TS in RL and highlights how structural assumptions and model uncertainty shape its performance in finite-horizon Markov Decision Processes.