2026-06-07-joshi26a.md

title	Online Caching in Tree Networks: Algorithms, Regret, and Complexity
section	Poster
openreview	T96umoMcab
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.
layout	inproceedings
series	Proceedings of Machine Learning Research
publisher	PMLR
issn	2640-3498
id	joshi26a
month	0
tex_title	Online Caching in Tree Networks: Algorithms, Regret, and Complexity
firstpage	925
lastpage	952
page	925-952
order	925
cycles	false
bibtex_author	Joshi, Ativ and De, Rajat and Bhattacharjee, Rajarshi and Musco, Cameron N and Sinha, Abhishek and Hajiesmaili, Mohammad
author	given family Ativ Joshi given family Rajat De given family Rajarshi Bhattacharjee given family Cameron N Musco given family Abhishek Sinha given family Mohammad Hajiesmaili
date	2026-06-07
address
container-title	Proceedings of The 8th Annual Learning for Dynamics and Control Conference
volume	331
genre	inproceedings
issued	date-parts 2026 6 7
pdf	https://raw.githubusercontent.com/mlresearch/v331/main/assets/joshi26a/joshi26a.pdf
extras