Data-Driven Decision Processes - Whiteboard Talk
Thomas Kesselheim (University of Bonn)
2nd Floor Collaboration Space
Title: Online and Bandit Algorithms for \ell_p Norms and Beyond
Abstract: This talk will focus on two seemingly very different sequential decision making problems, namely Online (Generalized) Load Balancing and Bandits with Knapsacks. We will see that for both of them simple algorithms obtain optimal guarantees against probability distributions and against an adversary. In the basic version, these algorithms rely on the softmax function, a smooth approximation of the maximum. We will then see that they easily generalize to \ell_p norms and even beyond. After the talk, we could discuss if these techniques also apply in (generalizations of) your favorite problem.Based on joint work with Sahil Singla [COLT 2020] and Marco Molinaro and Sahil Singla [SODA 2023]