Covariance Adaptive Best Arm Identification

• URL: http://arxiv.org/abs/2306.02630v2
• Date: Wed, 20 Dec 2023 15:01:25 GMT
• Title: Covariance Adaptive Best Arm Identification
• Authors: El Mehdi Saad (CentraleSup\'el\'ec), Gilles Blanchard (LMO, DATASHAPE), Nicolas Verzelen (MISTEA)
• Abstract summary: The goal is to identify the arm with the highest mean reward with a probability of at least 1 -- $delta$, while minimizing the number of arm pulls. We propose a more flexible scenario where arms can be dependent and rewards can be sampled simultaneously. This framework is relevant in various applications, such as clinical trials, where similarities between patients or drugs suggest underlying correlations.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of best arm identification in the multi-armed bandit model, under fixed confidence. Given a confidence input $\delta$, the goal is to identify the arm with the highest mean reward with a probability of at least 1 -- $\delta$, while minimizing the number of arm pulls. While the literature provides solutions to this problem under the assumption of independent arms distributions, we propose a more flexible scenario where arms can be dependent and rewards can be sampled simultaneously. This framework allows the learner to estimate the covariance among the arms distributions, enabling a more efficient identification of the best arm. The relaxed setting we propose is relevant in various applications, such as clinical trials, where similarities between patients or drugs suggest underlying correlations in the outcomes. We introduce new algorithms that adapt to the unknown covariance of the arms and demonstrate through theoretical guarantees that substantial improvement can be achieved over the standard setting. Additionally, we provide new lower bounds for the relaxed setting and present numerical simulations that support their theoretical findings.

Related papers

• Best Arm Identification with Minimal Regret [55.831935724659175]
  Best arm identification problem elegantly amalgamates regret minimization and BAI. Agent's goal is to identify the best arm with a prescribed confidence level. Double KL-UCB algorithm achieves optimality as the confidence level tends to zero.
  arXiv  Detail & Related papers  (2024-09-27T16:46:02Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible. We study multi-fidelity best-arm identification, in which the can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost. Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm.
  arXiv  Detail & Related papers  (2024-06-05T08:02:40Z)
• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  We introduce the constrained best mixed arm identification (CBMAI) problem with a fixed budget. The goal is to find the best mixed arm that maximizes the expected reward subject to constraints on the expected costs with a given learning budget $N$. We provide a theoretical upper bound on the mis-identification (of the the support of the best mixed arm) probability and show that it decays exponentially in the budget $N$.
  arXiv  Detail & Related papers  (2024-05-23T22:35:11Z)
• 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)
• Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget [10.470114319701576]
  This study investigates the experimental design problem for identifying the arm with the highest expected outcome. Under the assumption that the variances are known, we propose the Generalized-Neyman-Allocation (GNA)-empirical-best-arm (EBA) strategy. We show that the GNA-EBA strategy is infinitelyally optimal in sense that its probability of misidentification aligns with the lower bounds.
  arXiv  Detail & Related papers  (2023-10-30T17:52:46Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite state space. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds.
  arXiv  Detail & Related papers  (2023-10-20T10:04:05Z)
• Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits [40.71199236098642]
  In the infinite-armed bandit problem, each arm's average reward is sampled from an unknown distribution. We consider a general class of distribution functionals beyond the maximum, and propose unified meta algorithms for both the offline and online settings.
  arXiv  Detail & Related papers  (2022-11-01T18:20:10Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  We study the problem of identifying the best arm in a multi-armed bandit environment. A decision entity wishes to find the index of the best arm as quickly as possible, subject to an upper bound error probability. We show that this policy achieves an upper bound that depends on $R$ and is monotonically non-increasing as $Rtoinfty$.
  arXiv  Detail & Related papers  (2022-03-29T04:58:04Z)
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification [19.777265059976337]
  Fed-SEL is a simple communication-efficient algorithm that builds on successive elimination techniques and involves local sampling steps at the clients. We show that for certain heterogeneous problem instances, Fed-SEL outputs the best-arm after just one round of communication. As our final contribution, we develop variants of Fed-SEL, both for federated and peer-to-peer settings, that are robust to the presence of Byzantine clients.
  arXiv  Detail & Related papers  (2021-09-13T04:22:21Z)
• Quantile Bandits for Best Arms Identification [10.294977861990203]
  We consider a variant of the best arm identification task in multi-armed bandits. Motivated by risk-averse decision-making problems, our goal is to identify a set of $m$ arms with the highest $tau$-quantile values within a fixed budget.
  arXiv  Detail & Related papers  (2020-10-22T09:58:54Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)

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.