Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning
Authors: Ahmadreza Moradipari
Mohammad Pedramfar
Modjtaba Shokrian Zini
Vaneet Aggarwal
Venue: NeurIPS 2023 poster (2023)
Keywords: Thompson Sampling
Reinforcement Learning
Bayesian Regret

Abstract: In this paper, we prove state-of-the-art Bayesian regret bounds for Thompson Sampling in reinforcement learning in a multitude of settings. We present a refined analysis of the information ratio, and show an upper bound of order $\widetilde{O}(H\sqrt{d_{l_1}T})$ in the time inhomogeneous reinforcement learning problem where $H$ is the episode length and $d_{l_1}$ is the Kolmogorov $l_1-$dimension of the space of environments. We then find concrete bounds of $d_{l_1}$ in a variety of settings, such as tabular, linear and finite mixtures, and discuss how our results improve the state-of-the-art.

Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning
Ahmadreza Moradipari" f
Mohammad Pedramfar"
Modjtaba Shokrian Zini"
Vaneet Aggarwal 9
Abstract
In this paper, we prove the first Bayesian regret bounds for Thompson Sampling in reinforcement learning multitude of settings. We simplify the learning problem using discrete set of surrogate environments, and present refined analysis of the information ratio using posterior consistency. This leads an upper bound of order
Ö(H di, T)) in the time inhomogeneous reinforcement learning problem where H is the episode length and di, the Kolmogorov ( -dimension of the space of environments. We then find concrete bounds of di, in a variety of settings, such as tabular, linear and finite mixtures, and discuss how how results are either the first of their kind or improve the sate-offthee-as
Introduction
Reinforcement Learning (RL) is sequential decision-making problem in which agent interacts with an unknown environment typically modeled as a Markov Decision Process (MDP) [38, 8). The goal of the agent is maximize its expected cumulative reward. This problem has variety of applications, including robotics, game playing, resource management, and medical treatments. The key challenge RL is balance the so-called exploration-exploitaaie trade-off efficiently: exploring unseen state-action pairs to gain more knowledge about the unknown environment or exploiting the current knowledge maximize the expected cumulative reward. Two efficient approaches have been developed to control this trade-off: optimism in the face of uncertainty (OFU) and Thompson Sampling (TS) (or Posterior Sampling (PS)). OFU constructs confidence set of statistically plausible MDPs that includes the true MDP with high probability and plays optimistic policy according to the MDP with maximum gain from this set [5, 40). TS samples a statistically plausible MDP from posterior distribution and plays the optimistic policy of the sampled MDP [29, 31]. In this work, we focus on the latter, and by combining an information theoretical approach first introduced by [36] with analysis based on posterior consistency tools, we prove sfate-of-the-art Bayesian regret bounds variety of settings.
In this paper, we start by defining the Bayesian RL problem, where transition and reward functions are Bayesian and time inhomogeneous. The Bayesian RL problem we consider more comprehensive than in previous works, as we allow for both Bayesian transition and Bayesian rewards, and do make any assumption on their individual prior. To simplify the learning problem, we utilize the notion of surrogate environments, which is discretization of the environments space, and its learning task and TS regret is proxy that of the main problem. The construction of the surrogate environments was first introduced by [18] with an incorrect proof, which is fixed in our work by
Authors have equal contribution
Toyoda Moter North America, InfvTTech Labs, Mountain View. CA. USA, ahmadroza www.ddppasttoyots..commm spedrand Spurduo.
Purdue University, Lafayette,
6 sodjjtbba, shoke inniiiiiininnnnee @guail con.
Purdue University, West Lafayette IN, USA, vaneet edu
This work was supported in part by the National Seience Foundation under grant 0C5-214958 and Cisco, Inc.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

defining the surrogate environments through an optimization. Of main importance is the size of this new environment space. The Bayesian regret decomposes to the product of two terms, one being the cumulative mutual information of the environment and history traversed by the policy. By the well-known entropy estimation of the mutual information, this significant factor in the regret connected to the 1 -idienniionss (di,) of the transition and reward functions space, which can be more succinctly interpreted as the ( -dimennsion di, of the environment space. The latter is in turn estimated by the size of the space of surrogate environments.
The information ratio, representing trade-off of exploration/cxplotttiin is the other significant term in the decomposition of the TS Bayesian regret. In an improvement to [18], our novel analysis of this ratio based on posterior consistency tools, shows that this trade-off is bounded by H where H is the episode length. This bound is general and independent of the dimension of transition/reward function space at each step, which is is a key factor behind the advantage of our regret bound, such as the VSA advantage in the tabular case compared to [18], or the lack of any restriction on the prior (e.g., Dirichlet prior) compared to [31]. Following further refined approach, we finally estimate the TS Bayesian regret to be O(> /di T) for large enough T in the time inhomogeneous setting. X Here, a new term 'value diameter' X, which is the average difference of the optimal value functions at different states, is used in bounding the information ratio, where instead of H3/2, we have the smaller term 1/2, Bounding the information ratio with is a conceptual contribution of our work, which shows that the ratio is bounded by a value-dependers term, which is in nature different from H but always I H + 1. Further, there exists another bound for X; in environments where states are reachable from one another in D steps, we have À < D + 1. In 'well-connected' MDPs, one could have D < H, implying an improvement over the 3/22 information ratio bound.
Our generic bound is abstract in terms of di, so we estimate it in more explicit terms for useful applications. [18] have bounded di, in the tabular and linear case without formalizing this notion, and while for tabular MDPs, d,, was bounded by SAH, for linear MDPs with feature space dimension dy, we investigate their claim of the bound y H. Detailed in Appendix G, we show a countercxample to their analysis, and manage find correct estimate in this setting. We also introduce finite mixtures MDPs and are the first prove a TS Bayesian regret of order OAAHHmT)) where m is the number of mixtures.
Lastly, we note that our regret bound of order ((Add, d,, T) is the first in the general nonlinear time inhomogeneous Bayesian RL setting for TS, and generalizing [31, Conj. 1], we conjecture it to be optimal if À can be replaced by Ö(VH).
Related work. Since the introduction of information ratio by [35, 36), new line of research has emerged to provide tighter regret bounds for TS. The general approach involves factoring the Bayesian regret into two components: information ratio that captures the trade-off between optimal action selection and information gain, and a cumulative information gain term that depends on the target environment and the history of previous observations. Then, both components are bounded separately using information theoretic tools.
In the bandit setting, this analysis has been used to bound Bayesian regret for TS [14, 9]. as well as that of a new algorithm called information-directer sampling (IDS) [35, 26, 23, 19, 20]. This analysis has also been used in partial monitoring [25, 24] and RL with specific Dirichlet prior and additional assumptions [28, 27] or when the true environment is too complicated to learn [4]. More recently. [18] studied the Bayesian regret of TS in RL without any prior assumptions for tabular MDP. This is the closest work to our paper and we discuss our generalization in detail in Section 5.
The Bayesian tabular MDP case has also been studied with the additional Dirichlet prior assumption in [31], where they achieve regret bound matching ours. In an independent approach, the first non-linear Bayesian RL model was considered by [16] with regret bound of 3//3/221122 where d
a notion of dimension of their model, but their results were limited to Gaussian process settings with linear kernels. Finally, [11] considered general non-linear Bayesian RI. models and introduced an algorithm that obtains 1 where a is tuning parameter and d is the dimension of A S.
worth noting that there is another line of work that incorporates confidence regions into TS to achieve Bayesian regret bounds that can match the best possible frequentist regret bounds by

---

UCB in both bandit settings [35] and RL [31, 30, 32, 12]. However, this technique often results in sub-optimal Bayesian regret, as the best bound known for UCB itself is not optimal.
Table I: Bayesian regret bounds for TS (i.e. PSRL)
Reference
Tabular
Linear
General
Comments
[29]
V AA
Uses Eluder dimension
[30]
Le dgddhHL
Lipschitz assumption
[31]
VH
Dirichlet prior
[28]
v VHSSAL
Assumptions on prior
Assumptions on regularity & noise Lipschitz assumption
[12]
L" AL
L' HL
[18]
VH
Assumptions & 2 Holds in the limit L + oc
This paper
XVISAAL
Avdd, HT
dy HL
As discussed in Scction 4.3 of [16), the Lipschitz term L", which is used in the grayed papers in the table, may grow exponentially in episode length. Note that [18] claims regret bound for the linear setting. However, as discussed in Appendix G.I. their proof is incorrect.
While our work's emphasis is on theoretical guarantees for TS, we discuss here the experiments using this algorithm. Previous works on PSRL [35, 26, 23, 20, 31] come with extensive experiments on TS (and/or its variants), and diseussions on computational efficiency of PSRL. In particular, experiments in [31] support the assertion that "PSRL dramatically outperforms existing algorithms based on OFU". In addition, PSRL with oracle access has been shown be the most performant, esp. when compared to recent OFU based UCBVVUCCVI-B, or even variants of PSRL such as Optimistic PSRL [39, Fig. 1.3]. However, an important limitation in experiments is the need for oracle access to an optimal policy, and that can not be always satisfied efficiently. Nevertheless, clever engineering can make TS work even in large scale Deep RL. Indeed, for general RL settings, the recent work [37] shows how to implement TS in Deep RL on the Atari benchmark and concludes that "Posterior Sampling Deep RL (PSDRL) significantly outperforms previous state-of-the-as art randomized value function approaches, its natural model-fre counterparts, while being competitive with state-of-the--e art (model-baseed reinforcement learning method in both sample efficiency and computational efficiency". In summary, experiments in the literature provide enough support for the empirical performance of TS.
2 Preliminaries
2.1 Finite-horizon MDP
We follow the literature's conventions in our notation and terminology to avoid confusion when comparing results. The environment tuple & = (S. A. M.A. H. (= (r>) where S is the topological measurable state space, AA is the topological measurable action space. As and μa are base probability measures on S and A respectively, H the episode length, Ps SS - As,us is the transition probability kernel, and rı S x A Lebegeee is the reward function, where
we fix the convention r(s, a) := E2, [r(]s a)] = fo xr(z]s, a) dr as we mostly deal with its mean X that absolutely continuous to J.. We will use A x when the base measure is clear from the context. We assume S, A are known and deterministic while the transition probability kernel and reward are unknown and random. Throughout the paper, the implicit dependence of P/, and ry on & should be clear from the context.
value. Notice that A x, is the set of probability distributions with respect
Let Of be the topological function space of Pn, and @ = Of x .... x O be the full function space. The space Of is assumed to separable and equipped with prior probability measure pf. yielding the product prior probability measure p = of @ ... @ p for OP. The exact same definition with similar notations O R pa, R applies for the reward function. Notice the explicit assumption of time inhomogeneity in these definitions, with all 'layers' h being independent. The two sets define the set of all environments parametrized by = 0 x .... x Oh where O = 0i x Of Note that the prior is assumed to be known to the learner. This setting implies that an environment & sampled according to the prior p = pf 69 y essentially determined by its transition and reward functions We simplify the notation to view θ as the set of all environments, i.c., saying pair ((hh, Th) H 1=z1-
3

---

E E θ should be viewed as ((PR,T E θ. The space of all possible real-valued functions {(P), rh)] has a natural vector space structure. Therefore it is meaningful to discuss the notion of the convex combination of environments. We assume that θ is a convex subspace of the space of all possible environments. This assumption is not restrictive, since we may replace any environment space with its convex hull. Note that we do not assume that the support of the prior is convex.
Remark 1.
The case of joint prior may be of interest, but to our knowledge all prior works also take pf, p be independent.
Agent, policy and history. An agent starts at an initial state si, which is fixed for all episodes É. It observes state sy, at layer h episode E, takes action d and receives reward r/. The environment changes to the next random state =h with probability Pn. ( of). The agent stops acting at +11+1 and the environment is reset to its initial state.
We define He, as the history (sf: a4, rf, ri....,, s/. ah. rf)) Denote by Dr =HH,, 14-1.H) the history up to episode f, where Dj := 0. Finally, let O2 = II (S x A x [0, 1]) be the set of all possible histories up to layer
A policy is represented by stochastic maps (TI,..., , where each Th 2 x S + A A.Ma Let Tlg denote the entire stationary policy class, stationary meaning dependence only the current state and layer and let II C lls.
Value and state occupancy functions. Define the value function Vi, as the value of the policy πT interacting with layer h:
h (s) = E
Σ (sw an) 8h =
(I)
where BE denotes the expectation over the trajectory under policy, transition, and reward functions T, Ph. Th- The value function step H + 1 is set to null, ())+ == O. We assume there is measurable function T θ > II such that h (s) max Vh (s), Vs S, E [H]. The optimal policy πt is a function of ε, making it a random variable in the Bayesian setting. Lastly, let the state-action occupancy probability measure be P (sh, 8, az = a), also known the state occupancy measure under policy æ and environment E. It follows from the definitions that this measure is absolutely continuous with respect to USSAA
us PA- Let d (s, a) denote the Ridon-Nikodym derivative so that we have df, d = dPf(s) = s, ag = a). We will assume throughout the paper that this density (s, a) is measurable and upper bounded for all S.E,saa h. The upper bound is reasonable assumption, and it happens trivially in the tabular case (s a) < SA). This also happens, e.g., when one assumes that the maps (E, s, a, s', h) + P (s']s, a) and (T, 8, a, h) + ग. (als) are continuous and O, S, A and the set of all optimal policies (as subset of II) are compact.
2.2 Bayesian regret
We formulate the expected regret over L episodes and T LH total steps in environment & as
Vi,ng (51) Vi (c1))
RE E
f=1
where the expectation is over the randomness of (5')e- The Bayesian regret is ( (E, For Thompson Sampling (TS), the algorithm selects the optimal policy of given sample & picked from the posterior E IP E :De):
TTS = argmax, en V
V (sf)
Importantly, the law of TS aligns with the posterior, i.e., P(E = P( = T2(
Remark 2. Note that P ( = o (Dr) is a probability for a specific measure on the space of optimal policies. To ensure that JTT P( (D:)dmm- = 1, we need an appropriate measure pmT on I1* Given the law of TS, the natural choice for this measure is the fosh-forward of the prior measure under the map star: θ + II., where star(E) n

---

2.3 Notations
For Bayesian RL, conditional expressions involving given history Dj are widely used. We adopt the notation in [18] refer to such conditionals; let Pe(-) == P(-)D.), Eel == B[-[De]. We can rewrite the Bayesian regret as
I. = BRL(T)
Σ t=1
E
Et
Ve 1,7g
(sf) - Vi, (sf)]
(4)
and define the conditional mutual information IX( DKI (P(,())(XX))) E e E P(Y E (Dz))) For a random variable and random policy x, the following will be involved in the information ratio:
I7 (c: He,)) == Te(x; He)lT) = (F He,,) PT) e 1x) 2 Pe(Men E [T))]
(5)
Note that [[[,(X; = I(x; To clarify, (Pee, E -|xz) is the probability of Hegh being generated under т within some environment. Given that the histories under consideration are generated by the TS algorithm, they always generated in the true environment & under optimal policy zg.. For π = Tis. this can be computed as (He, (T) = Se P(He,, T TTEE) dP)(), where P(He,NTT,E) ) is an expression in terms of transition and reward functions of & and m.
Finally, we define & as the mean MDP where P (-|s, a) EeIP, (-Is, a)] is the mean of posterior measure, and similarly for o (-1s, a)
Ee ( We note that under the independence assumption across layers, the same is given for the state-oceupancy density dfe h1r = Ex(df.n]
Bayesian RL problems
Definition 1. A Bayesian RL in this paper refers to the time-inhomogeneouss finite-horizon MDP with independent priors on transition and reward functions, as described in Section 2.1.
The Bayesian RL problem is the task of finding algorithm æ with optimal Bayesian regret as defined in Eq. (4), Below we list the variations of this problem. A setting considered by most related works such as [31, 16] is the following:
Definition 2. The time (reward) homogeneous Bayesian RL refers to the Bayesian RL setting where the prior pf (p is over the space OF (0R) containing the single transition (reward) function P (r) defining& E, i.e., all layers have the same transition (reward) functions.
Definition 3. The tabular Bayesian RL is Bayesian RL where S.A finite sets.
Definition 4 (Linear MDP [41, 22]). Let o² S A + R4,, S²: S x A - Rdf be feature maps with bounded norm | a)l2 (1, a)ll2 S The linear Bayesian RL is a Bayesian RL where for any = {(P) H E θ, there exists vector-valued maps v (s), v R.E (s) ( norn such that for any (s, E A.
with bounded
(1), A. (6 (F)
= (0 a), (s), RE (-) th
(6)
A restricted version of the finite mixtures called linear mixture was first considered in [6] in the frequentist setting. Here, we consider the general setting.
Definition 5. The finite mixtures Bayesian RL is Bayesian RL where for any [H] there exists fixed conditional distributions {Zf,, : S A As m for any environment & given by {(PE h + there exists parametrized probability distributions P.E an : A -
A and { A " such that
A ah S x A + Amp such that
REE
m
m
PV (-1s, Σ
P.E. hit (s, a) 2P (1s,a),, a(()))))=
Σ
hi (s, a) 2) (-1s,
R.E
1=1
5

---

4 Surrogate learning
Next, we define the discretized surrogate learning problem, and bound the size of the surrogate environments space, significant term in the regret. To do so, we need to first define the Kolmogorov dimension of set of parametrized distributions, esp. working out the case of didstannce. In the definitions below, we implicitly assume any required minimal measurability assumptions the involved sets.
Definition 6. Given set F of O- parametrrzze distributions P: P - A(S) over set S where
both O,S are measurable. Let M).:)) F x F R2 be a distance, i... MMP, Q) > 0 i
P = Q. Then its right e e-covering number is the size KM(E) of the smallest set CM(()) = {P1 ....... PKmle)) C F such that
vP EF, 3P E CM()): M(P.P))
(8)
The potential asymmetry of M (e.g., KL-divergence) requires the notion of left/right covering number. The right covering number will be the default, so covering number will always refer to that.
Definition 7. Let dm(() (M)()) Define the Kolmogorov M-dimension dM of F as
dm limsup dm(E) c1> log( !
(9)
For 4 (P, supoeo - Q(110]l1+ applying Definition 6 to the sets 0 0 with O S x A, and denote the respective covering numbers by (e), LE()) corresponding to covering sets C, C (E)). Similarly applying Eq. (9) and denote the corresponding didimenss by
df (c), d (E), df,, and df == Σn df,, of == Σn df,,. The sums di, = df,,, di di, df + df can be interpreted as the 1 dimension of θ, and O, i... the environment space.
Remark 3. We also apply this framework the KL-divergence, by MKL(P, This was implicitly used by [18] to prove their regret bound in
sup.go DKL (P(((o))))Q(()1))))) the tabular case. Note that Pinsker's lemma (Lemma 9) implies that the KL-divergence is larger than the squared total variance, and the latter is trivially larger than the I distance. Therefore, didimensoon is smaller than d allowing for tighter regret bounds.
We now revisit the definition of e- partitions and show their existence is guaranteed by finite 4 covering numbers. These partitions are the origins of surrogate environments.
Definition 8. Given e >> an 5 value partition for a Bayesian RL problem a partition ) over θ such that for any & E [K] and E
)K
E E Op.
T.,g($$)
( SE.
(10)
A layered E value partition is one where the transition functions are independent over layers after conditioning on k. Throughout this paper, we will only consider layered e- e-value partition. We define Ksur(()) as the minimum K for which there exists layered & value partition.
Inspired by Eq. (9), we define the surrogate dimension as d lim sup log(1/c)
Kaurr (6)
Lemma 1. Given a Bayesian RL, we have Kaur (s) < II, (f(ss((1)) x (e((())) This implies deurr S di,-
The above is proved in Appendix B. It is hard to find deurzs but one can estimate d,,, and according to the above, this acts proxy for Kaurr- This is useful the regret relates to K But show this, we need to construct surrogate environments inside each partition, and show that learning those is almost equivalent to the original problem. Let Ç be discrete random variable taking values in {1.-. (E)r(E)) that indicates the partition & lies in, such that Ç <= k and only if & E Oμ-
Lemma 2.
For any E valuee partition and any l E [L], there are random environments & E θ with their laws only depending on Ç, Dr, such that
E2 [Vf. (of) VI,ne, (s1)
[. (01) Vei V. (o1) se.
Er
1
(11)

---

The expectation in both equations is over & and ris t with both sampled independently Pr(c), and the K different values of Eg. The second expectation over (Éz E) is over pairs that are in the same partition, i.e., & & are independent only after conditioning on Ç.
We note that the proof in [18, App. B.1] contains the use of a lemma that does not apply to construct the law of the environment Ez. More details is provided Appendix C, where we find & by minimizing an expected value of mfs-
Bayesian regret bounds for Thompson Sampling
5.1 General Bayesian regret bound
We start by introducing the notion of value diameter.
Definition 9. Given the environment its value diameter is defined as
max Ag max (sup h,,zg (s) inf V hing (s)) i5h$H.EES (1% (1 (8, (r a)),
1ShSH
where Th (s, a) (and ria a)) is the supremum (and infimum) of the set of rewards that are attainable under the distribution (8, a) with non-zero probability. As special case, if rewards are deterministic, then we have ri. ( a) ri a) for all s, a. The (average) value diameter over é is denoted by A : [x))
As the value function between 0 and H, we have dg < +H+1 implying À H + 1. Note that value diameter is closely related to the notion of diameter commonly defined in finite RL problems. Strictly speaking, for a time- homogeooogsssuus RL, straightforward to see that the value diameter is bounded from above by one plus the diameter [33].
We now discuss the assumptions surrounding our results. The main technical assumption of this paper is the existence of consistent estimators, which as we will see in Appendix K, is closely related to the notion of posterior consistency:
Assumption There exists a strongly consistent estimator of the true environment given the history.
Roughly speaking, we assume that with unlimited observations under TS, it is possible to find the true environment. For this assumption to fail, we need to have two environments that produce the same distribution over histories under TS and are therefore indistinguishable from the point of view of TS. The precise description of this assumption detailed in Appendix K.
Another necessary technical assumption is that almost all optimal policies visit almost all state action pairs in their respective environment.
Assumption 2. For almost every environment & E ④ and almost every (s,a) E and every h E [H, we have
dh (8,a) $ O.
Recall that, for any environment & E θ the policy मद is the optimal policy of within the policy class II. Therefore, one example of how the above assumption holds is when II is the set of e-greedy algorithms and transition functions of environments assign non-zero probability to every state. Under these assumptions, discuss our main result and its corollaries.
Theorem 3. Given a Bayesian RL problem, for all > we have
BR,(FIS) < 22/Togg( (Xvoo(KKarr)()) su)r(e)) + Le + To
(12)
where To does not depend on T. This can be further upper bounded by BRy((TT)) S ((Av/d,TT)
(13)
for large enough T. Given a homogeneous I dimension dhom di Vh, this simplifies to
BBIS(TT)) & Ō(\v Hdhoom T)
(14)
Remark 4. For all regret bounds, we will replace À < H + to compare our result. For the case of homogeneous dimensions, we obtain 0(H3/2 / /hom 7). Crucially, our main result shows new conceptual understanding of the information ratio by bounding by two terms of different nature: H and X, where the latter can be bounded by either the largest diameter of the environments H.
7

---

Despite not impacting the asymptotics, the impact of Tu can be large depending on the structure of the RL problem, and could be dominant even for large T's in practice.
Remark 5.
Remark 6. Considering time as a part of the state observation, one could apply this regret analysis to particular timehhomogeneuu settings. However, this mapping of time-inhomogeneous RLss to homogeneous ones is not surjective, hence the result above does not readily extend to time- homogeneous settings.
While [16] were the first to consider nonlinear Bayesian RL model, their bound is limited to the Gaussian process (with linear kemel) setting, while ours in the nonlinear time inhomogeneous setting makes no assumptions on the prior and the first such bound. Our novel analysis allow us to upper bound the information ratio by Av H instead of, for example 3 /S3/ ([18)) in the tabular case, improving the regret bound by square root relevant to the dimension d of the problem.
The detailed proof is given in Appendix D. Following [18), the regret (4) rewritten using Lemma to reduce the problem into its surrogate, and we use the well-known information ratio trick by multiplying and dividing by the mutual information. We follow that with Cauchy-Schward summarized below
($1) - 1 (81) V 1,ng
-ve
L
Ee
VI
BRL (TT)
SE
+ LE
(15)
V (82; He,
Ee (sf) v
27 1 (of)))
Ee
E
1,ag
Σ I (Et;
+ Le (16)
(B;; He,H)
Note the cost each episode (Lemma in the first inequality, yielding the overall error Le. Then, can bound the mutual information appearing in the regret term by E - Ha,
(ET: Da) S (C < H() S log(Ksurr(E), where we used the mutual information chain rule, followed by data processing inequality to substitute E - C, and finally used the trivial bound by the entropy. But the main novelty of our approach lies in control of the first term
Ee V 1.mg
(of) - V (of)
2
Te(mfs)
(17)
(E;; He,H)
called the information ratio. In our analysis, we have the following bound on its expectation.
Ec -s
B(l'e(Tfs)) Eg] S
Σ
uSxA E
Ee
ae (s,
where the average is taken over all histories De that are generated from running TS on the true environment Eg. and we have introduced the smaller term dg instead of H in [18]. While [18] essentially bound the above only the tabular setting with SAH'S we manage to generally bound the above with a more precise bound using Doob's 's consistency theorem. Assumption allows to use Doob's consistency theorem to conclude that for almost every environment Eg. almost every infinite sequence of histories (De) sampled from Eo, and every integrable function f. the posterior mean [f[]] = (E) Drl] converges to f(E)). In particular, we conclude that [E[T (T((((T(s)) Eo] tends to X H in the limit, allowing us to claim that for large enough E, the expected information ratio [f('((T())] is uniformly bounded by ] H = 2X²H H. As there are L many such ratios, the two bounds together yield 2 2
(Kaurr())) + Le. This bound is true for large enough E, giving the additional additive term To in the theorem. Since this term is additive, applying Lemma I to bound log( Kuur (=)), we have successfully shown the asymptotic behavior of the regret, independent of the prior, of order Ö(H T.
5.2 Applications
In each application below, the challenge is to bound di using the specifics of the model, and except for the case of tabular Bayesian RI,, such analysis has not been carried out rigorously. We formalize the corollaries and show they are state-of-the-e compared to the literature.
8

---

Tabular RL. The result below follows from Theorem 3; the main contribution comes from our new information ratio bound, followed by the estimate (((()sAH)) of (E) ((18)..
Corollary 4. Given a tabular Bayesian RL problem, for large enough T.
(RT( I HSAT)
(18)
where the polylogarithmic terms are explicitly in terms of H, S,
We observe that our result matches [31] when their result in the time homogeneous setting (Defini- tion 2) is extended to time inhomogeneous. However, in that paper, the authors assume a Dirichlet based prior which we not.
Linear RL. A previous state-of-the-arr (d was claimed by [18] to hold for linear Bayesian RLs with deterministic reward. We note:
As in the previous cases, their proof in bounding their information ratio includes a factor of dy, which ours avoids.
We show that the proof bounding (E) in [18, App. B.4] is incorrect, starting with wrong application of Cauchy- Schwarz and wrong mutual information in their definition of information ratio. We provide counterexamples for the estimates found therein to substantiate our claim (see Appendix G.1).
To state our own corollary in this case, we need to define a few notions. Let d/, df + +4, be the sum of the dimiensso of the feature map space {1h, P. Jeee, - R.E ( where the l distance between feature maps is defined as 4 (wi, vx.") J. 1 - vi Il Our corollary also provides concrete bound in the case of mixture linear Bayesian RL where the feature maps are themselves sum of finitely many fixed feature maps. This means for all & E O, we have
P.E V/
P.E v K
R.
Σ
R.E 1 RR hi
(19)
where [ (s)) Σ, fa 1 E, h4is & C₂ for some constant C. > O. Let M = M +M n En m Σ m
1::: { { (s)] are finitely many fixed feature maps and Aε, h R.E
h.
Corollary 5. For a linear Bayesian RL, large enough T,
BRL( S ō af
(20)
Given a linear Bayesian RL with finitely many states and total feature space dimension d, d.. - d.. we have di S 22d H.S yielding for large enough T.
BRL( S
(2.1)
Given mixture linear Bayesian RL, for large enough T,
BA, (TTS) S Ō(AVMT)
(22)
The proof is given Appendix G. The fact that di, appears instead of d, in the general bound is not counter-intuitive, ( (s))eee.teim) Ru (s))ee to play role in the regret, especially as this space can be very complex, and model very different environments that can not be grouped in the same a value partition.
should expect the complexity of the feature map space
Therefore, opposite to the claim made by [18], this complexity can not be captured by simply d, except maybe in degenerate cases, such as when S is finite, which our second statement. More generally, each feature map wh P... bounded norm 0, is done in Eq. (22) (the finite state case corresponds to mf. df S, m, =R()).
(s), the R.E(s) (s) can be characterized with a vector of uniformly R.E E Rm""" then we can bound the regret in terms of m mi ss as
P.E RRT!," a

---

Finite mixtures RL. To state our finite mixtures model result, we need to set the following notations. Let dy = di + + = -xx diihk + +E Li correspond to the total dimmenssoo of the space of mixtures coefficient maps { P. (s, (s,a)}eee, {a R.E (s, fese with ( - distance defined as 11 (af, af) su | (s.a) a (s,a)]l1. Define also the restricted finite mixtures model P.E nE are vectors in Rm Rm independent of (s, a) and let M = M + M En mf. + En m..
where an aa
Corollary 6. Given a finite mixtures Bayesian RI. problem, for large enough? T,
(RT(( S Õ d..T)
(23)
Assuming the restricted finite mixtures model, for large enough T,
BRr S (AvMT)
(24)
which, given uniform dimension m = mf yields D(vVHm'))
We prove the above in Appendix H, deriving it from our generic bound, after relating the di-dimensoon di of the environment space to that of the mixtures coefficients. To the best of our knowledge, this is the first bound for finite mixtures Bayesian RL problems. We note that in a previous work ([6]), restricted version of finite mixtures, like in Eq. (24), was considered in the frequentist setting.
We finish this section by proposing the following conjecture, in line with [31, Conj. 1].
Conjecture 7. For the Bayesian RI., the following is true and optimal for all T:
BRL(TTI) So
inf (af(V/loo sourr Lε)
(25)
<=3
where the constant factor is independent of the prior. This means there exists Bayesian RL problem such that BR,, (TTs) = [2( HdduurT)), All polylogarithmic terms are in terms of H, d T.
Note that the above coincides with the lower bound for the (model-based) time inhomogeneous frequentist setting; see e.g., [21] for the proven lower bound for the tabular case. This is also VH higher (this factor being baked in dsarr) than that of the time homogeneous frequentist setting, which expected, according to [21, App. D]. Note that in this conjecture, the À in our bound is replaced by VH, and the conjecture is not for T large enough, but for all T. Supporting this conjecture requires experiments where TS can be exactly implemented assuming access to an oracle which provides the optimal policy for query environment. Simulations have been performed for the similar [31, Conj. 1] in the time homogeneous case. Our conjecture is similar but with the additional expected factor of v H due to time inhomogeneity, thus their simulation also supports the above.
Conclusions
In this paper, we have addressed the Bayesian Reinforcement Learning (RL) problem in the context of time inhomogeneous transition and reward functions. By considering both Bayesian transition and Bayesian rewards without prior assumptions, we have extended the scope of previous works, making our formulation more comprehensive. To simplify the learning problem, we have introduced surrogate environments, which discretize the environment space. We have established a connection between the size of this new environment space and the I ddddmennsoons of the transition and reward functions space, providing insights into the 4 1-dimension of the environment space denoted by di,- We have employed posterior consistency tools analyze the information ratio, which captures the trade-off between exploration and exploitation. We conjecture that (at least a weakened version of) our posterior consistency assumption should hold general, which left for future work. Our analysis has resulted in refined approach to estimate the Bayesian regret in Thompson Sampling (TS), yielding regret bound of Ö(> d; T) for large enough time steps T. The result is specialized to linear, tabular, and finite mixtures MDPs
While the paper provides asymptotic generic regret bound for TS in a generalized setup which improve the state of the art results, finding lower bounds, esp. one dependent on X, are left open. In addition, the issue of prior misspecificity is not discussed and left for future studies.
Limitations:
10

---

References
[1]
Amirhesam Abedsoltan, Mikhail Belkin, and Parthe Pandit. Toward large kernel models. arXiv preprint arXiv:2302.026605 2023.
[2] Alekh Agarwal, Yujia Jin, and Tong Zhang. VOQL: Towards optimal regret in model-free rl
with nonlinear function upproximation. arXiv preprint crXivv2212.06069, 2022.
[3] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
[4] Dilip Arumugam and Benjamin Van Roy. Deciding what to model: Salieeequivalent sampling for reinforcement learning. 35:9024- 009022--944,, 2022.
[5] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008
[6] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. International Conference on Machine Learning, pages 463 474. PMLR, 2020.
[7] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272.
PMLR, 2017.
[8] Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
[9] Sébastien Bubeck and Mark Sellke. First-order bayesian regret analysis of thompson sampling. In Algorithmic Learning Theory, pages 196-233. PMLR, 2020.
[10] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning. pages 1283-1294, PMLR, 2020.
[11] Souradip Chakraborty, Amrit Bedi, Alec Koppel, Pratap Tokekar, Furong Huang, and Dinesh Manocha. Posterior coreset construction with kernelized stein discrepancy for model based reinforcement learning. In NeurlPS 2022 Workshop
Methods, 2022.
[12] Sayak Ray Chowdhury and Aditya Gopalan, Online learning in kernelized markov decision pro- cesses. In Proceedings of the Twenly-Second International Conference on Artificial Intelligence and Statistics, pages 3197-3205. PMLR, 2019.
[13] Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34: 14:12040-12051 2021.
[14] Shi Dong and Benjamin Van Roy. An information-theoretie analysis for thompson sampling with many actions. Advances in Neural Information Processing Systems, 31, 2018
[15] Yaqi Duan, Mengdi Wang, and Martin J Wainwright. Optimal policy evaluation using kerne-- based temporal difference methods. arXiv preprint Stt::2/09.12000) 2021.
[16] Ying Fan and Yifei Ming. Model-based reinforcement learning for continuous control with posterior sampling. In International Conference Machine Learning, pages PMLR, 2021.
[17] Subhashis Ghosal and Aad Van der Vaart. Fundamentals of nonparametric Bayesian inference, volume 44. Cambridge University Press, 2017.
[18] Botao Hao and Tor Lattimore. Regret bounds for information-directed reinforcement learning. arXiv preprint arXiv:2206.04664) 2022.
[19] Botao Hao, Tor Lattimore, and Wei Deng. Information directed sampling for sparse linear bandits. Advances in Neural Information Processing Systems, 1AA:16338-167555 2021.
11

---

PMLR, 2022. [20] Botao Hao, Tor Lattimore, and Chao Qin. Contextual information commmatioo-diretedd sampling. In International Conference on Machine Learning. pages
[21] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[22] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learming Theory, pages 2137- 2143. PMLR, 2020.
[23] Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asymptotically optimal information-directed sampling. In Conference on Learning Theory, pages 2777-2821. PMLR, 2021.
[24] Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pages 1965-2992 PMLR, 2021.
[25] Tor Lattimore and Csaba Szepesvári. An information-theoreti approach to minimax regret in partial monitoring. In Conference on Learning Theory, pages 21 2111-2139, PMLR, 2019.
[26] Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[27] Xiuyuan Lu. Information-directe sampling for reinforcement learning. Stanford University, 2020.
[28] Xiuyuan Lu and Benjamin Van Roy. iitommation-thorreee confidence bounds for reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
[29] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
[30] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
[31] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference machine learning, pages 2701-2710.
PMLR, 2017.
[32] Ian Osband, Benjamin Van Roy. Daniel Russo, Zheng Wen, et al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20(1 2019.
[33] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[34] Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019.
[35] Daniel Russo and Benjamin Van Roy. Learning optimize via information-directed sampling. Advances in Neural Information Processing Systems, 27, 2014.
[36] Daniel Russo and Benjamin Van Roy. An information-thhoorticc analysis of thompson sampling. The Journal of Machine Learning Research, ((11):2442-2771,, 2016.
[37] Remo Sasso, Michelangelo Conserva, and Paulo Rauber. Posterior sampling for deep reinforce- ment learning, arXiv preprint arXivv2305.0044 23477004777 2023.
[38] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[39] Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, éric Moulines, Remi Munos, Alexey Naumov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees. Advances in Neural Information Processing Systems, 35:10737-10711,, 2022.
12

---

[40] Aristide Tossou, Debabrota Basu, and Christos Dimitrakakis. Near- Mear-optimal optimistic rein- forcement learning using empirical bernstein inequalities. arXiv preprint arXiv:1905.12422 2019.
[41] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning. pages 6995-7004. PMLR, 2019.
[42] Andrea Zanette, David Brandfoobrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020.
[43] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learn- ingvia reference-ad decomposition. Advances in Neural Information Processing Systems, 33:15198 15207, 2020.
[44] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021.
13


Reviews:
[{"review_id": "UdmSdD83r4", "reviewer": "Reviewer_bSE3", "summary": "This paper considers the problem setting of Bayesian reinforcement learning, in which both the transition function and the reward function are sampled from a known prior distribution. The authors study Thompson sampling in this setting and prove a Bayesian regret bound of order O(\\lambda \\sqrt{ d T}) where \\lambda is the average value diameter induced by the prior, d is the Kolmogorov dimension (with respect to l1 distance) of the environment, and T is the number of episodes the learner interacts with the environment.\n\nThe authors instantiate their general result to two previously studied settings. \n\n- In the tabular setting, the authors show that their main result implies a regret bound that matches the previous state of the art by Osband and Van Roy (2017), but generalized to hold over any prior distribution rather than specific to the product of Dirichlet distribution prior considered by Osband and Van Roy.\n\n- In the linear MDP setting, the authors give a regret bound of $O(\\lambda \\sqrt{d^f T})$, where $d^f$ is the Kolmogorov l1 dimension of the feature space. The authors also present a counterexample showing that the previously claimed state of the art due to Hao and Lattimore (2022) was in fact incorrect.\n\n\nThe paper also provides corollaries for specialized finite mixtures settings.\n", "questions": "On line 138, it is claimed that the law of Thompson sampling aligns with the true posterior distribution. Is this true with no other assumptions? For example, if two environments induce the same optimal policy, then it seems like this would not be true.", "limitations": "The paper does point out that they do not have lower bounds to substantiate the tightness of their upper bounds. Another limitation of the paper, not mentioned by the authors, is that the analysis is limited to the setting where the prior is specified with perfect accuracy.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's main contribution is a general treatment of Thompson sampling in MDPs. Specifically, the paper claims to provide the most general results to date on the Bayesian regret of Thompson sampling in RL. These results appear to generalize the results of Osband and Van Roy (2017) in the tabular case, and, when their counterexample to Hao and Lattimore (2022) is taken into account, provides the tightest upper bounds in the linear MDP case. The paper clearly signposts these contributions and provides proofs for their claims.", "weaknesses": "Some of the theorem statements/assumptions could be more explicit. For example, the strong consistency assumption (Assumption 1) is not rigorously defined until Appendix J. Also, in my reading of the proof of Theorem 4, it appears that there is another assumption needed in the statement (Assumption 2 from Appendix D). I think it is also worth pointing out that T_0 in Theorem 4 is doing a lot of heavy lifting, as it seems like it could actually be a very large constant, depending on the prior and the structure of the RL problem. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their thorough and careful summary of our paper and our results. We greatly appreciate the time and the comments made to improve the manuscript. We invite the reviewer to read the Author Rebuttal beforehand.\n\n**Weaknesses**:\n\n$\\bullet$ Thank you for raising this issue. We will give more context and rigor to Assumption 1 within the main text, and we will bring forth the second assumption into the main text as well.\n\n$\\bullet$ We will emphasize the limitation with respect to $T_0$, and indeed, while it may not change the asymptotics of the bound, its effect can be dominant for even large $T$s in practice.\n\n\n**Questions**:\n\nThank you very much for your question. This raises a subtle mathematical question which could be addressed without any additional assumptions. Our definition of TS is exactly the one by [12], which itself follows the seminal work on IDS [29] (Van Roy \\& Russo, 2014). We will include the following reply in our revised version and acknowledge the reviewer's contribution.\n\nThe question is: If two or even a nonzero-measure set of environments give the same optimal policy, then how could one have\n $\\mathbb{P}(\\mathcal{E}|\\mathcal{D}\\_\\ell)=\\mathbb{P}(\\pi^\\ell\\_{\\text{TS}}=\\pi^*\\_\\ell|\\mathcal{D}\\_\\ell),\\forall\\mathcal{E}$, while also having the latter as a probability measure on the set of optimal policies $\\Pi^*$, i.e. $\\int\\_{\\Pi^*} \\mathbb{P}( \\pi^*|\\mathcal{D}\\_\\ell) \\text{d} \\rho\\_{\\Pi^*}= 1$? \n\nThe answer is to define the measure $\\rho\\_{\\Pi^*}$ on $\\Pi^*$ to have appropriate measure on optimal policies $\\pi^*$, based on the set environments of which $\\pi^*$ is an optimal policy. Mathematically, this means that the map $star : \\Theta \\to \\Pi^*$, where $star(\\mathcal{E}) = \\pi^*\\_{\\mathcal{E}}$, must be used to define $\\rho\\_{\\Pi^*}$: \n\n$ \\rho\\_{\\Pi^*}(\\mathcal{O}) := \\rho(star^{-1}(\\mathcal{O})), \\ \\forall \\mathcal{O} \\subset \\Pi^* $\n\ni.e., $\\rho\\_{\\Pi^*}$ is defined as the push-forward of the prior measure $\\rho$ on the set of environments under the map $star$. This ensures that even when a nonzero measure set of environments have the same optimal policy, it is possible to postulate the law of TS to be $\\mathbb{P}( \\mathcal{E}|\\mathcal{D}\\_\\ell) = \\mathbb{P}( \\pi^\\ell\\_{\\text{TS}} = \\pi^*\\_\\ell |\\mathcal{D}\\_\\ell), \\forall \\mathcal{E}$.\n\n**Limitations**:\n\nWe thank the reviewer for their observation. Studying cases with prior misspecificity will be included as part of our limitations and future studies in our revised version."}, {"review_id": "Now9UjJOmV", "reviewer": "Reviewer_pUAk", "summary": "The authors propose the novel Bayesian regret analysis for posterior sampling for reinforcement learning algorithm. The proposed regret bounds are applicable in a large variety of different RL settings, such as tabular, linear and finite mixture MDPs.", "questions": "- Is there any results in literature where this type of dimension were called “Kolmogorov”? Seems that this definition is a just usual covering dimension (at least in the presented setup of $\\ell_1$ distance).\n- Is there examples where $\\lambda$ is much smaller than $H$?\n- What is the limitation to show this analysis for a more general class of MDPs such as MDPs with a finite Eluder dimension?\n- Where is topological structure of $S$ and $A$ were used during the proofs? What is the topological structure of them?\n- The missed references of frequentist regret bounds for TS-based exploration in tabular and linear MDPs:\n    - Zanette, Andrea, et al. \"Frequentist regret bounds for randomized least-squares value iteration.\" *International Conference on Artificial Intelligence and Statistics*. PMLR, 2020.\n    - Agrawal, Shipra, and Randy Jia. \"Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.\" *Advances in Neural Information Processing Systems* 30 (2017).\n    - Tiapkin, Daniil, et al. \"Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees.\" *Advances in Neural Information Processing Systems* 35 (2022): 10737-10751.\n    - Agrawal, Priyank, Jinglin Chen, and Nan Jiang. \"Improved worst-case regret bounds for randomized least-squares value iteration.\" *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 35. No. 8. 2021.\n- Line 83: In [32] they consider not episodic setup. The state-of-the-art result in the episodic setup were presented in [4].", "limitations": "The paper presented the theoretical research on Bayesian regret for posterior-sampling algorithms for reinforcement learning, thus it does not require discussion of ethical limitations.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The novel analysis for posterior sampling algorithm in the setting of Bayesian regret;\n- The presented result holds not only in the setting of tabular MDPs but also in linear and finite mixture MDPs.", "weaknesses": "- The weak notion of Bayesian regret is the main weakness of the presented result. Currently, there exists near-optimal results in posterior-sampling based algorithms in the frequentist setting (see section Questions for precise references).\n- The computational side of the presented algorithm was not discusses.\n- The upper bound in linear setup seems to be a contradiction with established lower bound in the setup of linear contextual bandits (see reference below for example). This effect requires additional explanations why is it possible in the presented setting.\n- Lattimore, Tor, and Csaba Szepesvári. *Bandit algorithms*. Cambridge University Press, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments improving the paper, and invite them to read the author rebuttal beforehand. Below are our replies:\n\n**Strengths**:\n\nThank you for the strength highlights. We also like to point out that the mentioned results are corollaries of our main contribution on general nonlinear RLs stated in Theorem 4.\n\n**Weaknesses**:\n\n1. This suggests that the PSRL problem in the frequentist setting is (nearly-)solved. However, references considered, there exists results only for tabular Dirichlet-based RLs, a small subset of general RLs. Our work expands the scope of knowledge on the Bayesian bounds for PSRL further than what exists in the frequentist case. Regarding the references: Thank you, and we shall include them in the intro for more context. Two of those are for model-free RL (ours is model-based PS), and the other two's results are very limited in scope (tabular RL Dirichlet-based priors). To our knowledge, a frequentist bound for PS is still an open problem for general RLs and those tabular cases solved optimally are for a *variant* of PSRL (Optimistic PSRL). Our bound is an appropriate first step towards the much more general principled study for Bayesian RLs.\n\n2. A discussion on this will appear in our revision. For general RL settings, we refer to the ICML23 [arXiv:2305.00477] where they show experiments regarding TS outperforming other methods in Deep RL. We will also point out PSRL papers with experiments (some cited in Related Works) on TS and its variants [29,20,17,13,14] and discussions on computational efficiency of PSRL.\n\n3. Despite sharing \"linear\" in name, said bandit problem is not directly related to linear RLs. Though it could be cast into an RL problem, it will not be an episodic/Bayesian/inhomogeneous/and finally not a linear RL either, unless made to be so:(1) No \"episode\" in the definition of linear contextual bandits. (2) The inhomogeneity condition should be added too. (3) [Bandit Algorithms, 2020] mentions the frequentist case only. (4) Contexts $X_t$ are like states in an environment. According to the bandit's definition, these are pre-selected, regardless of the actions, implying an environment where transitions $P(s'|s,a)$ are independent of $a$. (5) A linear RL requires these transitions  to be linear-- expressible as $\\langle \\phi(s), \\psi(s')\\rangle $; there is no such parallel assumption in the bandit problem. So one needs to consider an \"episodic inhomogeneous Bayesian linear contextual bandits with linear contextual transition functions\"! It is unclear what the lower bound for the regret would be after imposing this many assumptions.\n\n**Questions**:\n\n1. The term \"Kolmogorov\", as some limsup of covering *numbers*, has appeared before in e.g. [arXiv:1406.1853]. Regarding terminology usage: Our $l_1-$dimension is a type of upper box dimension, also referred to as \"Kolmogorov\" dimension [wikipedia, Minkowski-Bouligand dimension]. While most notions of dimensions match on well-behaved metric spaces, their definitions/scopes are not identical. In particular, *covering dimension* [wikipedia, \"Lebesgue covering dimension\"'] is a topological notion, while the upper box requires a metric. Further, we have (for metric spaces):\\\nupper-box dim $\\ge$ lower-box dim $\\ge$ Hausdorff dim $\\ge$ large inductive dim = covering dim;\\\nThe first two are in the Minkowski-Bouligand wiki. The last two are in [wikipedia, Inductive dimension]. Every single one of these inequalities can be strict, e.g. the metric space of rational numbers in $[0,1]$ with $l_1$ metric, has box dimension one, and Hausdorff dimension zero, so covering dimension is also zero [wikipedia, Hausdorff dimension]. All in all, this motivates the use of the exact and appropriate dimension terminology.\n\n2. Thank you for the question. This discussion will be in our final version. Assume every state is reachable from another in at most $D$ steps (defined more precisely as \"MDP diameter\"). Using $0\\le r(s,a)\\le 1$, it can be shown: $\\lambda \\le D$. Therefore, if environments have small diameters, $\\lambda$ can be much smaller than $H$. In addition, we note the conceptual contribution: the information ratio is bounded by (the $l_1-$dimension of $\\Theta$) times (the diameter of the value function). The latter is always $\\le H$, but its nature is different from $H$.\n\n3. Thank you for the question. We will summarize what follows in our conclusion/future works.With regards to applicability to general MDPs, so long as our assumptions regarding posterior consistency hold, the analysis applies. We conjecture that (at least a weakened version of) our posterior consistency assumption should hold in general, and we leave that for future work. As for Eluder dimension (in)finiteness, especially used in frequentist bounds, it is of no relevance here. As Theorem 4 states, there is no assumption except for the posterior consistency. One could ask the relation between Eluder and $l_1$ dimensions, and which is easier to derive. We leave this for future work.\n\n4. There is no assumption other than those in the preliminaries: topological spaces with probability measures. The Bayesian bound does not depend directly on some dimension of these spaces. However, given that transition functions are defined on $\\mathcal{S},\\mathcal{A}$, it is not surprising to see the $l_1-$dim being expressed in terms of $\\mathcal{S},\\mathcal{A}$, such as in the tabular case.\n\n5. We addressed this under \"Weaknesses 1.\".\n\n6. Thank you for the correction. Please note this is for tabular only. To our knowledge, there is no lower bound in the frequentist model-based for general RLs.\n"}, {"review_id": "rFu4RAkY66", "reviewer": "Reviewer_4ohk", "summary": "The paper presents uniform Bayesian regret bounds for Thompson Sampling by utilizing a uniform bound of information ratio and specific bounds of the Kolmogorov dimension in different settings. \n", "questions": "Why is time inhomogeneous specially highlighted in this work? If we consider time also as a part of the state observation, it would be homogeneous (i.e., share the same model across all timesteps). With that being considered, is it possible just to extend the time inhomogeneous bounds to this setting, and is the proposed bound also better than those?\n", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a uniform Bayesian regret bound for Thompson Sampling which yields results in a variety of settings, improving upon previous approaches in some scenarios.\n2. The authors incorporate a comprehensive discussion with previous works which helps to understand the contribution of the proposed bounds.\n", "weaknesses": "1. Potential overclaim: in the introduction, the authors state that they first define Bayesian RL with time inhomogeneous settings, which might be an overclaim since there are also previous works discussing this setting like [1].\n\n[1]Variational Bayesian Reinforcement Learning with Regret Bounds. Brendan O'Donoghue\n\n2. The presentation of the paper would benefit from a table that includes all the results discussed in the paper for a comprehensive comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments improving the paper, which we will include in our final revision. We also invite the reviewer to read the author rebuttal beforehand. Below are our replies:\n\n**Weaknesses**:\n\n1. Thank you for pointing this out. The phrase \"we first define\" was intended to mean that we are *starting* our presentation with this notion, similar to \"we first do X/we then do Y\", but we realize how the phrasing causes confusion, and so we change it accordingly in our revision. We have previously referred to [12] and other works for where this notion was previously introduced, but we thank the reviewer for providing the additional reference (to be also included in our revision).\n\n2. We would like to thank the reviewer for this suggestion. For the Bayesian RL, there are very few works, of which we can name [25] (for time-homogeneous Dirichlet-prior tabular) and [12] (for time-inhomogeneous Bayesian RL), and while the latter is general and makes comparable claims, part of our paper is essentially spent on correcting their claims and proofs. We will expand on the comparisons with these works using a table. We note that frequentist model-based bounds in the table would be misleading, and such bounds are also limited to tabular settings. \n\n**Questions**:\n\nWe thank the reviewer for their question and observation. Indeed, we see that if one applies the proposed mapping, we get a time homogeneous environment as a result. Hence, we could apply the regret bounds in that setting. The regret bound in this setting would be, to our knowledge, the first Bayesian regret bound for these general time-homogeneous RLs. However, we are not sure if this mapping is surjective on the set of time-homogeneous RL problems. We appreciate this remark. We will include it in our revised paper after our main theorem and mention the reviewer's contribution in the acknowledgments."}, {"review_id": "sOaHA37pB6", "reviewer": "Reviewer_z7jd", "summary": "The paper shows a refined analysis of Thompson Sampling in RL. The analysis leverages the notion of Kolmogorov dimension, and results in an improved rate of the regret. The authors further presented the bounds in terms of several specific settings, which match the state-of-the-art results.  ", "questions": "1. The authors mentioned the incorrectness of [12] in terms of surrogate loss. Can the authors make some discussion on it and how did they fix the issue? ", "limitations": "The paper has addressed it limitations. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The writing of the paper is clear and easy to follow. The paper studies an important problem in RL. The notion of Kolmogorov dimension as well as the corresponding analysis is novel. The paper also presents a complete discussion for specific settings, and makes sufficient comparisons with previous works, which shows the significance of its results. ", "weaknesses": "1. While the bound relies on a new notion $\\lambda$, the term can still be as big as $H$ in many cases. It hard to to quantify how much improvement is made by this notion, and therefore, in the discussion of specific RL settings, the corresponds bounds only match the state-of-the-art results, but don't improve them. \n\n2. The paper doesn't provide a lower bound in terms of the proposed notion, which weakens the significance of this notion. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, which we will include accordingly in our final revision as detailed below. We also invite the reviewer to read the author rebuttal beforehand. Below are our replies:\n\n**Weaknesses**:\n\n1. Thank you for the comment. Given other reviewer's remarks, we have realized that we need to discuss a bit more the potential conceptual and practical improvement brought about by $\\lambda$. A summary of this reply will appear in the revised version.\\\nThe value-diameter $\\lambda$ is bounded by another notion of environment-diameter, which is roughly speaking the longest path among the shortest paths between any two states. If states can be reached from one another quickly in environments, then $\\lambda$ can be far smaller than $H$ (as alluded to after Definition 10). Perhaps more importantly, the conceptual contribution is the realization that the information ratio is not bounded by the term $H$ and $d\\_{l\\_1}$, but the value-diameter $\\lambda$ and $d\\_{l\\_1}$. While it is true that $\\lambda$ can be always upper bounded by $H$, it is important to recognize the nature of what is bounding the information ratio, which is not $H$, but the value-diameter; this opens the door to further optimizations in specific cases, one of which we just mentioned. Regarding the discussion of specific RL settings and the significance of our results, we would like to note again that our results generalize to nonlinear settings, and further, we achieve the first correct and state-of-the-art regret bounds for the Bayesian linear and finite mixtures settings.\n\n2. Thank you for the comment. We understand your statement as asking for a regret lower bound based on the notion $\\lambda$. We thank you for reminding us, as we have mentioned this as a limitation of our work (after the section Conclusion). We will include this more explicitly as an open problem for future work in our revised version.\n\n**Questions**:\n\n1. Thank you for your question. We assume that you are referring to surrogate \"environments\"/\"regret\", as there is not a notion of surrogate \"loss\" in our paper (or in the related work [12]). We will include a summary of our reply below in our revised paper to provide an outline of this matter.\\\nWe recall that the goal is to construct surrogate environments that have a surrogate regret which approximates that of every environment in the same $\\varepsilon-$value partition. We claim that the construction of surrogate environments in our paper corrects the one in [12]; the formalized statement is our Lemma 2, with proof and details given in our Appendix B. The incorrect proof by [12] in [App. B.1, 12] contains the use of a technical inequality lemma that does not apply to the setting the authors claim (please refer to our Remark 6 in Appendix B, line 502).\\\nWhat we show is that the desired property of a surrogate environment is achieved when the value function of TS is smaller than the average value over the partition. This informs us to take the surrogate environment as the average of the environments in the partition, and prove the statement.\\\nIn addition to surrogate environments construction, we corrected a fundamental issue with the surrogate information ratio bound.  We have quoted and explained the authors' argument in App. J.2.1, and shown with equations in details, and explained the intuition, for why their argument fails. We elaborate on the intuition here as well.\\\nNote this ratio is used to bound the surrogate (and therefore, main) regret. In [12], the authors claim to bound this ratio by showing that the numerator (surrogate regret) is smaller than a particular surrogate mutual information: $\\mathbb{I}^{\\pi^*\\_{\\mathcal{E}}}\\_\\ell(\\widetilde{\\mathcal{E}}^*\\_\\ell;\\mathcal{H}\\_{\\ell,H})$. Recall that the denominator in the (surrogate) information ratio is supposed to represent the information gain by the algorithm on the true (or surrogate) environment. What we observe is that the surrogate mutual information ratio that one should bound is:\\\n\\\n$\n\\frac{\\left(\\mathbb{E}\\_\\ell\\left[V\\_{1,\\pi^*\\_{\\mathcal{E}}}^{\\widetilde{\\mathcal{E}}\\_\\ell^*}(s\\_1^\\ell)-V\\_{1,\\pi}^{ \\widetilde{\\mathcal{E}}\\_\\ell^*}(s\\_1^\\ell)\\right]\\right)^2}{\\mathbb{I}\\_\\ell^{\\pi}\\left(\\widetilde{\\mathcal{E}}\\_\\ell^*; \\mathcal{H}\\_{\\ell, H}\\right)},\n$\\\n\\\nwhere $\\pi$ is the algorithm (so we select $\\pi=\\pi\\_{\\text{TS}}$). Indeed, clearly the algorithm can not know about the true environment $\\mathcal{E}$, which makes it questionable to try to bound the surrogate regret\n$\\mathbb{E}\\_\\ell\\left[V\\_{1,\\pi^*\\_\\mathcal{E}}^{\\widetilde{\\mathcal{E}}\\_\\ell^*}(s\\_1^\\ell)-V\\_{1,\\pi}^{\\widetilde{\\mathcal{E}}\\_\\ell^*}(s\\_1^\\ell)\\right]$ by a mutual information such as $\\mathbb I\\_\\ell^{\\pi^*\\_{\\mathcal{E}}}\\left(\\widetilde{\\mathcal{E}}\\_\\ell^*; \\mathcal{E}\\_{\\ell, H}\\right):= \\mathbb I\\_\\ell\\left(\\widetilde{\\mathcal{E}}\\_\\ell^*; \\mathcal{H}\\_{\\ell, H}|\\pi^*\\_\\mathcal{E} \\right)$, where there is **assumed** knowledge of the true environment in the conditional $\\pi^*\\_\\mathcal{E}$, as opposed to conditioning on the algorithm itself like in the ratio above. Therefore, the mutual information used in [12] is not the right one."}, {"review_id": "lZItGPFFJX", "reviewer": "Reviewer_DrLb", "summary": "The paper presents a refined analysis of TS in Bayesian regret reinforcement learning. Regret bounds are derived for tabular, linear, and finite mixture MDPs. The paper uses an information theoretical approach: the information ratio, representing the exploration-exploitation trade-off, is analyzed and bounded by the episode length. The paper uses discretization of the environment space defined by fixing a previous proof from the literature. The paper concludes by discussing related work and the optimality of the obtained regret bounds.", "questions": "Could you please provide more references that specifically highlight the theoretical analysis of TS in the context of RL and Bandit problems? Usually, bayesian regret is easier than frequentist to analyse. Do you know if your approach could be applicable to frequentist regret ?\n\nWhat is the relationship between the Kolmogorov dimension for $l_1$-distance, the \"value partition for surrogate learning,\" and the time-inhomogeneous Bayesian RL problem? \n\nHow does leveraging this relationship help in bounding the information ratio and achieving regret bounds in TS ? \n\nCan concrete estimates of the dimension be provided for linear, tabular, and finite mixtures applications? What is the significance of isolating the contributions of the information ratio and the cumulative mutual information terms? \n\nCan you clarify the specific experimental results or empirical evidence that support the conjecture regarding the optimality of the regret bound when substituting $H$ in place of the variable? \n\nAre there any specific experiments conducted with TS, assuming access to an oracle, that provide insights into the performance of the regret bound in practical scenarios?\n\nYou mention related work on bounding Bayesian regret for TS, including the use of confidence regions and algorithms such as UCBVI and OPPO. How does the proposed work in this paper compare to these approaches in terms of regret bounds and optimality? Are there any notable advantages or limitations of the proposed approach compared to the existing literature?\n", "limitations": "Can you provide a motivation for using TS-based policies rather than OFU ones ? If this is about empirical performances, then it makes sense to run some experimental comparisons.\n\nI am not sure to clearly understand what evidence or rationale is provided to support the claim that the regret in surrogate environments serves as a proxy for the main problem.\n\nI think you could elaborate more on the methodology used in this analysis. How does it contribute to a better understanding of the trade-off between exploration and exploitation? Are there any limitations or assumptions associated with this analysis?\n\nminor:\nLemma 11 : fix the X vs x notation\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides state-of-the-art Bayesian regret bounds for Thompson Sampling in reinforcement learning through a refined analysis of the surrogate environments and information ratio in many different settings, including tabular, linear, and finite mixtures. The obtained bound is general and independent of the dimension of transition/reward function space. Proof sketches are provided.", "weaknesses": "The proposed analysis and bounds may have limited applicability to real-world RL problems beyond the considered settings.\nThe paper does not provide experimental results or empirical validation of the derived bounds.\nSome assumptions and prior works are discussed without providing detailed explanations or comparisons.\nOverall, the paper makes significant contributions to the theoretical understanding of TS in RL by providing refined analysis and state-of-the-art Bayesian regret bounds in various settings. However, practical applicability and empirical validation of the derived bounds need further investigation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your questions and comments improving our paper. Please read the Author Rebuttal beforehand.\n\nW:\n\n1. See Q.6 and L.1 for experiments and empirical validations.\n\n2. See L.4 and replies to reviewers: W.2 of 4ohk and W.1 of bSE3.\n\nQ:\n\n1. (a) Here are more refs:  [1111.1797] for multi-armed bandit, [1611.06534] for linear bandit. For RL: [1306.0940, 1607.00215] for tabular Bayesian RL problem with variants of TS. Theory of TS in general Bayesian RL only includes [2206.04640] which is the closest to our work.\\\n(b) It is yet unclear if our approach could be applied to the frequentist setting, as some of the derivation need the average over the prior. We hope posterior consistency tools will play a role similar to concentration inequalities in spirit in frequentist analysis.\n\n2. The $l_1$-distance determines the $l_1-$dim of the environments space, and is a bound on the size of any discrete set that approximates this space up to $\\epsilon$ error. This surrogate set is used for surrogate learning (Lemma 1). Surrogate learning is meant to act as a proxy to the main learning problem for time-inhomogeneous Bayesian RL (Lemma 2). This proxy regret is then used to bound the main one, expressed by the $d_{l_1}$ estimation of the size of the surrogate set (Theorem 4). More precisely, the regret is isolated into an information ratio and cumulative mutual information terms, and the latter is bounded by the size of the surrogate space. This shows how this relationship helps in regret bounding.\n\n3. These estimates are in Corollaries 5-7, Tabular: $SAH$; Linear: $l_1-$dim of the feature maps space ; Finite mixtures: $l_1-$dim of the space of mixtures coefficients.\n\n4. This is a technique introduced in [29]. On the significance of this decomposition of regret: (1) The ratio quantifies the exploration/exploitation trade-off of the algorithm at each step. Using Pinsker's inequality relating expectation and mutual information, one can bound this ratio. (2) The cumulative mutual information terms can always be bounded by entropy measures or relevant dimensions of the environments space. Our work improves and/or finds correct estimates for both terms in different RL settings.\n\n5. The simulation supporting our conjecture is in [25, Fig 9]. There are 3 sets of data points in that figure, and the one in blue (PSRL) has the best asymptotic behavior of $\\tilde{O}(\\sqrt{HSAT})$. Note that we added $\\sqrt{H}$ to convert to time-inhomogeneous.\n\n6. Yes, such works include Optimistic PSRL [2209.14414], wherein PSRL with oracle access is the most performant. See also recent practical work in this area [2305.00477] stating: \"Our extensive experiments on the Atari benchmark show that PSDRL significantly outperforms previous state-of-the-art randomized value function approaches, its natural model-free counterparts, while being competitive with a state-of-the-art (model-based) reinforcement learning method in both sample efficiency and computational efficiency\".\n\n7. Our work has few reasonable assumptions, but does not assume a special RL setting like tabular. Previous UCB based works achieve competitive regret for frequentist model-free settings, and [1] has shown optimality with regret $\\tilde{O}(d\\sqrt{HT})$, where $d$ is the functional approximation dimension of the MDP. As frequentist model-free vs Bayesian model-based are quite different, one must be careful in comparing them. Frequentist optimal/lower regret bounds can be larger than Bayesian regret bounds; Our work achieves a regret $\\tilde{O}(H\\sqrt{d_{l_1}T})$, and conjectures the lower bound $\\tilde{O}(\\sqrt{Hd_{l_1}T})$, while not being in contradiction with the optimal bound $\\tilde{O}(d\\sqrt{HT})$ in frequentist model-free setting. In terms of limitations of TS: the main one is the oracle access to an optimal policy, which cannot always be satisfied efficiently. Nevertheless, clever engineering can make TS work even in large scale Deep RL, as cited above.\n\nL:\n\n1. We cite the paper \"why is PS better than optimism for RL?\" directly addressing this: \"Computational results...demonstrate that PSRL dramatically outperforms existing algorithms based on OFU\". In addition, more up-to-date works on PSRL [2209.14414, Fig. 1,3] compares this recent OFU based UCBVI/UCBVI-B wherein PSRL shows the lowest regret. These experiments provide enough support for the empirical performance of TS.\n\n2. We address this by explaining the intuition and evidence. Intuition: The discrete surrogate environments set $\\Theta^\\epsilon$ are built to approximate the original environments $\\Theta$ up to a chosen accuracy $\\epsilon$. The rationale behind building such a set is that any regret bound on this set is, up to some  error related to $\\epsilon$, a regret bound for $\\Theta$, hence the use of the phrase \"proxy for the main problem\". Evidence: The supporting evidence is mathematically laid out in Section 4 and 5, culminating in (Theorem 4), where it is shown that the regret of the main problem scales by the size of $\\Theta^\\epsilon$. This is established by replacing every environment of the main problem by their $\\epsilon$-close surrogate environment, and analyzing the regret in the surrogate space (Lemma 2). This proves the intuition behind the surrogate serving as a proxy to the main problem.\n\n3. This reply is complementary to Q.3. We demonstrate how this trade-off is better understood in terms of the $l_1-$dim of $\\Theta$, and a new notion called $\\lambda$, the value diameter. Using posterior consistency tools, we achieve sublinear dim scaling $d_{l_1}^{1/2}$ (vs linear in previous tabular works). We also make a conceptual contribution by showing that, unlike previous studies, the number of time-steps $H$ is not the right quantity to bound the information ratio. Instead, it is the value diameter.\n\n4. On limitations/assumptions, as noted in Section 5, the posterior consistency assumption is needed to show $d_{l_1}^{1/2}$ scaling for the information ratio bound."}]

Author rebuttal:
We thank very much all reviewers for their questions and comments, which we will include in our revision. Please note that we had to address each reviewer's response within the character limit. We kindly invite all reviewers to ask any further questions they have in the discussion period.

Please also note that in our replies, references are cited with either of these two formats:

(1) With the arXiv code, e.g. "[1406.1853]" is meant to reference arXiv:1406.1853, Or,

(2) With the associated number in the reference section of the paper, e.g. [29] refers to "Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. Advances in Neural Information Processing Systems, 27, 2014."


Meta-review: Studies the performance of Thompson sampling on general RL problems when the true prior over rewards and transitions is provided to the learner. The Bayesian regret is given in terms of a quantity called the Kolmogorov l1 dimension—a measure connected to covering numbers of the MDP. For specific paradigms of MDPs including tabular, linear, and mixture, the authors bound this quantity providing results that match prior art. While the general treatment is appreciated, different reviewers were disappointed to not find a lower bound in terms of this Kolmogorov dimension, calling into question the tightness of the results. Nevertheless, such a general treatment is appreciated for such a challenging set of problems and spurs new directions to be explored.
Decision: Accept (poster)