Best Arm Identification in Batched Multi-armed Bandit Problems

Shengyu Cao, Simai He, Ruoqing Jiang, Jin Xu, Hongsong Yuan
12/21/2023
stat.MLcs.LGstat.ME

No confident code implementation found for this paper.

Abstract

Recently multi-armed bandit problem arises in many real-life scenarios where arms must be sampled in batches, due to limited time the agent can wait for the feedback. Such applications include biological experimentation and online marketing. The problem is further complicated when the number of arms is large and the number of batches is small. We consider pure exploration in a batched multi-armed bandit problem. We introduce a general linear programming framework that can incorporate objectives of different theoretical settings in best arm identification. The linear program leads to a two-stage algorithm that can achieve good theoretical properties. We demonstrate by numerical studies that the algorithm also has good performance compared to certain UCB-type or Thompson sampling methods.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

On Universally Optimal Algorithms for A/B Testing

86% match2023

Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

86% match2023

Best Arm Identification in Bandits with Limited Precision Sampling

86% match2023

Optimal Multi-Objective Best Arm Identification with Fixed Confidence

85% match2025

SPRT-based Efficient Best Arm Identification in Stochastic Bandits

85% match2022

Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids

85% match2025

Cite this paper

@article{cao2023best,
  title  = {Best Arm Identification in Batched Multi-armed Bandit Problems},
  author = {Shengyu Cao and Simai He and Ruoqing Jiang and Jin Xu and Hongsong Yuan},
  year   = {2023},
  eprint = {2312.13875},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2312.13875v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2312.13875.svg)](https://codeofpaper.com/paper/2312.13875)

Discussion