Is O(log N) practical? Near-Equivalence Between Delay Robustness and Bounded Regret in Bandits and RL
Authors: Enoch H. Kang
Panganamala Kumar
Venue: NeurIPS 2024 poster (2024)
Keywords: Delayed anonymous reward
reward attribution
robustness
consistent algorithm
bounded regret
bandits
RL
Primary area: learning_theory
TL;DR: We characterize the link between consistency and delay robustness in interactive decision-making (Bandit, RL), establishing near-equivalence between bounded regret and any-level delay robustness.

Abstract: Interactive decision making, encompassing bandits, contextual bandits, and reinforcement learning, has recently been of interest to theoretical studies of experimentation design and recommender system algorithm research. One recent finding in this area is that the well-known Graves-Lai constant being zero is a necessary and sufficient condition for achieving bounded (or constant) regret in interactive decision-making. As this condition may be a strong requirement for many applications, the practical usefulness of pursuing bounded regret has been questioned. In this paper, we show that the condition of the Graves-Lai constant being zero is also necessary for a consistent algorithm to achieve delay model robustness when reward delays are unknown (i.e., when feedback is anonymous). Here, model robustness is measured in terms of $\epsilon$-robustness, one of the most widely used and one of the least adversarial robustness concepts in the robust statistics literature. In particular, we show that $\epsilon$-robustness cannot be achieved for a consistent (i.e., uniformly sub-polynomial regret) algorithm, however small the nonzero $\epsilon$ value is, when the Grave-Lai constant is not zero. While this is a strongly negative result, we also provide a positive result for linear rewards models (contextual linear bandits, reinforcement learning with linear MDP) that the Grave-Lai constant being zero is also sufficient for achieving bounded regret without any knowledge of delay models, i.e., the best of both the efficiency world and the delay robustness world.

Is Ollog N) practical? Near-Equivalence Between Delay Robustness and Bounded Regret in Bandits and RL
Enoch H. Kang" Foster School of Business University of Washington Seattle, WA 98195
P. R. Kumar
Electrical Computer Engineering Texas A&M University College Station, TX 77843
Abstract
Interactive decision making, encompassing bandits, contextual bandits, and rein- forcement learning, has recently been of interest to theoretical studies of experi- mentation design and recommender system algorithm research. One recent finding in this area is that the and sufficient condition for achieving bounded (or constant) regret in interactive decision-making. As this condition may be strong requirement for many appli- cations, the practical usefulness of pursuing bounded regret has been questioned. In this paper, show that the condition of the Graves-Lai constant being zero is also necessary for a consistent algorithm to achieve delay model robustness when reward delays are unknown (i.c., when feedback is anonymous), Here, model robustness is measured in terms of e-robustness, one of the most widely used and one of the least adversarial robustness concepts the robust statistics literature. In particular, we show that c-robustness cannot be achieved for a consistent (i.e., uniformly nub-polynomial regret) algorithm, however small the nonzero value is, when the Grave-Lat constant is not zero. While this is a strongly negative result, we also provide positive result for linear rewards models (contextual linear bandits, reinforcement learning with linear MDP) that the Grave-Laa ai constant being zero is also sufficient for achieving bounded regret without any knowledge of delay models, i.e., the best of both the efficiency world and the delay robustness world.
Graves-Lai constant being zero is necessary
1 Introduction
We consider the cost of addressing stochastic and anonymous delayed rewards in Decision-Making with Structured Observations (DMSO) 21] which generalizes interactive decision cerisjon-mmaiing problems, such as structured bandits, contextual bandits, and reinforcement learning") In many real-life applications of interactive decision-makinn problems, stochastic and unknown delays in reward make challenging to attribute the sequence of observed outcomes previous decisions. In medical treatments, for example, doctor cannot easily be sure whether medical outcome is due to the effect of current treatment due some other previously taken treatment's delayed effect. This type of reward delay in decisions is called an 'unknown reward delay' [3] or 'delayed anonymous feedback'
Under this setting, the decision maker never observes the period information for which each
"chw kahwkanger @ uew.edu
*One refer Appendix A (or 2 for comprehensive, detailed description) how bandit,
contextual bandit, and episodic reinforcement learning problems can be described as DMSO problems.
$ "Most previous studies focus on delayed, anonymous, and aggregated (DAAF) feedback, where only the observe sum of the rewards arriving at each episode is observed. Here, we consider impossibility results for
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Delay
Only
Ouky:
Given delay model of ny: 13; True delay model of Dg
Given model of D2 Tree delay model of it Dj
Given delay model of wy:
True delay model of
Figure 1: Examples of misspecification of the reward delay model of decisions (T1, 72, T3)
reward corresponds to, even after it receives the delayed reward at the later time step. As it is not obvious which decision caused each observed reward, reward attribution becomes challenge.
Some knowledge (e.g., mean) of the probabilistic distribution of each decision's 's reward delay, combined with the careful design of algorithms, may help to resolve this reward attribution problem under stochastic and anonymous delayed rewards (4). However, those delay models themselves may be misspecified [6]. Therefore, whether can design algorithm that is robust to model misspecification becomes a main concern in the problems with stochastic and anonymous delayed rewards.
One of the most widely used concepts of model misspecification in the robust statisties literature is e-robustness 7]. Given a parameter é > O and true distribution D, a model distribution ò is called an e-(general) contamination of D if (D, D) S e, where drv denotes the total variation distance function Figure illustrates some examples of e-contamination of the delay models. As e-robustness is also one of the weakest (i.e., least adversarial) and most elementary notion of robustness (8), the first question on an algorithm's 's delay robustness will be, "up to which e the algorithm's properties robust to e-contamination of delay model misspecification....
In this paper, prove that consistent (i.e., uniformly sub- cobb-poynooiall regret) algorithm for DMSO can be designed to be robust to e-contamination of delay model misspecification unless DMSO's being zero While this is strong negative result, we also provide positive result for linear DMSO problems (linear contextual bandit, reinforcement learning with linear MDPs), showing that the Graves-Lai constant being zero I0 is sufficient for achieving bounded regret without any knowledge of delay models, As the Graves-Lai constant being zero holds if and only if we can achieve bounded regret 2 10 I1], the results in this paper strongly motivate the practical usefulness of designing learning systems where we can achieve bounded regret.
Graves-Lai constant [9, 2
1.1 Related work
While no previous work has studied the link between consistent algorithms and robustness to delay distribution misspecification when reward delays are unknown (=anonymous) in problems related to DMSO (e.g. bandit problems and reinforcement learning problems), there has been other work looking at different flavors of delayed anonymous rewards. There were prior studies delayed rewards [1,
13 14 15). but was the first to formalize the unknown stochastic reward delays assumption interactive decision making problems, which led to the literature stochastic delayed, anonymous and aggregated feedback (DAAF). While [4] provides a consistent algorithm for stochastic bandits that does not require any knowledge of delay distributions, it requires strong assumption that the mean of delay distribution is precisely known, which cannot be achieved under c-contamination however small isF] (In Section 4. show that no algorithm
be consistent when >> 0). [16] provides another consistent algorithm for stochastic bandits that also does not require any know knowledge of delay distributions and improves [4) but it requires different assumption that the delayed reward
feedback exactly associates the reward and the arm and therefore rewards are not anonymous; [17]
18
make similar assumption for episodic reinforcement learning problems with stochastic delays.
the delayed, anonymous, and non-aggregated feedback, where observe each delayed anonymous reward separately.
"The total variation distance drv v) is defined as _ w/Ii supEEy (x(B) vBB),, where Σ stands for the measurable sets on which two distributions and are defined.
'For example, for the family of distributions with k-th moment bounded by for k: 2 2, e-contamination > k-l-1/k (See Assumption 4.2 for more).
delay distribution, i.c., drv (D. D) > implics E [D] - E []

---

While our work centers on delayed anonymous rewards-wher the learner cannot associate delayed rewards with the actions that generated them there exists a parallel line of research addressing non-anonymous delays, in which such associations are possible. In this context, several studies have proposed algorithms that account for unrestricted or unbounded delays. (19) developed algorithms for nonstochastic multiarmed bandits with unrestricted delays, achieving robust regret bounds by employing a skipping strategy to manage excessively delayed feedback. (20) adapted Thompson sampling to handle multiarmed bandits with unrestricted delays, extending its applicability to delayed feedback settings without assuming bounded delays. [2I] derived near-optimal regret bounds for adversarial MDPs with delayed bandit feedback, addressing the challenges posed by feedback delays in adversarial environments. [2] proposed an optimal algorithm for adversarial bandits experiencing arbitrary delays, establishing regret bounds that hold even when delays are extensive. Building
on this foundation, (23] introduced a "hest-of-hoth-worldds algorithm that improves upon (22) by providing both adversarial guarantees and near-optimal stochastic performance without requiring prior knowledge of the maximal delay.
2 Preliminaries
2.1
Decision-Making with Structured Observations
The DMSO problem framework generalizes many problems such as bandit problems, contextual bandit problems, and episodic reinforcement learning problems. DMSO is characterized by the environment and its learning protocol, which is described as follows:
The environment of DMSO problem framework is specified as tuple (11, O, where II denotes the decision space, R denotes the reward space, O denotes the observation space, and F =IIree= Fx denotes the model class where Fr C ARx (Here, Ag notation means the space of all possible probability distributions over a set E) We use fx to refer to an element of Fr, with fa being the r-coordinate of f E F. A ground-trun -ruth model f* E F governs the rewards and the observations based on the decisions made in the rounds. While f unknown to the learner, is typically assumed that set F that includes f is known to the learner. Formally, we make the following assumption, which is often called the realizability assumption (24) 25 26].
Assumption 2.1 (Realizability). The learner has access to the model class F containing the ground- truth model f"
The learning protocol for the DMSO problem consists of n rounds. In round k S n,
1. The learner makes a decision F II.
2. A reward F R and an observation оą O are generated, where (rk, o&) l F
3. Learner observes Og. If there are reward delays, the learner observes Rş, the set rewards that arrive at the round k. R& is equivalent to ra only if there are no reward delays.
2.2 Learning Algorithm for DMSO
Given that we characterized the DMSO problem framework, we can now describe a learning algorithm for it. Let hg be the history up round k, i.e., f4 = { Ry, o;)} where n, E 11, R2 E R, o, O and H be the set of all possible histories of rounds for k 2 1. A learning algorithm A is defined as an element of A C (H + An), which is a subset of the set of all possible mappings from the history space H the set of all possible distributions over IT. That is, each round k; given the history h4 E H. a learning algorithm A E A chooses Pk A(hx) E An. The decision at round k. nR. is sampled from Pę. Note that f E F. A A and the round n completely determine the stochastic behavior of the learning protocol up to round n, i.c., they induce a probability distribution we call [-] over the set of all histories up to round n. We also denote the respective expectation by Efm.Al-)) When the meaning is clear from the context, we use Py..I-] and E instead of Pr Pr...al) and E E....Al..
Py.n.A
Given o) ~ Sn. we denote J, == E,, |r]. Let F E arg max f4 denote an optimal decision for the model f. The sub-optimality gap of decision π for model is defined as A ( == 1f,, - Uf, When the ground truth model is f. choosing ny at each round until round n yields the largest value of
'This model class definition is equivalent to the definition used by Wagenmaker and Foster [ because if A is set, countable or not, the Cartesian product X is defined to be the collection of all functions f A X.
3

---

total reward until round n. Therefore, we can measure the optimality of an algorithm A until round in terms of regret, which is defined by
Regg,a (n) == EA
Σ A (TA)
2.3 Consistent Learning Algorithm's Instance-Dependeni Regret Lower Bound
Reg,.a(M) (n) is quantity that is dependent on the true model instance f. Since the true model f is unknown to the learner priori, a good learning algorithm must be able to perform well for all possible E F. Therefore, one might want to define the goodness of an algorithm by its capability to achieve the minimal value of Reg,,A (n) among all possible algorithms for all the instances However, this is not achievable; a bespoke algorithm that always chooses will outperform all possible algorithms for the instance while suffering linear regret for the instances in F \--
F..
Since many problems have algorithms that incur sub-polynomial regret for instances, it common to exclude algorithms that suffer polynomially increasing regret in some instances. This idea is formalized the following definition that restricts the space of 'interesting" algorithms.
Definition 2.2 (Graves and Lai (1997) (9). A learning algorithm is called consistent and f E F.
Reg,,a (n) = o (n²) holds for every
For DMSO problems, it has been recently shown that any consistent algorithm's 's instance-dependent regret must satisfy the asymptotic lower bound described in the following theorem (2).
Theorem 2.3 (Dong and Ma (2022) (2). Suppose that there are no reward delays. Then for every instance f E F, the expected regret of any consistent algorithm A satisfies
Regg,A(1)
lim sup
c(f) lim c(f.n).
(2)
In
1-000
where C(f. n.) is the solution to the optimization equation
C(S,n) A min
Σ WT))(()
WEB
W. DKL 21, Vg F())
(3)
xell
| 30 S n,
where DEL is the KL. divergence and F(f)= (g
Corollary 2.4. Let fo E FF be the ground-truth model. For consistent algoritiun to achieve sub- lob--oggaittmicc regret, C(f*)= = must hold. That is, achievement of sub-logarithmic regret for all possible instances of F can be assured a priori only iff(f) for F.
Theorem 2.5 (Wagenmaker and Foster 1]. Expected regret of order C(f*) In can be achieved for DMSO problems without delays. That is, bounded regret can be assured ifC()) 0 for f
2.4 e-contamination and Total Variation Distance
robust statistics, one of the oldest and the most commonly used concepts for modeling contaminated data is the concept of e-contamination 7 Given parameter ( < < and original distribution D, distribution X called an e-additive contamination (or Huber contamination) of D if X a mixture distribution of D and unknown arbitrary distribution E, with their selection probabilities being (1 - e) for D and for E. Furthermore, distribution X called an e-subtractive contamination of D it is equivalent to arbitrary e-probability removal from D (and normalization). Finally, say that a distribution X is a (general) e-contamination of D if can constructed by removing c-probability from D and replacing that with equal mass from some arbitrary distribution E.
As discussed earlier, the concept of e-contamination is closely related to the concept of total variation distance. Given space of distributions, the total variation distance, denoted as drv(", (2, v), is defined as drv (v,z) w) = [ v/I1 = supges Iu v [)], where E stands for the measurable sets on which / and e are defined. It is well known that drv is metric that satisfies interesting properties

---

such as 1) drv = 0 if and only if and 2) drv = if and only if v and are singular, i.c. there exists E such that v(E) and v(E) 0. is also well known that the concept of e-contamination is equivalent to the concept of total variation distance [8]; we separately state this property as the following lemma.
Lemma 2.6 (8), Given parameter 0 < 1, distribution X is e-contamination of D (and vice versa) if and only if drv (X, D) =
3 Main Model: e-delay Robustness
Denote the true reward delay distributions of each decision E by Dz. Every time m. determined at each round k, dg ~ Dr, is generated along with the generation of (rk, 0&. ~ fx. While og is observed immediately round k, T'k is scheduled arrive at round d2 + k. The order of reward arrivals does not necessarily match the order of the reward generation.
As in 3 we assume the unknown delays setting throughout the paper. In the unknown delays setting, the delay dg is not observed, and therefore attributing rewards to the previous decisions becomes a nontrivial problem. One can only guess from which decision the reward just arrived came based on the history of previous decisions and some information about reward delay distributions.
As reward delays are not observed, information we know about reward delay distributions is likely to be misspecified. We model this misspecification as e-contamination of the true delay distri- bution models { resulting in information about {Dx men instead, where D, is an out- come of e-contamination of the delay distribution model Dz, i.e., (D,, 12) S e. Note that e-contamination of delay distribution models encompasses many possible misspecification of informa- tion about delay distribution. For example, it implies misspecification of mean of delay distribution
as dr (. D implies [E[D] Σ!D > 0 (See discussions in Assumption 4.2 for details).
We now propose the formal definition of robustness in terms of delay distribution knowledge.
Definition 3.1. We say that consistent algorithm is e-delay robust if it is consistent when the given delay distributions are e-contaminations of the true delay distributions.
4
Main Results
4.1 Negative Result: Delay Robustness Requires C(f) = 0 for all f E F
Given the definition of e-delay robustness provided in Section 3 the main question is when consistent, e-delay robust algorithm exists. The answer is quite negative: unless C(f*) = 0 holds, no consistent algorithm can be c-delay robust, however small > 0s.
Theorem 4.1. Under minor technical assumptions (see Assumptions how small c > 0 is, a consistent learning algorithm can be e-delay robust only (ff( 0.
below), regardless of
Theorem 4. implies that the concept of consistent algorithm fails even with very small misspecifi-
cation of the delay model unless the Graves- constant C(f*) satisfies C(f*) = 0. Since we want to design learning system with existence of consistent algorithm that works for all instances of f e F. we need C(f) = 0 for of E F, which was the necessary and sufficient condition for achieving bounded regret when there were reward delays (Corollary 2.4 4 and Theorem 2.5)
The intuition behind the proof of Theorem 4.1 (See Appendix B for details), as follows. When the
reward delay model is precisely known, i.e., when the reward delay model is not contaminated, we might be able to address this challenge by designing a good algorithm that makes the probability of confusion in reward attribution small models, under minor technical assumptions below (Assumptions 4.2 we can always provide a delay model contamination that makes the precision of any consistent algorithm's 's reward attribution no better than 5 for some 5 > 0. This leads to reward distribution suffering 5-contamination, which makes impossible to design a consistent algorithm.
want. However, in the case of e-contamination of delay
The assumptions required for Theorem 4.1 are as follows.
Assumption 4.2. For the family of distributions Dr := {- 0) f EI, E. 0), there exists function g(0) s.t. for D1, D2 Drjos [[[ - E[D2 S 4()) implics drv (Dv, D2) I 8.
5

---

For some special families of reward distributions, such that satisfies Assumption 4.2 is known g
(Let be constant in what follows)
For the family of Gaussian distributions with standard deviation 1, l.)()) = k8.
For the family of log-con cog-concave distributions with standard deviation 1, q(()) = kd log (1/8).
For the family of distributions with kth moment bounded by 1 for k 2 2, g( = ko 1/k,
Assumption 4.3 expresses the conditional unimodality in likelihood functions in terms of rewards.
Assumption 4.3. Given ground truth f E F and g g².g² E F, for every т E 11, Egg |r S E3 [r|o] < E,, [r|o] or Egg [rlo] 2 [ri 2 E,, [r]o] implies DRI(Ja(: o) 0)) S DEL (f=( 90 o)) almost everywhere (a.e.).
Assumptions 4.4 and 4.5 exclude trivial cases where the reward information is not all needed for the inference of the ground-truth model f.
Assumption 4.4 (Density of Fx for every π E II). For every π E 11, {gx E Fx Max 2 Msay n {or F= y (r 0) gg (r [+]o]] | S q()) a.e.) } is nonempty given 5 > 0.
Intuitively, (gT Fx Ms. 2 /'xx,) is the set of hypotheses in F= need reject, and {9x E Fx [E (r () - Eg (r oo] $ q()) a.e.} is the set hypothesis we cannot reject under contamination of outcomes from decision æ. Note that {gx Fx E o) -g o) 1 (0)) a.e.) S {gr E Fx 1gg. Hs S {())}.
Assumption 4.5. Let 9f the marginal distribution the observation of gr Fr. There exists To 0 such that for every E II, (,y, M'g. S To implies f a.e..
Note that f== 9f a.e. and only if DxIl(ffll9? = 0 holds. If on the rewards will be required reject fr under Sz, the true hypothesis for the decision On the other hand, in the reinforcement learning problems where reward functions are parametrized independent of the transition model parameters, To in the Assumption 4.5 is +00.
> 0, no information
4.2 Positive Result: C(J) 0 for all f E F enables Super-Robust Bounded Regret
In the previous section, we saw in Theorem 4. that C() = for f f F is required to assure the existence of a delay-robust consistent algorithm. We also that C(J) for F is required to assure sub-logarithmic regret for all possible instances of true f (Theorem 2.3).
Here, try to answer when it is sufficient to assure best of both worlds, i.e., bounded regret and robustness to any delay-model miss-specification at the same time. Before answering this question, need to define and explore two new concepts: mons-informatiieesss and max-contamination.
4.2.1 Cross-informativeness
Recall that we denote by Py..A the distribution of the outcomes of algorithm A for the model instance / F by the with round. Let denote the algorithm that always chooses decision II as म. Then Lemma 4.6 motivates the concept of boos-informmaiveness.
Lemma 4.6. Suppose that f E F the ground-truie model instance. Then C(f) = implies that DKL (PImay [P (anaa) (1)) holds for g E F(f).
Proof. Suppose that C(J) = O. According to equation (3). this implies that there exist Why and 0 < no < 0o such that for all n 2 no, Wxy (fr T9n,)) 2 1, Vg E F(f)s. Therefore, PP P....llPPgg... = nD (JTy (19,,) Z way
DKL. (Pr.,
holds Vg E F(J) for n 2 no.
Lemma 4.6 provides an intuitive and straightforward connection between C(f) 0 and bounded regret: we can reject all the hypotheses that need a rejection to conclude that f is indeed the ground truth hypothesis (F()))), simply by exclusively playing म forever, while incurring (emma|4.6)shee shows how informative n is when the true hypothesis is f. When the true hypothesis is not f, n. can be arbitrarily uninformative.
regret.
The natural question now arises is how much crossinfformativennss (informativeness of mi E II for the ground truth f E F when h * is sufficient for us achieve bounded regret. The key

---

assumption used in this paper is Assumption 4.7 which is later shown to be satisfied for the linear systems (contextual linear bandits, linear MDP) when the conditions implied by C(f) = 0 for f F are satisfied (Section
Assumption 4.7 (Cros-informmativness) Suppose that f F is the ground-truth model. Then for any g, h E F, DKL M...nllPggnna (Inn) holds.
Note that the rrossinffrmmatieenss lower bound rate of w(lnn) in Assumption 4.7 is a much weaker rate than the lower bound rate (2()) in Lemma 4.6
4.2.2 Max-contamination
Whatever true delay distribution the reward delays follow, the maximum number of reward ar- rivals from by the round & is Nr (k), the total number of decisions by the round k. The max-
min( Encmyy N+ 1), N(k)
contamination of the decision n' II at round & is defined as 6
where (k) stands for the total number of reward arrivals by round k. Note that the contamination of reward arrival at l is bounded by the mux-contaminationn 8m (k:), the delay distributions of decisions are stationary, i.., they do not change over time.
4.2.3 Algorithm Simply-Test-o--Commi (ST2C)
Assumption 4.8. For all f.g E F, DKL (fa( ()]lgx(11 60.
and O, In fz gx
c for some e > This implies
Assumption 4.8 excludes trivially informative cases where f and almost immediately dis- tinguished given the observation o E O. Under Assumption 4.8) we can well-define B := dfa(-lo)
(suP (SU, (go(-lo) (E)) (where Ex denote the collection of measurable sets for (
and gx(( (- o)), Assumption 4.8 holds if and only if the log- likelihood ratio In f( o) is well-defined on the support of In and is finite a.e..
9x o)
Let P. indicate the likelihood of g E F that is computed as all reward arrivals by the round are from the decision т. (Note that this actually not true, as we allow decision transitions in Algorithm Note that In Fi
Ek= In [T) where (k) and of (k) are likelihood of each (5k)
Po 9.A.V
data assuming that the data is from π.
We now describe the algorithm Simply-Test Test-to-Comme (ST2C) the Algorithm below.
Algorithm Cemplyy-Tes-to--Comeee (ST2C) Algorithm
1: Choose any E F, set f=
2: for n = 1, 2, do
3: Choose w as the decision at period n
4: Observe and Rn, newly compute 6 (n)
o (M)
5: if (o E
2ln + Ei Vi 6m
8max
then
1 (K)
6: Choose any & E Fr
Set f =g
8: end if
9:
end for
4.2.4 Analysis of algorithm ST2C
Later in Section 5 we will show that C(f) 0 for all f E F, which is design feature of learning problem we decide priori, sufficient to show that Assumption 4.7 indeed holds for
some representative linear problems. In this section, we show that Assumption 4.7 (combined with technical minor Assumption 4.8) is sufficient to allow Algorithm D to achieve bounded regret without any knowledge of delay distribution model.
7

---

The following Lemma 4.9 shows that stays at incorrect instances for only finite time, except for the periods ff arrives at incorrect instances.
Lemma 4.9. Under Assumption 4.7 and 4.8 total number of periods f stays in F \ f is finite in expectation, except for the periods wrong transition (transition F (*) happens.
Lemma
that the total number of wrong transitions from the correct inferences is finite in expectation.
Lemma 4.10. Under Assumption f E F(ft)ss.t s.t. E
4.8
the number of rounds Algorithm satisfies the event {f S 2 21n Ek=1 0 (k)) holds is finite in expectation.
9-
In
Theorem 4.11. Under Assumption 4.7
and 4.8 the algorithm ST2C (Algorithm) D. which does not require any knowledge the delay distribution model, achieves bounded regret 4(1+5 1 y where W is the principal branch Lambert W function (27), A the maximum per-period mean reward difference among decisions, and is from Assumplion 4.8.
W(227)) 6
Proof. Combining Lemmas 4.9 and 4.10 we can conclude that f F((*) holds only for a finite number of rounds in expectation. That is, regret is bounded in expectation. For detailed derivation of the bound, see Appendix C.3
5 Equivalence of bounded regret and delay robustness in linear systems
As discussed in Section satisfying the cross-informativeness condition introduced in Assumption 4.7 ii the key assumption that enables Algorithm to achieve bounded regret with super-robustness to delay. In this section, we show that linear learning problems such as contextual linear bandit and reinforcement learning (RL) with linear MDP indeed satisfies the mrossinformattiennss condition if C() = 0 for F. That is, for those problems, the condition *C(J) 0 for / E F² is not only necessary (Section 4). but also sufficient for achieving bounded regret under any level of delay model misspecification. In other words, we can conclude that achieving bounded regret is equivalent to achieving any level of delay robustness for such linear problems discussed Section 5.1 and 5.2
5.1 Contextual linear bandit problem
Hao, Lattimore, and Szepesvari [10] was the first to characterize when C(f) holds for contextual linear bandit problems. In this paper, we follow the notations and settings of (TO] as follows: Let's consider the stochastic M M-armed contextual linear bandit with a horizon of n rounds with M arms and finite A-size set of k-dimensional possible contexts X' = {x, ]E[[A]- each round, context is sampled according to the unknown distribution over X' and then observed. Every time context sampled, an arm choice (a decision in MDSO framework) happens. When the sampled context is xj and its chosen arm is m, we receive &n (x,xx000 + e, where {p.m IR² - IRd) ] representation functions that are assumed to be precisely known, 0 is a parameter vector of dimension d that is shared across the arms, and is an i.i.d. random noise that follows a sub-Gaussian distribution with variance proxy o².
mmE[M) are linear
Let θ be the set of all parameter vectors, and let 0* E θ be the unknown true parameter. Suppose that C(B)
for 8 E Let m,e be an optimal arm for context E when the true parameter 8, i.e., myo E argmaxme[M) @m (x,) The following Theorem 5.1 characterizes previous results on when bounded regret can be achieved when there are no reward delays.
Theorem 5.1 (10,, 28).. Given linear contextual bandit setting described above, when there are no reward delays, bounded regret can be a priori guaranteed be achieved if and only if (0myo (x₂) E A} spans RRd for all O E O.
Note that the condition that '(0mp (imns((x)) (x,) |j E A} spans Rdd for all 0 E O' in Theorem 5.1 is easily satisfied a priori when we are given rich enough context set [29). How does this eastly satisfied condition work when there are anonymous delayed rewards? The following theorem of ours shows that {f @m (xx) j A} spans Rd for all 0 O' implies that the Assumption 4.7 is satisfied.
8

---

Theorem 5.2. Given contextual linear bandit setting described above, Assumption 4.7 (DRI. (Por,, n, (o (n)) holds for 6' y") is satisfied if {Omg (x²) 1 E A} spans R for all f E
See Appendix [ for the proof of Theorem 5.2 As Assumption 4.8 triviil holds for linear problems
(2). Theorem 4. (which requires Assumption a a.8 to hold) conclude that our Algorithml T
achieves bounded regret without any knowledge of delay distribution model if (Øm go (x,) E A]
spans Rdd for all 0 E O (which is easily satisfied when the context space is rich enough [29
For contextual linear bandit setting described above, it has been shown that (fmmy (x,) 1 E A
spans Id for all 0 E O' is equivalent to *C()) = 0 for all 0 E e' [26 2 Since C(0) = 0 for all
0 E θ is necessary condition for a-priori assurance of any-level robustness of consistent algorithm (Theorem 4. we have the following Corollary [533] which is a reminiscent of Theorem 5.1 above.
Corollary 5.3. Given contextual linear bandit setting described above, under any anonymous delayed rewards. bounded regret can be priori guaranteed to be achieved if and only if (fmmp (x,) 1 E A] spans R for all 0 O.
Note that Corollary 5.3 strongly motivates the practical usefulness of bounded regret algorithm design in contextual linear bandit problems, as it is also a necessary and sufficient condition for achieving any level of delay robustness. This condition is indeed not hard to satisfy in the real world; for example, in Spotify, million daily users can be considered a rich enough context for exploring 60,000 new songs uploaded daily (29).
5.2 Reinforcement learning with Linear MDP
Papini et al. 11] was the first to characterize the condition for achieving bounded regret for some popular classes of reinforcement learning with episodic Linear Markov Decision Process (MDP). In this paper, we follow the notations of [TI], which are as follows: we are given a time-inhomogenous MDP M- = (S.A, H, (ra) P.u). where
finite state space, A a finite action space, H
the length of each episode, {ra} are the reward functions where (s. a) the expected reward of a pair (s, a) E S x A at time-step h. P == } are the transition kernels, and is the initial state distribution. A policy π = (TT.....,. TH) ll is sequence of per-time-step policies Th : S + A. For every h E [H] = {1..... H). we define the state-action value function of a policy as (x, = (x a) + Ex EE= ri (8;, (si,as) ai) and Q% (s, a) = (2(s,)) = sup, (% = LA (7,41 a) where Ln Qh+1 = (s, + (s.rp)(s..) [max,/ 1h+ (0++1(s',a') (s',a').
As in [T]] we focus episodic Linear MDP setting with Bellman closure [30]. which is more general than many popular Linear MDP settings such as low-rank Linear MDPs [30].
Definition 5.4 (Linear MDP with Bellman closure (complttnnsss)(00)
Suppose that we are given feature map Φx S x A + Rda, possibly different at any h E [H], mapping state-action pair (s, a) into d -imeenioona vector Φn(s,a), For the set of bounded value function 2n = {Q, 0n. E To,, V(s.a)) }}} and the associated parameter space θ {0, Rd
On : (n a) (s, a)T 0n, (s, a) T S D}. An MDP is said to satisfy zero Inherent Bellman Error (IBE) (or satisfy
Bellman closure) if vh E [M], supQ, 160.11 infq.ee, I|Qr LaQu-illss holds.
The following Theorem 5.5 summarizes a previous result that characterizes when bounded regret can be achieved when there are no reward delays.
Theorem 5.5 (Papini et al. (II. Denote the optimal policy n" and o7 (s) == ón (s, (s). In Linear MDPs satisfying Bellman closure, the condition that 'span( (s) Vs E S, T-" visits s at with positive probubility) = Rdd for all h E [H)* is sufficient for achieving bounded regret in high probability when there is no unknown reward delay.
Theorem 5.6. Given episodic Linear MDP with Bellman closure described above, Assumption 4.7 (DKL. (Pir m |P (n.g)) I(n) holds for 6' (") is satisfied if span (s) Vs S, n visits h with positive probability) = Rdd for all h E {H].
Again, as Assumption 4.8 trivially holds for linear problems (2) Theorem 4.11
(which requires
Assumption 4.7 and 4.8 to hold) conclude that our Algorithm acchevess bounded regret without

---

any knowledge of delay distribution model if spanf As E S, visits s at h with positive
probability = IR for all h E [H]. Therefore, we have the following Corollary 5.7
Corollary 5.7. Given episodic Linear MDP with Bellman closure setting described above, under any anonymous delayed rewards, bounded regret can be a priori guaranteed to be achieved if span(d: (8) Vs E S, ' visits 8 at h with positive probability| R for all h E [H].
Again, note that Corollary 5.7 strongly motivates the practical usefulness of bounded regret algorithm design, as the sufficient condition for it is also sufficient for achieving any level of delay robustness.
6 Conclusions
In this paper, we characterize the link between consistent algorithms and delay robustness in inter- active decision-making. The first main result states that, for consistent algorithms, the necessary condition for achieving any (small) level robustness against delay model misspecifications is also sufficient for achieving bounded regret. Viewed from another perspective, this result urges to revisit the practicality of the instance-dependent regret minimizing algorithm design regime [ for real-world problems with anonymous delayed rewards. The second main result states vice versa for linear problems, showing that the well-known necessary (and sufficient) condition for bounded regret is also sufficient for designing consistent algorithm that achieves any (large) level of robustness against delay model misspecifications and bounded regret at the same time. An interesting future research direction raised by our paper is whether it is possible to achieve second main result without restricting to linear problems.
Acknowledgements
This material is based upon work partially supported by the US Army Contracting Command under W91 INF-22-1- 0151 and USARO under W911NF22 10064, the US National Science Foundation under CNS-2328395 and CMM112038625, and the US Office of Naval Research under N00014. 4- 24-1-2615 and N00014-21-1-255 This work was also partially conducted with support from the Bertauche Transportation Endowment and the Edna Benson PhD Fellowship.
References
[1] Andrew Wagenmaker and Dylan J Foster. "Instance-Opimmality in Interactive Decision Making: Toward a Non-Asymptotic Theory". In: arXiv preprint arXiv:2304. 12466 (2023).
[2] Kefan Dong and Tengyu Ma. Asymptotic Instance-Optimal Algorithms for Interactive Decision Making.
2023, arXiv: 2206. 02326 [Cs.LG]
[3] Bingcong Li, Tianyi Chen, and Georgios B Giannakis. "Bandit online learning with unknown
delays". In: The 22nd International Conference Artificial Intelligence and Statistics.
PMLR. 2019, pp. 993-1002.
[4] Ciara Pike-Burke et al. "Bandits with delayed, aggregated anonymous feedback". In: International Conference on Machine Learning. PMLR. 2018, pp. 4105-4113
[5] Nicolo Desa-Bianchi, Claudio Gentile, and Yishay Mansour. "Nonstochastic bandits with composite anonymous feedback". In: Conference On Learning Theory. PMLR. 2018, pp. 750-
773.
[6] Siwei Wang. Haoyun Wang. and Longbo Huang. "Adaptive algorithms for multi-armed bandit with composite and anonymous feedback". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. 11. 2021, pp. 10210- 10217.
[7] Peter J Huber. Robust statistics. Vol. 523. John Wiley & Sons, 2004.
[8] Ilias Diakonikolas and Daniel M Kane. Algorithmic high-dimensional robust statistics. Cam- bridge University Press, 2023.
[9] Todd L Graves and Tze Leung Lai. "Asymptotically efficient adaptive choice of control laws incontrolled markov chains". In: SIAM journal on control and optimization 35.3 (1997),
pp. 715-743.
10

---

[10] Botao Hao, Tor Lattimore, and Csaba Szepesvari. "Adaptive exploration in linear contextual bandit".. In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020,
pp. 3536-3545.
[11] Matteo Papini al. "Reinforcement learning in linear mdps: Constant regret and representation selection". In: Advances in Neural Information Processing Systems 34 (2021), pp. 16371- 16383.
[12] Gergely Neu et al. "Online Markov decision processes under bandit feedback". In: Advances in Neural Information Processing Systems 23 (2010).
[13] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. "Delay-tolerant online convex optimization: Unified analysis and Staapivvegradienn algorithms". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. 2016.
[14] Nicolo Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. "Delay and cooperation in nonstochastic bandits".. In: Journal of Machine Learning Research 20.17 (2019), pp. 1-38.
[15] Claire Vernade, Olivier Cappé, and Vianney Perchet. "Stochastic bandit models for delayed conversions". In: arviv preprint arXiv:
(2017).
[16] Tal Lancewicki et al. "Stochastic multi- bandits with unrestricted delay distributions".
In: International Conference on Machine Learning. PMLR. 2021, pp. 5969-5978.
[17] Benjamin Howson, Ciara Pike-Burke, and Sarah Filippi. "Optimism and delays in episodic reinforcement learning". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2023, pp. 6061 6061-6094.
[18] Nikki Lijing Kuang et al. "Pusterior sampling with delayed feedback for reinforcement learning with linear function approximation". In: Advances in Neural Information Processing Systems 36 (2023), pp. 6782-6824.
[19] Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin. "Nonstochastic multiarmed bandits with unrestricted delays". In: Advances in Neural Information Processing Systems 32 (2019).
[20] Han Wu and Stefan Wager. "Thompson sampling with unrestricted delays". In: Proceedings of the 23rd ACM Conference on Economics and Computation. 2022, pp. 937- 955.
[21]
Tiancheng Jin et al. "Near-optimal regret for adversarial mdp with delayed bandit feedback". In: Advances in Neural Information Processing Systems 35 (2022), pp. 33469-33481.
[22] Julian Zimmert and Yevgeny Seldin. "An optimal algorithm for adversarial bandits with arbitrary delays". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020, pp. 3285-3294.
[23] Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. "A Best-of-bothhworldd Al- gorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays". In: and Perspectives.
ICML 2024 Workshop: Foundations of Reinforcement Learning and
2024.
[24] Alekh Agarwal et al. "Contextual bandit learning with predictable rewards". In: Artificial Intelligence and Statisties. PMLR. 2012, pp. 19-26.
[25] Simon Du et al. "Bilinear classes: A structural framework for provable generalization rl".
In: International Conference on Machine Learning. PMLR. 2021, pp. 2826-2836.
[26] Dylan Foster al. "The statistical complexity of interactive decision making". In: arxiv preprint arxiv:21 12. (2021).
[27] Robert
M Corless et al. "On the Lambert Advances in Computational mathematics (1996), pp. 329-359.
W function". In:
[28] Matteo Papini et al. "Leveraging good representations in linear contextual bandits". In: International Conference Machine Learning. PMLR. 2021, pp.
[29] Enoch Hyunwook Kang and PR Kumar. "Bounded recommendation learning via synthetic controls oracle". In:
(1)) re-
gret 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE. 2023, pp. 1-7.
[30] Andrea Zanette al. "Learning optimal policies with low inherent bellman error". In: International Conference on Machine Learning. PMLR. 2020, pp. 10978-10989,
[31] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

---

[32] Thomas M Cover. Elements of information theory, John Wiley & Sons, 1999.
[33]
Sergio Verdú. "Total variation distance and the distribution of relative information". In:
2014 Information Theory and Applications Workshop (ITA). IEEE. 2014, pp. 1-3.
12

---

A Special Cases of DMSO Framework
In finite-armed bandit problems, each round is an arm pull. 11 is the arm space, and R. is the space of rewards from arms. Since there is no observation space O, the model class degenerates S (II Ar).
In contextual bandit problems, each round is arm pull. II is the set (& A) of all policies, where X' is the context space and the A is the arm space. The reward space R is the space of rewards from arms. The observation space O is X, where the kth round's observation Og: E O (which results from TH) is the + 1th round's context. Since the future context arrival is not affected by previous decisions, the model class degenerates to F FC (II AR).
In episodic reinforcement learning problems, each round is an episode. II is the set (S + AA) of all policies, where S is the space of all possible states and A is the action space. The reward space R. is the space of value functions at each initial state, and the observation space O is the set of all possible sequences of action choices, state transitions, and received rewards in one episode. The model class F characterized jointly by the initial state distribution and the transition kernel, which are shared across all the episodes.
B Proof of Theorem
Recall that P- denotes the distribution of outcomes of algorithm A on the true model instance by the round n. We further denote the marginal distribution of Pf,n,a(:] in terms of decision r's rewards and outcomes by Pj pl..,
Lemma B.1. Suppose that the ground-truth model is F. Then consistent algorithm must satisfy (1 + o(1) In S ErEn DKL (PT (P ga.A) .) for E F(f)..
Proof. According to Dong and Ma (2022) [2]. any consistent algorithm A must satisfy (1 o(1) Inn I DKI. (Pr.n,a P.P..n g., for E F(FY. Since the terms involving A (the algorithm used to collect the data) cancel out and the outcomes of decisions are independent of each other, PLoA
II
PT
holds. Therefore, the condition of Dong and Ma (2022) becomes (1
Paand
PE D.n.A
o(1) Inn S Exen DKL (PFm,,llee. for E F(f)..
Lemma B.2. For any > O, c-contamination in the delay model of a² makes the rewards of decisions * TT suffer b-contamination for some 5 >> 0 under consistency.
See Section B. for the proof of Lemma B.2
Lemma B.3 shows that, under 5-reward contaminations in reward distributions of all + Tt, choosing optimal decision ' alone must be enough to satisfy the condition described Lemma B. and otherwise, we cannot satisfy it.
Lemma B.3. If the rewards of decisions π E \ Ty suffer 5-contamination for some 5 > 0, consistency of the algorithun requires (1+00) o()) & DKL (Pj,.l1ghh) for all E F(f)..
See Section B.2 for the proof of Lemma
B.3
The rest of the proof Theorem 4.1 immediate from the derivation of (2)'s Theorem 2.3 which is
follows: from the chain rule of divergence, DKL (P p...
EE [Na]] DKL (f= (g.) holds
g.n
for E 11. Defining w, Ey [N= /((1 o(1) In n2). Lemma B.3 implies that C(f) by the
definition of C(f) in the equation (3). Since we don't know the ground truth f priori, designing a
learning system that assures the existence of robust algorithm requires C(f) 0 for all F.
B.1 Proof of Lemma B,2
Denote by N!a.8] the random variable that counts the number of decisions of a between rounds a and b. For consistency, for any small enough
0, for any r > 0, for some m, there must exist constant
13

---

E[N > (b - a) (b (b- a)Pr and by D the given model for D Note that e-contamination means we can arbitrarily choose D mell as long as d Dx) S Consider the case when Dx* Dx* eD2 cDe where P(D, k) ang for 0 S Dr - 1 and for elsewhere, and De is an arbitrary distribution. For π II \ consider D Dx. Then for k 2 max,Frr
Kr.p such that for all intervals (a, bi with b- 2 drp and a, > holds. Recall that we denote by Dx the true delay model for the decision
1
P((A reward arrival at k is not from π²
E P( 's reward arrives at k and n; + +²})
E P( 's reward arrives at k})
I1
(4)
11 + i=1
P( 's reward arrives at and H. = m=)))
Rr.pp Li=k mhp
Σ
B[1x [1
(Dr.p
| 1 + c(1 mfp'rr
Reg
where the inequality in the equation follows from the fact that the delay distribution of each decision sums to one. Therefore, P({A reward arrival at from x²)) }) > 6 = [1|-1++(11x0
<(1-n?-'1
Denote the rewards distributions associated with Da.. Do. and De as R Rx FExt,R,, Ra, and R. each. Then R.. R.. + e Ra cR must hold, where the mean of R.. and R. are supposed to be the same. Since the choice of R2 can be arbitrary by choosing R2 accordingly, we can conclude that the reward distributions of decisions * x² indeed suffer ò-contamination.
B.2 Proof of Lemma B.3
Recall that we use fx to refer to an element of F.,, while fn also denotes the r-coordinate of some F. Suppose that the ground-trus -trth model is f F. For g E F(f)", consistent algorithm must satisfy
(1 + o(1) Inn S DRT. (Pr.ul) Pa.)) =
Σ DRL. (PT.all pg.)) nEll
(5)
= DKL (Pille
+
Σ
Eyn [Na] DRL (Ru
(6)
mEllimy
[Na] (RI. + E,, log fa (rlo)
= DRt. p P finll 9.
Σ REIRaas
Es,
(7)
gn (rlo)
Above,
The inequality the equation (5) is from Dong and Ma (2022) 2
The equality in the equation (5) follows from the fact that algorithm- relattedd-reeddeeee-----o- terms cancel
out.
The inequality in the equation 66) is from the Divergence decomposition Lemma 31
The inequality the equation follows from the chain rule of KI. divergence
32
Let min(g(5), g8))), where r. is defined as in Assumption 4.5 By Assumption 4.4 for every r Er |r < ('()) a.c. {u,, Z La En, for for मO o J.. Note that Fo E IT s.l. Mg. 2 ub,,) }. Therefore, for every
Ty, there exists non-empty set E, {l, E F, E
MSe, ). Hense we can construct E(T)) = [1
E(T) C F(J) = (g E F n = {g E F
14

---

TT Ty.
log f=(rlo)
(1 (1+ Inn S DKL (P (P
+
Σ
By. (N)(n)) By,
for g E E(T)
(8)
gr (r(
Felliyy
log {r(r)
(+) (1+o(1))nnns S DKL
D 9.
f.y [N=(n)] (n)))BBB,. By,
for E E(T)
(9)
(r(r)))
(+) (1 (1(+()))nns S DKL
for E E(T)
(10)
9.
(+) (1+ < DKL
[P P
forg E (T))
(11)
(+) (1+ (1)) In DKL (...l for E (g E F Mgg. 1/a
(12)
where E = 11= Fx Ms,y S mn,) and (T) {1 F ln E Egi f for n' x).
Above,
Equation 8 follows from Assumption 4.5 and equation 7
The logical implication in equation
follows from the definition of (T)).
The logical implication in equation
10 follows from Assumptions 4.2 and 4.4
E.g. [rlo] Fig. [rlo]] < ('(6) I q(0) a.e. implies drv o), 9r
5 a.e.
from Assumption 4.2] therefore, under some 8-contamination
(x o), the con-
taminated Es, [r|o]
be farther from the true Fy, [rlo] than Egg [rlo]- Therefore,
DKL (fx( o) 9m ()) S a.e. due Assumption 4.3 and so E, log f-(rlo)
(x(r))
(s-(rio) log (r(o)
E, [DEL (f=(-1o) lI 9x [|)] S.
9- (rio)
The logical implication in equation (11) follows from Assumption 4.3
Define E.. {1,, - Mo,l (0)) (Kg. 2 M'N,, and E(T) ==
E En
fx' for n' + T). Note that ((r) S {TT). Then for g' E (T) ((x) and g E E(x)
with (Hy. 11,))(s )1,) 2 0, DKL Pf g.a) DKL (P in) due to the monotonicity assumption of Assumption 4.3
The logical implication in equation (12) follows from the fact that any element in {g E F Mga 2 MSny has element in E' that is strictly closer to f.
(g F Br E s.l. Mg. 2 US J. we immediately get (1+ o(1)) In S DEL 117h for g F(F).
Since F(J)= = {g E F mi t
15

---

C Proof of Lemma 4.9
Lemma 4.10 and Theorem 4.11
C.1 Proof of Lemma 4.9
Lemma C.1 (Upper bounding lemma).
4e'c-
satisfies
miin 2 2c
I k 1 for all n 2 1, where
W22.212
W is the principal branch Lambert W function (27).
Proof.
y x² 20tn a)
x e f(m) (by setting f(x) 2<In x)
20
dy d
dx de (x²) f(x) + +x²
d
(e-((x)
dr
(m)x)
In
e f(z) + + .e 1(x)
2c
c²
d (e-((o)) =c-s(o) (-f'(z)) and
(:: -
dx
d [=(1no)2)
!
(lnx)
In
f((x) dx 202
(Inx)²
2x Inx
26
2
(Inx)²
In
flar) 12)-((a)
2c
c²
In a
=e-((=)
2x
x²
2c
c²
Set the derivative
find the critical points:
(Inx)²
In
2x - x²
=0
2c
c²
2 (In x)2
In
r
20
c²
46 x: (In ar)² + 2x In
This is the uni-modal function with maximum, the derivatives are positive on the left side of the critical point and negative on right side the critical point. Also, note that xmax In Tmax S 2c as x)2 2 0. This implies that Tmax W function. Now note that
where W denote the principal branch Lambert W(267J
2,2
Clu Smax )
Mmax
2: maxx
2
(13)
x e
(2+ Emage Imaa
(14)
< e 2
(15)
20
2
4
<e -
(16)
(2
W (202)
Therefore,
46te-2 W(2633² satisfies
nla 2
202
< h 1 no
for all n 2 1.
16

---

Proof of Lemma
4.9 Let f be the ground truth model. After each of f's transition to E F(f).. at
period n,
J (k)
2
P(1
In
I
2nn +
Σ
maa (k)))
9 (k)
VB
k=1
= P(
fmg.
+ In
f4, (k)
+ In
9r,
) S 22nn n +
2
(k)))
97,
9 (k)
k=1
k=1
J +
f (k)
Dry
2C
2 P(1)
In
+ In
) S 2n +
Inn)) for some
(17)
Ons
Sz,
g (k)
vB
x P((
In [ro
DKL DKL 9m.))
+
In
fr. (k)
+
In
Ix,
fzy
gi, (k)
k=1
k=1
R=1
$ - (nnnn) for n 2 no for some no
<
00
(18)
In Fea
ma (k)
< P(()
DKIlfs 95.)
In
g5.
Σ
In
95g 9h, (k)
DKLLIma Da, (k) S - Inm]) for n 2 no
(19)
STa.
n
f (k)
S P(
In
DKI (xgl -lnn,
In
DKI Sag (k:)
95,
f
k=
In gag DKLLOFy, Dig (R:)) 2 -Inn] for norn: 2 no
2 - Inn,
2h, (k)
k=1
In Fz.
f2,(k)
P({ k=1
DKc(JTmy S - 1nn) U 1
In
DKI(JE, S2, (ki)
gr,
fr,
k=1
< - imn) u E
In Sr, DKL Pa (k))
s - =lnn)) for 2
g4 (k)
k=
miln
$ 30
2.2
(20)
12cte-2 1 W (2 n²
(21)
Above,
Equation
17 follows from the fact that (kmax(k: decreases with the rate 1/n.
Equation 18 follows from the fact that nDKII wIn from the Assumption 4.7
Equation follows from the fact that substracting positive value on the left does not change the inequality.
Equation followss from the fact that the log- logelikeli ratios bounded by constant c due to Assumption 4.8 and thus sub gaussian random variables with 0² -
2
Equation 21 from Lemma C.I
Therefore, after each time bad transition to g F(f) happens, the event (Eh= In S6 (R) gF, S
2 2n
gmax (k)) happens only finite many times (more precisely, smaller than 3- 1 / S
W(269)
6 W(2 in expectation by the Borel-Cantelli lemma, which implies that the inference will arrive at the correct instance within finite expected time.
=² -²²2
17

---

C.2 Proof of Lemma 4.10
Proof of Lemma 4.10
Suppose that f is the ground truth model. For any g E FFF fr, when f= f.
Bay (k)
n1
2
P(
2 2ln +
mmax (k)})
(k)
v3
k=1
[In gz
F,y
Pxy (k)
"
P(
+ In
+ In
2 2 2n +
8 (k)))
J
fāy (k)
gaz
vB
$ P(
In fa
+
In
faz
DKI.lfaysFF Sr, (k))
$ (k)
2h, (1:)
DKL (k),, (()))rs)) 2 2lmn))
(22)
gas
In gos
Sxz (k)
< P(
S 2 n,,
In
- DRu(JE,
s 2lnn,
fT
1=
In Szy (k)
(KI (K).
< 1
yns
k=1
< P((
In Dwy fxy
2 2mm U
In
Ix (k)
DKulla,, (k) 2 21nn]
x=1
R=1
In Tūy (k)
DRIlLh (k), 2 21nn))
Oz,
k=1
1
4cte- 1
<
2
(23)
W (2c2)² n² n
Above,
Equation 22 follows from the reverse Pinsker's inequality 33 (total variation distance smaller than implies KL divergence smaller than v/²)
Equation 23 follows from Lemma 4.3 of Dong and Ma (2022) (2), which says that Po {<ET In P. Q
cg) I <ex((-c), and the fact that the log- logelikelihood ratios are
bounded due Assumption 4.8 and thus sub-gaussian random variables.
Therefore, the event holds total only for finite rounds of k in expectation (more precisely, bounded 8ete-2 n²
by (1 + W 6 by the Borel-Cantelli lemma.
C.3 Proof of Theorem 4.11
Combining Lemmas 4.9 and 4.10
can conclude that f F(f*) holds only for finite number of rounds in expectation. That is, regret is bounded in expectation with value A(1 + 4oto 2 x²
W(263)² B
18

---

D Proof of Theorem 5.2 (Linear contextual bandit case)
Let θ be the set of all parameters, and let 0* è be the unknown true parameter. Suppose that C(0) = 0 for 0 E e. By Theorem 2.3 2.3 and Theorem 5.1 {6myo (zy) j E A} spans IR for 0 e.
Denote Tx (n) be the number of arrivals of context X E E
Then for any E O {8*).
DKL.
Por.mmoollPo (.
Σ
E [T2 (r, -
(24)
2
xEA
1
-0" -0)T
Σ
Te (n)
(0* -0--0) 0)
2
LEA
1 2 2000 0) nÊ
(n)
xx
(0r -0--0) 0)
n
LZEA
1
3 1100 8112n2mmin
(25)
12(1)
(26)
Above,
The equality in equation (4) is from the divergence decomposition lemma Lattimore and
Szepesvári 31
min equation
25) denotes the smallest eigenvalue for Exjoup [6mmg (x,) ( (x
x² Ax af is larger than the smallest
The inequality of equation
25 is from the fact that
eigenvalue of A.
0 is equivalent to The equality of equation (26) comes from the fact that Amin
(Ømye (iz)) j A} spanning Rd 28
E Proof of Theorem 5.6 (Reinforcement learning with Linear MDP case)
It is straightforward that the proof of Theorem 5.6 is almost equivalent the proof of Theorem 5.2 except that the problem here is inferring 6n separately for each h E [H].
19

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope?
Answer: [Yes]
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Theory paper.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [ÑA]
Justification: Theory paper.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Theory paper.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Theory paper.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: Theory paper.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS
Code of Ethics https///euurrp..ccpaaaa////aaaaa
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Learning theory paper that is not bound to practical implications.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Theory paper.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Theory paper.
13. New Assets
20

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Theory paper.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: Theory paper.
15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Theory paper.
21


Reviews:
[{"review_id": "FxAgvQUDNZ", "reviewer": "Reviewer_bj5z", "summary": "The paper considers the problem of regret minimization under delayed rewards. The paper considers the setting where the Decision-making with Structured Observations  (DMSO) setting and asks when the learner can achieve logarithmic regret when the reward signal is delayed and we only have an estimate of the delay distribution up to precision \\epsion within the given model class. \n\nThe main results are twofold:\n1. They show that logarithmic regret under \\eps-misspecified delay distribution is possible (no matter what is \\eps) only if a certain algebraic quantity called the graves-lai constant is 0 for all models in the given family. Interestingly, the same condition is necessary for obtaining constant regret bounds in DMSO. \n2. They provide an upper bound showing that for learning settings for which the the graves-lai constant is 0, and an additional condition called cross-informativeness holds, then one can obtain an upper bound on the regret under delayed reward feedback (with \\eps-contaminated delay distribution). \n\nOverall I like the paper as it draws interesting connections between two seemingly different learning settings.", "questions": "1. Given the close connection, is there a direction reduction of consistent algorithms with delayed rewards to algorithms with bounded regret in DMSO? \n2. The definition of consistency in Defn 2.2 seems to only consider algorithms that have at most logarithmic regret. Can we handle \\eps-contamination in reward delay distribution, in the absence of the graves-lai constant being 0, if we are OK with some sort of sublinear regret? It seems to me right now that this notion of consistency is too strong.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Interesting connection between two seemingly unrelated topics \n- Applications to linear contextual bandits and linear MDPs given", "weaknesses": "Weakness: \n\nI think the overall exposition can be improved a bit. In particular, it was not clear to me for a long time whether the agent also received the time step for which the reward corresponds to, when it received the delayed reward at a later time step. Other minor issues are: \n- Theorem 4.11 should provide a regret bound, if possible. \n- Definition 5.4 is also called the Linear Bellman Complete setting. It might be worth adding this phrase for completeness.  \n\nMinor typo:\n- \"for of\" at the end of page 5 last paragraph \n- First paragraph of page 5 says that d_{TV}(D, D^) >= \\eps implies that |E[D] - E[D^]| > 0 (should be >=0 I think).  \n- Section 4.2 title -- remove \"when\" \n- Section 4.2.2 first line has redundancy", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Answer to comments in \"Weaknesses\"**\n\n**Comment 1.**\n> It was not clear to me for a long time whether the agent also received the time step for which the reward corresponds to, when it received the delayed reward at a later time step. \n\n**Author response to Comment 1**:\\\nThank you for pointing this out. We believe two changes we made will address this:\n* Instead of \"unknown reward delays\", we now use \"anonymous delayed rewards\" to avoid ambiguity and improve representation.\n* We added a clarifying sentence in the introduction that _\"the agent never observes the period information for which each reward corresponds to, even after it receives the delayed reward at the later time step.\"_ Thank you for your suggestion.\n\n**Comment 2.**\n> Theorem 4.11 should provide a regret bound, if possible.\n\n**Author response to Comment 2**:\n\n_(Modified Theorem 4.11)_:\n*  _Under Assumption 4.7 and 4.8, the algorithm ST2C, which does not require any knowledge of the delay distribution model, achieves bounded regret. More precisely, the regret is bounded by $\\Delta(1+5\\frac{4 c^4 e^{-2} }{\\mathcal{W}\\left(2 c^2\\right)^2}) \\frac{\\pi^2}{6}$, where $\\mathcal{W}$ denote the principal branch lambert W function (which is an increasing function)._\n\n, where $\\Delta$ is the maximum per-period mean reward difference among decisions and $c$ is from Assumption 4.8:\n\n_(Modififed Assumption 4.8)_:\n* _For all $f, g \\in \\mathcal{F}, \\pi \\in \\Pi$, and $o \\in \\mathcal{O}, |\\log \\frac{f\\pi}{g\\pi} |<c$ for some $c>0$._\n\n**Comment 3.**\n> Definition 5.4 is also called the Linear Bellman Complete setting. It might be worth adding this phrase for completeness.\n\n**Author response to Comment 3**:\\\nThank you for your suggestion. We updated this part accordingly.\n\n**Comment 4.**\n> Fix minor typo.\n\n**Author response to Comment 4**:\\\nThank you for pointing them out. We fixed them accordingly.\n\n### **Answer to comments in \"Questions\"**\n**Comment 1.**\n> Given the close connection, is there a direct reduction of consistent algorithms with delayed rewards to algorithms with bounded regret in DMSO?\n\n**Author response to Comment 1**:\\\nThe phrase _\"reduction of consistent algorithms with delayed rewards to algorithms with bounded regret in DMSO\"_ correctly depicts our contribution. We will add it to the conclusion section.\nIn other words, we prove $poly(n)$ lower bound for the case when we cannot achieve bounded regret.\n\n**Comment 2.**\n>The definition of consistency in Defn 2.2 seems to only consider algorithms that have at most logarithmic regret. Can we handle $\\epsilon$-contamination in reward delay distribution, in the absence of the graves-lai constant being 0, if we are OK with some sort of sublinear regret? It seems to me right now that this notion of consistency is too strong.\n\n**Author response to Comment 2**:\\\nYou are absolutely right. While this paper proves $poly(n)$ lower bound for the case when \"Graves-Lai constant being 0\" does not hold,\nupper bound for this case is an open question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "78I7O64ccA", "reviewer": "Reviewer_ykEi", "summary": "The paper investigates interactive decision-making in bandits, contextual bandits, and reinforcement learning, focusing on the Graves-Lai constant's role in achieving bounded regret. It establishes that a zero Graves-Lai constant is necessary and sufficient for bounded regret, but questions its practical utility due to its stringent requirements. The study shows that $\\epsilon$-robustness in delay model robustness cannot be achieved if the Graves-Lai constant is non-zero, presenting a negative result for consistent algorithms. However, it offers a positive result for linear rewards models, indicating that a zero Graves-Lai constant is sufficient for bounded regret without delay model knowledge, balancing efficiency and robustness.", "questions": "1. Is the definition of \"the sub-optimality gap of decision\" also used in the previous paper? If yes, give the citation.\n2. Is the assumption of \"Realizability\" generally used in other work? If yes, give the citation.\n3. The lower bound is studied by other work. What is the explicit form of the lower bound and can you derive the instance-independent lower bound?\n4. What is the application of your algorithm and can you run some experiments?", "limitations": "There is no experiment.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper investigated some interesting questions.", "weaknesses": "1. The related work on robustness seems not comprehensive.\n2. There is no experiment.\n3. The authors didn't give proper citations in definitions or assumptions and so on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Answer to comments in \"Weaknesses\"**\n\n**Comment 1**.\n\n> \"There is no experiment.\"\n\n**Author response to comment 1**:\\\nAS DMSO is a framework that generalizes many different sequential-decision making problems\n such as bandits, contextual bandits, and reinforcement learning and so forth, it is quite uncommon for papers on DMSO to include\nsimulation experiments for particular environments. Examples include all the key papers of this paper:\n* The first paper that suggested the concept \nof DMSO ([Foster, Kakade, Qian, Rakhalin, 2021][1] \\[1\\])\n* The paper that characterizes Graves-Lai coefficient for DMSO ([Dong and Ma, 2023 ][2] \\[2\\])\n* The paper that proposes an instance-optimal algorithm for DMSO ([Wagenmaker and Foster, 2023 ][3] \\[3\\])\n\nand all other related papers on DMSO:\n* [Chen, Mei and Bai (2024)][4] \\[4\\]\n* [Foster, Golowich and Han (2023)][5] \\[5\\]\n* [Foster, Golowich, Qian and Rakhlin (2023)][6] \\[6\\]\n* [Foster, Han, Qian and Rakhlin (2024)][7] \\[7\\]\n\n**Comment 2**. \n\n> \"The related work on robustness seems not comprehensive.\"\n\n**Author response to Comment 2**:\\\nThank you for pointing this out. We believe that we were not clear enough about the fact that this is the first\npaper that approaches _anonymous_ delay in rewards through the lens of robustness. \n\nFor the papers that discuss robustness/unrestricted delay for _non-anonymous_ delays (i.e., the setup where agents can associate each delayed reward to the arm it is from), \nwe are adding a new separate paragraph with 10-15 papers in the related work section, including:\n\n* [Thune, Cesa-Bianchi, and Seldin (2019)][8] \\[8\\]\n* [Wu, Ha, and Wager (2022)][9] \\[9\\]\n* [Jin, Lancewicki, Luo, Mansour, Rosenberg (2022)][10] \\[10\\]\n* [Masoudian, Zimmert, and Seldin (2024)][11] \\[11\\]\n* [Zimmert and Seldin (2020)][12] \\[12\\]\n* ... \n\n**Comment 3.**\n> The authors didn't give proper citations in definitions or assumptions and so on.\n\n**Author response to Comment 3**:\\\nThank you for pointing this out and leaving detailed instruction in **Questions** section as questions. We will answer your questions in the next section.\n\n\n### **Answer to comments in \"Questions\"**\n**Comment 1.**\n>Is the definition of \"the sub-optimality gap of decision\" also used in the previous paper? If yes, give the citation.\n\n**Author response to Comment 1**:\\\nThis is a kind of folklore definition used in almost every bandit/reinforcement learning\npapers that deals with the concept of regret. Specifically for a decision's sub-optimality gap, \nwe can cite [Foster, Kakade, Qian, Rakhalin, 2021][1] \\[1\\], as this paper defines \"decision\" in a DMSO framework and also the sub-optimality gap of a decision accordingly.\n\n**Comment 2.**\n> Is the assumption of \"Realizability\" generally used in other work? If yes, give the citation.\n\n**Author response to Comment 2**:\\\nThank you for pointing this out; we will cite the following three papers.\n* [Agarwal, Dudik, Kale, Langford and Schapire, 2012][13] \\[13\\]\n* [Du, Kakade, Lee, Lovett, Mahajan, Sun and Wang, 2021][14] \\[14\\]\n* [Foster, Kakade, Qian, Rakhalin, 2021][1] \\[1\\])\n\n**Comment 3.**\n> The lower bound is studied by other work. What is the explicit form of the lower bound and can you derive the instance-independent lower bound?\n\n**Author response to Comment 3**:\n* When the Graves-Lai constant is 0, the lower bound is clearly O(1), as we proved that there is an algorithm\nthat achieves the upper bound of O(1).\n* When the Graves-Lai constant is not 0, our first main result shows that no algorithm can achieve sub-polynomial regret. In other words, \"we prove _poly(n)_ lower bound\". We greatly appreciate your pointing out this, as we have not yet explicitly stated this sentence in the previous draft.\n\n**Comment 4.** \n> What is the application of your algorithm and can you run some experiments?\n\n**Author response to Comment 4**:\\\nWhile the algorithm proposed is a proof-of-concept algorithm of which purpose is to\nprove the equivalence of bounded regret and any-level delay robustness, you can apply this algorithm for real-world platforms.  \nAs discussed in our draft, for linear contextual bandits, for example, the necessary & sufficient condition for bounded regret ([Hao, Lattimore, and Szepesvari 2020][16] \\[16\\]) can be easily satisfied by having rich enough context space ([Kang and Kumar, 2023][15] \\[15\\]). \nIn [Kang and Kumar, 2023][15] \\[15\\]'s Spotify context, million daily users can be considered a rich enough context for exploring 60,000 new songs uploaded daily. That is, we can apply our algorithm to this Spotify music recommendation and exploration example.\n\nFor the author response related to experiments, please see above.\n\n\n[1]: https://arxiv.org/abs/2112.13487\n\n[2]: https://openreview.net/forum?id=oGVu9spZaJJ\n\n[3]: https://proceedings.mlr.press/v195/wagenmaker23a.html\n\n[4]: https://arxiv.org/abs/2209.11745\n\n[5]: https://proceedings.mlr.press/v195/foster23b.html\n\n[6]: https://proceedings.neurips.cc/paper_files/paper/2023/hash/3fcd0f8747f9217c6dbc45ed138b1fde-Abstract-Conference.html\n\n[7]: https://arxiv.org/abs/2404.10122\n\n[8]: https://proceedings.neurips.cc/paper/2019/hash/0e4f5cc9f4f3f7f1651a6b9f9214e5b1-Abstract.html\n\n[9]: https://dl.acm.org/doi/abs/10.1145/3490486.3538376\n\n[10]: https://proceedings.neurips.cc/paper_files/paper/2022/hash/d850b7e0cdc7f1c0820c6ad85405ae94-Abstract-Conference.html\n\n[11]: https://openreview.net/forum?id=aLgJssbizV\n\n[12]: https://proceedings.mlr.press/v108/zimmert20a.html\n\n[13]: https://proceedings.mlr.press/v22/agarwal12\n\n[14]: https://proceedings.mlr.press/v139/du21a.html\n\n[15]: https://arxiv.org/abs/2301.12571\n\n[16]: https://proceedings.mlr.press/v108/hao20b.html", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mfKdqtK7BG", "reviewer": "Reviewer_uxdM", "summary": "This paper studies the relationship between bounded regret and delay robustness in interactive decision-making, which captures bandits, contextual bandits, and reinforcement learning. The authors show that the Graves-Lai constant being zero is necessary for achieving delay model robustness when reward delays are unknown. On the other hand, it is also shown that the Graves-Lai constant being zero is sufficient for achieving bounded regret without delay model knowledge for linear reward models.", "questions": "1. The positive results are specific to linear reward models. Could you please elaborate on the challenges in extending these results to other types of models?\n\n2. What if the reward delay distribution is precisely known?\n\n3. Has there been any prior research in bandit or reinforcement learning that investigates the connection between regret and delay?\n\n4. Minor typo on Line 253: \"indicates\" -> \"indicate\".", "limitations": "This theoretical paper may have limited direct societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper introduces a novel connection between bounded regret and delay robustness, offering a fresh perspective on interactive decision-making.\n2. The paper presents results in both directions, although positive results are limited to linear models.", "weaknesses": "Indeed, the requirement for the Graves-Lai constant to be exactly zero is exceedingly strong. In the context of linear bandits, it necessitates that the set of optimal actions spans the entire action space, a condition that is nearly unattainable in practical applications. This consideration could potentially diminish the paper's overall significance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Answer to comments in \"Weaknesses\"**\n\n**Comment 1.**\n> Indeed, the requirement for the Graves-Lai constant to be exactly zero is exceedingly strong. \nIn the context of linear bandits, it necessitates that the set of optimal actions spans the entire action space, a condition that is nearly unattainable in practical applications. \nThis consideration could potentially diminish the paper's overall significance.\n\n**Author response to Comment 1**:\n* **Because the requirement for bounded regret is indeed exceedingly strong, our negative result shines.**: We show that the consistent algorithm design regime, one of the most popular algorithm design regime, may be impractical under anonymous reward delays, as Graves-Lai constant to be exactly zero is exceedingly strong. **In other words, we prove reduction of consistent algorithms with delayed rewards to algorithms with bounded regret in DMSO**.\n* Cost of satisfying condition of Graves-Lai constant being zero indeed questions the usefulness of bounded regret algorithm design, but **the cost we should pay is not too much impractical in practice**. As discussed in our draft, for linear contextual bandits, for example, the necessary & sufficient condition for bounded regret ([Hao, Lattimore, and Szepesvari 2020][1] \\[1\\]) can be easily satisfied by having rich enough context space ([Kang and Kumar, 2023][2] \\[2\\]). For example, in [Kang and Kumar, 2023][2] \\[2\\]'s Spotify context, million daily users can be considered a rich enough context for exploring 60,000 new songs uploaded daily. That is, we can apply our algorithm to this Spotify music recommendation and exploration example.\n\n\n### **Answer to comments in \"Questions\"**\n\n**Comment 1.**\n> The positive results are specific to linear reward models. \nCould you please elaborate on the challenges in extending these results to other types of models?\n\n**Author response to Comment 1**:\\\nThank you for this question. As discussed in Section 4.2.1, cross-informativeness is\nthe key to achieving such positive result. For linear cases, we attribute Section 5 to show that cross-informativeness holds when the Graves-Lai constant is 0. \nTo extend the positive result in our paper for other type of models, one can show that the model's particular structure allows Graves-Lai constant being 0 to imply cross-informativeness. \nWe will add this answer to the discussions section.\n\n**Comment 2.**\n> What if the reward delay distribution is precisely known?\n\n**Author response to Comment 2**:\n* As discussed in 1.1. Related work, we can then apply [Pike-Burke et al., 2018][3] \\[3\\], which requires an assumption that the mean of delay distribution is precisely known (which cannot be achieved under $\\epsilon$-contamination however small $\\epsilon$ is).\n* Of course, knowing _anonymous_ reward's delay distribution precisely is highly unrealistic.\n\n**Comment 3.**\n> Has there been any prior research in bandit or reinforcement learning that investigates the connection between regret and delay?\n\n**Author response to Comment 3**:\\\nThank you for your question. We believe that we were not clear enough about the fact that this is the first\npaper that approaches _anonymous_ delay in rewards through the lens of delay robustness. \n\nFor the papers that discuss robustness/unrestricted delay for _non-anonymous_ delays (i.e., the setup where agents can associate each delayed reward to the arm it is from), \nwe are adding a new separate paragraph with 10-15 papers in the related work section, including:\n\n* [Thune, Cesa-Bianchi, and Seldin (2019)][4] \\[4\\]\n* [Wu, Ha, and Wager (2022)][5] \\[5\\]\n* [Jin, Lancewicki, Luo, Mansour, Rosenberg (2022)][6] \\[6\\]\n* [Masoudian, Zimmert, and Seldin (2024)][7] \\[7\\]\n* [Zimmert and Seldin (2020)][8] \\[8\\]\n* ... \n\n**Comment 4.**\n> Minor typo on Line 253: \"indicates\" -> \"indicate\".\n\n**Author response to Comment 4**:\\\nThank you for pointing this out. We have fixed the typo.\n\n\n[1]: https://proceedings.mlr.press/v108/hao20b.html\n[2]: https://arxiv.org/abs/2301.12571\n[3]: https://arxiv.org/abs/1709.06853\n[4]: https://proceedings.neurips.cc/paper/2019/hash/0e4f5cc9f4f3f7f1651a6b9f9214e5b1-Abstract.html\n[5]: https://dl.acm.org/doi/abs/10.1145/3490486.3538376\n[6]: https://proceedings.neurips.cc/paper_files/paper/2022/hash/d850b7e0cdc7f1c0820c6ad85405ae94-Abstract-Conference.html\n[7]: https://openreview.net/forum?id=aLgJssbizV\n[8]: https://proceedings.mlr.press/v108/zimmert20a.html", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8Fxjqxubq1", "reviewer": "Reviewer_f9VR", "summary": "This paper studies anonymous delay (i.e. when it is unknown which trial the delayed reward came from) in interactive decision making. It gives a strongly negative result that if the reward delay distribution is not exactly known and the “Grave-Lai constant” is non-zero then no algorithm has sub-polynomial regret. It also gives a positive result that, for linear-rewards models, the Grave-Lai constant being zero is sufficient for achieving bounded regret with no knowledge of the delay distribution.", "questions": "Line 131: what is an $\\epsilon$-probability removal?\n\nLine 135: $\\nu$ lots a lot like $v$ - I recommend a different letter", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think that the negative result (Theorem 4.1) is quite neat although I am not sure of its importance (the other reviewers’ opinions on this will certainly influence my final score).", "weaknesses": "Whilst Theorem 4.1 rules out (unless the Grave-Lai constant is zero) sub-polynomial regret with unknown reward distributions, it does not rule out algorithms with very small polynomial regret. A lower bound on a polynomial exponent would be a much better result in my opinion.\n\nThe positive result seems limited. As the authors say in the abstract - “as the condition of the Graves-Lai constant being zero may be a strong requirement for many applications, the practical usefulness of pursuing bounded regret (or in this case unknown delay functions) has been questioned”.\n\nLine 7 of Algorithm 1 suggests that F must be finite. If this is true then this is a serious limitation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Answer to comments in \"Weaknesses\"**\n\n**Comment 1**. \n> \"Whilst Theorem 4.1 rules out (unless the Grave-Lai constant is zero) sub-polynomial regret with unknown reward distributions, it does not rule out algorithms with very small polynomial regret. A lower bound on a polynomial exponent would be a much better result in my opinion.\"\n\n **Author response to comment 1**:\n* When the Graves-Lai constant is not 0, our first main result shows that no algorithm can achieve sub-polynomial regret. In other words, **\"we prove _poly(n)_ lower bound\"**, which resonates with your point that _\"a lower bound on a polynomial exponent will be nice\"_. We greatly appreciate your pointing this out, as we have not yet explicitly stated this sentence in the previous draft.\n\n**Comment 2**.\n\n> \"The positive result seems limited. As the authors say in the abstract - “as the condition of the Graves-Lai constant being zero may be a strong requirement for many applications, the practical usefulness of pursuing bounded regret (or in this case unknown delay functions) has been questioned\"\n\n**Author response to Comment 2**:\\\nCost of satisfying condition of Graves-Lai constant being zero indeed questions the usefulness of bounded regret algorithm design, but **the cost we should pay is not too much impractical**. As discussed in our draft, for linear contextual bandits, for example, the necessary & sufficient condition for bounded regret ([Hao, Lattimore, and Szepesvari 2020][2] \\[2\\]) can be easily satisfied by having rich enough context space ([Kang and Kumar, 2023][3] \\[3\\]). For example, in [Kang and Kumar, 2023][3] \\[3\\]'s Spotify context, million daily users can be considered a rich enough context for exploring 60,000 new songs uploaded daily.\n\n**Comment 3**.\n\n> \"Line 7 of Algorithm 1 suggests that F must be finite. If this is true then this is a serious limitation.\"\n\n**Author response to Comment 3**:\\\nThank you for your suggestion. We modified our Algorithm 1 pseudocode to remove the error.\\\n[Link to the new Algorithm 1 pseducode's image][4]\n\n\n\n### **Answer to comments in \"Questions\"**\n\n**Comment 1.**\n> \"Line 131 : what is an $\\epsilon$-probability removal?\"\n\n**Author respoonse to Comment 1**:\\\n$\\epsilon$-probability removal from a distribution is also called \"Subtractive Contamination\" in robust statistics literature. The definition is as follows:\\\n_Definition ($\\epsilon$-probability removal or Subtractive Contamination)_\\\n_Given a parameter $0<\\epsilon<1$ and a distribution $D$ on inliers, we say that one can sample from $D$ with $\\epsilon$-subtractive contamination if the following holds: for some event $R$ with probability $1-\\epsilon$, one can obtain independent samples from the distribution of $D$ conditioned on $R$. In other words, with probability $\\epsilon$, the event $R^c$ occurs and these samples are removed from the data stream. This allows an adversary to remove an $\\epsilon$-fraction of inlier samples._\n \n**Comment 2.**\n\n> Line 135: $\\nu$ lots a lot like $v$ - I recommend a different letter.\n\n**Author response to Comment 2**:\\\nThe new draft now uses $\\mu$.\\\n(Please note that we cannot show this change, as NeurIPS does not allow the pdf draft replacement in openreview)\n\n[1]: https://epubs.siam.org/doi/abs/10.1137/S0363012994275440\n\n[2]: https://proceedings.mlr.press/v108/hao20b.html\n\n[3]: https://arxiv.org/abs/2301.12571\n\n[4]: https://postimg.cc/VSdHXhf7\n\n\n\\[1\\]: Graves, T. L., & Lai, T. L. (1997). Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3), 715-743.\n\n\\[2\\]: Hao, B., Lattimore, T., & Szepesvari, C. (2020). Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics (pp. 3536-3545). PMLR.\n\n\\[3\\]: Kang, H., & Kumar, P. R. (2023). Recommender system as an exploration coordinator: a bounded O (1) regret algorithm for large platforms. arXiv e-prints, arXiv-2301.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "taobj54d2Q", "reviewer": "Reviewer_3wWt", "summary": "The paper explores interactive decision-making scenarios encompassing bandits, contextual bandits, and reinforcement learning, focusing on the concept of regret minimization. It highlights the Graves-Lai constant, where its zero value is crucial for achieving bounded regret in interactive decision-making. This condition, however, may be stringent for practical applications, prompting questions about its feasibility. The study extends this analysis to include robustness against unknown reward delays, termed ϵ-robustness, which measures algorithmic resilience to misspecified delay models. The main finding asserts that achieving ϵ-robustness is impossible for consistent algorithms unless the Graves-Lai constant is zero. The paper contrasts this negative result with positive outcomes in linear reward models, demonstrating that a zero Graves-Lai constant is sufficient for achieving bounded regret without knowledge of delay models. This dual perspective underscores the theoretical and practical implications of the Graves-Lai constant in designing robust learning algorithms for interactive decision-making under uncertainty.", "questions": "Can you provide a more intuitive explanation of how delay robustness affects decision-making in interactive systems?\n\nAre there specific conditions under which the proposed delay-robust algorithms may not perform optimally? What are the limitations of the theoretical framework?\n\nHow confident are you that the proposed algorithms will perform well in practical scenarios, given the complexities and uncertainties inherent in real-world applications?", "limitations": "Explicit discussion of the limitations of the proposed approach and avenues for future research could enhance the paper. Addressing these aspects would provide a more balanced view of the scope and potential of the findings.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes significant contributions by establishing theoretical results that link the Graves-Lai constant to delay robustness in interactive decision-making scenarios. It introduces the concept of ϵ-delay robustness, which quantifies how learning algorithms perform under ϵ-contaminated delay models.\n\nIt provides rigorous theoretical foundations, leveraging concepts from robust statistics and decision theory to analyze the impact of delay model misspecification on learning algorithms.\n\nThe problem of attributing delayed rewards to decisions (anonymous feedback) is clearly articulated, which is essential for understanding the challenges addressed by the proposed algorithms.", "weaknesses": "While the paper provides theoretical analysis and proofs, empirical validation through simulations or real-world experiments could strengthen the practical relevance of the results. Lack of empirical validation might limit the confidence in how well the theoretical findings translate into actual performance improvements in real interactive decision-making scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Answer to comments in \"Weaknesses\"**\n\n**Comment 1.**\n> While the paper provides theoretical analysis and proofs, \nempirical validation through simulations or real-world experiments \ncould strengthen the practical relevance of the results. \nLack of empirical validation might limit the confidence in\n how well the theoretical findings translate into actual performance\n improvements in real interactive decision-making scenarios.\n\n**Author response to Comment 1**:\\\nThank you for your comment. It is true that empirical validation or simulation studies are \nout of our paper's scope as in other papers on DMSO. \\\n_(DMSO is a framework that generalizes many different sequential-decision making problems,it is quite uncommon for papers on DMSO to include simulation experiments for particular environments. Examples include all the key papers of this paper:_ \n* _The first paper that suggested the concept of DMSO ([Foster, Kakade, Qian, Rakhalin, 2021][1] \\[1\\])_\n* _The paper that characterizes Graves-Lai coefficient for DMSO ([Dong and Ma, 2023 ][2] \\[2\\])_\n* _The paper that proposes an instance-optimal algorithm for DMSO ([Wagenmaker and Foster, 2023 ][3] \\[3\\])_\\   \n* And so forth, including all other papers on DMSO.\n\n)\n\nHowever, to help readers to understand the real-world applicability of this paper's theoretical result, \nthe new draft will have a paragraph on how the Graves-Lai constant being 0 works in practice. \n*  As discussed in our draft, for linear contextual bandits, the necessary & sufficient condition for bounded regret ([Hao, Lattimore, and Szepesvari 2020][4] \\[4\\]) can be easily satisfied by having rich enough context space ([Kang and Kumar, 2023][4] \\[4\\]). \nIn [Kang and Kumar, 2023][4] \\[4\\]'s Spotify context, million daily users can be considered a rich enough context for exploring 60,000 new songs uploaded daily.  That is, we can apply our algorithm to this Spotify music recommendation and exploration example.\n\n### **Answer to comments in \"Questions\"**\n\n**Comment 1.**\n> Can you provide a more intuitive explanation of how delay robustness affects decision-making in interactive systems?\n\n**Author response to Comment 1**:\\\nTo achieve O(log n) regret, you must pull the best arm much more than you pull the other arms. This hinders identification of non-optimal arms, as\na very small contamination in your knowledge about optimal arm's delay distribution will hinder you from getting a good enough statistical information to help conclude whether a reward is from a non-optimal arm.\n\n**Comment 2.**\n> Are there specific conditions under which the proposed delay-robust algorithms may not perform optimally? What are the limitations of the theoretical framework?\n\n**Author response to Comment 2**:\n* Recall that algorithm proposed is a proof-of-concept algorithm of which purpose is to prove the equivalence of bounded regret and any-level delay robustness. \nTo this end, the key assumption we make for this algorithm is that the Graves-Lai constant is 0 (= the iff condition for bounded regret ([Hao, Lattimore and Szepesvari 2021][5] \\[5\\])). \nWe prove $poly(n)$ lower bound for the case when this assumption does not hold. But we don't prove any upper bound for the case when the \"Graves-Lai constant being 0\" does not hold.\n\n* For non-linear setting, whether our positive result works is an open question.\n\n**Comment 3.**\n> How confident are you that the proposed algorithms will perform well in practical scenarios, given the complexities and uncertainties inherent in real-world applications?\n\n**Author response to Comment 3**:\n* As described above, in real-world online platforms with diverse users, the condition that Graves-Lai constant being 0 easily holds. \nTo see how well bounded regret algorithm like ours works in practical recommender systems, see [Kang and Kumar, 2023][4] \\[4\\]. \n* Graves-Lai constant being 0 is not likely to hold in smaller systems.\n\n\n### **Answer to comments in \"Limitations\"**\n**Comment 1.**\n>Explicit discussion of the limitations of the proposed approach and avenues for future research could enhance the paper. Addressing these aspects would provide a more balanced view of the scope and potential of the findings.\n\n**Author response to Comment 1**:\\\nThank you for this comment. In discussions section, we will include the following ideas:\n* While this paper proves $poly(n)$ lower bound for the case when \"Graves-Lai constant being 0\" does not hold,\nupper bound for this case is an open question.\n* The algorithm proposed is a proof-of-concept algorithm of which purpose is to prove the equivalence of bounded regret and any-level delay robustness. \nTo this end, the key assumption we make for this algorithm is that the Graves-Lai constant is 0 (= the iff condition for bounded regret ([Hao, Lattimore and Szepesvari 2021][5] \\[5\\])). While large systems such as Spotify satisfies this condition (a million daily users for 60,000 new songs exploration), smaller systems won't satisfy this condition.\n* As discussed in Section 4.2.1, cross-informativeness is\nthe key to achieving the positive result in our paper. For linear cases, we attribute Section 5 to show that cross-informativeness holds when the Graves-Lai constant is 0. \nWhether we can extend the positive result in our paper for other type of models is an open question. Towards this direction, one may want to show that a model's particular structure allows Graves-Lai constant being 0 to imply cross-informativeness.\n\n\n\n[1]: https://arxiv.org/abs/2112.13487\n\n[2]: https://openreview.net/forum?id=oGVu9spZaJJ\n\n[3]: https://proceedings.mlr.press/v195/wagenmaker23a.html\n\n[4]: https://arxiv.org/abs/2301.12571\n\n[5]: https://proceedings.mlr.press/v108/hao20b.html", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## 1. Overall comments and thank you response
We first want to thank all reviewers for putting enormous efforts in reviewing this paper. \
We are happy to hear that there was no major issue found by the reviewers, while we were told by all 5 reviewers that this paper
* makes significant contributions by establishing theoretical results and provides rigorous theoretical foundations leveraging concepts from robust statistics and decision theory, while the problem is clearly articulated, which is essential for understanding the challenges addressed by the proposed algorithms. _(Reviewer 3wWt)_
* introduces a novel connection between bounded regret and delay robustness _(Reviewer uxdM)_
* draws interesting connections between two seemingly different learning settings _(Reviewer bj5z)_
* investigated some interesting questions _(Reviewer ykEi)_
* presents a negative result that is quite neat _(Reviewer f9VR)_

### **For each of the reviews, we have submitted a separate author rebuttal below.**

## 2. Summary of the author responses on weaknesses and questions by multiple reviewers
**Point 1.** 
> "incomprehensiveness of related works on robustness/unrestricted delay" (by Reviewer ykEi and uxdM)

**Answer to Point 1**: \
We believe that we were not clear enough about the fact that this is the first paper that approaches _anonymous_ delay in rewards through the lens of delay robustness. \
For the papers that discuss robustness/unrestricted delay for _non-anonymous_ delays (i.e., the setup where agents can associate each delayed reward to the arm it is from), we are adding a new separate paragraph with 10-15 papers in the related work section, including:
* [Thune, Cesa-Bianchi, and Seldin (2019)][4] 
* [Wu, Ha, and Wager (2022)][5] 
* [Jin, Lancewicki, Luo, Mansour, Rosenberg (2022)][6] 
* [Masoudian, Zimmert, and Seldin (2024)][7] 
* [Zimmert and Seldin (2020)][8] 

**Point 2.** 
> "There is no experiment" (by Reviewer ykEi and 3wWt)

**Answer to Point 2**: \
AS DMSO is a theoretical framework that generalizes many different sequential-decision making problems
 such as bandits, contextual bandits, and reinforcement learning and so forth, **it is not a common practice for papers on DMSO to include
simulation experiments for particular environments.** Examples include all the key papers of this paper:
* The first paper that suggested the concept 
of DMSO ([Foster, Kakade, Qian, Rakhalin, 2021][1])
* The paper that characterizes Graves-Lai coefficient for DMSO ([Dong and Ma, 2023][2])
* The paper that proposes an instance-optimal algorithm for DMSO ([Wagenmaker and Foster, 2023][3])

and all other papers on DMSO:
* [Chen, Mei and Bai (2024)][9] 
* [Foster, Golowich and Han (2023)][10]
* [Foster, Golowich, Qian and Rakhlin (2023)][11] 
* [Foster, Han, Qian and Rakhlin (2024)][12] 

**Point 3.** 
> "The requirement for bounded regret is indeed exceedingly strong, as pointed out by authors. Doesn't it potentially diminish the paper's overall significance? Is it practical?" (Reviewer f9VR, uxdM, bj5z)

**Answer to Point 3**: 
* **Because the requirement for bounded regret is indeed exceedingly strong, our negative result shines**; we show that _consistent (i.e., $\log n$ regret for all instances) algorithm design (e.g., ([Dong and Ma, 2023][2] and [Wagenmaker and Foster, 2023][3])  may not be practical_ under anonymous delayed rewards, as _we prove reduction of consistent algorithms with anonymous delayed rewards to algorithms with bounded regret_ in DMSO. That is, we prove $poly(n)$ lower bound for the case when bounded regret cannot be achieved.
* The algorithm proposed for positive result is a proof-of-concept algorithm of which purpose is to prove the equivalence of bounded regret and any-level delay robustness. To this end, the key assumption we make for this algorithm is that the Graves-Lai constant is 0 (= the iff condition for bounded regret ([Hao, Lattimore and Szepesvari 2021][14])). **It is not hard for systems with large enough user pool such as Spotify to satisfy this strong requirement** (a million daily users are enough for 60,000 new songs exploration ([Kang and Kumar, 2023][13]). Therefore, we can apply our proposed algorithm in large digital platforms such as Spotify. **However, smaller systems won't satisfy this requirement**.

## 3. Attached pdf 
The attached pdf includes the following information:
* Updated Algorithm 1 with improved representation, to fix the issue raised by reviewer f9VR

[1]: https://arxiv.org/abs/2112.13487
[2]: https://openreview.net/forum?id=oGVu9spZaJJ
[3]: https://proceedings.mlr.press/v195/wagenmaker23a.html
[4]: https://proceedings.neurips.cc/paper/2019/hash/0e4f5cc9f4f3f7f1651a6b9f9214e5b1-Abstract.html
[5]: https://dl.acm.org/doi/abs/10.1145/3490486.3538376
[6]: https://proceedings.neurips.cc/paper_files/paper/2022/hash/d850b7e0cdc7f1c0820c6ad85405ae94-Abstract-Conference.html
[7]: https://openreview.net/forum?id=aLgJssbizV
[8]: https://proceedings.mlr.press/v108/zimmert20a.html
[9]: https://arxiv.org/abs/2209.11745
[10]: https://proceedings.mlr.press/v195/foster23b.html
[11]: https://proceedings.neurips.cc/paper_files/paper/2023/hash/3fcd0f8747f9217c6dbc45ed138b1fde-Abstract-Conference.html
[12]: https://arxiv.org/abs/2404.10122
[13]: https://arxiv.org/abs/2301.12571
[14]: https://proceedings.mlr.press/v108/hao20b.html

Meta-review: This paper received rather positive reviews, but none of the reviewers was that excited. So I read the paper myself, and I found it interesting and quite original. 

After discussion, the only reviewer that was slightly negative changed the grade to 5, hence I am happy to recommend acceptance !
Decision: Accept (poster)