Timezone: »

 
Poster
Equipping Experts/Bandits with Long-term Memory
Kai Zheng · Haipeng Luo · Ilias Diakonikolas · Liwei Wang

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #51
in Algorithms -- Online Learning »
We propose the first black-box approach to obtaining long-term memory guarantees for online learning in the sense of Bousquet and Warmuth, 2002, by reducing the problem to achieving typical switching regret. Specifically, for the classical expert problem with $K$ actions and $T$ rounds, using our general framework we develop various algorithms with a regret bound of order $\order(\sqrt{T(S\ln T + n \ln K)})$ compared to any sequence of experts with $S-1$ switches among $n \leq \min\{S, K\}$ distinct experts. In addition, by plugging specific adaptive algorithms into our framework we also achieve the best of both stochastic and adversarial environments simultaneously, which resolves an open problem of Warmuth and Koolen 2014. Furthermore, we extend our results to the sparse multi-armed bandit setting and show both negative and positive results for long-term memory guarantees. As a side result, our lower bound also implies that sparse losses do not help improve the worst-case regret for contextual bandit, a sharp contrast with the non-contextual case.
Keywords: Bandit Algorithms · Online Learning · Algorithms
[ Paper]  [ Poster] 

Author Information

Kai Zheng (Peking University)
Haipeng Luo (University of Southern California)
Ilias Diakonikolas (UW Madison)
Liwei Wang (Peking University)

More from the Same Authors