標題: 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
顯示於類別:會議論文