PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-time Popularities

Alireza Sadeghi, Fatemeh Sheikholeslami, Georgios B. Giannakis

arXiv:1708.06698v2cs.NI

TL;DR

The paper addresses how small basestations can cache files under limited storage, unknown popularity dynamics, and costly backhaul service. It models local and global popularity with Markov processes and uses Q-learning plus linear function approximation to learn scalable caching policies online. The approximation converges faster in the reported tests, while reinforcement-learning caching reduces incurred costs even with storage for 10 / 1,000 = 0.01 of available files.

  • Problem

    Small basestations must learn what and when to cache despite limited memory, many contents, unknown popularity profiles, and space-time request dynamics.

  • Method

    The paper models local and global popularity with Markov processes and develops online Q-learning with linear function approximation, incorporating popularity mismatch and cache-refreshing costs.

  • Results

    The scalable algorithm converges faster to the optimal solution in the reported tests, and RL-enabled caching considerably reduces incurred costs with 10 / 1,000 = 0.01 of available files stored.

  • Takeaways & Limitations

    The resulting caching scheme is asynchronous and semi-distributed, with adaptive parameter tuning for space-time variability in file requests.

Abstract

from arXiv · show

Small basestations (SBs) equipped with caching units have potential to handle the unprecedented demand growth in heterogeneous networks. Through low-rate, backhaul connections with the backbone, SBs can prefetch popular files during off-peak traffic hours, and service them to the edge at peak periods. To intelligently prefetch, each SB must learn what and when to cache, while taking into account SB memory limitations, the massive number of available contents, the unknown popularity profiles, as well as the space-time popularity dynamics of user file requests. In this work, local and global Markov processes model user requests, and a reinforcement learning (RL) framework is put forth for finding the optimal caching policy when the transition probabilities involved are unknown. Joint consideration of global and local popularity demands along with cache-refreshing costs allow for a simple, yet practical asynchronous caching approach. The novel RL-based caching relies on a Q-learning algorithm to implement the optimal policy in an online fashion, thus enabling the cache control unit at the SB to learn, track, and possibly adapt to the underlying dynamics. To endow the algorithm with scalability, a linear function approximation of the proposed Q-learning scheme is introduced, offering faster convergence as well as reduced complexity and memory requirements. Numerical tests corroborate the merits of the proposed approach in various realistic settings.

I. INTRODUCTION

The paper frames 5G caching as an online learning problem under uncertain, space-time-varying local and global content popularity. It proposes Q-learning with a scalable approximation to learn caching policies while balancing popularity mismatch and cache-refreshing costs.

  • 5G traffic growth and congested backhaul links motivate shifting content fetching from peak to off-peak periods through small-basestation caching.
  • Content-agnostic small basestations must learn what and when to cache despite limited observations and unknown popularity profiles.
  • The proposed framework models space-time request popularity with Markov processes and uses online Q-learning to learn an optimal policy when transition probabilities are unknown.
  • Each small basestation estimates local popularity, exchanges it with the network operator to obtain global popularity, and tunes rewards between global trends and local requests.
  • A linear function approximation reduces the Q-learning scheme’s complexity and memory requirements while enabling faster convergence and tracking in non-stationary settings through stepsize selection.

II. MODELING AND PROBLEM STATEMENT

The system models a small basestation with limited storage that repeatedly selects files for caching from a much larger catalogue. Each slot reveals requests, exchanges popularity information, and updates the cache for subsequent demand.

  • A small basestation stores M unit-sized files from F ≫ M available files and selects a feasible cache contents vector at every slot.
  • Each slot comprises content delivery, information exchange of local and global popularity profiles, and cache placement for the next slot.
  • Slots may have unequal durations and can be scheduled around off-peak starts and peak traffic periods when service costs are high.
  • Cached requested files are served locally at almost zero cost, whereas uncached files require costly backhaul fetching that can increase delay and reduce QoE.
  • The control unit uses historical states and incurred costs to learn the optimal caching action for the next slot.

A. Cost functions and caching strategies

The caching objective combines cache-refreshing, local service, and global-popularity mismatch costs. These costs let the control unit trade off retaining files, serving local demand, and following network-wide trends.

  • The overall cost is modeled as the sum of three components representing cache refreshing, user-request service, and popularity mismatch.
  • Cache-refreshing cost counts files newly fetched and cached before a slot that were absent from the previous cache.
  • The service cost penalizes uncached files according to local popularity while treating transmission of cached files as relatively negligible.
  • Global-mismatch cost penalizes caching actions that omit globally popular files, promoting policies closer to global demand trends.
  • Weights λ1,t, λ2,t, and λ3,t control the relative importance of refreshing, local service, and global mismatch, with λ1,t ≪ λ2,t justified by cheaper off-peak refreshing.

B. Popularity profile dynamics

The framework models global and local popularity profiles as Markov processes with known state sets but unknown transition probabilities, framing caching as an RL decision problem.

  • Global and local popularity profiles are modeled using separate Markov chains.The global profile uses states in PG, alongside a corresponding set of local-profile states PL.
  • The transition probabilities underlying both popularity processes are unknown.
  • The overall network state combines global popularity, local popularity, and the caching decision.The feasible caching decisions belong to action set A.
  • The RL learner makes sequential caching decisions while observing resulting costs, avoiding the need to know transition probabilities beforehand.The formulation addresses the dimensionality challenges associated with RL problems.

C. Reinforcement learning formulation

The caching problem is formulated as sequential decision-making over observed popularity states and costs, with a policy minimizing discounted long-run average cost.

  • After each slot’s delivery and information exchange phases, global and local popularity profiles become available and the system state and conditional cost are revealed.
  • The expected slot cost is taken over local and global popularity profiles, with weighting parameters controlling the relative importance of its components.
  • A policy maps each system state to a caching action for the next slot.
  • The state value function measures discounted total average cost over an infinite horizon, balancing current and future costs through γ.
  • The objective is to find an optimal feasible policy that minimizes the average cost of every state.
  • Bellman optimality conditions motivate a Q-learning solver for the sequential caching optimization.

III. OPTIMALITY CONDITIONS

The paper contrasts model-based policy iteration with Q-learning: policy iteration requires transition probabilities and has high per-iteration complexity, whereas Q-learning avoids explicit transition estimation.

  • Bellman equations provide necessary optimality conditions for the sequential decision problem.
  • With known transition probabilities, policy iteration evaluates state values and updates the optimal policy.
  • The Q-function combines expected current cost with discounted future value under a policy.
  • Policy iteration alternates policy evaluation and policy update until the policy stops changing.
  • O(|S|3 + |A||S|2) is the per-iteration complexity of policy iteration.Policy evaluation costs O(|S|3), while policy updating costs O(|A||S|2).
  • Because transition probabilities are typically unavailable, Q-learning is introduced to infer the optimal policy without estimating all transition probabilities.Adaptive dynamic programming would estimate |S|2 × |A| probabilities and can be slow or impractical.

A. Optimal caching via Q-learning

The paper develops online Q-learning for caching with exploration and stochastic updates, then introduces linear function approximation to address slow convergence and improve scalability.

  • Q-learning jointly estimates the optimal policy and optimal state-action value function online.
  • The caching agent updates its Q estimate from the observed action cost and next state using stochastic gradient descent.
  • Q-learning converges to Q∗ with probability 1 when all state-action pairs are continuously updated under standard stochastic-approximation conditions.
  • The action-selection rule uses epsilon-greedy exploration, with higher exploration during initial learning or substantial popularity shifts.
  • The stepsize sequence must satisfy convergence conditions for the Q estimates to approach Q∗.
  • A constant stepsize prevents exact stationary convergence but allows adaptation to non-stationary Markov processes.The policy can nevertheless be obtained in practice before convergence is reached.
  • Linear function approximation is introduced because independent Q-value updates converge slowly and limit scalability.The approximation exploits relationships among Q-function values to enable multiple updates per observation.

IV. SCALABLE CACHING

The scalable caching scheme replaces the prohibitively large Q-table with a linear approximation that preserves global, local, and cache-refreshing cost components while reducing learned parameters.

  • Motivation: The exact Q-table grows prohibitively with the number of files, and action selection requires exhaustive search over feasible cache configurations.The table has |PG||PL||A|^2 entries, while |A| encompasses all selections of M files from F.
  • Approximation: Linear function approximation decomposes Q(s, a′) into global-popularity mismatch, local-popularity mismatch, and cache-refreshing components.The three terms correspond respectively to QG, QL, and QR.
  • Approximation: The approximation represents global and local costs through state-profile and file-specific parameters, with a separate parameter for average cache-refreshing cost.The global term uses θG_i,f, the local term models average cost when a file is not cached, and θR models refresh cost per content.
  • Approximation: The approximation incorporates the fixed-cache-size constraint a⊤1 = a′⊤1 = M, which supports factoring terms involving 1 − a′.The constraint is used in the derivation of the approximated Q-function.
  • Scalability: The parameter set Λ := {ΘG, ΘL, θa} reduces learning from |PG||PL||A|^2 parameters to (|PG| + |PL|)|F| + 1 parameters.This reduction is the central scalability benefit of the proposed Q-function approximation.

A. Learning Λ

The scalable learner updates its linear parameters online from observed popularity states and selects cache actions probabilistically. Its design reduces parameter growth and avoids exhaustive action searches while retaining a practical approximation to Q-learning.

  • Action selection: The action policy selects the M best files according to the approximate score with probability 1 − ϵt, and explores a random feasible action with probability ϵt.This combines exploitation of the learned approximation with probabilistic exploration.
  • Learning Λ: Algorithm 2 implements the scalable Q-learning approximation using stochastic-gradient parameter updates based on observed popularity profiles.The pseudocode updates parameters according to the derived rules after popularity profiles are revealed from user requests.
  • Scalability: The scalable scheme reduces the parameter count from |PG||PL||A|^2 to (|PG| + |PL|)|F| + 1.The reduction directly addresses the large state-action space of exact Q-learning.
  • Convergence: Unlike single-entry exact Q-learning updates, the scalable method updates F − M entries in ΘG and ΘL and θR per observation, leading to faster convergence.The broader update affects multiple learned components for each observation rather than only one table entry.
  • Action selection: The scalable method circumvents exhaustive searches over feasible actions during exploitation and error evaluation.This removes a computational step required by the exact Q-learning formulation.
  • State representation: The finite popularity-state representation partitions an otherwise infinite state space, creating a complexity–accuracy trade-off in quantization design.The popularity vectors act as centroids of quantization regions.

V. NUMERICAL TESTS

Numerical tests compare exact and scalable Q-learning with optimal caching across cost settings and network sizes. The scalable solver converges faster, remains effective in large state-action spaces, and adapts caching behavior to dynamic costs.

  • Experimental setup: The experiments compare Q-learning and its scalable approximation with the optimal policy under multiple caching-cost settings.The optimal policy assumes known transition probabilities, while the learning algorithms use specified exploration and stepsize parameters.
  • Small-network results: Q-learning and the scalable approximation converge to the optimal policy’s cost, but the scalable method converges faster, especially when mismatch costs slow exact learning.Under s1, high local and global popularity-mismatch costs require learning both Markov chains, whereas lower local mismatch costs under s2 simplify convergence.
  • Small-network results: Penalizing local popularity mismatch increases cache-accommodated requests, whereas prioritizing global popularity tracking produces lower cache-hit performance in the tested setting.This comparison uses settings s4 and s5; only the scalable solver is shown because exact Q-learning converges slowly there.
  • Convergence analysis: Under s6, the scalable algorithm reaches the optimal solution after only a few iterations, while exact Q-learning converges more slowly.The faster convergence is attributed to reduced problem dimension and multiple updates per iteration.
  • Large-network results: For 1,000 files and cache capacity 10, RL-enabled caching reduces incurred costs despite storing only 0.01 of available files, while approximate Q-learning provides scalability and lightweight updates.Exact optimal-policy computation is unaffordable in two large-network settings because of memory and computational requirements.
  • Dynamic-cost results: Dynamic cost parameters directly influence the caching policy, allowing the network operator to control caching behavior across intervals.The tests report corresponding cost and cache-accommodated-request percentages for preselected cost profiles.

VI. CONCLUSIONS

The paper models space-time file popularity with local and global Markov chains and formulates caching as reinforcement learning. Its online Q-learning policy and linear approximation support adaptive, scalable caching with lightweight updates.

  • Conclusions: The framework models local and global popularity mismatches together with cache-refreshing costs in a reinforcement-learning formulation of 5G caching.The popularity dynamics are represented by local and global Markov chains.
  • Conclusions: The Q-learning algorithm finds the optimal caching policy online, while a linear approximation provides scalability over large networks.The resulting scheme is asynchronous and semi-distributed, with adaptive parameter tuning for space-time request variability.
  • Conclusions: Adaptive parameter tuning enables policy adjustments to space-time file-request variability through lightweight updates.The conclusion characterizes the approach as an asynchronous and semi-distributed caching scheme.
Loading 1708.06698v2…