Minimizing wide range regret with time selection functions

Subhash Khot, Ashok Kumar Ponnuswami

Research output: Contribution to conferencePaperpeer-review

Abstract

We consider the problem of minimizing regret with respect to a given set S of pairs of time selection functions and modifications rules. We give an online algorithm that has O(√ T log |S|) regret with respect to S when the algorithm is run for T time steps and there are N actions allowed. This improves the upper bound of O(√ TNlog(|I||F|)) given by Blum and Mansour [BM07a] for the case when S = I × for a set I of time selection functions and a set F of modification rules. We do so by giving a simple reduction that uses an online algorithm for external regret as a black box.

Original languageEnglish (US)
Pages81-86
Number of pages6
StatePublished - 2008
Event21st Annual Conference on Learning Theory, COLT 2008 - Helsinki, Finland
Duration: Jul 9 2008Jul 12 2008

Other

Other21st Annual Conference on Learning Theory, COLT 2008
Country/TerritoryFinland
CityHelsinki
Period7/9/087/12/08

ASJC Scopus subject areas

  • Education

Fingerprint

Dive into the research topics of 'Minimizing wide range regret with time selection functions'. Together they form a unique fingerprint.

Cite this