# On the Regret of Online Edge Service Hosting

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 13 Mar 2023.

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

- [Mobile Edge Computing: A Survey on Architecture and Computation Offloading](https://mlsanity.com/paper/1702.05309/) (2017)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [LeadCache: Regret-Optimal Caching in Networks](https://mlsanity.com/paper/2009.08228/) (2020)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Service Placement with Provable Guarantees in Heterogeneous Edge Computing Systems](https://mlsanity.com/paper/1906.07055/) (2019)
- [Budget-constrained Edge Service Provisioning with Demand Estimation via Bandit Learning](https://mlsanity.com/paper/1903.09080/) (2019)
- [Joint Optimization of Service Caching Placement and Computation Offloading in Mobile Edge Computing Systems](https://mlsanity.com/paper/1906.00711/) (2019)
- [Learning Augmented Index Policy for Optimal Service Placement at the Network Edge](https://mlsanity.com/paper/2101.03641/) (2021)
- [Dynamic Service Migration in Mobile Edge Computing Based on Markov Decision Process](https://mlsanity.com/paper/1506.05261/) (2015)
- [RetroRenting: An Online Policy for Service Caching at the Edge](https://mlsanity.com/paper/1912.11300/) (2019)
- [Online Partial Service Hosting at the Edge](https://mlsanity.com/paper/2103.00555/) (2021)
- [Online Service Caching and Routing at the Edge with Unknown Arrivals](https://mlsanity.com/paper/2107.10446/) (2021)

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

- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)

## Abstract (arXiv)

We consider the problem of service hosting where a service provider can dynamically rent edge resources via short term contracts to ensure better quality of service to its customers. The service can also be partially hosted at the edge, in which case, customers' requests can be partially served at the edge. The total cost incurred by the system is modeled as a combination of the rent cost, the service cost incurred due to latency in serving customers, and the fetch cost incurred as a result of the bandwidth used to fetch the code/databases of the service from the cloud servers to host the service at the edge. In this paper, we compare multiple hosting policies with regret as a metric, defined as the difference in the cost incurred by the policy and the optimal policy over some time horizon T. In particular we consider the Retro Renting (RR) and Follow The Perturbed Leader (FTPL) policies proposed in the literature and provide performance guarantees on the regret of these policies. We show that under i.i.d stochastic arrivals, RR policy has linear regret while FTPL policy has constant regret. Next, we propose a variant of FTPL, namely Wait then FTPL (W-FTPL), which also has constant regret while demonstrating much better dependence on the fetch cost. We also show that under adversarial arrivals, RR policy has linear regret while both FTPL and W-FTPL have regret O(√T) which is order-optimal.