非参数随机情境臂机

Jan, 2018

Nonparametric Stochastic Contextual Bandits

Melody Y. Guan, Heinrich Jiang

TL;DR探讨K-armed bandit问题下的noisy reward，提出了一种简单实用的算法（kNN-UCB），并得到了紧密的top-arm identification和sublinear regret边界，并讨论了该算法的全局intrisinic dimension和ambient dimension的regret边界，同时介绍了对于无限武装情境下bandit算法的扩展和实验证明了算法在多种任务上的优越性。

Abstract

We analyze the $K$-armed bandit problem where the reward for each arm is a noisy realization based on an observed context under mild nonparametric assumptions. We attain tight results for top-arm identification and a sublinear regret of $\widetilde{O}\Big(T^{\frac{1+D}{2+D}}\Big)$, whe