# Doubly robust Thompson sampling for linear payoffs

arXiv: https://arxiv.org/abs/2102.01229 · HTML: https://mlsanity.com/paper/2102.01229/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 1 Feb 2021.

## Builds on (most cited first, 6 of 6)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Balanced Linear Contextual Bandits](https://mlsanity.com/paper/1812.06227/) (2018)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)

## Built on by (most cited first, 21 of 21)

- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits](https://mlsanity.com/paper/2206.05404/) (2022)
- [Learning the Pareto Front Using Bootstrapped Observation Samples](https://mlsanity.com/paper/2306.00096/) (2023)
- [RoME: A Robust Mixed-Effects Bandit Algorithm for Optimizing Mobile Health Interventions](https://mlsanity.com/paper/2312.06403/) (2023)
- [Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap](https://mlsanity.com/paper/2201.04469/) (2022)
- [Linear Bandits with Partially Observable Features](https://mlsanity.com/paper/2502.06142/) (2025)
- [Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization](https://mlsanity.com/paper/2605.10405/) (2026)
- [Best Arm Identification with Contextual Information under a Small Gap](https://mlsanity.com/paper/2209.07330/) (2022)
- [Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds](https://mlsanity.com/paper/2302.02988/) (2023)
- [A Doubly Robust Approach to Sparse Reinforcement Learning](https://mlsanity.com/paper/2310.15286/) (2023)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13791/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Risk-aware linear bandits with convex loss](https://mlsanity.com/paper/2209.07154/) (2022)
- [Experimental Design for Semiparametric Bandits](https://mlsanity.com/paper/2506.13390/) (2025)
- [Adaptive Data Augmentation for Thompson Sampling](https://mlsanity.com/paper/2506.14479/) (2025)
- [Adaptive Exploration for Latent-State Bandits](https://mlsanity.com/paper/2602.05139/) (2026)
- [Set Membership Estimation for Stochastic Linear Contextual Bandits](https://mlsanity.com/paper/2606.20022/) (2026)
- [Dominant Arm Identification with Mixing and Recycling Observed Samples](https://mlsanity.com/paper/2608.01545/) (2026)

## Abstract (arXiv)

A challenging aspect of the bandit problem is that a stochastic reward is observed only for the chosen arm and the rewards of other arms remain missing. The dependence of the arm choice on the past context and reward pairs compounds the complexity of regret analysis. We propose a novel multi-armed contextual bandit algorithm called Doubly Robust (DR) Thompson Sampling employing the doubly-robust estimator used in missing data literature to Thompson Sampling with contexts (textttLinTS). Different from previous works relying on missing data techniques (citetdimakopoulou2019balanced, citetkim2019doubly), the proposed algorithm is designed to allow a novel additive regret decomposition leading to an improved regret bound with the order of tildeO(φ-2√T), where φ2 is the minimum eigenvalue of the covariance matrix of contexts. This is the first regret bound of textttLinTS using φ2 without the dimension of the context, d. Applying the relationship between φ2 and d, the regret bound of the proposed algorithm is tildeO(d√T) in many practical scenarios, improving the bound of textttLinTS by a factor of √d. A benefit of the proposed method is that it utilizes all the context data, chosen or not chosen, thus allowing to circumvent the technical definition of unsaturated arms used in theoretical analysis of textttLinTS. Empirical studies show the advantage of the proposed algorithm over textttLinTS.