There is increasing interest in applying learning methods to networks, both to uncover the inherent unknowns in the system (through online bandit learning) and to tackle complex stochastic decision problems (through reinforcement learning). However, due to the unique network environment, directly using standard learning methods is often inadequate. For one, exploring options/arms across a communication network often involves significant overhead. The corresponding switching cost can significantly degrade the regret of bandit learning. For another, reinforcement learning methods treating the whole system as a large-scale MDP (Markov Decision Process) overlook the decentralized nature of network operation. As a result, the learned policy is often difficult to interpret and adapt slowly to changes. Thus, we argue that there is a significant need to revisit and improve learning methods for networks, possibly by borrowing ideas from network theory.
Specifically, I will talk about two of our recent studies in this direction. In the first work, motivated by the need to select ML (machine learning) models at a capacity-constrained edge server, we study online bandit learning with switching costs. We show a surprising "power-of-2-arms" effect, i.e., by having access to the feedback of two ML models at a time, our proposed learning algorithm can reduce the regret from $O(T^{2/3})$ to $O(T^{1/2})$. In the second work, motivated by stochastic decision problems for minimizing the age-of-information over multi-channel wireless networks, we propose a new concept of partial index that significantly extends the traditional Whittle index, which can be used to decompose the associated large-scale MDP and to produce scalable, easy-to-interpret, and adaptive solutions.

Speaker: Professor Xiaojun Lin
Date: 28 November 2023 (Tuesday)
Time: 11:00am – 12:00nn
Poster: Click here