Reinforcement Learning for Dynamic Dimensioning of Cloud Caches: A Restless Bandit Approach
Reinforcement Learning for Dynamic Dimensioning of Cloud Caches: A Restless Bandit Approach
复制标题
DOI：
10.1109/infocom48880.2022.9796809
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Guojun Xiong;Shu-Fan Wang;Gang Yan;Jian Li
中科院分区：
文献类型：
--
作者：
Guojun Xiong;Shu-Fan Wang;Gang Yan;Jian Li
我们研究的动态缓存尺寸的问题，其中的目标是决定有多少存储放置在该高速缓存，以最大限度地减少总成本的存储和内容交付延迟。我们制定这个问题作为一个马尔可夫决策过程，这是一个不安分的多臂土匪问题，是证明难以解决。对于给定的尺寸决策，可以根据著名的Whittle指数策略开发解决方案。然而，Whittle索引策略还没有被研究用于动态缓存尺寸，主要是因为缓存尺寸需要反复求解并与内容缓存联合优化。为了克服这个困难，我们提出了一个低复杂度的流体惠特尔索引政策，共同确定尺寸和内容缓存。我们证明了该策略是渐近最优的。我们进一步开发了一个轻量级的强化学习增强算法称为fW-UCB时，内容的请求和交付率是不可用的。fW-UCB实现了次线性后悔，因为它充分利用了近最优流体Whittle指数策略的结构，因此可以很容易地实现。大量的模拟使用真实的痕迹支持我们的理论结果。
We study the dynamic cache dimensioning problem, where the objective is to decide how much storage to place in the cache to minimize the total costs with respect to the storage and content delivery latency. We formulate this problem as a Markov decision process, which turns out to be a restless multi-armed bandit problem and is provably hard to solve. For given dimensioning decisions, it is possible to develop solutions based on the celebrated Whittle index policy. However, Whittle index policy has not been studied for dynamic cache dimensioning, mainly because cache dimensioning needs to be repeatedly solved and jointly optimized with content caching. To overcome this difficulty, we propose a low-complexity fluid Whittle index policy, which jointly determines dimensioning and content caching. We show that this policy is asymptotically optimal. We further develop a lightweight reinforcement learning augmented algorithm dubbed fW-UCB when the content request and delivery rates are unavailable. fW-UCB is shown to achieve a sub-linear regret as it fully exploits the structure of the near-optimal fluid Whittle index policy and hence can be easily implemented. Extensive simulations using real traces support our theoretical results.