# Learning Augmented Index Policy for Optimal Service Placement at the Network Edge

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 61 references that are in the map.
- First posted on arXiv 10 Jan 2021.

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

- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [Reward Biased Maximum Likelihood Estimation for Reinforcement Learning](https://mlsanity.com/paper/2011.07738/) (2020)
- [Service Placement with Provable Guarantees in Heterogeneous Edge Computing Systems](https://mlsanity.com/paper/1906.07055/) (2019)
- [Joint Service Placement and Request Routing in Multi-cell Mobile Edge Computing Networks](https://mlsanity.com/paper/1901.08946/) (2019)
- [Spatio-temporal Edge Service Placement: A Bandit Learning Approach](https://mlsanity.com/paper/1810.03069/) (2018)
- [Index Policies for Optimal Mean-Variance Trade-Off of Inter-delivery Times in Real-Time Sensor Networks](https://mlsanity.com/paper/1501.06446/) (2015)

## Built on by (most cited first, 4 of 4)

- [On learning Whittle index policy for restless bandits with scalable regret](https://mlsanity.com/paper/2202.03463/) (2022)
- [On the Regret of Online Edge Service Hosting](https://mlsanity.com/paper/2303.06851/) (2023)
- [Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits](https://mlsanity.com/paper/2109.09855/) (2021)
- [An Index Policy Based on Sarsa and Q-learning for Heterogeneous Smart Target Tracking](https://mlsanity.com/paper/2402.12015/) (2024)

## Abstract (arXiv)

We consider the problem of service placement at the network edge, in which a decision maker has to choose between N services to host at the edge to satisfy the demands of customers. Our goal is to design adaptive algorithms to minimize the average service delivery latency for customers. We pose the problem as a Markov decision process (MDP) in which the system state is given by describing, for each service, the number of customers that are currently waiting at the edge to obtain the service. However, solving this N-services MDP is computationally expensive due to the curse of dimensionality. To overcome this challenge, we show that the optimal policy for a single-service MDP has an appealing threshold structure, and derive explicitly the Whittle indices for each service as a function of the number of requests from customers based on the theory of Whittle index policy. Since request arrival and service delivery rates are usually unknown and possibly time-varying, we then develop efficient learning augmented algorithms that fully utilize the structure of optimal policies with a low learning regret. The first of these is UCB-Whittle, and relies upon the principle of optimism in the face of uncertainty. The second algorithm, Q-learning-Whittle, utilizes Q-learning iterations for each service by using a two time scale stochastic approximation. We characterize the non-asymptotic performance of UCB-Whittle by analyzing its learning regret, and also analyze the convergence properties of Q-learning-Whittle. Simulation results show that the proposed policies yield excellent empirical performance.