Likelihood Ratio Confidence Sets for Sequential Decision Making
Authors: Nicolas Emmenegger
Mojmir Mutny
Andreas Krause
Venue: NeurIPS 2023 poster (2023)
Keywords: confidence sets
uncertainty quantification
bandits
active learning
testing

Abstract: Certifiable, adaptive uncertainty estimates for unknown quantities are an essential ingredient of sequential decision-making algorithms. Standard approaches rely on problem-dependent concentration results and are limited to a specific combination of parameterization, noise family, and estimator. In this paper, we revisit the likelihood-based inference principle and propose to use \emph{likelihood ratios} to construct \emph{any-time valid} confidence sequences without requiring specialized treatment in each application scenario. Our method is especially suitable for problems with well-specified likelihoods, and the resulting sets always maintain the prescribed coverage in a model-agnostic manner. The size of the sets depends on a choice of estimator sequence in the likelihood ratio. We discuss how to provably choose the best sequence of estimators and shed light on connections to online convex optimization with algorithms such as Follow-the-Regularized-Leader. To counteract the initially large bias of the estimators, we propose a reweighting scheme that also opens up deployment in non-parametric settings such as RKHS function classes. We provide a \emph{non-asymptotic} analysis of the likelihood ratio confidence sets size for generalized linear models, using insights from convex duality and online learning. We showcase the practical strength of our method on generalized linear bandit problems, survival analysis, and bandits with various additive noise distributions.

Likelihood Ratio Confidence Sets for Sequential Decision Making
Nicolas Emmenegger'
Mojmír Mutný" ETH Zürich
Andreas Krause ETH Zürich
ETH Zürich
Abstract
Certifiable, adaptive uncertainty estimates for unknown quantities essential ingredient of sequential decision-making algorithms. Standard approaches rely problem-dependent concentration results and limited specific combi- nation of parameterization, noise family, and estimator. In this paper, we revisit the likelihood-basee inference principle and propose struct any-rime valid confidence sequences without requiring specialized treatment in each application scenario. Our method is especially suitable for problems with well well-specified likelihoods, and the resulting sets always maintain the prescribed coverage
likelihood ratios con-
model--ggnstic manner. The size of the sets depends on choice of estimator sequence in the likelihood ratio. We discuss how to provably choose the best sequence of estimators and shed light on connections to online convex opti- mization with algorithms such as estimators, we propose a reweighting scheme that also
To counteract
the initially large bias opens up deployment in non-parametric settings such as RKHS function classes. We provide non-asymptotic analysis the likelihood ratio confidence sets size for generalized linear models, using insights from convex duality and online learning. We showcase the practical strength of our method on generalized linear bandit problems, survival analysis, and bandits with various additive noise distributions.
Introduction
One of the main issues addressed by machine learning and statistics is the estimation of unknown model from noisy observations. For example, in supervised learning, this might concern learning the dependence between input (covariate) æ and random variable (observation) y- In many cases, we are not only interested an estimate Ô of the true model parameter 0., but instead in set of plausible values that 0, could take. Such confidence sets are of tremendous importance in sequential decision-makine
tasks, where uncertainty used to drive exploration or risk aversion needs to be implemented, and covariates are iteratively chosen based on previous observations. This setting includes problems such as bandit optimization, reinforcement learning, or active learning. In the former two, the confidence sets are often used to solve the exploration-exploiatiee more generally influence the selection rule (Mukherjee al., 2022), termination rule Katz-Samuels and Jamieson, 2020), exploration (Auer, 2002) and/or risk-aversion (Makarova et al., 2021).
dilemma and
When interact with the environment by gathering data sequentially based previous confidence sets, we introduce correlations between past noisy observations and future covariates. Data collected in this manner is referred to as adaptively gathered (Wasserman al., 2020). Constructing estimators, confidence sets, and hypothesis tests for such no..i.i.d data comes with added difficulty. Accordingly. and also for its importance in light of the reproducibility crisis (Baker, 2016), the task has attracted significant attention in the statistics community in recent years (Ramdas et al., 2022).
"qqual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

2
sruh
og(2/5)
(2011)
-0.4
-0.2
0.0
0.2
0.4
(a) Gaussian
(b) Laplace C
(c) Gaussian C RKHS
Figure 1: (a) and (b) show examples of confidence sets defined via level sets of the log- -ikeeiilddood function in 2D at two dataset sizes, for Gaussian (a) and Laplace (b) likelihoods respectively. The sets inherit the geometry of the likelihood, and are not always ellipsoidal. (c) shows confidence bands on an RKHS function in a bandit game searching for the optimum. We compare prior work on confidence sets (Abbasi- Abbbai-Yadkkori- et al., 20 our LR sets, and common heuristic (orange). Our sets are nearly as small as the commonly used heuristic, but have provable coverage and can vastly improve sequential recision-making tasks such as bandits by quickly eliminating hypotheses.
Instead of deriving explicit concentration inequalities around an online estimator, we construct confidence sets implicitly defined by an inclusion criterion that easy to evaluate in computationally efficient manner and requires little statistical knowledge to implement. Roughly speaking, given model po (z) that describes the conditional dependence of the observation y given the covariate under parameter f. we will build sets based on a weighted modification of the sequential likelihood ratio statistic (Robbins al., 1972; Wasserman et al., 2020)
(0) = (1(10,)111) Lx(0)
IT. P/ (Vo (25)
IT We (ys v..)
where {8.} is a running estimator sequence that we are free to choose, but which may only depend previously collected data. Parameters I for which this statistic is small, i.c., for which (0) S 1/a will be included in the set (and considered plausible). Examples of sets in a parametric and non-parametric setting are shown in Figure 1. 'he weighting terms w, E (0, 1] are crucial for dealing with inherent irregularities of many conditional observation models but can be flexibly chosen. Classically, these are set to w, 1. The full exposition of our method with choice of estimators and weights is given in Section 2. Apart from being easy to use and implement, our approach also comes with performance guarantees. These sets maintain a provable 1 a coverage fact we establish using Ville's inequality for supermartingales ( (Ville, 1939), which is known to be essentially tight for martingales (see Howard al., 2018, for a discussion). Therefore, in stark contrast to alternate methods, our confidence sequence is fully data-dependeny making it empirically tighter than competing approaches. Despite the rich history of sequential testing and related confidence sets going back to Wald (1945) and Robbins et al. (1972), these sets have found little use the interactive machine learning community, which a gap we fill in the present paper.
Contributions In this work, we revisit the idea of using likelihood ratios to generate anytime-valid confidence sets. The main insight is that whenever the likelihood of the noise process is known, the likelihood ratio confidence sets are fully specified. They inherit their geometry from the likelihood function, and their size depends on the quality of our estimator sequence. We critically evaluate the likelihood ratio confidence sets and, in particular, we shed light on the following aspects: Firstly, for generalized linear models, we theoretically analyze the geometry of the LR confidence sets under mild assumptions. We show their geometry is dictated by Bregman divergences of exponential families (Chowdhury et al., 2022). Secondly,
show that the size of the confidence set is dictated by an online prediction game. The size of these sets depends on sequence of estimators (d. k that one uses to estimate the unknown parameter 0.. We discuss how to pick the estimator sequence in order yield a provably small radius of the sets, by using the www.tthe-Reuuarizeedd which implements regularized maximum- lin-liikeeihddd estimator. We prove that the radius of the con- fidence sets is pearly-worst-com optimal, and accordingly, they yield nearly- worst-case regret bounds when used in generalized linear bandit applications. However, due to their data-dependent nature, they can be much tighter than this theory suggests. Thirdly, we analyze the limitations of classical (un- weighted) LR sets when the underlying conditional observation model is not identifiable. In this case, the resulting (inevitable) estimation bias unnecessarily increases the size of the confidence sets. To mitigate this, propose an adaptive reweighting scheme that decreases the effect of uninformed carly
algorithm,

---

bias of the estimator sequence on the size of the sets downstream. The reweighting does not affect the coverage guarantees of our sets and utilizes an elegant connection to (robust) powered likelihoods (Wasserman et al., 2020). Finally, thanks to the adaptive reweighting scheme, our sets are very practi- cal as we showease experimentally. We demonstrate that our method works well with exponential and non-exponential family likelihoods, and in parametric as well as in kernelized settings. We attribute their practical benefits to the fact that they do not depend on (possibly loose) worst-case parameters.
2 The Likelihood Method
The sequential likelihood ratio process (LRP) in (1) is a statistic that compares the likelihood of a given model parameter, with the performance of an adaptively chosen estimator sequence. As noted above, we generalize the traditional definition, which would have wa = 1, and define a corresponding confidence set as
C. = {0 R, S 1/aa}.
(2)
The rationale is that the better parameter 0 is at explaining the data {(r,, Us) } from the true model 0., the smaller this statistic will be, thereby increasing its chances to be included in C.. When we construct RG. the sequence of Eg. W, and é, cannot depend on the noisy observation ys- Formally, consider the filtration (Fe) with sub-o-algeebas F, oz Va.... zg Ya 2s+1). We require that Og and w, are Fa-1- mmeasurbbe. Under these very mild assumptions and with arbitrary weights W, E (0, IJ. we can show coverage, i.c., our (weighted) confidence sets uniformly track the true parameter with probability a
Theorem 1. The stochastic process Rg (0.) in (1) is a non-negative supermartingale with respect to the filtration (Fi) and satisfies Ro (f,) = 1. In addition, the sequence Ct from (2) satisfies Po. (3t 0. & C.) 5 a.
The last statement follows by applying Ville's inequality for super-martingales on (0.). The proof closely follows Wasserman al. (2020). While coverage is always guaranteed irrespective of the estimator sequence {0a], we would like to make the sets as small as possible fixed coverage, which we do by picking a well pred-ptrd estimator sequence.
2.1 The Estimator Sequence Game
The specification of the LR process (LRP) allows us to choose an arbitrary estimator sequence (0=).- To understand the importance of the sequence, let us introduce 0, to the definition of Re in (1), and divide by L. ([,]1_11) 1=1)). This gives the equivalent formulation
(o.)) 1 (0.)) + confidence parameter (0) a L.((0.)._
C. =
We see that the predictor sequence does not influence the geometry of the confidence set, which is fully specified by the likelihood function. We also observe that the ratio on the right-hand side serves as a confidence parameter controlling the size (radius) of the confidence sets measured under the likelihood ratio distance to 0.. the confidence parameter goes to zero, only 9, in the set. The better the estimator sequence is at predicting the data, the smaller the inclusion threshold, and hence the smaller the sets will ultimately be. Specifically, taking the log, we would like minimize
(.(O.)
R₂ :- log
Σ
log(p" ui 0, (u= xx))
p. (v. xx)))
(3)
((00))
==1
The quantity R2 corresponds to a regret in an online prediction game, as will become apparent below.
Online Prediction Game Online optimization is a mature field in interactive learning (Cesa- Bessa-Bianchi and Lugosi, 2006; Orabona, 2019). The general goal is to minimize sequence of loss functions as in Eq. (3) and compete against a baseline, which typically is the best-in-hindsight prediction, or p in our case given by the performance of the fixed parameter 0.. Specifically, at every timestep 8, iteratively, the agent chooses an action Ú, based on Fa-1, and loss function f0) is revealed. In most of the online optimization literature, fa can be chosen adversarially. In our prediction game, we know the whole form of loss function f0)
log(p>" (y, Ix.)). as can be seen in (3), and not just (Q.). Opposed to traditional assumptions in online prediction, in our case, f. are non-adversarial, but have a stochastic component due to V.- Also, contrary to most instances of online prediction, we do not com- pare against the best-in-hing hiiddsighh predictor, but 0, instead, as this is more meaningful in our setting.
3

---

Online Optimization Algorithms Generally, we seek an algorithm that incurs low regret. Here, we focus on Follow-the-Rege Regularre Leader (FTRL), which corresoonds exactly to using regularized max- imum likelihood estimation, making it a natural and computationally practical choice. 'he update rule defined in Alg. (Line 3). While other algorithms could be considered, FTRL. enjoys the optimal regret rate for generalized linear regression as we show later, and is easily implemented. In order to run the algorithm, one requires a sequence of strongly convex regularizers. For now, let us think of as (0) X||0| I.. which we use in practice. However, one can derive a tighter analysis for slightly modified, time-dependent regularization strategy for generalized linear models as we show in Sec. 3.3.
2.2 Adaptive Reweighting: Choosing the Right Loss
There is yet more freedom in the construction of the LR, via the selection of the loss function. Not only do we select the predictor sequence, but also the weights of the losses via wt. This idea allows controlling the influence of a particular data point (z,, y1) on the cumulative loss based on the value of zt. For example, if we know a priori that for a given 22, our prediction will be most likely bad, we can opt out of using the pair (Zi, 3t) by setting wy = O. Below we will a weighting scheme that depends on a notion of bias, which captures how much of the error in predicting ye is due to our uncertainty about O, (compared to the uncertainty we still would have knowing 0.). Sometimes this bias is referred to as epistemic uncertainty in the literature, while the residual part of the error is referred to aleatoric. Putting large weight unnecessarily increase the regret of our learner (and hence blow up the size of the confidence set). Note that, conveniently, even if put low weight (zero) this sample point to improve the estimator sequence in the next prediction round. As we will show below, our reweighting scheme is crucial in defining a practical algorithm for Reproducing Kernel Hilbert Space (RKHS) models and in high signal-to-noist ratio scenarios. Since we do not know 0., our strategy is to compute an estimate of the bias of the estimator 6, and its effect on the value of the likelihood function for specific z that we played. We use the value of the bias to rescale the loss via Wt such that its effect is of the same magnitude as the statistical error (see Algorithm 1; we call this step -EAS-WEIGHHING).
data point heavily affected by this bias might
data point, nothing stops from using
To give a bit more intuition, suppose we have a Gaussian likelihood. Then the negative log-likelihood of (Iz,3t 31) with weighting is proportional to 5² (v/- x 0.) Now, if Ir does not lic
Intuition
in the span of the data points {x {==)==) used to compute 0r, it in general unavoidable incur large error, inversely proportional to -². To see this, let us decompose the projection onto It as
z (0, - 0.) (0, E(6.)) + x. [E [0]] 0.),
(4)
statistical error
biuss (ō.)
where the first term represents the statistical error up to time I, while the second, bias, is deterministic, and independent of the actual realization y. depending only O.. Estimators with non-zero bias are biased. Plugging this into the likelihood function, we see that in expectation d2 E[ye - x,7 F, S a2 bias?, (0t) + c² + t. where e² is the unavoidable predictive error in expectation (due to a noisy objective) and is a constant independent of a². C error, and C' is independent of o². Note that the bias term scales inversely with the variance, and leads to unnecessarily big confidence parameters for small o².
? is the statistical
In fact, the problem is that we use the likelihood to measure the distance between two parameters, but this is only a "good" distance once the deterministic source of the error (bias) vanishes. For this reason, without weighting, the incurred regret blows up severely in low-noise settings. To counter this, we balance the deterministic estimation bias and noise variance via proper selection of wy, In this case. it turns out that wA = + (6.)
ensures that the overall the scaling is independent of o². While the
choice of weights {w, J. influences the geometry of the confidence sets, with good data collection and estimation strategy the bias asymptotically decreases to zero, and hence the weights converge to 1.
Bias estimation In order to generalize this rule beyond Gaussian likelihoods, we need proper generalization of the bias. Our generalization is motivated by our analysis of generalized linear models, but the method can be applied more broadly. The role of the squared statistical error (variance) is played by the inverse of the smoothness constant of the negative log- likeliood functions fa. denoted by L. This is the usual smoothness, commonly seen in the convex optimization literature.

---

We consider penalized likelihood estimators with strongly convex regularizers (Alg. 1, line 3). For this estimator class, we define the bias via hypothetical stochastic-error-free estimate 0 had we access to the expected values the gradient loss functions (a.k.a. score), We use the first-order optimality conditions and the indicator function of the set θ ig, to define the error-free ersttiateest 0," and the bias of the estimator Og as
bias" (0.) (x: (0+ ))² with E V logPa Par (usl=x) Vole(0 + (0 0, (5)
where the expectation denotes sequence expectations conditioned on the prior filtration. This notion of bias coincides with the definition of bias in Eq. (4) for the Gaussian likelihood. This quantity cannot be evaluated in general, however, we prove a computable upper bound.
Theorem 2 (Bias estimate). Let the negative log- eiglikelihood have the form. log pe (yalæ.) g a 0).
where g : IR- + R is strongly-conve and let the regularizer be (b)( = X \| making the overall objective strongly convex. Then, defining ViiAA = E'=n ,I T + AI, we can bound
bias S 2\ 0010 (V
(6)
The proof is deferred to App. A.3, and requires elementary convex analysis.
This leads us to propose the weighting scheme Wl bias?, +1/z We justify that this is sensible
1/L
choice by analyzing the confidence set the GLM class in Section 3, which satisfies the smoothness and strong-con strong-convexity conditions. We show that this rule properly balances the stochastic and bias components of the error in the regret as in (3). However, this rule is more broadly applicable beyond the canonical representation of GLM or the GLM family altogether.
Algorithm 1 Constructing the LR Confidence Sequence
1: Input: convex set C Rd, confidence level a > 0, likelihood (o(l),) regularizers {viee
2: for E No do
3: 0. arg mingee
1==1
log (Us x..) + (0)
> FTRL
1/L
THIS WORK
4:
1/I++bass, (0.)
HIAS-WEIGHTING bias,, (0.) in Eq. (5) (6,
CLASSICAL
(M. 12,)
5: G +
IT
1
Confidence set
Po
(M- 2x)
6: end for
3 Theory: Linear Models
While the coverage (i.e., "correctness"") of the likelihood ratio confidence sets is always guaranteed, their worst-case size (affecting the "performance") cannot be easily bounded in general. We analyze the size and the geometry of the LR confidence sequence in the special but versatile case of generalized linear models.
3.1 Generalized Linear Models
We assume knowledge of the conditional probability model po where the covariates E X C Rd. and the true underlying model parameter lies in a set ② C Rd If t is indexing (discrete) time, then Pr is acquired sequentially, and the subsequently observed ye is sampled from an exponential family distribution parametrized as
p xx) h(y) exp (T(y) = A(z-((z]0)) 0))
Here, is referred to as the log-partition function of the conditional distribution, and T is the suf- ficient statistic. The function h is the base measure, and has little effect our further developments, as it cancels out in the LR. Examples of commonly used exponential families (Gaussian, Binomial, Poisson Weibull) with their link functions can be found in Table I in App. A.I.
In order to facilitate theoretical analysis for online algorithms, we make the following assumptions about the covariates X' and the set of plausible parameters e.
5

---

Assumption 1. The covariates are bounded, i.e., supnexl|z|la I 1, and the set θ is contained in an by-ball of radius B. We will also assume that the log nog-partition function is strongly convex, that is, that there exists == inf =e[-B.B] (z), and that A is I-smooth, i.e. I, == su (z).
These assumptions are common in other works addressing the confidence sets of GLMs (Filippi et al., 2010; Faury et al., 2020), who remark that the dependence μ is undesirable. However, in contrast to these works, our confidence sets do not use these assumptions in the construction of the sets. We only require these for our theoretical analysis. As these are worst-case parameters, the practical performance can be much better for our sets.
3.2 Geometry and Concentration
Before stating our results, we need to define a distance notion that the convex negative log-likelihoods induce. For a continuously differentiable convex function f. we denote the Bregman divergence as Dy(a, b) := f(a)- f(b)- VI(b) (a- b). The u-regularized sum of log-partition functions
is defined as
(0) = Σ w.,((o +
" 1011
(8)
This function will capture the geometry of the LR confidence sets. The confidence size depends mainly on two terms. One refers to a notion of complexity of the space referred to as Bregman
information gain: (0:) log
Jgd exp( 3100 first defined by Chowdhury et al. (2022) as Je (2y
a generalization of the information gain of Srinivas al. (2009), 3/' = log (det(E.=1 - + I) for Gaussian likelihoods. We will drop the superscript whenever the regularization is clear from context and simply refer to 7t- This term appears because one can relate the decay of the likelihood as function of the Bregman Divergence from 0, with the performance of (regularized) maximum likelihood estimator via convex (Fenchel) duality. In particular, if 0, is a regularized MLE, r. == (O.) will asymptotically scale as O log 1) (cf. Chowdhury et al., 2022, for further discussion). For Gaussian likelihoods and w = 1, it coincides with the classical information gain independent of 0,. The second term that affects the size is the regret R, of the online prediction game over rounds we introduced previously in (3). These two parts together yield the following result:
Theorem 3. Let > 0 and a. 5 E (0. 1). For the level - confidence set Ct defined in (2) under the GLM in (7), with probability 8, for all t 2 1, any 0 E C. satisfies
4h E + 2lo
(0)
D2-(0,0.) (0,0.) S
(8) + 2R.
where & = (log (2) + vB² + 17) and L, μ are defined as above and finally Re is the regret of the game in Eq. (3).
The set defined via the above divergence does not coincide with the LR confidence set. It is slightly larger due to term involving v (as in Eq. (8)). This is a technical consequence of our proof technique, where the gradient of Z needs to be invertible, and regularization is added to this end. We note that this v > 0 can be chosen freely. Note that the theorem involves two confidence levels, and ō: is a bound on the Type error coverage of the confidence sets while d upper bounds the probability of a large radius - and therefore related to the power and Type II error of corresponding hypothesis test. The proof of the theorem is deferred to App. B.2.
To give more intuition on these quantities, let us instantiate them for the Gaussian likelihood case with w. 1. In this scenario, Z (8) Ei=1 2 ||0 12 I + 5 11 and the (in this case symmetric)
Bregman divergence is equal to Dzy (0., = 1 - 0-11,, V 2... where V = -'- [ + vI, which means that our confidence sets are upper bounded by a ball in the same norm as those in the seminal work on linear bandits (Abbasi- Yadkori et al., 2011).
3.3 Online Optimization in GLMs: Follow the Regularized Leader
The size of the confidence sets in Theorem 3 depends on the regret of the online prediction game involving the estimator sequence. We now bound this regret when using the Follow-the Reg-thhe--R Leader (FTRL) algorithm in this setting. This high probability bound is novel to the best of our

---

knowledge and may be of independent interest. We state in tright--gnostic manner first, and then with our particular choice. The latter variant uses a specifically chosen regularizer. In this case, we can track the contribution of each time-step towards the regret separately.
Theorem 4. Let (0) = -l111l Assume Assumption 1, and additionally that A is L-smooth everywhere in R2, and let w, E [0, 1] be arbitrary. Then, with probability 1 - 8 the regret of FTRL
(Alg. 1) satisfies for all 2 1
L (16 + +llog(1/8) 2L
R. S XB² +
(10)
The regret bounds are optimal in the orders of n/, matching lower bounds of Ouhamma et al. (2021),
as for linear models "/t (d t). Combining results of Thm. 4 with Thm. 3, we get confidence parameter that scales with ((vT)), for confidence sets of the form | - 0. which coincides with the best-known confidence sets in this setting in the worst-case The requirement of global L s-smoothness can be relaxed to L smmshhtssesss over O. With a more elaborate (but less insightful) analysis, we can show that we achieve ((x)) bound even in this case. The proof' of these results are deferred to App. C.4, App. C.5 and App. C.6 respectively.
Yadkori et al., 201 2).
Regret, Weighting and Estimation Bias Interestingly, the term in Thm. involving the (crude) proxy to the bias the bound B is not scaled by the same L/μ factors as the other terms in the regret bound (10) and Theorem 3. Namely, the prefactor is T/2/u instead of I.Ju. This extra dependence manifests itself in the unnecessary penalization through the estimation bias we introduced in Sec. 2.2, particularly in low-noise settings. We addressed this issue by picking the weights } While the above theorem holds for any valid weighting, it does not exhibit the possible improvement from using specific weights.
We argued earlier that the error in prediction should not be measured by the likelihood function if there is deterministic error, since initially, we are fully uncertain about the value of 0. T(-) outside the span of previous observations. Of course, if our goal would be to purely pick weights to minimize R2, then W,- = 0 would lead to zero regret and hence be optimal. However, the likelihood ratio would then be constant, and uninformative. In other words, the associated log- aag-paatttion Bregman divergence in Theorem 3 would be trivial and not filter out any hypotheses. Clearly, some balance has to be met. With this motivation in mind, we proposed a nonzero weighting that decreases the regret contribution of the bias, namely ut = b/ns+ (02)*
1/L
The advantage of this choice becomes more apparent when
we use the regularizer (0) = >1 011 + AAxT 6) to obtain the following result.
Theorem 5. Let vb, (0) 2 + A(xT0). Assume Assumption 1, and additionally that A is 1/L
L- L-smooth everywhere in Rd, and choose ws 1/L+tias,, 10.y²' Additionally, let the sequence of I, be such that, Σ, - w. (fs)) (=(0++1)) S L/ where 0g is the FTRL optimizer with the regularizer X||0| 3 from Theorem 4 2. Then, with probability 1 the regret of FTRL (Alg. 1) satisfies for all t
2T.
2/ + log (1))+1
B²
R2 S XB2 +
A7
1
1/L + bias? z. (0.)
where AyA = 78+1 - - 7d.
One can see that for points where the information gain Ars is large (corresponding to more unexplored regions of the space, where the deterministic source of error is then large), the weighting scheme will make sure that the multiplicative contribution of B is mitigated, along with having the correct prefactor L/P The reader may wonder how this result is useful when we replace bias", (f.) with the upper bound from Thm. 2. While instructive, our bound still only makes the bias proxy B² appear in front of the information gain Are, instead of the more desireable bias itself. In the latter case, we could also directly make use of the upper bound and get an explicit result only using an upper bound on the bias. We leave this for future work.
We point out that this choice of vh. (0) in Theorem 5 corresponds to the Vovk-Azoury- Bork-AzouryWarmutt Warmuth predictor (Vovk, 2001; Azoury and Warmuth, 1999) in the online learning literature. This choice is helpful in order to track the bias contribution more precisely in our proof.
Note that this assumption was missing in an earlier version. 0.41 corresponds to a regularized MLE that did observe the data pair (I,, ).
7

---

4 Application: Linear and Kernelized Bandits
Our main motivation to construct confidence sets is bandit optimization. A prototypical bandit algorithm - the Upper Confidence Bound (UCB) (Auer, 2002) sequentially chooses covariates I, in order to maximize the reward Σ ro, (rx), where rs, is the unknown pay-off function parametrized by 0.. UCB chooses the action I, which maximizes the optimistic estimate of the reward in each round, namely
Ig arg max max ro(x), RE BEC.-1
(11)
where C--1 some confidence set for 0., and can be constructed with Algorithm from the first - data points. An important special case is when ra, is linear (Abe and Long, 1999) modelled by a generalized linear model (Filippi et al., 2010). that case, the inner optimization problem convex long C.-1 is convex. The outer optimization is tractable for finite X. In the applications we consider, our confidence sets are convex, and we easily solve the UCB oracle using convex optimization toolboxes.
Extension to RKHS We introduced the framework of LR confidence sets only for finite- dimensional Euclidean spaces. However, it can be casily extended to Reproducing Kernel Hilbert Spaces (RKHS) (Cucker and Smale, 2002). The definition of the LR process in (1) is still well-posed. but now the sets subsets of the RKHS, containing functions f E He. An outstanding issue is how to use these sets in downstream applications, and represent them tractably as in Figure 1. Conveniently, even with Lagrangian formulation, and the generalized representer theorem applies (Schölkopf et al., 2001; Mutný and Krause, 2021). In other words, we can still derive a pointwise upper confidence band as ucb(x) = fa.. BBCEEC {f, k(x, :)) in terms of (z,} U {z), leading to + 1-dimensional, tractable optimization problem.
RKHSs, the inner-optimization in (11) admits
We also point out that the weighting is even more paramount in the RKHS setting, as the bias never vanishes for many infinite dimensional Hilbert spaces (Mutný and Krause, 2022). For this purpose, our weighting is of paramount practical importance, as we can see in Figure 2a), where the gray arrow represents the significant improvement from reweighting.
4.1 Instantiation of the Theory for Linear Bandits
Before going to the experiments, we instantiate our theoretical results from Sec. 3 to the important and well-studied special case of linear payoffs. In that case, ra = (ar, 0) and the agent observes y. (z,; 0.) + TTs upon playing action I,, where 7)s o0,,a²), We are interested in minimizing the so-called cumulative pseudo-regret, namely, R, = = Krr,, 0-) (a.,; 0-)], where v, refers to the optimal action. Using the set from (2) along with Theorem and the FTRL result we can get regret bound for the choice w, =
result of Theorem
Theorem 6. Let W 1. For any X 2 2.. with probability at least - 35, for all t E N we have
R, S 1 (a log(1))) + 78 + ox + BVT))
Our results are optimal in both d and f up constant and logarithmic factors. The proof is deferred to App. D, but is an instantiation of the aforementioned theorems, along with a standard analysis. There, we also compare the seminal result of Abbasi- Yadkori et al. (201 1), which does not suffer from the dependence on TT- We attribute this to the incurred bias in the absence of the reweighting scheme.
For the weighted likelihood ratio, we can obtain a result similar to the above, but multiplied by an upper bound on sup,21 w This undesirable, as our experiments will show that the reweighting scheme vastly improves performance. While this could be somewhat mitigated by using the Theorem instead of Theorem 4 to bound the FTRL regret, a better result should be achievable using weighting scheme that improves upon Theorem 6 and possibly even matches Abbasi- Yadkori et al. (2011) 1) exactly in the worst-case. We leave this for future work.
4.2 Experimental Evaluation
In this subsection, we demonstrate that the practical applicability goes well beyond the Gaussian theoretical result from the previous subsection. In the examples below, we always use the UCB
8

---

60
a)
Gaussian Likelihood
100
b)
Laplace Likelihood
Regret
Regret
80
20
200
50
150 Poisson Bandits
Iterations Surival Analysis
Iterations
100 C)
d)
200
175
Regret
60
Regret
125
3400
75
100
200
300
230
300
Iterations
Iterations
AY (2011)
LR (no weights)
NR (2021)
MK (2021)
LR (Our Alg.1)
Heuristic 8 = 21og(1/6)
Sub-Exp
Laplace
Figure 2: Bandit experiments: On the y-axis report cumulative regret, while the x-axis shows the number of iterations. In a) and b) we report the results for linear models with different parametric additive noise. In c) we report the results on a survival analysis with log-Weibull distribution (p 2) and in d) we showcase Poisson bandits. See App. E for more details. Heuristic methods are dashed, while provable are solid. Our sets perform the best among all provable methods. Notice in a) the difference in gray and black represents the improvement due to adaptive weighting over W' = 1 for all E [4]. For each experiment we did 10 reruns, median values are plotted.
algorithm but employ different confidence sets. In particular, we compare our LR confidence sets for different likelihood families with alternatives from the literature, notably classical sub-family confidence sets (Abbasi-Yadkori Yadkori et al., 201 Mutný and Krause, 2021), and the robust confidence set of Neiswanger and Ramdas (2021). In practice, however, the radius of these confidence sets is often tuned hcuristically. We include such sets as a baseline without provable coverage as well. The main take-home message from the experiments is that among all the estimators and confidence sets that enjoy provable coverage, our confidence sets perform the best, on par with successful heuristics. For all our numerical experiments in Figure 2, the true payoff function is assumed to be infinite dimensional RKHS element. For further details and experiments, please refer to App. E.
Additive Noise Models Suppose that re, is linear and observe y, __ 8, + 7)s, where n)s is additive noise, and A, is an element of Hilbert space. We consider classical Gaussian noise as well as Laplace noise in Fig. 2[a), b)]. Notice that in both cases confidence sets yield lower regret than any other provably valid method. In both cases they are performing as good as heuristic confidence sets with confidence parameter et al. (2011) 1) (AY 201 are invalid for the Laplace distribution as it is not nub-Gaussian but only sub- Exponential. For this reason, compare also with sub-exponential confidence sets derived similarly to those of (Faury et al., 2020). The confidence sets of (Neiswanger and Ramdas, 2021) (NR 2021) perform similarly on Gaussian likelihood, but are only applicable this setting, as their generalization to other likelihood families involves intractable posterior inference. We note also the difference be- tween the unweighted LR and the weighted one. The examples in Fig. use the true payoff functions r(z) - (1.4 3z) sin (18z), which we model as an element of a RKHS with squared exponential kernel lengthscale 7 = 6 x 10 on [0, 1.2), which the baseline function no. 4 in the global optimiza- tion benchmark database infimity77 (Gavana, 2021). Additional experiments can be found in App. E.
2 log( 1/8). The sub-Gaussian confidence sets of Abbasi- Yadkori
Poisson Bandits A prominent example of generalized linear bandits (GLB) are Poisson bandits, where the linear payoff is scaled by an exponential function. We instantiate our results on a common benchmark problem, and report the results in Fig. 2d). We improve the regret of UCB for GLBBs compared to two alternative confidence sets: one that uses Laplace approximation with a heuristic confidence parameter, and one inspired by considerations in Mutný and Krause (2021) (MK 2021), also with a heuristic confidence parameter. Note that we cannot compare directly to their provable results in their original form as they do not state them in the canonical form of the exponential family.

---

Survival Analysis Survival analysis is branch of statistics with rich history that models the lifespan of service or product (Breslow, 1975; Cox, 1997; Kleinbaum and Klein, 2010). The classical approach postulates a well-informed likelihood model. Here, we use a specific hazard model, where the survival time T is distributed with Weibull distribution, parametrized by and p. The rate (x) = exp(x 0) differs for each configuration x, and p which defines the shape of the survival distribution - is fixed and known. We assume that the unknown part is due to the parameter O which is the quantity we build confidence set around to use within the UCB Algorithm. In particular, the probability density of the Weibull distribution is P(T = f/)r = Ag (ar (a)ppP - expl exp(-f" (xp(-((Xy(xz)) In fact, with p 2, the confidence sets convex and the UCB rule can be implemented efficiently.
Interestingly, this model admits an alternate linear regression formulation. Namely upon using the transformation Y = log T. the transformed variables Y|2 follow a Gumbel-type distribution, with the following likelihood that can be obtained by the change of variables P(Y = y| = do (x) exp(y)" exp( exp(y)">xo )a)))). The expectation over Y allows us to express it as a linear regression problem since E|y [r] = -00 100==== +1/pp, where y is the Euler-Mascheroni constant. More importantly, Y|2 is sub-exponential. Hence, this allows us to use confidence sets for sub-exponential variables constructed with the et al. (2020). More details on how these sets are derived can be found in App. E. However, these approaches necessarily employ crude worst-case bounds and as can be seen in Figure 2c) the use of our b-sed confidence sequences substantially reduces the regret of the bandit. learner.
maximization technique inspired by Faury
5 Related Work and Conclusion
Related Work The adaptive confidence sequences stem from the seminal work of Robbins et al. (1972), who note that these sets have a- a-bounded Type I error. The likelihood ratio framework has been recently popularized by Wasserman et al. (2020) for likelihood families without known test statistics under the name universal inference. This approach, although long established, is surprisingly uncommon in sequential decision-making tasks like bandits. This might be due to the absence of an analysis deriving the size of the confidence sets (Mutný and Krause, 2021), a necessary ingredient to obtain regret bounds. We address this gap for generalized linear models. Another reason might be that practitioners might be interested in non-parametric sub- sub-families- scenario our method does not cover. That being said, many fields such as survival analysis (Cox, 1997) do have well-informed likelihoods. However, most importantly, if used naively, this method tends to fail when one departs from assumptions that our probabilistic model is identifiable (i.e., pa (x) pg( ax)) even if A * Ø). We mitigate this problem by introducing the scaling parameters wy in Eq. (1) to deal with it.
Prevalent constructions of anytime-valid confidence intervals rely on carefully derived concentration results and for a specific estimator such as the least-squares estimator and noise sub-families such as sub-Gaussian Mutný and Krause (2021). Their constructions involve bounding the suprema of collections of self-normalized stochastic processes (Faury et al., 2020; Mutný and Krause, 2021; Chowdhury et al., 2022). To facilitate closed-form expressions, worst-case parameters are introduced that prohibitively affect the size of the sets making them much larger than they need to be.
and sub-Poisson Abbasi Yadkori et al. (201 1); Faury et al. (2020);
Chowdhury et al. (2022) use the exact form of the likelihood to build confidence sets for parameters of exponential families. However, their approach is restricted to exponential family distributions. They use neff-normalization and mixing techniques to explicitly determine the size of the confidence set and do not use an online learning subroutine as we do here. Neiswanger and Ramdas (2021) use likelihood ratios for bandit optimization with possibly misspecified Gaussian processes but is not tractable beyond Gaussian likelihoods. The relation between online convex optimization and confidence sets has been noted in so-called online-to-confidere
conversions (Abbasi-yadkori Yadkori et al., 2012; Jun et al., 2017: Orabona and Jun, 2021: Zhao et al., 2022), where the existence of a low-regret learner implies a small confidence set. However, these sets still use potentially loose regret bounds to define confidence sets. Our definition is implicit. We do not necessarily need a regret bound to run our method, as the radius will depend on the actual, instance-dependee performance of the learner.
Conclusion In this work, we generalized and analyzed sequential likelihood ratio confidence sets for adaptive inference. We showed that with well-specified likelihoods, this procedure gives small, any-time valid confidence sets with model-agnostic and precise coverage. For generalized linear models, we quantitatively analyzed their size and shape. We invite practitioners to explore and use this very versatile and practical methodology for sequential decision- making tasks.
10

---

Acknowledgments and Disclosure of Funding
We thank Wouter Koolen and Aaditya Ramdas for helpful discussions well as for organizing the SAVI workshop where these discussions took place. NE acknowledges support from the Swiss Study Foundation and the Zeno Karl Schindler Foundation. MM has received funding from the Swiss National Science Foundation through NFP75. This publication was created as part of NCCR Catalysis (grant number 180544), National Centre Competence in Research funded by the Swiss National Science Foundation.
References
Abbasi- Yadkori, Y., Pál, D., and Szepesvari, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages
Abbasi- Yadkori, Y., Pal, D., and Szepesvari, C. (2012). Enline-to-connidence-ss conversions and application to sparse stochastic handits. In Lawrence, N. D. and Girolami, M., editors, Proceedings of the Fifteenth International Conference Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 1-9, La Palma, Canary Islands. PMLR.
Abe, N. and Long, P. M. (1999). Associative reinforcement learning using linear probabilistic concepts. In ICMI., pages 3-11. Citeseer.
Auer, P. (2002). Using confidence bounds for exploitation trade-offs. Journal of Machine Learning Research, 3NNo)):397
Azoury, K. S. and Warmuth, M. K. (1999). Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, 43:211-2466
Baker, M. (2016). 1,500 scientists lift the lid reproducibility. Nature, 533:452-4555
Breslow, N. E. (1975). Analysis of survival data under the proportional hazards model. International Statistical Review / Revue Internationale de Statistique.
Carpentier, A., Vernade, C., and Abbasi-Yadkori, Y. (2020). The elliptical potential lemma revisited. ArXiv, abs/2010.101 10182.
Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, Learning, and Games. Cambridge University Press, New York, NY, USA.
Chowdhury, S. R., Saux, P., Maillard, O.-A., and Gopalan, A. (2022). Bregman deviations of generic exponential families. arXiv preprint 27X10:2201.07366.
Cox, D. R. (1997). Some remarks the analysis of survival data. In Proceedings of the First Seattle Symposium in Biostatistics, pages 1-9. Springer.
Cucker, F. and Smale. S. (2002). On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1-44
Faury, L., Abeille, M., Calauzènes, C., and Fercoq, O. (2020). Improved optimistic algorithms for logistic bandits. In /CML2020: Proceedings of the 37th International Conference on International Conference Machine Learning.
Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010). Parametric bandits: The generalized linear case. In Advances in neural information processing systems, pages 586-594.
Gavana, A. (2021). infinity global optimization benchmarks and ampgo. http://infinity:: net/g
ieteraatioonnnnexe. index.idxx..//// html#.
Hazan, E. (2016). Introduction to online convex optimization. Found. Trends Optim., 2:157-325.
Hazan, E., Agarwal, A., and Kale, S. (2006). Logarithmic regret algorithms for online convex optimization. Machine Learning, 1992
Howard, R., Ramdas, A., McAuliffe, J., and Sekhon, (2018). Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317.

---

Jun. K.-S.. Bhargava, A., Nowak. R., and Willett, R. (2017). Scalable generalized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30.
Katz-Samuels, and Jamieson, K. (2020). The true sample complexity identifying good arms. In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 178 1781-1791, PMLR.
Kleinbaum, D. G. and Klein, M. (2010). Survival analysis, volume 3. Springer.
Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithmss. Cambridge University Press.
Makarova, A., Usmanova, Bogunovie, I., and Krause, A. (2021). Risk-averse heteroscedastic bayesian optimization. In Proc. Neural Information Processing Systems (NeurIPS).
McCullagh, P. (2018). Generalized linear models. Chapman and Hall.
Mukherjee, S., Tripathy, A. S., and Nowak, R. (2022). Chernoff sampling for active testing and extension to active regression. International Conference on Artificial Intelligence and Statistics, PMLR.
pages
Mutný, M. and Krause, A. (2021). No-regret algorithms for capturing events in poisson point processes. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7894- 7904. PMLR.
Mutný, M. and Krause, A. (2022). Experimental design of linear functionals in reproducing kernel hilbert spaces. In Proc. Neural Information Processing Systems (NeurIPS).
Neiswanger, W. and Ramdas, A. (2021). Uncertainty quantification using martingales for misspecified gaussian processes. In Feldman, V., Ligett, K., and Sabato, S., editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings Machine Learning Research, pages 963-982. PMLR.
Orabona, F. (2019). A modern introduction to online learning.
Orabona, F. and Jun, K.-S. (2021). Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory, 70:436-455.
Ouhamma, R., Maillard, O.-A., and Perchet, (2021). Stochastic online linear regression: the forward algorithm to replace ridge. In Neural Information Processing Systems.
Ramdas, A., Grünwald, P., Vovk, V., and Shafer, G. (2022). Game-theoretic statistics and safe anytime-vale valid inference.
Robbins, H., Siegmund, D., et al. (1972). A class of stopping rules for testing parametric hypotheses. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 4: Biology and Health. The Regents the University of California.
Schölkopf, B., Herbrich, R., and Smola, A. (2001). A generalized representer theorem, In Computa- tional learning theory, pages 416-426. Springer.
Srinivas, N., Krause, A., Kakade, M., and Seeger, M. W. (2009). Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning.
Ville, J.-L. (1939). Étude critique de la notion de collectif.
Vovk, V. (2001). Competitive on-line statistics. International Statistical Review, 69.
Wainwright, M. J. (2019). High-dimensional statisties: A non-asymptotic viewpoint. Cambridge university press.
Wald, A. (1945). Sequential tests of statistical hypotheses. Annals of Mathematical Statistics, 16:256-298.
12

---

Wasserman, L. A., Ramdas, A., and Balakrishnan, S. (2020). Universal inference. Proceedings of the National Academy of Sciences, 117:16880- 16890.
Zhao, H., Zhou, D., He, J., and Gu, Q. (2022). Bandit learning with general function classes: Heteroscedastic noise and variance-dependent regret bounds. ArXiv, 21222222211363..
13


Reviews:
[{"review_id": "ZtYCHpYSDh", "reviewer": "Reviewer_CfDQ", "summary": "This paper proposes a new construction of confidence sets for a parametric setting, where the likelihood of the noise process is explicitly given.\nThe proposed method is based on a weighted variant of the sequential likelihood ratio (LR) statistics, which was proposed in universal inference (Wasserman et al., 2020).\nThe confidence set is a function of the choice of estimators that construct the sequential LR statistics, and the paper proposes a specific method to construct such estimators by the means of Follow-the-Regularized-Leader (FTRL) algorithm in online learning, by viewing the confidence parameter minimization as a regret minimization problem.\nFurther, the paper proposes a new adaptive reweighting scheme, which uses a powered LR statistics to make the resulting confidence set more “robust”. The proposed reweighting scheme is based on the bias of the used estimators. While the bias may not be directly estimated, they provide a computable upper bound on the bias for a certain form of distributions.\nFor generalized linear models, the size of the confidence set is analyzed under regularity assumptions. To make the bound fully concrete, they also provide a high-probability regret guarantee of the used FTRL estimators (for GLMs).\nThe effectiveness of the proposed method is demonstrated with linear and kernelized bandit experiments.\n", "questions": "- I find the sentence in line 107 a bit confusing. It says “If the confidence parameter goes to zero, only $\\theta_\\star$ is in the set.” This is not the case, as the LHS (of the inequality inside the set notation) in the equation after line 103 is 1 if $\\theta=\\theta_\\star$, and so $\\theta_\\star$ will be excluded if the RHS goes to zero. What should be a proper explanation?\n- I cannot make much sense of the specific reweighting scheme in line 162 right away, though I can understand the intuition thanks to the Gaussian example. Can you elaborate this choice?\n\nA possible typo:\n- Line 153: depending only $\\theta_\\star$\n\n", "limitations": "Limitations are not discussed. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very well written. The proposed framework and analysis are a nice and careful combination of several different techniques (universal inference, FTRL, Bregman information gain, …) in statistics and online learning.\nI think this could be indeed useful in bandit problems but it can be also applicable whenever parametric models are available.\n", "weaknesses": "I do not find a crucial weakness of this paper, except a few questions detailed below.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. Indeed you are right; this is a typo on our side. What we meant to say is if the $\\log$ of the expression goes to zero (or the expression goes to 1), then only the true parameter $\\theta^*$ is included in the set. We bear in mind here that the prediction game is played on the log-likelihood loss.\n        \nRegarding the reweighting: In general, there are two sources of error, stochastic (sometimes called \"aleatoric\" uncertainty) and deterministic (sometimes called \"epistemic\" uncertainty) – we refer to it as bias. The likelihood function properly measures only stochastic noise. In a certain sense, our problem is not well posed in the absence of sufficiently rich data. For example, it is impossible to distinguish between (linear) models that differ only in the subspace orthogonal to the data. This causes the likelihood ratio to unnecessarily blow up, as we show in theory and in examples. \n\nLet us now give some intuition behind the choice of our reweighting scheme. A naive solution would be to gather data and set $w_i = 0$ until the bias vanishes -- i.e., we observe data that span the whole space. However, this might never happen in non-parametric settings like RKHSs, and is therefore not viable. Additionally, even when the bias is non-zero, there is information that can be leveraged by including it in the likelihood ratio sequence. Now, the question is how much information, and how can we include it. The reasoning we adopt is motivated by understanding how much the deterministic error (bias) influences the likelihood ratio when compared against the stochastic component. If these two parts are, say, equal in magnitude, then we would choose $w_i =1/2$ to reflect that only half of the contribution is the stochastic part relevant to the likelihood formulation. This simple example, generalizes the intuition from the Gaussian case to GLMs, and helps us to reduce the bias of the online optimizer that we analyze in Sec. 3.2.\n\nGiven that we are interested in practical methods, and not just theory, we were driven to propose a widely applicable and performant scheme. Our reweighting scheme is just that: motivated by balancing out terms in the regret of the online learner (by effectively changing its objective), it strikes a balance between bias and variance. \n\n"}, {"review_id": "eASQ5MEXPV", "reviewer": "Reviewer_DGax", "summary": "The paper proposes to use likelihood ratios to construct confidence sequences that facilitate the downstream online decision making under uncertainty. The weighting and corresponding bias estimation are proposed to avoid regret blow-up in low-noise setting. The paper offers theoretical insights for the bias estimation, the geometry of the confidence set for generalized linear model (GLM), and regret in the online optimization in GLM. The paper offers the corresponding empirical results on bandits problems.", "questions": "1. Minor issue: the product on the denominator of eq (1) seems to be falsely indexed, could the author double-check?\n2. In the bandit problems, how are the confidence levels specified?\n3. Could the author briefly comment on the potential impact of misspecified likelihood (robustness to misspecification when there is a uniform error bound for the misspecification)? ", "limitations": "Discussed in the comments above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper incorporates the likelihood ratios into online decision-making. The LR confidence set reduces the requirement of conventional concentration results and allows existing algorithms to solve more generalized problems as long as the likelihood is well specified. There is room for studying its application in various sequential decision-making tasks.\n2. The adaptive weighting scheme is well justified with practical bias estimation.\n3. The geometry analysis could be helpful to justify the usage of the LR confidence set rather than alternatives.", "weaknesses": "1. In general the paper is clearly organized. However, the scattered yet closely related notations in sections 2 and 3 make it challenging to follow. I would recommend further highlighting important definitions and formulas or trying to concentrate on them to allow easier revisits.\n2. The experiment results shown in Figure 2 lack statistical significance. The fact that the figure shows median values rather than mean values indicates the stability problem of the experiment results.\n3. The mismatch between the theoretical results in section 3 with regards to the online optimization and the empirical study mostly focused on bandit problems in section 4. As only the downstream cumulative regrets are shown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, we will try to polish notation and improve the readability of the manuscript. Now to specific concerns and questions:\n       \n**C:**: *\"The experiment results shown in Figure 2 lack statistical significance.\"* **R:** We provide the same plot with the mean in the attached document. However, we disagree with you that plotting the median shows instability. What shows instability is the large spread in general. Plotting quantiles with mean is to the best of our knowledge non-standard, hence the median was chosen. We find results reporting mean more questionable. Additionally, we would like to point out that our method is stable and instability usually arises with heuristics such as MK2021 or NR2020 which suffer from numerical issues. \n        \n**C:** *“Mismatch”* **R:** At first sight, there might seem to be a mismatch between theory and experiments, however, downstream bandit regret and the size of the confidence set are intimately related. For the UCB algorithm (the one we use in the experiments), the better the confidence sets, the better the algorithm's bound and its practical performance. We chose to demonstrate our applicability in this manner, as at the end of the day, our sets' worth is measured by their downstream applicability. This being said, we prove a calibration plot in the attached documents and will add it to the paper. The plot shows that the heuristic methods lose coverage while the other provable methods are way too conservative. These likelihood ratios are somewhere between these two extremes. The calibration plots come with caveats however, since they depend on the true parameter $\\theta_*$, and how you collect the data. Since we are not interested in the iid setting, we need to choose a way to collect data, say via a bandit algorithm or in some active learning setting. In these scenarios, calibration plots are rarely what people are interested in, and therefore a rather non-standard method of evaluation. We show our results for two different values of $\\theta_*$. \n\nWe understand that the different regret notions (bandit application regret vs. regret of the online learner) could lead to confusion, and we will clarify this in a revised version. In terms of theory, for that reason as well, we were reluctant to state explicit regret bounds of the bandit algorithm. Note however, that they follow immediately by an application of the elliptical potential lemma. For instance, for linear bandits, we directly obtain the optimal $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ regret rate. \n           \n**Q1:**: Thank you for pointing this out. This is indeed a typo, and the index should be $s$ instead of $i$.\n           \n**Q2:** The confidence levels are done exactly as proposed in the paper and maintain provable coverage up to the chosen $\\delta$. We chose $\\delta = 0.1$. We compare the exact methods from the literature as well as to empirical heuristics popular in the field that people use in deployed applications. The reason our sets need no tuning is that the confidence radius is implicit when compared to ellipsoid confidence sets from the literature with fixed (worst-case dependent) radius. Since we practically use no inequalities to derive our confidence sets, they are arguably closer to what is practically achievable with provable coverage, and inherit forms of instance-dependency.\n            \n**Q3:** We do not discuss robustness in the paper, and a proper treatment requires a follow-up. In general, as noted in the work on universal inference [1], exponentiating a likelihood with small powers can improve robustness, but this is only a heuristic. In general, in the presence of misspecification, it is not possible to guarantee coverage with our approach. In contrast, the size analysis mostly depends on tail properties of the random variables involved, and it is believable that this part can be wholly extended accordingly.\n\nWe spent some time thinking about probably robust versions of our approach, but did not succeed. In case robust variants are necessary, confidence sets which are designed for sub-families may be more appropriate e.g. [1].\n\n*[1] Yadkori, Pal,Szepesvari (2012) Improved algorithms for linear stochastic bandits*"}, {"review_id": "vbD9bh6fpL", "reviewer": "Reviewer_4g2j", "summary": "This paper examines the confidence set of an estimator, defined by a likelihood ratio. The contributions stated within the work, alongside my corresponding queries, are outlined as follows:\n* For generalized linear models, we theoretically analyze the geometry of the LR confidence sets under mild assumptions. We show their geometry is dictated by Bregman divergences of exponential families (Chowdhury et al., 2022). \n*We show that the size of the confidence set is dictated by an online prediction game. The size of these sets depends on a sequence of estimators \\{\\theta_s\\}_{s=1}^t that one uses to estimate the unknown parameter \\theta_*. We discuss how to pick the estimator sequence in order to yield a provably small radius of the sets, by using the Follow-the-Regularized-Leader algorithm, which implements a regularized maximum-likelihood estimator. We prove that the radius of the confidence sets is nearly-worst-case optimal, and accordingly they yield nearly-worst-case regret bounds when used in generalized linear bandit applications. However, due to their data-dependent nature, they can be much tighter than this theory suggests. \n*We analyze limitations of classical (un-weighted) LR sets when the underlying conditional observation model is not identifiable. In this case, the resulting (inevitable) estimation bias unnecessarily increases the size of the confidence sets. To mitigate this, we propose an adaptive reweighting scheme that decreases the effect of uninformed early bias of the estimator sequence on the size of the sets downstream. The reweighting does not affect the coverage guarantees of our sets, and utilizes an elegant connection to (robust) powered likelihoods (Wasserman et al., 2020). \n* Thanks to the adaptive reweighting scheme, our sets are very practical as we showcase experimentally. We demonstrate that our method works well with exponential and non-exponential family likelihoods, and in parametric as well as in kernelized settings. We attribute their practical benefits to the fact that they do not depend on (possibly loose) worst-case parameters.", "questions": "* The relationship between LR confidence set geometry and Bregman divergences is briefly discussed on page 6. It would be beneficial to have this connection elaborated upon more thoroughly in the main body of the text.\n\n* Section 2 provides a clear explanation on how to select a sequence of $\\{ \\theta_s \\}_{s=1}^t$ to minimize the radius of the confidence set. However, this connection becomes less clear in Section 3. \n\nMoreover, the paper claims that the radius of the confidence set is nearly-worst-case optimal. Could you please provide further explanation as to why this is the case? While it's clear that the FTRL can lead to nearly-worst-case optimal regret for the online optimization problem, $\\mathcal{R}_t$ defined in $(3)$ appears to be not identical, but smaller than the definition of regret in the online optimization problem. If $\\mathcal{R}_t$ is significantly smaller than the regret of the FTRL algorithm, might our confidence set not be optimal?\n\n* The introduction of a re-weighting scheme is intriguing. However, given that the re-weight $w_t$ is difficult to compute, could you provide any theoretical performance guarantees? Additionally, in Theorem 2, the bias estimate depends on \\norm{\\theta_*}_2^2. Could this potentially conflict with our objective to estimate the confidence set of \\theta_*? Furthermore, in Section 3, we ascertain the geometry of the linear models assuming $w_t = 1$. Is it possible to perform a similar analysis incorporating the re-weighting scheme? Otherwise, the value of the re-weighting scheme might be discounted if we cannot incorporate it into the analysis of simple model\n\n* A query arises from Theorem 3, where \\theta \\in \\mathcal{C}_t satisfies a certain inequality. I am curious about the application of this inequality in estimating the confidence set of \\theta_*, given that the Bregman distance involved depends on $\\theta_*$, which is unknown. Is this result primarily of theoretical interest, or is it of practical use in this context?", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The research question posed in this paper is notably intriguing and holds significant potential for various applications. Furthermore, the innovative approach adopted by the authors represents a substantial contribution to the field.", "weaknesses": "While the paper offers several valuable insights, I noticed that the overall integration of its contributions could be improved. For instance, claimed contributions 1 and 3, which could potentially have been effectively merged, were instead treated separately. This compromise the contribution significantly from my perspective. Furthermore, I have concerns about the clarity and accuracy of some claims. For more specific observations, please refer to the \"Questions\" section. I believe addressing these issues would greatly enhance the coherence and validity of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback on improving the clarity and coherence of our paper. We very much welcome the fact you see our contribution as substantial and we will use your insights to improve the exposition. The reason we separated the exposition of our first and third contribution is because we see the theory and methodology as separate contributions. The theory for GLMs and the proposition of a reweighting scheme can be considered adjacently, as reweighting is a more general approach that is not limited to GLMs.\n            \n We now answer your individual questions in order: \n\n**Q:** *Bregman divergence and confidence sets* **R:** The relationship between Bregman divergence and confidence set is indeed intriguing and we are planning to add more information in a revised version. The main reason it arises is in the study of exponential family likelihoods that generalize the Gaussian case. In the Gaussian case, we can measure the confidence set in an ellipsoid norm, and in GLMs, Bregman divergences are the appropriate generalization. We plan to add more 2d confidence sets for different exponential families to provide intuition in the revised version.\n\n**Q:** Selecting online learners **R:** Any low regret online learning algorithm can be chosen to select $\\\\{\\hat{\\theta}_t\\\\}_t$ as you can see in Eq. (9). We make the FTRL choice because of its well-specified meaning as a regularized maximum likelihood estimator, but considering algorithms based on exponential weights or other types of forecasters is possible too. \n       \n**Q:** *Regret notions* **R:** The two notions of regret are indeed different, but lower bounds on linear regression show that the difference between the two can be at most logarithmic. Furthermore, a good way to convince ourselves that our confidence sets are nearly optimal at least in the Gaussian case is to look at the downstream linear bandit regret. It follows easily from our confidence set size and specification that we achieve optimal regret in a linear bandit application. Therefore, the set being any smaller would imply that we broke through a lower bound for linear bandits, an impossibility. \n\nAdditionally, we would like to point out an *important distinction* between our work and other types of online-to-confidence set conversions. Here, we do not need a regret bound for the online learner to implement our algorithm. Our confidence set will simply *adapt* to the performance of the learner we use. It is therefore not crucial to understand the sharpest possible rates of FTRL on this slightly easier problem. Our theory is mostly derived for validation, but is not necessary for implementation.\n        \n**Q:** *The introduction of a re-weighting scheme is intriguing.* **R:** The reweighting we propose can be difficult to compute in general, but does not have to be. For example, for GLMs, or any likelihood satisfying Ass of Thm. 2 the calculation is rather straightforward. The reweighting scheme is a very important addition for practical purposes, see the gray arrow in Figure 2a). This scheme is a crucial ingredient in making our method competitive with heuristics. \n        \n**Q:** *“In Theorem 2, the bias estimate depends on* $||\\theta_*||$ *conflict with our objective to estimate the confidence set of* $\\theta_*$?*”* **R:** In Theorem 2, the bias does indeed depend on the value of $\\theta_*$, but for our purposes an upper bound on its norm is sufficient. Namely, we merely require having $||\\theta_*||_2^2 \\leq B^2$ throughout the paper (Assumption 1), which is necessary knowledge for competing methods as well. Making the bound loose for the purposes of balancing bias just hampers the sharpness of the confidence sets and not the coverage guarantees.\n        \n             \n**Q:** *Incorporating the reweighing* **R:** Incorporating the reweighing scheme in Section 3 is a challenging problem. We were unable to provide do so, and we find this extension challenging. While the geometry of the set is influenced by the weighting (effects we do not analyze), the size of the set is analyzed with the weighting scheme as well, which gives us the intuition. Arguably, the weighting scheme is in place to counteract undesirable effects of bias, which inflates the regret of the online learner. Therefore, it arguably makes sense to analyze the effects of weighting on the online learning regret. We do agree that in principle though, it would be very interesting to understand the geometry at an even more precise level. For purely theoretical purposes, the weighting can be discarded, since up to constant factors, the resulting set will be equivalent with and without it. However, reweighting observations is of tremendous practical importance, in particular in non-parametric settings, so we are convinced of the scheme's value nonetheless. Thanks to the weighting scheme, our sets should be the go-to practical method in cases where the likelihood is well-specified. \n\nFirst and foremost, we wish to emphasize that Theorem 3 is not needed for the construction of the sets in any way. The theorem is merely there for theoretical understanding. The reason the Bregman divergence depends on $\\theta_*$ is that the likelihood landscape (geometry) is influenced by the true data-generating process beyond the Gaussian case. In case one desires global bounds, a worst-case perspective could be taken.\n"}, {"review_id": "5wqc7OJijS", "reviewer": "Reviewer_XFVf", "summary": "This paper proposed to use the likelihood ratio approach to provide an any-time valid confidence sequence, which is suitable for problems with well-specified likelihood. It discusses how to provably choose the best sequence of estimators and sheds light on connections to online convex optimization. To counteract the initially large bias of estimators, they propose a reweighing scheme. They also provide a non-asymptotic analysis of the likelihood ratio confidence set size for GLM, and performed numerical simulations. \n\n", "questions": "NA", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The idea of using the universal inference method in bandit problems is interesting. \n", "weaknesses": "In bandit problems, the target of interest is regret, and the validity/length of the confidence set is a tool of analysis. One shortcoming of this paper is that there is no regret analysis (of the bandit problem) of the proposed method. One important question is, what is the regret of the proposed method on simple bandit problems such as the K-armed bandit (UCB method gives \\sqrt{KT} regret) and the linear bandit (LinUCB gives \\sqrt{d^2 T} regret). Since bandit is the focus of this paper, without a concrete regret bound (showing that it matches the best existing method), the benefit of the proposed method is not convincing. \n\nThe method proposed in this paper is similar to the OMLE method [1], which has a provable regret guarantee in many RL problems. One interesting question is to study whether the proposed algorithm has benefit over the OMLE algorithm. \n\n[1] Optimistic MLE—A Generic Model-based Algorithm for Partially Observable Sequential Decision Making. \n\nAfter reading the rebuttal: \nI am convinced that a regret bound can be obtained for this method. I trust the authors will add this in the revised version. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. As you mention, the LinUCB analysis uses the radius of the confidence set to derive the overall regret bound for the bandit problem. Of course, we can do this with our confidence sets as well, and in the linear case, obtain immediately the optimal regret. Indeed, the proof is one line, starting from our confidence set diameter, and multiplying with a $\\sqrt{Td\\log T}$ factor due to the elliptical potential Lemma (Lemma 9), we obtain a $ \\sqrt{Td\\log T} \\times \\texttt{confidence parameter}$ regret bound. Since our confidence sets have size $\\mathcal{O}(\\sqrt{d\\log T})$ we match the lower bounds $\\sqrt{T}d$ for the problem up to log-factors for the Gaussian linear model case, i.e. $\\sqrt{T}d\\log T$. Similar steps can be taken for generalized linear models leveraging smoothness and strong convexity constants. We can add these theoretical results in a revised version. \n\nAs to the OMLE paper, this work also uses likelihood ratios to define the confidence set for a family of likelihoods. **However the method significantly differs from our setup.** *They do not use the online prediction game as a comparator for the likelihood ratio in the denominator.* Instead, they use a running MLE estimator as a comparator – not a sequence of estimators viewed as a game. This way they have to resort to the same type of analysis as prior works, say for sub-Gaussian likelihoods when calculating the confidence parameter $\\beta$, and need to adopt the worst-case perspective.\n        \nIn our work, we do not depend on these worst-case analyses, since the confidence set radius is defined *implicitly*, by way of the real-time performance of the online sub-learner, and not its worst-case performance guarantee. This is a **crucial distinction** between our work and other approaches, including OMLE and online-to-confidence set conversions. Additionally, our method can be applied to any likelihood without the need to perform a worst-case/theoretical analysis to get the right confidence parameter *at all*.\n        \nWe invite you to reconsider your score, as our work brings significant theoretical and practical contributions on top of the paper you mention, and we are convinced that the similarities are only superficial. \n"}]

Author rebuttal:
We would like to thank all reviewers for their time and effort spent. We are pleased that most reviewers see the benefits of our work. We hope that our individual responses clarify any misunderstandings and that the reviewers will consider raising their scores if they see fit.

We really believe this method is of great importance to the fields utilizing adaptive inference, and hope that we will get the opportunity to present it to the community. We attach some additional plots for reviewer DGax.


Meta-review: This paper uses a likelihood ratio approach to construct any-time valid confidence sequences for downstream sequential decision making applications. The approach is based on a weighted variant of sequential likelihood ratio (LR) statistics (Wasserman et al., 2020), and builds a confidence set based estimators that construct sequential LR statistics. The paper proposes a specific method to construct such estimators using the Follow-the-Regularized-Leader (FTRL) algorithm in online learning, viewing the confidence parameter minimization as a regret minimization problem, and provide non-asymptotic guarantees, as well as experiments in which the confidence sets are applied to linear and kernelized bandits.

Reviewers generally agreed that the paper's approach is novel and potentially significant. In particular, the results involve an interesting and non-trivial combination of several different techniques (universal inference, FTRL, Bregman information gain, …) from statistics and online learning, and hence may be of interest to multiple communities. As such, there was a consensus that this work should be accepted.

For the final version of the paper, the authors are encouraged to incorporate the reviewers' suggestions, particularly regarding provable regret bounds for the bandit application.
Decision: Accept (poster)