Events
Spring 2022

# Learning & Games Visitor Speaker Series: Offline-to-Online Transformation via Blackwell Approachability

Thursday, Mar. 3, 2022 2:00 pm3:00 pm PST

Abstract: Black-box reduction from offline optimization to online algorithms has been the topic of study of numerous works (Kalai and Vempala (2005); Dudík et al. (2017); Kakade et al. (2009); Hazan and Koren (2016)). In this work, we consider designing online algorithms for problems with greedy approximation algorithms which are robust to local errors. Our first result is a reduction which gives a $O(\sqrt{T})$-regret algorithm for the full information setting via Blackwell Approachability. Next, we introduce Bandit Blackwell Sequential Games which is a bandit version of Blackwell Approachability, and leverage this to get a reduction which gives a $O(T^{2/3})$-regret algorithm in the bandit setting. We further show several applications of these reductions to problems including submodular maximization, reserve pricing in auctions, and assortment optimization.