图 书 馆
具有相似信息的语境错误Contextual Bandits with Similarity Information |
|
| 课程网址: | http://videolectures.net/colt2011_slivkins_bandits/ |
| 主讲教师: | Aleksandrs Slivkins |
| 开课单位: | 微软公司 |
| 开课时间: | 2011-08-02 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence of choices. In each round it chooses from a time-invariant set of alternatives and receives the payoff associated with this alternative. While the case of small strategy sets is by now well-understood, a lot of recent work has focused on MAB problems with exponentially or infinitely large strategy sets, where one needs to assume extra structure in order to make the problem tractable. In particular, recent literature considered information on similarity between arms. We consider similarity information in the setting of contextual bandits, a natural extension of the basic MAB problem where before each round an algorithm is given the context – a hint about the payoffs in this round. Contextual bandits are directly motivated by placing advertisements on webpages, one of the crucial problems in sponsored search. A particularly simple way to represent similarity information in the contextual bandit setting is via a similarity distance between the context-arm pairs which bounds from above the difference between the respective expected payoffs. Prior work on contextual bandits with similarity uses “uniform” partitions of the similarity space, so that each context-arm pair is approximated by the closest pair in the partition. Algorithms based on “uniform” partitions disregard the structure of the payoffs and the context arrivals, which is potentially wasteful. We present algorithms that are based on adaptive partitions, and take advantage of ”benign” payoffs and context arrivals without sacrificing the worst-case performance. The central idea is to maintain a finer partition in high-payoff regions of the similarity space and in popular regions of the context space. Our results apply to several other settings, e.g. MAB with constrained temporal change (Slivkins and Upfal, 2008) and sleeping bandits (Kleinberg et al., 2008a). |
| 关 键 词: | 相似信息; 数学问题; 数学分析; 策略算法 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-04-28：chenxin |
| 阅读次数: | 41 |