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/tnet.2023.3235480
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Guojun Xiong;Shu-Fan Wang;Gang Yan;Jian Li
中科院分区：
文献类型：
--
作者：
Guojun Xiong;Shu-Fan Wang;Gang Yan;Jian Li
我们研究动态缓存规模问题，其目标是确定在缓存中放置多少存储空间，以最大限度地降低存储和内容交付延迟方面的总成本。我们将这个问题表述为马尔可夫决策过程，结果证明这是一个不安定的多臂老虎机问题，并且证明很难解决。对于给定的尺寸决策，可以根据著名的 Whittle 指数策略开发解决方案。然而，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.