Online Caching in Tree Networks: Algorithms, Regret, and Complexity

Ativ Joshi, Rajat De, Rajarshi Bhattacharjee, Cameron N Musco, Abhishek Sinha, Mohammad Hajiesmaili
Proceedings of The 8th Annual Learning for Dynamics and Control Conference, PMLR 331:925-952, 2026.

Abstract

We study the problem of online caching when the caches are arranged in a tree network – the root is the source, the clients are at the leaves, and the intermediate nodes are the caches. Each client’s request for a file is forwarded up the tree until a cache hit occurs, or the request reaches the root node, with hits at lower levels of the tree yielding higher rewards. The goal is to maximize the total reward over a sequence of requests. The tree-caching problem models caching in many content delivery networks (CDNs) and generalizes work on caching in more restricted network models, such as those with a single client connected to a single cache or a single client connected to a multi-level cache. We show that for general tree networks, finding the optimal static offline caching configuration for a given request sequence is NP-Hard. However, in the natural setting where the tree has bounded depth and large enough cache capacities, we present an algorithm that computes a near-optimal configuration with high probability in polynomial time. We then leverage this result to give an online algorithm that achieves $(1+\epsilon)-$approximate sublinear regret for adversarial request sequences when the cache capacity $C$ satisfies $C = \tilde\Omega(\frac{1}{\epsilon^2})$. Numerical simulations show that our algorithm outperforms several natural baseline strategies.

Cite this Paper

BibTeX
@InProceedings{pmlr-v331-joshi26a, title = {Online Caching in Tree Networks: Algorithms, Regret, and Complexity}, author = {Joshi, Ativ and De, Rajat and Bhattacharjee, Rajarshi and Musco, Cameron N and Sinha, Abhishek and Hajiesmaili, Mohammad}, booktitle = {Proceedings of The 8th Annual Learning for Dynamics and Control Conference}, pages = {925--952}, year = {2026}, editor = {Sukhatme, Gaurav and Lindemann, Lars and Tu, Stephen and Wierman, Adam and Atanasov, Nikolay}, volume = {331}, series = {Proceedings of Machine Learning Research}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v331/main/assets/joshi26a/joshi26a.pdf}, url = {https://proceedings.mlr.press/v331/joshi26a.html}, abstract = {We study the problem of online caching when the caches are arranged in a tree network – the root is the source, the clients are at the leaves, and the intermediate nodes are the caches. Each client’s request for a file is forwarded up the tree until a cache hit occurs, or the request reaches the root node, with hits at lower levels of the tree yielding higher rewards. The goal is to maximize the total reward over a sequence of requests. The tree-caching problem models caching in many content delivery networks (CDNs) and generalizes work on caching in more restricted network models, such as those with a single client connected to a single cache or a single client connected to a multi-level cache. We show that for general tree networks, finding the optimal static offline caching configuration for a given request sequence is NP-Hard. However, in the natural setting where the tree has bounded depth and large enough cache capacities, we present an algorithm that computes a near-optimal configuration with high probability in polynomial time. We then leverage this result to give an online algorithm that achieves $(1+\epsilon)-$approximate sublinear regret for adversarial request sequences when the cache capacity $C$ satisfies $C = \tilde\Omega(\frac{1}{\epsilon^2})$. Numerical simulations show that our algorithm outperforms several natural baseline strategies.} }
Endnote
%0 Conference Paper %T Online Caching in Tree Networks: Algorithms, Regret, and Complexity %A Ativ Joshi %A Rajat De %A Rajarshi Bhattacharjee %A Cameron N Musco %A Abhishek Sinha %A Mohammad Hajiesmaili %B Proceedings of The 8th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2026 %E Gaurav Sukhatme %E Lars Lindemann %E Stephen Tu %E Adam Wierman %E Nikolay Atanasov %F pmlr-v331-joshi26a %I PMLR %P 925--952 %U https://proceedings.mlr.press/v331/joshi26a.html %V 331 %X We study the problem of online caching when the caches are arranged in a tree network – the root is the source, the clients are at the leaves, and the intermediate nodes are the caches. Each client’s request for a file is forwarded up the tree until a cache hit occurs, or the request reaches the root node, with hits at lower levels of the tree yielding higher rewards. The goal is to maximize the total reward over a sequence of requests. The tree-caching problem models caching in many content delivery networks (CDNs) and generalizes work on caching in more restricted network models, such as those with a single client connected to a single cache or a single client connected to a multi-level cache. We show that for general tree networks, finding the optimal static offline caching configuration for a given request sequence is NP-Hard. However, in the natural setting where the tree has bounded depth and large enough cache capacities, we present an algorithm that computes a near-optimal configuration with high probability in polynomial time. We then leverage this result to give an online algorithm that achieves $(1+\epsilon)-$approximate sublinear regret for adversarial request sequences when the cache capacity $C$ satisfies $C = \tilde\Omega(\frac{1}{\epsilon^2})$. Numerical simulations show that our algorithm outperforms several natural baseline strategies.
APA
Joshi, A., De, R., Bhattacharjee, R., Musco, C.N., Sinha, A. & Hajiesmaili, M.. (2026). Online Caching in Tree Networks: Algorithms, Regret, and Complexity. Proceedings of The 8th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 331:925-952 Available from https://proceedings.mlr.press/v331/joshi26a.html.

Related Material