论文标题
通过多军匪徒评估近似功能
Approximate Function Evaluation via Multi-Armed Bandits
论文作者
论文摘要
我们研究了在未知点$ \boldsymbolμ\ in \ mathbb {r}^n $中估算已知平滑函数$ f $的价值的问题，其中每个组件$μ_i$都可以通过嘈杂的甲骨文进行采样。对应于具有较大定向衍生物的函数方向的$ \boldsymbolμ$的更频繁的成分更有效。但是，由于$ \boldsymbolμ$尚不清楚，因此最佳抽样频率也未知。我们设计了一种实例自适应算法，该算法学会根据每个坐标的重要性进行采样，并且概率至少$ 1-δ$返回$ε$准确估计为$ f（\boldsymbolμ）$。我们将算法推广以适应异性噪声，并在$ f $是线性时证明渐近最佳性。我们通过数值实验证实了我们的理论结果，表明适应性带来了巨大的收益。
We study the problem of estimating the value of a known smooth function $f$ at an unknown point $\boldsymbolμ \in \mathbb{R}^n$, where each component $μ_i$ can be sampled via a noisy oracle. Sampling more frequently components of $\boldsymbolμ$ corresponding to directions of the function with larger directional derivatives is more sample-efficient. However, as $\boldsymbolμ$ is unknown, the optimal sampling frequencies are also unknown. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-δ$ returns an $ε$ accurate estimate of $f(\boldsymbolμ)$. We generalize our algorithm to adapt to heteroskedastic noise, and prove asymptotic optimality when $f$ is linear. We corroborate our theoretical results with numerical experiments, showing the dramatic gains afforded by adaptivity.
