We apologize for any confusion regarding the appendix section. We included it in the supplementary material - after unzipping the file, there should be a folder containing a file named “appendix.pdf” and a folder named “code”. The appendix may be found in the “appendix.pdf” file. These files are showing in our system as having been uploaded and when we download them ourselves, they appear as we expect, but let us know if there is an issue with accessing our appendix and we can try to fix it. We believe that the supplementary material was accessible to at least some of the other reviewers, as we have received comments from other reviewers regarding our proofs (which appear in the appendix).

We briefly discuss in Appendix F reasons why our proof technique does not extend to the setting of general parametric models; please let us know if our discussion in Appendix F fails to clarify the reason that our proof technique does not generalize. We apologize if this was not accessible for you when you reviewed our paper.

Thank you for catching this issue in Question 1! We should have written it differently, and we will be sure to clarify in our revision what we meant to say: “First, Lai and Wei showed that condition (i) of Theorem 1 is nearly necessary for MLE consistency. In particular, if condition (i) of Theorem 1 is removed, the statement becomes false.”

Thank you for pointing out the formatting mistake on line 92 - it will be corrected.

We have spent considerable effort thinking of ways to extend our results to more general parametric models. We discuss in Appendix F reasons why our proof technique does not extend to the setting of general parametric models. Briefly, the main reason is that in general parametric models, we require an accurate second-order Taylor expansion of the log likelihood, but the unbounded condition numbers of the Fisher information matrix make it difficult to give a sufficiently strong error bound (even with the assumption of differentiability in quadratic mean). Please let us know if our discussion in Appendix F fails to clarify the reason that our proof technique does not generalize. Also, we’ll be sure to explicitly state the goal of generalizing to parametric models that are differentiable in quadratic mean, as we currently do not mention q.m.d. in Appendix F (though this class of models was exactly what we had in mind in our attempts to generalize).

We compared our results with previous BvM results in adaptively collected data in the second paragraph of our “Background” section. Prior results assume that the ratio of the maximum and minimum eigenvalues of the Fisher information matrix are bounded, and in fact most assume the stronger condition that there exists some consistent norming rate $\delta_n \to 0$ where $\delta_n I_n$ converges in probability to some limiting Fisher information $I$. The results established by [2] also make this assumption where this norming rate is $1/n$, as the posterior distribution is shown to be asymptotically normal with variance $V_0/n$ for some fixed $V_0$. The assumption of a bounded condition number is not satisfied by optimal bandit algorithms as discussed in section 2 of our paper, and therefore both our theorem statement and proof technique do not require this assumption. To our knowledge, our result is the first non-i.i.d. BvM result to accomplish this. For the sake of completeness, we will add [2] to our block of citations on line 82. The result given in [1] provides an asymptotic error bound on the BvM distance, providing a more quantitative analysis of the convergence rate, similar to other prior works such as [3] which gives a nonasymptotic error bound. Their argument, like ours, requires truncating the posterior distribution, which they argue by proving bounds on the observed likelihood and empirical Fisher information. However, their argument relies critically on Doeblin’s condition which guarantees a fixed rate of convergence of the Markov chain to a stationary distribution, so it is difficult to generalize their result to non-Markovian settings such as bandits.

[3] Lee, Jeyong, Junhyeok Choi, and Minwoo Chae. "Online Bernstein-von Mises theorem." arXiv preprint arXiv:2504.05661 (2025).

Clarity:

We chose to use the term “uncertainty quantification” in the paper because we wanted to include a variety of different use cases, not just constructing confidence/credible intervals (although these are what our empirical evaluations focus on). For instance, frequentist asymptotic normality is often used for forms of UQ other than confidence interval construction such as (multiple) hypothesis testing or prediction intervals (i.e., a high probability region for the response given a new test X). In the Bayesian paradigm, posterior distributions (and approximations thereof) are also often used for hypothesis testing and constructing posterior predictive intervals. To clarify our terminology, we will add the sentence “We will use the term frequentist (resp. Bayesian) UQ generically to refer to any of the many forms of frequentist (resp. Bayesian) statistical inference such as hypothesis tests, confidence intervals, or prediction intervals (resp. such as Bayesian hypothesis tests, credible intervals, or posterior predictive intervals).” to the introduction of the paper. We would prefer not to directly replace the phrase “UQ” as suggested, as that would restrict the use cases to frequentist confidence intervals and Bayesian credible intervals.

We will add precise definitions of “Wald-type” and “frequentist-valid” in the introduction section of our paper after the “Contributions” paragraph: “By Wald-type frequentist UQ, we refer to standard asymptotic hypothesis testing or confidence interval construction using the MLE and its asymptotic Normality—for instance, as demonstrated in Example 15.6 of [1].” and “Throughout this paper, we refer to a confidence set as asymptotically frequentist-valid at level alpha if the limit inferior of the frequentist coverage is at least 1-alpha for any parameter value. Similarly, we refer to a credible set as asymptotically Bayesian-valid at level alpha if the limit inferior of the Bayesian coverage is at least 1-alpha.”

Regarding the notations $H_n^n$ and $H_n$, could the reviewer please elaborate on what specifically they found confusing? We would be happy to change our notation accordingly, but weren’t sure what aspect the reviewer was referring to. In case it helps, the reason we chose these notations was as follows: we use $H_j$ (e.g., in Algorithm 1) to denote the history (hence the letter $H$) up to time $j$. In the non-triangular array setting this history extends as the subscript increments, i.e., $H_{j+1}$ is simply $H_j$ with one more time step concatenated, so there is only one sequence of histories. But in the triangular array setting, the sequence of histories can be completely different for different $n$, i.e., $H_j^n$ and $H_j^{n+1}$ are not the same, so we need notation to distinguish them, hence the superscript so that $H_j^n$ and $H_j^{n+1}$ have distinct notations. Then, when we look at the entire history up to time $n$, which is an important quantity, the subscript also takes the value $j=n$, and we get the notation $H_n^n$, meaning the history up to time step $n$ of the $n$th trajectory in the triangular array.

Technical Concerns:

We will add a more detailed explanation of why truncation works without bounded condition numbers to the extent that space allows in our main paper, akin to: “Our proof for why we can truncate the posterior relies critically on the second part of condition (i) of Theorem 1 which allows us to show that the density of the representative normal distribution outside of local ellipsoids converges to zero. We furthermore show that the posterior can be written as proportional to the prior multiplied by the density of the representative normal, meaning we can truncate the distribution to a local ellipsoid even if the prior is unbounded.”

It is correct that our results are not uniform in the underlying parameter. However, we have not come across any uniform BvM results in the existing literature (even in the standard i.i.d. setting). Additionally, it is generally not the case that the asymptotic normality of the MLE is uniform in the underlying parameter. For example, the (square-root-Fisher-information-rescaled) MLE is not asymptotically Normal in a triangular array setup with p=1/n for IID Bernoulli data. Consequently, the utility of a parameter-uniform BvM statement is unclear as, in most applications, it would not imply uniform frequentist validity of Bayes’ procedures.

Your point about uniformity does raise an interesting question, however, which we had not considered before, which is whether or not our result gives uniform convergence of the TV distance over suitable sets of sampling rules. More formally, the triangular array result Theorem 2 of our paper can be interpreted as the following non-triangular-array uniform convergence result for multi-armed bandits.

Corollary 1. For any sequences $(r_n, \epsilon_n)$ for which $r_n \to \infty$ and $\epsilon_n \to 0$, let $\mathcal{P}\_n$ be the sequence of sets of distributions $P$ on $H_n$ induced by sampling rules $\Lambda$ satisfying $P(\lambda_{\text{min}}(X_n^\top X_n) > r_n) > 1-\epsilon_n$. Then, we have for any $c>0$,

$\limsup_{n \to \infty} \sup_{P \in \mathcal{P}\_n} P(||\pi(\beta|H_n) − \mathcal{N}(\hat{\beta}\_n, \sigma^2(X_n^\top X_n)^{−1})||_{TV} > c) = 0$

This shows that we do have uniform convergence of TV distance over sets of sampling rules where $\lambda_{\text{min}}(X_n^\top X_n)$ grows at some uniform rate. We will add this to our revision as a remark after Theorem 2.

Experimental Limitations:

Our validation procedure consists of running multiple iterations of an experiment on synthetic data and comparing confidence intervals to the ground truth to estimate coverage and other quantities of interest. This process would be difficult to execute in real world applications where we often don’t have access to the ground truth (perhaps only estimates of it). We can, however, include examples of real-world data and report the TV distance between the Bayesian posterior and the MLE-centered Gaussian distribution (with variance-covariance matrix using the empirical Fisher information matrix, rather than the true one, as the latter is unknown to us). However, it should be noted that, as we established, Bayesian credible intervals may fail to be asymptotically frequentist-valid (in the same settings in which Wald-type intervals are asymptotically valid).

Showing coverage plots for the other non-MAB environments is a great suggestion - we’ll be sure to add these plots to the Appendix (due to space limitations) in the revision.

Questions:

We apologize that we did not specify this more clearly earlier, but the bounded $b’’’$ condition is actually satisfied for all natural exponential family models (provided that the $\beta_{0,i}$ parameters are in the interior of the parameter space). This is because the log-partition function $b(\eta)$ is smooth on the interior of the natural parameter space (see, e.g., Theorem 2.2 of [2]) and consequently it is bounded on any sufficiently small neighborhood of any interior point.

In the case of Poisson, for example, letting $\eta=\log \lambda$ be the natural parameter of the Poisson distribution, we have $b(\eta)=\exp(\eta)$ meaning $b’’’(\eta) = \exp(\eta)$, which is bounded on a union of neighborhoods around a finite number of true parameters. We will replace condition (i) with just “$\beta_{0,1},\ldots,\beta_{0,p}$ are in the interior of the natural parameter space”.

The “washout” effect can indeed be logarithmically slow if the minimum eigenvalue of the Fisher Information grows logarithmically, which is certainly a problem for finite-sample validity which we agree should be better acknowledged. We will add some text discussing this to the last paragraph of Section 3: “Note, however, that the rate at which the ‘wash out’ effect occurs depends on the rate at which the posterior distribution converges in TV distance to a normal distribution, which may be logarithmically slow for optimal bandit algorithms. Thus, it may not be accurate in finite samples to treat a misspecified prior as having `washed out’.”

Yes, if we want to show asymptotic frequentist-validity using our theory, we do need the MLE to be asymptotically normal, which can be guaranteed by regularity conditions such as stability. What’s surprising is that the step that allows us to conclude asymptotic agreement between Bayesian inference and Wald-type frequentist inference, i.e. the BvM statement, still works without the stability condition. In this sense, our result is not a relaxation of the stability condition on frequentist results but instead a new theorem about the behavior of Bayesian inference from a frequentist perspective.

Suggestions:

Our work does not provide a mitigation to instability-induced instability, and as far as we know, there is no Bayesian mitigation for this issue. We will revise our Societal Impact section by addressing the fact that Bayesian UQ may be used as if it were frequentist valid. We will include a warning that in general, Bayesian UQ should not be treated as frequentist valid in adaptive settings.

[1] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000. [2] Brown, Lawrence D. "Fundamentals of statistical exponential families: with applications in statistical decision theory." Ims, 1986.

I appreciate the author's detailed response. I believe that most of my concerns have been duly addressed. However, there are still a few points as follows:

• Regarding the notation $H_n^n$, my apologies for not being clearer. I meant to suggest using a different index for the length of the sequence, as it doesn't seem the sequence length needs to coincide with the maximum timestep $n$ (or am I wrong about this?)
• Regarding Theorem 3's statement, I think it is appropriate to make condition (i) more succinct and further elaborate on the implication in the proof. However, I suggest the authors also acknowledge in the paper that the result is limited to "the interior of the natural parameter space" and hence will not hold in some intuitive extremes, such as $Pois(\lambda \to \infty)$ (near continuous, which I mistook with near zero in the initial review)
• Regarding the delivery of the main contribution, I suggest that the authors thoroughly revise several details to distinguish "asymptotic agreement" from "frequentist validity". For instances, some of the current sentences could lead to confusion:
  • Lines 14-16: "Our results do not require the standard stability condition for validity of Wald-type frequentist UQ, and thus provide positive results on frequentist validity of Bayesian UQ under stability".
  • Lines 59-60: "...surprising aspect of our BvM results is that they do not require the key stability condition required for asymptotic validity of Wald-style frequentist inference..."

To clarify our notation, we will add the sentence “Let $\lambda_{\text{min}}(A)$ and $\lambda_{\text{max}}(A)$ denote the minimum and maximum eigenvalues of the matrix $A$ respectively” in the introduction of our paper. We will also clarify at the beginning of section 3 that $\Lambda$, our sampling rule, is allowed to be an arbitrary function of the history up to the current data point; i.e. it is meant to denote a placeholder that can represent any sampling algorithm including UCB, Thompson sampling, autoregressive models, etc.

We included Theorem 2 as a separate theorem specifically to address the setting of multi-armed bandits, which does not satisfy the assumptions of our main theorem. Even though the assumptions of Theorem 2 are satisfied in the bandit setting, the convergence provided by our theorem may be logarithmically slow if suboptimal arms are pulled at logarithmic rates. In other words, we don’t avoid the problem you identified, and we will clarify in our paper after our main theorem that the convergence can be very slow.

(W1) It is correct that our results imply that, in some cases, Bayesian credible intervals will fail to be asymptotically frequentist-valid when frequentist MLE-based inference is invalid (e.g., possibly because the stability condition is not satisfied). However, instead of a weakness, we view this as an interesting consequence of our work. In particular, our main contribution is not a new method of implementing frequentist-valid inference, but rather to explain the behavior of Bayesian inference from a frequentist perspective. We note in our “Discussion and Future Work” section that asymptotic frequentist validity may fail even when the BvM statement holds, and we discuss potential ways a practitioner could mitigate this issue. For the sake of clarity, we will add the sentence “Note that this paper does not suggest a method of asymptotically frequentist-valid Bayesian inference; in fact, we would like to warn practitioners against using either Wald-type frequentist UQ or Bayesian UQ as if it were asymptotically frequentist-valid.” to the “Discussion and Future Work” section.

(W2) We will give explicit definitions for asymptotic frequentist validity and asymptotic Bayesian validity in the introduction by adding the following sentences to a “Notation” paragraph after the “Contributions” paragraph in section 1: “Throughout this paper, we refer to a confidence set as asymptotically frequentist-valid at level alpha if the limit inferior of the frequentist coverage is at least 1-alpha for any parameter value. Similarly, we refer to a credible set as asymptotically Bayesian-valid at level alpha if the limit inferior of the Bayesian coverage is at least 1-alpha.”