Seminar: Understanding the Role of Feedback in Online Learning and Sequential Decision-Making
Bo Ji
Associate Professor, Computer Science
College of Engineering Faculty Fellow
Virginia Tech
Friday, November 8, 2024
2:30 - 3:45PM
3100 Torgersen Hall
Abstract
In this talk, we will discuss the role of feedback in online learning and sequential decision-making. In the first part of the talk, we discuss the role of feedback in online learning with switching costs. While it has been shown that the minimax regret under full-information feedback (i.e., observing the losses of all actions) can be significantly improved upon under bandit feedback (i.e., observing the loss of the chosen action only), it remains largely unknown how the amount and type of feedback generally impact the regret. To this end, we consider the setting of bandit learning with extra observations. We fully characterize the minimax regret in this setting, which exhibits an interesting phase-transition phenomenon; that is, the extra observations do not help improve the minimax regret unless the amount is large enough. To design algorithms that can achieve the minimax regret, it is instructive to consider a more general setting where the learner has a total observation budget. We fully characterize the minimax regret in this setting and show that the minimax regret improves smoothly as the total budget increases. Furthermore, we propose a generic algorithmic framework, which enables us to design different learning algorithms that can achieve matching upper bounds for both settings based on the amount and type of feedback. One interesting finding is that bandit feedback is no longer sufficient to achieve the minimax regret when the budget is relatively large. In the second part of the talk, we discuss a new problem called kernelized bandits with distributed, biased feedback, where users from a large population contribute to the reward of the action chosen by a central entity, but it is difficult to collect feedback from all users. Instead, only biased feedback (due to user heterogeneity) from a subset of users may be available. In addition to such partial, biased feedback, we face two practical challenges due to communication costs and computation complexity. To tackle these challenges, we carefully design a new distributed phase-then-batch-based elimination (DPBE) algorithm, which samples users in phases for collecting feedback to reduce the bias and employs maximum variance reduction to select actions in batches within each phase. We show that DPBE achieves a sublinear regret and can significantly reduce communication costs and computation complexity. Furthermore, we generalize DPBE by incorporating differential privacy to protect user feedback privacy in the distributed learning process.
Biography
Dr. Bo Ji received his B.E. and M.E. degrees in Information Science and Electronic Engineering from Zhejiang University, Hangzhou, China, in 2004 and 2006, respectively, and his Ph.D. degree in Electrical and Computer Engineering from The Ohio State University, Columbus, OH, USA, in 2012. Dr. Ji is an Associate Professor of Computer Science and a College of Engineering Faculty Fellow at Virginia Tech. Prior to joining Virginia Tech, he was an Associate Professor in the Department of Computer and Information Sciences at Temple University, where he was an Assistant Professor from July 2014 to June 2020. He was also a Senior Member of Technical Staff at AT&T Labs, San Ramon, CA, from January 2013 to June 2014. His research interests lie in the modeling, analysis, control, and optimization of computer and network systems, such as next-generation (NextG) wireless networks, edge and cloud computing, information-update systems, and cyber-physical systems. He also works broadly on various topics belonging to the intersections of networking, machine learning, security and privacy, and spatial computing. He has been the general co-chair of IEEE/IFIP WiOpt 2021 and the technical program co-chair of ACM MobiHoc 2023 and ITC 2021, and he has also served on the editorial boards of various IEEE/ACM journals (IEEE/ACM Transactions on Networking, ACM SIGMETRICS Performance Evaluation Review, IEEE Transactions on Network Science and Engineering, IEEE Internet of Things Journal, and IEEE Open Journal of the Communications Society). Dr. Ji is a senior member of the IEEE and the ACM. He was a recipient of the National Science Foundation (NSF) CAREER Award in 2017, the IEEE INFOCOM 2019 Best Paper Award, the IEEE/IFIP WiOpt 2022 Best Student Paper Award, the IEEE TNSE Excellent Editor Award in 2021 and 2022, and the Faculty Fellow Award from the College of Engineering at Virginia Tech in 2023.