Abstract: Classical online learning algorithms make a static assumption on the nature of the data generating process (either stochastic or adversarial) and the nature of the offline benchmark to measure performance. Neither of these assumptions are well-justified in practice. While assuming a probability model on the data could lead to suboptimal performance in practice, worst-case adversarially robust algorithms may be unnecessarily pessimistic. More subtly, since our objective in online learning is to maximize reward rather than regret, the choice of offline benchmark (i.e. model) matters as much as the choice of online algorithm.  

 This talk will describe two research vignettes in full-information and bandit learning. The first research vignette will motivate and describe the design of online learning algorithms in the “tree-expert” setting that are computationally efficient and adapt both to underlying stochasticity and the minimal model complexity. These algorithms achieve reward that is almost as good as an “oracle” algorithm that has access to all of this information beforehand. The second research vignette will describe approaches to data-adaptive model selection in the more challenging limited-information feedback paradigm, which includes contextual bandits and reinforcement learning. I will conclude with a discussion of open problems involving computational efficiency and non-adversarial strategic behavior, and, time permitting, mention some initial work in these directions.  

Bio: Vidya Muthukumar is an Assistant Professor in the Schools of Electrical and Computer Engineering and Industrial and Systems Engineering at Georgia Institute of Technology. Her broad interests are in game theory, online and statistical learning. She is particularly interested in designing learning algorithms that provably adapt in strategic environments, fundamental properties of overparameterized models, and algorithmic foundations of multi-agent reinforcement learning.  

Vidya received the PhD degree in Electrical Engineering and Computer Sciences from the University of California, Berkeley. She is the recipient of the Adobe Data Science Research Award, a Simons-Berkeley-Google Research Fellowship (for the Fall 2020 program on “Theory of Reinforcement Learning”), IBM Science for Social Good Fellowship and a Georgia Tech Class of 1969 Teaching Fellowship for the academic year 2021-2022.