Online prediction problems with variation

Chia Jung Lee*, Shi-Chun Tsai, Ming Chuan Yang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


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.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319087825
StatePublished - 1 Jan 2014
Event20th International Computing and Combinatorics Conference, COCOON 2014 - Atlanta, GA, United States
Duration: 4 Aug 20146 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8591 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Computing and Combinatorics Conference, COCOON 2014
CountryUnited States
CityAtlanta, GA


  • bandit setting
  • combinational prediction game
  • prediction with expert advice problem
  • semi-bandit setting
  • variation

Fingerprint Dive into the research topics of 'Online prediction problems with variation'. Together they form a unique fingerprint.

Cite this