Regret Minimization via Saddle Point Optimization
Authors: Johannes Kirschner
Alireza Bakhtiari
Kushagra Chandak
Volodymyr Tkachuk
Csaba Szepesvari
Venue: NeurIPS 2023 poster (2023)
Keywords: sequential decision-making
decision-estimation coefficient
regret minimization
bandits
reinforcement learning
partial monitoring
TL;DR: We introduce and analyze an anytime variant of the E2D algorithm by proposing the average-constraint decision estimation-coefficient.

Abstract: A long line of works characterizes the sample complexity of regret minimization in sequential decision-making by min-max programs. 
In the corresponding saddle-point game, the min-player optimizes the sampling distribution against an adversarial max-player that chooses confusing models leading to large regret. The most recent instantiation of this idea is the decision-estimation coefficient (DEC), which was shown to provide nearly tight lower and upper bounds on the worst-case expected regret in structured bandits and reinforcement learning. By re-parametrizing the offset DEC with the confidence radius and solving the corresponding min-max program, we derive an anytime variant of the Estimation-To-Decisions algorithm (Anytime-E2D). Importantly, the algorithm optimizes the exploration-exploitation trade-off online instead of via the analysis. Our formulation leads to a practical algorithm for finite model classes and linear feedback models. We further point out connections to the information ratio, decoupling coefficient and PAC-DEC, and numerically evaluate the performance of E2D on simple examples.

Regret Minimization via Saddle Point Optimization
Johannes Kirschner
Seyed Alireza Bakhtiari Department Computer Science
Department of Computer Science
University of Alberta jkirschn@ualberta.cco
University of Alberta sbakhtia@ualberta.cco
Kushagra Chandak
Volodymyr Tkachuk
Department of Computer Science
Department of Computer Science
University of Alberta
University Alberta
tchandaaduallerta..co
vtkachuk@ualberrt.ccm
Csaba Szepesvári
Department of Computer Science University of Alberta
szepesva@uallerta. ca
Abstract
A long line of works characterizes the sample complexity of regret minimiza- tion in sequential decision-making by min-max programs. In the corresponding saddle-point game, the min-player optimizes the sampling distribution against an adversarial max-player that chooses confusing models leading to large regret. The most recent instantiation of this idea is the decision-estimation coefficient (DEC), which was shown to provide nearly tight lower and upper bounds on the worst-case expected regret in structured bandits and reinforcement learning. By parametrizing the offset DEC with the confidence radius and solving the correspond- ing min-max program, derive anytime variant of the -oiimattioo-o-Decission algorithm (ANYTIME-E2D) Importantly, the algorithm optimizes the exploration- exploitation trade-off online instead of via the analysis. Our formulation leads to a practical algorithm for finite model classes and linear feedback models. We further point out connections the information ratio, decoupling coefficient and PAC-DEC, and numerically evaluate the performance of E2D on simple examples.
Introduction
Regret minimization is widely studied objective in bandits and reinforcement learning theory [Lat- limore and Szepesvári 2020a] that has inspired practical algorithms, for example, noisy zero-order optimization e.g.. Srinivas al. 2010) and deep reinforcement learning [e.g., Osband et al. 2016 Cumulative regret measures the online performance the algorithm by the total loss suffered due to choosing suboptimal decisions. Regret is unavoidable to certain extent the learne collects infor- mation to reduce uncertainty about the environment. In other words, a learner will inevitably face the apploratonnexploittiiie trade-off where must balance collecting rewards and collecting information. Finding the right balance the central challenge of sequential decision-making under uncertainty.
More formally, denote by II decision space and O an observation space. Let M be class of models, where f (r My) E M associated with reward function ry - R and observation
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

map M : II + (O)) where ((O) is the set of all probability distributions over O objective is collect as much reward as possible in n steps when facing a model J E M. The learner's prior information is .M and the associated reward and observation maps, but does not know the true instance /" E M.. The learner constructs a stochastic sequence TI....,hhh "n of decisions taking values in IT and adapted to the history of observations Y1 ~ M (m²). The policy of the learner is the sequence of probability kernels Mim = (pt)i=1 that are used to take decisions. The expected regret of a policy Mlm. and model f after n E IN steps is
O The learner's s
Re (Mins (*) max E
Σ (-) - r-)
wlll
The literature studies regret minimization for various objectives, including worst-case and instance- dependent frequentist regret [Lattimore and Szepesvári 2020a]. Bayesian regret (Russo and Van Roy 2014) and robust variants [Garcelon et al. 2020 Kirschner et al., 2020a]. For the frequentist analysis, all prior knowledge is encoded in the model class M. The worst-case regret of policy pi:n on M SuM R2 (#1mm f), and therefore the optimal minimax regret inf, JEM (Mim: J] only depends on M and the horizon n. The Bayesian, in addition, assumes access to a prior v E (M). which leads to the Bayesian regret E [R. (pi:n f)]. Interestingly, the worst-case frequentist regret and Bayesian regret are dual in the following sense [Lattimore and Szepesvári 2019
inf sup (n = sup inf EE (M f)] (E Mi:
Minm FEM
Unfortunately, directly solving for the minimax policy (or the worst-case prior) is intractable. except in superficially simple problems. Ths is because the optimization is over the exponentially large space of adaptive policies. However, the relationship in Eq. (1 has been directly exploited in prior works, for example, to derive non-constructive upper bounds on the worst-case regret via a Bayesian analysis [Bubeck et al., 2013). Moreover, it can be seen as inspiration underlying "optimization-bar -based" algorithms for regret minimization: The crucial step is to carefully relax the saddle point problem in way that preserves the statistical complexity. but can be analyzed and computed more easily. This idea manifests in several closely related algorithms, including information-directed sampling [Russo and Van Roy| 2014 Kirschner and Krause 2018). ExpByOpt [Lattimore and Szepesvári 2020b
Lattimore and Gyorgy 2021], and most recently, the Estimation- To-Decisions (E2D) framework Foster et al. 202 2 2023] These algorithms have in common that they optimize the information trade- off directly, which in structured settings leads to large improvements compared to standard optimistic exploration approaches and Thompson sampling. On the other hand, algorithms that directly optimize the information trade-off can be computationally more demanding and, consequently, are often not the first choice of practitioners. This is partly due to the literature primarily focusing statistical aspects, leaving computational and practical considerations underexplored.
Contributions Building on the results by Foster et al. 2021 we introduce the overage-construined decision-estimate coefficient (dec saddle-point objective that characterizes the frequentist worst-case regret in sequential decision-making with structured observations. Compared to the decision-estimation coefficient of [Foster et al. 2021]. the dee is parametrized via the confidence radius e, instead of the Lagrangian offset multiphirr. This allows optimization of the information trade- off online by the algorithm, instead of via the derived regret upper bound. Moreover, optimizing the dec leads to an anytime version of the E2D algorithm (ANYTIME- E2D) with a straightforward anal- ysis. We also point out relations between the dec the information ratio [Russo and Van Roy| 2016)) the decoupling coefficient (Zhang] 2022 and PAC version of the DEC [Foster
2003). We
further detail how to implement the algorithm for finite model classes and linear feedback models, and demonstrate the advantage of the approach by providing improved bounds for linear bandits with side- observations. I Lastly, we report the first empirical results of the E2D algorithm on simple examples.
1.1 Related Work
There is a broad literature on regret minimization in bandits [attimore and Szepesvári, 2020a
and reinforeement learning (Jin et al., 2018 Azar et al., 2017 Zhou et al., 2021 Du et al. 2021
'To simplify the presentation, we ignore tedious measure- measure-theoretic details in this paper. The reader could either fill out the missing details, or just assume that all sets, unless otherwise stated, are discrete.
"The result by Lattimore and šzepesvári (2019) was only shown for finite action, reward and observation spaces, but can likely be extended to the infinite case under suitable continuity assumptions.
2

---

Zanette et al. 2020]. Arguably the most popular approaches are based on optimism, leading to the widely analysed upper confidence bound (UCB) algorithms [Lattimore and Szepesvári 2020a]. and Thompson sampling (TS) (Thompson, 1933, Russo and Van 2016].
saddle point problem. Degenne al. (2020b) showed that in the structured bandit setting, an algorithm based on solving a saddle point equation achieves asymptotically optimal regret bounds, while explicitly controlling the finite-order terms. Lattimore and Szepesvári [2020b] propose an algorithm based on exponential weights in the partial monitoring setting [Rustichini] 1999] that finds a distribution for exploration by solving a saddle-poing problem. The saddle-pond problem balances the trade-off between the exponential weights distribution and an information or stability term. The same approach was further refined by Lattimore and Gyorgy (202T]. In stochastic linear bandits, Kirschner et al.) (202T) demonstrated that information-directer sampling can be understood as a primal-dual method solving the asymptotic lower bound, which leads to an algorithm that is both worst-case and asymptotically optimal. The explored
A long line of work approaches regret minimization
saddle-pe point approach has been further explored in the PAC setting [e.g.. Degenne et al. 2
Our work is closely related to recent work by Foster et al. [2021] 2023
They consider decision making with structured observations (DMSO), which generalizes the bandit and RL setting. They introduce a complexity measure, the offset decision-estimalin a min-max game between learner and an environment, and provide lower bounds in terms of the offsee DEC. Further, they provide an algorithm, Estimation coommaationtt--aaee Coeenntt---eeiiee to-Diiiioon (E2D) with corresponding worst-case upper bounds terms of the offset DEC. Notably, the lower and upper bound nearly match and recover many known results in bandits and RL. More recently. Foster et al. (2023 refined
coefficient (offset DEC), defined as
the previous bounds by introducing the constrained DEC and a corresponding algorithm E2D+
There are various other results related to the DEC and the E2D algorithm. Foster et al. [202al] show that the E2D achieves improved bounds in model-free RL when combined with optimistic estimation (as introduced by Zhang 20222). ). Chen et al. 2022] introduced two new complexity measures based on the DEC that are necessary and sufficient for reward-free learning and PAC learning. They also introduced new algorithms based on the E2D algorithm for the above two settings and various other improvements. Foster et al. [2022b] have shown that the DEC is necessary and sufficient to obtain low regret for adversarial decision-
An asymptotically instance-optimal algorithm for DMSO has been proposed by Dong and Ma [2022]. extending a similar approach for the linear bandit setting [Lattimore and Szepesvari 2017].
The decision-estimatioo coefficient is also related to the information ratio [Russo and Van Roy 2014 and the decoupling coefficient [Zhang 2022]. The information ratio has been studied under both the Bayesian [Russo and Van Roy| [2014] and the frequentist regret [Kirschner and Krause 2018 Kirschner et al. 2020b 2021 2023] in various settings including bandits, reinforcement learning, and partial monitoring. The decoupling coefficient was studied for the Thompson sampling algorithm
in contextual bandits [Zhang 2022], and RL [Dann et al.) 2021 Agarwal and Zhang 2022]
2 Setting
We consider the sequential decision-making problem already introduced in the preface. Recall that IT is a compact decision space and O is an observation space. The model class M is a set of tuples f = (ry, My) containing a reward function ry II - R and an observation distribution My. II + (O). We define the gap function
A g) (T((T)) (T))
where 7 arg max ren (T) is an optimal decision for model g, chosen arbitrarily if not unique. A randomized policy is a sequence of kernels Mi..- = (14)²= from histories h;-1 = (T1, V1....., TT 1 E (II O)--1 to sampling distributions 9 (II). The filtration generated by the history hy is F.. The learner's s decisions ......, Tr are sampled from the policy ny ~ μ and observations Y1 My- (mx) are generated by unknown true model f E MM. The expected regret under model f is formally defined as follows:
R2 (p f²) = E > Brom(th) (TTe, f`)]
3

---

For now, we do not make any assumption about the reward being observed. This provides additional flexibility to model wide range of scenarios, including for example, duelling and ranking feed-
back Yue and Joachims, 2009 Radlinski et al. 2008, Combes et al. 2015 Lattimore et al. 2018
Kirschner and Krause 2021 (e.g. used in reinforcement learning with human feedback, RI.H) or dynamic pricing (den Boer, 2015]. The setting is more widely known as partial monitoring
Rustichini [199]]. The special case where the reward is part of the observation distribution is called
Recision-making with structured observations [DMSO, Foster et al. 2021]. Earlier work studies the
closely related structured bandit setting [Combes et al. 2017].
A variety of examples acToss bandit models and reinforcement learning are discussed in [Combes cet al., [017 Foster et al., [202]] 2023 Kirschner et al.] (223). For the purpose of this paper, we focus on simple cases for which we can provide tractable implementations. Besides the finite setting where M can be enumerated, these are the following linearly parametrized feedback models.
Example 2.1 (Linear Bandits, Abbe and Long (1999). The model class is identified with subset of Fd and features on E Ed for each π E II. The reward function is (T) = ()(T), and the observation distribution is M = [
The linear bandit setting can be generalized by separating reward and feedback maps, which leads to the linear partial monitoring framework (Lin et al. 2014 Kirschner et al., 2020b]. Here restrict
our attention to the special case of linear bandits with iide-observations [c.f. Kirschner et al.) 2023]
which, for example, generalizes the classical cemi-bandit setting Mannor and Shamir [2011]
Example 2.2 (Linear Bandits with Sade-Ohservationss: As in the linear bandit setting, we have
M C TRdd and features @a E Rd that define the reward functions ry( = (Øx, s'- Observation matrices Ma E " for each æ E Il define m, dimeennniio observation distributions Mf(
N(M+J,, mm,) ). In addition, we assume that कي ~ M Ma., which is automatically satisfied if
o is included in the rows of Mn. ie. when the reward is part of the observations.
3 Regret Minimization via Saddle-Point Optimization
The goal of the learner is to choose decisions π E that achieve a small gap fTT,))) under the true model f* e M. Since the true model is unknown, the learner has to collect data that provides statistical evidence to reject models g # f* for which the regret A(T, g) is large. To quantify the information-regree trade-off, reference model f, the information (or divergence) function is defined by:
divergence D--ll-) defined for distributions in 9 (O). For
1y( g) DKr. (M)(
where (-I-) is the KL divergence. Intuitively, (z 9) is the rate at which the learner collects statistical information to reject E M when choosing E II and data is generated under the reference model f. Note that [ f) = 0 for all f = . and π E II. As we will see shortly, the ingret-information trade-off can be written precisely as combination of the gap function, A, and the information function, Ty. We remark in passing that other choices such as the Hellinger distance are also possible, and the KL. divergence is mostly for concreteness and practical reasons.
To simplify the notation and emphasize the bilinear nature of the saddle point problem that we study, will view A, 1 E TR IR.I [T] x |M| matrices (by fixing canonical ordering on II and M). For vectors μ E _ and // R.MM we will frequently write bilinear forms pA,p v and pl This also means that by convention, fs will always denote a row vector, while v will always denote a column vector. The standard basis for IR. and R.M is (ex)ren and (eg)gEM.
3.1 The Decision-Estimatie Coefficient
To motivate our approach, we recall the decision decision--stimation estimation coefficient (DEC) introduced by Foster et al. 2021 2023), before introducing the main quantity of interest, the avverage-costrraing DEC. First, the offset decision-estimatioo coefficient (without localization) (Foster et al. 2021] is
dec
min ( 9EM
pde, Aul
The tuning parameter > controls the weight of the information matrix relative to the gaps: Viewing the above as two-player zero-sum game, we that increasing X forces the max-player

---

to avoid models that differ significantly from ff under the min-player's is sampling distribution. The advantage of this formulation is that the information term e can be telescoped in the analysis. which directly leads to regret bounds in terms of the estimation error (introduced below in Eq. (8). The disadvantage of the X-parametrization is that the trade-off parameter chosen by optimizing the final regret upper bound. This is inconvenient because the optimal choice requires knowledge of the horizon and a bound on faX d (f). Moreover, any choice informed by the upper bound may be conservative, leading sub-optimal performance.
The constrained
coefficient Foster et al.
2023 is
(fc = min max edeyy Me (LI) 9EM
s.t.
(2)
In this formulation, the max player is restricted to choose models g that differ from f at most by c² in terms of the observed divergence under the min-player's sampling distribution. Note that because ex Fef = 0 for all 6, E IT, there always exists a feasible solution. For horizon n. the radius can be set to c² ~ ЛMM where By is model estimation complexity parameter, thereby essentially eliminating the trade-off parameter from the algorithm. However, because of the hard constraint, strong duality of the Lagrangian saddle point problem (for fixed p)) fails, and consequently, telescoping the information gain in the analysis is no longer easily possible (or at least, with the existing analysis). To achieve sample complexity dec (f), Foster al. 2023 propose sophisticated scheme that combines phased
exploration with a refinement procedure (E2D*) )
As the main quantity of interest in the current work, now introduce the average--onstrrineed decision- eestiinnnstiiation coefficient, defined as follows:
dec min max pAv s.t. pIu S
PE (M))
Similar to the dec,, the parameterization of the dec is via the confidence radius c², making the choice of the hyperparameter straightforward in many cases (more details in Section 3.2). By convexifying the domain P (MV) of the max-player, we recover strong duality of the Lagrangian (for fixed μt). Thereby, the formulation inherits the ease of choosing the e-parameter from the dec while, at the same time, admitting a telescoping argument in the analysis and much simpler algorithm.
Specifically, Sion's theorem implics three equivalent Lagrangian representations for Eq. (3)
dec""())
min max min pAv Mu e²)
(4)
#e (I)) (M) X20
min max pāv M e2) (M (MM))
(5)
min max min ,&v- M(ITpV - 2))
When fixing the outer problem, strong duality holds for the inner saddle-point problem in each line, however, the joint program in Eq. (5) is not convex-concave. An immediate consequence of relaxing the domain of the max player and Eq. (5) is that
(ec < dec (f) min (dec + Ac3
(7)
X20
The t can therefore be understood setting the À parameter of the dee optimally for the given confidence radius e². On the other hand, the cost paid for relaxing the program is that there exist model classes M where the inequality in Eq. 7 is strict, and dec does not lead a tight characterization of the regret Foster et al.] 2023] Proposition 4.4). The remedy is that under a stronger regularity con- dition and localization, the two notions are essentially equivalent [Foster al. 2023
Proposition 4.8).
3.2 Anytime Essimattion-T--Decsiiiii ToDDecisios (Anytime-E2D)
Estimations- De-iesisson (E2D) is an algorithmic framework that directly leverages the decision- estimation coefficient for choosing decision in each round. The key idea is compute sampling distribution 14 E (PT attaining the minimal DEC for estimate fe of the underlying model, and then define the policy to sample ग. ~ 14- The E2D approach, using the dec formulation, is summarized in Algorithm
To compute the estimate fú, the E2D algorithm takes an abstract estimation oracle EST input, that, given the collected data, returns fr M. The final guarantee
[
5

---

Algorithm 1: ANYTIME-E2D
Input: Hypothesis class M, estimation oracle EST, sequence et 2 data Dg
for i = 2, do Estimate f. EDT(D:-1)
Compute gap and information matrices, A and 1, e _
14 arg min (II) maxve (uAv: pl S e?
5 Sample Te ~ and observe ~ My (Te)
Append data D. D U ((TT.))))
depends on the estimation error (or estimation regret), defined as the sum over divergences of the observation distributions under the estimate ft and the true model f":
Est, E Σ jerr
(8)
x since je pe 0. Equation ( is closely related to the total information gain used in the literature information-directed sampling [Russo and Van Roy 2014] and kernel bandits [Srinivas et al. 2010).
Intuitively, the estimation error well-behaved
To bound the estimation error, Foster et al. [202T] rely on online density estimation (also, online regression or online aggregation) [Cesa-Bianchi and Lugosi 2006, Chapter 9]. For finite M,, the default approach is the exponential weights algorithm (EWA), which we provide for reference in Appendix When using this algorithm, the estimation error always satisfies Est, I log(IM) see [Cesa Bianchi and Lugosi, [006] Proposition 3.1]. While these bounds extend to continuous model classes via standard covering arguments, the resulting algorithm often not tractable without additional assumptions. For linear feedback models (Examples 2.1 and 2.2). one can rely on the more familiar ridge regression estimator, which, we show, achieves bounded estimation regret Est, (d For further discussion, see Appendix A.1
With this in mind, we state our main result.
Theorem 1. Let Xe 2 0 be any sequence adapted to the filtration Ft. Then the regret of ANYTIME- E2D (Algorithm with input sequence de satisfies for all n 2
decac er.21 (f:) }
R. I CS8 sup [E|N]
Σ
2 + Est,
where we defined dec2.)(f) = (((() max.E HAD A(uIşv-
As an immediate corollary, we obtain regret bound for Algorithm I where the sampling distribution He is chosen to optimize dec for any sequence
Corollary 1. The regret of ANYTIME- (Algorithm)
with input a 2 satisfies for all 1:
dec (
R, < max
Σ
& Est,
fEI
Importantly, the regret of Algorithm is directly controlled by the worst-case DEC, max (f), and the estimation error Est,- It remains to set of (respectively Ao ap- propriately. For a fixed horizon n, we let o? = Est.. With the reasonable assumption that maxfeM{e "dee "dee""(
is non-decreasing in Corollary reads
Rn < 2n max ( dec JEM VEStn (
(9)
This almost matches the lower bound R. 2 M(ndecf / up to the estimation error and the beforehand mentioned gap between dec; and dec
(F) (/
Foster et al. 2023 Theorem 2.2],
Here, dec cax min.e (()) maw.emutn tuAV plre, E)

---

Setting
dec,
dec
Multi-Armed Bandits
[11//7
2 [1I
Linear Bandits
d/4g
evd
Lipschitz Bandits
2y
2
Convex Bandits
O(d /x)
O
Table 1: Comparison of dec?, and _ for different settings. Bounds between dee,, and dec can be converted using Eq. (7). Refined bounds for linear bandits with side-observations are Lemma
To get an anytime algorithm with essentially the same scaling as in Eq. 9 we set ef = ll)( for finite model classes, and cf Aan if Est, I 3M log(t) for 8M
For linear bandits, dec I evdd (see Section 3.3) and Est,, S dllog(n) Choosing of = d/t recovers the optimal regret bound Rr I Ö(dyn) [Lattimrre and Szepesvári 2020a]. Alternatively, one can also choose X by minimizing an upper bound on maXre[m].FEM dec (f) For example, in linear bandits, hence, for ei d/t, can set X t/4. Further discussion and refined upper bound for linear leedback models are in Section 3.3
dec2f. S A Xeς (see Table 1
Proof of Theorem
Let pr and vi be a saddle-point solution to the offset dec,
dec (ft)
min #e (I)) (M
HAv AepTT
Note that p4 Art - AOGELNUE 2 MGDe - Apilles 2 O, which implies that Xre? S dec Next,
Rn E Σ
Σ E Mr x. - -2) Xolmel - -c)
<
B
max MEEM
/4 j. A EG) + jef
1=1
max HAv A--- 2 + Ae -t:) (T) VE
=
min
So far, we only introduced the saddle point problem by maximizing over f The last equality by our choice of d and ft, and noting that E (MM) can always be realized as a Dirac. Continuing,
decte E
(fr) + AelmeT - 27)
Σ
12
E de r
1 (fe) +
1
xe (fi)
2
ess sup max
3
1
de
2r. (1)
Σ (c++
AE(N FEM
E
We first drop the negative term in (i) and use the beforehand stated fact that Xee < de (ft). The last step, (ii), is taking the maximum out of the sum.
3.3 Certifying Upper Bounds
As shown by Corollary [ the regret of Algorithm 1 scales directly with the dec. For analysis purposes, however useful to compute upper bounds on the dec to verify the scaling w.r.t. pa- rameters of interest. Via the equivalence Eq. (7). bounds on the dec directly translate to the dec (see Table T). For a detailed discussion upper bounds in various models, we refer Foster et al. 2021 Below, highlight three connections that are directly facilitated by the dec.".
7

---

To this end, we first introduce a variant of the dec," where the gap function depends on
dec, (f) WE (E
min max
μÁ SU S.L. pI S
(10)
where ()) - (T)) We remark that for distributions v E (MM and μ 9 (I). the gap A can be decoupled, ,u 85 + μājef, where we defined وy(g) = Tg (T ry (T)) The following assumption implies that the observations for decision at least as informative as observing the rewards.
Assumption 1 (Reward Data Processing). The rewards and information matrices are related via the following data-processing inequality that holds for any p E (IT):
Exculry (r) rr((T)] & V (G
The next lemma shows that under Assumption I dec (f) and dec.c./ (f) are essentially equivalent, at least for the typical worst-case bounds where JEx dec,"" (f) 2 12(c).
Lemma 1. If Assumption 7 holds, then
dec (f) - dec?"())) dec d +
The proof is in Appendix C.1 We remark that Algorithm [ where the sampling distribution is computed dec (fe) and A
achieves a bound analogous to Theorem as long as Assumption Appendix C
holds. For details see Lemma 8
Upper Bounds via Decoupling First, we introduce the information ratio.
(HArv)² 1
V f v)
The definition is closely related the Bayesian information ratio [Russo and Van Roy takes the role of a prior over M. The Thompson sampling distribution is 1u,
2016), where
2EeM Vh
The decoupling coefficient, dc(J). [Zhang 2022 Definition 1] is defined the smallest number K O, such that for all distributions
(M))
1 A inf 720
Σ g.kEM
Mayherg (r. - ry)² + 4n
K
V
rr) (11)
The next lemma provides upper bounds on the dec (f) in terms of the information ratio, which is further upper-boundes by the decoupling coefficient.
Lemma 2. With (f) max,EM min L ( v) and Assumption satisfied, we have
dec ac. ( S Ev (() S e dc(s)
The proof follows directly using the AM-GM incquality, see Appendix C.2 By [Zhang 2022 Lemma
2]. this further implics d < evd.. An analogous result for the generalized information ratio
[Lattiorr and Gyorgy 2021 that recovers rates c² for p 1 is given in Appendix C.4
PAC to Regret Another useful way upper bound the dec is via an analogous definition for the PAC setting [c.f. Eq. (10), Foster et al. 2023]:
pac-dec (())((()))))))
min max 6Fm m (IT PEM
ulsv < à
(12)
Lemma 3. Under Assumption
7
dec ac. (f)
min pac- ac. ep 1/2 (f) + pmmax
pc [0.1]
The proof is given in Appendix B.1 Lemma combined with Theorem leads to (n2333) upper bounds on the regret that are reminiscent of so-called globally observable games linear partial monitoring [Kirschner et al. 2023].

---

Application to Linear Feedback Models To illustrate the techniques introduced, we compute regret bound for Algorithm for linear bandits with side-observations (Examples2..) and (2.2)
Lemma 4, For linear bandity with side- side-observations and divergence Iy(T, - || 9 f)1
pac-dec. 2c. (J) S
min max é (l Sevd
I ( bell
where ((p)= = ((p)=Eren Mn MrMMM
Moreover, denoting Q minpe maxben (b
dec (f) S *mii (() 2/3 1/3 max
The proof is given in Appendix B.2 ment over the standard (t) without further refinement specification of the upper bounds, in the case of linear -odervbbersttions there is an improvement whenever f I max (f). To exemplify the improvement, consider semi- mami-bandit with "revealing" action ît, e.g. Ma 1a- Here, the regret bound improves to R., S min(dy d dl d3//n2/// J, since then pac-dec -e (f) S e. The corresponding improvement in the regime n < dt might seem modest, but is relevant in high-dimensional and non- non-parametric models. Moreover, in (deep) reinforcement learning, nigh-dimensional models are commonly used and the learner obtains side information in the form of state observations. Therefore, is plausible that the n2/3 rate is dominant even for a moderate horizon. Exploring this effect in reinforcement learning is therefore an important direction for future work.
While in the worst-case for linear bandits, there is no improve-
Notably, this improvement not observed by upper confidence bound algorithms and Thompson sampling. because both approaches discard informative but suboptimal actions early on [c.f. Lat timore and Szepesvari 2017], including the action á in the example above. E2D for constant offset parameter À > O. in principle, attains the better rate, but only if one pre-commits to fixed horizon. Lastly, we note that a similar effect was observed for information-direcdt sampling in sparse high-dimensional linear bandits Hao et al. 2020
3.4
Computational Aspects
For finite model classes, Algorithm can be readily implemented. Since almost no structure is imposed on the gap and information matrices of size [II x [M], avoiding scaling with III |M] seems hardly possible without introducing additional assumptions. Even in the finite case, solving Eq. (3) is not immediate because the corresponding Lagrangian is not convex-concave. A practical approach is to solve the inner saddle point for Eq. (5) as a function of X. Strong duality holds for the inner problem, and one can obtain solution efficiently by solving the corresponding linear program using standard solvers. then remains to optimize over 2 0. This can be done, for example, via a grid search over the range [0, max "ddee" (f)].
In the linear setting, the above is not satisfactory because most commonly M is identified with param- eters in Rdd As noted before, ridge regression can be used instead of online aggregation while preserv- ing the optimal scaling of the estimation error (see Appendix A.I]). The next lemma further shows that the saddle point problem Eq. (3) can be rewritten to only scale with the size of the decision set [II].
Lemma 5. Consider linear bandits with side observations, M Rd and quadratic divergence, [y( = || - II?,, and denote op = ΣnEu 2r and ((p) Exen Mn Mq. Then
dec o (f))
min min (ax - Φur f.) + 41 X (U) bell
|l ( +
Moreover, the objective is convex in μ (1I).
The proof is straightforward calculation provided in Appendix Note that the saddle point expression is analogous to Eq. (5). and in fact, one can linearize the inner maximization over (IT). such that the inner saddle point becomes convex-coneave. This leads to expressions equivalent to Eqs. ( and (6). albeit the objective is no longer linear in E (II). We use Lemma 5 employ the same strategy as before: As a function of À > 0, solve the inner problem the expression in Lemma convex program with IIT] variables and [T constraints (Appendix D). Then all that remains is to solve a one-dimensional optimization problem over E [0, max ma 6 (dec((()) We demonstrate this approach in Appendix E to showcase the performance of E2D on simple examples.
for example,

---

4 Conclusion
We introduced ANYTIME-E2D, an algorithm based on the estimation-to-dee sequential decision-making with structured observations. The algorithm optimizes the average- constrained decision-making coefficient, which can be understood as reparametrization of the corresponding offset version. The reparametrization facilitates an elegant anytime analysis and makes setting all remaining hyperparameters immediate. We demonstrate the improvement with a novel bound for linear bandits with aude-observations, that is not attained by previous approaches. Lastly, discuss how the algorithm can be implemented for finite and linear model classes. Nevertheless, much remains be done. For example, to round, and therefore, it seems wasteful to solve Eq. (3) from scratch repetitively. Preferable instead would be incremental scheme that iteratively computes updates to the sampling distribution.
framework for
can expect the reference model change very little from round
Acknowledgments and Disclosure of Funding
Johannes Kirschner gratefully acknowledges funding from the SNSF Early Postdoc.Mobility fellow- ship P2EZP2_199781
References
Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts. In Proceedings of the Sixteenth International Conference on Machine Learning. ICML '99, pages 3-11, 1, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1-55860-612-2.
A. Agarwal and T. Zhang. Model-based with optimistic posterior sampling: Structural conditions and sample complexity. arXiv preprini arXiv:2206. 276,09290007.599 2022.
M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272. PMLR, 2017.
S. Bubeck, O. Dekel, T. Koren, and Y. Peres. Bandit convex optimization: /sqrtt regret in one dimension. In Conference on Learning Theory, pages 266-278. PMLR, 2015.
N.
and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
F. Chen, S. Mei, and Y. Bai. Unified algorithms for rl with decision-estimatiee estimation coefficients: No-regret, pac, and reward-free learning. arXiv preprint arXiv:2209.11745, 2022.
R. Combes, S. Magureanu, A. Proutiere, and C. Laroche. Learning to rank: Regret lower bounds and efficient algorithms. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 231-244. ACM, 2015. ISBN 978- 1- 4503-3486-0.
R. Combes, S. Magureanu, and A. Proutiere. Minimal exploration in structured stochastic bandits. Advances in Neural Information Processing Systems, 30, 2017.
C. Dann, M. Mohri, T. Zhang, and J. Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances Neural Information Processing Systems, 12055, 2021.
R. Degenne, P. Ménard, X. Shang, and M. Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432-2442. PMLR, 2020a.
R. Degenne, H. Shao, and Koolen. Structure adaptive algorithms for stochastic bandits. In D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 14522242. PMLR, 13-18 Jul 2020b. URL attps://proceee hhtp:////pcceeingga mlr, www.srssssvee.. wwteess/vvvi////// /ew1////ededd.bbbbee.e html
10

---

A. V. den Boer. Dynamic pricing and learning: Historical origins, current research, and new directions. Surveys Operations Research and Management Science, 20(1):1-18, 2015.
K. Dong and T. Ma. Asymptotic instance-optimal algorithms for interactive decision making. arXiv preprint arXiv:2206.0233: 2022.
Du, Kakade, Lee, S. Lovett, Mahajan, W. Sun, and R. Wang. Bilinear classes: structural framework for provable generalization in rl. In International Conference Machine Learning, pages 2826-2836. PMLR, 2021.
J. C. Dunn and S. Harshbarger. Conditional gradient algorithms with open loop step size rules. Journal of Mathematical Analysis and Applications, 62(2):432-444 1978.
D. J. Foster, M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112. 134887 2021.
D. J. Foster, N. Golowich, J. Qian, A. Rakhlin, and A. Sckhari. A note on model-free reinforcement learning with the decision-estimation coefficient. arXiv preprint arXiv:2211. 2tti:22211.12500, 2022a.
D. J. Foster, A. Rakhlin, A. Sckhari,, and K. Sridharan. On the complexity of adversarial decision making. arXiv preprint arXiv:2206. 13063,, 2022b.
D. J. Foster, N. Golowich, and Y. Han. Tight guarantees for interactive decision making with the decision-estiman coefficient. arXiv preprint arXhv:2301.082/5 2023.
M. Frank and Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-11) -10, 1956.
E. Garcelon, B. Roziere, L. Meunier, Tarbouriech, O. Teytaud, A. Lazaric, and M. Pirotta. Adver- sarial attacks on linear contextual bandits. Advances in Neural Information Processing Systems, 33:14362-14373, 2020.
A. György, D. Pál, and C. Szepesvári. Online learning: Algorithms for big data. Lecture Notes, 2013.
B. Hao, T. Lattimore, and M. Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753-10763, 2020.
M. Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning, pages 427-435. PMLR, 2013.
C. Jin, Z. Allen-Zhu, Bubeck, and M. Jordan. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
J. Kirschner and A. Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pages 358-384. PMLR, 2018.
J. Kirschner and A. Krause. Bias-robust bayesian optimization via dueling bandits. In International Conference on Machine Learning, pages 5595-5605. PMLR, 2021.
J. Kirschner, I. Bogunovic, S. Jegelka, and A. Krause. Distributionally Robust Bayesian Optimization. In Proc. International Conference Artificial Intelligence and Statistics (AISTATS), August 2020a. URL http::/pproceedinggs mlr press/v108/ http://www.r..rccchooo/////reeee
pdf
J. Kirschner, T. Lattimore, and A. Krause. Information directed sampling for linear partial monitoring. PMLR, 2020b.
In Conference on Learning Theory, pages
J. Kirschner, T. Lattimore, C. Vernade, and C. Szepesvári. Asymptotically optimal information- directed sampling. In Conference on Learning Theory, pages 2777 28211. PMLR, 2021.
J. Kirschner, Lattimore, and A. Krause. Linear partial monitoring for sequential decision making: Algorithms, regret bounds and applications. Journal of Machine Learning Research, August 2023.
Lattimore and Gyorgy. Mirror descent and the information ratio. Conference on Learning Theory, pages PMLR, 2021.

---

T. Lattimore and C. Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statisties, pages 728-737 PMLR, 2017.
Lattimore and C. Szepesvári. An information-theoortic approach to minimax regret partial monitoring, In Conference Learning Theory, pages 21 11-2139. PMLR, 2019.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020a.
T. Lattimore and C. Szepesvári. Exploration by optimisation in partial monitoring. In Conference on Learning Theory, pages 2488-2515. PMLR, 2020b.
T. Lattimore, B. Kveton, S. Li. and C. Szepesvári. Toprank: A practical algorithm for online stochastic ranking. In Advances Neural Information Processing Systems, pages 3949-3958. Curran Associates, Inc., 2018.
T. Lin, B. Abrahao, R. Kleinberg, J. Lui, and W. Chen. Combinatorial partial monitoring game with linear feedback and its applications. In International Conference on Machine Learning, pages 901-909, 2014.
S. Mannor and O. Shamir. From bandits experts: On the value of side-observations. Advances in Neural Information Processing Systems, 24, 2011.
1. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016.
Radlinski, R. Kleinberg, and T. Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th International Conference on Machine Learning, pages 784-791. ACM, 2008.
D. Russo and B. Van Roy. Learning to optimize via information-direectd sampling. Advances in Neural Information Processing Systems, 27, 2014.
D. Russo and B. Van Roy. An iettormmtiionthhoreeee analysis of thompson sampling. The Journal of Machine Learning Research, 17(1)24442-447, 2016. 2016.
A. Rustichini. Minimizing regret: The general case. Games and Economic Behavior, 29(1-2): 224-243, 1999.
Shalev-Shwarde Shwartz et Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. International Conference on Machine Learning (ICML), 2010.
W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294 1933.
Y. Yue and T. Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th International Conference on Machine Learning, pages 1201-1208. ACM, 2009.
A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill. Learning near optimal policies with low inherent bellman error, In International Conference on Machine Learning, pages 10978-10989, PMLR, 2020.
T. Zhang. Feel-good thompson sampling for contextual bandits and reinforcement lcarning, SIAM Journal on Mathematics of Data Science, 4(2):834-857) 2022.
D. Zhou, Q Gu, and C. Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pages 4532-4576. PMLR, 2021.
12

---

Algorithm 2: Exponential Weights Algorithm (EWA) for Density Estimation
Input: Finite model class M, data D; {(V1, mT),... (ye, me)), Learning rate > Ex log M (3))
Define L(f)
Let p(f) & exp(-n)(()) For convex M: Return > _SEMP(f)f
3
4 Else: Return f ~ p(-).
A Online Density Estimation
For any f E M and π E II, we denote by ff the the density function of the observation distribution ( w.r.t reference measure over the observation space O Consider finite model class M and the KL divergence,
plu IT, 9) p(y| f) )
ex = (xx)
log
(13)
In this case, the estimation eтror can be written as follows:
Est,,
E
C.e J.. ee.-
E
log(p(u me, (t), p')pp(pllTeee.. fo)
E
log
1
Σ log
p(uel (T. fa)
((ye Te. fo)
The last line can be understood as the estimation regret the estimates fi...., under the logarithmic loss. classical approach control this term is the exponential weights algorithm (EWA) given in Algorithm 2 For the EWA algorithm, we have the following bound.
Lemma 6 (EWA for Online Density Estimation). For any data stream {y1, T1..... predictions fu.... fu obtained via Algorithm 2 with r = satisfy
Vns nnd the
Est, E
Σ log
inf 9EM
log (p( log(IM))
(14)
p(uel 1.)
For proof, see Cesa-Biaaccii and Lugosi 2006 Proposition 3.1].
A.1 Bounding the Estimation Error of Projected Regularized Least-Squares
In this section, we consider the linear model from Example 2.2] We denote by ||- || the Euclidean norm. For simplicity, the observation maps M E Rmxd are assumed to have the same output dimension E N. The observation distribution is such that y, Mx f" &,, where random noise such that [g] 0 and E, [[] < o². Here, Ee[-] E[- [T W1...., TT-1, M--1, the conditional observation in round including the decision ne chosen in round t.
IR" is
We will use the quadratic divergence ex exT 1 M f) This choice corresponds to the Gaussian KI, but we not require that the noise distribution Gaussian the following. In the linear bandit model, this choice reduces to e, er
(Ø=.9 f)
Let K C. Rd be closed convex set. Our goal is to control the estimation regret for the projected regularized least-squares estimator,
f. arg min fek
Σ Mr. 12 115 -Projv,
V.
M ys
(15)
where Vi a positive definite matrix, V = Σ5=1 M Mr. + Vo and Projy, (.) is the orthogonal
projection w.r.t. the || llv, norm. For K = Rd and Vo = 1ld, this recovers the standard ridge
We added factor of for convenience.
13

---

regression. The projection is necessary to bound the magnitude of the squared loss, and the result will depend on an almost-surely bound on the "observed' diameter,
max max | g)ll feeK #ell
Recall that our goal is to bound the estimation error,
Ma. (f" -fill]
Est,
C.e j.leeeer er
(16)
We remark that one can get the following naive bound by applying Cauchy-Schwarz:
(f fi) M -1 fulit - O(d log(n)²)
(17)
The last inequality follows from the elliptic potential lemma and standard concentration inequalities [Lattimree and Szepesvári, 2020a Lemma 19.4 and Theorem 20.5]. However, this will lead to an additional d-factor the regret that can be avoided, as see next.
For K = R&, mme-dimensional observations and noise bounded in the range [-B, B.BB B], one can also directly apply [Cesa-Biande) and Lugosi 2006 Theorem 11.7] to get Est, OlBBdlog(n)) thereby improving the naive bound by a factor d In). This result is obtained a more general setting, where assumptions, other than boundedness, are placed the observation sequence y/..... Vn- Here we refine and generalize this result in two directions: First, we allow for the more general feedback model in with multi-dimensional observations (Example 2.2p. Second, directly exploit the stochastic observation model to obtain a stronger result that does not require the observation noise to be bounded.
Theorem 2. Consider the linear observation setling with additive noise and quadratic diver- gence ex 1 f)l described at the beginning of this section. Assume that M, [| g)ll B and E [[[E]]?]] S 0². Then
det Vn det Vo
Est, (o² + BB log
in addition ||M+I| S I. and Vo nl then Est, (o² B²) log (1 +
nL? "j
Remark 1. Note that by the [Lattimore and Szepesvári 2020a Theorem 19.4], log further be upper bounded by d dlog
det Va det det Vo
can
[IaceVotnL** dddetVV))taal which effectively results the desired bound.
Proof. The proof adapts György et al. 2013 Theorem 19.8] to multi-dimeensionll observations and takes advantage of the stochastic loss function by taking the expectation.
First, define l(f)) = 1lM 12. Then, using that E, [yd] = Mr.
Est, E
|| (f" (f- f1)1
E
M fe yell2 - 1 Mr, yr 11
E
4(f.)) 4(5))
Further, by directly generalizing [György et al. 2013
Lemma 19.7], we have that
((64))44(f S V4.0) = (Mr,
v)) TM. V.D.V,-M., Mn, (Mr. ve) (18)
14

---

We now start upper bounding the estimation error,
Est,
| + E
(le(wr) (((w)++))
(6)
(Er + Mf fc-1)) Vi MMx, V (5t + Mrr (f - f(-i))
|| E
(08)
| + IE
M. Vo Ma.Si)
+E
Σ
Fe M.M V M Ft)
1=1
(10)
|1 + EB
Amax (Mxr MM..))l
E
Amax (Ma, V 11bx)13)
Mn,
1=1
11 + (0² + BE maxx Ve Vi- Man)
(19)
The inequality (i) follows from (haaeev Swwwrrtz et 2012, Lemma 2.3]. For (it) we used Eq. (8
For (dii) we used that Eg = O. In (iv), we introduce the maximum eigenvalue Amax (A) for
A ma and denote It Mr. (f fi-1). Lastly, in (v) we used that | S B and
E. [IIG]]]]]]] o²
We conclude the proof with basic linear algebra. Denote by (A) the i-th eigenvalue of matrix M E R=xm Using the generalized matrix determinant lemma, we get
det(Vi-1) = det(VV - MT, Mm.)
dee(VV) det(1 MT. V
= dee((V) II [1 AcMM V MM.))
Note that de Ae VE=1 MM.)) E (0, 1]. Next, using that log(1 - x) S x for all x < 1, we get that
log (V-(() dct(Vi)
log(1 - V. Mx s A.M V. Mx.)
1=1
Rearranging the last display, and bounding the sum by its maximum element, we get
Aunax (M ne V Mx.) S CMM V. Ma.) I log dVt();)) (det(V(-1)
(20)
The proof is concluded by combining Eqs.
19 and 20p.
Remark (Expected Regret). The beauty of Theorem Dis that the proof uses only in-expectation arguments. This is unlike most previous analysis, that controls the regret via controlling tail-events, and bounds on the expected regret are then derived a-posteriori from high high-probability bounds. In the context linear bandits, Theorem leads bound on the expected regret that only requires the noise variance to bounded, whereas most previous work relies on the stronger sub-Gaussian noise assumption [e.g. Abbasi-Yadkori al. 2017).
Remark 3 (Kernel Bandits/ / Bayesian Optimization). Using the standard 'kernel-trick', the analysis can further be extended to the non- narameraitriic setting where M is an infmite-dimmesioonll reproducing kernel Hilbert space (RKHS).
B PAC to Regret Bounds
B.1 Proof of Lemma
3
Proof.
The Lagrangian for Fq. 12) is
pac-dec. o (f) min min max 850 (
X pe (M)
15

---

Reparametrize any μ (II) as p(p) = (1 p)en; + 1/2. We bound dec by a function of pac-dec. Starting from Eq. we have
dec. aa (f) = min min
max uÁSv - - X20 (T) (M)
min min
max A20 ( (M)
RA M
min min
min X20 0SPS p (T)
max + puz Aull de
S min min min
81 + puzaies Aplelfp de
X20 OSPS1 (I) (M)
min max dzv N(u2lşu - +ppamax USP51 X (2 (M)
min min
min pac-dec aed (f) pp
0SPS1
B.2
Proof of Lemma
Proof of Lemma
For the first part, note that
pac-dec
min min max 6Gv - AullV + Xe? م (I) 220 (M)
min min max max 9) (0 - ~119 1000-liip fllv Xc²
(C(((T A20 bell 3EM
min min max 6nz, f) + 41 1106 [106l1210)= + 2c²
(1) X20 Bell
(4))
min min max - μЕ)((M X20 bell 4A
1
| 1100 (P( 2
min maxell@ellv(a))
μé (a) bell
(181)
evd.
Equation (i) follows by computing the maximizer attaining the quadratic form over M = Rd, The inequality (wi) is by definition of nī and the last inequality (1ii) by the assumption that the reward is observed, respectively, Φ M Mr, and the Kiefer-Wolfowizz theorem.
The second part of the statement follows by combining Lemmas and
C
Coefficient Relations Results and Proofs
Lemma 7, Assume Assumption 7 holdds, iee.
(m(r, - r2)))² S pI
(21)
Then
2
Σ u(rs T3)0//
Σ (plr, - -ry)) S &uls..
Proof. First Jensen's 's inequality, then Eq.
21
16

---

C.1 Proof of Lemmal
Proof of Lemmal Note that
dec (f)
min max pāv (EP(T) PEP(M)
s.t.
plpu S 2
min max (EP(I) (EP(M)
p
E (1)
s.t.
gEM
min
,AS + Vulsv
ulsu S?
μEP(I)) PEP(M)
Sc+ min max pAS μEP(I)) (EP(M)
s.t.
pllu
dec
s.t.
p
where the first inequality is by Lemmal by- s we get left inequality.
Also, by lower bounding the sum in the second inequality
C.2 Proof of Lemma
Proof of Lemma For the first inequality, using the definition of dec," (J,A,) and the AM-GM inequality:
decacs(1 (f) = min max min vā Autzv A6
X20 wE PE
I min max min X>0 (M) (E) 4 + Ac²
(22)
min V()
(23)
As0
41
Further, by Eq. 11 and Assumption
we have p. 1 AR S / K ConneMPpheene (rg - rr S
V kkpp which gives v()) S K. Plugging this into Eq. (23) gives the second inequality.
C.3 Regret bound for Algorithm defined for A, and dec
Lemma 8. If Asssupption 7 Tholds, then the regret of ANYTIME-E2D (Algorithm) 7 with A replaced
with A is bounded as follows:
decac. ac (f)
R. S
max IEE
2
Σ
2 + Est, + VnEst,
Proof. The proof follows along the lines of the proof of Theorem The main difference is that when introducing A, we get a term that captures the reward estimation error:
R, S
Σ E. deca: (f:) de 27) +
+ E ( 1=1
(24)
< max max (E)n) JEM
dec (f)
}
(e) + (ertt + VnEst, Σ 1=1
(25)
E
For the last inequality, we used Cauchy-Schward and Assumption to bound the error term,
E (ellr - -r.-)] s
E >
(HelT r) <
Mel j. VnEst,
17

---

C.4 Generalized Information Ratio
The generalized information ratio [Lattimore and Gyorgy 2021 for p E PII,, e (M). and is defined as
(HDrDa)
V Wa (H, v))
(26)
For a = 2, we get the standard information ratio introduced by Russo and Van Roy (2014) with as a prior over the model class M. Define (a(f) max.EM minue ((TT) Va, (H, v). To upper bound dec we have the following lemma.
Lemma 9, For the reference model J, the ac-dec can be upper bounded as
d (f) S min (Ar a T ())= xc A50
(27)
for a >
Proof. We start by noting that for 21, .1,...,, La O, from AM-GM we have that a( .22 ...) <
n-1
31 Ta. Substituting 22 Dz
Taa we get xz 22
(a 1)22. Writing
T A and 22 a- (HAv)a Aplyv
and using the previous inequality with the dec," program
gives the result.
The information ratio o (14, v) can be thought of the Bayesian information ratio in [Russo and Van Roy| [014]] where the expectation is taken over the distribution v of possible environments. However, for information gain I,. [Russo and Van Roy [014] entropy difference in the posterior distribution of o before and after the observation is revealed.
C.5 Proof of Lemma 5
Proof of Lemma 5
dec a (f:) = min min max max mox((os g) (dpp fa) - A11g- - felle(n) + Ac²
(II( X20 bEll 9EM
min min max X20 (1)) bell
Φp. fi) +
4A 1106 + 2c?
1
(28)
The first equality is by definition, and the second equality follows from solving the quadratic
maximization over E M = Rdd To show that the problem is convex in μ4, note that taking inverses of positive semi-definite matrices X,Y Y is convex function, i.e. ((1 - -) + +
(--n)x-- + y- In particular, V(( - n)j + mP2) = (1 - (M)) V (22) With this the claim follows.
D Convex Program for Fixed À
Take Eq.
28 and fix À > 0. Then we have the following saddle- point problem:
min max per fu) (II) bell
1
4x 110b 1 + AE?
1
1
Xa2
min max (0r Gy, Sa) (I) BEll
+ 41
| [00bl
Up to the constant additive term, this saddle point problem equivalent to the following convex program
min
s.t.
y 2 (Ør Qn fi) + 41
10b 100012
V6 W
VERR
1p = 1
My > 0
VT
18

---

E
Experiments
All experiments below were semi-bandit problem with a "revealing action", alluded to in the paragraph below Lemma 4 Specifically, we assume a semi-bandit model where M = R and the features are 6x Rdd For an instance f E MM, the reward function is Ty. (Øx, f*) for all π 11. There is one revealing (sub-optimal) action स + Tj.. The observation for any action o ß is
(x) f()..
(29)
Define Ms [ ................................ mmm Then the observation for action # is
My. (f) . 1a)
(30)
Thus, the information for any action π + के is
0²
[g(
( 9 f)²
(31)
while the information for action म is
a² 15 R) 7 M f)12=
o² Σ
(o - f)²
(32)
For this setting Est, Oddlog(n) (see Appendix A.1
E.1 Experimental Setup
Our main objective to compare our algorithm ANYTIME-EE2D the fixed-horizon E2D algorithm by Foster et al. 202T]. ENDDMMF-E2D and E2D were implemented by using the procedure described
in Section 3.4 Both ANYTIME-E2D and E2D need to solve the inner convex problem in Lemma 5 To do so use Frank-Wolt [Frank and Wolfe 1956 Dunn and Harshbarger, 1978 Jaggi 2013
for 100 steps and warm-starting the optimization at the solution from the previous round, 14-1-
For ANYTIME-EE E22 we further perform a grid search over À E [0, maX e dec (g)] (with a discretization of 50 points) to optimize over lambda within each iteration of Frank-Wolle the E2D and ANYTIME- E2D algorithm we used the version with the gaps A replaced with 4,, since noticed that both algorithms performed better with A For E2D, the scale hyperparameter À was set using X / [og(n] as mentioned in Foster et al. 2021 Section 6.1.1]. While for ANYTIME-
For both
E2D we set the hyper-parameter ot = d/t. Further, we compare standard bandit algorithms: Upper Confidence Bound (UCB) and Thompson Sampling (TS) [Lttimore and Szepesvári] 2020a]
E.2 Experiment 1
In this experiment, we aim to demonstrate the advantage of having an anytime algorithm. Specifically,
we tune À in the E2D algorithm for different horizons n = 200, 500, 1000, 2000, but run it for fixed horizon of than E2D when À was tuned for the incorrect horizons (i.c. n = 200, 500, 1000). The feature dimension is d = 3. The number of decisions is [I| 10. We generated the features Φ for each II and parameter f* Rd randomly the beginning and then kept them fixed throughout the experimentation. 100 independent runs were performed for each algorithm.
2000. As such, we expect algorithm ANYTIME-E22 to perform better
The results of the experiment can be seen as the left plot in Fig. [ As expected, our algorithm ANYTIME-E2D performs better than E2D (for 200, 500, 1000). This indicates that the E2D al- gorithm is sensitive to different settings of X, which is problematic when the horizon is not known beforehand. Whereas our ANYTIME- BED algorithm performs well even when the horizon is not known.
E.3 Experiment 2
In this experiment, we investigate the when < d As pointed out below Lemma 3 expect improvement in this regime the regret bound of our algorithm is R,, min(dynn d ///3,2///
19

---

TS
UCB
F2D-2000
F2D-500
F2D-1000
R2D-2000
AnytimeF2D
30
25
20
20
regia
reggel
15
10
0
0 500
1000
1500
2000
200
400
600
800
1000
step
step
Figure 1: Running ANYTIME-E22 E2D, TS, UCB, and E2D optimized for different horizons
{200, 500, 1000, 2000}. Left: The result for horizon 2000, and the feature space dimension d = 3. Right: The result for horizon 1000, and the feature space dimension d = 30.
while the default, fixed-horizon E2D algorithm cannot achieve these bounds simultaneously and one has to pick one of d or /3/33 beforehand for setting the scale hyperparameter It is standard that the choice of À is made according to the d regret bound for E2D Foster et al. [2021 (which not optimal when n < d²), especially, if the horizon is not known beforehand. Thus, we set the horizon to 1000 and the dimension of the feature space d = 30, which gives us that n = 1000 < 810000 d². The rest of the setup and parameters are the same as in the previous experiment except for the features o and f" which again chosen randomly in the beginning and then kept fixed throughout the experiment.
The results of the experiment can be seen as the right plot in Fig. [ As expected, our algorithm ANYTIME-E2D performs better than E2D, UCB, and TS. This indicates that indeed, ANYTIME- E2D likely setting À appropriately achieve the preferred d' d3 regret rate for small horizons. The poor performance of the other algorithms can be justified, since E2D is optimized based on the worse d regret rate (for small horizons), while the UCB and TS algorithms are not known get regret better than d. n.
20


Reviews:
[{"review_id": "qcxxNCSZXJ", "reviewer": "Reviewer_ye2a", "summary": "This paper focuses on regret minimization in sequential decision-making through min-max optimization. The authors introduce an anytime variant of the estimation-to-decisions algorithm that utilizes the average-constrained decision-estimation coefficient. The proposed algorithm is shown to effectively balance exploration and exploitation. The algorithm achieve a slightly improved regret performance in the context of high-dimensional linear bandits.  ", "questions": "Please see the weakness. ", "limitations": "No", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper proposed anytime variant of the estimation-to-decisions algorithm and show the algorithm could potentially improve the linear bandits for a given fixed period.", "weaknesses": "1) A major concern is the contribution of the paper compared to the existing literature, particularly the work by Foster et al. in 2021 and 2023. The concept of average constrained DEC appears to be very similar to the (constrained) DEC introduced in Foster et al.'s papers. It is unclear what distinguishes the introduction of the average constrained DEC in this paper and what advantages it brings. \n\n2) The min-max problem in E2D algorithm is inefficient to solve in general, where the paper needs to find the dual variable via grid search and the choice of stepsize could be an issue.\n\n3) While the paper states that the formulation of the average DEC leads to a practical algorithm, it would be more convincing to provide numerical results to support this claim. Comparisons with Foster et al.'s work from 2021 and 2023, as well as classical methods like UCB, Thompson sampling, and Information Direct Sampling, would justify the practicality and effectiveness of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and valuable comments. We address the points raised below:\n\n**Contributions compared to the existing literature:**\n\nWe discuss the relation to the existing E2D literature in detail in Section 3.1. While our results build on the framework by Foster et al (2021; 2023), we make several non-trivial and practically relevant contributions:\n- The anytime analysis and bounds are novel. The anytime upper bound deviates from the proof by Foster et al (2021) in a non-obvious way.\n- The algorithm is different from the prior work in that the trade-off parameter is chosen for the current estimated model $\\hat f_t$; The suggested choice by Foster et al (2021) is optimized for the worst-case, which, as we show, can lead to suboptimal performance (see Appendix E for numerical results).\n- The anytime analysis and bounds lead to improved regret in linear bandits models in the regime $n < d^2$ (resp. up to $n < d^4$ in linear feedback models), which is relevant in high-dimensional and kernel bandits - and we are not aware of a similar result in the literature (Remark 2). Note further that the E2D algorithm by Foster et al (2021) uses a fixed trade-off parameter, therefore cannot achieve the optimal regret rate on different horizons simultaneously (again - we are not aware of any other approach that achieves this).\n- We explicitly derive the E2D objective for linear bandits, avoiding a computational dependence on the (continuous) model space (Lemma 6). This is important because so far it was left unclear whether E2D can be implemented even in simple case like linear bandits.\n- *We implement our approach, the E2D baseline and UCB algorithm in Appendix E* - these are the first empirical results for E2D that we are aware of.\n- We prove bounds on the estimation error for regularized least squares in linear feedback models (Theorem 2). We believe that it is important to highlight that a standard least squares estimator is feasible as an estimation oracle in the E2D framework.\n\n*To conclude, we strongly believe that we make several novel and valuable contributions to the E2D framework propsed by Foster et al (2021, 2023).*\n\n**Solving the minimax problem**\n\n- It is correct that solving the minimax problem requires a one-dimensional line search (which we show is feasible at least in smaller examples, see Appendix E). It is currently unclear whether exactly solving the minimax problem is efficient. \n\n**Numerical results**\n\n- While our focus is on the anytime analysis, we do provide numerical results in Appendix E (including E2D from Foster et al (2021), Thompson Sampling and UCB).\n\nWe will update the submission to reflect these points better.\n\nWe further noted that this review gives low scores for presentation and soundness. In addition to the contributions highlighted above, we kindly ask the reviewer to clarify further issues with the presentation and soundness of the paper. We will be happy to provide further clarification."}, {"review_id": "JtDBN3u3ya", "reviewer": "Reviewer_j2sL", "summary": "This paper studies the estimation-to-decisions framework for sequential decision-making problems with structured observations. They propose the ANYTIME-E2D algorithm, improving precious approaches with a novel bound for linear bandits. Numerical simulations are presented to show the performance of their algorithm against the baselines.", "questions": "As is discussed in the Weakness part, I hope the authors could provide more explanations and examples about the advantage of the proposed new objective and the anytime variant algorithm.", "limitations": "I don't see any limitations or potential negative societal impact of this work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is in general well-written and the overall structure is nicely organized. The proofs seem to be theoretically rigorous. \n- The significance of the paper is relatively high, since the proposed algorithm can be applied to linear bandit settings and is achieving improved rates in the high-dimensional regime, which is getting increasing attention in the literature. ", "weaknesses": "- My first concern is the originality and significance of this work, over the existing E2D papers. It is claimed that they introduce the new objective $\\operatorname{dec}_\\epsilon^{a c}$, which enables the optimization of the information trade-off directly instead of the regret bound. However, no clear evidence is presented to validate the superiority of the new objective. I wonder if there are any special cases where the original objective fails to balance the trade-off, while the new one could. \n\n- Secondly, the authors could provide more compelling motivation for the notion of 'anytime' algorithms. As a new reader of the E2D literature, I don't get the advantage of an anytime algorithm over its original version. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and valuable comments. We address the points raised below:\n\n**Significance and originality compared to prior work:**\n\nThe average-constrained DEC objective and the corresponding anytime analysis has several advantages compared to the approach proposed by Foster et al:\n- Our analysis leads to practically important anytime bounds not achieved by prior work. The anytime upper bound deviates from the proof by Foster et al (2021) in a non-obvious way.\n- In linear bandits, we prove improved regret in the regime $n < d^2$ (resp up to $n < d^4$ in linear feedback models). While the existing E2D approach achieves the same bound, it does so *only for the horizon fixed before running the algorithm*. The anytime algorithm achieves the optimal trade-off simultaneously for all horizons.\n- *We validate these claims numerically in Appendix E*\n- It is true, however, that the E2D approach by Foster et al (2021) achieves (near-)optimal worst-case bounds for fixed horizon and appropriately chosen trade-off parameter. In this sense, the existing E2D paper does not “fail”.\n- Another significant difference is that the trade-off parameter in the average-constrained DEC objective is chosen for the current estimate, whereas the choice suggested by Foster et al (2021) is essentially a conservative worst-case bound derived from the analysis. Choosing the trade-off parameter adaptively can lead to improved empirical performance as we show in Appendix E.\n\n*To conclude, we strongly believe that we make several novel and valuable contributions to the E2D framework propsed by Foster et al (2021, 2023).*\n\n**Motivation for anytime algorithm:**\n\nThe main advantage of the anytime algorithm is that it does not require the horizon as input parameter. This is important for several reasons:\n- The horizon might simply not be known before running the algorithm, i.e. the experimenter wishes the algorithm to keep running, possibly until some external termination criterion is met.\n- Fixing the horizon as in E2D (Foster et al, 2021) leads to optimization of the trade-off parameter for the given horizon, and the performance can be suboptimal on smaller and larger horizons - as we demonstrate theoretically (Remark 1) and numerically in Appendix E.\n\nWe will update the paper to reflect these points better.\n"}, {"review_id": "sif6XDZxhp", "reviewer": "Reviewer_zR5j", "summary": "The authors consider a framework to solve the bandit problem by means of the minimax problem, which has been rapidly developed in recent years.\nAmong them, the paper focuses on the decision-estimation coefficient (DEC).\nThe DEC was developed in a series of studies by Foster+ and is known to characterize the upper and lower bound of the worst-case regret in a general class of bandit problems.\nThe Estimation-to-Decisions (E2D) framework, an algorithm using DEC, determines action selection probabilities based on DEC.\nHowever, the algorithm based on offset DEC, which is an existing DEC, is expected to have conservative performance because it needs to determine the tradeoff parameter based on the regret upper bound.\nFurthermore, the recently developed constrained DEC does not require a tradeoff parameter, but has the problem that the strongly duality of a Lagrangian saddle point fails.\nTo solve these problems, the authors propose average-constrained DEC, a formulation in which the feasible region of the max player in the constrained DEC formulation is relaxed.\nThis eliminates the need to determine the tradeoff parameter based on the regret upper bound while maintaining the good properties of the optimization problem, resulting in an anytime algorithm.\nFurthermore, by considering a variant of average-constrained DEC, the authors show that an improved rate can be obtained for high-dimensional linear bandits, and this is confirmed through actual numerical experiments.\n", "questions": "- While the original DEC is formulated based on the Hellinger distance, this paper uses KL divergence for simplicity. What are the advantages and disadvantages that arise from these?\n- (e.g.,l169) The meaning of telescope was unclear. Can you explain the meaning of this?\n- (after l244) For the part of inequality (i), shouldn't the second term of max contains $\\mathrm{dec}^{ac}_{\\epsilon_t}(\\hat{f}_t)$? (The order and the last equation are correct.)\n- (l226) Why is the assumption \"$\\max_f \\{ \\epsilon^2 \\mathrm{dec}^{ac}_{\\epsilon} (f)\\}$ is non-decreasing in $\\epsilon$\" reasonable? Is there any exception?\n- Foster+2022 also devised DEC in the adversarial setting. Is the same kind of reparameterization possible in adversarial setting as in the paper? Is there any exception?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Overall, the paper is written in a very clear manner. In particular, it clearly summarizes the characteristics of the DECs proposed so far.\n- It clearly points out the problems of existing algorithms and presents simple solutions to solve them.\n- The authors devise a specific procedure for obtaining a regret upper bound not only when the model is discrete, but also when linear bandits ( possibly with side observations) are used.\n- While no numerical experimental evaluation of the DEC has been done so far, the effectiveness of the DEC is demonstrated through numerical experiments in the high dimensional linear bandits.\n", "weaknesses": "- Abstract and introduction are slightly misleading, as it appears that the average-constrained DEC results can be used directly to obtain results for high-dimensional linear bandits.\n- Although partial monitoring is mentioned in l120-125, the authors are actually solving the problem in a setting where rewards are also observed (or can be assumed to be included), as described in Example 1.2. The authors do not explain to what extent there is a gap with partial monitoring, and it is not clear to what extent the proposed algorithm is applicable to partial monitoring.\n- As mentioned by the authors, there are other approaches to characterizing sequential decision problems by minimax problems, such as IDS and ExpByOpt. A brief explanation of why the focus is on DEC would be desirable.\n\nMinor issues and typos:\n\n- l31: $M_f$ should be $M_{f^*}$\n- the meaning of \"localization\" was unclear and it would be better to explain the meaning in short.\n- In footnote 3, $\\max_{f \\in co(\\mathcal{M})}$ is $\\max_{f \\in \\mathcal{F}}$?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and questions. We address the points raised below:\n\n**High-dimensional bandits:**\n\n- We believe that the average-constrained DEC results do allow us to directly obtain results for high-dimensional linear bandits as shown in Remark 2. We will happily improve the clarity of our explanation if further comments are provided. The existing results on E2D imply a similar bound but only for a fixed horizon, whereas the anytime algorithm is optimal simultaneously for any stopping time. *This is a non-trivial finding not implied by prior works*.\n- The main results (Theorem 1 and also Theorem 2) do not require the rewards to be observed, and therefore apply to partial monitoring (this is the same for the existing results on E2D). Example 1.2 does not require the reward to be directly observed: It is sufficient that the reward vector is in the span of the observations. We will clarify this in the updated version of the paper. Note that Assumption 1 is only used in Lemmas 2-4.\n- We focus on the stochastic setting, where DEC was shown to tightly characterize the sample complexity of regret minimization [Foster et al. 2021, 2023]. The relation to IDS is apparent in Lemma 2, i.e. IDS respectively the information ratio certifies an upper bound on the DEC objective. In other words, without changing the proof, the bounds for DEC are always as least as good as for IDS. ExpByOpt is related but for the adversarial setting. We will make sure to clarify this further in the updated version of the paper.\n\n**Minors:** Thank you for pointing out minor issues and typos - these will be fixed and clarified in the updated version of the paper.\n\n\n**Questions:**\n\n- Hellinger vs KL: The (squared) Hellinger distance was used by Foster at al to prove near-matching upper and lower bounds. To what extent and in which cases the KL can be used instead of the Hellinger distance is currently unclear to us. In the examples we consider, the KL is sufficient. Note that the choice of divergence is independent of the main contribution of the paper - proving anytime bounds.\nFrom a practical perspective, the main advantage of the KL is the somewhat simpler closed-form for Gaussian distributions, the upper bounds for least-squares (Theorem 2), and the fact that the exponential weights algorithm directly bounds the KL. On a technical level, the KL upper bounds the squared Hellinger distance. Consequently, bounds on the estimation error for the KL imply bounds for the estimation error for the Hellinger distance. On the other hand, using the Hellinger distance might make it hard to prove upper bounds on the DEC. \n- By telescoping we mean that the sum over instantaneous estimation errors is bounded by the estimation error EST_n - this fact is directly used in our regret upper and the analysis by Foster et al (2021), whereas Foster et al (2023) require a stronger result, which is achieved by a more complicated refinement procedure.\n- The second term in the max in (i) is obtained by using the inequality $\\lambda\\_t \\leq \\epsilon\\_t^{-2} \\text{dec}^{\\text{ac}}\\_{\\epsilon\\_t}(\\hat f\\_t)$ (Lemma 1). Plugging this upper bound cancels out the first $ \\text{dec}^{\\text{ac}}\\_{\\epsilon\\_t}(\\hat f\\_t) $ term so that only $ \\frac{1}{\\epsilon\\_t^2} \\text{dec}^{\\text{ac}}\\_{\\epsilon\\_t}(\\hat f\\_t) \\mu\\_t I\\_{\\hat f\\_t} e\\_{f^*}$ remains.\n- The assumption was added by mistake and is not needed to derive equation (9) from Theorem 1. \n- To what extent the results apply to the adversarial setting as in (Foster et al 2022) is an interesting question for future work. Since in this case, the trade-off parameter also corresponds to the learning rate in exponential weights, achieving an anytime result might require a different proof, i.e. an anytime analysis of FTRL.\n\n\nWe will update the paper to reflect these points better. \n\n"}, {"review_id": "27feJX1z9T", "reviewer": "Reviewer_frUC", "summary": "This paper focuses on regret minimization in sequential decision-making under uncertainty. It introduces the average-constrained decision-estimation coefficient, a saddle-point objective that characterizes the worst-case regret, enabling optimization of the information trade-off directly by the algorithm. Moreover, the paper presents a version of the Estimation-To-Decisions (E2D) algorithm (ANYTIME-E2D), with practical implementation details, improved bounds for high-dimensional linear bandits, and the first empirical results of the E2D algorithm.\n", "questions": "What is the importance and impact of the new algorithm? Why is it better, more effective? ", "limitations": "NA", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper offers several results. The regret results are new since they are based on (3).", "weaknesses": "It is unclear how innovative the paper is. The brunt of the mathematics in the paper is drawn from existing prior results. Many mathematical derivations rely on standard Lagrangian (equations (3)-(7) and the proof of Lemma 1). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We provide clarifications on the contributions and impact below.\n\n**Importance and impact of the new algorithm:**\n- Anytime algorithms are of great importance in practice as the horizon is often not known in advance. A theoretically sound anytime version of the E2D algorithm has not been proposed before as far as we know.\n- The anytime analysis and bounds lead to improved regret in linear bandits models in the regime $n < d^2$ (resp up to $n < d^4$ in linear feedback models), which is relevant in high-dimensional and kernel bandits - we are not aware of a similar result in the literature (Remark 2). Further note that the E2D algorithm by Foster et al (2021) uses a fixed trade-off parameter, therefore cannot achieve the optimal regret rate on different horizons simultaneously (and we are not aware of any other approach that achieves this)\n- The algorithm is different from the prior work in that the trade-off parameter is chosen for the current estimated model $\\hat f_t$; The suggested choice by Foster et al (2021) is optimized for the worst-case, which, as we show, can lead to suboptimal performance, *which we  demonstrate numerically in Appendix E*.\n\n\n**Technical innovations of the paper:**\n\nWhile our results build on the framework by Foster et al (2021; 2023) to which we give full credit, we make several important and practically relevant contributions:\n- The anytime analysis and bounds are novel. The anytime upper bound deviates from the proof by Foster et al (2021) in a non-obvious way.\n- We explicitly derive the E2D objective for linear bandits, avoiding a computational dependence on the (infinite) model space (Lemma 6) - this has not been stated before and is important to note in particular when comparing E2D to established approaches such as UCB.\n- We prove bounds on the estimation error for regularized least squares in general linear feedback models (Theorem 2). We believe that it is important to highlight that a standard least squares estimator is feasible as an estimation oracle in the E2D framework.\n- Lemma 3 and 4 clarify the relation bounds the DEC via the information ratio IDS, DC and PAC with a direct and simple argument. A consequence of this is the improved bound for linear bandits (Lemma 5).\n\n*To conclude, we strongly believe that we make several novel and valuable contributions to the E2D framework propsed by Foster et al (2021, 2023).*\n\nWe will update the paper to reflect these points better. \n"}]

Author rebuttal:
We would like to thank all reviewers for their time and valuable inputs.
We respond to each review individually below.

We further point out that our submission contains an experimental evaluation of the proposed approach on two simple test cases in Appendix E. While the focus of the paper is on deriving the anytime bound, the experimental results include a direct comparison of E2D, TS and UCB and corroborate the claims made in Lemma 5 and Remark 2.

Meta-review: The reviewers with detailed evaluations largely agreed in the opinion that this paper has strong contribution in online decision making problems. On the other hand, main concerns are the technical novelty and the relation with previous work such as Foster et al. and other approaches based on optimization like information-directed sampling. They seem to be largely solved by the rebuttals and I strongly expect that the authors carefully address these points in the final version.
Decision: Accept (poster)