NSF Award 1824337, 2001687 - NSF: SpecEES: Collaborative Research: Leveraging Randomization and Human Behavior for Efficient Large-Scale Distributed Spectrum Access
Personnel:
PIs: Atilla Eryilmaz (OSU), Michael J. Neely (USC), Lei Ying (UMich), and Irem Eryilmaz (OSU)
Graduate Students: Xujin Zhou (PhD student, OSU), Dheeraj Narasimha (PhD student, ASU), Akshat Devrani (MS student, OSU)
Project Objectives:
This project seeks to design energy and spectrum-efficient strategies for scalable spectrum access of dynamic and large user populations under low-energy and stringent delay requirements. This is an increasingly pressing problem. Indeed, we are experiencing an explosion of low-cost wireless devices that promise new services in diverse domains, including health, transportation, energy, and entertainment. The capabilities and service requirements of these devices can vary greatly between very energy-limited and low-rate devices such as RFID tags, to highly powerful and throughput-hungry smart devices. Applications within the growing Internet-of-Things (IoT) present scenarios where mobile devices have a small number of packets but have strict delay constraints. How can desired energy and delay requirements be met in a distributed wide-spectrum multi-access setting? This problem is particularly challenging because the number of competing devices is possible large, unknown, and can change over time. Algorithms must adapt and learn, but required adaptation times are significantly restricted by the low delay requirements for the system. Algorithms must also make use of the vast amount of spectrum that has recently been made accessible by the FCC. Thus, the technology must efficiently utilize this very high and large frequency band (including the 57-71 GHz) that includes a mix of licensed and unlicensed bands for large-scale access.
Publications:
Qining Zhang, Zixian Yang and Lei Ying. "Towards Understanding the Fundamental Limits of Offline Stochastic Bandits with Constraints." Working paper.
Honghao Wei, Arnob Ghosh, Ness Shroff, Lei Ying, and Xingyu Zhou. "Provably efficient model-free algorithms for non-stationary CMDPs." In International Conference on Artificial Intelligence and Statistics, pp. 6527-6570. PMLR, 2023.
Yang, Zixian, R. Srikant, and Lei Ying. "Learning while scheduling in multi-server systems with unknown statistics: MaxWeight with discounted UCB." In International Conference on Artificial Intelligence and Statistics, pp. 4275-4312. PMLR, 2023.
M. Wijewardena and M. J. Neely, "A Two-Player Resource-Sharing Game with Asymmetric Information," Games, vol. 14, no. 61, 2023.
K. Asgari and M. J. Neely, "Nonsmooth Projection-Free Optimization with Functional Constraints,"arXiv:2311.11180v1
M. Wijewardena and M. J. Neely, "Multi-Player Resource-Sharing Games with Fair Reward Allocation," arXiv:2402.05300v2
M. J. Neely, "Adaptive Optimization for Stochastic Renewal Systems," arXiv:2401.07170v1
Z. Zhou, I. Koprulu, A. Eryilmaz, M. J. Neely. "Efficient Distributed MAC for Dynamic Demands: Congestion and Age Based Designs", IEEE/ACM Transactions on Networking, DOI 10.1109/TNET.2022.3191607, 2022.
B. Abolhassani, J. Tadrous and A. Eryilmaz, "Single vs Distributed Edge Caching for Dynamic Content," in IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 669-682, April 2022, doi: 10.1109/TNET.2021.3121098.
B. Abolhassani, J. Tadrous, A. Eryilmaz and E. Yeh, "Fresh Caching of Dynamic Content Over the Wireless Edge," in IEEE/ACM Transactions on Networking, vol. 30, no. 5, pp. 2315-2327, Oct. 2022, doi: 10.1109/TNET.2022.3170245.
S. Cayci, Y. Zheng, A. Eryilmaz, "A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback", Proceedings of the AAAI Conference on Artificial Intelligence, pages 2159-5399, 2022.
M. J. Neely. "Repeated Games, Optimal Channel Capture, and Open Problems for Slotted Multiple Access", 58th Allerton Conf. on Communication, Control, and Computing, 2022.
Honghao Wei, Xin Liu, Lei Ying. "A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes", AAAI, 2022.
Honghao Wei, Xin Liu, Lei Ying. "Triple-Q: A Model-Free Algorithm for Constrained Reinforcement Learning with Sublinear Regret and Zero Constraint Violation", AISTATS, 2022.
M. J. Neely. "A Converse Result on Convergence Time for Opportunistic Wireless Scheduling", IEEE Transactions on Networking, DOI 10.1109/TNET.2022.3146126, 2022.
M. J. Neely. "Random Variables with Measurability Constraints with Application to Opportunistic Scheduling", arXiv:2207.02345v1, July 2022.
Xin Liu, Bin Li, Pengyi Shi, Lei Ying, "An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints", Proc. NeurIPS, 2021.
X. Zhou, I. Koprulu, A. Eryilmaz, M. J. Neely, "Low-Overhead Distributed MAC for Serving Dynamic Users over Multiple Channels," Proc. WiOpt 2021. https://viterbi-web.usc.edu/~mjneely/docs/solitonMAC2021.pdf
M. J. Neely, "Reversible Models for Wireless Multi-Channel Multiple Access," Proc. IEEE INFOCOM, 2021. https://ee.usc.edu/stochastic-nets/docs/multi-channel-reversible-infocom2021.pdf
Hairi, X. Liu, and L. Ying, "Beyond Scaling: Calculable Error Bounds of the Power-of-Two-Choices Mean-Field Model in Heavy-Traffic", in Proceedings of ACM MobiHoc, 2021.
X. Liu, B. Li, P. Shi, and L. Ying, "A Constrained Bandit Approach for Online Dispatching," SIGMETRICS, RLNQ Workshop, 2021.
B. Abolhasani, J. Tadrous, A. Eryilmaz, E. Yeh, ‘‘Fresh Caching for Dynamic Content’’, in Proceedings of IEEE Infocom, 2021.
S. Kang, A. Eryilmaz, and C. Joo, “Comparison of Decentralized and Centralized Update Paradigms for Remote Tracking of Distributed Dynamic Sources”, in Proceedings of IEEE Infocom, 2021.
J. Yun, A. Eryilmaz, and C. Joo, “Remote Tracking of Dynamic Sources under Sublinear Communication Costs”, in Proceedings of IEEE Infocom, AoI Workshop, 2021.
G. Quan, J. Tan, A. Eryilmaz, N. Shroff, ‘‘Prefetching and Caching for Minimizing Service Costs: Optimal and Approximation Strategies’’, in Proceedings of IFIP Performance, 2020.
S. Cayci, S. Gupta, A. Eryilmaz, ‘‘Group-Fair Online Allocation in Continuous Time’’, in Proceedings of NeurIPS, 2020.
Weichang Wang and Lei Ying. "Learning Parallel Markov Chains over Unreliable Wireless Channels", in 54th Annual Conference on Information Sciences and Systems (CISS), 1-6, 2020.
Bahman Abolhassani, John Tadrous, A. Eryilmaz, ‘‘Achieving Freshness in Single/Multi-User Caching of Dynamic Content over the Wireless Edge’’, in Proceedings of IEEE International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2020.
Guocong Quan, Jian Tan, A. Eryilmaz ‘‘Counterintuitive Characteristics of Optimal Distributed LRU Caching Over Unreliable Channels’’, in IEEE/ACM Transactions on Networking, December, 2020.
S. Cayci and A. Eryilmaz, "Optimal Learning for Dynamic Coding in Deadline-Constrained Multi-Channel Networks," in IEEE/ACM Transactions on Networking, vol. 27, no. 3, pp. 1043-1054, June 2019.
J. Tadrous, A. Eryilmaz and A. Sabharwal, "Action-Based Scheduling: Leveraging App Interactivity for Scheduler Efficiency," in IEEE/ACM Transactions on Networking, vol. 27, no. 1, pp. 112-125, Feb. 2019.
B. Abolhasani, J. Tadrous, A. Eryilmaz, ‘‘Wireless Multicasting for Content Distribution: Endless Stability and Delay Gains’’, in Proceedings of IEEE Infocom, May, 2019.
D. Narasimha, S. Shakkottai and L. Ying. “A Mean Field Game Analysis of Distributed MAC in Ultra-Dense Multichannel Wireless Networks.” In Proc. MobiHoc 2019, Catania, Italy, July, 2019.
Educational/Broader Impact Activities:
PI Ying has been working with undergraduate students through the Summer Undergraduate Research in Engineering (SURE) program at Michigan.
PI Ying has developed a new course on machine learning for undergraduate students at the University of Michigan.
PI Ying has developed a new course on reinforcement learning at the University of Michigan.
PI Ying has developed an online Master course on reinforcement learning algorithms.
PI Neely held a zoom-seminar for students and faculty at USC on lessons learned from 7 semesters of the MAC game competition in the EE 550 Data Networks class. This included a 3-slot game played by two audience members; reporting on the results of student algorithms for playing the 100-slot games; reporting on open problems. Slides are here: https://viterbi-web.usc.edu/~mjneely/docs/MAC-GAME-CILQ-Nov2021-markup.pdf
PI Ying co-organized a 2-day workshop on Epidemics, Opinion, and (Mis)Information: The Analytic Foundations of Dynamics over Networks
PI A. Eryilmaz has been regularly teaching a course on network optimization and algorithms that present stochastic design and analysis methods for optimizing wireless network resources.
PI A. Eryilmaz has developed and taught a new course on Online Learning. In particular, the courses included discussions and project topics on designing efficient distributed random access strategies for a large population of users.
PI Ying gave invited talks on mean-field analysis at the University of Michigan, Cornell, and Princeton. The talks presented the concepts and analytical framework based on Lyapunov theory and Stein's methods.
PI Neely has been teaching a graduate course on data networks that includes a MAC-game project, whereby students design their own multi-access algorithms as matlab subroutines and compete them against each other in a tournament of 2-player multi-access games. This course project not only contributes to the students’ understanding of the elements of multiple access and resource sharing, but provides valuable input on various strategies that can feed into the research investigations. A publication that presents results on these games and develops mathematical properties of winning algorithms is in the works.
PI I. Eryilmaz has been teaching an individual study course geared to MS students. Students work on setting up and running an experimental platform based on software defined radio devices to implement and test the designs under this project. This provides valuable hands-on training opportunity to these graduate students and prepares them for future engineering jobs.
PIs also gave an invited talk at several universities (e.g., University of Michigan, Cornell and Princeton), and SIGMETRICS CINS Workshop 2019.
USC student design project on random access (Fall 2019): Students in the EE 550 class of PI Neely were given the open-ended problem of writing a matlab program to change the slotted Aloha algorithm, analyzed in class when the number of users is fixed and known, to operate in an environment with a fixed but unknown number of users. Is it possible to meet or exceed the 1/e throughput as analyzed in class? This may involve estimation, dynamic probability selection, and dynamic channel capture strategies. Students were encouraged to investigate this question using their own ideas. Each student designed a single algorithm that all (unknown) number of multi-access users implement. Several students volunteered to present their algorithm and its simulated throughput and fairness results to the class.
USC Multi-Access student competition (Fall 2019): A multi-access programming challenge was held in the Fall 2019 semester of the EE 550 Data Networks class of PI Neely. Students programmed their multi-access algorithms into matlab. The challenge here is that the algorithm must be designed to operate well against unknown algorithms designed by other students. (This considers human-in-the-loop factors.) The 4-state algorithm and the FullGreedy algorithm (of interest in this NSF project) were also entered into the competition. All algorithms were paired for competition against all other algorithms in separate one-on-one games. The total score of each algorithm (summed over all games) was tallied and compared. Top-scoring students were asked to present the ideas behind their algorithm to the class. This multi-access competition has been conducted at USC in the past 4 semesters and the 4-state algorithm has never lost. In general, greedy algorithms always do poorly, and algorithms that learn to fairly share the channel do well.