# Stochastically Constrained Best Arm Identification with Thompson Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 27 references that are in the map.
- First posted on arXiv 7 Jan 2025.

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

- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms](https://mlsanity.com/paper/2211.14722/) (2022)
- [Improving the Knowledge Gradient Algorithm](https://mlsanity.com/paper/2310.17901/) (2023)

## Abstract (arXiv)

We consider the problem of the best arm identification in the presence of stochastic constraints, where there is a finite number of arms associated with multiple performance measures. The goal is to identify the arm that optimizes the objective measure subject to constraints on the remaining measures. We will explore the popular idea of Thompson sampling (TS) as a means to solve it. To the best of our knowledge, it is the first attempt to extend TS to this problem. We will design a TS-based sampling algorithm, establish its asymptotic optimality in the rate of posterior convergence, and demonstrate its superior performance using numerical examples.