Deep Reinforcement Learning for Adaptive Caching in Hierarchical Content Delivery Networks
Alireza Sadeghi Gang Wang Georgios B. Giannakis

	
	
	
	
	
	
	Deep Reinforcement Learning for Adaptive Caching  
		in Hierarchical Content Delivery Networks
    Alireza Sadeghi, Gang Wang, and Georgios B. Giannakis
		This work was supported in part by NSF grants 1711471 and 1514056. The authors are with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA. E-mails: {sadeghi, gangwang, georgios}@umn.edu. 
		
	
    December 30, 2023
=======================================================================================================================================================================================================================================================================================================================================================


		Caching is envisioned to play a critical role in next-generation content delivery infrastructure, cellular networks, and Internet architectures. By smartly storing the most popular contents at the storage-enabled network entities during off-peak demand instances, caching can benefit both network infrastructure as well as end users, during on-peak periods. In this context, distributing the limited storage capacity across network entities calls for decentralized caching schemes. Many practical caching systems involve a parent caching node connected to multiple leaf nodes to serve user file requests. To model the two-way interactive influence between caching decisions at the parent and leaf nodes, a reinforcement learning (RL) framework is put forth. To handle the large continuous  state space, a scalable deep RL approach is pursued. The novel approach relies on a hyper-deep Q-network to learn the Q-function, and thus the optimal caching policy, in an online fashion. Reinforcing the parent node with ability to learn-and-adapt to unknown policies of leaf nodes as well as spatio-temporal dynamic evolution of file requests, results in remarkable caching performance, as corroborated through numerical tests.     
	
	
	
		Caching, deep RL, deep Q-network, next-generation networks, function approximation. 
		
	
	
	

§ INTRODUCTION

	
	In light of the tremendous growth of data traffic over both wireline and wireless communications, next-generation networks including future Internet architectures, content delivery infrastructure, and cellular networks stand in need of emerging technologies to meet the ever-increasing data demand. Recognized as an appealing solution is caching, which amounts to storing reusable contents in geographically distributed storage-enabled network entities so that future requests for those contents can be served faster. The rationale is that unfavorable shocks of peak traffic periods can be smoothed by proactively storing `anticipated' highly popular contents at those storage devices and during off-peak periods <cit.>. Caching popular content is envisioned to achieve major savings in terms of energy, bandwidth, and cost, in addition to user satisfaction <cit.>.
	
To fully unleash its potential, a content-agnostic caching entity has to rely on available observations to learn what and when to cache. Toward this goal, contemporary machine learning and artificial intelligence tools hold the promise to empower next-generation networks with `smart' caching control units, that can learn, track, and adapt to unknown dynamic environments, including space-time evolution of content popularities and network topology, as well as entity-specific caching policies.

Deep neural networks (DNNs) have lately boosted the notion of “learning from data” with field-changing performance improvements reported in diverse  artificial intelligence tasks <cit.>. DNNs can cope with the `curse of dimensionality' by providing compact low-dimensional representations of high-dimensional data <cit.>. Combining deep learning with RL, deep (D) RL has created the first artificial agents to achieve human-level performance across many challenging domains <cit.>. As another example, a DNN system was built to operate Google's data centers, and shown able to consistently achieve a 40% reduction in  energy consumption for cooling <cit.>. This system provides a general-purpose framework to understand complex dynamics, which has also been applied to address other challenges  including e.g., dynamic spectrum access <cit.>, multiple access and handover control <cit.>, <cit.>, as well as resource allocation in fog-radio access networks <cit.>. 



 §.§ Prior art on caching

Early approaches to caching include the least recently used (LRU), least frequently used (LFU), first in first out (FIFO), random replacement (RR) policies, and their variants. Albeit simple, these schemes cannot deal with the dynamics of content popularities and network topologies.	Recent efforts have gradually shifted toward developing learning and optimization based approaches that can `intelligently' manage the cache resources. For unknown but time-invariant content popularities, multi-armed bandit online learning (e.g., <cit.>) was pursued in <cit.>.  Yet, these methods are generally not amenable to online implementation. To serve delay-sensitive requests, a learning approach was developed in <cit.> using a pre-trained DNN to handle a non-convex problem reformulation.
	
In realistic networks however, popularities exhibit dynamics, which motivate well the so-termed dynamic caching. A Poisson shot noise model was adopted to approximate the evolution of popularities in <cit.>, for which an age-based caching solution was developed in <cit.>. RL based methods have been pursued in <cit.>. Specifically, a Q-learning based caching scheme was developed in <cit.> to model global and local content popularities as Markovian processes. Considering Poisson shot noise popularity dynamics, a policy gradient RL based caching scheme was devised in <cit.>. Assuming stationary file popularities and service costs, a dual-decomposition based Q-learning approach was pursued in <cit.>.  Albeit reasonable for discrete states, these approaches cannot deal with large continuous state-action spaces. To cope with such spaces, DRL approaches have been considered for content caching in e.g., <cit.>. Encompassing finite-state time-varying Markov channels, a deep Q-network approach was devised in <cit.>. An actor-critic method with deep deterministic policy gradient updates was used in <cit.>. Boosted network performance using DRL was documented in several other applications, such as connected vehicular networks <cit.>, and smart cities <cit.>.


The aforementioned works focus on devising caching policies for a single caching entity. A more common setting in next-generation networks however, involves a network of interconnected caching nodes. It has been shown that considering a network of connected caches jointly can further improve performance <cit.>. For instance, leveraging network topology and the broadcast nature of links, the coded caching strategy in <cit.> further reduces data traffic over a network. This idea has been extended in <cit.> to an online setting, where popularities are modeled Markov processes. Collaborative and distributed online learning approaches have been pursued <cit.>.  Indeed, today's content delivery networks such as Akamai <cit.>, have tree network structures. Accounting for the hierarchy of caches has become a common practice in recent works; see also <cit.>. Specifically, a general framework to evaluate caching policies in a hierarchical network of caches was developed in <cit.>. Joint routing and in-network content caching in a hierarchical cache network was formulated in <cit.>, for which greedy schemes with provable performance guarantees can be found in <cit.>. 
	
We identify the following challenges that need to be addressed when designing practical caching methods for next-generation networks.

	
  c1) Networked caching. Caching decisions of a node, in a network of caches, influences decisions of all other nodes. Thus, a desired caching policy must adapt to the network topology and policies of neighboring nodes.

	
  c2) Complex dynamics. Content popularities are random and exhibit unknown space-time, heterogeneous, and often non-stationary dynamics over the entire network. 
	
	
  c3) Large continuous state space. Due to the shear size of available content, caching nodes, and possible realizations of content requests, the decision space is huge. 
		
	 
	


 §.§ This work
 
 Prompted by the recent interest in hierarchical caching, this paper focuses on a two-level network caching, where a parent node is connected to multiple leaf nodes to serve end-user file requests. Such a two-level network constitutes the building block of the popular tree hierarchical cache networks in e.g., <cit.>. To model the interaction between caching decisions of parent and leaf nodes along with the space-time evolution of file requests, a scalable DRL approach  based on hyper deep Q-networks (DQNs) is developed. As corroborated by extensive numerical tests, the novel caching policy for the parent node can adapt itself to local policies of leaf nodes and space-time evolution of file requests. Moreover, our approach is simple-to-implement, and performs close to the optimal policy.  

	

	


§ MODELING AND PROBLEM STATEMENT

	
Consider a two-level network of interconnected caching nodes, where a parent node is connected to N leaf nodes, indexed by n∈𝒩:={1,…,N}. The parent node is connected to the cloud through a (typically congested) back-haul link; see Fig. <ref>. One could consider this network as a part of a large hierarchical caching system, where the parent node is connected to a higher level caching node instead of the cloud; see Fig. <ref>. In a content delivery network for instance, edge servers (a.k.a. points of presence or PoPs) are the leaf nodes, and a fog server acts as the parent node. Likewise, (small) base stations in a 5G cellular network are the leaf nodes, while a serving gate way (S-GW) may be considered as the parent node; see also <cit.>.   
	
All nodes in this network store files to serve file requests. Every leaf node serves its locally connected end users, by providing their requested files. If a requested content is locally available at a leaf node, the content will be served immediately at no cost. If it is not locally available due to limited caching capacity, the content will be fetched from its parent node, at a certain cost. Similarly, if the file is available at the parent node, it will be served to the leaf at no cost; otherwise, the file must be fetched from the cloud at a higher cost.
	
To mitigate the burden with local requests on the network, each leaf node stores `anticipated' locally popular files. In addition, this paper considers that each parent node stores files to serve requests that are not locally served by leaf nodes. Since leaf nodes are closer to end users, they frequently receive file requests that exhibit rapid temporal evolution at a fast timescale. The parent node on the other hand, observes aggregate requests over a large number of users served by the N leaf nodes, which naturally exhibit smaller fluctuations and thus evolve at a slow timescale. 

This motivated us to pursue a two-timescale approach to managing such a network of caching nodes. To that end, let τ=1,2,… denote the slow time intervals, each of which is further divided into T fast time slots indexed by t=1,…,T; see Fig. <ref> for an illustration. Each fast time slot may be e.g., 1-2 minutes depending on the dynamics of local requests, while each slow time interval is a period of say 4-5 minutes. We assume that the network state remains unchanged during each fast time slot t, but can change from t to t+1.
	
Consider a total of F files in the cloud, which are collected in the set ℱ = {1,  …, F}. At the beginning of each slot t, 	every leaf node n selects a subset of files in ℱ to prefetch and store for possible use in this slot.
To determine which files to store, every leaf node relies on a local caching policy function denoted by π_n, to take (cache or no-cache) action a_n ( t+1, τ  ) = π_n ( s_n (t, τ)) at the beginning of slot t+1, based on its state vector s_n at the end of slot t. We assume this action takes a negligible amount of time relative to the slot duration; and  define the state vector s_n (t, τ) := r_n(t,τ) := [r_n^1(t,τ) ⋯ r_n^F(t,τ)]^⊤ to collect the number of requests received at leaf node n for individual files over the duration of slot t on interval τ. Likewise, to serve file requests that have not been served by leaf nodes, the parent node takes action a_0 ( τ ) to store files at the beginning of every interval τ, according to a certain policy π_0. Again, as aggregation smooths out request fluctuations, the parent node observes slowly varying file requests, and can thus make caching decisions at a relatively slow timescale. In the next section, we present a two-timescale approach to managing such a network of caching nodes. 




§ TWO-TIMESCALE PROBLEM FORMULATION

File transmission over any network link consumes resources, including e.g., energy, time, and bandwidth. Hence, serving any requested file that is not locally stored at a node, incurs a cost. Among possible choices, the present paper considers the following cost for node n∈𝒩, at slot t+1 of interval τ

    c_n(π_n ( s_n ( t,τ ) ),  r_n (t+1,τ),  a_0 (	τ ) )   :=   r_n (t+1, τ) ⊙  (  1 -  a_0 (τ))  
    ⊙ (  1-  a_n (t+1,τ) ) +  r_n (t+1, τ) ⊙ (  1-  a_n(t+1,τ) )


where c_n (·):=[c_n^1(·) ⋯ c_n^F(·)]^⊤ concatenates the cost for serving individual files per node n; symbol ⊙ denotes entry-wise vector multiplication; entries of a_0 and a_n are either 1 (cache, hence no need to fetch), or, 0 (no-cache, hence fetch); and 1 stands for the all-one vector. Specifically, the second summand in (<ref>) captures the cost of the  leaf node fetching files for end users, while the first summand corresponds to that of the parent fetching files from the cloud. 

We model user file requests as Markov processes with unknown transition probabilities <cit.>. Per interval τ, a reasonable caching scheme for leaf node n∈𝒩 could entail minimizing the expected cumulative cost; that is, 
	
    π^∗_n,τ:= π_n ∈Π_nmin 𝔼[ ∑_t=1^T 1^⊤ c_n (π_n ( s_n ( t,τ ) ),  r_n (t+1,τ),  a_0 (τ ))]
 
where Π_n represents the set of all feasible policies for node n. Although solving (<ref>) is in general challenging, efficient near-optimal solutions have been introduced in several recent contributions; see e.g., <cit.>, and references therein. In particular, a RL based approach using tabular Q-learning was pursued in our precursor <cit.>, which can be employed here to tackle this fast timescale optimization. The remainder of this paper will thus be on designing the caching policy π_0 for the parent node, that can learn, track, and adapt to the leaf node policies as well as user file requests.   
	


	
At the beginning of every interval τ +1, the parent node takes action to refresh its cache; see Fig. <ref>. To design a caching policy that can account for both leaf node policies and file popularity dynamics, the parent collects local information from all leaf nodes. At the end of interval τ, each leaf node n∈𝒩 first obtains the time-average state vector s̅_n (τ):= (1/T) ∑_t=1^T s_n ( t , τ), and subsequently forms and forwards the per-node vector s̅_n ( τ ) ⊙ ( 1 - π_n ( s̅_n ( τ )) ) to its parent node. This vector has nonzero entries the average number of file requests received during interval τ, and zero entries if π_n stores the corresponding files. Using the latter, the parent node forms its `weighted' state vector as
	
    s_0 (τ):= ∑_n = 1^N w_n s̅_n ( τ ) ⊙ ( 1 - π_n ( s̅_n (τ) ) )

where the weights {w_n≥ 0} control the influence of leaf nodes n∈𝒩 on the parent node's policy. Similarly, having received at the end of interval τ +1 the slot-averaged costs

    c̅_n( π_0 ( s_0 ( τ))  ;  { a_n ( t, τ +1),  r_n ( t , τ +1) }_t=1^T )
     
    	 = 1/T∑_t = 1^T c_n( a_n (t,τ+1),  r_n(t,τ+1 ),  a_0 (	τ +1) )

from all leaf nodes, the parent node determines its cost 

    c_0 (  s_0 ( τ), π_0 ( s_0 ( τ)) )   
         = ∑_n=1^N w_n  c̅_n( π_0 (  s_0 (τ) )  ; { a_n ( t, τ +1),  r_n ( t , τ +1) }_t=1^T ) ).

Having observed { s_0( τ' ),  a_0 ( τ'),  c_0 (  s_0 ( τ'-1),  a_0 (τ') }_τ' = 1^τ, the objective is to take a well-thought-out action a_0 ( τ + 1 ) for next interval. This is tantamount to finding an optimal policy function π^∗_0 to take a caching action a_0 (τ + 1 ) = π^∗_0 ( s_0 ( τ)). 
	
Since the requests { r_n (t,τ)}_n,t are Markovian and present actions { a_n ( t , τ )}_n,t also affect future costs, the optimal RL policy for the parent node will minimize the expected cumulative cost over all leaf nodes in the long term, namely

    π_0^∗:=π_0 ∈Π_0min 𝔼[ ∑_τ= 1^∞γ^τ-1 1^⊤ c_0(  s_0 (τ), π_0 (  s_0 (τ) )  )  ]
  
where Π_0 represents the set of all feasible policies; 
expectation is over { r_n (t,τ)}_n,t, as well as (possibly random) parent a_0 (τ) and leaf actions { a_n ( t , τ )}_n,t; and the discount factor γ∈ [ 0, 1) trades off emphasis of current versus future costs. 
	
It is evident from (<ref>) that the decision taken at a given state s_0 (τ), namely a_0 (τ +1) = π ( s_0(τ)), influences the next state s_0(τ+1) through π_n,τ (·)  in (<ref>), as well as the cost c_0 (·) in (<ref>). Therefore, problem (<ref>) is a discounted infinite time horizon Markov decision process (MDP). Finding the optimal policy of an MDP is NP-hard <cit.>. To cope with this complexity of solving 
(<ref>), an adaptive  RL approach is pursued next. 



§ ADAPTIVE RL-BASED CACHING
 
	
RL deals with action-taking policy function estimation in an environment with dynamically evolving states, so as to minimize a long-term cumulative cost. By interacting with the environment (through successive actions and observed states and costs), RL seeks a policy function (of states) to draw actions from, in order to minimize the average cumulative cost as in  (<ref>) <cit.>. To proceed, we start by giving some basics on Markov decision processes (MDPs) <cit.>.




 §.§ MDP formulation

MDPs provide a well-appreciated model for decision making tasks. It is represented by a tuple <𝒮, 𝒜, 𝒞, 𝒫>, where 𝒮 denotes a set of possible states, 𝒜 a set of feasible actions, 𝒞 a set of costs, and 𝒫 the set of state transition probabilities. In our problem of interest, at the end of each interval τ, the parent node is in state s_0(τ) ∈𝒮 and takes a caching decision a_0 (τ+1) ∈𝒜 for the next interval τ+1, according to its local caching policy a_0 (τ+1) = π_0( s_0(τ)). Upon proceeding to interval τ+1, every leaf node n serves its locally connected users. Let vector r_n (t,τ+1) collect the number of received requests at node n during slot t across files. We model the temporal evolution of this vector with Markov dynamics as r_n (t+1,τ+1) = ⌊ r_n (t,τ+1) + Δ_n (t,τ+1)⌋^+, where Δ_n(t,τ+1) is a multivariate Gaussian random noise; ⌊·⌋ and (·)^+ denote the entry-wise floor and  max{·, 0} operators. In this context, the incurred cost c_0 ( s_0(τ), π_0( s_0(τ))) ∈𝒞 (c.f. (<ref>)), is a random vector with an unknown distribution. As requests { r_n} are random, caching decisions { a_n} are also random. In addition, decision a_0 of the parent node  influences those of leaf nodes via (<ref>), as well as the next state of the parent node in (<ref>). That is, the current decision of parent node probabilistically influences its next state. To formalize this, we use P^ a_ s  s'∈𝒫 to denote the unknown state transition probability from state s to s' upon taking action a

    P^ a_ s  s' = Pr{ s(τ + 1) =  s' | s(τ) =  s,  a = π( s) }
 
where the subscript 0 referring to the parent node is dropped for brevity. 
As a_0 probabilistically influences the next state as well as the incurred cost, 
our problem is indeed an MDP. The rest of this paper targets finding an optimal policy solving (<ref>). 

 

 §.§ RL based caching
 
 Towards developing an RL solver for  (<ref>), define the so-termed value function to indicate the quality of policy π_0, starting from initial state s_0 (0) as 
	
    V_π_0 (  s_0 ( 0 )):= 𝔼[ ∑_τ= 1^∞γ^τ-1 1^⊤ c_0 (  s_0 (τ), π_0 (  s_0 (τ) ) )  ]
  
which represents the average cost of following policy π_0 to make caching decisions starting from s_0(0). Upon finding V_π_0(·) for all π_0 ∈Π_0, one can readily obtain π_0^∗ that minimizes V_π_0( s_0 ( 0 )) over all possible initial states s_0 (0).
	
For brevity, the time index and the subscript 0 referring to the parent node will be dropped whenever it is clear from the context.
To find V_π(·), one can rely on the Bellman equation, which basically relates the value of a policy at one state to values of the remaining states <cit.>. 
Leveraging (<ref>) and (<ref>), the Bellman equation for value function V_π(·) is given by

    V_π (  s) =  𝔼[ 1^⊤ c ( s, π ( s ))  + γ∑_ s' P^π ( s)_ s  s' V_π ( s')  ]

	where the average immediate cost can be found as 
	
    𝔼[  1^⊤ c ( s, π ( s )) ] = ∑_ s' P^π ( s)_ s  s' 1^⊤ c( s, π ( s) |  s').

	

If P^ a_ s  s' were known ∀ a ∈𝒜, ∀ s,  s' ∈𝒮, finding V_π(·) would be equivalent to solving the system of linear equations (<ref>). Indeed, if one could afford the complexity of evaluating V_π ( · ) for all π∈Π_0, the optimal policy π^∗ is the one that minimizes the value function for all states. However, the large
(possibly infinite)  number of policies in practice discourages such an approach. An alternative is to employ the so-termed policy iteration algorithm <cit.> outlined next. Define first the state-action value function, also called Q-function for policy π 

    Q_π( s,  a) := 𝔼[  1^⊤ c( s,  a )  ] + γ∑_ s' P^ a_ s  s' V_π( s').

This function captures the expected immediate cost of starting from state s, taking the first action to be a, and subsequently following policy π to take future actions onwards. 
The only difference between the value function in (<ref>) and that of Q-function in (<ref>) is that the former takes the first action according to policy π, while the latter starts with a as the first action, which may not necessarily be taken when adhering to π. Having defined the Q-function, we are ready to present the policy iteration algorithm, in which every iteration i entails the following two steps:
	
Policy Evaluation. Find V_π^i (·) for the current policy π^i by solving the system of linear equations in (<ref>).
	
Policy Improvement. Update the current policy greedily as
	
    π^i+1 ( s) = min_α∈𝒜 Q_π^i ( s, α).

	
To perform policy evaluation, we rely on knowledge of  P^π^i( s)_ s  s'. However, this is impractical in our setup that involves dynamic evolution of file requests, and unknown caching policies for the leaf nodes. This calls for approaches that target directly the optimal policy π^∗, without knowing P^ a_ s  s',  ∀ a, s,  s'. One such approach is Q-learning <cit.>. 

In the ensuing section, we first introduce a Q-learning based adaptive caching scheme, which is subsequently generalized in Section <ref> by invoking a DQN. 
	


 §.§ Q-learning based Adaptive Caching

The Q-learning algorithm finds the optimal policy π^∗ by estimating Q_π^∗(·,·) `on-the-fly.' It turns out that π^∗ is the greedy policy over the optimal  Q-function <cit.>, that is 	

    π^∗ ( s) = min_α∈𝒜  Q_π^∗ ( s, α ),   ∀ s ∈𝒮

where Q_π^∗ is estimated using Bellman's equation for the Q-function. This is possible because the V-function is linked with the Q-function under π^∗ through (see <cit.> for details)

    V_π^∗ ( s) =  min_α∈𝒜  Q_π^∗ ( s, α ),   ∀ s.

Substituting (<ref>) into (<ref>), Bellman's equation for  the Q-function under π^∗ is expressed as 

    Q_π^∗ ( s,  a) = 𝔼[  1^⊤ c( s, a)  ] +γ∑_ s' P^ a_ s  s'min_α  Q_π^∗ ( s', α )

which plays a key role in many RL algorithms. Examples include Q-learning <cit.>, and SARSA <cit.>, where one relies on (<ref>) to update estimates of the Q-function in a stochastic manner. 
In particular, the Q-learning algorithm follows an exploration-exploitation procedure to take some action a in a given state s. Specifically, it chooses the action minimizing the current estimate of Q_π^∗ (·,·) denoted by Q̂_τ (·,·), with probability (w.p.) 1-ϵ_τ, or, it takes a random action a∈𝒜 otherwise; that is,

    a={[ α∈𝒜min  Q̂_τ ( s,α ),          w.p.  1- ϵ_τ;       random    a ∈𝒜,             w.p.  ϵ_τ ]..

After taking action a, moving to some new state s', and incurring cost c, the Q-learning algorithm adopts the following loss function for the state-action pair ( s, a) 

    ℒ( s,  a) =  1/2(  1^⊤ c( s,  a) + γmin_α∈𝒜 Q̂_τ ( s' ,α ) - Q̂_τ (  s ,  a) )^2.

The estimated Q-function for a single state-action pair is subsequently updated, by following a gradient descent step to minimize the loss  in (<ref>), which yields the update

    Q̂_τ+1 ( s,  a)  = Q̂_τ ( s,  a )  - β∂ℒ( s,  a )/∂Q̂_τ ( s,  a )

where β>0 is some step size. Upon evaluating the gradient and merging terms, the update in (<ref>) boils down to 

    Q̂_τ+1 ( s,  a ) =(1 -β) Q̂_τ ( s,  a ) +β[  1^⊤ c (  s,  a ) +γmin_α∈𝒜Q̂_τ ( s' ,α)  ].
	

		
Three remarks are worth making at this point.

As far as the fast-timescale caching strategy of leaf nodes is concerned, multiple choices are possible, including e.g., LRU, LFU, FIFO, <cit.>, the multi-armed bandit scheme <cit.>, and even RL ones <cit.>.

		
	
The exploration-exploitation step for taking actions guarantees continuously visiting state-action pairs, and ensures convergence to the optimal Q-function <cit.>. Instead of the ϵ-greedy exploration-exploitation step, one can employ the upper confidence bound scheme <cit.>. Technically, any exploration-exploitation scheme should be greedy in the limit of infinite exploration (GLIE) <cit.>. An example obeying GLIE is the ϵ-greedy algorithm <cit.> with ϵ_τ = 1/τ. It converges to an optimal policy, albeit at a very slow rate. On the other hand, using a constant ϵ_τ=ϵ approaches the optimal Q^∗(·, ·) faster, but its exact convergence is not guaranteed as it is not GLIE.


Clearly, finding Q_π^∗ ( s,  a) entails estimating a function defined over state and action spaces. In several applications however, at least one of the two vector variables is either continuous or takes values from an alphabet of high cardinality. Revisiting every state-action pair in such settings is impossible, due to the so-called curse of dimensionality – a typical case in practice. To deal with it, function approximation techniques offer as a promising solution <cit.>. These aim at finding the original Q-function over all feasible state-action pairs, by judicious generalization from a few observed pairs. 
Early function approximators for RL design good hand-crafted features that can properly approximate V_π^∗(·), Q_π^∗(·,·), or, π^∗(·) <cit.>. Their applicability has only been limited to domains, where such features can be discovered, or, to state spaces that are low dimensional <cit.>.




Deep learning approaches on the other hand, have recently demonstrated remarkable potential in applications such as object detection, speech recognition, and language translation, to name a few <cit.>. This is because DNNs are capable of extracting compact low-dimensional features from high-dimensional data. Wedding DNNs with RL results in `deep RL' that can effectively deal with the curse of dimensionality, by eliminating the need of hand-crafting good features. These considerations have inspired the use of DNNs to estimate either the Q-function, value function, or, the policy <cit.>. The most remarkable success in playing AI games adopted DNNs to estimate the Q-function, what  is termed DQN in <cit.>. 

Prompted by this success, the next leverages the power of function approximation through DNNs to develop an adaptive caching scheme for the parent node. 



§ ADAPTIVE DQN-BASED CACHING
 
To find the optimal caching policy π^∗ for the parent node, the success of function approximators for RL (e.g., <cit.>), motivated us to pursue a parametric approach to estimating Q( s,   a) with a DNN (cf. (<ref>)). This DNN has as input  pairs of vectors ( s,  a), and as scalar output the corresponding estimated Q( s,  a) values. Clearly, the joint state-action space of the sought Q-function has cardinality |𝒜×𝒮| = |𝒜| |𝒮|. To reduce the search space, we shall take a parametric DQN approach <cit.> that we adapt to our setup, as elaborated next. 
		
Consider a deep feedforward NN with L fully connected layers, with input the F× 1 state vector s(τ) as in (<ref>), and F× 1 output cost vector  o (τ + 1) <cit.>. Note that input does not include the action vector a. Each hidden layer l ∈{ 2, …, L-1} comprises n_l neurons with rectified linear unit (ReLU) activation functions h(z):=max(0, z) for z ∈ℝ; see e.g., <cit.>. Neurons of the L-th output layer use a softmax nonlinearity [Softmax is a function that takes as input a vector z∈ℝ^F, and normalizes it into a probability distribution via σ( z)_f= e^ z_f/(∑_f=1^F  e^z_f), ∀ f.] to yield for the f-th entry of o, an estimated long term cost o_f that would incur, if file f is not stored at the cache.


If this cache memory can store up to M (<F) files at the parent node, the M largest entries of the DQN output o (τ + 1) are chosen by the decision module in Fig. <ref> to obtain the action vector a (τ + 1). We can think of our DQN as a `soft policy' function estimator, and o (τ + 1) as a `predicted cost' or a `soft action' vector for interval τ+1, whose `hard thresholding' yields a (τ + 1).  It will turn out that excluding a from the DQN input and picking it up at the output lowers the search space from 
|𝒜| |𝒮| to |𝒮|. 
		
To train our reduced-complexity DQN amounts to finding a set of weights collected in the vector θ that parameterizes the input-output relationship o (τ +1 ) = Q( s (τ); θ_τ). To recursively update 
θ_τ to θ_τ+1, consider two successive intervals along with corresponding states s(τ) and s(τ+1); the action  a(τ+1) taken at the beginning of interval τ+1; and, the cost c(τ+1) revealed at the end of interval τ +1. The instantaneous approximation of the optimal cost-to-go from interval τ +1 is given by c(τ+1) + γ Q( s(τ+1) ; θ_τ), where c(τ+1) is the immediate cost, 
and Q( s(τ+1) ; θ_τ) represents the predicted cost-to-go from interval τ +2 that is provided by our DQN with θ_τ, and discounted by γ. Since our DQN offers  Q ( s(τ) ; θ_τ) as the predicted cost for interval τ+1, 
the prediction error of this cost as a function of  θ_τ is given by



    δ(θ_τ )      :=  [  c(τ+1) + γ Q( s(τ+1) ; θ_τ)^target cost-to-go from interval τ+1 - Q ( s(τ) ; θ_τ) ]  
           ⊙ ( 1 -  a (τ +1 ) )



and has non-zero entries for files not stored at interval τ+1.

Using the so-termed experience E_τ+1 := [ s(τ),    a(τ+1),  c(τ+1),  s(τ + 1)], and 
the ℓ_2-norm of δ(θ_τ) as criterion 

    ℒ  (θ_τ) = δ (θ_τ ) _2^2

the sought parameter update minimizing (<ref>) is given by the stochastic gradient descent (SGD) iteration as   

    θ_τ+1 = θ_τ - β_τ. ∇ℒ (θ)  |_θ = θ_τ
   
where β_τ>0 denotes the learning rate.  
		
Since the dimensionality of θ can be much smaller than |𝒮|  |𝒜|, the DQN is efficiently trained with few experiences, and generalizes to unseen state vectors. Unfortunately,  DQN model inaccuracy can propagate in the cost prediction error in (<ref>) that can cause instability in (<ref>), which can lead to performance degradation, and even divergence <cit.>. Moreover, (<ref>) leverages solely a single most recent experience E_τ+1. These limitations will be mitigated as elaborated next. 
		

				
				
				


 §.§ Target Network and Experience Replay

NN function approximation, along with the loss (<ref>) and the update (<ref>), often result in unstable RL algorithms <cit.>. This is due to: i) correlated experiences used to update the DQN parameters θ; and, ii) the influence of any change in policy on subsequent experiences and vice versa. 
				
Possible remedies include the so-called experience replay and target network to update the DQN weights. In experience replay, the parent node stores all past experiences E_τ in ℰ:= { E_1, …,  E_τ}, and utilizes a batch of B uniformly sampled experiences from this data set, namely { E_i_τ}_i= 1^B∼ U (ℰ). By sampling and replaying previously observed experiences, experience replay can overcome the two challenges. On the other hand, to obtain decorrelated target values in (<ref>), a second NN (called target network) with structure identical to the DQN is invoked with parameter vector  θ^Tar. Interestingly, θ^Tar can be periodically replaced with θ_τ every C training iterations of the DQN, which enables the target network to smooth out fluctuations in updating the DQN <cit.>. 
				
With a randomly sampled experience E_i_τ∈ℰ, 
the prediction error with the target cost-to-go estimated using the target network (instead of the DQN) is 

    δ^Tar(θ ; E_i_τ)    :=     [ c(i_τ + 1) + γ  Q(  s(i_τ + 1); θ^Tar )- Q( s(i_τ) ;θ )] 
          ⊙ ( 1 -  a(i_τ + 1) ).

Different from (<ref>), the target values here are found through the target network with weights θ^Tar. In addition, the error in (<ref>) is found by using the most recent experience, while the experience here is randomly drawn from past experiences in ℰ. As a result, the loss function becomes

    ℒ^Tar (θ) = 𝔼δ^Tar(θ;  E ) _2^2

where the expectation is taken with respect to the uniformly sampled experience E. In practice however, only a batch of B samples is available and used to update θ_τ, so the expectation will be replaced with the sample mean. Finally, following a gradient descent step over the sampled experiences, we have 

    θ_τ+1 = θ_τ - β_τ∇ℒ^Tar(θ)|_θ = θ_τ.

Both the experience replay and the target network help stabilize the DQN updates.  Incorporating these remedies, Alg. <ref> tabulates our deep RL based adaptive caching scheme for the parent node. 


				

				


§ NUMERICAL TESTS
 

In this section, we present several numerical tests to assess the performance of our deep RL based caching schemes which  is represented in Alg. <ref>.
				
The first experiment considers a simple setup, consisting of a parent node that directly serves user file requests. A total of F = 50 files were assumed in the cloud, each having the same size, while M_0 = 5 files can be stored in the cache, amounting to 10% of the total. The file popularities were drawn randomly from [0,1], invariant across all simulated time instants, but unknown to the caching entity. A fully connected feed-forward NN of 3 layers was implemented for DQN with each layer comprising 50 hidden neurons. For simplicity, we assume that the dataset ℰ can store a number ℛ of most recent experiences, which is also known as the replay memory. It was set to ℛ = 10 in our test, along with mini-batch size B = 1 to update the target network every C=10 iterations.  In addition, hyper-parameter values γ = 0.8, learning rate β_τ = 0.01, as well as ϵ_τ = 0.4 were used throughout our numerical tests.
				
Figure <ref> shows the convergence of the DQN parameter θ_τ to that of the target network θ^Tar. Since θ^Tar is updated with θ_τ per C iteration, the error ||θ_τ - θ^Tar||_2 vanishes periodically. While the error changes just in a few iterations after the θ^Tar update, it is constant in several iterations before the next θ^Tar update, suggesting that θ_τ is fixed across those iterations. This motivates investigating the impact of C on θ_τ's convergence. Figure <ref> shows the convergence of θ_τ to θ^Tar for C = 20,  5,  3,  2. Starting with C = 20, vector θ_τ is not updated in most iterations between two consecutive updates of θ^Tar. Clearly, the smaller C is, the faster the convergence for θ_τ is achieved. Indeed, this is a direct result of having static file popularity. Based on our numerical tests, having small C values is preferable in dynamic settings too. 		

For the second experiment, a similar setup having solely the parent node, plus M_0 =5 and F = 50, was considered. Dynamic file popularities were generated with time evolutions modeled by Markov process described earlier in the paper, and again they are unknown to the caching node.  

 We first consider that the parent node is connected to N = 5 leaf nodes, and every leaf node implements a local caching policy π_n with capacity of storing M_n = 5 files. Every leaf node receives user file requests within each fast time slot, and each slow-timescale interval consists of T = 2 slots. File popularity exhibits different Markovian dynamics locally at leaf nodes. Having no access to local policies {π_n}, 
the parent node not only should learn file popularities along with their temporal evolutions, but also learn the caching policies of leaf nodes. To endow our approach with scalability to handle F ≫ 1, we advocate the following hyper Q-network implementation. Files are first split into K smaller groups of sizes F_1,  …, F_K with F_k≪ F. This yields the representation s^⊤(τ) := [ s^1^⊤(τ ) , … ,  s^K^⊤(τ ) ], where s^k ∈ℝ^F_k. By running K DQNs in parallel, every DQN-k now outputs the associated predicted costs of input files through o^k (τ) ∈ℝ^F^k. Concatenating all these outputs, one obtains the predicted output cost vector of all files as o^⊤(τ+1):= [   o^1^⊤(τ+1), … ,  o^K^⊤(τ+1)]; see Sec. <ref> for discussion on finding action a from vector o, and also Fig. <ref> for an illustration of our hyper Q-network. 

The ensuing numerical tests consider F = 1,000 files with K = 25 and {F_k = 20}, where only M_0 = 50 can be stored. To further assess the performance, we adopt a non-causal optimal policy as a benchmark, which unrealistically assumes knowledge of future requests and stores the most frequently requested files. In fact, this is the best policy that one may ideally implement. Further, practically used cache  schemes including e.g., the LRU, LFU, and FIFO <cit.> are also simulated. A difference between LRU, LFU, FIFO, and our proposed approach is that they refresh the cache whenever a request is received, while our scheme refreshes the cache only at the end of every time slot. 




By drawing 100 samples[During these samples, DRL policy is enforced to exploit its learned caching policy.] randomly from all 2,000 time intervals, the instantaneous reduced cost and the empirical cumulative distribution function (CDF) obtained over these 100 random samples for different policies are plotted in Fig. <ref> and Fig.<ref>, respectively. These plots further verify how the DRL policy performs relative to the alternatives, and in particular very close to the optimal policy.  

 LRU, LFU, and FIFO make caching decisions based on instantaneous observations, and can refresh the cache many times within each slot. Yet, our proposed policy as well as the optimal one here learns from all historical observations to cache, and refreshes the cache only once per slot. Because of this difference, the former policies outperform the latter at the very beginning of Fig. <ref>, but they do not adapt to the underlying popularity evolution and are outperformed by our learning-based approach after a number of slots. The merit of our approach is further illustrated by the CDF of the reduced cost depicted in Fig. <ref>.

In the last test, we increased the number of leaf nodes from 10 in the previous experiment to N = 1,000.  Figures <ref> and <ref> showcase that the DRL performance approaches that of the optimal policy as the number of nodes increases. This is likely because the more leaf nodes, the smoother the popularity fluctuations, and therefore the easier it becomes for DRL to learn the optimal policy. 









				


§ CONCLUSIONS


Caching highly popular contents across distributed caching entities can substantially reduce the heavy burden of content delivery in modern data networks. This paper considered a network caching setup, comprising a parent node connected to several leaf nodes to serve end user file requests. Since the leaf nodes are closer to end users, they observe file requests in a fast timescale, and could thus serve requests, either through their locally stored files or by fetching files from the parent node. Observing aggregate requests from all leaf nodes, the parent node makes caching decisions in a slower-time scale. Such a two-timescale caching task was tackled in this paper using a RL approach. An efficient caching policy leveraging deep RL was introduced, and shown capable of learning-and-adapting to dynamic evolutions of file requests, and caching policies of leaf nodes. Simulated tests corroborated its impressive performance. 
This work also opens up several directions for future research, including multi-armed bandit online learning <cit.>, and distributed deep RL using recurrent NNs <cit.> for future spatio-temporal file request prediction.

IEEEtran


