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 -