標題: | Online Prediction Problems with Variation |
作者: | Lee, Chia-Jung Tsai, Shi-Chun Yang, Ming-Chuan 資訊工程學系 Department of Computer Science |
公開日期: | 1-一月-2014 |
摘要: | We study the prediction with expert advice problem, where in each round, the player selects one of N actions and incurs the corresponding loss according to an N-dimensional linear loss vector, and aim to minimize the regret. In this paper, we consider a new measure of the loss functions, which we call L-infinity-variation. Consider the loss functions with small L-infinity-variation, if the player is allowed to have some information related to the variation in each round, we can obtain an online bandit algorithm for the problem without using the self-concordance methodology, which conditionally answers an open problem in [8]. Another related problem is the combinatorial prediction game, in which the set of actions is a subset of {0, 1}(d), and the loss function is in [-1, 1](d). We provide an online algorithm in the semi-bandit setting when the loss functions have small L-infinity-variation. |
URI: | http://hdl.handle.net/11536/25276 |
ISBN: | 978-3-319-08783-2; 978-3-319-08782-5 |
ISSN: | 0302-9743 |
期刊: | COMPUTING AND COMBINATORICS, COCOON 2014 |
Volume: | 8591 |
Issue: | |
起始頁: | 49 |
結束頁: | 60 |
顯示於類別: | 會議論文 |