固定预算与固定置信度的最优采样复杂度相差仅对数因子。
Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors
- 提出新元算法FC2FB，可将任意固定置信算法转为固定预算算法。
- 转换后算法的采样复杂度与原算法相差不超过对数因子。
- 适用于追求高效采样的结构化最优臂识别问题研究者。
最优臂识别（BAI）是交互式机器学习中最基础的问题之一，有两种范式：固定预算（FB）和固定置信（FC）。对于具有唯一最优臂的K臂老虎机，两种设置下的最优采样复杂度已确定，且彼此相差仅对数因子。这引出一个关键问题：在一般、可能具结构的BAI问题中，FB是否比FC更难？本文证明，FB并不比FC更难，至多相差对数因子。我们通过构造性方法提出新算法FC2FB（固定置信转固定预算），该元算法接收一个FC算法$\mathcal{A}$，将其转化为一个FB算法。我们证明，FC2FB的采样复杂度与$\mathcal{A}$的采样复杂度在对数因子内一致。这意味着最优FC采样复杂度是最优FB采样复杂度的上界，至多差一个对数因子。该结果揭示了两类设置间的根本关系，并具有重要应用价值：将FC2FB与现有先进FC算法结合，可提升多个FB问题的采样效率。
原文摘要 · Abstract (English)
The best-arm identification (BAI) problem is one of the most fundamental problems in interactive machine learning, which has two flavors: the fixed-budget setting (FB) and the fixed-confidence setting (FC). For $K$-armed bandits with a unique best arm, the optimal sample complexities for both settings have been settled down, and they match up to logarithmic factors. This prompts an interesting research question about the generic, potentially structured BAI problems: is FB harder than FC or the other way around? In this paper, we show that FB is no harder than FC up to logarithmic factors. We do this constructively: we propose a novel algorithm called FC2FB (fixed confidence to fixed budget), which is a meta algorithm that takes in an FC algorithm $\mathcal{A}$ and turn it into an FB algorithm. We prove that FC2FB enjoys a sample complexity that matches, up to logarithmic factors, that of the sample complexity of $\mathcal{A}$. This means that the optimal FC sample complexity is an upper bound of the optimal FB sample complexity up to logarithmic factors. Our result not only reveals a fundamental relationship between FB and FC, but also has a significant implication: FC2FB combined with existing state-of-the-art FC algorithms leads to improved sample complexity for a number of FB problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。