# Minimizing Age of Information for Mobile Edge Computing Systems: A Nested Index Approach

arXiv: https://arxiv.org/abs/2307.01366 · HTML: https://mlsanity.com/paper/2307.01366/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 3 Jul 2023.

## Builds on (most cited first, 12 of 12)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Age of Information: An Introduction and Survey](https://mlsanity.com/paper/2007.08564/) (2020)
- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [Age of Information: Whittle Index for Scheduling Stochastic Arrivals](https://mlsanity.com/paper/1801.03422/) (2018)
- [A Whittle Index Approach to Minimizing Functions of Age of Information](https://mlsanity.com/paper/1908.10438/) (2019)
- [Deep Reinforcement Learning for Task Offloading in Mobile Edge Computing Systems](https://mlsanity.com/paper/2005.02459/) (2020)
- [Delay-Optimal Computation Task Scheduling for Mobile-Edge Computing Systems](https://mlsanity.com/paper/1604.07525/) (2016)
- [An Approximate Dynamic Programming Algorithm for Monotone Value Functions](https://mlsanity.com/paper/1401.1590/) (2014)
- [Optimizing Information Freshness Through Computation-Transmission Tradeoff and Queue Management in Edge Computing](https://mlsanity.com/paper/1912.02692/) (2019)
- [Age Optimal Information Gathering and Dissemination on Graphs](https://mlsanity.com/paper/1901.02178/) (2019)
- [Timely Cloud Computing: Preemption and Waiting](https://mlsanity.com/paper/1907.05408/) (2019)
- [Joint Caching and Transmission in the Mobile Edge Network: A Multi-Agent Learning Approach](https://mlsanity.com/paper/2209.04164/) (2022)

## Abstract (arXiv)

Exploiting the computational heterogeneity of mobile devices and edge nodes, mobile edge computation (MEC) provides an efficient approach to achieving real-time applications that are sensitive to information freshness, by offloading tasks from mobile devices to edge nodes. We use the metric Age-of-Information (AoI) to evaluate information freshness. An efficient solution to minimize the AoI for the MEC system with multiple users is non-trivial to obtain due to the random computing time. In this paper, we consider multiple users offloading tasks to heterogeneous edge servers in a MEC system. We first reformulate the problem as a Restless Multi-Arm-Bandit (RMAB) problem and establish a hierarchical Markov Decision Process (MDP) to characterize the updating of AoI for the MEC system. Based on the hierarchical MDP, we propose a nested index framework and design a nested index policy with provably asymptotic optimality. Finally, the closed form of the nested index is obtained, which enables the performance tradeoffs between computation complexity and accuracy. Our algorithm leads to an optimality gap reduction of up to 40%, compared to benchmarks. Our algorithm asymptotically approximates the lower bound as the system scalar gets large enough.