arXiv:2412.17753stat.MLcs.LG2024-12

证明了奈曼分配在两臂最优臂识别中最小化简单后悔,达到理论极限。

Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification

  • 采用奈曼分配进行自适应实验,按结果标准差比例分配样本。
  • 在最坏情况下,奈曼分配的简单后悔率与理论下界完全匹配。
  • 无需分布局部假设,适用于高斯和伯努利等广泛分布场景。

本文研究两臂固定预算最优臂识别问题中的渐近极小极大最优算法。给定两个处理臂,目标是通过自适应实验识别期望结果最高的臂。聚焦于奈曼分配(按结果标准差比例分配样本),证明其在简单后悔(真实最优臂与估计最优臂期望结果之差)上达到极小极大最优。首先推导出在位置平移分布(包括高斯分布)下的简单后悔极小极大下界;随后证明奈曼分配的简单后悔在最坏分布下渐近匹配该下界,包括常数项,不仅匹配速率。特别地,该最优性结果不依赖分布的局部假设(如局部渐近正态性)。此外,当分布为伯努利时,奈曼分配退化为均匀分配,即标准随机对照试验。

原文摘要 · Abstract (English)

This study investigates an asymptotically minimax optimal algorithm in the two-armed fixed-budget best-arm identification (BAI) problem. Given two treatment arms, the objective is to identify the arm with the highest expected outcome through an adaptive experiment. We focus on the Neyman allocation, where treatment arms are allocated following the ratio of their outcome standard deviations. Our primary contribution is to prove the minimax optimality of the Neyman allocation for the simple regret, defined as the difference between the expected outcomes of the true best arm and the estimated best arm. Specifically, we first derive a minimax lower bound for the expected simple regret, which characterizes the worst-case performance achievable under the location-shift distributions, including Gaussian distributions. We then show that the simple regret of the Neyman allocation asymptotically matches this lower bound, including the constant term, not just the rate in terms of the sample size, under the worst-case distribution. Notably, our optimality result holds without imposing locality restrictions on the distribution, such as the local asymptotic normality. Furthermore, we demonstrate that the Neyman allocation reduces to the uniform allocation, i.e., the standard randomized controlled trial, under Bernoulli distributions.

最优臂识别奈曼分配统计优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。