A number of MAB papers establish theoretical bounds on regret when observations are subject to delay. See for instance [1]}, [2]}, [3]} and references therein. As noted in the introduction, information delays arise organically in our model as a consequence of particular nonstationary context sequence. In dealing with this, we developed analysis techniques that also apply when there reward observations are subject to delay. In particular, Proposition REF  shows formally that robust results for DTS are possible even when reward signals are observed only after some delay of arbitrary length. Since at least [4]}, it has been recognized informally that Thompson sampling has some resilience to delayed feedback since it is a randomized algorithm. To our knowledge, the most closely related theoretical result to ours is one of [5]} on parallelized Thomspon sampling. They provide a bound on Bayesian simple regret that degrades if there is a very high degree of paralellization. By contrast, our bound allows for delay in observing rewards that is as long as the experiment itself, which is equivalent to a problem where all arm pulls must be decided in parallel at the start of the experiment. Notice that even without delayed reward observations, this magnitude of delayed learning arises implicitly in Example REF , since uncertainty does not resolve until the end of the experiment.
