SC²I Distinguished Lecture | Pushing the Boundary for Index Policies: Recent Advances, Challenges and Opportunities

Many network control problems (e.g., minimizing age-of-information, network slicing, and caching, just to name a few examples) can be cast as Markov Decision Processes (MDP). However, as the network size increases, MDP is known to suffer from curse-of-dimensionality. Index policies, e.g., the Whittle index, can be a useful tool to decompose an otherwise intractable multi-agent MDP into per-agent problems, which can then lead to low-complexity, scalable and highly adaptive solutions. However, the existing theory of Whittle index still has severe limitations. First, when the problem of interest is slightly more complex, even verifying Whittle indexability becomes very challenging. Second, Whittle index cannot be used for systems with multiple heterogeneous resources. Third, calculating the index can still incur high overhead. In this talk, we will introduce some recent work that pushes the boundary for index policies in terms of (i) indexability verification, (ii) partial index for multiple resources, and (iii) fast index-computation. Our goal is to make index policies more easily applicable to a larger class of problem settings. We conclude with some discussions on further challenges and potential opportunities for index policies.