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

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 ϵ-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 ϵ-robustness cannot be achieved for a consistent (i.e., uniformly sub-polynomial regret) algorithm, however small the nonzero ϵ 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.

the delayed, anonymous, and non-aggregated feedback, where we observe each delayed anonymous reward separately. 4 The total variation distance dTV(ν, υ) is defined as 1 2 ∥ν -υ∥1 = sup E∈Σ |ν(E) -υ(E)|, where Σ stands for the measurable sets on which two distributions ν and υ are defined.

5 For example, for the family of distributions with k-th moment bounded by 1 for k ≥ 2, ϵ-contamination in delay distribution, i.e., dT V D, D > ϵ, implies E [D] -E D > kϵ 1-1/k (See Assumption 4.2 for more).