图 书 馆
多武装土匪问题中方差估计的应用Use of variance estimation in the multi-armed bandit problem |
|
| 课程网址: | http://videolectures.net/otee06_audibert_uvema/ |
| 主讲教师: | Jean Yves Audibert |
| 开课单位: | 国立巴黎高等矿业学院 |
| 开课时间: | 2007-02-25 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | An important aspect of most decision making problems concerns the appropriate balance between exploitation (acting optimally according to the partial knowledge acquired so far) and exploration of the environment (acting sub-optimally in order to refine the current knowledge and improve future decisions). A typical example of this so-called exploration versus exploitation dilemma is the multi-armed bandit problem, for which many strategies have been developed. Here we investigate policies based the choice of the arm having the highest upper-confidence bound, where the bound takes into account the empirical variance of the different arms. Such an algorithm was found earlier to outperform its peers in a series of numerical experiments. The main contribution of this paper is the theoretical investigation of this algorithm. Our contribution here is twofold. First, we prove that with probability at least 1 − B, the regret after n plays of a variant of the UCB algorithm (called B-UCB) is upper-bounded by a constant, that scales linearly with log(1/B), but which is independent from n. We also analyse a variant which is closer to the algorithm suggested earlier. We prove a logarithmic bound on the expected regret of this algorithm and argue that the bound scales favourably with the variance of the suboptimal arms. |
| 关 键 词: | UCB算法; 决策; 算法 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-10-22：chenxin |
| 阅读次数: | 305 |