No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes
Authors: Jasmine Bayrooti
Sattar Vakili
Amanda Prorok
Carl Henrik Ek
Venue: NeurIPS 2025 poster ()
Keywords: Thompson sampling
reinforcement learning
Gaussian processes
regret bounds
Primary area: reinforcement_learning
TL;DR: We derive no-regret guarantees for Thompson sampling in episodic reinforcement learning with Gaussian process modelling.

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\Gamma(KH)})$ over $K$ episodes of horizon $H$, where $\Gamma(\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.

No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes
Jasmine Bayrooti University of Cambridge jgb520cam ac.
Sattar Vakili MediaTek Research sattar. vaki 1ittkreeeearrchcoom com
Amanda Prorok University of Cambridge asp450cam. ac. uk
Carl Henrik Ek University of Cambridge Karolinska Institutet che290cam. ac.uk
Abstract
Thompson sampling (TS) is powerful and widely used strategy for sequential decision-making. with applications ranging from Bayesian optimization to rein- forcement 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 episodic RL with joint Gaussian process (GP) priors over rewards and transitions. We prove a regret bound of O(VK ((HKH((II)) over K episodes of horizon H. where 1'(.) cap- tures the complexity of the GP model. Our analysis addresses several challenges, including the Gan-Gaas nature of value functions and the recursive structure of Bellman updates, and extends classical tools such as the elliptical potential lemma 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.
Introduction
Sequential decision-making under uncertainty lies the core of many machine learning systems, from robotics (Kober et al., 2013) and chip design (Mirhoseini et al., 2021) to large language models (Ouyang et al., 2022). In these settings, an agent must make a series of decisions, balancing exploration to learn about the environment with exploitation to act effectively. A central question is: how should an agent leverage uncertainty to act optimally over time?
Thompson sampling (TS) a widely used and principled approach for sequential decision-making that naturally balances exploration and exploitation through posterior sampling (Thompson, 1933). The idea is to sample a model from the posterior and select actions that are optimal under that model. The inherent randomness in TS aligns exploration with the agent's 's uncertainty and can lead to more efficient learning compared to methods based on confidence bounds (Russo et al., 2018). TS underpins range of applications including bandits (Chapelle and Li. 2011; 1; Kaufmann et al., 2012b; Russo et al., 201 10), Bayesian optimization (Srinivas et al., 2010; Chowdhury and Gopalan, 2017;
Vakili et al., 2021b), and reinforcement learning (RL) (Sasso et al., 2023; Osband and Van Roy, 2017;
Bayrooti et al., 2025). Empirically, TS has demonstrated strong performance across domains and is widely adopted in practice. Theoretical guarantees for TS have been well-developed multi-armed bandit settings (Agrawal and Goyal, 2012; Kaufmann et al., 2012a) and have also been extended to RL settings (Osband et al., 2013; Osband and Van Roy, 2017; Chowdhury and Gopalan, 2019; Dann
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

et al,, 2021). However, existing analyses in RL typically rely on discrete state-action spaces, assume linear or kemnliized dynamics, or yield regret bounds that scale poorly with state dimensionality, Establishing tight regret bounds for TS in continuous-state Markov Decision Processes (MDPs) without strong structural assumptions remains an important open problem.
In this work, we take a step toward closing this gap by studying TS for sequential decision-making under general, continuous models of the environment. We focus on RL in finile-horizon MDPs, where both rewards and transitions are jointly modeled using a multi-output GP, as proposed by Bayrooti et al. (2025). This approach enables the agent to model correlations across different components of the environment in a flexible and data-efficient manner. We consider an episodic MDP with K episodes of horizon H. where at the start of each episode, the agent samples a realization from the GP posterior and computes an optimal policy with respect to this sample. Regret is defined as the cumulative loss in value relative to the optimal policy. We provide a stylized analytical upper bound on the regret, showing its dependence on the number of episodes, the horizon, and the complexity of the GP kernel. Our analysis highlights the key theoretical challenges of applying TS in sequential settings, particularly due to the recursive and compositional nature of value functions in RL.
1.1 Contributions
We establish a sublinear regret bound for TS in model-based RL under GP models, an approach refer to as Reinforcement Learning with GP Sampling (RL-GPS). We prove regret bound of ((УКНT(КH)) over K episodes of horizon H, where I(..) captures the complexity of the GP model. Sublinear regret in K implies that RL-GPS asymptotically matches the performance of the optimal policy, referred to as no-regrer learning (Srinivas et al., 2010; Agrawal and Goyal, 2013b).
Our theoretical analysis introduces several novel intermediate contributions that are essential to deriving the final regret bound. Extending TS regret guarantees to RL presents two main challenges: (i) the optimal value function is a recursive composition of GPs which is not a GP itself (Damianou proxy models induced by Bellman updates, rather
and Lawrence, 2013); and (ii) TS operates than sampling directly from the posterior over the optimal value function. To address (i), we derive high-probabilityy confidence bounds for compositional functions of GPs, formalized in Theorem 1, which allow us to control the error that accumulates through Bellman recursion. Building on these bounds, we obtain high-probability confidence intervals for recursive value functions in episodic MDPs (Corollary 1) that links the sampled proxy to the true value. To address (ii), we bound the regret in terms of cumulative posterior uncertainty via new multi-outpur elliptical potential lemma (Lemma 1) that jointly tracks correlated uncertainty across multiple outputs. This lemma provides tighter regret guarantees than naively applying the standard versions (Srinivas al., 2010; Abbasi- Yadkori et al., 2011; 1: Carpentier et al., 2020) independently to each output dimension by leveraging the correlation structure. We further introduce a delayed-update lemma (Lemma 2) that accounts for model updates at the end of episodes, yielding an improved dependence on the horizon H.
Finally, we conduct controlled experiments designed to mirror the theoretical assumptions and validate our regret bounds. Our results confirm sublinear cumulative regret across a range of environments, including Ga-sampled MDPs and sparse navigation tasks. Furthermore, empirically illustrate how the choice of GP kernel affects learning efficiency, with smoother kernels such as RBF leading to faster regret decay in smooth environments, and rougher Matérn kernels outperforming in sparse settings. These findings are consistent with the theoretical dependence on model complexity and highlight the importance of model selection in practical applications.
1.2 Related work
RL with TS. The theoretical performance of Thompson sampling (TS) has been extensively studied in the bandit setting, where it achieves near-optimal regret bounds and strong empirical performance (Agrawal and Goyal, 2012, 2013a; Kaufmann et al., 2012b; Korda et al., 2013; Russo and Van Roy, 2014; Russo al., 2018; Kveton et al., 2020). In the GP bandit setting, Chowdhury and Gopalan (2017) provided regret bounds for TS under kernel-based assumptions on the target functions, introducing techniques that our analysis builds on (see Step 2 in Section 4 for details). Extending TS to RL introduces new challenges due to the recursive structure of value functions and the dependence on both states and actions. Several works have established foundational regret guarantees for TS in finite MDPs (Osband et al., 2013; Osband and Van Roy, 2014; Osband et al.,

---

2016; Russo, 2019). In particular, Posterior Sampling for Reinforcement Learning (PSRL) (Osband et al., 2013; Osband and Van Roy, 2017) achieves D Bayesian regret, where H is the horizon, 5 the number of states, A the number of actions, and T the total number of steps. Building on their analyses, Fan et al. (2018) studied TS in continuous MDPs and established Bayesian regret bounds. Dann et al. (2021) also considered continuous MDPs, but under linearity assumptions, and derived tighter regret guarantees although their bounds scale poorly with state dimensionality, In the kernelized RL setting, Chowdhury and Gopalan (2019) analyzed TS where the transition probability distribution is assumed to be fixed function in reproducing kernel Hilbert space (RKHS) and derived regret bounds that depend on the maximum information gain of the kernel.
Our work differs fundamentally from these approaches in both modeling and analysis. We model the reward and transition functions jointly as a multi-output GP and our analysis provides probabbibbyi bounds that hold uniformly across all problem instances, unlike Bayesian regret bounds that are averaged over the distribution of all problems. Consequently, our approach requires different proof techniques and much of the analysis we present is novel, including Theorem 1 on confidence bounds for composed GPs, Corollary 1 on high-probability value function bounds, and Lemmas and on multi-output elliptical potential bounds. Our assumptions are also more mild than in prior analyses. For example, PSRL (Osband et al., 2013; Osband and Van Roy, 2017) assumes finite state and action spaces, linear MDP methods (Dann et al., 2021; Jin et al., 2020) assume linearity in both rewards and transitions, and RKHS-basee approaches (Chowdhury and Gopalan, 2019) assume that the transition dynamics are modeled as fixed functions within known RKHS, effectively treating each component independently. In contrast, our multi-output GP framework flexibly captures correlations between reward and transition without requiring assumptions on discretization, linearity, or independence.
Episodic MDP. The episodic MDP framework is a central setting for RL. Sublinear regret bounds have been established for Upper Confidence Bound (UCB) based methods in tabular finite-horizon MDPs (Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019). Subsequent works have developed regret analyses for UCB-style methods with additional structural assumptions, including linear (Jin et al., 2020) and kernelized MDPs (Chowdhury and Gopalan, 2019; Yang and Wang, 2020; Vakili and Olkhovskaya, 2023). Additionally, Curi et al. (2020) introduced an optimistic algorithm for continuous state-action MDPs and established regret guarantees under standard assumptions for GP models. These approaches all rely optimism via constructed confidence sets to guide exploration. In contrast, TS offers an exploration approach that avoids explicit construction of confidence sets and has been less theoretically studied in complex RL settings.
Broader RL settings. Beyond episodic MDPs, it is also common to study performance in infinite- horizon discounted (Puterman, 2014) and average-rewant settings (Auer et al., 2008; Vakili and Olkhovskaya, 2024). In the discounted setting, the contraction properties of the Bellman operator enable efficient learning. For example, Ouyang et al. (2017) leverages these properties to dynamically adapt episode lengths and demonstrate sublinear regret for TS. In the infinite-horizon average-reward setting, regret bounds have been established for tabular communicating MDPs with finite diameter using -CB-dased strategies (Auer et al., 2008; Jaksch et al., 2010; Agrawal and Jia, 2017; Wei et al., 2021). More recent works have analyzed regret in structured aefinite-horizon settings, each addressing different challenges. Wu et al. (2022) provided nearly manimax--ptimml guarantees for model- linear mixture MDPs with known feature mappings. Ghosh and Zhou (2023) established sublinear regret bounds using model-free methods with linear function approximation in weakly communicating MDPs. Sukhija et al. (2024) studied continuous, nonlinear dynamical systems in nonepisodic settings and established sublinear regret bounds in terms of maximum information gain under continuity and bounded energy assumptions. In general, infinite-horizon and average-reward settings require structural assumptions such as finite diameter, weakly communicating structure, or continuity and boundedness to obtain theoretical guarantees and the resulting regret bounds often depend explicitly on these properties. By focusing on the episodic setting, we sidestep these complications and exploit the horte-horizon structure to develop regret analysis using GP-based recursive bounds.
2 Problem formulation
An episodic MDP is defined by the tuple (S.A, fn, fs, H), where S C Rdd is the state space. A C dRdd is the action space, and H is the episode length. The reward function is fn : S x + R. and the state transition function is fs S S.
3

---

The policy x = {TT S A] specifies the action Tá (s) the agent takes in state at step h. At the start of each episode determines a policy π [T h=
1,2. K, the environment selects an initial state $1,8 and the agent h= At each step h of the episode, the agent observes the state s and selects action dz.k = (5h,k) The agent then receives reward (s (h.k) and transitions to the new state $4+1,k = [Sh,, (h,k).
In an episodic MDP, the agent aims to maximize the cumulative reward collected over an episode. To formalize this, define the value function of policy æ as the expected total reward obtained when starting at state at step h and following я thereafter, where the expectation is taken over the trajectory {(SW, aw) = induced by the policy æ.
V (s)
Σ fR(S,, TR(ss,ax) | sh =
E S, [nI.
The associated state-action value function is defined as:
(x, Σ fulsw, aw) 18/ 8, 0/h a
(2)
We assume the existence of an optimal policy x* that maximizes the expected total reward from any state and time step. The optimal value and optimal state-action value functions are defined as:
(s) max V (s), (s, max (%
(3)
The optimal value function satisfies the Bellman optimality equation:
(s,s,)) fR(S, a) + Vi
(i( max (5,
(4)
with Vi+ (s) for all S. An RL algorithm aims find near-optimal policy while interacting with the environment. The regret over T timesteps is defined as:
K
Regret(T) = E(vT(NLN) - (sTx))
(5)
k=1
where ma is the policy executed by the agent in episode k. and $1,8 is the initial state of that episode, and we use = K for the total number of steps.
Gaussian process modeling. GPs specify distributions over the space of functions, offering cal- ibrated uncertainty estimates that can be leveraged for exploration and decision making. In the single-output case, model unknown function f Z R Gaussian process:
(6) with a scllur- kernel k x x 2 + R. Given noisy observations {(zi, 3 with V: = f(;)) + E; and E, ~ NN(0, X²), the posterior mean and variance at any test point Z are given by:
f ~ GP(O,
(=(=) = k, (K, + A "yn, (=) = k(2, =) - k (K,, + >2I,)) -
where K., E Ruxx is the kernel matrix with [KnJs = k(zz,zz) 2j), kn(z) E R" has entries k(z,, =), and yn IR" the vector of observed outputs.
Multi-output Gaussian processes. In many applications, we wish to model a vector-valued function f: 2 - Rdd jointly across multiple correlated outputs. In this setting, f is modeled multi-output GP (6) where k Z x Z + [ jadx is a matrix-valued positive semidefinite kernel that encodes both input similarity and output correlations.
Given n input points 21...., Zn. let the observed outputs be collected into a vector yn E Rnd by stacking all d outputs at each input. The full joint prior over yn is multivariate Gaussian with zero mean and block kernel matrix K, E gndxnd defined by:
Ki - 1)d (j- 1)d + s) [k(2,, 2i)lr for [no), r, [d].

---

The posterior at test point 2 is again Gaussian:
(n. = (2) (K, + X IIndn) "oryyyyn (x) = k(2,, 2) - (n(2) (K,, + II 'n, (2) -
Yn E Rd
E Raxd
(8)
where (2) E Radxd is the cross-covariance between f(z) and the training outputs, defined via (=)())( = [k 2)]rs- We define o (=) == diag (iag((E(z))) E I as the marginal predictive variances. With slight abuse of notation, we use oz.(z) to denote the vector of marginal standard deviations, where (=) (=)) for iori=1, ......d. d. The posterior mean (n(=) and uncertainty (z) allow multi-output GPs to provide joint, uncertainty-aware predictions across outputs, making them well-suited for RL settings where transition and reward models must be estimated simultaneously.
Reinforcement learning with GP sampling
In this section, present RL-GPS for learning episodic MDPs with joint GP modeling of the reward and transition functions, following the multi-output model Bayrooti et al. (2025).
Assumption 1. Let f = [fR. fs] denote the joint reward and transition function. We assume f is distributed as a multi-output Gaussian process: f ~ GP(O, for a known matrix-valued kernel k: x - IRdxd
Remark 1. GPs offer flexible representational capacity since their smoothness and expressiveness depend on the kernel choice. For instance, the Matérn Matérffamily introduces a smoothness parameter controlling function regularity, where smaller v values yield rougher functions that better capture non-smooth behavior. As shown by Srinivas et al. (2010), Matérn kernels can approximate any continuous function our setting can capture a broad class of reward and transition functions, including those with limited smoothness, and is applicable to many continuous-come environments (Bayrooti et al., 2025).
compact subsets of Rd, making GP priors highly expressive. Consequently,
The RL-GPS algorithm follows
sinee-ittration-aassee form of TS, where the start of each episode. the agent samples a realization of the reward and transition functions from the GP posterior and computes proxy value functions Qr, ^ via backward induction. The agent then executes the greedy policy induced by this value function for the duration of the episode. This sampling- based approach encourages exploration by introducing structured randomness into value estimates, naturally balancing exploitation of high-reward regions with exploration of uncertain areas of the state-action space. Pseudocode provided in Algorithm
Algorithm 1 RL with GP Sampling (RL-GPS)
1: Require: number of episodes K, episode length H, GP kernel k
2: Initialize: reward-dynamics model p(f), reward and transition buffer
3: for episode k = 1,..., ......KK K do
4: // Create the proxy value functions Qh,k
5: Sample functions [f., fs.x] from GP posterior p(f (D)
6: Initialize (.+ (-) =
7: for H...,, do
8:
Qn.(s, = (x, + Vn+1 (s,
9:
(8) max (8,
10:
// Follow the greedy policy with respect to Qi.k Observe initial state 81,4
12:
for 1, H do
Select action aA,k argmax Qn.((h)k:a)
14:
Observe next state SM+1 = fs (s an,k) and reward Thik fR fR(S an.)
Store reward and transition buffer (5h,k, ab,k, Th,ki sh+1,k) D
16:
Update GP posterior p(ʃ 'D) using new transitions
5

---

4 Analysis
In this section, derive regret bound for RL-GPS (Algorithm 1) in episodic MDPs with multi- output GP model. We introduce intermediate results and provide the regret bound Theorem 2.
4.1
Confidence intervals
To analyze the regret, we require figh-probabiliig bounds on the accuracy of GP predictions. For single-output GP f with posterior mean pn, and standard deviation on the tail decay of the Gaussian distribution implies that, with probability at least 1 - 6, the following holds uniformly over z:
If(z) nn (z)l - (5)(()))22)
where (6) =
()) (e.g., see Srinivas et al., 2010).
In the RL setting, we must also construct confidence intervals for e(fs(-) as part of the policy's recursive design where S IR is generic value function. The following theorem addresses this. Theorem (Confidence bounds for composed GPs). Assume f : 2 -> C TRds is multi-output Let v S + TR. be twice differentiable
GP with posterior mean prn and standard deviation value function where for all s E S, [[Vr())] S ug and [| S ug. Define the composition g(z) v(f())). Then, with probability 1 8. for all E 2,
lØ(=) - (x)) I 3. (z)1l + u 3r (8/d5 (1),
(6/
(10)
The proof uses a Taylor expansion to bound [g(z) - vn (3)) | in terms of the first- and second- order behavior of together with the standard GP confidence intervals given in (9). A detailed proof provided in Appendix A.
4.2 Performance analysis of RL-GPS
To analyze the regret of RL-GPS, we first introduce our assumption regarding the smoothness of the value functions.
Assumption 2 (Smoothness of the value functions). We assume that for all h, Vy. is twice differentiable where for all s, (s)ll ua and || ( un.
Remark 2. The assumptions on the gradient and Hessian norms are mild compared to those typically imposed value functions in the literature. For example, in Jin al. (2020) and Yang al. (2020), is assumed that all proxy value functions belong to a function class defined using linear or kernel- based models, respectively. In contrast, we impose weaker assumption only on the first and second derivatives of the value functions.
Now we present the main theorem bounding the regret of RL-GPS.
Theorem 2. Consider the episodic MDP setting described in Section 2 and the RL-GPS algorithm given in Algoritium 1. Under Assumptions 1 and 2, with probability 6,
(egret(T) = (log(T//5)/TT/)))
where I(T) MeEMM,, Ir. Ip det((ar + 2 Kr).
The determinant in r(-) represents the complexity of the function space described by the GP (Ras- mussen and Williams, 2006) and serves as an upper bound on the information gain, which discussed in detail in the next section.
The regret bound holds with high probability, where the randomness accounts for both the joint GP distribution of the environment and the randomness in the Thompson samples.
Remark 3. The Matérn family is both theoretically significant and practically prevalent among kernel choices. By substituting the bounds on from Vakili et al. (2021a) we obtain the following regret rales. For base Matérn kernel with smoothness parameter
our regret bound becomes:
Regret(T) - ( (
while for the radial basis function (RBF) kernel, the regret bound simplifies Ô (VT).

---

Remark 4. When H = 1. learning in episodic MDPs reduces to the degenerate special case of Bayesian optimization, also known GP bandits. In this setting, we have T K and our regret bound becomes:
(Tg = (ogg(T/OVTTC))
which recovers the standard regret bounds in Bayesian optimization (e.g, see Srinivas el al., 2010).
4.3 Proof Theorem
Our analysis bounds the total regret by comparing the per-episode value of RL-GPS to the optimal value function. We decompose this difference into immediate and recursive components, bound each using confidence intervals derived from the GP model, and then accumulate the bounds via the information gain of the kernel. The key novelty lies in extending both the confidence analysis and the elliptical potential lemma to multi-output GPs. A detailed proof is provided in Appendix B, structured around the following four main steps:
Step 1: Regret decomposition. We decompose the per-step regret into two components: an immediate regret term related to TS, and a recursive term capturing uncertainty value propagation through the transition model (proven in (13) in Appendix B).
Vi (8h,x) - Vn (#I,k) = (sp.ee (h,x)) - Q% (sn. an.e) + (Viti(s4411 - Vi+ii (8++1.)))
(Immediate sogret)
(Recursive part regret)
(11)
Step 2: Bounding the immediate regret. To bound the immediate regret, we build on techniques from the analysis of TS in GP bandits (Chowdhury and Gopalan, 201 7), but face two key challenges unique the RL setting: (i) the target function (s, a) fR(S, a) + V (fs(s, a)) recursive and compositional and thus cannot be directly modeled as GP; (fi) the TS algorithm samples from the posterior of proxy Qr,k. not the true posterior over Q7-
To address both issues, we construct high-probability upper and lower confidence bounds on the proxy and target value functions, which our knowledge have not appeared in prior analyses. These confidence intervals allow us to relate the sampled proxy values to the true value the selected action and quantify the regret incurred.
Definition 1 (Upper and lower confidence bounds for value functions). We define the upper confidence bounds recursively as:
(8, a) (s, + Vi+1. (Ms, a)) + Eu(s,a), VR, = max (h,
with VN & (8) O. Similarly, the lower confidence bounds are defined as:
(h, a) = MRA(S, a) + Vett,,(usssAss..) - (x(s,)), (s) max aEA
with V (s) 0. The confidence width E a) given by:
(s,,a)== = 3,(0/Td)oRA(sss) uGGxx66 (d a))l u (
based Theorem 1. Here, PR.ki JR, and kss as,k the posterior mean and standard deviation of fR and fs. respectively.
Corollary 1. With probability least 8, the optimal and proxy value functions lie within the confidence bounds:
(h,(s,,) s Qu,e(s,a), a). (s a) I (s,(ss,), 4(h, s,
Step 3: Accumulating regret across an episode. We unroll the recursive regret decomposition and accumulate the bounds over all steps 1,..., H within an episode, leading a per-episode regret bound expressed in terms of confidence widths:
K
H
Regret(T) < ><Σ>
(s (h.))
mm Am

---

where e is an absolute constant.
Step 4: Bounding cumulative regret. Finally, we the per-episode regret bounds K episodes, obtaining a cumulative regret expression that involves sums of posterior standard deviations in GPs. We bound these terms using new elliptical potential lemma (Lemma 1) for multi-output GPs, which is introduced in the next section. Also, an additional challenge arises due to the structure of the problem: involves double sum over episodes k and steps h, but within each episode, the observations across h are not sequentially incorporated into the GP posterior. This batched structure leads to an additional dependence on the episode length H. which we address using tools developed for GP analysis under batch observations and delayed feedback (Calandriello et al., 2020, 2022).
4.4 Elliptical potential lemma for multi-output GPs
In analyzing cumulative regret, a central quantity is the of sequentially conditioned posterior variances from a GP. A classical result by Srinivas et al. (2010) shows that for scalar-output GPs, the sum of variances along sequence of inputs 21,..., 27 bounded by a log-determinant term:
T
(2)) C. Cologder det Σ
(Ira
X2 Kr)
where À is the GP noise parameter, Kr is the kernel matrix over the inputs, and C' is a constant. This result often referred to as the elliptical potential lemma, particularly in the special case of linear kernels (Carpentier et al., 2020).
In our setting, the transition function is modeled as a multi-output GP, which requires a generalization of the classical result to pector-valued functions. Applying scalar GP bounds independently across output dimensions would result regret bounds that scale linearly with the state dimension ds. To address this, we derive the following elliptical potential lemma for multi-output GPs that exploits inter-dimensional correlations captured by the kernel.
Lemma 1 (Elliptical potential lemma for multi-output GPs). Let f: - RRd be a d-dimensional function modeled by multi--otpuut GP with matrix-valued kernel k. Let 21...., 2T E Z be sequence of input points, and denote by 0t-1(z)) Rd the vector of posterior standard deviations at 2, conditioned on data up to round t - 1. Then,
T Σ |1)-((20)11 S CIr.
where C' Tog(1+A 2j is constant and Ir denotes the mutual information between the observations 91.7 = (f())) + eT and the latent function f. given by
IT log det (ITa - KT))
A detailed proof is provided in Appendix C.2. It extends the result of Srinivas et al. (2010) to the multi-output setting relevant to our analysis.
Experiments
To empirically validate the regret scaling in Theorem 2, we present synthetic experiments based on the episodic MDP setup from Section to assess the performance of RL-GPS in controlled environments that refleet the assumptions in our theoretical analysis.
This experiment studies how kernel complexity impacts regret in synthetic MDPs generated from GP-sampled environments. The state and action spaces are continuous, S= [0, 1]2 and AA- (0, 1). but each dimension discretized into 25 equally sized bins to enable tractable value function approximation. We compare three common kernel functions: the Radial Basis Function (RBF) kernel and Matérn kernels with smoothness parameters v = 2.5 and v = 1.5. For the specific multi-output GP model, we the popular linear model of coregionalization (LMC) (Grzebyk and Wackernagel, 1994; Wackernagel, 2003), which predicts the final vector- valued output as a linear combination of independent latent GPs (see Appendix D for more details).
Kernel complexity.
8

---

GP Environment
For each kernel, sparse LMC multi-output GP with zero mean and fixed linear correlations is used to sample the ground-truth reward and tran- sition functions, JR and fs. respectively (with re- wards normalized to E [0, 1] per step), thereby defining the MDP. The optimal value function V* is computed using finite-horizon value it- eration with H = 20. Algorithm is run for K 1000 episodes and cumulative regret rel- ative to the optimal value function is quanti- fied. The results averaged over 200 randomly sampled environments and shown Figure Across all kernels, cumulative regret grows sub- linearly, which is consistent with our theoretical analysis. Performance varies with the complex- ity of the kernel: the RBF kernel yields the low- est regret, followed by Matérn
200
175
Matem 1.5
Cumulattive Regret
125
100
75
50
200
400
600
800
1000
Episodes
Figure 1: Cumulative regret over different kernels on GP-sampled environments over 200 trials. The shaded region around each curve represents +1 standard error of the mean across trials. Dotted lines represent median regrets.
2.5 and then Matérn P 1.5, as predicted by Remark 3. This reflects that rougher kernels correspond more complex function classes and require more data accurately estimate value functions. These results empirically confirm the theoretical link between kernel smoothness and learning efficiency that our analysis formally elucidates through the regret bound's s dependence on information gain (--).
Navigation Regnet Growt
1.0
Mndiyation Reward Runeiton
Kaddpation Optimal Functton
-L0
V/asem
State Dimergon
000
-1
280
7.5
-22
200
0.2
22
0.8
8.0
403
E00
1000
State Dimemtion
Stare 3imemiion
Epiiocis
1.0
Maze Reward Tunction
-12
Optimal Value
Mare Regnnt Growth
0.8
-10
State (imentonn
0.6
Conditrr
0.4
2000
0.2
02
0.0
0.2
0.4
2.6
2.5
1.0
0.0
0.2 0.4 0.6
0.8
200
-00
100
100
1000
Dimension
Figure 2: The reward function (left column), optimal value function (middle column), and cumulative regret of TS with multi-output GP with confidence regions representing the standard error over 200 random trials (right column) are given. The first row corresponds to the sparse navigation task and the second row corresponds to the sparse maze problem.
Multi-output kernel structure. These experiments study how the multi-output kernel structure affects regret in sparse navigation tasks. The state space S [0, 1]2 discretized into 25 equally spaced bins per dimension and the action space A consists of 9 discrete actions that move the agent in the cardinal diagonal directions or allow it to remain stationary. The agent receives a reward of +1 when within 0.1 of the destination and penalty of -0.01 otherwise. We study two settings: free movement within the grid and constrained navigation through a maze. As before, the optimal value function V is computed using finite-horizon value iteration. Algorithm runs for K = 1000 episodes with a sparse LMC multi-output GP posterior. The results over 200 trials are shown in Figure 2 and demonstrate sublinear regret growth, consistent with our theory. Notably, in these sparse,

---

less smooth environments, the RBF kernel accumulates regret more rapidly than the Matérn kernlss. This is due to the RBF kernel's strong smoothness assumptions, which lead to model misspecification and slower adaptation when the ground truth is rougher (Rasmussen and Williams, 2006). The results also highlight the value of modeling output correlations using the LMC. Specifically, the Matérn 1.5 kernel without LMC incurs substantially higher regret in the maze environment compared to its LMC-enabled counterpart. This indicates that explicitly capturing output dependencies can improve sample efficiency and reduce regret, especially in structured or high- high-dimensional tasks. Additional information about our experiments and results are given in Appendix E and our open-sourced implementation at: https:/ /tte:://gttttt com/ wwwgyrooiiSSrrerett...
6
Conclusion
We presented regret analysis of Thompson sampling for reinforcement learning in finite-horizon Markov Decision Processes with multi-output Gaussian Processes jointly modeling rewards and transitions. Our analysis established a sublinear regret bound of how the complexity of the GP kernel governs learning efficiency. To derive this result, introduced new tools for bounding uncertainty in recursive value functions, including confidence intervals for compositional functions of GPs and multi-output elliptical potential lemma that captures correlations across components. These results extend classical GP analysis to vector-valued and recursive settings and may be of independent interest. Our experiments validated theoretical predictions, showing sublinear regret across various tasks and kernels. Overall, this work illustrated how structural assumptions and posterior uncertainty influence the dynamics of exploration in reinforcement learning.
demonstrating
Limitations. Our analysis relies on assumptions that may not hold general. Specifically, we assume that the environment dynamics and rewards at each decision step jointly Gaussian (Assumption 1) and that value functions are twice differentiable with bounded gradients and Hessians (Assumption 2). These conditions enable tractable analysis but exclude settings with discontinuous or non-smooth dynamics. Nonetheless, our smoothness assumptions are milder than those commonly imposed in prior work regret analyses. Finally, this work focuses finite-horizon episodic MDPs; extending the analysis to infinite- horizon settings remains a promising direction for future research.
Acknowledgments
J. Bayrooti is supported by DeepMind scholarship. A. Prorok supported part by European Research Council (ERC) Project 949940 (gAla).
References
Y. Abbasi-Yadkonk D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, 2011.
S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi- bandit problem. In Conference on Learning Theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135, 2013a.
S. Agrawal and N. Goyal. Further optimal regret bounds for thompson sampling. In International Conference on Artificial Intelligence and Statistics, volume 31 of PMLR, pages 99-107, 2013b.
S. Agrawal and R. Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, volume 30, 2017.
Auer, T. Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems, volume 21, 2008
M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272. PMLR, 2017.
10

---

J. Bayrooti, C. H. Ek, and A. Prorok. Efficient model-based reinforcement learning through optimistic thompson sampling. International Conference on Learning Representations, 2025.
D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco. Near-linear time gaussian process optimization with adaptive batching and resparsification. International Conference on Machine Learning, pages 1295-1306 PMLR, 2020.
D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco. Scaling Gaussian process optimization by evaluating few unique candidates multiple times. In International Conference Machine Learning, pages 2523-2541. PMLR, 2022.
A. Carpentier, C. Vernade, and Y. Yadkor. The elliptical potential lemma revisited. arXiv preprint arXiv:2010. 10182, 2020.
O. Chapelle and I.. Li. An empirical evaluation of thompson sampling. In Advances in Neural Information Processing Systems (NeurIPS), volume 24, pages 2249-2257, 2011.
R. Chowdhury and Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844-853. PMLR, 2017.
S. Chowdhury and A. Gopalan, Online learning in kernelized markov decision processes. In International Conference on Artificial Intelligence and Statistics, pages 3197-3205. PMLR, 2019.
S. Curi, F. Berkenkamp, and A. Krause. Efficient model-based reinforcement learning through optimistic policy search and planning. In Advances in Neural Information Processing Systems, volume 33, pages 14110, 2020.
A. Damianou and N. D. Lawrence. Deep gaussian processes. In International Conference on Artificial Intelligence and Statistics, pages 207-215. PMLR, 2013.
C. Dann, M. Mohri, T. Zhang, and J. Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 12040-12051, 2021.
K. Diederik and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Y. Fan, L. Chen, and Y. Wang. Efficient model-free reinforcement learning using gaussian process. arXiv preprint arxiv: 1ee.11222..3333 2018
J. Gardner, G. Pleiss, K. Q. Weinberger, D. Bindel, and A. G. Wilson. GPyTorch: Blackbox matrix- matrix gaussian process inference with GPU acceleration. Advances Neural Information Processing Systems, volume 31, 2018.
A. Ghosh and X. Zhou. Achieving sub-linear regret in infinite horizon average reward constrained mdp with linear function approximation. International Conference Learming Representations, 2023.
M. Grzebyk and H. Wackernage.. Multivariate amalysis and spatial/temporal scales: real and complex models. In International Biometrics Conference, volume 1, pages 19-33, 1994.
T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. In Journal of Machine Learning Research, volume 11, pages 1563-1600, 2010.
C. Jin, Z. Allen-Zhu, Bubeck, and M. I. Jordan. Ielaanning provably efficient? Advances in Neural Information Processing Systems, volume 31, 2018.
C. Jin, Z. Yang, Wang, and M. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137-2143. PMLR, 2020.
E. Kaufmann, Korda, and Munos. Bayesian upper confidence bounds for bandit problems. In International Conference Artificial Intelligence and Statistics, 2012a.

---

E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-tine analysis. International conference on algorithmic learning theory, pages 199-213. Springer, 2012b.
J. Kober, J. A. Bagnell, J. Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11):1238--2744 2013.
N. Korda, E. Kaufmann, and R. Munos. Thompson sampling for I-dimensional exponential family bandits. Advances in neural information processing systems, 26, 2013.
B. Kveton, M. Zaheer, C. Szepesvari, L. Li, M. Ghavamzadeh, and C. Boutilier. Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 2066-2076. PMLR, 2020.
A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, S. Song, E. Wang, Y.-. Lee, J. Johnson, A. Pathak, T. Duerig, et al. graph placement methodology for fast chip design. Nature, 594(7862)20772212 2021.
I. Osband and B. Van Roy. Near-optimal reinforcement learning in factored MDPs, In Advances in Neural Information Processing Systems, volume 27, 2014.
I. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, pages 2701-2710. PMLR, 2017.
I. Osband, D. Russo, and Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, volume 26, 2013.
I. Osband, B. Van Roy, and Z. Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR, 2016.
L. Ouyang, Wu, X. Jiang, D. Almeida, C. Wainwright, Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.022 02555, 2022.
Y. Ouyang, M. Gagrani, A. Nayyar, and R. Jain. Learning unknown markov decision processes: A thompson sampling approach. In Advances in Neural Information Processing Systems, volume 30, 2017.
M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006.
D. Russo. Worst-case regret bounds for exploration via thompson sampling. In Advances in Neural Information Processing Systems, pages 14196-14206, 2019.
D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 12211:1221 2014.
D. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen. A tutorial thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
R. Sasso, M. Conserva, and P. Rauber. Posterior sampling for deep reinforcement learning. In International Conference on Machine Learning, pages 30042-30061. PMLR, 2023.
N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In International Conference on Machine Learning. page 1015-1022, 2010.
B. Sukhija, I.. Treven, Dörfler, Coros, and A. Krause. NeoRL: Efficient exploration for nonepisodic RI. In Advances in Neural Information Processing Systems, volume 37, pages 74998, 2024.
W. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-246 1933.
12

---

S. Vakili and J. Olkhovskaya. Kernelized reinforcement learning with order optimal regret bounds. In Advances Neural Information Processing Systems, volume 36, pages 4225 2225-4247, 2023.
Vakili and J. Olkhovskaya. Kemel--baeed function approximation for average reward reinforcement learning: an optimist no-regret algorithm. Advances in Neural Information Processing Systems, 37: 25401-25425, 2024.
S. Vakili, K. Khezeli, and V. Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021a.
S. Vakili, H. Moss, A. Artemev, V. Dutordoir, and V. Picheny. Scalable thompson sampling using sparse gaussian process models. Advances in neural information processing systems, 34:5631- 5643, 2021b.
H. Wackernagel. Multivariate geostatisties: an introduction with applications. Springer Science & Business Media, 2003.
C.-Y. Wei, M. J. Jahromi, H. Luo, and R. Jain. Learning infinite-horizen horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3007-3015. PMLR, 2021.
J. Whitehouse, A. Ramdas, and S. Z. Wu. On the sublinear regret of GP-UCB. In Advances in Neural Information Processing Systemx, volume 36, pages 35266-35276, 2023.
Y. Wu, D. Zhou, and Q. Gu. Nearly minimax optimal regret for learning infinite-horizon average- reward mdps with linear function approximation. In International Conference on Artificial Intelli- gence and Statistics, pages 3883-3913, PMLR, 2022.
L. Yang and M. Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
Z. Yang, C. Jin, Z. Wang. M. Wang, and M. Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. In Advances in Neural Information Processing Systems, volume 33, pages 13903-13916, 2020.
A. Zanette and F. Brunskill. Tighter problen-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
13

---

A Proof of Theorem 1
In this section, we provide detailed proof of Theorem 1. Recall from (9) that for single-output GP with posterior mean and standard deviation An and nn we have, with probability 1 - 8, uniformly 2,
If(z) - mn - (.())o,(z))
(12)
where (0) O(vlog()))
To extend this composition u((())), where f(z) Rd is drawn from multi-output GP and RR + R is smooth function, we apply Taylor's theorem. For any E 2, there exists point on the line segment connecting f'(2) and (2) such that:
v(f(=)) (z)) + Fu(u,()))TT((()) (n( 2) (z)))
px(()))
Taking absolute values and using the bounds gradient and Hessian
[e([(=)) (=)(1=)) < | v( (M)))())]]]](() (z)(1) + _
( ( -n)
1 uG lf()) (x(())] ffll((()))))))))))))))))) (=)1
By the standard single GP confidence bound (9), with probability 1 6/ /s. we have Iff(2) Mn. (=)l s 3, ity -6, 6,
for all j. and hence, applying probability union bound, with probabil-
[I
ph, (=)ll - (,(6/d.)loo
Substituting into the bound above, we obtain
(u(((=)) - v(un S (=33,6//44)l0o (0000//)
that completes the proof of Theorem
B Proof of Theorem 2
In this section, provide detailed proof of Theorem on the regret performance of RL-GPS. We bound the total regret by analyzing the per-episode difference between the optimal value function and the value function of the GP-TS-RI algorithm. We structure the proof in four main steps.
First, we decompose the per-step regret into two components: an immediate regret term arising from TS, and a recursive term capturing uncertainty in value propagation through the transition model.
Second, bound the immediate regret using techniques inspired by those used in the analysis of TS in GP bandits. There are however certain challenges which are discussed below.
Third, unroll the recursion and accumulate these bounds over all steps within episode.
Fourth, we bound the cumulative regret by bounding the sum posterior standard deviations in GPs. which appear in the third step, to complete the regret bound.
First step: Decomposing the per-step regret.
We begin by analyzing the regret incurred at step h of episode k. Let ar, (56, denote the action taken by the algorithm, and let 0j = arg maxas Qf denote the optimal action at that state. The per-step regret is defined as the difference between the optimal and executed value functions:
V (Bn,c) - V. (Sn.k)-
14

---

By the Bellman equation, this can be written as:
(sn,a) - V/ (Sh,k)
= (fR(Sn. oN,x) + V (fs(ss,,, (h,)) - (fR(Sh,, an.)) + (fs (p,k))
=(R(SS,A oh1xk) V (fs
(fR(Sn,Rs (c(sh,)sah.))) ) + VR+ (/si(f((sh,) ap,)))
(Vs+1(/s(Sh,. (p, x)) W+1 (Jss (Js(5H,,,,
= = Q k) 0% (8n,, an.x) + (Vi+i (81+4,1) W+ (8h+1,4))
(13)
where the first equality follows from the definition the value function, the second adds and subtracts the term V (Sf As x)), and the third rewrites the expression using the definition of Q7,, and noting 1, = (s an.
We split this expression into two terms:
Vir (5h,)) - V (Sh,k) (% ah,x)) - (sp,k an,k) (Viti ($1+1.4) - V (9++1))))
(immeddalte regret)
(recursive part of regret)
(14)
The first term captures the immediate regret incurred by TS. The second term reflects the recursive component of regret, which arises due uncertainty in the transition model and its impact on value propagation. We next proceed to bound the immediate regret term.
Second step: Bounding the immediate regret (TS).
This term captures the suboptimality of the action a chosen by TS, relative to the optimal action 77 under the target function -%)-)). The analysis presents two key challenges compared to the standard Thompson sampling analysis in kernel bandits (Chowdhury and Gopalan, 2017):
1. The target function (; fx(+s)) + V ((s((s))) is more complex, has recursive and compositional structure involving both the reward and value functions and cannot be directly modeled as GP.
2. The TS algorithm does not sample directly from the posterior of this target function, but instead from the posterior of a proxy Qn defined the algorithm.
To address both challenges, we create upper and lower confidence bounds Q" and Q' for both Q and Qh-
Recall the following upper and lower confidence bounds from Definition We define the upper confidence bounds recursively as:
(), (R,, a) + (1H,,((Ass + (x(s, a), (x) = max (8,
initialized with 1 0. Similarly, the lower confidence bounds are defined as:
(s Mn, (s, a) V - (s, (s) max (s,
initialized with V H 0. The confidence width {x(s, a) is given by:
(s(s, a) -.(0/Td)on GBllo/allosossssssssso. a)ll + [1130///00losssss..0f (ttp::/ssssaa.o......//./oooooo. (15)
which is based on the confidence bound from Theorem 1.
Also recall Corollary With probability at least 5, the optimal and proxy value functions are bounded by the high- probabiityy confidence intervals:
(,,(ssa)) s as,
() S (s.a,,
for all (h, k s, a). Let us denote this event as
15

---

Following the analysis technique used in the kernel bandit setting (Chowdhury and Gopalan, 2017). we aim show:
(Sn. (h, Q% (n.s) S cE (n.k);
(16)
for some universal constant > To this end, we define the saturated set of actions at step (h, k) as:
Sh, == {a E A (R x) Q% (S a) > 2 [ 1
(17)
Intuitively, S4, includes actions that significantly suboptimal under the true value function Qi with suboptimality gap that exceeds twice their confidence width.
We now prove loose lower bound on the probability of selecting an action from unsaturated set. Specifically:
Pr [an, & Sp,Me 2 Pr
(, Qna((sa,sa) Va E Sm.k
Pr (Sn,, (7,)) (S0. (man)
Q (8b, (n Qn.(onn,, a), Va E Sn.c]
Pr QnL (h, > (s x) - Pr
8.
The first inequality holds because af, is, by definition, the optimal action under Qj, and therefore saturated. The second step follows by decomposing the event into two sufficient conditions. To see the third line, observe that under the event E, for any saturated action a E Sn,ks we have:
Q a) S (s,,s a) + 2 a) S (h,, a),)).
The fourth inequality follows from the symmetry and probability bound for & from Corollary
Let & = arg min ( a) denote the unsaturated action with the smallest confidence width. Then, using the law of total expectation:
E 1Ex-1(8A.k an 2 E I (Sh.ks an,)) I an, & Sn,kl Pr [an. & St.kk
& (SM. 1) 8).
(18)
We now upper bound the immediate regret using bn.s as a reference:
(s x Qi (Sn,A an,x)
(on (h Q (on,a bn, + (8h bn.k) - Qi an,))
S 2 26-1 bn,s) + (Qn, (sh, bn.k) + Ek-1 (Sn,ks bn.k)
- (Qni an,k) Ex (8h, k))
S 3366-1 (Sh bb,a) + Ex- (8h,k: (h,
+ Ex-1 an,k).
where the first inequality adds and subtract the value at by.k, the first inequality uses definitions of the set S, by. and event & and the final step uses the earlier bound on ( b).
This completes the bound immediate regret in terms the confidence width at the selected action.
Third step: Bounding the episode regret.
From the per-step regret decomposition (14) and the bound on the immediate regret (16) and using telescoping sum over steps h = 1 to H, we obtain the following bound the regret incurred in episode
(7((),)) VITh (s1,)) S c Σ I an.k)
h=1
16

---

Fourth step: Bounding the total regret.
Summing the episode regret over & K episodes, we have:
K
Regret (T) S 6 (sp, an.k)
Replacing Ex. we get:
Regret(T) S (x/T/Td)
1 0b.8) + uG (b,))
"n (8/Td)
K
(19)
2
The sum of sequentially conditioned standard deviations of sequence of observations from GP often appears in the analysis of regret bounds in Bayesian optimization. A classical result by Srinivas et al. (2010) shows that in the case of a single output GP, for a sequence of inputs 21, .2....; 2T, we have:
[z) Coloo det
In
X2 K
where is the GP noise parameter, K, is the kernel matrix over the observed inputs and C 2/log(1 1/x²) is constant. This result is sometimes referred to the elliptical potential lemma, especially in the special case of linear kernels (Carpentier et al., 2020).
A direct application of this result to setting faces two key challenges: i) We model transitions using a multi-output GP. Naively applying the bound to each output dimension separately results in regret bound that scales suboptimally with ds, the dimension of the state space. ii) Our regret decomposition involves double sum over episodes & and steps h, but within each episode, the observations across h are not sequential updates. This structure leads to additional scaling with the episode length H.
We address both challenges. First, we derive new elliptical potential lemma tailored for multi-output GPs, which improves the dependence on ds in the regret bound. That given Lemma Second, to improve the H dependence, leverage tools and techniques from the analysis of GPs under batch observations and delayed feedback (Calandricllo et al., 2020) to tighten the bound with respect to H (that roughly speaking can be understood as delay in updating the GP model).
Lemma 2 (Elliptical potential for multi-output GPs with delayed updates). Let f 2 - Re be d-dimensional function modeled as multi-outpus GP with a matrix-valued kernel k. Ler 21...., 2r E Z be a sequence of input points and suppose the GP posterior is only updated every H steps, so that the standard deviation at time o (((11))// 1)/H)
(2+) E BRd. Then,
4T(T)
T 4Н²Т(T/Н)
Σ lo (1
log(1 + +
log(1 x-22)
Applying Lemma 2 to the regret bound in terms of uncertainties (19), we obtain
Regret(T) (T)) = (Iog(T//6//IT(TT)
(20)
C Auxiliary proofs
C.1 Proof of Corollary
We prove the lower bound by induction; the upper bound can be shown similarly.
As the base case, observe that VH+1 = Vž++ = V = 0.
17

---

Now consider the inductive step. We compare the value of (s, to (%,s))):
(hu(s,a) - () a) Mn, a) + V a)) (x( (fx(s, + Vit (n,a(,,a) - fR(8, 0) + Vh+ (1s, VVL (x(8,
Temm
(l Vi+ (Ms,
Term
0..
The first line follows from the definitions of Uh and O The second line is obtained by adding and subtracting V (Us,((s, a)), followed by regrouping terms. The incquality holds since Term is non-positive due the confidence bounds in Theorem I, and Term 2 non-positive by the induction hypothesis.
Next, we extend the argument to the value function:
(s))) (s)
max a
(s, max ()) aEA
< max aed
(0)(8, (7)
00
which completes the inductive proof that (s a) s (7.s. and Vi(ss S (s) for all s, a, h. We know that (s, a) S Qn,k(s, a) for all (s,a, k). For the inductive step, consider,
as) as)
= MRAA(S, + V (Ms.((s)))) - Ex(s, (fR,(ss, a) + VILIn a)))
= (R. - fR,((s, a) + (I+IA(ps.,(s, VILIn - Ex(s,
Term
((HLA(sSHA(s.d) V
Term
S..
The decomposition follows by adding and subtracting (1s a)) and regrouping terms. Term 1 is non-pon non-positive due to the high-probability confidence bound (Theorem 1). Term 2 is non-positive by the induction hypothesis.
Hence, we conclude &h a) < Qn, for all as,
Extending to the value function:
Vh) (s) max
0h, a) max (s)
aEd
aad (8, (s)
< max aEd
0.
This completes the inductive proof that Qha s Qh, and Vh, Vs, for all s, h. The upper bounds, i.c., (s,s, a), (s, S (h,,( for all s, a, h, proven analogously using similar argument.
C.2 Proof of Lemma
We consider d-dimensional GP f: - Rd and sequence of inputs 27. Define the full observation vector as:
f(z)) +
E ERd & 2~,,00,2211)
V//1
f(zr) + ET
18

---

The mutual information between 91.T and the latent function values is:
IT [yy:: f(z)) f(r)) log det (Ira A Krr)
where Kr E Rdxdd is the prior kernel matrix over all outputs.
Let 0z ( E Rd be the vector of posterior standard deviations given observations up time I -- 1. Define the total uncertainty:
T ΣΣ
ST Σ (2))1
Iml
We apply the scalar inequality (used in Srinivas et al. (2010)):
log 2) log o² x²) for all 0² E [0, 1].
Applying this to each term oi-15 (2t) and summing, obtain:
1 of 12-1((2))
ST log(1 + x
log
j=
Since yır is jointly Gaussian, the total of these log-terms is bounded by 2Ir, giving:
2
ST <
Ir.
log(1 + 2)
Thus, we conclude:
2 Σ |0-1(21)11 CI2, with C log(1 (1 + 2-2)
C.3 Proof of Lemma 2
We begin by naively applying the elliptical potential lemma to the same step index across episodes
H
K
|on(0-1/H|(<001 <
|oHG-D=a((H)HNNI
CHT(К)
(21)
To improve on this, we use the following inequality proven in Lemma 3, for any = and 1' 1
(=)11 < [|).())11
+
(2)(2)))1
j=f-1
Applying this to the case where the model is updated every H steps, for each t E [T], we let t' = H H)/H}. Then,
[ s llon
1+
Σ
#=
Now, summing over all t = I,..., we apply the Cauchy-Schward inequality:
T (=2)
T <
|0H10-12HH
lo((
1+
10HL (2
1=1
J=H [ (1- -1
1/2
T
1/2
lon(zi)12)
T H
Σ || (2.)))
19

---

We now substitute the same term with the looser bound given earlier in (21),
2T(T) Σ Iomee-yyn V log(1 +
(H² log(1 x-)
T
This completes the proof.
Lemma 3 (Variance ratio inequality for multi- multi-output GPs). Let f RR be a d-dimensional function modeled as multi-outphn GP with a matrix-valued kernel k. Let 02(2) E R. denote the vector of posterior marginal standard deviations at point given observations. Then, for any 2 E Z and l' I,
15 11)2 [o,(2)]1 S1+
Σ (z) j-M+1
Proof. For each output dimension j E [d], the scalar variance update satisfies (see, e.g., Lemma of Calandriello et al. (2020) and Proposition A.1 of Calandriello et al. (2022))
g2)(2)
S 1
Σ
ot (2)).
Now summing over j i..... d get:
|or (2)11
Ei=1 (2)
Σ
Σ
of
(z)
=
Σ
Iow (2
|
Σラ=1 of. (z)
5=
Therefore,
(2)(2))1
Σ j=
(,)
[x)
The lower bound < (z)) /| (=)]l holds since variance decreases monotonically as more data is observed. This completes the proof.
D Discussion on the linear model of coregionalization
A widely used and computationally convenient special case of multi-output GPs is the linear model of coregionalization (LMC) (Grzebyk and Wackernagel, 1994; Wackernagel, 2003). In this model, the vector-valued function f Z - IRd is expressed as a linear combination of L, independent latent Gaussian processes:
f1(z) = Σ aggg((=), ge ~ GP(O,
(22)
where R((0) 2 2 - R is shared scalar kernel, and E R is matrix of output mixing
weights. This induces a matrix-valle valued kernel:
k<2, = A ( (z,z'), ='), where A = oa. T E Rddd
(23)
Under this kernel structure, the block kernel matrix over the training data admits a Kronecker product decomposition:
K, A (
(24)
where K mx is the input kernel matrix with [ 1sg k(0)) (21. The cross-covariance matrix between test point and training data becomes:
k, (x) = A 3 (()) (z) E Bgndxd
(25)
with k. (z)); A(00 (2,, 2).
This formulation is particularly useful when jointly modeling structured outputs such as reward and transition functions in reinforcement learning, it captures both intra- and inter-output correlations while enabling scalable inference. We provide brief discussion on the regret bounds with such structured kernel.
20

---

D.1 Information gain and regret bounds for LMC
We analyze how the structure of the LMC affects the information gain term (T) appearing in the regret bound. Recall that [(') upper bounds the quantity 2 log det(Ira x K ) where Kr is
the kernel matrix of the multi-output GP. Under the LMC structure, K = @ K where A
captures output correlations and K( is the kernel matrix corresponding shared latent GP. Using properties of Kronecker products and letting A; denote the eigenvalues of A, we obtain:
1 X2 kr)
log det
ITa +
= log det
ITa
+
A
&
KT
X
log det
Ir
A K
(0)
For the Matérn family of kernels, the information gain the latent scalar GP is known to satisfy (Vak- illi et al., 2021a; Whitehouse al., 2023):
(0)=()))
T
(T)
where a = 20+d < 1 depends on the input dimension and the kernel smoothness parameter v. Substituting into the sum, we obtain:
d
((
Th
))
T(T) Σσ
x2
T
δ
Σ
x
(26)
In the general case without structure, standard upper bound is given by:
I(T) ö ((
Td
X2
Comparing the two, observe that when A has low-rank behavior, specifically, when Σ Xo < d", the LMC-based bound (26) can be tighter. In particular, the regret bound becomes:
Regret = δ
Σ
A
T
(27)
This shows the effect of shared latent structure and output correlations on the regret bounds.
E Additional experiments
In this section, we provide further information about our experiments and additional results. Note that the code we used to run these experiments is available at /tttps://gitaee com/ jbayrooti/ TS pogret_study..
Model training. We model the reward and transition functions using a multi-output sparse varia- tional Gaussian process, trained by maximizing the evidence lower bound (ELBO) with the Adam optimizer (Diederik and Ba, 2015). A shared base kernel (either RBF or Matérn) is used across outputs, the outputs are linearly mixed according to matrix following linear model of coregion- alization (LMC). The model uses 100 inducing points per output dimension, zero mean function, and optimized for 20 steps per iteration using GPyTorch (Gardner et al., 2018). Full code included in the supplementary material for reproducibility.
21

---

RBF
Matten 2,5
Mallem 1.5
23
50
Curunatve Regeet
Cundraiie Pagget
40
15
80
-0
20
10
100
300
300
402
500
500
1000
1993
2000
2000
3000
303
1000
1500
2030
Episodes
Episodas
Epfoodos
Muram 2.5
Mulern 1.5
3000
2000
Corstrtie Reggtt
Curraatvve Rogeet
2000
Curpaatte
1600
8000
1000
100
000
0
900
9030
200
400
602
502
1000
200
400
500
500
1000
Figure 3: The first row shows the histogram of cumulative regrets over all trials on the last episode of RL-GPS training with each kernel. The second row shows the regret growth curves from all trials for each kernel.
Kernel complexity. We study the effect of kernel complexity regret using synthetic MDPs generated from 200 different Sa-sampled environments. For all GPs, we fix a random linear mixing matrix (see Appendix D),
0.9926
0.2082
0.4968
0..196
0.8869
0.1603
0.1557
-1.4231
-1.3905
In each trial, we sample new ground-truth reward and transition functions from the multi-output GP define an MDP. The optimal value function is then computed for this MDP via finite-horizon value iteration with horizon H 20. We train RL-GPS (Algorithm 1) for K = 1000 episodes in each environment and record the cumulative regret. Since the mixing matrix fixed, randomness within a trial arises only from the starting state distribution during rollouts. Across trials, randomness stems from variation in the sampled environments, which can differ significantly in difficulty. As result, we observe a substantial right-skew in cumulative regret, with a few environments producing particularly challenging instances. To demonstrate this variability, we show the cumulative regret at the final episode across all trials for each kernel as well as the individual regret curves for each trial Figure 3. All trials for each experiment run within 24 hours on one NVIDIA GeForce RTX 2080 Ti GPU.
Multi-output kernel structure. For this set of experiments, we train the multi-output GP using Matérn kernel with v = 1.5, comparing two modeling approaches: independent GPs and the linear model coregionalization (LMC). When using LMC, the mixing weights are learned during training, the randomness across trials arises only from the random initialization of the mixing weights and the starting states for rollouts. contrast to the earlier experiments, the environment itself is fixed across all trials. For the unconstrained navigation experiments, the horizon used is Hl 20 and the GP is updated for 20 optimization steps at each iteration. For the maze experiments, the horizon used also H 20 and, due to the increased modeling difficulty, the GP is updated for 50 optimization steps at each iteration. All trials for each unconstrained navigation experiment run within 24 hours one NVIDIA GeForce RTX 2080 Ti GPU. Due the greater number of GP updates in the maze setting, trials take longer to run and all 200 trials complete within 80 hours on the same hardware. Note that all experiments easily parallelizable.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We state the paper's main contributions in the abstract and introduction, including the problem setting, model, and algorithm considered. Our claims the abstract and introduction reflect the content and scope of the paper and are supported by both theoretical analysis and empirical evaluation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss the limitations of our analysis in the limitations paragraph in the conclusion.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We state the assumptions for all theoretical results in Section 4 and provide the complete proofs in Appendices A, B, and
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe the algorithm in Section 3, experimental setup in Section 5, and full details in Appendix Furthermore, we provide the code supplementary material so our results are reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code as supplementary material and the hyperparameterss in Appendix E. The code is documented with instructions reproduce the experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Sogllic/guidee//ooeSSttmii ooopoioooooiooooooooooooooo/ for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nips. cctpublic/guu httpl//cgguiee/eeeeeebbiiisseee hee////oouueieeeee wwwssssssiiggoiooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the experiment details are described in Section 5 of the main paper and the comprehensive details are provided in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
We report the mean performance with standard error over 200 trials in our main plots. In Appendix E, we provide more insights into the variance over trials by visualizing each individual curve.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We give details on the compute resources required to reproduce the experiments in Appendix E.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics https: httpp::////eriipee /tt///nurip..p/ cc ctw.iheeeiinnneeeeeeneennne
Answer: [Yes]
Justification:
Our research conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
26

---

Justification: This work provides theoretical no-regret guarantees for Thompson Sampling in reinforcement learning and is not tied any specific application deployment. As such, it does not directly introduce new societal risks beyond those already associated with reinforcement learning more broadly, ranging from benefits for healthcare to risks in safety-critical systems.
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not use or release data or models with high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite all creators whose code we use in our experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
27

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide our code as supplementary materials along with documentation explaining how to install and run the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
28

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this work does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy Inttps://neuria: for what should or should not be described.
29


Reviews:
[{"review_id": "s2qFXGFFLw", "reviewer": "Reviewer_19Xz", "summary": "This paper presents a theoretical analysis of Thompson Sampling (TS) for finite-horizon episodic MDPs. The authors introduce an algorithm, RL-GPS, which uses a multi-output Gaussian Process (GP) to jointly model the environment's reward and transition functions. The core contribution is a formal \"no-regret\" bound, which proves that the algorithm's performance asymptotically converges to the optimal policy. The paper includes experiments in synthetic environments to validate the sublinear regret growth and explore the impact of different GP kernel choices.", "questions": "See weakness.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n- The paper provides a rigorous theoretical analysis for TS in a continuous-state RL setting. \n\n- The paper is well-organized and clearly presents the problem, algorithm, and theoretical results. \n\n## Weaknesses\n\n- The reliance on a GP to model the environment dynamics is a major limitation. This assumption restricts the method's applicability to a very narrow class of problems where the true reward and transition functions are smooth and well-behaved. Many real-world episodic RL problems involve discontinuous, non-stationary dynamics that cannot be accurately captured by a standard GP model.\n\n- The empirical evaluation is insufficient to demonstrate the practical value of the proposed algorithm. The experiments are limited to internal comparisons between different kernel choices for RL-GPS and do not include any established benchmark methods from model-based or model-free RL (e.g., UCB-based approaches, PPO, SAC).", "was_revised": true, "final_justification": "Authors have address my concern on the restrictions on the MDP setting and provide the literature about the empirical performance of a close method. This shows the significance of study theoretical property for the proposed method.", "rebuttal": "Thank you very much for taking the time to review our paper. We appreciate your comments and are glad that you find the paper to be clear and well-structured and the theoretical analysis to be rigorous. We address the weaknesses highlighted in detail below and hope our responses will help improve your evaluation of the paper.\n\n**Weaknesses**\n\n1. *Relying on a GP to model the environment dynamics restricts the application to a narrow class of smooth, well-behaved true functions that may not be practical*. \\\nWe agree that GP modeling introduces an assumption about the true underlying environment that does not always hold (as explicitly stated in the Limitations section), however we believe it is not overly restrictive, especially when compared to existing regret analyses. To clarify this, we respond in several parts:\n   - GP models are often used for modeling complex dynamics in RL, particularly in low-data regimes where uncertainty quantification is critical. Notably, GP-based methods such as PILCO (Deisenroth and Rasmussen, 2011) and its successors have demonstrated strong empirical performance in continuous-control robotics.\n   - GPs offer flexible representation capacity as the smoothness of functions depends on the GP kernel choice. For example, the Mat&eacute;rn kernel family provides a smoothness parameter $\\nu$ that controls function regularity. As shown in Srinivas et al. (2010), functions sampled from Mat&eacute;rn kernels can uniformly approximate any continuous function on compact subsets of $\\mathbb{R}^d$, making the GP prior highly expressive. Lower values of $\\nu$ yield rougher functions that better capture non-smooth behavior. Thus, our setting can model a broad class of reward and transition functions, including those with limited smoothness.\n   - Our assumptions are milder than many related works on regret bounds for RL. For instance, the regret analysis for posterior sampling for RL (Osband et al., 2013; Osband et al., 2017) assumes a finite state-action space and does not extend to continuous MDPs, while RKHS-based regret analyses (e.g., Chowdhury & Gopalan, 2019) rely on predefined feature maps and a fixed kernel class, and linear MDP approaches (e.g., Jin et al., 2020) assume linearity in both rewards and transitions. In contrast, our multi-output GP model flexibly models correlations between reward and transitions without relying on discretization, linearity, or fixed feature representations.\n   - Our assumption that the true joint reward and transition function is drawn from a multi-output GP enables a tractable regret analysis in continuous state-action spaces. While GPs may not capture all real-world dynamics, such as sharp discontinuities, this setting still reflects many realistic control problems (e.g., MuJoCo environments) and provides an important intermediate step toward more general regret bounds.\n\n2. *Empirical evaluation is insufficient to demonstrate the practical value of the algorithm*. \\\nWe would like to highlight that, as mentioned in the introduction, one of the motivations for our work is the recent empirical success of a closely related algorithm called HOT-GP that is studied by Bayrooti et al. (2025). HOT-GP achieved strong performance on standard benchmarks such as MuJoCo and VMAS and outperformed both model-free (e.g., PPO, SAC) and model-based (e.g., MBPO, UCB-based) methods. While their work demonstrated the algorithm’s practical utility, it did not provide theoretical guarantees. Our goal is complementary: we focus on establishing theoretical bounds for this class of algorithms by deriving the first sublinear regret bounds guaranteeing convergence to the performance of the optimal policy. To support our analysis, we include controlled numerical experiments that align closely with our theoretical framework and are designed to corroborate the analytical findings. Specifically, our experiments confirm sublinear regret and illustrate how the kernel complexity empirically influences the learning efficiency relative to the theoretical dependence on $\\Gamma(\\cdot)$.\n\nThanks again for your review and we would be happy to further discuss any of these points during the author-reviewer discussion period."}, {"review_id": "rS2xhklCMX", "reviewer": "Reviewer_z43g", "summary": "The authors propose performing posterior sampling in reinforcement learning (PSRL) for infinite state-action space using Gaussian processes over deterministic rewards and transitions. The authors established a sublinear regret bound, improving prior work that only provided Bayesian regret guarantees.", "questions": "- Could you explain how Assumption 1 was used in the proof?\n- Is it possible to generalize the proof for the case of stochastic rewards and transitions (for example, in the Gaussian case)?\n- Is it possible to compare your results and assumptions with the results and assumptions in the case of kernel RL (see, e.g., Vakili and Olkhovskaya 2023)? It seems that the dependence on H for your algorithm is better than presented in (Vakili and Olkhovskaya 2023), but I am not sure that it is possible to compare these settings.\n\n\nRelated work that would be good to discuss:\nFan, Y., Chen, L., & Wang, Y. (2018). Efficient model-free reinforcement learning using gaussian process. arXiv preprint arXiv:1812.04359.\n\nVakili, S., & Olkhovskaya, J. (2023). Kernelized reinforcement learning with order optimal regret bounds. Advances in Neural Information Processing Systems, 36, 4225-4247.", "limitations": "The paper is of a theoretical nature and thus does not have a clear potential negative societal impact that needs to be discussed.\n\nRegarding the theoretical limitation, the paper needs to discuss Assumption 1 in more detail.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- First worst-case regret bound for PSRL-type procedure with Gaussian process regression with a very short and elegant proof technique.\n- Improvements from Bayesian to worst-case regret bound (although it is not discussed in the paper since it misses a reference to Fan et al. 2018. )\n\n## Weaknesses\n- Restrictive assumptions on deterministic rewards and transitions;\n- Lack of large-scale experiments (on MuJoCo, for example) that may add additional value.\n\nFan, Y., Chen, L., & Wang, Y. (2018). Efficient model-free reinforcement learning using gaussian process. arXiv preprint arXiv:1812.04359.", "was_revised": true, "final_justification": "The paper presents a very elegant analysis in the Bayes-RL paradigm. After the rebuttal, the practical motivation of the method became clearer to me, and I happily increased my score to Accept.", "rebuttal": "Thank you very much for reviewing our paper and for your positive and constructive feedback. Below we respond to your comments and questions in detail and we hope this will help improve your evaluation of the work.\n\n**Questions**\n\n1. *How was Assumption 1 used in the proof?* \\\nAssumption 1 is used in the proof to derive the confidence bounds that serve as a key building block in the regret analysis and are specifically used in Step 2 of the proof of Theorem 2 to bound the immediate regret. To elaborate more on this, our analysis is decomposed into four steps and Step 2 bounds the immediate regret, i.e., the loss in the optimal Q-function $Q^{\\star}(s_h, a^{\\star}_h) - Q^{\\star}(s_h, a_h)$, where $a_h$ is the action selected by the Thompson sampling algorithm at step $h$. This step relies on Corollary 1, which in turn is based on Theorem 1. Briefly, Theorem 1 establishes high-probability confidence intervals for composed GP functions and Corollary 1 applies this to recursive value functions in RL. These confidence intervals crucially rely on Assumption 1, which models the joint reward and transition functions as a multi-output GP. To clarify this connection explicitly, we have added this sentence before introducing Theorem 1: “Under Assumption 1, the true reward and transition functions are modeled with a GP prior, allowing us to derive high-probability bounds for compositional functions of the form $v(f)$.” We hope this improves the clarity and would like to note that the full derivation can be found in Appendices A and B and is also outlined in the proof sketch in Section 4.\n\n2. *Is it possible to generalize the proof for the case of stochastic rewards and transitions?* \\\nThank you for this insightful question. Generalizing to stochastic environments is indeed a natural next step and we view our work as a foundation for this direction. In the case of stochastic rewards, the extension is straightforward and does not affect our analysis. The confidence intervals remain valid as long as the GP noise parameter $\\lambda^2$ is chosen to upper-bound the variance of the reward noise. This adjustment ensures the posterior remains well-calibrated and the regret analysis proceeds as in the deterministic case. In contrast, generalizing to stochastic transitions introduces new challenges as this setting corresponds to GP regression with input uncertainty, since the state $s$ that is used recursively in the value function would depend on a random variable. Addressing this would require nontrivial extensions beyond the standard GP framework used in our work. Developing such tools is outside the scope of this paper but we believe the techniques that we introduce provide a strong foundation for extending regret analysis to stochastic transition dynamics in future work.\n\n3. *Comparing with kernel RL (Chowdhury and Gopalan, 2019; Yang and Wang, 2020; and Vakili and Olkhovskaya, 2023) and their dependence on $H$.*\nAll of these works assume that the conditional probability distribution of the next state belongs to the RKHS of a known kernel: $p_h(\\cdot \\mid s,a) \\in \\mathcal{H}_k$ for all $(s,a)$ and each step $h$. In contrast, our assumption is that the function $f(\\cdot \\mid s,a)$, which maps state-action pairs to next states, can be modeled using a GP and this model remains fixed across all steps $h$ within an episode.\n\n   There are also key differences in algorithm design: prior works adopt UCB-based approaches while we analyze Thompson Sampling.\n\n   Our regret bounds are not only tighter by a factor of $H$, but also by a factor of $\\sqrt{\\Gamma(T)}$ compared to Chowdhury and Gopalan (2019) and Yang and Wang (2020). This is particularly important, as their $O(\\Gamma(T)\\sqrt{T})$ bounds can become vacuous (i.e., linear in $T$) for many practical kernels such as the Mat&eacute;rn family. A key reason is the confidence intervals used in our analysis, which are tighter due to the Bayesian modeling of transitions via $f$ rather than the non-Bayesian RKHS assumption on $p_h$.\n\n   Roughly speaking, in a non-formal comparison of the regret analyses, the improved confidence intervals contribute a $\\sqrt{H}$ factor. In addition, while those works model $p_h(\\cdot \\mid s,a)$ separately at each step $h$ (i.e., non-homogeneous transitions), our model assumes that $f(\\cdot \\mid s,a)$ remains fixed across steps within an episode. This shared structure contributes another $\\sqrt{H}$ improvement. We will highlight these distinctions in the related work section for better clarity.\n\n   The gap in confidence intervals under RKHS assumptions is also evident in the Bayesian optimization literature, and is formally stated in the following COLT open problem: Open Problem: Tight Online Confidence Intervals for RKHS Elements, Sattar Vakili, Jonathan Scarlett, Tara Javidi, COLT 2021.\n\n*Discussing Fan et al. (2018).* \\\nThank you for pointing out the related work by Fan et al. (2018). We will add the reference and include a comparison in the paper. Their analysis builds on a technique from Osband & Van Roy (2017), which was introduced as a general method for establishing Bayesian regret, that is, the expected regret averaged over the distribution of all problem instances. In contrast, our notion of regret is stronger: we establish a high-probability bound that holds uniformly over all instances of the problem. As a result, our analysis requires fundamentally different and novel proof techniques.\n\n*Lack of large scale experiments.* \\\nWe would like to highlight that, as mentioned in the introduction, one of the motivations for our work is the recent empirical success of a closely related algorithm called HOT-GP that is studied by Bayrooti et al. (2025). HOT-GP achieved strong performance on standard benchmarks such as MuJoCo and VMAS and outperformed both model-free (e.g., PPO, SAC) and model-based (e.g., MBPO, UCB-based) methods. While their work demonstrated the algorithm’s practical utility, it did not provide theoretical guarantees. Our goal is complementary: we focus on establishing theoretical bounds for this class of algorithms by deriving the first sublinear regret bounds guaranteeing convergence to the performance of the optimal policy. To support our analysis, we include controlled numerical experiments that align closely with our theoretical framework and are designed to corroborate the analytical findings. Specifically, our experiments confirm sublinear regret and illustrate how the kernel complexity empirically influences the learning efficiency relative to the theoretical dependence on $\\Gamma(\\cdot)$.\n\nThanks again for your review and we would be happy to further discuss any of these points during the author-reviewer discussion period."}, {"review_id": "iInXXSwriq", "reviewer": "Reviewer_7dz9", "summary": "The paper analyzes Thompson Sampling (TS) in episodic finite-horizon Markov-Decision Processes whose reward and transition dynamics are modeled jointly as a multi-output Gaussian Process (GP), and proves a sublinear regret bound of $\\tilde{\\mathcal{O}}(\\sqrt{K H \\Gamma(K H)})$ over $K$ episodes of horizon $H$,\nwhere $\\Gamma(\\cdot)$ is the complexity of the GP model.  This paper demonstrates the confidence bounds for composed GPs and extend traditional elliptical potential lemma to multi-output cases. The regret bound is validated by numerical experiments.", "questions": "1. Could you explain more on the novelty of the paper? The idea follows Posterior-Sampling RL (PSRL).  Moving from two  GPs to one multi-output GP is not very novel. Moreover, most  proofs of the main results look standard or straightforward. The proof of Theorem  1 is a direct application of Taylor expansion and confidence bounds for the standard GP. The proof of multi-output elliptical potential lemma  seems to be a simple extension of standard elliptical potential lemma. Could you explain the novelty and key part in theoretical analysis?\n\n2. The numerical experiments are on small-scale problems with $\\mathcal{S}=[0,1]^2$ and $\\mathcal{A}=[0,1]$. This toy example is small. My concern lies in the scalability with respect to the cardinality and dimension of the state and action spaces. Moreover, there is no comparison with other benchmarks.\n3. Could you offer a practical example where Assumptions 1-2 hold?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 1, "strengths_and_weaknesses": "**Strengths:**\n\n1. This paper is a complete work with both theoretical guarantees and numerical results. The regret bound is shown with rigorous proofs.\n2. Paper is well structured and easy to understand.\n3. Tools (Theorem 1, Lemma 1) are likely reusable in other Bayesian-RL analysis.\n4. First regret bound for TS with joint GP modelling of reward and transition.\n\n**Weakness:**\n1. This paper assume strong modeling assumptions: rewards and dynamics are jointly Gaussian and value functions  are twice differentiable with bounded Hessian (Assumptions 1–2). This may be not applicable in most practical problems.\n2. Experiments are on small-scale probllems (2-dimensional states, discretised) and lack comparison with other baselines.\n3. There is not much novelty in the proposed idea. The proposed algorithm is a simple extension of posterior sampling RL (PSRL) by replacing posterior distribution with a Gaussian process, which is a non-parametric counterpart of posterior distribution, and most analysis procedures are standard.", "was_revised": true, "final_justification": "Authors clarify the technical novelty of their paper in the response, which previously was my main concern. Although their paper lacks large-scale experiments,  it may helps to future works about TS with GP.", "rebuttal": "Thank you very much for your time spent reviewing our paper. We are glad that you find the work complete, the paper well-structured, and the proofs rigorous with some results reusable by the community. We address your comments in detail below and hope this will help improve your evaluation of the paper.\n\n1. *Significance of contribution and technical novelty.* \\\nThank you for the opportunity to clarify this. At a high level, both TS and RL  are known to be inherently challenging to analyze. For instance, although TS is a natural algorithm dating back to Thompson (1933), its first rigorous analysis in the much simpler setting of K-armed bandits only appeared in the 2010s (Agrawal and Goyal, 2012; Kaufmann et al., 2012a). Extending such analyses to the RL setting, particularly with continuous state and action spaces and minimal structural assumptions, remains a significant open challenge.\\\nOur work takes a step forward in this direction by providing, to the best of our knowledge, the first sublinear regret bound for TS in continuous state-action MDPs using multi-output GP modeling of the reward and transition functions. We build on tools from the literature while also introducing key theoretical contributions to overcome challenges in this setting through a modular proof strategy. We highlight these innovations by walking through our analysis:\n   - Step 1: We decompose the regret into an immediate regret term and a recursive term that captures uncertainty in value propagation through the transition model.\n   - Step 2: Bounding the immediate regret term presents two unique challenges as outlined in Section 4. Namely, (i) the target function $Q^\\star_h(s, a) = f_R(s, a) + V^\\star_{h+1}(f_S(s, a))$ is recursive and compositional, and thus cannot be directly modeled as a GP; and (ii) the TS algorithm samples from the posterior of a proxy $Q_{h,k}$, rather than from the true posterior over $Q^\\star_h$. To address these issues, we derive high-probability upper and lower confidence bounds on the proxy and target value functions (Theorem 1). These bounds allow us to relate the sampled proxy values to the true values and quantify the regret incurred. This confidence analysis, which handles recursive composition under GP priors, is novel to our setting.\n   - Step 3: We extend the confidence bounds to the multi-step setting to analyze the propagation of uncertainty over the full episode.\n   - Step 4: Finally, we bound the uncertainty accumulated across all steps and episodes, which requires controlling the sum of posterior standard deviations over the sequence of inputs. In the multi-output setting, a naive approach would apply the standard elliptical potential lemma independently to each output dimension, resulting in a regret bound that scales with $\\sqrt{d \\Gamma(T)}$ where $d$ is the number of outputs. Instead, we introduce a new multi-output elliptical potential lemma (Lemma 1) that tracks uncertainty jointly across all outputs using the full output covariance structure. This avoids summing over independent bounds for each output and leads to a strictly tighter regret bound that scales with $\\sqrt{\\Gamma(T)}$ and is independent of the output dimension $d$. This improvement is essential for scalability and highlights the benefit of using a multi-output GP model rather than independent GPs.\n\n   In summary, while the algorithm we consider follows the general structure of posterior sampling, our analysis addresses a much more complex setting and introduces new analytical tools that are broadly applicable to related problems in RL and Bayesian learning (as noted by the reviewer). We therefore respectfully disagree with the reviewer’s assessment of the significance of our contribution as we believe that our work addresses an important and technically challenging problem of interest to the NeurIPS community.\n\n2. *Lack of large-scale experiments.* \\\nWe would like to highlight that, as mentioned in the introduction, one of the motivations for our work is the recent empirical success of a closely related algorithm called HOT-GP that is studied by Bayrooti et al. (2025). HOT-GP achieved strong performance on standard benchmarks such as MuJoCo and VMAS and outperformed both model-free (e.g., PPO, SAC) and model-based (e.g., MBPO, UCB-based) methods. While their work demonstrated the algorithm’s practical utility, it did not provide theoretical guarantees. Our goal is complementary: we focus on establishing theoretical bounds for this class of algorithms by deriving the first sublinear regret bounds guaranteeing convergence to the performance of the optimal policy. To support our analysis, we include controlled numerical experiments that align closely with our theoretical framework and are designed to corroborate the analytical findings. Specifically, our experiments confirm sublinear regret and illustrate how the kernel complexity empirically influences the learning efficiency relative to the theoretical dependence on $\\Gamma(\\cdot)$.\n\n3. *Assumptions.* \\\nBelow we clarify how Assumptions 1 and 2 relate to theory and practice.\n   - Assumption 1: GP models are often used for modeling complex dynamics in RL, particularly in low-data regimes where uncertainty quantification is critical. Notably, GP-based methods such as PILCO (Deisenroth and Rasmussen, 2011) and its successors have demonstrated strong empirical performance in continuous-control robotics. GPs offer flexible representation capacity as the smoothness of functions depends on the GP kernel choice. For example, the Mat&eacute;rn kernel family provides a smoothness parameter $\\nu$ that controls function regularity. As shown in Srinivas et al. (2010), functions sampled from Mat&eacute;rn kernels can uniformly approximate any continuous function on compact subsets of $\\mathbb{R}^d$, making the GP prior highly expressive. Lower values of $\\nu$ yield rougher functions that better capture non-smooth behavior. Thus, this assumption holds for a broad class of reward and transition functions, including those with limited smoothness, so we believe it is not overly restrictive.\n   - Assumption 2: This is a mild technical condition required for Theorem 1 to ensure that value functions admit Taylor expansions with controlled error. This holds when the reward and transition functions are differentiable with bounded first and second derivatives.\n   - Assumptions 1 and 2 hold in many continuous-control tasks common in RL, such as the Gymnasium Pendulum and MountainCarContinuous tasks. These environments have smooth, deterministic transition dynamics and reward functions, making GP modeling appropriate and ensuring the value functions are sufficiently smooth.\n\n   While these assumptions do not capture all real-world dynamics, our setting still reflects many realistic control problems and provides an important intermediate step toward more general regret bounds. Moreover, our assumptions are relatively relaxed compared to standard assumptions in prior RL theory. For instance, the regret analysis for posterior sampling for RL (Osband et al., 2013; Osband et al., 2017) assumes a finite state-action space and does not extend to continuous MDPs, while RKHS-based regret analyses (e.g., Chowdhury & Gopalan, 2019) rely on predefined feature maps and a fixed kernel class, and linear MDP approaches (e.g., Jin et al., 2020) assume linearity in both rewards and transitions. In contrast, we give a complete analysis under one of the more general settings considered in the literature.\n\nThanks again for your review and we would be happy to further discuss any of these points during the author-reviewer discussion period."}, {"review_id": "gBw5PY5Rzf", "reviewer": "Reviewer_oQJt", "summary": "The paper showcases new bounds for Thompson Sampling algorithms in Reinforcement Learning under Gaussian Process assumptions for the rewards and transition functions. It considers the case where the a multitask GP is used to generate reward and transition functions, which at its simplest case covers Bayesian optimisation, as well as more complex RL tasks. \n\nThe first challenge that the paper faces is the fact that the optimal value function is not a GP but a composition of GP (deep GP). Theorem 1 provides confidence bounds for the this case, where the bounds depend on the standard deviation up to a quadratic term, with constants depending over the gradient and hessian of the value function.\n\nUsing this, Theorem 2 is proved which bounds the regret of the algorithm, achieving bounds of: $$ \\mathcal{O}(\\log(T)d / \\delta) \\sqrt{T \\Gamma(T)} $$\n\nwhere $d$ is the output dimensionality, $\\delta$ the probability that the bound does not hold, and $\\gamma$ an upper bound on the information gain. \n\nThe proof follows the steps:\n\n1. Decomposing the regret into an immediate step, and a recursive part. \n\n2. Bounding the immediate regret. This is done by considering the confidence bounds on the value functions which are compositional.\n\n3. The regret then gets accumulated across each episode (i.e. for $K$ episodes of length $H$, we accumulate accumulate into $K$ parts.\n\n4. The sum of all $K$ per-episode regrets are bounded. \n\nThe individual regrets are using the elliptical potential lemma for multi-output GPs, which extends a classical result that sums of variances of sequences of inputs can be bounded by the log-determinant term. The extension allows for tighter bounds when considering multi-output GPs. \n\nThe theoretical findings are then empirically validated.", "questions": "- Are there any real-life examples where the algorithm has been used in the literature?", "limitations": "Limitations are discussed at the end of the paper.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- Quality: The paper appears to be technically sound and there are no errors I could find. \n\n- Clarity: I found the paper very easy to read and well structured, I was able to follow all arguments even if I am do not have much experience with theoretical work. Clarity on the experimental section could be improved though. \n\n- Significance: Regret bounds are always an important development, and it is good to obtain them for Thompson Sampling, since many algorithms use it. This work can serve as a stepping stone to future bounds for new algorithms.\n\n- Originality: The bounds appear to be novel. \n\nWeaknesses:\n\nThe experimental section is not written clear enough, as it is difficult to understand the link between the results and the theoretical findings. In short: the figures tell very little without referring to the large amount of text, it would be nice to find a way a visual way of showing the link between the experiments and the empirical results.", "was_revised": true, "final_justification": "Having read the other reviews and rebuttal, I maintain my original decision to recommend acceptance. This stems from my belief that theoretical contributions are difficult to obtain and should be valued, even if they will naturally cover smaller application areas.", "rebuttal": "Thank you very much for reviewing our paper and for your positive feedback. We are pleased to hear that you found our regret bounds to be a valuable contribution to the community and appreciate the practical recommendations. We address your comments below and hope this will help improve your evaluation of the paper.\n\n**Weaknesses**\n\n1. *Unclear experimental section*. \\\nThank you for highlighting this. We agree that a more detailed explanation of the link between the experiments and theoretical analysis would improve clarity. Our experiments are specifically designed to validate our theoretical findings by confirming the sublinear growth of cumulative regret, consistent with our $\\mathcal{\\tilde{O}}(\\sqrt{KH\\Gamma(KH)})$ bound, and by illustrating how the choice of GP kernel influences learning efficiency in line with the theoretical dependence on $\\Gamma(\\cdot)$. To emphasize these connections, we will add approximate theoretical reference curves to Figures 1 and 2 in the camera-ready version to visually highlight the sublinear regret growth predicted by our theory relative to the regret growth in practice. We are also open to incorporating additional visualizations if recommended (although we are constrained by this year’s rebuttal format and cannot upload revised figures at this stage).\n\n**Questions**\n\n1. *Are there examples of the algorithm in literature?* \\\nYes, the algorithm we study is closely related to a recent approach called HOT-GP (Bayrooti et al., 2025), which achieved strong empirical performance on standard benchmarks such as MuJoCo and VMAS. On these tasks, HOT-GP was shown to match or outperform both model-free (e.g., PPO, SAC) and model-based (e.g., MBPO, UCB-based) methods. While this prior work showed the algorithm’s practical utility in simulated robotics settings, it did not provide theoretical guarantees. Our work abstracts the core ideas behind HOT-GP into a form that enables a rigorous regret analysis, serving as the theoretical foundation for this class of algorithms.\n\nThanks again for your review and we would be happy to further discuss any of these points during the author-reviewer discussion period."}]

Author rebuttal:

Meta-review: The paper analyzes Thompson Sampling for episodic finite-horizon MDPs under a joint Gaussian-process model of rewards and transitions and proves a high-probability sublinear regret guarantee. The analysis tackles the non-Gaussian, recursive Bellman composition of value functions and introduces a multi-output elliptical potential lemma to control uncertainty jointly across outputs, yielding tighter bounds than applying single-output results independently. Controlled experiments are aligned to the theory and illustrate the predicted dependence on kernel complexity. The writing is clear and the technical development is careful. 
 
Across the reviews and discussion, the overall evaluation is positive: the theoretical contribution is regarded as rigorous and well organized, with the empirical section serving primarily to corroborate the analysis. Remaining questions centered on the scope of GP assumptions and on clarifying what is genuinely new in the proof pipeline; the authors’ responses clarified assumptions, positioning, and how the key steps extend prior TS analyses, and they committed to adding reference curves and sharpening novelty statements in the camera-ready. 
 
After weighing the overall feedback, the AC places particular weight on a detailed technical assessment that viewed the modular proof steps as meaningful contributions while asking for a clearer separation of new versus standard ingredients and a minimal comparative benchmark to better connect the theory to practice. 
Overall, this is a nice paper with a solid result, clear exposition, and reusable tools. The AC recommends acceptance, with a camera-ready that more explicitly highlights what is new in the proof pipeline, clarifies the role of the assumptions, and, if space permits, please incorporate suggestions that arise from the discussions.
Decision: Accept (poster)