Second, in Section  we propose deconfounded Thompson sampling (DTS), a simple and flexible approach that can address such problems. Thompson sampling (TS) is one of the leading approaches to efficient exploration in both academia and industry. See [1]}, [2]}, [3]} for background. DTS makes two critical modifications to TS as it would usually be applied in a contextual bandit problem. The first modification makes the algorithm suitable for learning about a decision which will be implemented across many future contexts. In the setting of Example REF , rather than sample an arm according to the posterior probability it is the best action for the current day — as would standard TS — DTS samples an arm according to the posterior probability it offers the best average performance throughout the week. The second modification makes the algorithm focus on post-experiment performance rather than solely on the reward generating during the experiment itself. For this, we adopt the top-two sampling strategy of [4]}. This modification explores suboptimal arms more aggressively by running Thompson sampling until two distinct actions are drawn and then randomly picking among those “top-two”.
Third, in Section  we prove that DTS offers robust performance even in settings with severe risk of delay and confounding. We study what [5]} call the utilitarian regret, by evaluating its expected value conditioned on an arbitrary sequence of contexts. We provide a finite-time bound that depends only on the information contained in the contexts and is completely independent of the order in which they arrive, demonstrating robustness to nonstationary confounders that are modeled by the algorithm. As discussed above, any algorithm must grapple with delayed information revelation due to the context sequence. This result also allows for an arbitrary delay in observing reward realizations. The analysis in this section seems to offer substantial innovation. Past proofs have analyzed TS as method that implicitly behaves optimistically in the face of uncertainty [6]}, [7]}, but natural optimistic algorithms fail to address Example REF  so an alternative theory is required. Our proofs use inverse propensity weights implicitly in the analysis of the posterior distribution, highlighting the importance of randomization and offering an interesting connection to the causal inference literature.
