Multi-Armed Sequential Hypothesis Testing by Betting

• URL: http://arxiv.org/abs/2603.17925v1
• Date: Wed, 18 Mar 2026 17:01:34 GMT
• Title: Multi-Armed Sequential Hypothesis Testing by Betting
• Abstract summary: We consider the global null hypothesis $mathscrP$ and a composite alternative $mathscrQ$ where at least one arm is non-null.<n>Even if several arms are non-null, we seek $e$-processes and sequential tests whose performance are as strong as the ones that have oracle knowledge about which arm generates the most evidence against $mathscrP$.<n>A key technical device in this optimality analysis is a modified upper-confidence-bound-like algorithm for unobservable but sufficiently "estimable" rewards.
• Score: 44.29651618521598
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a variant of sequential testing by betting where, at each time step, the statistician is presented with multiple data sources (arms) and obtains data by choosing one of the arms. We consider the composite global null hypothesis $\mathscr{P}$ that all arms are null in a certain sense (e.g. all dosages of a treatment are ineffective) and we are interested in rejecting $\mathscr{P}$ in favor of a composite alternative $\mathscr{Q}$ where at least one arm is non-null (e.g. there exists an effective treatment dosage). We posit an optimality desideratum that we describe informally as follows: even if several arms are non-null, we seek $e$-processes and sequential tests whose performance are as strong as the ones that have oracle knowledge about which arm generates the most evidence against $\mathscr{P}$. Formally, we generalize notions of log-optimality and expected rejection time optimality to more than one arm, obtaining matching lower and upper bounds for both. A key technical device in this optimality analysis is a modified upper-confidence-bound-like algorithm for unobservable but sufficiently "estimable" rewards. In the design of this algorithm, we derive nonasymptotic concentration inequalities for optimal wealth growth rates in the sense of Kelly [1956]. These may be of independent interest.

Related papers

• Thompson sampling: Precise arm-pull dynamics and adaptive inference [0.7614628596146601]
  We study the precise arm-pull dynamics in another canonical class of Thompson-type algorithms.<n>We show that the arm-pull count is deterministic if and only if the arm is suboptimal or is the unique optimal arm.<n>We show that normalized arm means obey the same dichotomy, with limits for stable arms and a semi-universal, non-Gaussian limit for unstable arms.
  arXiv  Detail & Related papers  (2026-01-29T00:12:04Z)
• Constrained Best Arm Identification with Tests for Feasibility [7.968868442731488]
  Best arm identification (BAI) aims to identify the highest-performance arm among a set of $K$ arms by collecting samples from each arm.<n>We propose an efficient algorithm and upper-bound its sample complexity, showing our algorithm can naturally adapt to the problem's difficulty.<n>We empirically show that our algorithm outperforms other state-of-the-art BAI algorithms in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2025-11-12T23:20:10Z)
• Near Optimal Non-asymptotic Sample Complexity of 1-Identification [5.279257531335345]
  We study the 1-identification problem, a fundamental multi-armed bandit formulation on pure exploration.<n>The goal is to determine whether there exists an arm whose mean reward is at least a known threshold $mu_0$, or to output None if it believes such an arm does not exist.<n>We design a new algorithm, and conduct theoretical analysis from the non-asymptotic perspective.
  arXiv  Detail & Related papers  (2025-06-08T03:23:45Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection.<n>The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error.<n>We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  We study the fixed-confidence best-arm identification problem in unimodal bandits.<n>We derive two lower on the stopping time of any bounds.<n>We show that a linear dependence on the number of arms is unavoidable in the confidence-independent cost.
  arXiv  Detail & Related papers  (2024-11-04T09:05:11Z)
• 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.<n>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.<n>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)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  We propose an optimal top-2 type algorithm for the best arm identification problem.<n>We show that the proposed algorithm is optimal as $delta rightarrow 0$.
  arXiv  Detail & Related papers  (2024-03-14T06:14:07Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• 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)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  We study the top-$k$ extreme contextual bandits problem, where the total number of arms can be enormous. We first propose an algorithm for the non-extreme realizable setting, utilizing the Inverse Gap Weighting strategy. We show that our algorithm has a regret guarantee of $O(ksqrt(A-k+1)T log (|mathcalF|T))$.
  arXiv  Detail & Related papers  (2021-02-15T19:10:52Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)

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.