1

A Reinforcement-Learning Approach to
Proactive Caching in Wireless Networks
Samuel O. Somuyiwa, András György and Deniz Gündüz

arXiv:1712.07084v1 [] 19 Dec 2017

Abstract
We consider a mobile user accessing contents in a dynamic environment, where new contents are
generated over time (by the user’s contacts), and remain relevant to the users for random lifetimes.
The user, equipped with a finite-capacity cache memory, randomly accesses the system, and requests
all the relevant contents at the time of access. The system incurs an energy cost associated with the
number of contents downloaded and the channel quality at that time. Assuming causal knowledge of
the channel quality, the content profile, and the user-access behavior, we model the proactive caching
problem as a Markov decision process with the goal of minimizing the long-term average energy cost.
We first prove the optimality of a threshold-based proactive caching scheme, which dynamically caches
or removes appropriate contents from the memory, prior to being requested by the user, depending on
the channel state. The optimal threshold values depend on the system state, and hence, are computationally intractable. Therefore, we propose parametric representations for the threshold values, and
use reinforcement-learning algorithms to find near-optimal parametrizations. We demonstrate through
simulations that the proposed schemes significantly outperform classical reactive downloading, and
perform very close to a genie-aided lower bound.
Index Terms
Proactive content caching, Markov decision process, reinforcement learning, policy gradient
methods, wireless networks.

I. I NTRODUCTION
Content delivery networks (CDNs), such as Amazon Web Service (AWS) and Akamai, replicate contents from a local repository at servers that are geographically closer to users; specifically,
at Internet exchange points or Internet service providers. This approach significantly improves
utilization of the Internet “backbone” capacity, thereby reducing latency and improving reliability
[3]. However, today a large proportion of high-rate contents, e.g., videos, are delivered to users
The authors are with the Department of Electrical and Electronic Engineering, Imperial College London, UK. Email:
{samuel.somuyiwa12, a.gyorgy, d.gunduz}@imperial.ac.uk.
Parts of this work were presented at the Int’l Symp. on Modeling and Optim. in Mobile, Ad Hoc, and Wireless Nets. (WiOpt),
and at the 2nd Content Caching and Delivery in Wireless Nets. Workshop (CCDWN), Paris, France, May 2017 [1], [2].

2

through cellular/wireless networks, which may introduce bottlenecks. Researchers have recently
proposed proactive caching of contents at the edge of the wireless network, that is, at the
micro/macro base stations (BS) and/or even directly at user equipments (UEs) as a method to
extend the idea of CDN all the way to the wireless network edge. Proactive caching is particularly
appropriate for prerecorded contents, for example, YouTube videos or user generated contents in
online social networks (OSNs), and is based on the assumption that the system knows/predicts
in advance which contents are likely to be requested by the users.
In [4]–[6] proactive caching of contents at wireless access points is considered to reduce
congestion in back-haul links. Caching at macro and micro BSs is modeled as a stochastic
optimization problem in [7], with the objective of minimizing the average transmission power
and delay in an heterogeneous wireless network. Proactive caching of contents directly at user
devices has also been studied. Downlink energy efficiency of proactive caching is addressed in
[8] and [9], which study the problem in the offline setting, that is, user demands and channel
conditions are known in advance. Offline proactive caching is also studied in [10] where, video
bit-rate adaptation is used to improve the video streaming performance. Both offline and online
proactive caching is considered in [11] to improve the effective throughput (hit-rate) given random
user requests and a limited cache capacity. However, these works do not take into account the
time-varying nature of contents, particularly in the context of OSNs, where content generation
varies with time (and can also be bursty [12]), and the popularity of each content is nonstationary, such that content popularity typically diminishes soon after the content is generated
[13]. For example, the average lifetime, that is, the period of time a content remains popular is
approximately 2 hours for a video posted on Facebook , and 18 minutes for a video tweeted
on Twitter [14]. Instead, most caching schemes in the literature make caching decisions based
on a static content-popularity profile and a fixed content library, which results in performance
degradation. For example, it is shown in [15] that service delay increases, and cache-hit ratio
decreases, when caching decisions for social media contents are done without taking the time
variations in popularity into consideration. Time variations in the wireless channel quality and
traffic conditions, together with variations in the lifetime and popularity of contents, require that
proactive caching must incorporate an intelligent content placement and cache update mechanism.
In this paper, we consider proactive content caching into a mobile UE in the framework of
an OSN, such that new contents (messages, videos, pictures), posted by the user’s connections,
become available over time. Each content has a lifetime, that is, the period of time it remains
relevant to the user. Contents are delivered to the user via wireless links, causing the serving

3

BS to incur a transmission energy cost1 . This energy cost depends on the amount of content
downloaded as well as the channel and network conditions, which typically vary over time due
to traffic, user mobility, pathloss, as well as large scale fading effects.
In reactive content delivery, which is the conventional method employed in wireless networks
today, every time the user accesses the OSN through an application software (app) on his
mobile device, all the contents that have not yet expired, that is, those that are still relevant, are
downloaded to the UE. The energy cost of reactive delivery depends on the channel conditions at
the time of user access and the number of contents downloaded. Alternatively, proactive caching
allows downloading contents to the UE before the user accesses the OSN to request these
contents. Downloaded contents are stored in the cache, and are retrieved and delivered to the
application layer, i.e., to the app, whenever the user accesses the OSN. Therefore, contents can be
downloaded under more favorable channel conditions, leading to reduced energy consumption.
On the other hand, proactive caching may push contents that will not be requested by the user
within their lifetimes, creating unnecessary energy consumption. Moreover, the limited cache
capacity at the UE limits the amount of contents that can be proactively cached, or may require
replacing already downloaded contents, increasing the cost. Hence, we aim to answer the question
of which contents, and at what time, should be pushed to the cache.
We consider a slotted time model, in which a random number of relevant contents are generated
with random lifetimes at each time slot. For simplicity, we assume that all contents have equal
size, which is without loss of generality if we assume that larger contents are split into smaller
chunks of equal size e.g., video segments in DASH. We model both the channel quality and the
user behavior as stochastic processes. The user randomly accesses the contents in her OSN feed
in order to view/consume all the relevant contents at the time of access. We will initially assume
that the statistics of the underlying stochastic processes are known, but we will later propose
reinforcement-learning algorithms that can learn and adapt to an unknown environment.
Our contributions are summarized as follows.
•

We formulate the problem as an infinite-horizon average-cost Markov decision process
(MDP) [16], with the objective of minimizing the long term average energy consumption.

•

To overcome the technical difficulty due to the continuous distribution of the channel quality,
we introduce a new MDP model, referred to as an MDP with side information (MDP-SI).
We show the optimality of a threshold-based proactive caching policy, which downloads

1

Although we focus on the energy cost at the BS in this work, the proposed framework can be easily adapted to any other

network resource, e.g., bandwidth, delay or the energy cost at the UE.

4

contents into, and removes contents from, the cache depending on the remaining lifetime of
the contents and the relative value of the current channel state with respect to a threshold.
•

Since the optimal threshold values depend on the system state, the prohibitively large size
of the state space makes it practically infeasible to compute and store them. Hence, we
introduce two low-complexity parametric policy representations that are able to approximate
the optimal performance. The first policy, called Longest lifetime In–Shortest lifetime Out
(LISO), assigns a single threshold to each pair of contents with the longest remaining
lifetime outside the cache, and content with the shortest remaining lifetime inside the cache,
independent of the system state. The second policy, called linear function approximation
(LFA), represents the threshold values for every possible pair of remaining lifetimes as a
linear function of the system state.

•

We use reinforcement learning techniques obtain the optimal threshold values for the proposed caching schemes. In particular, we apply two policy gradient schemes, he finite
difference method (FDM) and the likelihood-ratio method (LRM) [17].

•

To evaluate the performances of the proposed caching schemes, we describe two lower
bounds: one assuming unlimited cache capacity, and another assuming non-causal knowledge of the user-access times. Through numerical simulations, we demonstrate that the
proposed schemes perform close to the latter lower bound when the cache capacity is
small, and to the former for larger cache capacities, and significantly outperform reactive
caching. We also show that the LFA policy outperforms LISO to some considerable extent,
and that the PG with LRM finds a better solution than with FDM.

•

Finally, we introduce memory into the stochastic processes for content (lifetime) generation
and channel quality, and show via simulations that the performance gain of the LFA policy
over LISO is more significant in such scenarios.
II. S YSTEM M ODEL

We consider a slotted (discrete time) communication system. At the beginning of each time
slot t, a random number of contents, denoted by Mt , are generated. We denote the set of newly
generated contents by Nt , where |Nt | = Mt . Each content is generated with a lifetime, after
which it becomes irrelevant. In particular, if, at the beginning of time slot t, content i is generated
with lifetime Kt,i , it can be consumed in time slots t, t + 1, . . . , t + Kt,i − 1, and otherwise will
be removed from the system after time slot t + Kt,i − 1. We denote the set of contents that are
already in the cache at the beginning of time slot t by It , and the set of relevant contents not

5

Varying channel cost
• Mobility
• Traffic
• Environment, etc.

OSN

C

User Equipment
(UE)

SERVER

Base stations
Time 1

Content 1
Content 2

Lifetime K1,1
Lifetime K1,2

Content M1

Lifetime K1,M1

U1 = 0/1

Channel Cost = C1
OSN Application

Time t

Content 1
Content 2

Cache Memory
Capacity  B

Lifetime Kt,1
Lifetime Kt,2

Ut = 0/1
Content Mt

Lifetime Kt,Mt

Newsfeed

Channel Cost = Ct

UE

Fig. 1: Illustration of the system architecture. The OSN server has a list of relevant contents
with random lifetimes for the user. Contents can be pushed to the UE cache memory before
being requested by the user, to take advantage of favorable channel conditions.
inside the cache, including the Mt newly generated contents, by Ot . The system architecture is
illustrated in Fig. 1.
At each time slot, the user either accesses the system and consumes all the relevant contents,
or does not access the system. The user access behavior is represented by the binary random
variable Ut ; that is, Ut = 1 if the user accesses the system, and Ut = 0 otherwise. When the user
accesses the system, all the contents that are not already in the cache, Ot , are downloaded, and
moved, together with all the contents in the cache, that is, It , to the app. If Ut = 0, the cache
manager (CM) has the option of downloading some contents to, and removing others from the
(1)

cache. We denote the set of contents that are downloaded at time slot t by At ⊂ Ot , and the
(2)

set of contents that are discarded from the cache by At ⊂ It . To unify notation, if Ut = 1 we
(1)

(2)

set At = Ot and At = It .2
Throughout the paper, since all the contents have the same size, it will be convenient to
represent each content by its remaining lifetime. Following this representation, all sets of contents,
(1)

that is, Nt , Ot , It , At

(2)

and At , are multisets of remaining lifetimes (positive integers, with

the set of all positive integer tuples denoted by N∗ ). To simplify the treatment, when it does
not cause confusion, we will only talk about sets instead of multisets, or subsets instead of
2

We do not allow the CM to download and remove the same content in the same time slot, which is obviously suboptimal.

6

sub-multisets of multisets, and operations, such as union, should be treated in a multiset manner.
For a multiset Z with positive elements, we let Z − 1 = {z > 0 : z + 1 ∈ Z} denote the multiset
obtained by reducing each element of Z by 1 and removing the elements which become 0. With
these definitions in mind, if Ut = 0, the system evolves according to the following equations:
(1)
(2) 
It+1 = It ∪ At \ At − 1,


(1)
(2)
(1) 
Ot+1 = Ot ∪ At \ At − 1 ∪ Nt+1 ,
and according to the following equations if Ut = 1:
It+1 = ∅ and

Ot+1 = Nt+1 .

(2)

We assume that the user is equipped with a cache of capacity B, that is, |It | ≤ B, ∀t. Hence,
(1)

(2)

the CM’s actions, At = (At , At ), are constrained by the available cache capacity, and any
valid action leads to a new state with |It | ≤ B.
Downloading a content at time t has a cost Ct that depends on the channel state. The total
(1)

instantaneous cost at time t is µt = |At | · Ct , while the average cost after T time slots is given
P
by JT = T1 Tt=1 µt . The goal is to minimize the long-term expected average cost defined as
"
#
T
1X
ρ , lim sup E [JT ] = lim sup E
µt .
T t=1
T →∞
T →∞
1) User Access Model: We assume that the user access sequence {Ut } is an arrival process

with i.i.d. inter-arrival times {Dn }, where Dn denotes a positive-integer-valued random variable.
Throughout, we will make one of the two assumptions regarding Dn : (i) Bounded inter-arrival
times, i.e., Dn is bounded as 0 ≤ Dn ≤ Dmax , where Dmax ∈ Z+ . (ii) Geometric inter-arrival
times: Dn has a geometric distribution with parameter pa ; hence {Ut } is an i.i.d. process with
P [Ut = 1] = pa (in turn, Dmax = ∞ in this case). The latter assumption, which is standard in
the literature, is also known as the independent reference model (IRM) (see, e.g., [4], [7]).
2) Content Generation Model: We assume that {Mt } is an i.i.d. sequence with generic random
variable M, and is upper-bounded by Mmax ∈ Z+ . We further assume that the lifetimes are also
i.i.d. with generic random variable K, and upper-bounded by Kmax ∈ Z+ .
3) Channel Model: We assume that the energy cost for downloading a content Ct > 0 is a
continuous random variable with cumulative distribution function (cdf) FC (c), and it is assumed
to be i.i.d. across time, and bounded by Cmax ∈ R+ . Aside from simplifying our system model,
the i.i.d. assumption here is appropriate for micro BS deployments, where the user switches
micro BSs across time slots. We assume that the micro BSs can operate at the same time without

7

any interference because they operate at a relatively low transmit power. We also assume zero
download delay [7], [11], implying that the duration of a time slot is long enough to download
the required contents. Hence, the channel is approximately ergodic within a time slot, and is
only subject to large-scale fading effects.
In the rest of the paper, we assume that the sequences {Ct }, {Dn }, {Mt },{Kt,i } are independent of each other. In the following section, we assume that the CM is aware of the above
stochastic model governing the system behavior.
III. O PTIMAL

SOLUTION

In this section we derive a general result concerning the structure of the optimal cache
management policy. First we define a special class of MDPs, which we call MDPs with side
information (MDP-SI), and show that our cache management problem is an instance of this
class. Then, we derive a general structural result for optimal policies in MDP-SI under some
assumptions, and show that they apply to our problem.
A. Standard MDP model
A finite-state finite-action MDP is characterized by a quadruple (S, A, P, µ), where S and A,
the state and action spaces, respectively, are finite sets, P : S × A × S → [0, 1] is a probability
kernel (we will write P (s′|s, a) instead of P (s, a, s′)), and µ : S ×A → [0, µmax ]∪{∞} is a cost
function with some µmax > 0. The purpose of introducing an infinite cost is to allow a different
action set in every state without complicating the notation too much: for every state s ∈ S, the
set As = {a ∈ A : µ(s, a) < ∞} denotes the set of feasible actions (otherwise the agent suffers
infinite cost), and we assume that As 6= ∅, ∀s ∈ S. In an MDP, an agent controls a Markov
chain and pays some cost over time. Assuming the agent selects an action a ∈ As at state s ∈ S,
the system evolves to state s′ with probability P (s′|s, a) , P [St+1 = s′ | St = s, At = a], where
P
′
s′ ∈S P (s |s, a) = 1, ∀s ∈ S, a ∈ A. The cost of taking action a in state s is µ(s, a). Denoting

the state of the system at time t by St and the agent’s action by At , the agent’s goal is to
h P
i
minimize the infinite horizon average cost ρ = limT →∞ E T1 Tt=1 µ(St , At ) .
A deterministic policy is a mapping π : S → A, which selects a single action for each state; and

let Π denote the set of all deterministic policies. For any policy π let P π : S × S → [0, 1] denote
the transition kernel induced by π, that is P π (s′ |s) = P (s′|s, π(s)). Assuming the Markov chain

8

defined by P π is irreducible and aperiodic for all π, let ρπ denote the infinite-horizon average
cost ρ when At = π(St ), that is,
#
T
1X
µ(St , π(St )) .
ρ = lim E
T →∞
T t=1
"

π

(3)

Due to our assumption on P π , the initial state S0 does not matter, and the limit in (3) exits
thanks to the non-negativity assumption on µ(s, a). It is well-known (see, e.g., [18]) that there
exists a deterministic policy π ∗ that minimizes the infinite-horizon average cost over all, possibly
non-stationary and non-deterministic causal control policies, that is,
π ∗ = argmin ρπ ,

(4)

π

where the minimum is taken over all admissible (causal) control strategies of the agent, in which
At may depend on the history Ht , (S1 , . . . , St , A1 , . . . , At−1 ) and some randomization.
B. MDPs with side information (MDP-SI)
In the MDP-SI model, we extend the classical MDPs such that there is an i.i.d. sequence of
side information Zt ∈ Z for some Z ⊂ R, which is available to the agent before selecting At ,
and effects the cost µ, that is, µ : S × A × Z → [0, µmax ] ∪ {∞}. Then the decision of the agent
may depend on Ht , the randomization, and (Z1 , . . . , Zt ). This setup can be easily modeled in
the MDP framework by changing the state space to S × Z, but if Z is not finite, the analysis
of the resulting MDP is significantly more complicated. Before delving into the analysis of the
MDP-SI model, first we show that our problem can be cast as an MDP-SI problem.
At the end of time slot t, the state of the contents can be described by the sets It and Ot , while
the state of the user can be described by the time elapsed since the last access, denoted by Et .
To be precise, we assume that the user accesses the OSN at time t = 0 (i.e., we set U0 = 1); then
Et is defined as Et , min{t − n : t > 0, 0 ≤ n ≤ t, Un = 1}. We denote by S ⊂ N∗ × N∗ × N
the set of all possible combinations of Ot , It , and Et . Under the IRM user-access model (i.e.,
when the user-access process is i.i.d. and the inter-access times are geometrically distributed),
the memoryless property of the geometric distribution implies that the exact value of Et does not
affect the future given that Et > 0, and hence, the state of the user can be redefined as I{Et >0} ,
the indicator function of the event {Et > 0}.3 Unless otherwise stated explicitly, we will use
I{Et } in place of Et for the IRM model; accordingly, S will denote the possible combinations
3

For an event E , I{E} = 1 if E holds, and 0 otherwise.

9

of Ot , It , and I{Et >0} . Note that under both of our user-access models (i.e., IRM or bounded
inter-access times–Dmax < ∞), the state space S is finite. Furthermore, let As denote the set
of download/discard actions available to the CM in a state s ∈ S. The action of the agent in
(1)

(2)

time slot t is the pair At = (At , At ), and Ct can be regarded as the i.i.d. side information
Zt . Indeed, the decision of the CM (i.e., the agent) depends on Ct , as the cost of action At is
(1)

µ(St , At , Ct ) = Ct · |At |.
The state s ∈ S of the system evolves according to (1) and (2), where the user access sequence
depends on E, which evolves independently according to the distribution of Dn . The channel
cost Ct , which is the side information, also evolves independently, with cdf FC in every time
slot t. These independence assumptions ensure that the resulting model is indeed an MDP-SI.
C. Structure of the optimal policy in MDP-SI
In this section we derive the structure of the optimal policy for a general MDP-SI under certain
conditions. To begin with, assume we have an MDP-SI characterized by (S, ASI , PSI , µSI , Z, FZ ),
where FZ is the cdf of the real-valued side information, S and ASI are countable, and Z ⊂ R.
Let A denote the set of Borel-measurable4 functions {g : Z → ASI }, and consider the MDP
(S, A, P, µ) where
P (s′ |s, g) = E [PSI (s′ |s, g(Z))] ,

(5)

µ(s, g) = E [µSI (s, g(Z), Z)] ,

(6)

and

where the expectations are taken over Fz . It is easy to see that any deterministic policy πSI :
S × Z → ASI for the MDP-SI can be turned into a deterministic policy for the corresponding
MDP using
π(s) = πSI (s, ·) ∈ A,

(7)

and vice versa, and that the expected average cost of the two models are the same for the
corresponding policies. Therefore, it is enough to consider the MDP (S, A, P, µ). If Z is finite,
the new MDP is finite, and we can use standard results (see, e.g., [18]) to analyze the structure
of the optimal policy: Assume that the MDP is finite, P π is irreducible and aperiodic for any
deterministic policy π ∈ Π, and let S1 , A1 , S2 , A2 , . . . denote the state-action sequence obtained
4

While throughout the paper we assume the existence of the necessary probability spaces and the measurability of functions

as required, here we emphasize Borel measurability since it will be used explicitly in some proofs.

10

by following policy π. Then ρπ in (3) exists, and the differential value function for any state
s ∈ S is defined as

"

∞
X
π
V (s) = E
(µ(St , At ) − ρπ ) S1 = s
t=1

Furthermore, the optimal policy π ∗ in (4) satisfies
(
∗

V π (s) = min µ(s, a) − ρπ∗ +
a∈A

X

s′ ∈S

#

.

∗

(8)

)

P (s′|s, a)V π (s′ ) ,

(9)

and a = π ∗ (s) minimizes the right hand side. While these results make the analysis easy,
unfortunately they do not directly apply to our case, where the state space S can be countably
infinite and, due to the fact that Z is not finite, the action set A is infinite (and uncountable).
Luckily, it is possible to extend the above results, specifically (9) to the MDP (S, A, P, µ) when
Z is an interval (this will be done in the proof of Lemma 1). Using the definition of the MDP
in (5)–(7) and the expression for the optimal value function in (9), we can prove the following
property of the optimal policy π ∗ (s, ·) of an MDP-SI (the proof is given in Appendix A).
Lemma 1. Consider the countable-state, finite-action MDP-SI problem (S, ASI , PSI , µSI , Z, FZ ).
Suppose that P π is ergodic for any policy π in the corresponding MDP (S, A, P, µ) and that Z
is an interval. Then (9) holds for (S, A, P, µ). Furthermore, if µSI (s, aSI , z) is a linear function
of z for any s ∈ S, aSI ∈ ASI , then the optimal policy π ∗ (s, ·) is a piecewise constant function
for any s ∈ S.
Combining the MDP-SI formulation of Section III-B with Lemma 1, we obtain that for any
state s ∈ S, the optimal decision is a piecewise constant function of the channel cost Ct with
values taken from As . Also note that the technical condition in the lemma that P π is ergodic
is easily satisfied in our cache management problem due to the user access model: The fact
that the user access clears all contents from both inside and outside of the cache at least once
in every Dmax time slots or after a geometric waiting time ensures that any state visited with
positive probability is positive recurrent. Thus, to achieve ergodicity, it is sufficient to guarantee
that the process is aperiodic. This readily follows from the IRM model, and also holds for the
bounded inter-access time model under mild assumptions (e.g., if the user can access the OSN
in two consecutive time slots with positive probability).
D. Structure of the optimal cache management policy
Here we will describe the structure of the optimal policy for the proactive caching problem.

11

We start with the technical definition of partial ordering for multisets, which will be useful to
characterize the effect of good actions: For two multisets M1 and M2 with nonnegative elements,
we write M1 ≤ M2 , if, either (i) they are of equal size and there is a one-to-one mapping between
the elements of M1 and M2 such that the element from M1 is never larger than the corresponding
element from M2 ; or (ii) if they are of different size, but the same relationship holds after adding
zeros to the smaller set to equalize their sizes.
Now consider two states of the MDP describing the caching problem: s = (O, I, E) ∈ S
and s′ = (O′ , I ′ , E ′ ) ∈ S. We will say that s is better than s′ , and write s  s′ , if E = E ′ ,
the remaining lifetimes of all the contents are the same, that is, O ∪ I = O′ ∪ I ′ , and O ≤ O′
and I ≥ I ′ . Intuitively, s  s′ means that the same contents are available for pre-caching in
s and s′ , but in state s “better” contents have already been downloaded to the cache (i.e., the
contents in the cache remain relevant longer while the ones outside expire earlier). The next
lemma formalizes this statement:
Lemma 2. Assume the conditions of Lemma 1 hold. Let s, s′ ∈ S and suppose that s  s′ .
∗

∗

Then, V π (s) ≤ V π (s′ ), that is, the future average download cost starting form s is not larger
than the cost starting from s′ .
Proof. It is easy to see that if any action a′ is performed in s′ , it is always possible to find another
action â in s such that the cost of â is no more than that of a′ , that is, µ(s′ , a′ ) ≥ µ(s, â), and
the resulting new states satisfy ŝ2  s′2 , where s′2 and ŝ2 denote the next state for the chains
starting from s′ and s, respectively, assuming the content generation process and the user access
process are the same (e.g., if a′ downloads a content from outside the cache of s′ , â should
download the content with the largest remaining lifetime from outside the cache of s, unless all
the contents in the cache of s have larger lifetimes, in which case â should not do anything).
Now consider three coupled realizations of the MDP: {(St′ , A′t )} starts from S1′ = s′ , and follows
the optimal policy π ∗ ; the second realization {(Ŝt , Ât )} starts from Ŝ1 = s, and selects Ât such
that Ŝt  St′ and µ(Ŝt , Ât ) ≤ µ(St′ , A′t ) for all t; finally, {(St , At )} starts form S1 = s, and
follows the optimal policy π ∗ . Then, using the optimality of At and π ∗ , by (9) (which holds by

12

Lemma 1), we have
V

π∗

(s) = V

π∗

π∗

(S1 ) ≤ µ(Ŝ1 , Â1 ) − ρ

≤ µ(Ŝ1 , Â1 ) − ρπ
..
.
≤E

"

∞
X

∗

h ∗
i
π
+ E V (Ŝ2 )
h
h ∗
ii
∗
+ E µ(Ŝ2 , Â2 ) − ρπ + E V π (Ŝ3 )
π∗

(µ(Ŝt , Ât ) − ρ ) Sˆ1 = s

t=1

#

.

Furthermore, by the coupling of the realizations,
#
" ∞
#
" ∞
X
X
∗
∗
∗
E
(µ(St′ , A′t ) − ρπ ) S1′ = s′ = V π (s′ ) .
(µ(Ŝt , Ât ) − ρπ ) Sˆ1 = s ≤ E
t=1

Putting everything together, we obtain V

t=1

π∗

∗

(s) ≤ V π (s′ ).

Next we express the actions in As more intuitively by defining a simple action, which we
also denote as a, to simplify the notation.
Definition 1 (Simple Action). For any l ∈ I and L ∈ O (recall that l and L denote the
remaining lifetime of some contents), a simple action a = (l|L) is defined as follows: If Et > 0,
a = (l|L) replaces a cache content with remaining lifetime l with a relevant content outside the
cache with remaining lifetime L, by removing the former content from the cache and downloading
and caching the latter; i.e., it “swaps” the two contents. If Et = 0, a = (l|L) downloads the
content with remaining lifetime L, and moves both contents to the app.
In this definition, l = 0 means that the content with lifetime L is downloaded without any
corresponding removal of a content from the cache. Similarly, L = 0 means that no content is
downloaded while a content with remaining lifetime l is removed from the cache. Note that,
with the optimal policy, the latter (i.e., L = 0) can only happen if either l = 0 (i.e., an expired
content is removed from the cache), or when Et = 0 and more contents are moved from the
cache to the app than those downloaded from the OSN server to the app. At every time slot
t, because of the cache capacity constraint, the CM can only take up to B simple actions if
Et > 0. Therefore, at such instances, any action of an optimal policy can be expressed as at
most B consecutive simple actions, and an action At = ({L1 , . . . , LB′ }, {l1, . . . , lB′ }),5 for some
0 ≤ b ≤ B can be written as a sequence of simple actions {(l1 |L1 ) · · · (lb |Lb )}.
5

(1)

(2)

If either |O| or |I| is less than B ′ , we simply zero-pad the set so that |At | = |At | = B ′ .

13

Now for a state s = (O, I, E) with E > 0, assume that l1 ≤ · · · ≤ lB are the contents in I,
and let L1 ≥ · · · ≥ LB denote the B largest elements of O. To find the optimal action, first we
determine the best simple action. Let s∗1 denote the next state if action (l1 , L1 ) is taken, and let
s′1 denote the state after a different simple action (l′ |L′ ). Since l1 is the smallest element of the
cache and L1 is the largest element outside the cache, assuming the same content generation,
∗

it is immediate that s∗1  s′1 . Then, by Lemma 2, V π (s∗1 ) ≥ V (π ∗ )(s′1 ). Therefore, by (9),
(l1 , L1 ) is the best simple action. Considering larger actions composed of b simple actions for
b ≥ 2, it follows similarly that the optimal such action is Ab = {(l1 |L1 ) · · · (lb |Lb )} (note that
the energy cost associated with such an action is b C, where C is the channel cost of a single
download). To find the optimal action, it remains to compare the actions Ab for different values
of b ∈ {0, . . . , B}. Denoting the next state following action Ab by sb , the relative action value
of Ab for channel cost C is given by
 ∗

∗
Qπ∗ (s, Ab , C) = b C − ρπ + E V π (sb ) ,

∗

and, by (9), the optimal action is the one minimizing Qπ∗ (s, Ab , C) for a given C: that is, Ab

with b∗ = argminb Qπ∗ (s, Ab , C). Notice that, as a function of C, Qπ∗ (s, Ab , C) is a linear
 ∗

′
function with slope b and intersecting the y axis at E V π (sb ) . Since, obviously, sb  sb for

 ∗
′
∗
∗
any b > b′ , w have V π (sb ) ≤ V π (sb ), and so E V π (sb ) is non-increasing in b. Therefore,
there exist thresholds 0 = TB+1 ≤ TB ≤ · · · ≤ T1 ≤ Cmax , such that the optimal action is Ab
′

if the channel cost belongs to the interval [Tb+1 , Tb ]. Since Ab ⊂ Ab for b > b′ , this also means
that the simple action ab = (lb , Lb ) is performed whenever C ≤ Tb (note that Tb = 0 means that
action ab is never performed because C > 0).
This implies the following theorem.
Theorem 1. Consider a state s = (O, I, E) ∈ S of the MDP-SI for the proactive caching
problem, and let C denote the channel cost. Let l1 ≤ · · · ≤ lB denote the contents in I,
and L1 ≥ · · · ≥ LB denote the B largest elements of O. Then, there exist threshold values
0 ≤ TB ≤ TB−1 ≤ · · · ≤ T1 ≤ Cmax , such that there is an optimal caching policy that performs
the simple actions ai = (li |Li ) for all i such that C ≤ Ti if E > 0 (i.e., the user does not access
the OSN).
The thresholds for different simple actions depend on what other simple actions are available,
and on the contents of the cache. This is because if we cache a content, its value depends on
the likelihood of the content to be removed from the cache before being consumed by the user,
and this likelihood is affected by the lifetime of the other contents in the cache.

14

Having shown that the optimal policy exhibits a threshold behavior, one still has to evaluate
the optimal threshold values in order to characterize the optimal policy and the corresponding
optimal performance. Therefore, the number of threshold values to be determined is in the order
of the cardinality of the state space S, which is extremely large. This makes it computationally
infeasible to compute the optimal threshold values. Interestingly, this is not the case if we have a
sufficiently large cache capacity, e.g., B ≥ Mmax Kmax , in which case we never remove a content
from the cache unless it is consumed, or has expired; we will refer to this as the case of unlimited
cache capacity. Therefore, we can decide about each content individually, and independently of
the cache contents. This gives rise to the following corollary:
Corollary 1. Assume that the cache capacity is unlimited, that is, B = ∞. Then, for any state
s = (O, I, E) with E > 0, there exist thresholds 0 ≤ T1,E ≤ · · · ≤ TKmax ,E ≤ Cmax (recall that
Kmax is the maximum lifetime), which depend only on E, such that a content with remaining
lifetime L ∈ O is downloaded if C ≤ TL,E .
Since the decision to download any content is independent of the others, the problem can
be modeled as a finite-horizon MDP-SI, where the horizon equals the remaining lifetime L
with maximum horizon Kmax . Thus, we can apply dynamic programming [16] to determine
the optimal downloading thresholds recursively: Let VL,E denote the future download cost
associated with a content with lifetime L from a state with time E elapsed since the past
user access following an optimal policy. Since there is no need to proactively download a
content with lifetime 1, T1,E = 0 for all E > 0, and so V1,E = 0 for any E > 0. Let
pE = P [ Ut+1 = 1| Et = E] = P [D1 ≤ E + 1] − P [D1 ≤ E] denote the probability of user
access in the next time slot.6 Assuming that optimal decisions will be made for lifetimes up to
L − 1 for all E, a decision with threshold T for lifetime L > 1 and elapsed time E has a future
download cost

VL,E,T = P [C ≤ T ] E [ C| C ≤ T ] + P [C > T ] pE E[C] + (1 − pE )VL−1,E+1 .

(10)

Minimizing the above expression in T by setting its derivative to zero, we obtain that the optimal
threshold is TL,E = pE E [C] + (1 − pE )VL−1,E+1, which is exactly the expected future download
cost if the content is not downloaded in the current state. Noticing that TL,E equals the last term
in parentheses in (10), we obtain the following result.

6

Recall that Dn denotes the nth inter-access time and the Dn are i.i.d.

15

Corollary 2. Assume that the cache capacity is unlimited (i.e., Bmax = ∞). Then the optimal
thresholds TL,E can be computed recursively as follows: T1,E = 0 for all E > 0. For L ≥ 1,
given TL,E for all E, the optimal thresholds for L + 1 can be obtained for all E as


TL+1,E = pE E [C] + (1 − pE ) P [C ≤ TL,E+1 ] E [ C| C ≤ TL,E+1 ] + P [C > TL,E+1 ] TL,E+1 .
In case of the IRM user access model, the same thresholds can be used in all states, and the
expression for the thresholds simplifies to T1 = 0 and for L ≥ 1,


TL+1 = pa E [C] + (1 − pa ) P [C ≤ TL ] E [ C| C ≤ TL ] + P [C > TL ] TL .

(11)

The optimal performance with an infinite cache capacity will be studied as a lower bound on
the optimal performance for a practical finite cache capacity system in Section VI.
IV. L OW-C OMPLEXITY C ACHING S CHEMES

VIA

P OLICY A PPROXIMATION

In the previous section we determined the structure of the optimal caching policy. According
to Theorem 1, the optimal policy has a threshold structure, and the threshold for each simple
action depends in general on the remaining lifetimes of all the contents inside and outside the
cache, as well as on the time elapsed since the last user access. This implies that the optimal
policy may employ completely different threshold values for the same simple action at different
system states, and the optimal policy belongs to the family of policies parametrized by these
thresholds. The dimension of this policy set is |S̄|, where S̄ ⊂ S denotes the set of system states
2
where the user does not access the OSN. Moreover, we have approximately Kmax
/2 potential

simple actions, each of which can have a different threshold value at each state. However, for
any reasonable (finite) cache size B, this is huge; and hence, it is infeasible to compute an

max
different
optimal policy (e.g., if Mmax ≥ B, then just the cache content I can take B+K
Kmax

values, which is already prohibitively large for even moderate values of B or Kmax ). To resolve

this problem, we use policy approximation techniques, and approximate the policy space using
some simple parametrized form.
From now on we adopt the IRM user access model, which alleviates the need to consider
the time Et elapsed since the last user access, readily reducing the state space. In the rest
of this section, we introduce two low-dimensional approximations to the policy space, which
allow us to run optimization algorithms (policy search algorithms, described in Section V) to
find a policy with good performance, and hence, give rise to computationally feasible caching
schemes. These schemes are not based on a priori known statistics of the system and optimize
the policy parameters based on observations (these observations can be collected either from the

16

real system or via simulations through a generative model). Therefore, in principle, the methods
can be used in a learning context, where an agent, who does not known the statistics of the
environment a priori, can learn from its actions to update its policy in order to adapt to the
unknown environment in a reinforcement learning fashion.
A. The longest lifetime in–shortest lifetime out (LISO) policy
The longest lifetime in–shortest lifetime out (LISO) policy is a suboptimal threshold-based
proactive caching policy with a simplified structure, such that it has a single threshold value for
each simple action (corresponding to the content pair consisting of the content with the shortest
remaining lifetime inside the cache and the one with the longest remaining lifetime outside the
cache), independent of the system state. For every such pair, if the channel cost is below the
threshold value, the two contents are “swapped,” and no action is taken otherwise. In this case,
the policy is directly parametrized by the threshold values. That is,
T (l|L) = θ(l, L),
where θ(l, L) ∈ [0, Cmax ], for all pairs a = (l|L), l, L ∈ {0, . . . , Kmax }. Thus, the set of policies
parametrized this way is of dimension (Kmax + 1)2 , which is feasible. We can further reduce
the dimension by explicitly forbidding all simple actions (l|L) with l ≥ L (i.e., setting the
corresponding θ(l, L) to zero), since an optimal policy will not replace a cached content with a
content that has a shorter remaining lifetime. Hence, for such simple actions, we have T (l|L) = 0.
We also note that the optimal policy has a monotonic structure; that is, T (l|L1 ) ≤ T (l|L2 ) if
L1 < L2 and T (l1 |L) ≥ T (l2 |L) if l1 < l2 . These observations can be used to limit the search
space for the threshold vector, speeding up the policy search methods.
B. Linear function approximation (LFA) policy
Next, we propose an improved policy representation (an extension of LISO), which takes
into account the remaining lifetimes of the contents in the cache memory when determining the
threshold values; this information can be useful in estimating the likelihood that a downloaded
content will be removed from the cache before it expires or is consumed. However, to keep
the computational complexity feasible, we employ linear function approximation (LFA) [19]. To
characterize the state of the cache, we define features of the cache-state based on the number
of contents in the cache with a particular remaining lifetime (this is meaningful thanks to the
homogeneity of the size of the contents). More precisely, we define the cache-state features by

17

a frequency vector Φt = [φt (0), φt(1), . . . , φt (Kmax )], where φt (i) is the ratio of the number of
contents with lifetime i in the cache at time t, that is,
P
I{l=i}
, for i = 0, 1, · · · , Kmax ,
φt (i) , l∈I
B

where l = 0 denotes the empty locations as before. Clearly, 0 ≤ φ(i) ≤ 1, and

(12)
PKmax
i=0

φ(i) = 1.

The threshold value for each simple action a(l|L) for l < L, l, L ∈ {0, . . . , Kmax }, is then
defined as a linear function of the frequency vector Φ as
T (l|L) =

K
max
X

φ(i)θi (l, L) = Φ⊤ θ(l, L),

(13)

i=0

where θi (l, L) ∈ R for l < L, and θi (l, L) = 0 otherwise. The resulting scheme defines a
Kmax (Kmax + 1)2 /2-dimensional policy space.
Remark 1. We note that the LISO policy described in Section IV-A, which is directly parametrized
by the threshold values for each simple action ignoring other contents in the cache, is a special
case of the LFA policy with parameters θi (l, L) = θ(l, L) for all i.
In the next section, we describe two policy search algorithms that we use to optimize the
parameters of the proposed approximate caching schemes.
V. P OLICY S EARCH M ETHODS
Optimizing parametric policies for MDPs has been extensively studied in reinforcement learning [19]. In this paper, we are going to employ policy gradient (PG) methods to optimize
the parameters of our LISO and LFA policies. This section, based on [17], introduces these
algorithms. PG methods are model-free reinforcement learning algorithms to find an optimal
policy in an MDP by running gradient descent over the policy space to minimize the expected
average cost ρπθ , where πθ denotes the policy defined by the parameter vector θ. That is, in
every step of the policy gradient algorithm, the actual parameter θ j is updated using the gradient
∇θ ρπθ of ρπθ according to θ as
θ j+1 = θ j − λ∇θ ρπθj ,

(14)

for some positive step size λ.
Since the gradient ∇θ ρπθj is not known in closed form in most cases, the gradient (and the
average cost of the policy) has to be estimated through sample averages over independent, finite
trajectories of the system obtained via Monte Carlo rollouts. This, in turn, implies that, instead of
(14) we will use a random estimate of the gradient; so, in practice, (14) will become a stochastic

18

gradient descent algorithm. To curtail the effect of noise that is introduced due to the randomness,
P
we obtain θ j+1 as the average of m policy updates, i.e., θ j+1 = m1 m
i=1 θ j+1,i , where each θ j+1,i
is obtained using (14) with an independent estimate of the gradient. The estimation procedure
usually requires two steps:
1) Policy evaluation: The average cost of a sample trajectory τθ = (S1 , C1 , A1 ), . . . , (ST , CT , AT ),
obtained by following a given policy πθ with parameter vector θ, is evaluated as
T
1X
J(τθ ) =
µ(St , At , Ct ).
T t=1

(15)

2) Policy exploration: New sample trajectories are generated. Exploration is implemented either
directly on the actions At , or on the parameter vector θ, by introducing an exploration noise
either at every time step of the trajectory, or at the beginning of the trajectory.
In what follows, we review two practical policy gradient algorithms that employ different
estimation techniques.
A. Finite difference method (FDM)
In FDM, we estimate the gradient by generating sample trajectories following the policy πθj
given by the parameter vector θ j (determining the threshold values T (l|L)) and by new policies
obtained by applying small perturbations ∆θ [i] to the parameter vector θ j . Generating trajectory
[i]

τ [i] for θ j and τ∆ for θ j + ∆θ [i] , the change in the cost is estimated by
[i]

∆J [i] = J(τ∆ ) − J(τ [i] ),
which is also approximately equal to (∇θ ρπθ )⊤ ∆θ [i] . Thus, generating N independent trajectories
τ [i] , for i = 1, . . . , N, the gradient can be estimated from ∆J πθ = [∆J [1] , · · · , ∆J [N ] ]⊤ and
∆Θ = [∆θ [1] , · · · , ∆θ [N ] ]⊤ by linear regression as follows:
∇θ ρπθ ≈ ∆Θ⊤ ∆Θ

−1

∆Θ⊤ ∆J πθ .

(16)

In the FDM method, policy exploration is implemented on the parameter vector at the beginning of each trajectory. Perturbations can be chosen randomly; in this paper the perturbations
for each coordinate of θ j are drawn from a uniform distribution within the range [−r, r], for
some relatively small positive real number r.

19

B. Likelihood-ratio method (LRM)
In this section we describe another PG strategy, called LRM. To simplify the treatment,
throughout we use the MDP notation and include the cost C in the state S.
In LRM, exploration is implemented directly on the actions, and in every time step of each
trajectory by using a randomized policy πθ (A|S) ∈ [0, 1], which takes action A in state S with
probability π(A|S). Since A may consist of several simple actions, for each simple action (l|L)
where l < L, l, L ∈ {0, 1, . . . , Kmax }, we define a randomized policy πθ ((l|L)|S) as a sigmoid
function with negative slope parameter:
πθ ((l|L)|S) =

1
1+

e−η(T (l|L)−C)

,

where η > 0 is the slope factor. Given cache contents l1 ≤ · · · ≤ lB , and the B contents outside
the cache with the largest remaining lifetimes L1 ≥ . . . ≥ LB , we repeatedly try to perform the
action ai , (li |Li ) with probability πθ (ai |S) for i = 1, . . . , B, until the first failure. This implies
′

that for B ′ ≤ B, the probability of performing action AB′ = {a1 , . . . , aB } is
′

B′

B ′ +1

πθ (A |S) = 1 − πθ (a

|S)

B
Y

πθ (ai |S),

i=1

where πθ (aB+1 |S) is defined to be zero for all states S.

Let Pθ denote the density of an infinite trajectory τ = (S1 , A1 ), (S2 , A2 ), . . . obtained by
P
following policy πθ , and let J(τ ) = lim supT →∞ T1 Tt=1 µ(St , At ). Then, under general, nonrestrictive assumptions, we have

πθ

∇θ ρ

=

Z

∇θ Pθ (τ )Jπθ (τ )dτ .

Using the “likelihood-ratio” identity ∇θ log Pθ (τ ) = ∇θ Pθ (τ )/Pθ (τ ), the above gradient can be
expressed as
πθ

∇θ ρ

=

Z

Pθ (τ )∇θ log Pθ (τ )J(τ )dτ = E[∇θ log Pθ (τ )J(τ )] .

(17)

The expectation with respect to the trajectory distribution Pθ is approximated by sample
averages over sampled trajectories τ [i] of finite length. Interestingly, as it is well known in the
reinforcement learning literature [17], this can be done without the knowledge of the density Pθ .
Q
Indeed, since Pθ (τ ) = P (S1 ) Tt=1 P (St+1 |St , At )πθ (At |St ), taking logarithm and differentiating
according to θ gives

∇θ log Pθ (τ ) =

T
X
t=1

∇θ log πθ (At |St ),

(18)

20

which can be computed directly from τ using the parametric form of πθ . Thus, the expectation in
(17) can be estimated by averaging over a number of independent trajectories sampled following
policy πθ . To minimize the variance of the estimate, we introduce a baseline vector b, as in the
REINFORCE algorithm [20], and estimate the hth coordinate of the gradient by
" T
#
X
∇θh ρπθ = E
∇θh log πθ (At |St )(J(τ ) − bh ) .
t=1

The baseline does not introduce any bias in the gradient estimate: using (18), the likelihood-ratio
R
R
identity, and the fact that ∇θh Pθ (τ )dτ = 0 since Pθ (τ )dτ = 1, we get
" T
#
Z
Z
X
E
∇θh log πθ (At |St )bh = bh ∇θh Pθ (τ )dτ = bh ∇θh Pθ (τ )dτ = 0.
t=1

As in the REINFORCE algorithm, we select the baseline bh for ∇θh ρπθ by minimizing the
variance of the estimate of the hth coordinate, which yields


2
PT
E
J(τ )
t=1 ∇θh log πθ (At |St , Ct )

.
bh =
2 
PT
E
t=1 ∇θh log πθ (At |St , Ct )

Numerical results obtained with the proposed low-complexity proactive caching algorithms

optimized with both of the PG methods will be presented in Section VII. Next, we present
lower bounds on the performance to evaluate the performance loss introduced by the proposed
low-complexity caching policies.
VI. L OWER B OUNDS
We derive two lower bounds on the average cost, which become tight under different settings
of the problem. The lower bounds are based on some relaxation of the system constraints (the
first one assume infinite cache capacity while the second one a non-causal knowledge of the
user access times). For both cases, in the next subsections, we derive the optimal caching policy,
and the lower bounds can be computed by estimating the performance of the optimal policy (in
the corresponding relaxed system) using Monte Carlo rollouts; that is, averaging J(τθ ) in (15)
for several independent trajectories τθ obtained by following the optimal policy πθ .
A. Lower bound with unlimited cache capacity (LB-UC)
The first lower bound, called LB-UC, is obtained by considering an unlimited cache capacity
(i.e., B = ∞). In this case, as explained in detail in Section III-D, there is no need to remove

21

and replace any content inside the cache. The decision to download and store a content can be
taken individually, and independently of the existing contents in the cache. The structure of the
optimal threshold values for LB-UC follows from Corollary 2 and (11).
B. Lower bound with non-causal knowledge of the user access times (LB-NCK)
The second lower bound, called LB-NCK, is obtained by assuming non-causal knowledge of
the user access times. Since the user access times are known in advance, contents that will expire
before the user accesses the OSN will never be downloaded and can be automatically removed
(2)

from the system. Therefore, there is no need to remove any content from the cache, thus At = ∅
for all t. All the remaining contents must be downloaded by the next user access, which means
that there is no difference among contents, and so whenever the CM decides to download a
content, it does not matter which one it is. As such, without loss of generality, we assume that
the CM may pre-cache only the first B contents that become available after a user access. This
means that there will always be space in the cache for these contents to be downloaded. Then
it follows that the optimal policy only needs to decide when to download these contents, and
this decision is independent of the contents in O and I, and may only depend on the time till
the next user access and the current channel cost.
To determine the optimal policy, similarly to Corollary 2 and (11), the problem can be modeled
as a finite-horizon MDP-SI, where the time horizon is the time G until the next user access.
Denoting by VGN CK the average energy cost of downloading a content following the optimal
policy; we have V0N CK = E [C], since the content must be downloaded when G = 0. For any


N CK
G ≥ 1, the dynamic programming equations imply that VGN CK = E min{C, VG−1
} . Therefore,
the optimal decision is to download a content if the channel cost C is smaller than the future
N CK
download cost VG−1
. Thus, the optimal policy again has a threshold structure.

Corollary 3. Assuming that the user access times are known non-causally, there exist thresholds
CK
≥ 07 such that, for any O, I, if there are G time slots left until
Cmax ≥ T1N CK ≥ · · · ≥ TDNmax

the next user access, a content with remaining lifetime L ∈ O (with L ≥ G) is downloaded for
G ≥ 0 (i.e., when Ut = 0) if |I| < B and Ct ≤ TG . The thresholds are given by the recursion


N CK
T1N CK = E [C] and for G ≥ 2, TGN CK = E min{C, TG−1
} .
7

Note that Dmax is the bound on the length of the user access interval, and can be infinite under the IRM model.

22

VII. N UMERICAL R ESULTS
Here we present numerical simulations implementing the proposed caching schemes with both
FDM and LRM. We compare their performances with the two lower bounds in Section VI, as
well as with reactive and random caching schemes. In reactive caching, all the relevant contents
are downloaded at the time of user access. This scheme does not utilize the storage available at
the UE. In random caching, when Ut = 0, each relevant content in O is downloaded randomly,
with a constant probability pr > 0 whenever |It | < B, and pr = 0 whenever |It | = B. This
scheme does not utilize any intelligence in making caching decisions. Note that random caching
is equivalent to reactive caching when pr = 0. While random caching exploits the cache memory,
we will see that this does not improve the performance since it is done in a random manner.
A. System Setup
The number of contents generated at each time slot, Mt , is drawn uniformly at random from
the set {1, . . . , Mmax }, while the lifetime Kt,i of individual contents i ∈ {1, . . . , Mt } at the time
of generation is drawn from the set {5, 10, . . . , Kmax }, where Kmax is a multiple of 5. We assume
that the user accesses the system independently at each time slot, with probability pa = 0.25.
We obtain Ct using Shannon’s capacity formula, R = W log2 (1 + Psignal /Pnoise ), where R
is a deterministic transmission rate, W is the channel bandwidth, Pnoise is the noise power and
Psignal is the signal power. Using system parameters consistent with the Long Term Evolution
(LTE) network model [21], on a dB scale, the noise power is given by
Pnoise = 10 log10 (kT ) + 10 log10 W + NF,

(19)

where kT = −174 dBm/Hz is the noise power spectral density, and NF = 5 dB is a typical
noise figure. The signal power is given by
Psignal = Ct + GT X + GRX − P L(d),

(20)

where GT X and GRX are the transmit and receive antenna gains, respectively, and P L(d) is the
pathloss, which is a function of the distance d between the user and the serving BS. We adopt
the 3GPP channel model [22], and consider an urban micro (UMi) system, with an hexagonal
cell layout in the non-line-of-sight (NLOS) scenario, in which case the pathloss is given as
P L(d) = 36.7 log10 (d) + 22.7 + 26 log 10(fc ) + Xσ ,

(21)

where fc = 2.5GHz is the center frequency, and Xσ is the shadow fading parameter drawn
from a zero-mean log-normal distribution with standard deviation σ = 4 dB. The distance d is

23

in meters (m), and we assume that the user location, described by d, is uniformly distributed in
time and across BSs.
We assume that a micro BS has a radius of 250m, and the shortest possible distance of a user
from a serving BS is 50m. Therefore, the user distance d from the serving BS in any time slot is
drawn from a uniform distribution d ∼ U(50, 250). We assume that the user is only served by a
single BS in every time slot. Although we focus on a single user, the savings in energy will scale
proportionally with the number of users. We use the values GT X = 17 dBi and GRX = 0 dBi. To
compute the noise power, we assume a fixed (average) bandwidth of 10 MHz in every time slot,
and for the Shannon capacity formula, we assume a spectral efficiency of R/W = 2 bps/Hz
for each content item. The required power will be linearly scaled with the number of contents
downloaded at each time slot, assuming they are independently encoded and transmitted over
orthogonal subbands. For all the simulations, we set the initial state as O0 = I0 = ∅ and E0 = 0.
The cache capacity B is measured in number of contents.
For the FDM algorithm, we select the perturbation parameters ∆θ from a uniform distribution
∆θ ∼ U(−0.08, 0.08). For each iteration, a policy update is performed after 100 trajectories, with
the duration of a trajectory set as 300 time slots. On the other hand, for the LRM algorithm, for
the randomized policy to closely resemble the actual deterministic policy, the logistic function
defining the policy should be as close to a unit step function as possible. Hence, we choose the
slope η = 10. A policy update is performed after only 20 trajectories, with the duration of a
trajectory set as 300 time slots.
For the initial parameter vector θ 0 of the LISO policy, we use the threshold values obtained
as the solution of the unlimited cache capacity problem as the initial θ(0, L) values for all L.
For LFA, we use the components of the same parameter vector (obtained from the unlimited
cache capacity problem) as the initial components θi (l, L), ∀l, L, and i ∈ {0, 1, . . . , Kmax }. This
initialization allows our algorithm to start from a relatively good initial point, thus improving
the convergence speed over a random initial parameter vector. For all the algorithms, an average
of 5 policy updates is taken as the policy update of any iteration. In each simulation setup, we
select an appropriate step size by adjusting the step size at different runs until the best result is
obtained. Finally, to test the performance of any algorithm and policy, we use a test data of 100
trajectories, each consisting of 5000 time slots.

24

18

14
13

16

12
14
11
12

10

10

9
8

8
7
6

4
10

6
5
20

30

40

50

(a)

60

70

80

90

100

10

15

20

25

(b)

Fig. 2: Average energy cost vs. cache capacity with Kmax = 15, Mmax = 8, pa = 0.25.
B. Performance Evaluation
To simplify the presentation, we first compare the LISO policy implemented with the FDM
algorithm, with the benchmarks in Fig. 2a, where we plot the average energy cost with respect
to the cache capacity. We use pr = 0.45 for the random caching scheme. We observe that
the random caching scheme has the highest average energy cost, which increases with pr . The
average energy cost of the reactive scheme is independent of the cache capacity as it does not
utilize the caches. While the reactive scheme only downloads contents that are actually requested,
the random scheme downloads many contents that will eventually expire before being requested
by the user. Moreover, since the random scheme downloads the contents randomly, it has, on
average, the same cost as the reactive scheme for the contents that are eventually consumed by
the user. As expected, the performance of LB-UC, which assumes unlimited cache capacity, does
not depend on the cache capacity; while that of LB-NCK, which assumes non-causal knowledge
of the user access times, decreases with the cache capacity. This is because more contents that
will remain relevant by the user access time can be downloaded at favorable channel conditions
through proactive caching. The performance of LB-NCK is equal to that of the reactive scheme
when there is no cache memory available at the user, i.e., B = 0, since proactive caching is not
possible in that case.
The proposed LISO scheme significantly improves the system’s performance with respect to
the reactive caching scheme for any nonzero cache capacity. For a cache capacity of B = 30, the

30

25

LISO policy achieves an approximately 60% reduction in energy consumption over the reactive
scheme. For relatively large cache capacities, i.e., B ≥ 40, the performance of the LISO scheme
almost meets that of LB-UC. This is because more contents that will not expire by the time
the user accesses the system can be stored in the cache, and almost no contents need to be
removed from the cache. This means that a cache capacity of B = 40 is sufficient to provide all
the potential gains from proactive caching in this setup. Interestingly, 40 is roughly the average
number of relevant contents at any point in time. Moreover, in the low cache capacity regime,
the performance of the LISO scheme is very close to that of LB-NCK. This is because when
the cache capacity is small, the system is relatively conservative in proactively caching contents,
and so downloaded contents seldom expire or are swapped out of the cache before the next user
access. Thus, the gain from knowing the user access times is more limited. We conclude from
Fig. 2a that any improvement in the performance of the LISO policy, when implemented with
the FDM algorithm, can only occur at the low cache capacity regime (B ≤ 30).
In Fig. 2b we plot the performance of both caching schemes, LISO and LFA, implemented
with both FDM and LRM algorithms, in the low cache capacity regime. We observe that both the
policy representation using LFA and using the LRM algorithm for gradient estimation improve
the performance compared to LISO with FDM. At very low cache capacities, i.e., B < 10, the
performances of LISO with FDM, and LFA with FDM or LRM all closely follow the LB-NCK
bound. Meanwhile, the LFA policy has a performance gain of up to 4.4% over the LISO policy
when both schemes are implemented with the FDM algorithm. This performance gain can be
attributed to the fact that the LFA policy considers the remaining lifetimes of all the contents
inside the cache when making a cache decision, which is ignored by the LISO policy. When
the LFA policy is implemented with LRM, it achieves a performance gain of up to 5.6% over
the LISO policy implemented with FDM. LRM also improves the performance of LISO policy
with up to 4.2% with respect to LISO with FDM. We can attribute the better performance of
LRM to its improved exploration strategy.
In Fig. 3 we plot the average energy cost against the maximum lifetime of contents, Kmax .
We observe that the energy cost increases with the lifetime of contents. This is expected: when
the contents remain relevant longer, more contents will be consumed by the user at the time
of access. We observe that the improved performance of LFA policy over LISO extends to the
Kmax values considered here. The performance gain of LISO with LRM with respect to LISO
with FDM increases with Kmax , which means that a better exploration strategy becomes more
important as Kmax increases, since the cache space becomes relatively more limited per relevant

26

9

8.5

8

7.5

7

6.5

6

5.5
5

7.5

10

12.5

15

17.5

20

Fig. 3: Average energy cost vs. maximum lifetime of contents for B = 20, 30, when Mmax =
8, pa = 0.25.
7.8

7.7

7.6

7.5

7.4

7.3

7.2
100

200

300

400

500

600

700

800

900

1000 1100 1200

Fig. 4: The evolution of the FDM and the LRM algorithms with respect to the number of rollouts.

content.
In Fig. 4 we compare the convergence rates of the two PG methods. We observe that, initially,
LRM performs worse than FDM. However, after about 250 trajectories, LRM starts to converge
at a faster rate, saturating to the optimal performance after approximately 1000 trajectories. The
LRM is known to have better theoretical convergence guarantees, and its superiority over FDM
has been observed in other applications as well [23].
In the next section, we go beyond our modeling assumptions to show that the performance

27

gain of the LFA policy with respect to LISO can be more significant if the underlying stochastic
processes have memory.
C. Stochastic Process with Memory
Here we introduce temporal memory in the generation of content lifetimes and the user
location, i.e., distance from the serving BS, which is a more realistic model for a mobile user
served by micro BSs. For the lifetime process, we assume that the content generator has two
states, called “short” and “long” content states, respectively. When it is in the short content state,
all the generated contents have an initial lifetime of 5, whereas in the long content state, all the
contents are generated with a lifetime of 15. The content generator transitions from one state
to the other randomly. We assume that, if it is in the short content state, it remains there with
probability p1 , while if it is in the long content state it remains in taht state with probability p2 .
We assume that at each time slot the user moves either towards or away from the serving BS.
The distance from the serving base station at time slot t+1 is dt+1 = dt ±σ, where σ is a positive
constant, which describes how fast the user is moving. The corresponding user location model
is a Markov process where the state transition probabilities are given by P (dt+1 = dt + σ) = pu
and P (dt+1 = dt − σ) = 1 − pu , ∀t. We further impose that the distance d is bounded between
50m and 250m, so only a single direction of movement is possible on the boundary points.
Note that the threshold structure of the optimal policy detailed in Section III no longer holds
in this model with memory; however, we can still evaluate the performances of the proposed
caching schemes which exploit a threshold structure. Figure 5 shows the performances of the LFA
and LISO policies, both implemented with the LRM algorithm, for values of p1 ∈ {0.1, 0.5, 0.9}
and varying p2 from 0.1 to 0.9. Note that, higher p1 and p2 values mean that the system is more
likely to stay in the same state, and continue to generate contents with the same lifetime. The
results are obtained for a cache capacity of B = 20. For the user location process, we set σ = 5
and pu = 0.5. We observe that the average energy cost increases with increasing p2 and with
decreasing p1 , as they both lead to the generation of more contents with lifetime 15. We observe
similar trends for the gain of LFA with respect to LISO; that is, the improvement with respect
to LISO also increases with p2 and decreases with p1 .
We observe that the performance gain of LFA over LISO is more significant than the i.i.d.
scenario. For similar system parameters in the i.i.d case; that is, for a cache capacity of B =
20, and assuming that the LRM algorithm is used, LFA policy has a performance gain of
approximately 0.75% over LISO. However, when memory is introduced to the content lifetime

28

11.5

11

10.5

10

9.5

9
0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Fig. 5: Average energy cost vs. transition probabilities p1 and p2 for both LFA and LISO policies,
with cache capacity B = 20, σ = 5 and pu = 0.5.
and user location processes, the LFA policy can have a performance gain of approximately 2%.
We note that, when the lifetime generation has memory, existing contents in the system provide
more information about the future states; and hence, the LFA policy, which takes into account
the remaining lifetimes of all the contents, provides larger gains.
VIII. C ONCLUSIONS
We have considered the proactive caching problem in wireless networks with the aim of
minimizing the long term average energy cost of delivering contents to the UE over a timevarying wireless link under random user accesses to the system, random content lifetime, and
a time-varying library size. We have first showed the optimality of a threshold-based policy,
which pushes contents to the cache (or may remove contents from the cache if it is full)
depending on the relative value of the channel state with respect to preset threshold values
that depend on the time elapsed since last user access and the remaining lifetimes of all the
relevant contents in the system. Since this leads to a prohibitively large set of parameters to
be optimized, we have proposed two suboptimal caching schemes, LISO and LFA, that are
based on low-complexity parametrization of the system states and policy search techniques from
reinforcement learning. We have further introduced two lower bounds on the performance, and
through numerical simulations, we have showed that the two low-complexity proactive caching
schemes perform close to optimal, with LFA performing better than LISO in general. Proactive

29

caching under nonlinear cost functions, and in multi-user scenarios are currently being considered
as interesting future extensions of this paper.
A PPENDIX A
P ROOF

OF

L EMMA 1

We start the proof by showing that our MDP (S, A, P, µ) satisfies (9) when P π is ergodic for
any policy π and Z is an interval. First note that Theorems 5.1–5.3 of [24] imply that for any
MDP with a countable state space and whose action space is a compact metric space, there exists
an optimal deterministic policy satisfying (9). Clearly, under our assumptions, S is countable.
Furthermore, since g ∈ A is Borel-measurable, any limit point (under pointwise convergence)
of a sequence of functions from A also belongs to A (i.e., it is a Borel-measurable function).
On the other hand, the representation of policies with functions from A is not unique, since
any two functions g, g ′ ∈ A such that P [g(Z) = g ′ (Z)] = 1 represent the same policy (up to a
zero-measure event), and this causes problems in establishing the compactness of A.
To alleviate this problem, for any g ∈ A, define the equivalence class Gg = {g ′ ∈ G :
P [g(Z) = g ′(Z)] = 1}, and let G = {Gg : g ∈ A} denote the family of these classes. For any
G ∈ G, let fG ∈ G be a selected element of G. Then, since each function fG can take values
only in the finite set ASI , with a slight modification to the proof of Theorem 3 in [25], one can
show that the set Ā = {fG : G ∈ G} is a compact metric space for the metric P [g(Z) 6= g ′(Z)].
Consequently, the new MDP (S, Ā, P, µ) satisfies (9). Furthermore, it is easy to see that
the new MDP is equivalent to the original one in the sense that their trajectories equal with
probability one if any action g ∈ A in the original MDP is replaced with fGg in the new one.
Therefore, the original MDP also satisfies (9).
Using (5) and (6), we can express (9) as
( "
∗

∗

V π (s) = min E µSI (s, g(Z), Z) − ρπ +
g∈A

X

∗

P (s′|s, g(Z))V π (s′ )

s′ ∈S

such that, if g = π ∗ (s), then g minimizes (22)

#)

,

(22)

Since g is a mapping from Z, the above minimum can be realized by minimizing for each
value of the side information Z independently. Indeed, for any s, the minimum in (22) is achieved
by any g satisfying
g(z) ∈ argmin
aSI ∈ASI,s

(

∗

µSI (s, aSI , z) − ρπ +

X

s′ ∈S

∗

)

P (s′ |s, aSI )V π (s′ ) .

(23)

30

Since the right hand side of (23) is a minimum of finitely many linear functions, it follows that
g(z) can be chosen to be a piecewise constant function: a piecewise constant function over the
interval Z is defined by an interval partition Z1 , . . . , Zm of Z (for some m) and some actions
a1 , . . . , am ∈ ASI such that g(z) = ai if z ∈ Zi , i = 1, . . . , m. Converting this policy back to
the original MDP-SI problem finishes the proof.
R EFERENCES
[1] S. O. Somuyiwa, A. György, and D. Gündüz, “Energy-efficient wireless content delivery with proactive caching,” in Content
Caching and Delivery in Wireless Nets. Work., (CCDWN), Paris, France, May 2017, pp. 1–6.
[2] ——, “Improved policy representation and policy search for proactive content caching in wireless networks,” in Int’l Symp.
on Modeling and Optim. Mobile, Ad Hoc, and Wireless Nets., WiOpt 2017, Paris, France, May 2017, pp. 1–8.
[3] S. Borst, V. Gupta, and A. Walid, “Distributed caching algorithms for content distribution networks,” in INFOCOM, 2010
Proceedings IEEE, March 2010, pp. 1–9.
[4] N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and G. Caire, “Femtocaching: Wireless video content delivery
through distributed caching helpers,” in IEEE INFOCOM, Mar. 2012, pp. 1107–1115.
[5] E. Bastug, M. Bennis, and M. Debbah, “Living on the edge: The role of proactive caching in 5G wireless networks,” IEEE
Comms. Mag., vol. 52, no. 8, pp. 82–89, Aug. 2014.
[6] P. Blasco and D. Gunduz, “Learning-based optimization of cache content in a small cell base station,” in IEEE Int’l Conf.
Comms. (ICC), Jun. 2014, pp. 1897–1903.
[7] B. Zhou, Y. Cui, and M. Tao, “Stochastic content-centric multicast scheduling for cache-enabled heterogeneous cellular
networks,” IEEE Transactions on Wireless Communications, vol. 15, no. 9, pp. 6284–6297, Sept 2016.
[8] A. C. Güngör and D. Gündüz, “Proactive wireless caching at mobile user devices for energy efficiency,” in IEEE Intl
Symp. on Wireless Comm. Systems (ISWCS), Aug. 2015, pp. 186–190.
[9] M. Gregori, J. Gomez-Vilardebo, J. Matamoros, and D. Gunduz, “Wireless content caching for small cell and D2D
networks,” IEEE Jrnl. on Selected Areas in Comms., vol. 34, no. 5, pp. 1222–1234, May 2016.
[10] W. Bao and S. Valentin, “Bitrate adaptation for mobile video streaming based on buffer and channel state,” in IEEE Int’l
Conf. on Comms. (ICC), Jun. 2015, pp. 3076–3081.
[11] W. Chen and H. Vincent, “Joint pushing and caching with a finite receiver buffer: Optimal policies and throughput
analysis,” 2016. [Online]. Available: http://arxiv.org/abs/1602.04500
[12] C. Qi, Z. Zhao, R. Li, and H. Zhang, “Characterizing and modeling social mobile data traffic in cellular networks,” in
2016 IEEE 83rd Vehicular Technology Conference (VTC Spring), May 2016, pp. 1–5.
[13] A. Lobzhanidze, W. Zeng, P. Gentry, and A. Taylor, “Mainstream media vs. social media for trending topic prediction an experimental study,” in IEEE Consumer Comms. and Netw. Conf., Jan 2013, pp. 729–732.
[14] D. Wells. (2016) The lifespan of a social media post. [Online]. Available: http://bit.ly/29Byg3Q
[15] N. Zhang, J. Guan, C. Xu, and H. Zhang, “A dynamic social content caching under user mobility pattern,” in Int’l Wireless
Comms. Mobile Comp. Conf., Aug 2014, pp. 1136–1141.
[16] D. P. Bertsekas, Dynamic Programming and Optimal Control. Athena Scientific, 2007.
[17] M. P. Deisenroth, G. Neumann, and J. Peters, “A survey on policy search for robotics,” Found. Trends Robot, vol. 2, pp.
1–142, Aug. 2013. [Online]. Available: http://dx.doi.org/10.1561/2300000021
[18] M. L. Puterman, Markov Decision Processes: Discrete Time Stochastic Control. John Wiley and Sons, 2005.
[19] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction.

Cambridge, MA, USA: MIT Press, 1998.

31

[20] R. J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning,” in Machine
Learning, 1992, pp. 229–256.
[21] S. Stefania, T. Issam, and B. Matthew, LTE, The UMTS Long Term Evolution: From Theory to Practice. Wiley, 2011.
[22] T36.814 V9.0.0, “Further advancements for E-UTRA physical layer aspects (release 9),” 3GPP, Mar. 2010.
[23] J. Peters and S. Schaal, “Policy gradient methods for robotics,” in Int’l Conf. Intelligent Robots and Sys. (IROS), 2006.
[24] A. Arapostathis, V. S. Borkar, E. Fernndez-Gaucherand, M. K. Ghosh, and S. I. Marcus, “Discrete-time controlled markov
processes with average cost criterion: A survey,” SIAM Journal on Control and Optim., vol. 31, no. 2, pp. 282–344, 1993.
[25] A. György and T. Linder, “On the structure of optimal entropy-constrained scalar quantizers,” IEEE Transactions on
Information Theory, vol. IT-48, no. 2, pp. 416–427, Feb. 2002.

