期刊
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
卷 61, 期 3, 页码 203-230出版社
SPRINGER
DOI: 10.1007/s10472-011-9258-6
关键词
Computational learning theory; Multi-armed bandits; Contextual bandits; UCB; PUCB; Computer Go
A multi-armed bandit episode consists of n trials, each allowing selection of one of K arms, resulting in payoff from a distribution over [0,1] associated with that arm. We assume contextual side information is available at the start of the episode. This context enables an arm predictor to identify possible favorable arms, but predictions may be imperfect so that they need to be combined with further exploration during the episode. Our setting is an alternative to classical multi-armed bandits which provide no contextual side information, and is also an alternative to contextual bandits which provide new context each individual trial. Multi-armed bandits with episode context can arise naturally, for example in computer Go where context is used to bias move decisions made by a multi-armed bandit algorithm. The UCB1 algorithm for multi-armed bandits achieves worst-case regret bounded by O(root Knlog(n). We seek to improve this using episode context, particularly in the case where K is large. Using a predictor that places weight M (i) > 0 on arm i with weights summing to 1, we present the PUCB algorithm which achieves regret O (1/M, root n log(n) where M (auaEuro parts per thousand) is the weight on the optimal arm. We illustrate the behavior of PUCB with small simulation experiments, present extensions that provide additional capabilities for PUCB, and describe methods for obtaining suitable predictors for use with PUCB.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据