AI4OPT Seminar Series: An Algorithm for Crowdsourcing with Hard and Easy Tasks

Abstract: We discuss the role of learning in optimal network control, with focus on network stability in networks with uncooperative nodes, whose dynamics cannot be controlled and only sporadically estimated. It is well known that the MaxWeight algorithm can stabilize the network when all the nodes are fully cooperative. We show that MaxWeight fails when some of the nodes are uncooperative, and introduce Tracking-MaxWeight (TMW), which enhances the original algorithm with an explicit learning of the policy used by uncooperative nodes. We show that TMW achieves stability as long as the state of uncooperative nodes can be sporadically estimated and characterize the impact of infrequent and erroneous estimates on stability. Next, we consider the problem of network utility maximization (NUM) and propose a new Learning-NUM framework, where the users’ utility functions are unknown a priori and the utility function values can be observed only after the corresponding traffic is delivered to the destination. We design the Gradient Sampling Max-Weight algorithm (GSMW) based on the ideas of gradient estimation and Max-Weight scheduling, that achieves sublinear utility regret. We further demonstrate the applicability of the gradient sampling approach to minimum delay routing in wireless networks. Finally, we consider the general problem of reinforcement learning for queueing networks with unbounded state-spaces, with the goal of making control decisions that minimizing the queue length. We formulate the problem as an MDP with unknown queueing dynamics, and propose a new reinforcement learning framework, called Truncated Upper Confidence Reinforcement Learning (TUCRL), that can achieve optimal performance. Speaker Biography: Eytan Modiano is the Richard C. Maclaurin professor in the Department of Aeronautics and Astronautics and the Laboratory for Information and Decision Systems (LIDS) at MIT. Before joining MIT in 1999, Modiano was a Naval Research Laboratory Fellow between 1987 and 1992, a National Research Council Post-Doctoral Fellow during 1992-1993, and a member of the technical staff at MIT Lincoln Laboratory between 1993 and 1999. He received his B.S. degree in Electrical Engineering and Computer Science from the University of Connecticut at Storrs in 1986 and his M.S. and PhD degrees, both in Electrical Engineering, from the University of Maryland, College Park, MD, in 1989 and 1992 respectively. Modiano's research is on modeling, analysis and design of communication networks and protocols. He received the Infocom Achievement Award (2020) for contributions to the analysis and design of cross-layer resource allocation algorithms for wireless, optical, and satellite networks. He is the co-recipient of the Infocom 2018 Best paper award, the MobiHoc 2018 best paper award, the MobiHoc 2016 best paper award, the WiOpt 2013 best paper award, and the Sigmetrics 2006 best paper award. He was the Editor-in-Chief for IEEE/ACM Transactions on Networking (2017-2020) and served as Associate Editor for IEEE Transactions on Information Theory and IEEE/ACM Transactions on Networking. He was the Technical Program co-chair for IEEE WiOpt 2006, IEEE Infocom 2007, ACM MobiHoc 2007, and DRCN 2015; and general co-chair of WiOpt 2021. He had served on the IEEE Fellows committee in 2014 and 2015 and is a Fellow of the IEEE and an Associate Fellow of the AIAA. To receive AI4OPT seminar announcements, please sign up to our mailing list. at https://lists.isye.gatech.edu/mailman/listinfo/ai4opt-seminars. Past seminars can be found at https://www.ai4opt.org/seminars/past-seminars.