Is O(log N) practical? Near-Equivalence Between Delay Robustness and Bounded Regret in Bandits and RL

Authors: enoch h kang
p r kumar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 22:49:35

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.

Main paper: 
 introduction: 
 We consider the cost of addressing stochastic and anonymous delayed rewards in Decision-Making with Structured Observations (DMSO) [1, 2] , which generalizes interactive decision-making problems, such as structured bandits, contextual bandits, and reinforcement learning 2 . In many real-life applications of interactive decision-making problems, stochastic and unknown delays in reward make it challenging to attribute the sequence of observed outcomes to previous decisions. In medical treatments, for example, a doctor cannot easily be sure whether a medical outcome is due to the effect of current treatment or due to 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' [4, 5] 3 . Under this setting, the decision maker never observes the period information for which each Figure 1 : Examples of misspecification of the reward delay model of decisions (π 1 , π 2 , π 3 ) 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 a challenge. Some knowledge (e.g., mean) of the probabilistic distribution of each decision'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 we can design an 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 statistics literature is ϵ-robustness [7] . Given a parameter ϵ > 0 and true distribution D, a model distribution D is called an ϵ-(general) contamination of D if d T V (D, D) ≤ ϵ, where d T V denotes the total variation distance function 4 . Figure 1 illustrates some examples of ϵ-contamination of the delay models. As ϵ-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 delay robustness will be, "up to which ϵ the algorithm's properties are robust to ϵ-contamination of delay model misspecification?".In this paper, we prove that no consistent (i.e., uniformly sub-polynomial regret) algorithm for DMSO can be designed to be robust to ϵ-contamination of delay model misspecification unless DMSO's Graves-Lai constant [9, 2, 1] being zero. While this is a strong negative result, we also provide a positive result for linear DMSO problems (linear contextual bandit, reinforcement learning with linear MDPs), showing that the Graves-Lai constant being zero [9, 10, 11] 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, 1, 10, 11] , the results in this paper strongly motivate the practical usefulness of designing learning systems where we can achieve bounded regret.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 on delayed rewards [12, 13, 14, 15] , but [4] was the first to formalize the unknown stochastic reward delays assumption in interactive decision making problems, which led to the literature on 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 a strong assumption that the mean of delay distribution is precisely known, which cannot be achieved under ϵ-contamination however small ϵ is 5 (In Section 4, we show that no algorithm can be consistent when ϵ > 0). [16] provides another consistent algorithm for stochastic bandits that also does not require any knowledge of delay distributions and improves [4] , but it requires a 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.While our work centers on delayed anonymous rewards-where 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. [21] derived near-optimal regret bounds for adversarial MDPs with delayed bandit feedback, addressing the challenges posed by feedback delays in adversarial environments. [22] 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 "best-of-both-worlds" algorithm that improves upon [22] by providing both adversarial guarantees and near-optimal stochastic performance without requiring prior knowledge of the maximal delay. 
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 a DMSO problem framework is specified as a tuple (Π, R, O, F), where Π denotes the decision space, R denotes the reward space, O denotes the observation space, and F = π∈Π F π denotes the model class where F π ⊆ △ R×O (Here, △ E notation means the space of all possible probability distributions over a set E). 6 We use f π to refer to an element of F π , with f π being the π-coordinate of f ∈ F. A ground-truth model f ⋆ ∈ F governs the rewards and the observations based on the decisions made in the rounds. While f ⋆ is unknown to the learner, it is typically assumed that a 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 groundtruth model f ⋆ .• The learning protocol for the DMSO problem consists of n rounds. In round k ≤ n, 1. The learner makes a decision π k ∈ Π.2. A reward r k ∈ R and an observation o k ∈ O are generated, where (r k , o k ) ∼ f ⋆ π k ∈ F π k 3.Learner observes o k . If there are reward delays, the learner observes R k , the set of rewards that arrive at the round k. R k is equivalent to r k only if there are no reward delays.Given that we characterized the DMSO problem framework, we can now describe a learning algorithm for it. Let h k be the history up to round k, i.e., h k = {(π j , R j , o j )} k-1 j=1 where π j ∈ Π, R j ∈ R, o j ∈ O and H be the set of all possible histories of rounds for k ≥ 1. A learning algorithm A is defined as an element of A ⊆ (H → △ Π ), which is a subset of the set of all possible mappings from the history space H to the set of all possible distributions over Π. That is, at each round k, given the historyh k ∈ H, a learning algorithm A ∈ A chooses p k = A(h k ) ∈ △ Π .The decision at round k, π k , is sampled from p k . Note that f ∈ F, A ∈ A and the round n completely determine the stochastic behavior of the learning protocol up to round n, i.e., they induce a probability distribution we call P f,n,A [•] over the set of all histories up to round n. We also denote the respective expectation by E f,n,A [•] . When the meaning is clear from the context, we useP f,n [•] and E f,n [•] instead of P f,n,A [•] and E f,n,A [•].Given (r, o) ∼ f π , we denote µ fπ := E fπ [r] . Let π f ∈ arg max π∈Π µ fπ denote an optimal decision for the model f . The sub-optimality gap of decision π for model f is defined as ∆ f (π) := µ fπ f -µ fπ . When the ground truth model is f , choosing π f at each round until round n yields the largest value of total reward until round n. Therefore, we can measure the optimality of an algorithm A until round n in terms of regret, which is defined byReg f,A (n) := E A,f,n n k=1 ∆ f (π k ) .(1)Reg f,A (n) is a quantity that is dependent on the true model instance f . Since the true model f is unknown to the learner a priori, a good learning algorithm must be able to perform well for all possible f ∈ F. Therefore, one might want to define the goodness of an algorithm by its capability to achieve the minimal value of Reg f,A (n) among all possible algorithms for all the instances f ∈ F. However, this is not achievable; a bespoke algorithm that always chooses π f will outperform all possible algorithms for the instance f , while suffering linear regret for the instances in F \ f . Since many problems have algorithms that incur sub-polynomial regret for all instances, it is common to exclude algorithms that suffer polynomially increasing regret in some instances. This idea is formalized in the following definition that restricts the space of 'interesting' algorithms. Definition 2.2 (Graves and Lai (1997) [9] ). A learning algorithm A is called consistent if Reg f,A (n) = o (n p ) holds for every p > 0 and f ∈ F.For DMSO problems, it has been recently shown that any consistent algorithm'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 ∈ F, the expected regret of any consistent algorithm A satisfiesEQUATIONwhere C(f, n) is the solution to the optimization equationEQUATIONwhere D KL is the KL divergence and F(f) := {g ∈ F | π g = π f }.Corollary 2.4. Let f ⋆ ∈ F be the ground-truth model. For a consistent algorithm to achieve sub-logarithmic regret, C(f ⋆ ) = 0 must hold. That is, achievement of sub-logarithmic regret for all possible instances of F can be assured a priori only if C(f ) = 0 for f ∈ F. Theorem 2.5 (Wagenmaker and Foster [1] ). Expected regret of order C(f ⋆ ) ln n can be achieved for DMSO problems without delays. That is, bounded regret can be assured if C(f ) = 0 for f ∈ F.In robust statistics, one of the oldest and the most commonly used concepts for modeling contaminated data is the concept of ϵ-contamination [7] . Given a parameter 0 < ϵ < 1 and original distribution D, a distribution X is called an ϵ-additive contamination (or Huber contamination) of D if X is a mixture distribution of D and an unknown arbitrary distribution E, with their selection probabilities being (1 -ϵ) for D and ϵ for E. Furthermore, A distribution X is called an ϵ-subtractive contamination of D if it is equivalent to an arbitrary ϵ-probability removal from D (and normalization). Finally, we say that a distribution X is a (general) ϵ-contamination of D if X can be constructed by removing ϵ-probability from D and replacing that ϵ with equal mass from some arbitrary distribution E.As discussed earlier, the concept of ϵ-contamination is closely related to the concept of total variation distance. Given a space of distributions, the total variation distance, denoted as d T V (ν, υ), is defined as d TV (ν, υ) := 1 2 ∥ν -υ∥ 1 = sup E∈Σ |ν(E) -υ(E)|, where Σ stands for the measurable sets on which ν and υ are defined. It is well known that d T V is a metric that satisfies interesting properties such as 1) d T V = 0 if and only if ν = υ and 2) d T V = 1 if and only if ν and υ are singular, i.e. there exists E such that ν(E) = 1 and υ(E) = 0. It is also well known that the concept of ϵ-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 a parameter 0 < ϵ < 1, a distribution X is an ϵ-contamination of D (and vice versa) if and only if d T V (X, D) = ϵ.3 Main Model: ϵ-delay Robustness Denote the true reward delay distributions of each decision π ∈ Π by D π . Every timeπ k is determined at each round k, d k ∼ D π k is generated along with the generation of (r k , o k ) ∼ f π . While o k is observed immediately at round k, r k is scheduled to arrive at round d k + 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 d k 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 ϵ-contamination of the true delay distribution models {D π } π∈Π resulting in information about { Dπ } π∈Π instead, where Dπ is an outcome of ϵ-contamination of the delay distribution model D π , i.e., d T V (D π , Dπ ) ≤ ϵ. Note that ϵ-contamination of delay distribution models encompasses many possible misspecification of information about delay distribution. For example, it implies misspecification of mean of delay distribution asd T V (D π , Dπ ) > ϵ implies |E[D] -E[ D]| > 0 (See discussions in Assumption 4.We now propose the formal definition of robustness in terms of delay distribution knowledge. Definition 3.1. We say that a consistent algorithm is ϵ-delay robust if it is consistent when the given delay distributions are ϵ-contaminations of the true delay distributions. 
negative result: delay robustness requires: 
 C(f ) = 0 for all f ∈ FGiven the definition of ϵ-delay robustness provided in Section 3, the main question is when a consistent, ϵ-delay robust algorithm exists. The answer is quite negative: unless C(f ⋆ ) = 0 holds, no consistent algorithm can be ϵ-delay robust, however small ϵ > 0 is. Theorem 4.1. Under minor technical assumptions (see Assumptions 4.2-4.5 below), regardless of how small ϵ > 0 is, a consistent learning algorithm can be ϵ-delay robust only if C(f ⋆ ) = 0. Theorem 4.1 implies that the concept of consistent algorithm fails even with a very small misspecification of the delay model unless the Graves-Lai constant C(f ⋆ ) satisfies C(f ⋆ ) = 0. Since we want to design a learning system with existence of a consistent algorithm that works for all instances of f ∈ F, we need C(f ) = 0 for f ∈ F, which was the necessary and sufficient condition for achieving bounded regret when there were no reward delays (Corollary 2.4 and Theorem 2.5)The intuition behind the proof of Theorem 4.1 (See Appendix B for details), is 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 as small as we want. However, in the case of ϵ-contamination of delay models, under minor technical assumptions below (Assumptions 4.2-4.5), we can always provide a delay model contamination that makes the precision of any consistent algorithm's reward attribution no better than 1 -δ for some δ > 0. This leads to reward distribution suffering δ-contamination, which makes impossible to design a consistent algorithm.The assumptions required for Theorem 4.1 are as follows. Assumption 4.2. For the family of distributionsD r|o := {f π (• | o) | f ∈ F, π ∈ Π, o ∈ O}, there exists a function q(δ) s.t. for D 1 , D 2 ∈ D r|o , |E[D 1 ] -E[D 2 ]| ≤ q(δ) implies d T V (D 1 , D 2 ) ≤ δ.For some special families of reward distributions, such q that satisfies Assumption 4.2 is known [8] . (Let k be a constant in what follows)• For the family of Gaussian distributions with standard deviation 1, q(δ) = kδ.• For the family of log-concave distributions with standard deviation 1, q(δ) = kδ log(1/δ).• For the family of distributions with kth moment bounded by 1 for k ≥ 2, q(δ) = kδ 1-1/k . Assumption 4.3 expresses the conditional unimodality in likelihood functions in terms of rewards. Assumption 4.3. Given ground truth f ∈ F and g 1 , g 2 ∈ F, for every π ∈ Π,E g 1 π [r|o] ≤ E g 2 π [r|o] ≤ E fπ [r|o] or E g 1 π [r|o] ≥ E g 2 π [r|o] ≥ E fπ [r|o] implies D KL (f π (• | o), g 2 π (• | o)) ≤ D KL (f π (• | o), g 1 π (• | o))almost everywhere (a.e.). Assumptions 4.4 and 4.5 exclude trivial cases where the reward information is not at all needed for the inference of the ground-truth model f . Assumption 4.4 (Density of F π for every π ∈ Π). For every π ∈ Π,{g π ∈ F π | µ gπ ≥ µ fπ f } ∩ {g π ∈ F π | |E fπ (r | o) -E gπ (r | o)| ≤ q(δ) a.e.} is nonempty given δ > 0.Intuitively, {g π ∈ F π | µ gπ ≥ µ fπ f } is the set of hypotheses in F π we need to reject, and{g π ∈ F π | |E fπ (r | o) -E gπ (r | o)| ≤ q(δ) a.e.} is the set of hypothesis we cannot reject under contamination of outcomes from decision π. Note that{g π ∈ F π | |E fπ (r | o) -E gπ (r | o)| ≤ q(δ) a.e.} ⊆ {g π ∈ F π | |µ gπ -µ fπ | ≤ q(δ)}.Assumption 4.5. Let g o π be the marginal distribution of the observation of g π ∈ F π . There existsr o > 0 such that for every π ∈ Π, |µ fπ -µ gπ | ≤ r o implies f o π = g o π a.e.. Note that f o π = g o π a.e. if and only if D KL (f o π ∥g o π ) = 0 holds. If D KL (f o π ∥g o π )> 0, no information on the rewards will be required to reject g π under f π , 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, r 0 in the Assumption 4.5 is +∞.C(f ) = 0 for all f ∈ F enables Super-Robust Bounded RegretIn the previous section, we saw in Theorem 4.1 that C(f ) = 0 for f ∈ F is required to assure the existence of a delay-robust consistent algorithm. We also saw that C(f ) = 0 for f ∈ F is required to assure sub-logarithmic regret for all possible instances of true f (Theorem 2.3).Here, we 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, we need to define and explore two new concepts: cross-informativeness and max-contamination.Recall that we denote by P f,n,A the distribution of the outcomes of algorithm A for the model instance f ∈ F by the nth round. Let us denote the algorithm that always chooses decision π ∈ Π as π. Then Lemma 4.6 motivates the concept of cross-informativeness. Lemma 4.6. Suppose that f ∈ F is the ground-truth model instance. Then C(f ) = 0 implies thatD KL P f,n,π f ∥P g,n,π f = Ω(n) holds for g ∈ F(f ) c . Proof. Suppose that C(f ) = 0. According to equation (3), this implies that there exist w π f and 0 ≤ n 0 < ∞ such that for all n ≥ n 0 , w π f D KL (f π f ∥g π f ) ≥ 1, ∀g ∈ F(f ) c . Therefore, D KL P f,n,π f ∥P g,n,π f = nD KL (f π f ∥g π f ) ≥ 1 wπ f n holds ∀g ∈ F(f ) c for n ≥ n 0 .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(f ) c ), simply by exclusively playing π f forever, while incurring zero regret. Lemma 4.6 shows how informative π f is when the true hypothesis is f . When the true hypothesis is not f , π f can be arbitrarily uninformative.The natural question now arises is how much cross-informativeness (informativeness of π h ∈ Π for the ground truth f ∈ F when h ̸ = f ) is sufficient for us to 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 5). Assumption 4.7 (Cross-informativeness). Suppose that f ∈ F is the ground-truth model. Then for any g, h ∈ F, D KL (P f,n,π h ∥P g,n,π h ) = ω(ln n) holds.Note that the cross-informativeness lower bound rate of ω(ln n) in Assumption 4.7 is a much weaker rate than the lower bound rate Ω(n) in Lemma 4.6.Whatever true delay distribution the reward delays follow, the maximum number of reward arrivals from π by the round k is N π (k), the total number of π decisions by the round k. The maxcontamination of the decision π ′ ∈ Π at round k is defined asδ max π ′ (k) := min( π∈Π\π ′ Nπ(k) N (k), 1),where N (k) stands for the total number of reward arrivals by round k. Note that the contamination of reward arrival at k is bounded by the max-contamination δ max π ′ (k), as the delay distributions of decisions are stationary, i.e., they do not change over time.Assumption 4.8. For all f, g ∈ F, π ∈ Π, and o ∈ O, ln fπ gπ < c for some c > 0. This implies gπ(•|o) is well-defined on the support of g π and is finite a.e..D KL (f π (• | o)∥g π (• | o)) < ∞.g,k,π indicate the likelihood of g ∈ F that is computed as if all reward arrivals by the round k are from the decision π. (Note that this is actually not true, as we allow decision transitions in Algorithm 1.) Note that lnP c f,k,π P c g,k,π = n k=1 ln f c π (k) g c π (k), where f c π (k) and g c π (k) are likelihood of each data assuming that the data is from π.We now describe the algorithm Simply-Test-to-Commit (ST2C) as the Algorithm 1 below.Algorithm 1 Simply-Test-to-Commit (ST2C) Algorithm 1: Choose any h ∈ F , set f = h 2: for n = 1, 2, . . . do 3:Choose π f as the decision at period n 4:Observe on and Rn, newly compute δ max π f (n)5: if Fn := {g ∈ F | n k=1 ln g c π f (k) f c π f (k) ≥ 2 ln n + n k=1 2 √ β δ max π f (k)} ̸ = ∅ then 6:Choose any g ∈ Fn 7:Set f = g 8:end if 9: end forLater in Section 5, we will show that C(f ) = 0 for all f ∈ F, which is a design feature of a learning problem we decide a priori, is 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 a technical minor Assumption 4.8) is sufficient to allow Algorithm 1 to achieve bounded regret without any knowledge of delay distribution model.The following Lemma 4.9 shows that f stays at incorrect instances for only finite time, except for the periods f 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 to F \ f ⋆ ) happens. Lemma 4.10 shows that the total number of wrong transitions from the correct inferences is finite in expectation.Lemma 4.10. Under Assumption 4.8, the number of rounds Algorithm 1 satisfies the event , where W is the principal branch Lambert W function [27] , ∆ is the maximum per-period mean reward difference among decisions, and c is from Assumption 4.8.{ f = f ⋆ }∩{∃g ∈ F(f ⋆ ) c s.t. n k=1 ln g c π f (k) f c π f (k) ≥ 2 ln k + n k=1 2 √ β δ max π f (k)}Proof. Combining Lemmas 4.9 and 4.10, we can conclude that f / ∈ 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. 
equivalence of bounded regret and delay robustness in linear systems: 
 As discussed in Section 4.2, satisfying the cross-informativeness condition introduced in Assumption 4.7 is the key assumption that enables Algorithm 1 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 cross-informativeness condition if C(f ) = 0 for f ∈ F. That is, for those problems, the condition 'C(f ) = 0 for f ∈ F' is not only necessary (Section 4.1), 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 in Section 5.1 and 5.2.Hao, Lattimore, and Szepesvari [10] was the first to characterize when C(f ) = 0 holds for contextual linear bandit problems. In this paper, we follow the notations and settings of [10] as follows: Let's consider the stochastic M -armed contextual linear bandit with a horizon of n rounds with M arms and a finite A-size set of k-dimensional possible contexts X = {x j } j∈ [A] . At each round, a context is sampled according to the unknown distribution p over X and then observed. Every time a context is sampled, an arm choice (a decision in MDSO framework) happens. When the sampled context is x j and its chosen arm is m, we receive ϕ m (x j ) ′ θ + ϵ, where {ϕ m : R k → R d } m∈[M ] are linear representation functions that are assumed to be precisely known, θ 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 σ 2 .Let Θ be the set of all parameter vectors, and let θ ⋆ ∈ Θ be the unknown true parameter. Suppose that C(θ) = 0 for θ ∈ Θ. Let m jθ be an optimal arm for context j ∈ [A] when the true parameter is θ, i.e., m jθ ∈ argmax m∈[M ] ϕ m (x j ) ′ θ. 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 to be achieved if and only if ϕ m jθ (x j ) | j ∈ A spans R d for all θ ∈ Θ.Note that the condition that ' ϕ m jθ (x j ) | j ∈ A spans R d for all θ ∈ Θ' in Theorem 5.1 is easily satisfied a priori when we are given rich enough context set [29] . How does this easily satisfied condition work when there are anonymous delayed rewards? The following theorem of ours shows that ' ϕ m jθ (x j ) | j ∈ A spans R d for all θ ∈ Θ' implies that the Assumption 4.7 is satisfied. Theorem 5.2. Given contextual linear bandit setting described above, Assumption 4.7(D KL (P θ ⋆ ,n,π θ ∥P θ ′ ,n,π θ ) = Ω(n) holds for θ ′ ∈ F(θ ⋆ ) c ) is satisfied if ϕ m jθ (x j ) | j ∈ A spans R d for all θ ∈ Θ.See Appendix D for the proof of Theorem 5.2. 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 1 achieves bounded regret without any knowledge of delay distribution model if ϕ m jθ (x j ) | j ∈ A spans R d for all θ ∈ Θ (which is easily satisfied when the context space is rich enough [29] ).For contextual linear bandit setting described above, it has been shown that ' ϕ m jθ (x j ) | j ∈ A spans R d for all θ ∈ Θ' is equivalent to 'C(θ) = 0 for all θ ∈ Θ' [26, 2, 1] . Since C(θ) = 0 for all θ ∈ Θ is a necessary condition for a-priori assurance of any-level robustness of a consistent algorithm (Theorem 4.1), we have the following Corollary 5.3, 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 a priori guaranteed to be achieved if and only if ϕ m jθ (x j ) | j ∈ A spans R d for all θ ∈ Θ.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] .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 [11] , which are as follows: we are given a time-inhomogenous MDP M = S, A, H, {r h } H h=1 , P, µ , where S is finite state space, A is a finite action space, H is the length of each episode, {r h } are the reward functions where r h (s, a) the expected reward of a pair (s, a) ∈ S × A at time-step h, P := {p h } are the transition kernels, and µ is the initial state distribution. A policy π = (π 1 , . . . , π H ) ∈ Π is a sequence of per-time-step policies π h : S → A. For every h ∈ [H] := {1, . . . , H}, we define the state-action value function of a policy π asQ π h (s, a) = r h (s, a) + E π H i=h+1 r i (s i , a i ) and Q π ⋆ h (s, a) := Q ⋆ h (s, a) = sup π Q π h (s, a) = L h Q ⋆ h+1 (s, a) where L h Q ⋆ h+1 (s, a) := r h (s, a) + E s ′ ∼p h (s,a) max a ′ Q ⋆ h+1 (s ′ , a ′ ) .As in [11] , we focus on 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 (completeness) [30] ). Suppose that we are given a feature map ϕ h : S × A → R d h , possibly different at any h ∈ [H], mapping state-action pair (s, a) into a d h -dimensional vector ϕ h (s, a). For the set of bounded value function ∀(s, a ) and the associated parameter spaceQ h = {Q h | θ h ∈ Θ h : Q h (s, a) = ϕ h (s, a) ⊤ θ h ,Θ h = θ h ∈ R d : ϕ h (s, a) ⊤ θ h ≤ D . An MDP is said to satisfy zero Inherent Bellman Error (IBE) (or satisfy Bellman closure) if ∀h ∈ [H], sup Q h+1 ∈Q h+1 inf Q h ∈Q h ∥Q h -L h Q h+1 ∥ ∞ = 0 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. [11] ). Denote the optimal policy as π ⋆ and ϕ ⋆ h (s) := ϕ h (s, π ⋆ h (s)). In Linear MDPs satisfying Bellman closure, the condition that 'span{ϕ ⋆ h (s) | ∀s ∈ S, π ⋆ visits s at h with positive probability} = R d for all h ∈ [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(D KL (P θ ⋆ ,n,π θ ∥P θ ′ ,n,π θ ) = Ω(n) holds for θ ′ ∈ F(θ ⋆ ) c ) is satisfied if span{ϕ ⋆ h (s) | ∀s ∈ S, π ⋆ visits s at h with positive probability} = R d for all h ∈ [H].Again, as Assumption 4.8 trivially holds for linear problems [2] 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. 
conclusions: 
 In this paper, we characterize the link between consistent algorithms and delay robustness in interactive decision-making. The first main result states that, for consistent algorithms, the necessary condition for achieving any (small) level of robustness against delay model misspecifications is also sufficient for achieving bounded regret. Viewed from another perspective, this result urges us to revisit the practicality of the instance-dependent regret minimizing algorithm design regime [9, 1] 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 a 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 our second main result without restricting to linear problems. 
 
 Appendix: -In finite-armed bandit problems, each round is an arm pull. Π is the arm space, and R is the space of rewards from arms. Since there is no observation space O, the model class degenerates to F ⊆ (Π → ∆ R ). -In contextual bandit problems, each round is an arm pull. Π is the set (X → 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 o k ∈ O (which results from π k ) is the k + 1th round's context. Since the future context arrival is not affected by previous decisions, the model class degenerates to F ⊆ (Π → ∆ R ).-In episodic reinforcement learning problems, each round is an episode. Π is the set (S → A) 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 is characterized jointly by the initial state distribution and the transition kernel, which are shared across all the episodes.B Proof of Theorem 4.1Recall that P f,n,A [•] denotes the distribution of outcomes of algorithm A on the true model instance f by the round n. We further denote the marginal distribution of P f,n,A [•] in terms of decision π's rewards and outcomes byP π f,n,A [•]. Lemma B.1. Suppose that the ground-truth model is f ∈ F. Then a consistent algorithm must satisfy (1 + o(1)) ln n ≤ π∈Π D KL P π f,n,A ∥P π g,n,A for g ∈ F(f ) c .Proof. According to Dong and Ma (2022) [2] , any consistent algorithm A must satisfy (1 + o(1)) ln n ≤ D KL (P f,n,A ∥P g,n,A ) for g ∈ F(f ) c . Since the terms involving A (the algorithm used to collect the data) cancel out and the outcomes of decisions are independent of each other, Lemma B.3 shows that, under δ-reward contaminations in reward distributions of all π ̸ = π ⋆ , choosing optimal decision π ⋆ alone must be enough to satisfy the condition described in Lemma B.1 and otherwise, we cannot satisfy it. Lemma B.3. If the rewards of decisions π ∈ Π \ π f suffer δ-contamination for some δ > 0, consistency of the algorithm requires(1 + o(1)) ln n ≤ D KL P π f f,n ∥P π f g,n for all g ∈ F(f ) c .See Section B.2 for the proof of Lemma B.3.The rest of the proof of Theorem 4.1 is immediate from the derivation of [2] 's Theorem 2.3, which is as follows: from the chain rule of divergence, the random variable that counts the number of decisions of π between rounds a and b. For consistency, for any small enough p > 0, for any r > 0, for some m, there must exist a constant D KL P π f,n ∥P π g,n = E f,n [N π ] D KL (f π ∥g π ) holds for π ∈ Π. Defining w π := E f [N π ] /((1 + o(1)) ln n), Lemma B.EQUATION≤ |Π| -1 |Π| -1 + ϵ nr,p k i=k-nr,p E[1 πi=π ⋆ ] ≤ |Π| -1 |Π| -1 + ϵ nr,p (n r,p -n p r,p r) = |Π| -1 |Π| -1 + ϵ(1 -n p-1 r,p r)where the inequality in the equation ( 4) follows from the fact that the delay distribution of each decision sums to one. Therefore, P ({A reward arrival at k is fromπ ⋆ }) > δ := ϵ(1-n p-1 r,p r) |Π|-1+ϵ(1-n p-1 r,p r) .Denote the rewards distributions associated with D π ⋆ , Dπ ⋆ , D a , and D c as R π ⋆ , Rπ ⋆ , R a , and R c each. Then R π ⋆ = Rπ ⋆ + ϵR a -ϵR c must hold, where the mean of R π ⋆ and R π ⋆ are supposed to be the same. Since the choice of R a can be arbitrary by choosing R c accordingly, we can conclude that the reward distributions of decisions π ̸ = π ⋆ indeed suffer δ-contamination.Recall that we use f π to refer to an element of F π , while f π also denotes the π-coordinate of some f ∈ F. Suppose that the ground-truth model is f ∈ F. For g ∈ F(f ) c , a consistent algorithm must satisfyEQUATIONEQUATIONEQUATIONAbove,• The inequality in the equation ( 5) is from Dong and Ma (2022) [2] .• The equality in the equation ( 5) follows from the fact that algorithm-related terms cancel out.• The inequality in the equation ( 6) is from the Divergence decomposition Lemma [31] • The inequality in the equation (7) follows from the chain rule of KL divergence [32] .Let min(q(δ), r o ) = q ′ (δ), where r o is defined as in Assumption 4.5. By Assumption 4.4, for every π ̸ = π f , there exists a non-empty setEQUATIONEQUATIONEQUATION)whereE ′ π := {l π ∈ F π | µ fπ f ≤ µ lπ } and E ′ (π) := {l ∈ F | l π ∈ E ′ π , l π ′ = f π ′ for π ′ ̸ = π}. Above,• Equation ( 8) follows from Assumption 4.5 and equation (7) .• The logical implication in equation ( 9) follows from the definition of E(π).• The logical implication in equation (10) follows from Assumptions 4.2, 4.3 and 4.4: |E fπ [r|o] -E gπ [r|o]| ≤ q ′ (δ) ≤ q(δ) a.e. implies d T V (f π (• | o), g π (• | o)) < δ= E f o π E fπ(r|o) log fπ(r|o) gπ(r|o) = E f o π [D KL (f π (• | o) ∥ g π (• | o))] ≤ 0. • The logical implication in equation (11) follows from Assumption 4.3: Define Êπ := {|µ fπ -µ gπ | ≤ q ′ (δ)} ∩ {µ gπ ≥ µ fµ f } and Ê(π) := {l ∈ F | l π ∈ Êπ , l π ′ = f π ′ for π ′ ̸ = π}. Note that Ê(π) ⊆ E(π). Then for g ′ ∈ E ′ (π) \ Ê(π) and g ∈ Ê(π)with (µ gπ -µ fπ )(µ g ′ π -µ fπ ) ≥ 0, D KL P π f,n ∥P π g,n ≤ D KL P π f,n ∥P π g ′ ,n due to the monotonicity assumption of Assumption 4.3.• The logical implication in equation (12) follows from the fact that any element in {g ∈ F | µ gπ ≥ µ fπ f } has an element in E ′ that is strictly closer to f .Since F(f ≤ k 1 n 2 for all n ≥ 1, where W is the principal branch Lambert W function [27] .) c := {g ∈ F | π g ̸ = π f } = {g ∈ F | ∃π ∈ Π s.t. µ gπ ≥ µ fπ f }, we immediately get (1 + o(1)) ln n ≤ D KL P π f f,n ∥P π f g,n for g ∈ F(f ) c . C ProofProof.y = x 2 • e -x(ln x) 2 2c 2 = x 2 • e -f (x) (by setting f (x) = x(ln x) 2 2c 2 dy dx = d dx x 2 • e -f (x) + x 2 • d dx e -f (x) = 2x • e -f (x) + x 2 • e -f (x) - (ln x) 2 2c 2 + ln x c 2 (∵ d dx (e -f (x) ) = e -f (x) • (-f ′ (x)) and f ′ (x) = d dx x(ln x) 2 2c 2 = 1 2c 2 (ln x) 2 + 2x ln x • 1 x = (ln x) 2 2c 2 + ln x c 2 ) = 2xe -f (x) -x 2 e -f (x) (ln x) 2 2c 2 + ln x c 2 = e -f (x) 2x -x 2 (ln x) 2 2c 2 + ln x c 2Set the derivative to zero to find the critical points:2x -x 2 (ln x) 2 2c 2 + ln x c 2 = 0 2 = x (ln x) 2 2c 2 + ln x c 2 if x > 0 4c 2 = x(ln x) 2 + 2x ln xThis is the uni-modal function with a maximum, as the derivatives are positive on the left side of the critical point and negative on the right side of the critical point. Also, note that x max ln x max ≤ 2c 2 , as x(ln x) 2 ≥ 0. This implies that x max ≤ 2c 2 W(2c 2 ) , where W denote the principal branch Lambert W function. Now note thaty max = x 2 max • e -xmax(ln xmax) 2 2c 2 (13) = x 2 max • e -(2+ xmax c 2 ln xmax) (14) ≤ e -2 • x 2 max (15) ≤ e -2 2c 2 W (2c 2 ) 2 = 4c 4 e -2 W (2c 2 ) 2 (16) Therefore, k = 4c 4 e -2 W(2c 2 ) 2 satisfies e -n(ln n) 2 2c 2 ≤ k 1 n 2 for all n ≥ 1.Proof of Lemma 4.9. Let f be the ground truth model. After each of f 's transition to g ∈ F(f ) c , at period n,EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONAbove,• Equation 17 follows from the fact that δ max πg (k) decreases with the rate 1/n.• Equation 18follows from the fact that nD KL (f πg , g πg ) = D KL (P f,n,πg ∥P g,n,πg ) = ω(ln n) from the Assumption 4.7.• Equation 19 follows from the fact that substracting positive value on the left does not change the inequality.• Equation 20 follows from the fact that the log-likelihood ratios are bounded by constant c due to Assumption 4.8, and thus sub-gaussian random variables with σ 2 = c (lnEQUATION≤ P ({n k=1 ln g π f f π f ≤ 2 ln n, n k=1 ln f π f f c π f (k) -D KL (f π f , f c π f (k)) ≤ 2 ln n, , n k=1 ln g c π f (k) g π f -D KL (g c π f (k), g π f ) ≤ 2 ln n} c ) ≤ P ({ n k=1 ln g π f f π f ≥ 2 ln n} ∪ { n k=1 ln f π f f c π f (k) -D KL (f π f , f c π f (k)) ≥ 2 ln n} , ∪{ n k=1 ln g c π f (k) g π f -D KL (g c π f (k), g π f ) ≥ 2 ln n}) ≤ 1 n 2 + 2 4c 4 e -2W (2c 2 )EQUATIONAbove,• Equation 22 follows from the reverse Pinsker's inequality [33] (total variation distance smaller than δ implies KL divergence smaller than 1 √ β δ) • Equation 23follows from Lemma 4.3 of Dong and Ma (2022) [2] , which says that P Q m i=1 ln Pi Qi ≥ c ≤ exp(-c), and the fact that the log-likelihood ratios are bounded due to Assumption 4.8, and thus sub-gaussian random variables. Therefore, the event holds in total only for finite rounds of k in expectation (more precisely, bounded by (1 + 8c 4 e -2 W(2c 2 ) 2 ) π 2 6 ) by the Borel-Cantelli lemma.Combining Lemmas 4.9 and 4.10, we can conclude that f / ∈ F(f ⋆ ) holds only for a finite number of rounds in expectation. That is, regret is bounded in expectation with value ∆(1 + 5 4c 4 e -2 W(2c 2 ) 2 ) π 2 6 .Let Θ be the set of all parameters, and let θ ⋆ ∈ Θ be the unknown true parameter. Suppose that C(θ) = 0 for θ ∈ Θ. By Theorem 2.3 and Theorem 5.1, ϕ m jθ (x j ) | j ∈ A spans R d for θ ∈ Θ. Denote T x (n) be the number of arrivals of context x ∈ X .Then for any θ ∈ Θ \ {θ ⋆ },EQUATION= Ω(n)Above,• The equality in equation ( 24) is from the divergence decomposition lemma Lattimore and Szepesvári [31] • λ min of equation ( 25) denotes the smallest eigenvalue for E xj ∼p ϕ m (x j )ϕ m jθ (x j ) ⊤• The inequality of equation ( 25) is from the fact that x T Ax x T x is larger than the smallest eigenvalue of A.• The equality of equation (26) comes from the fact that λ min > 0 is equivalent to ϕ m jθ (x j ) | j ∈ A spanning R d [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 to the proof of Theorem 5.2, except that the problem here is inferring θ h separately for each h ∈ [H].One can refer to Appendix A (or[2,1] for a more comprehensive, detailed description) to see 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 forThis model class definition is equivalent to the definition used by Wagenmaker and Foster[1] because if A is a set, countable or not, the Cartesian product X A is defined to be the collection of all functions f : A → X. 


Decision: 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 !

Reviews: review: paper_summary: paper_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. 

The main results are twofold:
1. 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. 
2. 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). 

Overall I like the paper as it draws interesting connections between two seemingly different learning settings.
strength_weakness: strength_weakness: Weakness: 

I 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: 
- Theorem 4.11 should provide a regret bound, if possible. 
- Definition 5.4 is also called the Linear Bellman Complete setting. It might be worth adding this phrase for completeness.  

Minor typo:
- "for of" at the end of page 5 last paragraph 
- First paragraph of page 5 says that d_{TV}(D, D^) >= \eps implies that |E[D] - E[D^]| > 0 (should be >=0 I think).  
- Section 4.2 title -- remove "when" 
- Section 4.2.2 first line has redundancy
questions: questions: 1. Given the close connection, is there a direction reduction of consistent algorithms with delayed rewards to algorithms with bounded regret in DMSO? 
2. 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The related work on robustness seems not comprehensive.
2. There is no experiment.
3. The authors didn't give proper citations in definitions or assumptions and so on.
questions: questions: 1. Is the definition of "the sub-optimality gap of decision" also used in the previous paper? If yes, give the citation.
2. Is the assumption of "Realizability" generally used in other work? If yes, give the citation.
3. 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?
4. What is the application of your algorithm and can you run some experiments?
limitations: limitations: There is no experiment.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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?

2. What if the reward delay distribution is precisely known?

3. Has there been any prior research in bandit or reinforcement learning that investigates the connection between regret and delay?

4. Minor typo on Line 253: "indicates" -> "indicate".
limitations: limitations: This theoretical paper may have limited direct societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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”.

Line 7 of Algorithm 1 suggests that F must be finite. If this is true then this is a serious limitation.
questions: questions: Line 131: what is an $\epsilon$-probability removal?

Line 135: $\nu$ lots a lot like $v$ - I recommend a different letter
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Can you provide a more intuitive explanation of how delay robustness affects decision-making in interactive systems?

Are there specific conditions under which the proposed delay-robust algorithms may not perform optimally? What are the limitations of the theoretical framework?

How confident are you that the proposed algorithms will perform well in practical scenarios, given the complexities and uncertainties inherent in real-world applications?
limitations: 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.

Comments: comment: Thank you for your rebuttal. After considering the rebuttal, I have decided to keep my original rating.
I have read the authors' rebuttal and the comments from the other reviewers. I would like to keep my score unchanged.
**Comment 1.**
> I do not think that your response to comment 1 is correct. For instance, we could have, for every $\epsilon>0$, an algorithm with a regret of $\mathcal{O}\left(T^\epsilon\right)$. This means there is no polynomial lower bound. This does not mean that there exists an algorithm with regret $o\left(T^\epsilon\right)$ for every $\epsilon>0$. Hence, proving that there exists no algorithm with sub-polynomial regret is not the same thing as proving that there exists a polynomial lower bound on the regret. In any case, my question is asking if you can give the lower bound on the exponent (if one exists), which I guess would be problem dependent.

**Answer to comment 1**.\
I see your point. Although this paper's scope does not include an answer to what you are asking for, trying to answer that will be a really nice future research direction. **We will state this point in the discussion section, as it demonstrates a sharp boundary of our contribution**. This paper's focus is indeed on rejecting the popular notion of "consistent" algorithm design, which assure _uniform_ $o(n^p)$ regret for all $p>0$ and for all problem instances. As you pointed out, if we just say that there is no algorithm that satisfies $n^p$ regret for some $p$ we are wrong; we can at most say that there is no algorithm that satisfy $n^p$ regret for all $p$ for all problem instances. (i.e. it is kind of _uniform_ $poly(T)$ lower bound, **which is much weaker than $poly(T)$ lower bound**). Your point is clearly legitimate, as our result only negates the notion of consistency. Thank you very much for your comment.

**Comment 2.**
>I don't understand your response to comment 2 - could you please rephrase?

**Answer to Comment 2.**\
In linear contextual bandits, for example, Graves-Lai constant being 0 can be easily satisfied in large enough systems; it only requires some constant times $klogk$ daily Spotify users (=# of contexts) to satisfy the constraint of graves-Lai constant being 0, if the number of new songs (=# of arms) uploaded daily is $k$ ([Kang and Kumar 2023][1]). As daily new songs to explore are around 60,000 and $60,000 \times \log 60,000 \le 300,000$ daily users, we can apply any algorithm that requires Graves-Lai constant being 0 for Spotify (which has more than $100m$ daily users). 

[1]: https://arxiv.org/abs/2301.12571

**Comment 3.**
>In regards to comment 3 - in your new algorithm (for infinite F) how computationally hard is it to find such a g?

**Answer to Comment 3.**\
We really appreciate your pointing this out. Although $\mathcal{F}_n$ in our new algorithm can be easily computed in some problems like bandits, **we may definitely need to assume an existence of an oracle who can find an instance $g\in \mathcal{F}_n$ in general to abstract the computational complexity**. Like [Wagenmaker and Foster 2023][2] does, we will add an assumption on this and state that "We emphasize that the focus of this work is primarily statistical, and leave addressing the computational challenges for specific problems for future work." Thank you for improving this work.

[2]: https://proceedings.mlr.press/v195/wagenmaker23a.html
I do not think that your response to comment 1 is correct. For instance, we could have, for every $\epsilon>0$, an algorithm with a regret of $\mathcal{O}(T^\epsilon)$. This means there is no polynomial lower bound. This does not mean that there exists an algorithm with regret $o(T^\epsilon)$ for every $\epsilon>0$. Hence, proving that there exists no algorithm with sub-polynomial regret is not the same thing as proving that there exists a polynomial lower bound on the regret. In any case, my question is asking if you can give the lower bound on the exponent (if one exists), which I guess would be problem dependent.

I don't understand your response to comment 2 - could you please rephrase?

In regards to comment 3 - in your new algorithm (for infinite F) how computationally hard is it to find such a g?
Thank you for the reply. The responses are satisfactory. Please add these works in your next version. I am raising my score by +1.
References to the official Rebuttal below:

\[1\]: Foster, Dylan J., et al. "The statistical complexity of interactive decision making." arXiv preprint arXiv:2112.13487 (2021).

\[2\]: Dong, K., & Ma, T. (2023). Asymptotic instance-optimal algorithms for interactive decision making. The Eleventh International Conference on Learning Representations (ICLR)

\[3\]: Wagenmaker, A. J., & Foster, D. J. (2023). Instance-optimality in interactive decision making: Toward a non-asymptotic theory. In The Thirty Sixth Annual Conference on Learning Theory (pp. 1322-1472). PMLR.

\[4\]: 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. 

\[5\]: Hao, B., Lattimore, T., & Szepesvari, C. Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics (pp. 3536-3545). PMLR. (2020)
References to the official Rebuttal below:

\[1\]: Hao, B., Lattimore, T., & Szepesvari, C. Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics (pp. 3536-3545). PMLR. (2020)

\[2\]:  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. 

\[3\]: Pike-Burke, Ciara, et al. "Bandits with delayed, aggregated anonymous feedback." International Conference on Machine Learning. PMLR, 2018.

\[4\]: Thune, Tobias Sommer, Nicolò Cesa-Bianchi, and Yevgeny Seldin. "Nonstochastic multiarmed bandits with unrestricted delays." Advances in Neural Information Processing Systems 32 (2019).

\[5\]: Wu, Han, and Stefan Wager. "Thompson sampling with unrestricted delays." Proceedings of the 23rd ACM Conference on Economics and Computation. 2022.

\[6\]: Jin, Tiancheng, et al. "Near-optimal regret for adversarial mdp with delayed bandit feedback." Advances in Neural Information Processing Systems 35 (2022): 33469-33481.

\[7\]: Masoudian, S., Zimmert, J., & Seldin, Y. A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays. In ICML 2024 Workshop: Foundations of Reinforcement Learning and Control

\[8\]: Zimmert, J., & Seldin, Y. (2020, June). An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics (pp. 3285-3294). PMLR.
References to the official Rebuttal below:

\[1\]: Foster, Dylan J., et al. "The statistical complexity of interactive decision making." arXiv preprint arXiv:2112.13487 (2021).

\[2\]: Dong, K., & Ma, T. (2023). Asymptotic instance-optimal algorithms for interactive decision making. The Eleventh International Conference on Learning Representations (ICLR)

\[3\]: Wagenmaker, A. J., & Foster, D. J. (2023). Instance-optimality in interactive decision making: Toward a non-asymptotic theory. In The Thirty Sixth Annual Conference on Learning Theory (pp. 1322-1472). PMLR.

\[4\]: Chen, F., & Mei S., & Chen F. (2024). Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyond

\[5\]: Foster, D. J., Golowich, N., & Han, Y. (2023, July). Tight guarantees for interactive decision making with the decision-estimation coefficient. In The Thirty Sixth Annual Conference on Learning Theory (pp. 3969-4043). PMLR.

\[6\]: Foster, D. J., Foster, D. J., Golowich, N., Qian, J., Rakhlin, A., & Sekhari, A. (2023). Model-free reinforcement learning with the decision-estimation coefficient. Advances in Neural Information Processing Systems, 36.

\[7\]: Foster, D. J., Han, Y., Qian, J., & Rakhlin, A. (2024). Online estimation via offline estimation: An information-theoretic framework. arXiv preprint arXiv:2404.10122.

\[8\]: Thune, Tobias Sommer, Nicolò Cesa-Bianchi, and Yevgeny Seldin. "Nonstochastic multiarmed bandits with unrestricted delays." Advances in Neural Information Processing Systems 32 (2019).

\[9\]: Wu, Han, and Stefan Wager. "Thompson sampling with unrestricted delays." Proceedings of the 23rd ACM Conference on Economics and Computation. 2022.

\[10\]: Jin, Tiancheng, et al. "Near-optimal regret for adversarial mdp with delayed bandit feedback." Advances in Neural Information Processing Systems 35 (2022): 33469-33481.

\[11\]: Masoudian, S., Zimmert, J., & Seldin, Y. A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays. In ICML 2024 Workshop: Foundations of Reinforcement Learning and Control

\[12\]: Zimmert, J., & Seldin, Y. (2020, June). An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics (pp. 3285-3294). PMLR.

\[13\]: Agarwal, Alekh, et al. "Contextual bandit learning with predictable rewards." Artificial Intelligence and Statistics. PMLR, (2012).

\[14\]: Du, Simon, et al. "Bilinear classes: A structural framework for provable generalization in rl." International Conference on Machine Learning. PMLR, (2021).

\[15\]:  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. 

\[16\]: Hao, B., Lattimore, T., & Szepesvari, C. Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics (pp. 3536-3545). PMLR. (2020)