Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees
Authors: Daniil Tiapkin
Denis Belomestny
Daniele Calandriello
Eric Moulines
Remi Munos
Alexey Naumov
Mark Rowland
Michal Valko
Pierre MENARD
Venue: NeurIPS 2022 Accept (2022)

Abstract: We consider reinforcement learning in an environment modeled by an episodic, tabular, step-dependent Markov decision process of horizon $H$ with $S$ states, and $A$ actions.  The performance of an agent is measured by the regret after interacting with the environment for $T$ episodes. We propose an optimistic posterior sampling algorithm for reinforcement learning (OPSRL), a simple variant of posterior sampling that only needs a number of posterior samples logarithmic in $H$, $S$, $A$, and $T$ per state-action pair. For OPSRL we guarantee a high-probability regret bound of order at most $O(\sqrt{H^3SAT})$ ignoring $\text{poly}\log(HSAT)$ terms. The key novel technical ingredient is a new sharp anti-concentration inequality for linear forms of a Dirichlet random vector which may be of independent interest. Specifically, we extend the normal approximation-based lower bound for Beta distributions by Alfers and Dinges (1984) to Dirichlet distributions. Our bound matches the lower bound of order $\Omega(\sqrt{H^3SAT})$, thereby answering the open problems raised by Agrawal and Jia (2017) for the episodic setting. 

Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees
Daniil Tiapkin
Denis Belomestny
HSE University dtyapkinOhse.rv
Mhisburg-Essen University, HSE University denis. belomestay@uni-eee
Daniele Calandriello DeepMind dcalaandrielll@@eeemmiddd. com
Érie Moulines
École Polytechnique
eric. eric..oul.ieestpolyyeecemmt.
Remi Munos
Alexey Naumov
DeepMindd munos@deepmindd.cmm com
HSE University
anaumov@hse.rr
Mark Rowland
Michal Valko
Pierre Ménard ENS Lyon
Deep markrovllandddeepninnd com
DeepMind
valkoom@deepmind.ccomm com
pierre pierre. wwweeeemnnrddeee--yynn..mmm
Abstract
We consider reinforcement learning an environment modeled by an episodic, finite, stage-dependent Markov decision process of horizon H with S states, and A actions. The performance of an agent is measured by the regret after interacting with the environment for T episodes. We propose an optimistic posterior sam- pling algorithm for reinforcement learning (OPSRL), a simple variant of posterior sampling that only needs number of posterior samples logarithmic in H, S. A, and T per state-action pair. For OPSRL we guarantee a nigh-probability regret bound of order at most H3SAT) ignoring poly log (AT)) terms. The key novel technical ingredient is forms which may be of independent interest. Specifically, we extend the normal approximation-based lower bound for Beta distributions by Alfers and Dinges [1984] to Dirichlet distributions. Our bound matches the lower bound of order 2(v HAT),, thereby answering the open problems raised by Agrawal and Jia [2017b] for the episodic setting.
sharp anti-concentration inequality for linear
Introduction
In reinforcement learning an agent interacts with an environment, whose underlying mechanism is unknown, by sequentially taking actions, receiving rewards, and transitioning the next state [Sutton and Barto, 1998]. With the goal of maximizing the expected sum of the collected rewards, the agent must carefully balance between exploring order to gather more information about the environment and exploiting the current knowledge to collect the rewards. In this paper, we are interested in solving this palloration-exploiaaai
dilemma by injecting noise into the agent's decision-male makinn process.
We model the environment as an episodic, finite, unknown Markov decision process (MDP) of horizon H, with S states and A actions. In particular, consider the stage-dependent setting where the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

rewards and the transition probability distributions can vary within an episode. After T episodes, the performance of an agent measured through regret which the difference between the cumulative reward the agent could have obtained by acting optimally and what the agent really obtained.
Jin et al. [2018] and Domingues et al. [2020] provide a problem-independent lower bound of order ((VH for this setting; see also Azar et al. [2017] for lower bound when the transitions are stage-independent
One generic solution to the -xppoottonn-ellloatttinon dilemma is the principle of optimism in the face of uncertainty. A simple way to implement this principle consists in building upper confidence bound (UCB) on the optimal Q-value function through the addition of bonuses to the rewards. This is done by either model-basee algorithms [Azar et al., 2017, Dann et al., 2017, Zanette and Brunskill, 2019] or model-free algorithms [Jin et al., 2018, Zhang et al., 2020, Menard et al., 2021]; see also [Jaksch et al., 2010, Fruit et al., 2018, Talebi and Maillard, 2018] for the non-episodic setting. Notably, among others, both the upper confidence bound value iteration (UCBVI) of Azar et al. [2017] and the UCB-Advantage algorithm of Zhang et al. [2020] enjoys problem-independent regret bound' of order O( H that matches the aforementioned lower bound for T large enough and up to in H, S, A.
terms poly-logarithng
Another way is to implement the optimism by injecting noise. A typical example is the random least-square value iteration (RLSVI, Osband al., 2016b, Russo, 2019) algorithm which at each episode computes new Q-values by noisy value iteration from an estimated model and then acts greedily with respect to them. In particular, Gaussian noise is added to the reward before applying the Bellman operator to encourage exploration. Indeed, when the variance of the noise is carefully chosen, it allows to obtain optimístic Q-values with at least a fixed probability. Russo [2019] first proved a regret bound of order 55112/////AA for RLSVI. Later, Xiong et al. [2021] obtained an
optimal regret bound of order Õ( OAT for a modified version of RLSVI where the variance of the injected Gaussian noise is scaled by a term similar the Bernstein bonuses used in UCBVI. Note that the RLSVI was also successfully extended beyond the tabular case to settings with function approximation, e.g. see Ishfaq et al., 2021, Zanette et al., 2020.
Recently, Pacchiano et al. [2021] analyzed a version of RLSVI where the Gaussian noise is replaced by a bootstrap sample of the past rewards and added pseudo rewards in the same fashion as Kveton et al. [2019]. The algorithm proposed by Pacchiano et al. [2021]. comes with a regret bound of order O(H2SVAT)
By generalizing the Thompson sampling algorithm [Thompson, 1933] originally given for stochastic multi-armed bandit, Osband et al. [2013] propose a posterior sampling for reinforcement learning (PSRL). PSRL algorithm also relies on noise to drive exploration. The general idea behind it is to maintain a surrogate Bayesian model on the MDP, for instance, a Dirichlet posterior on the transition probability distribution if the rewards transition probability for each state-action pair) according to the posterior distribution of the Bayesian model. Then, the agent acts optimally in this sampled MDP. As the posterior is not well concentrated in the unexplored region of the MDP, the probability that the Q-value of the sampled MDP is optimistic in this region is high. Therefore, the agent will be incentivized to explore. Although the original Thompson sampling is well-studied in the frequentist setting [Agrawal and Goyal, 2012, Kaufmann et al., 2012, Agrawal and Goyal, 2013, Zhang. 2022] and the Bayesian setting ['Thompson, 1933, Russo and Roy, 2016, Russo and Van Roy, 2014], most of the analysis of PSRL only provide Bayesian regret bounds [Osband et al., 2013, 2016b, Ouyang et al., 2017, Osband and Van Roy, 2017]. i.e., when the true MDP is effectively sampled according to the prior of the surrogate Bayesian model. Despite this lack of guarantees, PSRL demonstrates competitive empirical performance in comparison to bonus- algorithms [Osband et al., 2013, Osband and Van Roy, 2017]. Additionally, the exploration mechanism used by PSRL (and RLSVI) was successfully extended outside the tabular setting and used in deep RL environments [Osband et al., 201 6a, 2018, 2019].
known. At each episode, new MDP is sampled (i.e.,
-adakri and Szepesvári, 2015, Osband et al.,
We translate all the bounds to the stage-dependent setting by multiplying the regret bounds in the stage- independent setting by VH, see Jin et al. [2018].
In the Ö(-) notation we ignore terms poly-log in S.S.A.AA A,T.

---

One exception to the above is the work of Agrawal and Jia [2017b] that studies PSRL from a frequettist perspective in the aefnite-horizon non-episodic average reward setting, In particular, they provide a regret bound of order" SVH2SVAAT for an optimistic version of PSRL that we call SOS-OPS-RL since it switches between two types of sampling of the transitions: (1) simple optimistic sampling, when the number of observed transitions at a given state-action pair is too small. In this case, the sampled transition is random mixture between the uniform distribution over the states and an empirical estimate of the true transition biased by some bonus-like terms; or if the number of observed transitions at given state-action pair is large enough (2) optimistic posterior sampling, where ((S) samples from an inflated Dirichlet posterior are used instead of one sample used in PSRL. Then, from these (S) sampled transition probabilities we select the most optimistic one i.c., the one leading to the largest optimal Q-value.
The key idea underpinning the analysis of SOS-OPS-RL, and PSRL-like algorithms in general, is to control the deviations of the Dirichlet posterior on the transition probability distributions. In particular, we need to show that the posterior spreads enough to ensure optimism. To this end, Agrawal and Jia [2017b] derive an unti-concentration bound for any fixed projection of Dirichlet random vector. The latter result in turn relies upon an equivalent representation of a Dirichlet vector in terms of independent Beta random variables and an anti-concentration bound for the corresponding Beta distribution. However, this anti-concentration inequality is not uniformly tight, in particular its polynomial dependence the number of states S is suboptimal.
Agrawal and Jia [2017b] conclude with two open problems. The first question is whether one can reduce the number of posterior samples required per state-action pair from (SS) to constant or logarithmic in S. The second asks if it is possible to obtain near-optimal regret bound and in particular to improve the dependence on S. In this paper, we answer both of them in the affirmative in the episodic setting. Indeed, we propose optimistic posterior sampling algorithm for reinforcement learning (OPSRL) that only requires (1)) samples from an inflated posterior while enjoying a near- optimal problem independent regret bound of order O SAT).. OPSRL is a simple optimistic variant of PSRL which, in particular, does not rely at all on "simple" (bonus-basec bbsed) optimistic sampling.
The essential ingredient for OPSRL's analysis is our novel anti-concentraatin bound for the projections of a Dirichlet random vector (Theorem 3.3). We base on tight Gaussian approximation for linear forms of a Dirichlet random vector. This latter approximation can be seen as a substantial generalization to Dirichlet distributions of the result obtained by Alfers and Dinges [1984] for the case of Beta distributions. We obtain this approximation through refined non-asymptotic analysis of the integral representation for the density of a linear form of Dirichlet random vector, which was first d by Tiapkin et al. [2022]. We believe that the new antinconcentaation incquality presented in this work could be of independent interest, c.g., to tighten or simplify analysis of non-nannae -aramarmettiic Thompson sampling like algorithms [Riou and Honda, 2020, Baudry et al., 2021a,b] for stochastic multi-armed bandits.
We propose the OPSRL algorithm for tabular, stage-dependent, episodic RL. It is a simple opti- mistic variant of the PSRL algorithm that only needs (11) posterior samples per state-action pair. For OPSRL, we provide regret bound of order ((H3AAAT) matching the problem independent lower bound up to poly-log terms. In particular we answer positively to two open questions by Agrawal and Jia [2017b] in the episodic setting.
We derive a new anti-concentration inequality for a linear form of a Dirichlet random vector (Theorem 3.3) which is essential for the analysis of OPSRL. This result is generalization to the Dirichlet case of the one provided by Alfers and Dinges [1984] for Beta distributions.
*As acknowledged by the authors, there was a mistake in the initial submission of their work where the previously announced bound was claimed to be v/ better, see Agrawal and Jia [2017a], Qian et al. [2020] *We translate all the bounds from the infinite-horizon, non-episodic average reward setting to our setting by identifying the diameter with the horizon H and multiplying the bound by / H because of our stage-dependent transitions assumption.
"Note that the anti concenttrntiinn inequality proved by Tiapkin et al. [2022] based on the same integral representation insufficient for our needs, Remark 3.4 for a discussion.
3

---

2 Setting
We consider a finite episodic MDP (S,A, (ph Feemt, frw (rwheer)) where S is the set of states, A is the set of actions, is the number of steps in one episode, Ps (s ss, a) the probability transition from state state s' by taking the action a step hi and rı (8, a) [o, 1] is the bounded deterministic" reward received after taking the action a in state & at step h. Note that we consider the general case of rewards and transition functions that are possibly non-stationary, i.e., that allowed to depend on the decision step h in the episode. We denote by S and A the number of states and actions, respectively.
Policy & value functions A deterministic policy is collection of functions Tr : S - A for all [H). where every Tr maps each state to single action. The value functions of æ, denoted by Vă, as well as the optimal value functions, denoted by Vi are given by the Bellman and the optimal Bellman equations,
(ī( = (2, + pa V (s.
Vi (+) = n (*) (s) max (s)
(x, r ph V2+1 1 (8.
where by definition, VH+1 H+1 - Furthermore, fi.f(s,a) & Egr-pa (11..) [f(') denotes the expectation operator with respect to the transition probabilities pa and TTg((s) & g(s, (s))) denotes the composition with the policy æ at step h.
Learning problem The agent, to which the transitions are unknown (the rewards are assumed to be known for simplicity), interacts with the environment during T episodes of length H, with a fixed initial state s1.² Before each episode t the agent selects policy x' based only on the past observed transitions up episode
1. At each step h [H] in episode the agent observes a state s) E S, takes an action (s)) = dj. E AA and makes transition to new state 4/41 according to the probability distribution pa (s), af)) and receives deterministic reward r' (
Regret The quality of an agent is measured through its regret, that is the difference between what it could obtain (in expectation) by acting optimally and what really gets,
T Σ Vi((s) (s1).
RT &
Counts The number of times the state action-pair (s, was visited in step h in the first t episodes is denoted as (s, a) Ei (s at)) = (s, a)}. Next, we define n (5'(s,)) a) a Ei= If (8) ai, +11) = (s, a, 8)) the number of transitions from s to s' at step h.
Improper Dirichlet distribution For m E No, the probability simplex of dimension m is denoted by Am- For a E ( we denote by Dir(a) the Dirichlet distribution Am with parameter We also extend this distribution to improper parameter a E (R+)mt +1 such that Σm ar > 0 by in- jecting
into A.,. Precisely, we say that p Dir(a) if (p<) ~ Dir((as)aa and all other coordinates are zero.
Additional notation For N E N+4, we define the set [N] & (1....,, NJ. We denote the uni- form distribution over this set by Unif[N]] The vector of dimension N with all entries one is N A (1....,1)) The empirical probability distribution (s, a) is defined as (s' s) ( a) ()/n a) if (s, a) and pf (s'(s, 1/S otherwise. Appendix references all the notation used.
6 We study deterministic rewards to simplify the proofs hut our result extend to bounded random rewards as well.
As explained by Ficchter [1994] and Kaufmann al. [2020], if the first state is sampled randomly as 81 ~ P. we can simply add an artificial first state 81r such that for any action a, the transition probability detined as the distribution (sr a) A p.

---

3 Algorithm
In this section we describe the OPSRL algorithm. In spirit, OPSRL proceeds similarly PSRL except that it uses several posterior samples instead and acts optimistically with respect to them, explaining the name Optimistic Posterior Sampling for Reinforcement Learning (OPSRL).
Optimistic pseudo-state In order to define the prior used by OPSRL, we extend the state space by an absorbing pseudo-state so with reward rn (s a) _ rp > for all h, a and transition probability distribution (n(sslso, a) - 1(s" = 50}. A similar pseudo-state was already introduce in previous works, see for example Brafman and Tennenholtz [2002], Szita and Lörinez [2008]. We denote by S' = {so} } the augmented states space and by As the set of probability distributions over SY.
Pseudo-counts We define the pseudo-counts, (s, a) è (s. a) + no, as the counts shifted by an initial value n2. This shift corresponds to prior transitions to the pseudo-state, that is ,े (s']s, a) & n (5'1ss,) a) no (s' so}- Similar the empirical transitions, we define pseudo-empirical transition probability distribution as (s, a) (s' a) (s.
Inflated Bayesian model Like PSRL, we define Bayesian model on the transition probability distributions, except that the prior/posterior is inflated. The practice of inflating the posterior is common the analysis of Thompson sampling like algorithm, see Agrawal and Jia [2017b], Abeille
and Lazaric [2017]. Precisely, the inflated prior is Dirichlet distribution Dir (s' a) a))a)))))e vES' parameterized by the initial sreudo-counts, and some constant κ. > 0 controlling the inflation. Thus the prior is Dirac distribution deterministic transition leading to the artificial state 8n- Then the inflated posterior is also Dirichlet distribution Dir (175, (s'ls, a))k)) .es)) Note that the prior a proper prior (i.c., valid probability distribution), but it will be updated in an improper way, ie., probability transitions with mass under the prior could get mass in the posterior, as they get positive counts.
Optimistic posterior sampling After episode for each state-action pair (s, a) and step h E [1] we sample J independent transition probability distributions Ph (s,a) Dir (s'ss, wEEs) from the inflated posterior. Then, the Q-values obtained by op- timistic backward induction with these transitions. Precisely the value after the last step is zero Vl (s) A 0 and the optimal Bellman equations become
(s, e (s max Paxp JE[J]
vi())) A max (s,a).
aEA
The next policy is greedy with the Q-values T (s) E arg max (s) The complete proce- dure of OPSRL is described in Algorithm 1 for general family of distributions parameterized by the pseudo-counts over the transitions instead the inflated Dirichlet prior/posterior.
3.1 Analysis
We fix d E 1) and the number of samples
J A [cy 1og(25AHT/5)].
[1 + ((1)) and ((.) is the cumulative distribution function (CDF) of a normal where c, = 1/ (2g(22(111) distribution. Note that // has logarithmic dependence on S, A, H. T, and 1/5.
We now state the regret bound of OPSRL with a full proof in Appendix B. and a sketch in Section 3.2. Theorem 3.1. Consider a parameter E (0, 1). Let k. P 2(ogg(2SAHH/) + 3 log(cn(2T 1))), no A [K(co + log17/16(T))] ro A 2, where co is an absolute constant defined in (4); see Appendix B.2, Then for OPSRL, with probability at least 6- 6,
π.. = (VHSSAALL H² 52 H
5

---

Algorithm OPSRL
1: Input: Family of probability distributions
N
As over transitions, initial pseudo-
count T2g. number of posterior samples J.
2: for E (T) do
3: For all (s, as a, h) E x A [H], sample J independent transitions " Ph
(s, a) ~ p(T " a)(ss)) [
4: Optimistic backward induction: set V 1++ (s) = and recursively for h E [H] compute
Q (8, a) = ( a) + max Ph - (8) jE(J]
1-1 V (s) = max Un (s. a)
aEA
T (s) arg max Qi (s)a). a) aEA
5:
for h E [H] do
6: Play oj, =
7: Observe 5/111 Ph a)))
8: Increment the pseudo-count ( 11% af2)
9: end for
10:
end for
where T. A O(log(HSAT)))
Computational complexity OPSRL is a model-based algorithm, and thus gets the O A) space complexity as PSRL. Since we need (11) posterior samples per state-action pair the time complexity of OPSRL is of order O(H A) per episode, the same PSRL up poly-logarithmic terms. Building on the idea of Efroni et al. [2019], in Appendix F we propose the Lazy-OPSRL. algorithm a more time-efficient version of OPSRL. Instead of recomputing the Q-value by backward induction before each episode, Lazy-OPSRL only performs one step of optimistic incremental planning at the visited states. It enjoys a regret bound of the same order ((TSHAT) as OPSRL but with an improved cime-ccoplexity per episode (HSA), see Theorem E.1 in Appendix F.
Comparison with SOS-OPS-RL and PSRL One structural difference between OPSRL and SOS-OPS-RL of Agrawal and Jia [2017a] is that OPSRL only relies on optimistic posterior sam- pling while SOS-OPS-RL also uses simple optimistic sampling: mixture of the uniform distribution over the states and an empirical estimate of the true transition kernel biased by some bonus-like like terms. In particular, OPSRL does not use bonus-like quantities which could lead to poor empirical performance [Osband and Van Roy, 2017]. Another important issue the number of posterior samples. SOS-OPS-RU needs ÕSS) posterior samples in order to obtain a regret bound of order ((H2SVAT) whereas OPSRL needs only ((1) samples and obtains a better regret bound. Note that if we choose the number of posterior samples as J in OPSRL we recover PSRL up to two technical differences: First, the posterior is inflated in order to increase its variance. This technical trick was already used by Agrawal and Jia [2017a] and allows to guarantee optimism with a small number of posterior samples, see Section 3.2. Second, OPSRL uses particular prior which is a Dirac distribution a deterministic transition towards an optimistic pseudo-state. This prior is needed to control the deviations of the (inflated) posterior, see Theorem D.2.
Comparison with RLSVI Both OPSRL and RLSVI build on the same mechanism for exploration. RLSVI just adds an Gaussian noise to the Q-values whereas OPSRL injects the noise naturally via a random transition sampled from Dirichlet distribution. As controlling the deviation of the Q-value obtained with additive Gaussian noise is not difficult, the analysis of RLSVI is relatively straightforward [Russo, 2019, Ishfaq et al., 2021]. On the contrary the analysis of OPSRL is much more involved, see Section 3.2. However, the benefit of optimistic posterior sampling in OPSRL is

---

that it adapts automatically to the variance of the estimates of the transitions which is central for regret bound with an optimal dependence on the horizon [Azar al., 2017]. Adapting to the variance with RLSVI is much more involved and artificial, see Xiong et al. [2021]. This is probably one reason why RLSVI performs empirically worse than PSRL [Osband et al., 2016a].
3.2 Proof sketch
The proof of Theorem 3.1 consists of three important steps. The first step is devoted to the approxima- tion for tails of weighted sums of Dirichlet distribution and embodies the main technical contribution of the paper.
Step 1. Exponential and Gaussian approximation for Dirichlet distribution The first result generalizes Riou and Honda [2020] to Dirichlet distributions with real parameters. Let us first recall the definition of the minimum Kullback-Leible divergence for p E Am where m N+, a function f: (o,...,,,, m) + [0, b] for some b E Ii+ and u E R.
(Dn u, f) & inf inf(KT(p.g) q a 9.2 u):
where we recall that pf A Ex~pf(X). This quantity appears already in the analysis of non- parametric bounded multi-arm stochastic bandits, see Honda and Takemura [2010], Cappé et al. [2013]. As the Kullback-Leible divergence, the minimum bullback-Leiblee divergence admits variational formula by Lemma 18 of Garivier et al. [2018] up to rescaling for any E (0, b),
Knt(p, u. f) AE[0.1/(b-u)) u)l
max
Ex<p log(1 X(f(X) u))].
Theorem 3.2 (Exponential upper bound, see Theorem D.I). For any (0r, ...,.... ,m,) E TR define E Am such that p(E) az/a,l = o,...,m,
m, where 2i= Oz.. Then for any f: (0, .0....,m, m - b) and 0 < μ < b, we have
PwNDH(())u n4] < exp(-aKingTT) M, f)).
The second result is devoted to tight Gaussian lower bound for the distribution of a linear function of Dirichlet random vector. Here we follow the ideas of Alfers and Dinges [1984] and use the exact expression for the density of linear form of Dirichlet random vector derived by Tiapkin et al. [2022].
Theorem 3.3 (Gaussian lower bound, see Theorem D.2). For any a = =(00 + 1,01...... 3m) E
Rm+1 define p E Am such that p(E) at/a, l O,....
...... m, where a EE Qz- Fix (0, 1) and assume that Ogg 2 c(E) + 10g17/16 (α) for c(E) defined in (11), Appendix D, and a 2 20g-
Then for any f: {0....,m) m] + [0, bul such that f(0) = by, f()) $ < 2o/ E (1,...,m, m] and (pf.bo)
P PuwDir(o) (wf 2 11 (1-e) 2 20x Konlo u,,
We emphasize that increasing the parameter org corresponding to the largest value of f by 1 is crucial. The same technique was used by Alfers and Dinges [1984] to derive lower bound on the tails of the Beta distribution.
Remark 3.4. We stress that the anti-concentration inequality of Tiapkin et al. [2022, Theorem D.2] is not sufficient for our purposes; their additional factor क -3/2 in front of the exponent makes it unusable for the analysis of OPSRL. Indeed, this inequality would imply (TT3/2) samples from the inflated posterior in order to get optimism with high-prohability, whereas with our refined bound (Theorem 3.3) we only need (1)) posterior samples.
Proof sketch of Theorem 3.3. We start from the integral representation for the density by Tiapkin et al. [2022, Proposition D.3]. Define Z A wf for w Dir(as + 1, L,a.,..., am,) then for any u E (0, bu),
{ (1+ i(bo u)s) II (1 +(f(((() uuss) - ds.
pz(u)= 2T JR
7

---

One additional term (1 + i(bo - u)s) comes from increasing the parameter ag by 1 corresponding to the value f(0) bo-
In the same spirit as it was done by Tiapkin et al. [2022], we apply the method of saddle point (see Fedoryuk, 1977, Olver, 1997) to the complex integral above. Informally, for cng σz by large enough the following approximation holds
(z( R 2T (bb u)) exp( Kine u, f)),
where X is the unique solution to the problem (2) and o² Ex-p (1-x0(()-)) The formal statement can be found in Lemma D.5 of Appendix D.
[(X]-u
Next we perform a change of variables f²/2 = Kmn(p, u, f) in the above expression to get
ho
PP wwwDir(oo+ L I.
V 2T (b u))² exp( Kint(P u, f) |wf 2 11
D(u(t))o(t0..)dd.
where o(x) μu, o²) is density of (N, o²) and D(u) is weight function bounded from below by 1 (see Lemma D.6 of Appendix D). This lower bound on D(u) concludes the proof.
Comparison with anti-concentration bound by Agrawal and Jia [2017b] We emphasise that our technique of deriving a Gaussian-like lower bound is substantially different from the methodology used by Agrawal and Jia [2017b]. The latter one was based on reduction of weighted sum of Dirichlet random vector to weighted sum of independent Beta distributed random variables and subsequent application of the Berry-Esseed inequality, whereas our approach relies on the integral representation for the density of the corresponding linear projection of Dirichlet random vector.
In particular, the Berry-Esseen inequality is likely to be very coarse since it uses only the first three moments of the distribution and therefore generates an additional S-factor. At the same time, our analysis is much better fitted to the Dirichlet distribution and provides very tight lower bound. The tightness of our bounds can be checked by comparing it to a similar result for the beta distribution derived in Alfers and Dinges [1984].
Step 2. Optimism Next, we apply Theorem 3.3 to prove that the estimate Q-function D% is optimistic with high probability for our choice of inflation parameter and number of posterior samples J: Q (s, a) 2 ()) for any (s, h, t) E x A x [H] x [T].
We show that the inequalities maxje (P) ( (s,
Z Pn Vi (s, a) hold for all (s, a, h, S x A [ [7] with high probability. First, notice that 2/ (s, a) Dir(og + 1,0,,.... as)) for oq no/ k - 1, a;- = ni, (s:|s, a) and ā ())))))))/a Additionally, define probability distribution q E As such that (i)) = a a This distribution slightly differs from (s, a) because of an additional +1 the parameters of the Dirichlet distribution. Next, we may apply Theorem 3.3 with 1/2 and proper choice of no no(e),
[ V
1 1 +b Ph (8,1(8,00) 2 Pa V (8,
2 <(V
P Fr (s.a)) as)
where a (7t, xx) Kinr(g, Ph Vit (s, Vi+1) and 2(.) is cumulative distribution function (CDF) of a standard normal distribution. By concentration argument we have
< S ni, (a a). ps V (8, a), Vi+1) S x/2,
with high probability for an appropriate choice of к = Ö(1). For this step of the proof the presence of the inflation parameter λ is crucial: this parameter increases the variance of Ph (s,a) a) ensure that the above inequality holds with a constant probability. Next, by tak- ing the maximum over J = AS samples and applying union bound, we guaran- tee that the inequality max 14d Vi a)} 2 pa (i44 a) holds simultancously for all
8

---

(s, a. h, E S x A [H] x (T) with probability at least 1 5/2. The formal statement and the proof could be found Proposition B.4 of Appendix B.2.
Finally, the standard backward induction over h E [H] concludes optimism. Indeed, the base of induction h H 1 is trivial. Next, by the Bellman equations for Qi and Q have
(s.a) - 0% (s, a) = max (ph
( V (8,1 a)} Ph Vh+ (8, ())
The induction hypothesis implies V v+t (5') 2 Qu+i(s', for any s' S. Hence.
a (s 2 1 ",,x"(s))) Vi++((')
a)) Qi max (p. (8 pa Pa 20 jE(l]
with probability at least 8/2.
Step 3. Regret bound The rest of proof directly follows Azar et al. [2017], where UCBVI algorithm with Bernstein bonuses was analyzed. By the optimism, we have
T
T
Σivi(s)) - VT (s1) Σ 8/
R =
1=1
1=1
where 8j e V (0%) - V/ (s%) The quantity 5% can be decomposed as follows using the Bellman
equation for Vxx and Qn 1-1
8% 1/
11 (sh a/)
Qh (sh, a/))
xet V h+1
(sh. ah) - Ph V (s/2 al,)
max jE[l]
Ph.
max sE(j]
Ph
--- V 1-
h+1
1 ohi) ph -
h+1 (8/ a1h) 1ph 1-1 Ph
1 h+1 (sh an)
(B)
(A)
+ 1r
ph [
V 18h at)) + 1P PnlVi (sh: an)
(C)
(D)
+ [v.VV t-1
A+1 - V 1shh aht - 14 - (o +0h+1
The terms (C),()) and c are standard in the analysis of the optimistic algorithms. The term (B) could be upper-bounded by ro-nn-H and turns out to be one of second-ored terms. The analysis of (A) is novel and requires application of the Bernstein inequality for Dirichlet distributions that follows from Theorem 3.2 and spelled in the following lemma.
Lemma 3.5 (see Lemma C.6 in Appendix C). For any a = (oo, on.... am) E Rm=-1 define E Am such that p({) ae/a. az E = O,..., m, where a = Ei=u09 az. for any f: {O....,. m] -
[0, bj such that f(0) = b and 8 E (0,1),
Varz(f) (oot(())og(///))) a
3b log(1/5) α
P Pw-Dir(a) w pf + 2/
S 5.
As opposed to Lemma C.8 of Tiapkin et al. [2022], the last result applies to Dirichlet distributions with non-integer parameters in our case (due the presence of the inflation parameter x). Therefore, see that the term (A) can be upper bounded by quantity which has the same role as in the analysis of UCBVI. After using the Bernstein bound, the rest of the proof follows from the analysis of UCBVI
with the Bernstein bonuses and Bayes- -UBBI: see Azar et al. [2017] and Tiapkin et al. [2022].
Experiments
In this section we provide experiment to compare OPSRL with some baselines on simple tabular environment; see details in Appendix G. particular, we illustrate that OPSRL competitive with the original PSRL algorithm and outperforms bonus-based algorithms such UCBVI.

---

Baselines We compare OPSRL with the following baselines: UCBVI (with Hoeffding- type bonuses) and UCBVI-B (with Bernstein-type type bonuses) Azar al. [2017]. PSRL Osband [2013], and RLSVI Osband et al. [2016b]. See Appendix G for full details on parameters for OPSRL and baselines.
name
70000
60000
RUSMI
UCMM
UCSVI-B
2000
4000
5000
8000
10000
epsode
Figure 1: Regret of OPSRL and baselines grid-world environment with 100 states and action for H 50 an transitions noise 0.2. We show average over 4 seeds.
Results In Figure 1, we plot the regret of the various baselines and OPSRL in the grid world environment. In this experiment, we observe that OPSRL achieves competitive results with respect to PSRL. It not completely surprising since they share the same Bayesian model on the transitions up to the prior. We shall elaborate more on the influence of the prior in Appendix G. We also note that OPSRL outperforms UCBVI and RLSVI. This difference may be explained by the fact that OPSRL's optimism implies (in the worst case) KL bonuses as in Filippi et al. [2010]. The KL bonuses are stronger than Bernstein bonuses, see Lemma E, because they somehow rely on all moments of the empirical distribution rather than the first two moments in the case of Bernstein bonuses first moments for Hoeffding bonuses or for the variance the Gaussian noise in RLSVI. Note also that in OPSRL, do not have solve the complex convex program to compute the KL bonuses Filippi et al. [2010], which could be computationally intensive.
Conclusion
In this work, we presented the OPSRL algorithm which can be viewed as a simple optimistic variant of the PSRL algorithm. Notably, OPSRL only needs Ō(1) posterior samples per state-action. We proved that the regret of OPSRL is upper-bounded with high probability by O(VH+$AT)) matching the problem-indepeeddnt lower-bound of order Q(VH3SAT) for T large enough and up to terms poly-logarithmic H, S, A, and While our work addresses the open questions raised by Agrawal and Jia [2017b] in the episodic setting, obtaining the same results in the infinite-horis reward setting remains an open issue. We believe that possible to adapt our analysis to this other setting up some technical adjustments. Ultimately, another open question, is obtain regret bound for PSRL, that is, when using only a single posterior sample and not inflating the posterior. As further future research direction we believe it could be interesting to obtain a model-free algorithm that relies on the same mechanism as OPSRL for exploration. Indeed, such an algorithm could avoid the use of complicated bonuses adopted by the current model-free algorithms while reducing the memory complexity of OPSRL.
average
Acknowledgments and Disclosure of Funding
D. Belomestny acknowledges the financial support from Deutsche Forschungsgemeinschattt (DFG), Grant Nr. 497300407. The work of D. Tiapkin, D. Belomestny and A. Naumov was prepared within the framework of the HSE University Basic Research Program. Pierre Ménard acknowledges the support of the Chaire SeqALO -ANR-20-CHIA-0000-00
10

---

References
Yasin Abbasi-Yadee Yadkori and Csaba Szepesvári. Bayesian optimal control of smoothly parameterized systems. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 15, page 2-11, Arlington, Virginia, USA, 2015, AUAI Press, ISBN 978099664310S
Marc Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 o Proceedings of Machine Learning Research, pages 176-184. PMLR, 20-22 Apr 2017. URL https: / http///proceeeen/e///ee//e/ee//e mlr. m.r.press wwwppeeeeeeeee v/t/ www////a//llleeee abwilleelllllaaae html.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 39.1-39.26, Edinburgh, Scotland, 25-27 Jun 2012. PMLR. URL https: fttap://prroceddngg mlr. aatesss/23//ggraaaalaa html.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Carlos M. Carvalho and Pradeep Ravikumar, editors. Proceedings the Sixteenth International Conference on Artificial Intelligence and Statistics, volume 31 of Proceedings of Machine Learning Research, pages 99-107, Scottsdale, Arizona, USA, 29 Apr-01 May 2013. PMLR. URL https: //proceedings mlr press/ hatp//aaaaaaaaaa html.
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. CoRR, hts/1705500041, 2017a. URL htttt://aaaxii wrw. 1070p///710.0.....
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30. Cur- ran Associates, Inc., 2017b. URL https: http://pproeeee...//ee/e/oo/sest wetgis..eriis.. cttps.ccpppppee pccpppprr/001//Elee 3621f 3621f 1ea144441454555555222223333
pdf.
D. Alfers and H. Dinges. A normal approximation for beta and gamma tail probabilities. Zeitschrift für Walrsscheinlichkeeitsseeerr und Verwandte Gebiete, 65(3):399 420, Feb 1984. ISSN 1432-2064. doi: 10.1007//BF00533744, URL https: http::/dooiooo. 1007//0000///////377774
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, 2017. URL https:
//arxiv.
baaxxiv.rgg//a wtt/pdf/////ooooooooooooo///oa// http/dff/1700 /1703. 05449. pdf.
Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric Maillard. Optimal thompson sampling strategies for support-aware evar bandits. In Marina Meila and Tong Zhang, edi- tors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 716-726. PMLR, 18-24 Jul 2021a. URL html.
https: http:s///pocceeings..omm mlr grress/v39//aaee
Dorian Baudry, Patrick Saux, and Odalric-Ambryen Maillard. From optimality to robustness: Dirichlet sampling strategies in stochastic bandits. In Neurips 2021, 2021b.
Ronen I. Brafman and Moshe Tennenholtz. R-MAX A general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3:213-231, 2002.
O. Cappé, A. Garivier, O-A. Maillard, R. Munos, and Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 1163)11511-1541,,
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Neural Information Processing Systems, 2017. URL
07710. pdf.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. Regret bounds for kernel-based reinforcement learning. arXiv preprint arXiv:2004. 055999 2020. URL org/ ab//abb////0.// 05599.

---

002...66.444949.. Omar Darwiche Domingues, Yannis Flet- Her-BBe Edouard Leurent, Pierre Ménard, Xuedong Shang. and Michal Valko. rlberry- Reinforcement Learning Library for Research and Education, 10 2021. URL htt.://ppp//ttbb...../bbeerr//// comm///bbeerrryyy//eeerrr
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In H. Wallach, H. Larochelle, A. Beygelzimer, F. A'Alché- Alché-Buc, Fox, and R. Gamnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: //ppcceedings... Papeeeappppppppp
neurips. http://pppe/////oe//////aaaaaaaa
M. V. Fedoryuk. Metod perevala. Izdat. "Nauka", Moscow, 1977.
Claude-Nicolas Fiechter. Efficient reinforcement learning. In Conference Learning Theory, 1994. URL http:::/ccttseerrr..tttttt ist ist. http:////eeooo////ooaaddaeeeeee is
S. Filippi, O. Cappé, and A. Garivier. Optimism Reinforcement Learning and Kullback-Leiin Divergence. Allerton Conference on Communication, Control, and Computing, 2010.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias bias-span upan-constrainge exploration-explootttinn in reinforcement learning. In International Conference on Machine Learning, pages 1578-1 1566. PMLR, 2018.
Aurélien Garivier, Hédi Hadiji, Pierre Menard, and Gilles Stoltz. Kl-ucb-switch: optimal regret bounds for stochastic bandits from both a distribution-ddpeedeett and distribution-fre viewpoints. arXiv preprint me0..0007577770 2018.
Junya Honda and Akimichi Takemura. An asymptotically optimal bandit algorithm for bounded support models. In Adam Tauman Kalai and Mehryar Mohri, editors, COLT, pages 67-79, Omnipress, 2010. ISBN -78-0-9822529-2-5. URL http: attt:://blpp uni-triers www.iierdeed///beee /onffo/////o/oooooooo/ooo////o/n colt/colt2010 html #HondaT10.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pages 4607-4616. PMLR, 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Ncar-optimal regret bounds for reinforcement learning, Journal of Machine Learning Research, 99:1563-1600, 2010. URL http:///www jmlr.
pdf.
Chi Jin, Zeyuan Allen-Zhu, Séhastien Bubeck, and Michael I. Jordan. Is Q-learning provably efficient? In Neural Information Processing Systems, 2018. URL https: //appsi////xxi..//// http://www....ppptt//../ org/pdf/ 1807. 1807.03765. pdf.
Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. arXiv preprini arXiv:2006.0588 jun 2020. URL http:://aaxiii org/ hatg//bb//20000 05879.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Proceedings of the 23rd International Conference on Algorithmic Learning Theory, ALT" 12, page 199-213, Berlin, Heidelberg, 2012. Meringer-Verlage ISBN
doi: 10. 10110077978-366444441069999 978-3-642 000-666223410---111111
9783642341052.
URL
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. arXiv preprint arXiv:2006.062944 2020. URL https:ttp///m htap::///axxxii httgg/pd//2000
Branislav Kveton, Csaba Szepesvari, Sharan Vaswani, Zheng Wen, Tor Lattimore, and Mohammad Ghavamzadeh. Garbage in, reward out: Bootstrapping exploration in aulti-armed bandits. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3601-3610. PMLR, 09-15 Jun 2019. URL https: stttps://proceedinng mlr, www...eessvieee kveton 9a. html.
12

---

Pierre Menard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momentum q-learning: Correcting the bias without forgetting, 2021. URL 01312.
htagg/abs/21000 2103.
Frank W. J. Olver. Asymptotics and special functions. AKP Classics. A K Peters, Ltd., Wellesley, MA, 1997. ISBN 1-56881-069-5. Reprint of the 1974 original [Academic Press, New York;
MR0435697 (55 #8655)].
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2701-2710. PMLR, 06-11 Aug 2017. URL https://proottte http:////pcceeee.../// mlr ppwsss/70/ osband17a.htm..
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In C. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Cur- ran Associates, Inc., 2013. URL https: https:// http://///..cccnn.....o. negris..urps.... wwtprriss.cppppppeeeee pc/pppprr/013//1le pdf.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep explo- ration via bootstrapped dqn. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Cur- ran Associates, Inc., 20. URL https: http:://pooooddddeee www.eeeinnnnnnnnnsss..eeee pdf.
neurips htt.ggg...........a///////eeeeee cc/paper/2016/Eiie
lan Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2377-2386, New York, New York, USA, 20-22 Jun 2016b. PMLR. URL https: http:///oocceddeeeee mlr. www.irppees//eee wwwps//4////pppppppppp hwtps//////bbbb1166// osw.nd16........ html.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep rein- forcement learning. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. cisa-Bianchi, and R. Gamnet, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018 URL https://proot https://proceedinggs www.ediiinnnnnnnunsneeeeee httpannnn..nn.....eeeereeeeeeeee hwtp:rpp..ccpppppr///////....... /appp/////////lle
pdf.
Ian Osband, Benjamin Van Roy, Daniel J. Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019. URL http:
139/939111111111 html.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown markov decision processes: A thompson sampling approach. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 1333-1342, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97815 11111699066..
Aldo Pacchiano, Philip Ball, Jack Parker-Holder, Krzysztof Choromanski, and Stephen Roberts. Towards tractable optimism in model-based reinforcement learning. In Cassio de Campos and Mar- loes H. Maathuis, editors, Proceedings of the Thirty-Sevents Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 1413-1423. PMLR, 27-30 Jul 2021. URL https: : httpp::/ppooeeee:iee http://pooeeeeeeeeeeeeeeeee mlr. wttps///vv1//ppccchcco
html.
Jian Qian, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Concentration inequalities for multinoulli random variables. CoRR, abs/2001.11595. 2020. URL https:// //arxiv. org/ /bbs// 2001. 11595.
Charles Riou and Junya Honda. Bandit algorithms based on thompson sampling for bounded reward distributions. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 777-826. PMLR, 08 Feb-11 Feb 2020. URL. attps://proceedeie press/vi17/iiou/e html.
mlr.
html..
13

---

Daniel Russo. carst-case regret bounds for exploration via randomized value functions. In H. Wallach, H. Larochelle. A. Beygelzimer, d'Alché-Bue, E. Fox, and R. Gar- netr, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL. 11111888222666000222277722272172
pdf.
Daniel Russo and Benjamin Van Roy. An information-theoree analysis of thompson sampling. Journal of Machine Learning Research, 17(68): 2016. URL http://jmmll org/ hatggpapers//// v17/14-083 087 .html.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direcctd sam- pling. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Wein- berger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL httpss////coceeggs..oo. (alaa0eeb66661167777244444448224
R. Sutton and A. Barto. Reinforcement Learning: Introduction. MIT press, 1998.
István Szita and András Lörinez. The many faces of optimism: unifying approach. Proceedings of the 25th International Conference on Machine Learning, ICML '08, page 1048-1055, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605550054. doi: 13.9029888.. URL https://doi. org/10..//o/ 1111111..11111111 1144/13991111661 Ttt.119911....11.1..11 1390288.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-awan regret bounds for undis- counted reinforcement learning in mdps. In Algorithmic Learning Theory, pages 770-805, 2018.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4)2285-22) 294, 12 1933. ISSN 0006-3444. doi: 10. 10..9///biomme/233.42255.. URL https://doi org/ 1093//icmet/2555 3- 4. 285.
Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Pierre Menard. From Dirichlet to rubin: Optimistic exploration in RL without bonuses. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 21380-21431. PMLR, 17-23 Jul 2022. URL https: httpc//eeooo......//////// mlr
MDP. CoRR, abs/2102.09703, 2021. URL wwwppppsssssssseeeee prress/v162ttiapkimne html.
Zhihan Xiong, Ruoqi Shen, and Simon Du, Randomized explorationn near-optimal for tabular 09703.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Proceedings of the 36th International Conference Machine Learning, (ICML), 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Mattco Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1954- 1964. PMLR, 26-28 Aug 2020. URL https: /tptopee/ppooeeddigggs mlr. prress/vi0//zanee html.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-855 2022. doi: 10.1137/21M1409244X URL https: //doi org/10. 1137711.1111111111111 1117/2221149924.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model- reinforcement learning via reference-advantage decomposition. In Advances in Neural Information Processing Systems, 2020.
URL https:://///. //tp///axvvv////////////e/e///a/ wttaaaiiw.g//aaaaaaaalaaa wtt/po///////o//oo 10000000.110000 10019. 10f.9.pdf.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] See Section G
of Appendix.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material URL? [Yes] See Section of Appendix.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "kBwaUkl0Y50", "reviewer": "Reviewer_Qhqb", "summary": "This paper proposes a novel optimistic posterior sampling algorithm, showing that it can achieve nearly mini-max optimal regret bound with a novel anti-concentration inequality of Dirichlet distribution.\n", "questions": "* I’m not convinced that this method can be better than the frequentist method, as it implicitly mimics the Bernstein type bonus with a sampling method. Can the authors describe what are the potential benefits of the proposed methods over traditional methods like UCBVI? (I admit that UCBVI focuses on the worst-case guarantee and sampling based methods can be better in constant, but I don't think this can lead to e.g. instance-wise benefits.)\n\n* In Line 182-184, is the proposed algorithm applied to general prior other than Dirichlet, as there is only one anti-concentration result for Dirichlet distribution? If not, I think there is no need for this claim.\n\n* Can the proposed methods be generalized to the case with function approximation? It is much more favorable to provide some insights that can be generalized to more general scenarios (e.g. [1]) rather than sticking to the specific tabular setting and Dirichlet distribution.\n\n[1] Zhang, Tong. \"Feel-good thompson sampling for contextual bandits and reinforcement learning.\" SIAM Journal on Mathematics of Data Science 4.2 (2022): 834-857.", "limitations": "This is a theoretical paper that does not need to address the potential societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n* A novel anti-concentration inequality for Dirichlet random vector, which may be of independent interest.\n\n### Weaknesses:\n* The application scenario is too limited, as it crucially depends on the Dirichlet distribution. Some artifacts like the pseudo-state $s_0$ may exacerbate this issue.\n* No empirical demonstrations of the newly proposed algorithm. The authors claim the benefit of posterior sampling algorithms multiple times (e.g. Line 216-225). Although there are several empirical demonstrations that show that some versions of the optimistic posterior sampling algorithms work better than the empirical counterpart, it’s not clear if such variants can still perform well. Given that this paper is all about tabular settings, I prefer having such an evaluation.\n* For me it is much more like an applied math paper, as it does not really solve important questions in reinforcement learning. It mainly show one other potential optimism mechanisms with the anti-concentration of Dirichlet random vector.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K74tTn9A4Qk", "reviewer": "Reviewer_DQbg", "summary": "The paper proposed an optimistic posterior sampling algorithm for episodic MDPs and proved that the algorithm has a regret bound matching the lower bound up to poly-log terms. ", "questions": "As discussed in the paper, the current proof only works when L posterior samples are drawn and L has some logarithmic dependence on H,S,A,T. Given empirical success of posterior sampling with one sample or a fixed number of samples, it would be very interesting if one can have some theoretical guarantees for these settings. From the proof, the size of L seems to come from the union bound on ensuring optimism for all state at all times. Are there some ideas on how the analysis could be extend to settings when L is a constant?", "limitations": "The problem setting and limitations are discussed and addressed in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed OPSRL algorithm combines ideas from optimism and posterior sampling. Though there are existing algorithms with a similar algorithmic structure (Fonteneau, Korda, Munos, An optimistic posterior sampling strategy for bayesian reinforcement learning, NIPS 2013 Workshop on Bayesian Optimization), OPSRL is the first one with lower bound matching regret guarantee.\n\n- New technical properties on the Gaussian lower bound for Dirichlet distribution is critical in establishing that the sampled Q-function is optimistic, and the exponential upper bound is used in the concentration results. They are useful in proving regret bounds for the episodic MDP setting, and they might be useful for posterior sampling algorithms in other settings as well.\n\n\nWeaknesses:\n- No numerical experience verifying the theoretical results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HNK9O9dcqM", "reviewer": "Reviewer_uUPZ", "summary": "This paper proposed an optimistic variant of the PSRL algorithm and proved a minimax regret bound, which settles an open problem raised by Agrawal and Jia [2017b]. The main technical contribution is a new sharp anti-concentration inequality for Dirichlet random vector, which may be useful for other settings.  ", "questions": "- Can authors elaborate more on how OPSRL adapts automatically to the variance of the estimates so that the optimal dependence on H can be achieved?", "limitations": "I am not aware of any potential negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper proved minimax regret bound for an optimistic variant of the widely used PSRL algorithm, which settles an open problem. \n- The algorithm is simple and clean. \n- The theoretical novelty in developing a tight anti-concentration bound. \n\nWeaknesses:\n- OPSRL is very similar to the algorithm analyzed in Agrawal and Jia [2017b] and the main difference is only in applying the new anti-concentration bound, which simplifies some technical ingredients in Agrawal and Jia [2017b]. \n- OPSRL is still far from the standard PSRL that people use/want to study as multiple posterior sampling is performed at each episode to achieve optimism, which makes the algorithm more similar to UCB algorithm. \n- If the authors compare the anti-concentration used in Agrawal and Jia [2017b] with their approach in more detail, it would be easier to understand why the extra S factor is removed. \n\nMinors:\nThe paper (Randomized Exploration in Reinforcement Learning with General Value Function Approximation) might be relevant as it considers optimistic RLSVI.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept