图 书 馆
匪徒问题，查询学习，和haystack维度Bandits, Query Learning, and the Haystack Dimension |
|
| 课程网址: | http://videolectures.net/colt2011_amin_bandits/ |
| 主讲教师: | Kareem Amin |
| 开课单位: | 宾夕法尼亚大学 |
| 开课时间: | 2011-08-02 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Motivated by multi-armed bandits (MAB) problems with a very large or even in finite number of arms, we consider the problem of finding a maximum of an unknown target function by querying the function at chosen inputs (or arms). We give an analysis of the query complexity of this problem, under the assumption that the payoff of each arm is given by a function belonging to a known, finite, but otherwise arbitrary function class. Our analysis centers on a new notion of function class complexity that we call the haystack dimension, which is used to prove the approximate optimality of a simple greedy algorithm. This algorithm is then used as a subroutine in a functional MAB algorithm, yielding provably near-optimal regret. We provide a generalization to the infinite cardinality setting, and comment on how our analysis is connected to, and improves upon, existing results for query learning and generalized binary search. |
| 关 键 词: | 函数; 简单贪婪算法; 查询学习 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-03-05：lxf |
| 阅读次数: | 66 |