Stochastically Constrained Best Arm Identification with Thompson Sampling

• URL: http://arxiv.org/abs/2501.03877v1
• Date: Tue, 07 Jan 2025 15:40:22 GMT
• Title: Stochastically Constrained Best Arm Identification with Thompson Sampling
• Authors: Le Yang, Siyang Gao, Cheng Li, Yi Wang,
• Abstract summary: We consider the problem of the best arm identification in the presence of constraints, where there is a finite number of arms associated with multiple performance measures. We will explore the popular idea of Thompson sampling (TS) as a means to solve it. We will design a TS-based sampling algorithm, establish its optimality in the rate of posterior convergence, and demonstrate its superior performance using numerical examples.
• Score: 11.728338956484091
• License:
• Abstract: 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.

Related papers

• Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits [35.35226227009685]
  Good arm identification (IGA) is a practical bandit inference objective that aims to label arms with means above a threshold as quickly as possible. We show that GA can be efficiently solved by combining a reward-maximizing sampling algorithm with a novel non-valid sequential test for labeling arm means. Our empirical results validate our approach beyond the minimax setting, reducing the expected number of samples for all stopping times by at least 50% across both synthetic and real-world settings.
  arXiv  Detail & Related papers  (2024-10-21T01:19:23Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  We study the fixed-confidence best arm identification problem in the bandit framework. We propose a novel policy that combines Thompson sampling with a computationally efficient approach known as the best challenger rule.
  arXiv  Detail & Related papers  (2023-10-01T01:37:02Z)
• Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits [81.45853204922795]
  Thompson sampling has been shown to achieve problem-dependent lower bounds in several reward models. We consider the optimality of TS for the Pareto model that has a heavy tail and is parameterized by two unknown parameters. We find that TS with the Jeffreys and reference priors can achieve the lower bound if one uses a truncation procedure.
  arXiv  Detail & Related papers  (2023-02-03T04:47:14Z)
• SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
  This paper investigates the best arm identification problem in multi-armed bandits in the fixed confidence setting. Existing algorithms for the exponential family of bandits face computational challenges. A framework is proposed that adopts the likelihood ratio-based tests known to be effective for sequential testing.
  arXiv  Detail & Related papers  (2022-07-22T15:54:53Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  We devise a simple algorithm whose sampling complexity matches known instance-specific lower bounds. Unlike existing best-arm identification strategies, our algorithm uses a stopping rule that does not depend on the number of arms.
  arXiv  Detail & Related papers  (2020-06-29T14:25:51Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  We study the best-arm identification problem in multi-armed bandits with, potentially private rewards. The goal is to identify the arm with the highest quantile at a fixed, prescribed level. We show that our algorithm is $delta$-PAC and we characterize its sample complexity.
  arXiv  Detail & Related papers  (2020-06-11T20:23:43Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.