揭示自适应采样在线性多臂问题中可实现多项式加速
On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits
- 提出非自适应固定设计方法，样本复杂度达下界
- 发现自适应采样在多个自然动作集上可实现多项式级提升
- 构建首个使自适应获多项式优势的动作集构造
研究线性多臂问题中ε-最优臂识别的最小最大样本复杂度。给定一个张成ℝ^d的紧凑动作集𝒳和未知收益向量θ∈ℝ^d，目标是输出一个臂𝑥̂∈𝒳，使得⟨𝑥̂,θ⟩≥max_{x∈𝒳}⟨x,θ⟩−ε，且置信度不低于1−δ，同时尽可能减少采样次数。首先，提出一种非自适应固定设计方法，其样本复杂度为𝒪((d log(1/δ))/ε² + w(𝒳)²/ε²)，其中w(𝒳)是依赖于𝒳的高斯宽度项，并证明所有非自适应固定设计方法的下界均为Ω((d log(1/δ))/ε² + w(𝒳)²/ε²)。随后转向自适应采样，提出关键结构性问题：除了标准基外，是否存在结构化动作集使得自适应仅带来对数因子改进？答案是肯定的，适用于超立方体、ℓ₂球、m-集及多任务多臂问题。最后，首次构造出一个动作集𝒳，使得自适应相比所有非自适应算法均能实现多项式级改进。该分离的关键在于一个ℓ₂范数估计子程序：设计了一种自适应算法，仅需从ℝ^d单位ℓ₂球采样𝒪((d log(1/δ))/ε²)次，即可以至少1−δ的概率输出估计值𝑟̂，满足|𝑟̂−‖θ‖₂|≤ε。
原文摘要 · Abstract (English)
We study the minimax sample complexity of $\varepsilon$-best arm identification in linear bandits. Given a compact action set $\mathcal{X}$ that spans $\mathbb{R}^d$ and an unknown reward vector $θ\in\mathbb{R}^d$, the goal is to output an arm $\widehat{x}\in\mathcal{X}$ such that $\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon$ with probability at least $1-δ$, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity $\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$, where $w(\mathcal{X})$ is a Gaussian width term dependent on $\mathcal{X}$, and we prove a matching lower bound $Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$ for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the $\ell_2$ ball, $m$-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set $\mathcal{X}$ for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an $\ell_2$-norm estimation subroutine: we design an adaptive algorithm that uses $\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right)$ samples from the unit $\ell_2$ ball in $\mathbb{R}^d$ and outputs an estimate $\widehat r$ satisfying $|\widehat r-\|θ\|_2|\le \varepsilon$ with probability at least $1-δ$, where $θ$ is the unknown reward vector.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。