Efficient and Optimal No-Regret Caching under Partial Observation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915182303772672 |
|---|---|
| author | Mazziane, Younes Ben Faticanti, Francescomaria Alouf, Sara Neglia, Giovanni |
| author_facet | Mazziane, Younes Ben Faticanti, Francescomaria Alouf, Sara Neglia, Giovanni |
| contents | Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios like caching at a cellular base station. Therefore, we study the caching problem in a more restrictive setting where only a fraction of past requests are observed, and we propose a randomized caching policy with sublinear regret based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL). Our caching policy is the first to attain the asymptotically optimal regret bound while ensuring asymptotically constant amortized time complexity in the partial observability setting of requests. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under synthetic and real-world request traces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02758 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient and Optimal No-Regret Caching under Partial Observation Mazziane, Younes Ben Faticanti, Francescomaria Alouf, Sara Neglia, Giovanni Machine Learning Networking and Internet Architecture Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios like caching at a cellular base station. Therefore, we study the caching problem in a more restrictive setting where only a fraction of past requests are observed, and we propose a randomized caching policy with sublinear regret based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL). Our caching policy is the first to attain the asymptotically optimal regret bound while ensuring asymptotically constant amortized time complexity in the partial observability setting of requests. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under synthetic and real-world request traces. |
| title | Efficient and Optimal No-Regret Caching under Partial Observation |
| topic | Machine Learning Networking and Internet Architecture |
| url | https://arxiv.org/abs/2503.02758 |