TY - GEN
T1 - Online prediction problems with variation
AU - Lee, Chia Jung
AU - Tsai, Shi-Chun
AU - Yang, Ming Chuan
PY - 2014/1/1
Y1 - 2014/1/1
N2 - 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 ∞-variation. Consider the loss functions with small L ∞-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∞-variation.
AB - 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 ∞-variation. Consider the loss functions with small L ∞-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∞-variation.
KW - bandit setting
KW - combinational prediction game
KW - prediction with expert advice problem
KW - semi-bandit setting
KW - variation
UR - http://www.scopus.com/inward/record.url?scp=84904753285&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-08783-2_5
DO - 10.1007/978-3-319-08783-2_5
M3 - Conference contribution
AN - SCOPUS:84904753285
SN - 9783319087825
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 49
EP - 60
BT - Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PB - Springer Verlag
T2 - 20th International Computing and Combinatorics Conference, COCOON 2014
Y2 - 4 August 2014 through 6 August 2014
ER -