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 language | English (US) |
---|---|
Pages | 81-86 |
Number of pages | 6 |
State | Published - 2008 |
Event | 21st Annual Conference on Learning Theory, COLT 2008 - Helsinki, Finland Duration: Jul 9 2008 → Jul 12 2008 |
Other
Other | 21st Annual Conference on Learning Theory, COLT 2008 |
---|---|
Country/Territory | Finland |
City | Helsinki |
Period | 7/9/08 → 7/12/08 |
ASJC Scopus subject areas
- Education