A Vector Bernstein Inequality for Self-Normalized Martingales
Authors: Ingvar Ziemann
Venue: Accepted by TMLR ()

Abstract: We prove a Bernstein inequality for vector-valued self-normalized martingales. We first give an alternative perspective of the corresponding sub-Gaussian bound due to Abbasi-Yadkori et al. via a PAC-Bayesian argument with Gaussian priors. By instantiating this argument to priors drawn uniformly over well-chosen ellipsoids, we obtain a Bernstein bound.

Published in Transactions on Machine Learning Research (03/2025)
A Vector Bernstein Inequality for Self-Normalized Martingales
Ingvar Ziemann
ingoarsOseas upenon. edu
University of Pennsyloania
Reviewed on OpenReview: https://openreveee por/forum? id 42=42JyrYYbBu
Abstract
We prove a Bernstein inequality for vector-valued self-normalized martingales. We first give an alternative perspective of the corresponding sub-Gaussiar bound due to Abbasi- Yadkori et al. (2011) via PAC-Bayesian argument with Gaussian priors. By instantiating This argument to priors drawn uniformly over well-chosen ellipsoids, we oblain a Bernstein bound.
1 Tail Bounds for Self-Normalized Martingales
Deviation incqualities for sclf-normalized martingales play key role in obtaining guarantees for lincar regression in interactive and sequential docision-makingg tasks, such as learning an autoregression or regret minimization in linear bandits. The most prevalent version of such inequality currently in is due to Abbasi-Yadkon et al. (2011) and rests the method of pseudo-maxiiization popularized by Peña et al.) (2009), dating back to Robbins & Siegmund (1970). Comparing their result to the central limit theorem, their bound is nearly optimal but depends on the sub-Gaussian variance proxy instead of the actual variance. technique through the lens of the PAC-Bayesian inequality. The present approach simplifies classical pseudo-maximizzatin by relegating the complexity of evaluating exponential integrals against the smoothing distribution the computation of a generic Kullback-Liebler divergence term. This allows to generalize the argument of Abbasi- Yackori al. 2011 but without access to globally defined moment generating function bounds.
In this note, we overcome this issuc by casting the pscudo-maximizatte
Let us now proceed by describing the setting of our result and that of Abbasi Yadkori et al. 20111. Fix a filtration Fooo and two square-integrable procosscs: X X1:00 taking values in R and W1:00 taking values R. For each E N, let X1.r be adapted to Fu:r-1 and WIT to F1:r with E[Wa = for every h E N. For E N, we define:
S
Σ W.Xx and V1 A Σ X
kml
and are interested in bounds on the random walk ST in the random Mahalanobis norm || ( I|
(1 for some fixed positive semidefinite matrix I' > This called a self-normalized martingale. Under the assumption that W₁ is Fondiionnt obub Sub---su--Gansse Gabssinn for each lc [ Abbasi- Yadkori
et al. 2011 show that for every stopping time (E Fo:co) and with probability 1 8-8:
| 1l LuD [log (dee(VV, +1)) log(1/0)) det(T)
(2)
Their approach rests elegant application of the pseulo-maxiinzzation technique developed by Peña et al. 2009), dating back to Robbins & Siegmund (1970). While elegant, the result of Abbasi- Yadkori et al. 2011 has one shortcoming as compared to classical asymplotics: the linear dependence on the conditional variance proxy o2 as opposed to the conditional variance, o2 - Sup(E[W2(FF-.) a.s., & E T}. The
22 m
'E (AW)) [e-1] < exp
Vk N.

---

Published in Transactions on Machine Learning Research (03/2025)
traditional fix to this in the literature concentration inequalities is to invoke Bernstein-type bound on the moment generating function (MGF) of the Wa instead of a Hoeffding type of bound (see e.g. Freedman 1975; de la Pena 1999/. Unfortumately, directly combining a Bernstein MGF bound with the pseudo- maximization tochnique does not lead to analytically tractable upper bounds as requires the evaluation an exponential integral over a bounded domain (an ellipsoid). Moreover, previous altempts at establishing Bernstein bounds (via methods orthogonal to aseudo-maximization for vector-valued self-normalized martingales suffer from extraneous logarithmic dependencies and have significantly looser constants (see e.g. Zhao et al., 2023
In this note, we provide alternative perspective on the proof of 12 where, instead of computing the exponential integral directly, we invoke the variational charactorization of Kullback-Liebler divergence via the PAC-Bayesian lemua (Shawe-Tayll & Williamson 1997: McAllester 1998) to relegate this difficulty to the calculation of said divergence. Beyond Gaussian priors, this turns out to be significantly simpler than the evaluation of an exponential integral. It allows us to modularize the proof strategy of Abbasii- Yadkori et al.) (2011) and replace their Gaussian prior with uniform ellipsoidal priors that are suitable in combination with exponential inequalities that only hold for restricted domain (contrast this with Hoeffding MGF bounds being valid for all X).
The rest of this note is organized as follows. We state our main result immediately below and then proceed to discuss its consequences. Tts proof is given in Section 3.2 Preliminaries relating to our application of the lemma are given in Section 3 where we also provide a proof of (2 as a warm-up. Auxiliary lemmata, including the PAC-Bayesian lemma, are proven in Section
2
The Result
To apply a Bernstein MGF bound, we will require some additional boundedness assumptions. Namely, we posit that:
W S Bw and X Bx.
Vk: E
for positive scalar Bw and a positive definite matrix Bx Our main result can now be stated: Theorem 1. Fix V (0, 1), stopping time T with respect to Fo positive semidefinite matriv I' 0, a posilive definile matrix V and assume that (3) holds. Define
A Ve(l + +) 1V, - vo.
v
Then as long as + e(1 V 2 (1+1)E-
we have that with probability at least 1 - 5; (( (d =
a1+
1
det(VV, (12) logg(11))
|| 1
x
x -
log
(4)
1 2a
1-E
det(V)
Remarks on Theorem 1
1.
The bound gives a refined confidence ellipsoid for least squares estimation with martingale difference noise in the model Y2- = (0_, + We up a stopping time т. An advantage over the result of Abbasi Yadkori et al. (2011) that the term o is always smaller than da appearing in (2). Moreover, even though both bounds assume oracle access to the variance (proxy), second order statistic such as o is more amenable to be directly estimated from data.
2. When I' = 0, requiring a = in Theorem can be thought as a burn-in requirement, restricting the Bernstein incquality to cases in which the corresponding least squares error is sufficiently small. Typically, once the sample size is large enough as || the norm-squared error of the least squares estimator in the model Y₁- = (6., Xx) + Wi up to time т. When S, is not too large, the variance proxy 2 in can thus be replaced by the variance term o% with just a little overhead in e.
For P "'
B (corresponding instead ridge regression) one may choose V I and use 2 to control at the cost of an inflated failure probability (6 to 25).
2

---

Published in Transactions on Machine Learning Research (03/2025)
4. Together, and control the sharpness of the multiplicative constants of the bound. In the large sample regime, when || v is small, these can often both be allowed to tend to 0.
5. The bound can be put in more convenient form by making use of either of the two numerical inequalities (1 + 20) a)² S + a²) (1+ a))
6. Using Theorem 1 instead of the result in Abbasi- Yadkori et al. (2011) sharpens existing bounds for least squares estimators with martingale difference noise, allowing one to achieve optimal dependence in o See e.g. the proof structure laid out in Ziemann et al. (2023 Section 1.2).
7. These improvements also potentially extend to refining linear bandit analyses, previously motivating the results in Abbasi-Yadkori et al. [2011) and Zhao et al. 2023
3 PAC-Bayesian Bounds
Let p and be two probability measures supported on set A Rd Recall that dKL T)) - SA log [0, +o] is the Kullback-Leibler divergence between P and Our analysis in the sequel rests the well- known PAC-Bayesian lemma, stated below.
de
dp E
de
Lemma 1 (PAC-Bayesial deviation bound). Let be a subset of R and Z(A), X E A, be a family of real- valued random variables. Assume that Elexp [()) S for every XE A. Lel x be probability distribution on A. Then for all (0,
yp: / ((A)dp(A) dKL(p. () +u 2 -1-
(5)
where p spons all probability measures A.
We will instantiate the PAC-Baycsian lemma with Z(A) as the quadratic form (and with = +)
= (A, IIAIR -
- - -,
(6)
To account for the fact that the Mahalanobis norm appearing in (2) includes additive factor I, let us also take note of the following identity, which can be obtained by completing the square in 6
|| || s, 1|Soll 1 (V, + +)) + IAI.
(7)
In particular, we seek to bound the RHS of 6 (or 7 but will use the LHS to establish an exponential inequality. In the two sections that follow we first show how to recover the results of Abbasi- Yadkori et al. (2011) featuring the variance proxy 2abb and then proceed to generalize these to variance sensitive Bernstein bounds depending on oz in the leading order.
3.1 Warm-up: Sub-Gauss Gaussian Deviation Bounds
Before prove our main result, let us explain how version of the result of Abbasi Yadkori et al. (2011) can be established via Lemma [ This will inform the proof strategy of our result by essentially replacing Gaussians with a certain covariance ellipsoid with uniform distributions over the same ellipsoid. We prove the result for 2 = 1 and note that. the general case follows by rescaling.
By making use of the identity nential inequality required for Lemma I Namely, the tower rule and the conditional sub- Gaussianity of (We,k k 2 1} implies that Eexp (A, ST = & 1 for all X Rd and T N. Hence, may pick
easy to see that the right hand side of satisfics the expo-
3

---

Published in Transactions on Machine Learning Research (03/2025)
N (T)++))-ss Ep) in Lemma
We have:
1 / [11501iv 1i 112 (Vr 12 Sr 11 + [1111]] dp(A)
1 - + (= 2 -trnnv---rr((V----
=
1
(r())))))) ||5 -
(8)
Moreover, if we now set N(O, 2.,) we have that:
(V++T) dRI T) 2 |r(E, 1) [| -gr (V++T)- log det 2ix
(9)
det 2p
We point out that there is an asymmetry between Dn and Σ, at this point. The first allowed to depend on the processes ST, V but the latter is not. Applying Lemma to the process (6) yields that with probability at least 1 - -e
|| liv - tr(V> 2
|| [|5r
$ tr(= E, I) + || 1x, + log det En det 2p u. (10)
Equivalently:
|| [Srl((2 +
||ST ||l 1|S (V++r) -|| 1 (V
< <Ir(E= VT 1) + log det 2i
+ 2u. (11)
det Exp
Hence makes sense to choose Mip (VT+1))* and Exx 1--1 giving:
|| S log det(VT + +1) det
2u
(12)
which is identical to the result of Abbasi- Yadkori al. (2011 be addressed see below).
(modulo the stopping time, which can easily
Remark 3.1. By directly applying this proof strategy to one may also obtain the following deviation bound with probability at least e=:
de((Vz) 2u.
|| l ||ST 1|ST "r
& log det(T)
(13)
3.2 Variance Sensitive Deviation Bounds: Proof of Theorem
The use of Gaussian distributions in the self-normalized martingale bound is very convenient. it admits closed form KL expressions. However, their use hinges on the fact that an exponential inequality holds throughout Rdd We now show how to obtain a similar bound using distributions with compact support. In the sequel, we assume that o (1 - to? = and note that the general result can be recovered by rescaling S,.
Let consider two ellipsoidal distributions. We construct them follows. Fix two positive definito matrices Σn and Σp to be determined momentarily and measurable weight factor E 00). First, let n be uniform over the ellipsoid centered at zero and with shape Ex, i.e., uniform over {x E Rd : - S 1). Second, let be uniform over the ellipsoid with center LL, + +1) and shape Σ, Note that we must choose such that Tta (V, -)- + for Rdd x: - 1} for Rdd x: -I & 1}. Momentarily

---

Published in Transactions on Machine Learning Research (03/2025)
leaving this point aside, it is easy to see that the event that the second ellipsoid is contained in the first, the KL, divergence between these two distributions is the logarithmic volume ratio (Lemma
1 det Σn
Ellipsoid C π
Ellipsoid
log dKL(p, x) 2 det 2ip
(14)
Moreover, using Lemma on the same event we have that
1 2 / ||. (15-lli,+t)--- +r)- π| - (V, + + + [AIR do(A)
= 1+ 20
St
11 (V, +r)-1 d+2 1r(V)2p) + (1 + a)
|S
(15)
+ a1)
In other words, combined with by the exponential inequality in Lemma 2 yields that with probability 1
2 0, the PAC-Bayesian bound in Lemma
justified
+ 2a
det E,
(1 + a)² ||, (i) 5 2u + d+2 tr(V;2pp) + log det 2p
(16)
In particular, we may choose 2p = (d+ + 2V +1)- and En = e ( 2) to obtain:
< 2u + log det(V, +1) (1 + a)2 || 1|5-1iiv+
1 1 2a
(17)
det(V)
We note that 16 17 contingent on our choice of a. First, note that with our choice of priors, the use of Lemma 2 requires the additional constraint V > 8 ---e-- + 2) B.. To conclude the proof it remains to verify that a good choice of a can be made. The required event occurs precisely when
only hold when the event {o Ellipsoid C Ellipsoid] occurs, which in itself is
1 (V, + + f : (V + r)x s d 23 f x Jvx (d+ 2)}.
(18)
1+ a
rT - r (1 + ee it suffices
2 Vd+2 1 [ (d+) 1+v
+
(19)
1+
To see this, let y 1 (V, + +-)'ss and note that we must show that (y + (1( S ( 2) for every x E Rd satisfying x² =T(V, + l)x S 2 Now we have that for every 1 > 0, using Young's inequality and optimizing the weight below:
(0+2) (1+ p) + (1+ Vy
(1 + ()( +
+ (1 + 4 1
3ee 6 +) - + +T))
c(1 + v)2
(20)
vd+2
c(1 + v12y
(ve VyTVy
#=
d+2
Moreover, one can verify that the above inequality holds with a Ve(1 ve(1+v) 1) (lvv +r) +V()+ +h V
vvd+2
0, so that our priors are indeed well defined for this choice. Hence, under the imposed constraints on V,E and y we have thus obtained that
1 1+ 2a
S 1p (V, +ry S 2u + log det(V, +I)
(21)
(1 + 1)
dot(V)
This finishes the proof.
5

---

Published in Transactions on Machine Learning Research (03/2025)
4 Auxiliary Results
Lemma 2. Impose
3
fit a stopping time T with respect to Fo:00 and E E (0, 1). We have that
ovrr Cear:
Eexp (A.
(22)
2
for every E Id satisfying |A B3 By
E² and where oarr
(1 (1-67 -1- var.
Proof. Applying Bernstein's moment inequality conditionally on Fk-1 yields that
xx 2 2(1 - 1(A, Xx) (B))
o
Es Ex-1 le
exx
(23)
as long as A X Xx) Bw Since X 3 B3 this holds deterministically as long
| B3 < 1. In particular, we fix (0, and impose
|AI Bq, se² find that
||l X X 2(1-E)
Ex- Le-LlelA.xwWe S exp
(24)
Applying the tower property repeatedly, thus follows that with o (1 - -1-- we have that
Eexp (A, (1) ovar.e IA
S
(25)
2
for every I and for every À satisfying ||Al By 5
To prove the result for I a stopping time, define the (by the calculations above) nonnegative supermartin- It follows by standard optional stopping arguments and Faton's Lemma that M, lim inf MrAT also is nonnegative supermartingale. In particular EM, as per requirement.
gale Me A exp (A, St) IlAl
Lemma 3. Fix E Raxd, 0 and let U be uniformly distributed over {x Rd T x < 1). Then
EUUT 242 E.
Proof. Since U = VY where Y is uniform over I x S it suffices to prove the result for Y. By symmetry we must have EYYT- = ala for some a > 0. Morcover, it is casy to see that tr EYYT d+2 Hence = (d + 2)-1 and the result is established.
Lemma 4. Fix Ex, Ep E Rdxd with Ex, Ep > 0. Let a and be uniform distributions over Ex {x e 13 and Epp & fo Rx E-1o S 1) respectively. Tf E.p E Fez have that (p,(p,
det Dx 2 log det de
Proof. We have that
dkL(p. / log p(x)
dp(x))
T(x)
/ log det v Exx
dp(x)
(volume ratio)
(26)
Ep del EEp
det VDn / dp(x) log det v En
(J E
dp(w) do(s)=1 =1
log det VIp E,
det /20
per requirement.

---

Published in Transactions on Machine Learning Research (03/2025)
Proof of Lemma
7 By integrating the inequality Elexp ( 1 with respect to and Fubini:
[ exp exp ((A)d((A))
E
s
(27)
We now change mcasure using the variational characterization of the relative relative entropy functional Donsker & Varadhan 1975), which reads:
{ (())dp(A) - dKL (k)(
log (X)( = sup P
(28)
where the supremum spans over all probability measures over A. Hence
((2)dp(A) - do m) }} S1. expsup (
(29)
The result follows by a Chernoff bound applied to {sup, {Ja Z(A)dp(A) - (p, ])} - u}.
Acknowledgments
The author acknowledges support by a Swedish Research Council international postdoe grant and thanks Bruce Lee for several stimulating discussions and Alberto Metelli for pointing a miscalculation in an carlier version of the manuscript.
References
Yasin Abbasi-Yadkoni Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural informalion processing systems, 24, 2011.
Victor de la Pena. A general class of exponential incqualitics for martingales and ratios. The Annals of Probabilily, (7(1):537-564 1999.
Monroe D Donsker and SR Srinivasa. Varadhan. Asymptotic evaluation of certain markov process expecta- tions for large time, i. Communications on Pure and Applied Mathematics, 28(1):1 47, 1975.
David A Freedman. On tail probabilities for martingales. the Annals of Probabilily, pp- 100- 118, 1975.
David A McAllester. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pp. 230-234, 1998.
Victor H Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical
Applications. Springer, 2009.
Herbert Robbins and David Siegmund. Boundary crossing probabilities for the wiener process and sample sums. The Annals of Mathematical Statistics, pp. 1410-1429, 1970.
John Shawe- Shawe-Taylor and Robert C Williamson. A pac analysis of a bayesian estimator. Proceedings of the tenth annual conference on Computational learning theory, pp. 2-9, 1997.
Heyang Zhao, Jiafan Hc, Dongruo Zhon, Tong Zhang, and Quanquan Gu. Varianco-dependent regret bounds for linear bandits and reinforcement learning: Adaptivily and computational elficiency. In The Thirly Sizth Annual Conference on Learning Theory, pp. 4977-5020, PMLR, 2023.
Ingvar Ziemann, Anastasios Tsiamis, Bruce Lee, Yassir Jedra, Nikolai Matni, and George J Pappas. A Autorial on the non-asymptotic theory of system identification. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 8921 8939. IEEE, 2023.


Reviews:
[{"review_id": "MldABxCkfx", "reviewer": "Reviewer_5zFA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors are mathematically competent and the mathematical narrative is neat. \n\nOn the other hand, this is a probability paper and definitely it does not fit TMLR. The motivations are definitely weak, and I foresee no applications of the findings exposed here, except for a loose comment on ridge regression.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is a technical paper where the authors prove a Bernstein type inequality for vector-valued random variables.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "I suggest to send the paper to an applied probability journal. However, the mathematical level is definitely not up to the top ones - I would recommend the Journal of Applied Probability as a good venue for this paper.", "broader_impact_concerns": "See my previous comment. I am strongly recommending a clear cut rejection.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "66GkqP9390", "reviewer": "Reviewer_4FTh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The main result is a nice theoretical advance for the study of concentration inequalities which are broadly applied.\n- The paper is generally well-written and well-structured.\n\nWeaknesses:\n- The paper would benefit from additional examples or concrete applications to illustrate the impact of the new bound.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper establishes a new Bernstein inequality for vector-valued self-normalized martingales, providing a concentration bound that depends on the variance rather than a uniform bound. The proof is based on a PAC–Bayesian argument with Gaussian priors, which also yields a new proof of a sub-Gaussian bound by Abbasi-Yadkori et al. This approach appears to be novel.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Provide additional examples or applications to illustrate how the new Bernstein inequality can be applied in concrete settings.\n\nLemma 1 is not clearly stated; in the expression $\\mathbf E[\\exp Z(\\lambda)] \\le 1$ it should be specified that $\\lambda$ is drawn from $\\pi$.\n\nIn Theorem 1, \"we that\" is a typo.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hgFUglT8WT", "reviewer": "Reviewer_gDu1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n\n1/ The content is relatively self-contained. I like that the authors present their strategy.\n\n2/ The result is concise / crisp.\n\n3/ The argument of the authors that their bound will find applications is plausible.\n    The authors chose to not directly illustrate this claim directly (e.g. for bandit problems), but I think it is not necessary.\n\n* Weaknesses:\n\n1/ Could consider a few additional steps in the derivations to help the reader.\n\n2/ I think the reader would also appreciate a few more references for some of the tools and claims being made.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors put forward a new technique to prove deviations inequalities for so-called self-normalized martingales.\nThe novelty is that the proposed technique relies on the PAC-Bayesian lemma.\n\n1/ The authors first demonstrate that their technique is able to recover a state-of-the-art bound from Abbasi-Yadkori (2011).\nThe above-mentioned bounds relies on an assumption: a bound on the sub-Gaussian norm of the process (conditioned on the past).\n\n2/ The authors then propose an improvement over the previous known result by obtaining an alternative bound where a \nbound on the sub-Gaussian norm is replaced with the conditional variance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The changes I propose are only minor and are as follows:\n\n1/ Since the paper is quite short, I would suggest that the authors take this opportunity to add a few more intermediary steps in their proofs (e.g. how to obtain the identity at (7)).\n\n2/ Perhaps review a bit the structure of the paper. \n    There currently is a single sub-section in Section 1.\n\n3/ Add a few more references:\n\na) I appreciate that the authors included a short derivation of the PAC-Bayesian lemma at the end of the work. \nPerhaps they can include a reference to most well-cited usages of this lemma in the literature.\nAlso mention after stating the lemma that you will offer a short proof at the end of the script.\n\nb) On page 1: \"The traditional fix in the literature\", please add a few references where this analysis is carried out.\n\n4/ On p4., Section 2.2, forth line. Was  $\\sigma^2_{var,\\varepsilon}$ defined anywhere before equation (22)?\n\n5/ In Remarks on Theorem 1, 3. When $\\nu \\to 0$, don't you have that $\\alpha \\to \\infty$, and so does your bound? What do I miss?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The TMLR acceptance criteria are that:

- (Claims and evidence) All claims in the paper are supported by accurate and convincing evidence;
- (Audience) And that *some* part of the community would be interested in the results.

Reviewers all agree that the result is rigorously proven, and they enjoyed reading through the discussion of the proof strategy prior to seeing the calculations.
Thus the paper clearly satisfies (Claims and evidence).

As for audience, while one of the reviewers has some concerns about the significance, impact and scope of the result, the other two reviewers think that the current results are already of interest to *some* people. I also agree that a new concentration bound, with new proof technique, is sufficient to pass the (Audience) criterion.

I recommend acceptance of this paper to TMLR.
Decision: Accept (poster)