# Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation

arXiv: https://arxiv.org/abs/2202.13187 · HTML: https://mlsanity.com/paper/2202.13187/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 72 references that are in the map.
- First posted on arXiv 26 Feb 2022.

## Builds on (most cited first, 18 of 18)

- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare](https://mlsanity.com/paper/2105.07965/) (2021)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits](https://mlsanity.com/paper/2011.02664/) (2020)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-time Popularities](https://mlsanity.com/paper/1708.06698/) (2017)
- [A Reinforcement-Learning Approach to Proactive Caching in Wireless Networks](https://mlsanity.com/paper/1712.07084/) (2017)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [The Role of Caching in Future Communication Systems and Networks](https://mlsanity.com/paper/1805.11721/) (2018)
- [Adaptive Caching Networks with Optimality Guarantees](https://mlsanity.com/paper/1604.03175/) (2016)
- [User Association in Dense mmWave Networks as Restless Bandits](https://mlsanity.com/paper/2107.09153/) (2021)
- [A Utility Optimization Approach to Network Cache Design](https://mlsanity.com/paper/1601.06838/) (2016)
- [Understanding Performance of Edge Content Caching for Mobile Video Streaming](https://mlsanity.com/paper/1702.07627/) (2017)
- [Kelly Cache Networks](https://mlsanity.com/paper/1901.04092/) (2019)

## Built on by (most cited first, 8 of 8)

- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Towards Foundation-model-based Multiagent System to Accelerate AI for Social Impact](https://mlsanity.com/paper/2412.07880/) (2024)
- [Faster Q-Learning Algorithms for Restless Bandits](https://mlsanity.com/paper/2409.05908/) (2024)
- [GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits](https://mlsanity.com/paper/2408.09882/) (2024)
- [Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes](https://mlsanity.com/paper/2409.04605/) (2024)
- [From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvement](https://mlsanity.com/paper/2502.05145/) (2025)
- [Model-Based Learning of Whittle indices](https://mlsanity.com/paper/2511.20397/) (2025)
- [Adaptive Scheduling: A Reinforcement Learning Whittle Index Approach for Wireless Sensor Networks](https://mlsanity.com/paper/2601.01179/) (2026)

## Abstract (arXiv)

We consider the problem of content caching at the wireless edge to serve a set of end users via unreliable wireless channels so as to minimize the average latency experienced by end users due to the constrained wireless edge cache capacity. We formulate this problem as a Markov decision process, or more specifically a restless multi-armed bandit problem, which is provably hard to solve. We begin by investigating a discounted counterpart, and prove that it admits an optimal policy of the threshold-type. We then show that this result also holds for average latency problem. Using this structural result, we establish the indexability of our problem, and employ the Whittle index policy to minimize average latency. Since system parameters such as content request rates and wireless channel conditions are often unknown and time-varying, we further develop a model-free reinforcement learning algorithm dubbed as Q^{+}-Whittle that relies on Whittle index policy. However, Q^{+}-Whittle requires to store the Q-function values for all state-action pairs, the number of which can be extremely large for wireless edge caching. To this end, we approximate the Q-function by a parameterized function class with a much smaller dimension, and further design a Q^{+}-Whittle algorithm with linear function approximation, which is called Q^{+}-Whittle-LFA. We provide a finite-time bound on the mean-square error of Q^{+}-Whittle-LFA. Simulation results using real traces demonstrate that Q^{+}-Whittle-LFA yields excellent empirical performance.