Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
Authors: Zhihan Xiong
Ruoqi Shen
Qiwen Cui
Maryam Fazel
Simon Shaolei Du
Venue: NeurIPS 2022 Accept (2022)
Keywords: randomized exploration
reinforcement learning theory
tabular MDP

Abstract: We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case $\widetilde{O}\left(H\sqrt{SAT}\right)$ regret bound for episodic time-inhomogeneous Markov Decision Process where $S$ is the size of state space, $A$ is the size of action space, $H$ is the planning horizon and $T$ is the number of interactions. This bound polynomially improves all existing bounds for algorithms based on randomized value functions, and for the first time, matches the $\Omega\left(H\sqrt{SAT}\right)$ lower bound up to logarithmic factors. Our result highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic are lower bounded by a constant, and 2) a new recursive  formula for the absolute value of estimation errors to analyze the regret.

Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
Zhihan Xiong
Ruoqi Shen shenr30cs washington, edu
zhihanx0cs. washington edu
Qiwen Cuil* qwcui@cs. washington. edu
Maryam Fazel² mf mfazelGuw. saeelGuw.. Bawlluwweddu edu
Simon S. Du
ssduêcs. wwshington. edu
Paul G. Allen School of Computer Science & Engineering, University of Washington 2 Department of Electrical & Computer Engineering, University of Washington
Abstract
We study algorithms using randomized value functions for exploration in reinforce- ment learning. This type of algorithms enjoys appealing empirical performance.
We show that when we 1) single random seed in each episode, and 2) a
Bernstein-type magnitude of noise, we obtain worst-case Ô (HVSAT) regret bound for episodic time- inmommonmogeeouus Markov Decision Process where S is the size of state space, A is the size of action space, H is the planning horizon and T is the number of interactions. This bound polynomially improves all existing bounds for algorithms based randomized value functions, and for the first time,
matches the Ω HVSAT lower bound up to logarithmic factors. Our result
highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic lower bounded by constant, and 2) recursive formula for the absolute value estimation errors to analyze the regret.
Introduction
This paper concerns learning in tabular Markov Decision Processes (MDP), arguably the most fundamental model for reinforcement learning (RL.. Existing algorithms that achieve the near- optimal minimax Ō (HVSAT) regret bound are based on the principle of Optimism in the face
of Uncertainty (OFU), such as upper confidence bound (UCB) [7, 53, 16, 57, 55].' Here S is the number of states, A is the number of actions, H is the planning horizon, and T' is the total number of interactions between the agent and the environment.
"Equal Contribution
'Tii bound for time-inhmmogencous MDP with each reward bounded by and is sufficiently large.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Another broad category is algorithms with randomized exploration such as Thompson Sampling [36, 5, 39J. These algorithms inject (carefully tuned) random noise to value function encourage exploration. UCB-type algorithms enjoy well-established theoretical guarantees but suffer from difficult implementation since an upper confidence bound is usually infeasible for many practical models like neural networks. Instead, practitioners prefer randomized exploration such as noisy networks in [19], and algorithms with randomized exploration have been widely used in practice [37, 13, 11, 35]. However, how to design randomized exploration algorithms in principled way and perform randomized exploration optimally is far from clear. While randomized exploration can have great performance in practice, theoretically, the best known worst-case regret bound for algorithms with randomized exploration is Ô HH2 AT) [2], which is far worse than that of the UCB-type algorithms. In this paper, we introduce a new randomized exploration algorithm and show it enjoys near-optimal δ / worst-case regret bound, thus closing the gap. Our work sheds new light on randomized exploration on both the algorithmic side and the theoretical side.
Our Contributions. Our contributions are summarized below:
We propose a new algorithm, Single Seed Randomization (SSR), which incorporates a crucial algorithmic idea: using a single random seed for the entire episode, in contrast to previous methods of randomized exploration which use one seed for each time step. SSR is able to explore more efficiently than previous methods by avoiding having noise at different time steps canceling with each other. Theoretically, we show, thanks to this new idea, if one uses a Hoeffding-type magnitude of noise, SSR achieves an Ô (HL.VSAT) regret bound, improving upon the best existing result on
randomized exploration algorithm [2].
We further design new Bernstein-type magnitude of noise for our algorithm, and achieve an H (HVSAT) regret bound, resolving an open problem raised in [2]. To our knowledge, this is the first time that a Bernstein-type bound is used in randomized exploration. More importantly, our upper bound matches the 2 (H (HVSAT) minimax lower bound up to logarithmic factors.
We note that our goal is not to show randomized exploration is better than optimistic algorithms [7] in the tabular setting. Instead, we aim to provide solid theoretical understanding of a practically relevant algorithm. Indeed, understanding randomized exploration itself is an important theoretical research direction and has attracted much interest in the community [3, 4, 6, 41, 52, 48, 2, 36, 39, 37, 35].
Main Challenge and Technical Overview. Besides the aforementioned algorithmic ideas (single random seed and Bernstein-type magnitude of noise), we also need additional ideas in analysis to prove the desired regret bound. The main challenge is that unlike UCB-type algorithms, the estimated value in algorithm with randomized exploration, is not upper bound of the true optimal value. This leads to the failure of directly utilizing their analysis, which only need to analyze the one-sided error in estimation. We instead work the absolute value of the estimation error, whose analysis is more complicated than that for the one-sided error in UCB-type algorithms. Working with absolute value forces to ensure that both the probability that the estimated value is optimistic and the probability that the estimated value is pessimistic are lower bounded. However, the clipping strategy in existing algorithm cannot maintain pessimism. To tackle with this issue, we develop new clipping method. Below we list our technical contributions.
1. First, we propose new clipping strategy to constrain the estimated value function (ef. Eqn. (4)). Previous clipping strategics in [52, 2] are based on uncertainty and can only maintain optimism. Our clipping strategy directly works the value function, which is similar to those used in UCB-type algorithms [7, 22, 57]. Our clipping strategy can maintain both the optimism and pessimism. In addition, the number of times that the clipping is used can still be bounded.
2. Second, we prove that the single seed randomization ensures that the estimated value function can both be optimistic or pessimistic with constant probability at all states and timesteps. This is stronger than previous randomized exploration algorithms that are only shown to be optimistic at the initial state with constant probability. With this property, we can then bound the difference between the optimal value function and estimated value function from both above and below, which results in a bound on its absolute value. See Section 5.1, Appendix C and Appendix D.

---

3. Third, we prove novel recursion argument on the absolute value of the policy estimation error. As mentioned in [2], the recursion in UCB-type algorithms can not directly utilized because our estimated value function is not high-probability upper bound of the true optimal value function. With the bound of absolute value, we are able to prove new recursion formulas and together we can control the policy estimation error. See Section 5.2 and Appendix E.
At last, we bound the sum of variance in novel manner. In [7], the UCB-type estimation guarantees that the policy estimation error is always positive so the difference of the variance can be directly bounded. We generalize the argument to the absolute value of the estimation error to bound the sum of variance. See Section 5.3.1 and Appendix G.
2 Related Work
In this section we review existing provably efficient algorithms for tabular MDP. There is long list of sample complexity guarantees for tabular MDP [27, 9, 25, 43, 44, 28, 8, 21, 45, 30, 36, 14, 7, 15, 38, 5, 22, 20, 46, 16, 18, 42, 41, 54, 12, 56, 51, 40, 34, 55, 49, 2, 41, 5, 17, 33, 31]. The state-of-the- methods are based on upper confidence bound (UCB) [7, 53, 16, 57, 55, 33, 31J. For the setting considered in this paper where the transition timeinhomogeneeuus and the reward is bounded by 1.
one can achieve an Ö H (HVSAT) in the regime where T is sufficiently large.
Algorithms with randomized exploration have been proved to enjoy favorable regret bounds bandit problems [29, 3, 26, 10, 4]. In certain settings, randomized exploration can match the worst-case
regret bound of UCB-based approaches and achieve nearly minimax optimal regret bounds [24, 4]. However, for RI, existing theory for randomized exploration are far from optimal [2, 41, 5, 50, 52]. For the setting considered in this paper, the sharpest existing regret bound among algorithms with randomized exploration is Ô AAT))AT))))) proved in [2]. Our paper closes this gap and thus deepens our understanding about randomized exploration.
3 Preliminaries
We consider time-inhomogeneous finite-horizon MDP M SH, where |S| S and |A| = A. Here, S = {I,....S} is the finite state space. A= [1....AA is the finite action space. H is the length of an episode. For convenience, we take $1 to be the fixed initial state, although more general initial distribution will not change the conclusion. P: S x A x [H] + ASS) is the transition function, where the agent stays at state s and takes action a time h, transits state
s' with probability (s'),aas)= E [0, 1]. R S x A x [H] + [0, 1] is the reward function. where the agent stays at s and takes action a at time h will receive reward Th,s, E [0, 1] such that E [rh.s.a] Rh,sa-
deterministic policy for such MDP is defined The associated value function at state s E S and level h E {l...., H} is recursively defined as
tuple ग (T..... TH), where m. : S A.
V (s) = (n + Σ ''ES
Pho (s') Vi+ (s').
For convenience, we set VØ+1 = O E The corresponding optimal value function is Ví (s) = max V/ (s), where II is the set of all possible deterministic policies. For a particular algorithm Alg, let x denote the policy that Alg employs during episode k. Then, the regret of running Alg on MDP M for K episodes is defined
K
Reg (, = R=1
V/ (v
(I)
Note that the regret, Reg (M, K, Alg), is random variable due to randomness in state transition and the algorithm, Alg. In this paper, we show the regret of our proposed algorithm can be upper bounded with high probability, and the upper bound matches the known lower bound up to logarithmic factors.
To facilitate our later analysis, we introduce some notations for empirical estimation. At episode we collect trajectory (sff, ff.r...... stx, al rh) as specified in Algorithm I. Let nı (h, s, a)
3

---

Algorithm 1: Single Seed Randomization (SSR)
Input:
H, S, A. perturbation type ty (Ho, K
for episodes k = .
do
Sample oµ ~ N (0,
Define terminal value function QH+11 = 0 RSA and V VH+1 = R
for time periods h = H, H,...,I do
(n, t- Ri defined in (5)
W (( V
+ (Phis (6).
oy (h, 0)
11 o (h, is
(8, a)) for all E Define VAL (8) - clip2(n--4H)) (maxaed Qa, end
Agent takes actions o argmax (sh a) throughout this episode
Observe data st at, ........ 8H a r and compute åk+1 ph+1 and R&+1 (h, 8, a) for all (h, s,a) [H] x X x A
h, h,s,a
end
a = (s, a}} be the number of times action a is taken at state s and time h before episode k, where 11 {.} is the indicator function. We define
EE 1(sh, (s. a)) aaaaar//oa hiot
nk (h, a) +
EEn 11(s// a/, sh (s,a,
P Ph (5')
Ti (h, 8, a) +1
Then, define empirical MDP based on our observation and estimation before episode & as the tuple M = S, A, ph:
Since Pk not a valid distribution over S, for being rigorous, we can imagine there an additional virtual absorbing state that every state will transit with remaining probability.
In addition to the above notations, let Ô (.) Ô (-) and (-) be asymptotic notations ignoring all poly- logarithmic terms. For distribution D A and value function V e RRS. let V/ (D, V) denote the vari- ance of under distribution D, which is defined as (D,V) = Eses D(s) (V(s) (D, V)) For constant a > O, we define the corresponding clipping function as c.ip, max { {-a, min {a, }]- Immediately we have (0lp,(#)) S a for any O. We introduce the definitions of other notations when used. In appendix, we summarize the notations and definitions used in this paper.
Main Results
4.1 Algorithm
The main contribution this paper is that we show algorithm with randomized value functions achieve regret that matches the known lower bound Ω HVSAT [21, 17] up to logarithmic factors in the tabular setting. To facilitate exploration, this type of algorithms uses random value perturbation instead of deterministic bonus. The algorithm we consider summarized in Algorithm 1. In our algorithm, SSR, the random perturbation ensures that optimism/pessimism can be obtained with constant probability in each episode. Moreover, randomized value function has its origin from posterior sampling for reinforcement learning (Thompson sampling). The randomized perturbation can be interpreted as approximate sampling from the posterior distribution of the value function on randomized training data [41].
We first give overview of SSR. In Algorithm 1, the policy used at episode k is computed using the empirical MDP, M S, pk jt si), which based on observation and estimation before episode However, instead of directly choosing optimal policy for M we add small random perturbation when computing the value of each state and action pair. To be more precise, each

---

episode k. we first estimate the reward and transition function for each state s and action based on (2) and (3). Then, we compute the value function for state and action a.
Qh,k (s. t Rh + (....a V VA+La) (
+ o (h, s,a) &g.
Here, & ~ (o 1) is a standard Gaussian random variable sampled once every episode. The magnitude of the perturbation, oty depends on how many samples ni (h, 8, a) we have observed and how confident we are on the estimations fthh and Pok h,s,a' We will discuss more about the choice of the magnitude later in this section.
In order to prevent estimated value function from behaving badly, add clipping to the value function:
V ( di 1)
max
(n,a(3,))
aE
As our analysis will show, this kind of clipping can bound the value function, maintain optimism and pessimism and also guarantee that clipping will not happen for lot of times. The constant (instead of 1) plays crucial role because it means the value function grows at an additive rate of 2 from h H to h = If we do not consider the added noise, then the value function should at most grow 1 at each timestep because the reward is at most 1. For our clipping technique, if a clip triggered, there exists a timestep such that the added noise is more than 1, which is equivalent to small number of visits (cf. Definition 23 and Lemma 8). As our later analysis will show, the clipping only affects the lower-order term and will not compromise the long-term performance the algorithm. Finally, after computing the value function and clipping, SSR chooses the action of that maximizes Qr. (5% a) at each time step, h i.... H, throughout the episode.
Note that from a Bayesian perspective, when there is no clipping, in Algorithm 1, Qn, follows distribution
( a) V V4+1, ~ ~ (A%.... + (Ph.... VALLa) ((1,,++(P........
(ott (h, (h,
This resembles posterior sampling because when estimating some parameter 0" ~ N (0, 32) based on noisy observations 01...., On ~ NN(0, 32), the posterior distribution of 0r given {0, ) is O2, a+1) Although exact posterior sampling may not be possible in 0" (0.)%_1 N n+F E+
complex reinforcement learning settings, SSR, o (h, s, a) is chosen at scale ō (1//
and therefore can interpreted as doing approximate posterior sampling. Moreover, SSR can be viewed as variant of Randomized Least Square Value Iteration (RLSVI). The major differences are the clipping function and a single random seed used in each episode instead of different random seeds at different tuples (h, 8,8, a). We will discuss more about the choice of the random seed later in this section. We refer to [37] and [41] for more detailed discussion on the relationship among RLSVI, posterior sampling and randomized value function.
In the following paragraphs, we discuss in more details about the three major algorithmic innovations:
Single Random Seed in Each Episode. SSR is similar to the algorithms analyzed in [41] and [2]. The major difference is that in the algorithm we propose, the perturbations for all time steps h = 1,... H in an episode kt
single random seed 2n to generate
When using different random seeds in episode, the algorithm can be optimistic in some time step while being pessimistic in others. Then, the effects of the perturbations at different time steps will cancel with each other. As result, to ensure sufficient exploration, the magnitude of the perturbation has to large. This issue was also pointed out in [2. 1].
A large perturbation magnitude can increase the instability of the algorithm and worsen the algorithm's 's performance. When a single random seed is used, a small perturbation magnitude is enough to guarantee that the algorithm is optimistic with constant probability in any episode. We are able to show that using a single random seed can significantly increase the stability of the algorithm and therefore enjoy much smaller regret. Coincidentally, [48] also uses similar single randomization in bandit problems to build near-optimal randomized exploration algorithm and our work can be treated as its natural extension to RL problems.
5

---

Clipping, To obtain a tight regret bound, the estimated value function needs to be well bounded. In [41], no clipping is used and the estimated value function is at the order of ((H which results in a suboptimal regret bound. Generally there are two types of clipping methods. The first one is uncertainty-basses i.e. the value is clipped to H - h + 1 at timestep h whenever the uncertainty is large [52. 2]. However this type of clipping cannot maintain pessimism which is critical in our analysis. The other kind of clipping is value-based, mostly in UCB-type algorithms [23]. These algorithms truncate estimated value greater than a certain threshold, i... H h + 1 at time step h. The problem here is that the number of clippings cannot be bounded because if the true value function is close to H - h + at timestep h, the clipping will happen with some constant probability.
Our clipping method leverages both type of clipping methods in the existing literature. Though our clipping is based on the value function, we show that whenever the clip is triggered, the esti- mation error must be large, which implies that the uncertainty at that state is large. This clipping method inherits the desired properties from both uncertainty-be -based and value-based clipping, i.e. the optimism/pessimism is maintained and the number of clippings can be bounded.
Magnitude of Perturbation. A large magnitude of perturbation can encourage exploration, but at the same time increase instability. In our algorithm, the magnitudes are chosen as the smallest values so that the algorithm can be optimistic with constant probability. Since the value function can roughly
be bounded by O(H), a naive choice of the perturbation magnitude can be O (H/ s,, a)) In this way, by Hoeffddingss 's inequality, as long as the random Gaussian variable sampled & bigger than a constant, which happens with constant probability, the estimated value function will be optimistic. By similar reasoning, we can see that the estimated value function will also be pessimistic with constant probability.
To make the magnitude even smaller, inspired by [7] who showed one can use an (empirical) Bernstein's 's inequality to derive a sharp exploration bonus for UCB-based algorithms, we propose new choice of perturbation magnitude based on Bernstein's 's inequality. The Bernstein-base perturbation uses the empirical variance of the value function, which makes it smaller than the Hoeffiding-baser one mostly, but still maintains optimism with constant probability.
In our paper, we study both types of magnitudes. In particular, we show that the regret of SSR based on Bernstein's 's inequality matches the known lower bound & (HVSAT): Following are the two choices:
log (2HSAR2) nu (h, +1
H ny s,) +1'
to (h, a) = H
(5)
16V (pt haaaa V (4 log AkH)
Th (h, 8, a) =
65H log (2H5AR2)
log (2H5
(6)
ny (h, 8, a) +1
mag (h, 8, a) + ma (h, a) +
where subscript "Ho" represents that the perturbation is based on Hoeffding's 's inequality and "Be" represents Bernstein's 's inequality, correspondingly. Here, for proof convenience, h.s.a is defined by replacing the denominator in Pits.a by max {ne (h,, 8, a), 13. To clarify, when subscript "ty" is used, which stands for "type" as a placeholder for "Ho" "Be", means that there no need write two copies of expressions for Hoeffding- baasdd and Bernstein- based noises separately.
Practical Considerations. Here, we explain why randomized exploration is widely used in practice and why our algorithmic formulation practically has advantage over UCB-type algorithms. In ran- domized exploration, there are usually two important components: (1) the algorithm (e.g.. Algorithm 1) and (2) the noise magnitude (oty). In practice. the main advantage of randomized exploration lies in the algorithm component. The generalization from the tabular setting to the function approximation setting is straightforward: one can just add a random regularization term in the value estimation step. whose details can be found in [35]. On the other hand, the generalization of optimistic algorithms from the tabular setting to the function approximation setting is more non-trivial because it often requires an explicit construction of the confidence set. For the second component, although generaliz- ing our strategy of tuning noise magnitude to the real-world function approximation setting is indeed not straightforward, it is often set hyperr-aramedt parameter in practice.

---

4.2 Regret Analysis
We analyze the regret, defined in (1), of our algorithm SSR using both types of perturbations. Our main theorems are presented in Theorem I and 2. In particular, Theorem 2 shows SSR with Bernstein- based perturbation can achieve the regret that matches the known lower bound ? (HVS SAT up to logarithmic factors. We sketch the proof of Theorem 1 and Theorem 2 in Section 5. Theorem 1, If the Hoeffding- noise (5) is used, then for any MDP M = (H, A, P. s1)) with probability at least 1 5, Algorithm 1 satisfies
Reg(M, K, SSRH)) Sō (H (H! +
In particular, when T 2 â SH A), it holds that Reg(M, K, SSRHa) S S0 H (H
Theorem 2. If the Bernstein-type noise (6) is used, then when T 2 á S2 A), for any MDP M = -H, A, S1), with probability at least 1 - 8, Algorithm satisfies
Reg(M, K, B)) S Ō (HVSAT + H²
In particular, if we further have T 2 Ω (1H A),, it then holds that Reg(M, K, SSRBe) - δ (HVSAT).
We give a brief comparison between SSR and other related works. [41] shows that RLSVI, an algorithm similar to SSR, can achieve ò 22 (/AT VAT) regret in expectation over the randomness
of MDP and the algorithm. In [2], improved high probability regret bound Ō (H&SVAT) is proposed. which is the sharpest bound for randomized algorithms prior to this work. Our paper closes the gap between those previous bounds and the lower bound in tabular setting.
We also run numerical simulations to empirically compare SSR and RLSVI in the deep-sea environ- ment, which is commonly used as benchmark test algorithm's 's ability explore. The results show that SSR significantly outperforms RLSVI as predicted by our regret analysis. More details about our experiment can be found in Appendix J.
5 Proof Outline
In this section, we present an proof outline of Theorem and 2. Since their proofs follow the same framework, we will present unified outline and explain the individual steps particularly for each case when necessary. The details of complete proof are deferred to the appendix.
Notation For the ease of exposure, we will use simplified notations during this sketch. Specifically, let s,, and 2f, (h, st. a.).
5.1 Concentration and Optimisn/Pessimism
We start by introducing a set of MDPs Mfy as a confidence set such that the empirical MDP M belongs to it with high probability, meaning that we have good estimation of the true MDP. Specifically, with M' = =H,,S, A, P', R², 81), we define
My. = M' Vx = (h, 8, a) (R, - Ra) + (P-2 - Pay Vitz) S v (e)
where / /etin()) (x) = o (x) and / / (x) xo (x).
Define the event Ctty := ar E M }.
Then, by applying Hoeffding's inequality Bernstein's inequality, for both types of perturbation, it is possible to show that
P ((c)) = =EP(Nr Nir & M s
π
3
k=1
7

---

Since the value function is bounded in [0, H), this inequality tells us that the regret incurred by bad estimation is at most O (H). To be precise, it holds with high probability that
K i { (C (vi
Σ
(vi - viA) (5f) S (H)).
Then, to better control the estimated value function, we need it to be bounded, which requires us to clip it. Specifically, will use two crucial properties of our clipping method. First, if (8, a) 2 (), ((s,a) E S x A, then we have V., (s) Z (s), (s, a) I (s, V(s, E A, then we have Vn,((s) S (s)
Vs E S. Similarly if
In addition, we can prove that whenever clip triggered for sx we have nu (h, sh, att S as with Og ((H)). As result, is possible to show that the total regret incurred by clipping is at most Ô (H+SA)) which is lower-order term when T is sufficiently large. That is, let HH denote the event that there is no clipping during episode Then, it holds with high probability that?
K
Σ 1 [ct n (EML)) 1=
) (vi - v1TA)(t) (o s Ō (H*5²A))
(8)
As claimed before, because of the randomness in Gaussian noise, our algorithm SSR will encourage exploration and takes effect when there is no clipping and the estimation is not too bad. other words, it can be optimistic. However, also because of this randomness, its optimism only holds in probabilistic sense. In precise, it is possible to show that
(9) where the value of constant Cty depends on the type of noise we choose. Meanwhile, we can also prove very similar probabilistic pessimism, which means to have Vn,((s) Vgg(s) Yh [H] s with constant probability. The property of optimism and pessimism will help us upper bound the absolute value of (sf) - (s,( which will be discussed soon.
P (s) 2 (s), vh E [H] E 1 City) Ciy,
5.2 Regret Decomposition
Now, given equations (7) and (8), we can see that for each episode k. it only remains to bound ck n &oom } (Vi-Vi' (sf). Technically, the further defined the good event G& will help N make VA. better-behaved. Its precise definition will be given in the appendix. Therefore, it is sufficient to bound { (Vr - vitt) (sf), which means to have
{
K
Reg (M, K, SSR
1 (G&) (Vi' - VI Win
+ (10)
pessimism
estimation
To proceed, we need to define two auxiliary value functions VA, and V Kikk, which are obtained by virtually running policy n on some deliberately perturbed MDPs. In particular, they are designed such that VA.K S n, S Vn.k h.k holds under the good event GE-
Pessimism Term Here, as a technical novelty, we bound the pessimism term's absolute value. Meanwhile, different from [52] and [2], by applying both optimism and pessimism, we do not resort to an independent copy of the perturbed MDP to bound the pessimism term and give conceptually simpler analysis. In particulary, by defining C1 1/ min (Cho, CBe). is possible show that
(Vi ( + (Ti((s)) vallesh)) (11)
I1 { (* (s.)) ( Ci
The full proof is given in Appendix under Lemma 15.
Teechically,, this is not precisely how we bound the regret incurred by clipping, but it aligns better with the intuition. Full technical details can be found in Appendix.
8

---

Estimation Error Term The sum of pessimism term and estimation error term can be further bounded via the techniques of recursion used in [7]. However, we want emphasize the differ- ence that in their algorithm, the estimated value is optimistic with high probability, which makes (,,,(s))) (sf) always positive, Instead, since our optimism only holds with constant probability, we use absolute value keep the estimation error terms positive. As result, show that
I. Vi (of) + V... Vi (sf) + VTA Vi. (of)
Σ (Lot (17i) + Mi.k), (12)
where I. denotes some holy-logarithmic term and MA,s denotes some martingale difference sequence term at period h, episode k. The full proof is given in Appendix under Lemma 19,
5.3 Combining Different Terms
By combining equations (10), (11) and (12) and applying concentration inequalities MDP Ma,K.
it is possible to show that
Reg (M, K, SSR
Se 30'
(13)
k=1h=1
Then, final high-pun probabiiity regret bound can be obtained by summing each individual terms over k, h separately. It is well-known among literature that
K ΣΣ (2 +1 S (HSA). (14)
ΣΣ
nx <ō (VHSAT).
Recall the definition of tt in equation (5). By using these two inequalities, the bound in equation (13) can be made explicit if we use Hoeffding-tyy type noise. As a result, we have
Reg (M, K, SSR & Ō SSAS + (H
5.3.1 Bound on Sum of Variance
Analyses become more involved when Bernstein-type noise is used. Specifically, notice that in- equalities in (14) cannot directly be used to bound Σx, V Phk =f Vn+1.). Here, apply some
techniques developed in [7]. However, since the optimism only holds with constant probability, the details for specific terms are quite different.
For the ease of exposure, we will ignore all constants and define Vi.a - Vi
V (pt
Vnn =
x
pk xk. Vn..). Then, by using
inequality and equation (14), we can get
(9x) V ne(x+t)+ +1 (VPr..+ v Van S Ö 1 (Vh, + Vn,)) (15)
def
k
Here, note that Ena (xt)). Then, after some steps of algebra, is possible to show that
K H
ΣΣ
(9 (Vh++
+ VnN) & (HT+HHU
(When T 2 (H
US O (VHSA + H-U) s 5 (HVSAT + HH.VVV) (By using equation (15))
Now, we can see that th x $ δ (HVSAT) plugging this result back into equation (13),
satisfies this incquality. Finally, by
have
Reg [M, K, SSR s δ H HVSAT + H
which matches the known lower bound when T > 55 A).

---

Conclusion
We gave new algorithm with randomized exploration, SSR, for tabular MDP, which enjoys near-optimal Ö [HVSAT) regret bound in the hume-homogeneous model. Previously, near-optimal regret bounds can only be achieved by optimistic algorithms. Our result also highlights the importance of using single random seed for the entire episode and using the variance information in tuning the magnitude of noise (cf. Bernstein's 's inequality).
One important open problem is whether randomized exploration can a achieve horizon- regret bound in the -ongeeooogeeeous model where the transition is the same at different levels [53, 49, 55]. Another possible future direction is to consider whether the sub-optimal lower order terms Ô ( S2 A) can be further improved to relax the current requirement T' 2 9t (H1 A) for being near-optimal.
Acknowledgements
We sincerely thank Jinglin Chen and Chao Qin for pointing out mistakes in the initial draft of this paper. We are grateful for their careful reading and insightful discussion. This work was supported in part by NSF TRIPODS HIDMMS 2023166, NSF CCF 2007036, NSF IIS 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844.
References
[1] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017.
[2] Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for ran- domized least-squares value iteration. Thirty-fifth AAAI conference on artificial intelligence, 2021.
[3] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[4] Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. J. ACM, 64(5), September 2017.
[5] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. In Advances in Neural Information Processing Systems, pages 1184-1194 2017.
[6] Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. In Advances Neural Information Processing Systems, pages 1184-1194, 2017.
[7] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volene Volume 70, pages 263-272. JMLR. org, 2017.
[8] Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 45-42, AUAI Press, 2009.
[9] Ronen Brafman and Moshe Tennenholtz. R-max a general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3(0ct):213 March 2003.
[10] Sébastien Bubeck and Che- Yu Liu. Prior-free and prior-dependent regret bounds for thompson sampling. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-9. IEEE, 2014.
[11] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint
2018
10

---

[12] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang, Provably efficient exploration in policy optimization. arXiv preprint xrXi::19/2.0580,, 2019.
[13] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249-2222 2257, 2011.
[14] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed- lixed-horizon reinforce- ment learning. In Advances Neural Information Processing Systems, pages 2015.
[15] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 5717-5727, Red Hook, NY, USA, 2017. Curran Associates Inc.
[16] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1507-1516, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
[17] Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
[18] Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with ucb exploration is sample efficient for infinite-horizon mdp. arXiv preprint 1XXXv:1901.99) 2019.
[19] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Osband, Alex Graves, Volodymyr Mnih, Remi Munos, Demis Hassabis, et al. Noisy networks for exploration. In International Conference on Learning Representations, 2018
[20] Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Near optimal exploration-exploitatii in non-communicating markov decision processes. In Advances in Neural Information Processing Systems, pages 2994-3004, 2018.
[21] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1 116Ap)):1533-1600, 2010.
[22] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873, 2018.
[23] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388 2019.
[24] Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal thompson sampling. arXiv preprint vrXiv:2003.0180. 2020.
[25] Sham M Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
[26] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
[27] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, (9(2-3):209-232 2002.
[28] J Zico Kolter and Andrew Y Ng. Near-bayesian exploration in polynomial time, In Proceedings of the 26th annual international conference machine learning, pages 513-520, 2009.
[29] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22, 1985.
[30] Tor I Lattimore and Marcus Hutter. Pac bounds for discounted mdps. International Conference on Algorithmic Learning Theory, pages 320-334. Springer, 2012.

---

[31] Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[32] Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3744 2009.
[33] Pierre Menard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb mo- mentum q-learning: Correcting the bias without forgetting. arXiv preprint arXiv:2103.01312, 2021.
[34] Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. arXiv preprint arXiv:2007.01891, 2020.
[35] Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep rein- forcement learning. In Advances in Neural Information Processing Systems, pages 8617-8629, 2018.
[36] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[37] lan Osband, Daniel Russo, Zheng Wen, and Benjamin Van Roy. Deep exploration via random- ized value functions. arXiv preprint arXiv: 07608, 2017.
[38] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pages 2701-2710. JMLR. org, 2017.
[39] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. arXiv preprini arXiv: 1402.0400. 2014.
[40] Aldo Pacchiano, Philip Ball, Jack Parker-Holde Krzysztof Choromanski, and Stephen Roberts. On optimism in model-based reinforcement learning. arXiv preprint arXiv:2006. 1911, 2020.
[41] Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In Advances in Neural Information Processing Systems, pages 14433-14443, 20199
[42] Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, pages 1153-1162, 2019.
[43] Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model-free reinforcement learning. In Proceedings of the 23rd international conference Machine learning, pages 881 188-88. ACM, 2006.
[44] Alexander Strehl and Michael I. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(6):1309-1331 2008.
[45] István Szita and Csaba Szepesvári. Model-based reinforcement learning with nearly tight exploration complexity bounds. ICMI., 2010.
[46] Mohammad Sadegh Talebi and Odalric- Odalric-Ambrym Maillard. Variance-aware regret bounds for undiscounted reinforcement learning in mdps. arXiv preprini arXiv: 2018.
[47] Tian Tan, Zhihan Xiong, and Vikranth R Dwaracherla. Parameterized indexed value function for efficient exploration in reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5948-5955, 2020.
[48] Sharan Vaswani, Abbas Mehrabian, Audrey Durand, and Branislav Kveton. Old dog learns new tricks: Randomized ueb for bandit problems. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, pages 1988-1998, 2020.
[49] Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforce- ment learning more difficult than short horizon reinforcement learning? arXiv preprint 20Xiv:2005.00527,200 2020.
12

---

[50] Ziping Xu and Ambuj Tewari. Worst-case regret bound for perturbation based exploration in reinforcement learning. Ann Arbor, 1001:48109, 2019.
[51] Kunhe Yang, Lin F Yang. and Simon Du. Q-learning with logarithmic regret. arXiv preprint arXiv:2006.09118, 2020.
[52] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Statistics, pages 1954- 1964, 2020.
[53] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312, 2019.
[54] Zihan Zhang and Xiangyang Regret minimization for reinforcement learning by evaluating the optimal bias function. In Advances in Neural Information Processing Systems, pages 2823 2832, 2019.
[55] Zihan Zhang, Xiangyang Ji, and Simon S Du. reinforcement learning more difficult than ban- dits? near-optimal algorithm escaping the curse of horizon. arXiv preprint 2005:2000.13503, 2020.
[56] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantagg decomposition. arXiv preprint arXiv:2004. 10019, 2020.
[57] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. arXiv preprint 20X1v 2020.
13

---

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 describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(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 URL)? [No]
(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 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, or 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? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "ZmbnBhdkmj1", "reviewer": "Reviewer_EVm9", "summary": "This paper studies episodic RL in tabular MDPs in the regret minimization setting, and presents an algorithm, called SSR, which follows the principle of exploration via randomized value functions. The paper presents two variants of SSR that differ in the choice of the noise. The variant that generates noise sequences based on Bernstein’s inequality is shown to achieve a worst-case regret bound (with high probability) that matches the lower bound up to logarithmic factors. This regret bound improves the best known regret bounds for randomized exploration by a factor of $\\widetilde O(H\\sqrt{S})$. ", "questions": "See the weaknesses above. Also address minor comments if relevant.", "limitations": "There is no negative societal impact associated to this work. The most important limitations of the presented methods in the paper are adequately and clearly discussed in the paper.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies a classic but important problem in RL. Despite all the recent advances in the theoretical aspects of episodic RL, the studied setup is interesting in view of the empirical success of exploration via randomized value function and considering that the theoretical picture is not yet complete. The paper makes a good step in this direction and thus makes a nice addition to the literature on theoretical episodic RL. \n\nThe paper is written well and admits a good organization. The presentation of the various elements (model, algorithm, and results) is clear and precise. All these makes the paper a nice read. \n\nAmongst the technical and algorithmic novelties is the use of a single seed for randomization and the use of a new clipping strategy. The latter is shown to maintain both optimism and pessimism, which turns out to be crucial in achieving the improved regret bounds. \n\nSome weaknesses and questions:\n\n- The regret bound of the Bernstein-type variant in Theorem 2 is stated to hold when $T$ is larger than a (rather large) polynomial of $H$ and $S$, whereas this is not the case for the other variant. Could you elaborate further on this? And what can be said about regret for when $T$ is smaller than this threshold?\n\n- I would like to appreciate the authors to have included the lower order terms in the regret bounds and to have clarified the time after which the desired $\\sqrt{T}$-regime kicks in. Under both variants, the lower order terms scale as $H^4S^2A$, so that the desired $\\sqrt{T}$-regime kicks in after a rather large $T$ (albeit polynomial in $H$ and $S$). I may urge the authors to compare SSR against state-of-the-art in terms of such critical values of $T$ as well.\n\n- The statement ”UCB-type algorithms … suffer from difficult implementation ...” is not entirely correct. While this statement could be valid for model-based UCB-type algorithms, model-free ones do not require complicated planning procedures (such as EVI in UCRL2 or alike). Rather, they just take actions greedily with a Q-function, which is cheaply implementable. I may ask the authors to further elaborate on this, and if necessary, make the statement more precise. \n\n- The paper nicely closes the gap between the regret lower and upper bounds, implying that for large enough time horizons, both UCB-type and randomized approaches could achieve the worst-case optimal regret bound. Then the following question naturally arises: In the considered episodic setting, which approach is empirically superior? Unfortunately, the paper does not provide any experimental result, so it remains inconclusive as to whether any of the two approaches provide a superior empirical performance. \n\nMinor comments:\n\nIn several places, it is stated that optimism and pessimism is guaranteed to hold with constant probability. In technical sections (e.g., Section 4 and later), it might be a good idea to explicitly state such a constant probability to enrich the discussion. \n\nSome typos: \n\nLine 89: Algorithms …. has been ==> … have been \n\nLine 130 (and elsewhere): in tabular setting ==> in the tabular setting\n\nLine 158: $h=1, \\ldots H$ ==> $h=1, \\ldots, H$\n\nLine 162: noisy observation ==> noisy observations \n\nLine 178: has to large ==> has to be large\n\nLine 188: in suboptimal regret bound ==> in a suboptimal regret bound\n\nLine 192: number of clipping ==> … clippings \n\nLine 194: is closed to ==> is close to \n\nLine 198: uncertain-based ==> uncertainty-based\n\nLine 212: … still maintain ==> still maintains\n\nLine 219: Full stop missing\n\nLine 221: noise ==> noises \n\n------ Post Rebuttal ------\n\nI would like to thank the authors for the rebuttal. My questions and concerns are adequately addressed. As a result, I maintain my score of 7, but with an increased confidence of 4. \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": "K0e7uoBMN7e", "reviewer": "Reviewer_bZZ8", "summary": "The paper studies a finite state-action MDP setting with time inhomogeneous transitions and costs. The authors then propose a single seed randomization algorithm that . Regret analysis then purports to achieve $\\tilde{O}(H\\sqrt{SAT})$ bound on regret in the finite MDP setting using randomized algorithms (as opposed to variants of the UCB family for MDPs).\n", "questions": "1. Steps are missing in Algorithm 1. \n    - Trajectory generation must be mentioned somewhere between Steps 5 and 6.\n    - Please point to equations 5 and 6 to show how $\\sigma^k_{ty}$ is generated. I was searching around for an expression for $\\sigma^k_{ty}$ for quite some time.\n\n2. In line 225, you claim that \"the main advantage of randomized exploration lies in the algorithm component.\" Yet, the results show that it is the other point, i,e, the Bernstein noise that really does the $H^{1.5}$ to $H$ reduction. In light of this, how would you justify your claim in Line 225?\n\n3. Can you say anything about expected regret?\n     -  I cannot find any numerical results in the paper. In the absence of simulations, how does one compare SSR empirically with other randomized (and UCB-based) algorithms? Regret analysis only provides upper bounds which could be rather loose.\n    - Moreover, simulations could also shed light on the matter of **expected regret**. The present analysis says nothing about what happens on the complement, i.e., the subset of sample paths with measure $\\approx \\delta.$", "limitations": "The work is theoretical and I cannot find any potential negative societal impact.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper addresses an important lacuna in finite MDP Reinforcement Learning. UCB algorithms have been known to show $\\tilde{O}(H\\sqrt{SAT})$ regret performance for quite some time now and an extension to Thompson Sampling-type algorithms is quite necessary.\n\nWeaknesses:\n1. I'm not convinced the setting of the problem is entirely natural. Essentially, the model is one where the agent interacts with the environment over H trajectories, and the exact same sequence of transition matrices and reward functions materializes every time.\n- Using a model just because it has been previously used does _not_ constitute sufficient justification.\n\n2. The algorithm and its analysis are lacking in novelty, in my opinion. \n- The concept of clipping and are introduced in [2, Algorithm 1] (see line 15) \n- With regards to $\\sigma^k_{ty}$ in Step 6: Moving from Hoeffding to Bernstein type randomization is rather dated and can be found in  UCB-type algorithms previously proposed in the literature.\n- It appears to me that using a single seed for the trajectory is the only truly novel idea.", "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": "HJniB9FQwtJ", "reviewer": "Reviewer_WUa3", "summary": "Authors propose novel algorithm for reinforcement learning with randomized exploration. Algorithm achieves minimax optimal regret bound up to poly-logarithmic factors, and it is the first such result for RL algorithms based not on the principle of Optimism in the face of Uncertainty. The most crucial algorithmic features that allow authors to achieve their result are\n1) use a single Gaussian noise up to scaling for all transitions;\n2) specific Bernstein-shaped magnitude of noise;\n3) novel clipping procedure that was used at the first time for algorithms with randomized exploration.", "questions": "- The main suggestion was listed in the section on Strength and Weaknesses: it would be very nice to have an additional empirical comparison between SSR algorithm and other baselines such as UCBVI, classical RLSVI, and PSRL.\n- Additionally there are several small issues with the text in the appendix:\n    - In the formula after line 577 $\\alpha_k$ was used without definition except the table of notations;\n    - In Lemma 10 it could be great to make $z$ a parameter of function $f$;\n    - In the beginning of the section of regret decomposition there was a lot of added subscript $k$ into value function that corresponds to $V^\\pi$.", "limitations": "Authors addressed all the limitations of their paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The first algorithm based on randomized exploration that achieves minimax optimal regret; It vastly extends the theoretical perspectives of randomized exploration.\n\n2) Novel proof technique that allows to control pessimism error for randomized algorithms;\n\nWeaknesses:\n\n1) Lack of empirical study. Authors claimed that use of single seed can significantly increase the stability of the algorithm, and it would be very interesting to observe this effect practically on tabular environment with non-trivial exploration problem (N-rooms for example).", "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": "68owXVCI6hv", "reviewer": "Reviewer_GzaW", "summary": "The paper considers the problem of regret minimization in RL using randomized algorithms. For this, the authors provide a single-seed-based algorithm that is able to obtain $\\tilde{O}(H\\sqrt{SAT})$ regret bound using Bernstein concentration-based variance scaling.", "questions": "How does the SSR algorithm compare against the PSRL algorithm by [5,6]?", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The result of the paper and the simplicity of the algorithm using a single seed in an episode is the biggest result. Further, providing an analysis based on absolute value analysis of the difference between the optimal policy of the true problem setup and of the optimal policy of the sampled value function is interesting and can be used in many future works working on sampled MDPs.\n\nWeakness: \n\n1. The additive term of $O(H^4S^2A)$ is quite large. \n2. The paper does not addresses the works in the area of Thompson Sampling and worst-case regret bounds for posterior sampling based algorithms. ", "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