# Thompson Sampling for Complex Bandit Problems

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2013.

## Built on by (most cited first, 30 of 43)

- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Thompson Sampling with a Mixture Prior](https://mlsanity.com/paper/2106.05608/) (2021)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [A Payload Optimization Method for Federated Recommender Systems](https://mlsanity.com/paper/2107.13078/) (2021)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Shattering the Agent-Environment Interface for Fine-Tuning Inclusive Language Models](https://mlsanity.com/paper/2305.11455/) (2023)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [Thompson Sampling with Unrestricted Delays](https://mlsanity.com/paper/2202.12431/) (2022)
- [Multi-Armed Bandits with Self-Information Rewards](https://mlsanity.com/paper/2209.02211/) (2022)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [On the Suboptimality of Thompson Sampling in High Dimensions](https://mlsanity.com/paper/2102.05502/) (2021)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Bayesian Reinforcement Learning with Limited Cognitive Load](https://mlsanity.com/paper/2305.03263/) (2023)
- [Thompson Sampling Itself is Differentially Private](https://mlsanity.com/paper/2407.14879/) (2024)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling](https://mlsanity.com/paper/2303.09033/) (2023)
- [Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback](https://mlsanity.com/paper/2305.16074/) (2023)
- [Preference Elicitation with Soft Attributes in Interactive Recommendation](https://mlsanity.com/paper/2311.02085/) (2023)
- [Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework](https://mlsanity.com/paper/2201.12955/) (2022)
- [Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems](https://mlsanity.com/paper/2504.07307/) (2025)
- [Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning](https://mlsanity.com/paper/2011.14266/) (2020)
- [An Efficient Algorithm for Deep Stochastic Contextual Bandits](https://mlsanity.com/paper/2104.05613/) (2021)
- [Regenerative Particle Thompson Sampling](https://mlsanity.com/paper/2203.08082/) (2022)
- [Maximum entropy exploration in contextual bandits with neural networks and energy based models](https://mlsanity.com/paper/2210.06302/) (2022)
- [Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox](https://mlsanity.com/paper/2410.05441/) (2024)
- [Thompson Sampling for Unimodal Bandits](https://mlsanity.com/paper/2106.08187/) (2021)
- [Online Bayesian Meta-Learning for Cognitive Tracking Radar](https://mlsanity.com/paper/2207.06917/) (2022)

## Abstract (arXiv)

We consider stochastic multi-armed bandit problems with complex actions over a set of basic arms, where the decision maker plays a complex action rather than a basic arm in each round. The reward of the complex action is some function of the basic arms' rewards, and the feedback observed may not necessarily be the reward per-arm. For instance, when the complex actions are subsets of the arms, we may only observe the maximum reward over the chosen subset. Thus, feedback across complex actions may be coupled due to the nature of the reward function. We prove a frequentist regret bound for Thompson sampling in a very general setting involving parameter, action and observation spaces and a likelihood function over them. The bound holds for discretely-supported priors over the parameter space and without additional structural properties such as closed-form posteriors, conjugate prior structure or independence across arms. The regret bound scales logarithmically with time but, more importantly, with an improved constant that non-trivially captures the coupling across complex actions due to the structure of the rewards. As applications, we derive improved regret bounds for classes of complex bandit problems involving selecting subsets of arms, including the first nontrivial regret bounds for nonlinear MAX reward feedback from subsets.