  We consider updating strategies for a local cache which downloads
time-sensitive files from a remote server through a bandwidth-constrained link.
The files are requested randomly from the cache by local users according to a
popularity distribution which varies over time according to a Markov chain
structure. We measure the freshness of the requested time-sensitive files
through their Age of Information (AoI). The goal is then to minimize the
average AoI of all requested files by appropriately designing the local cache's
downloading strategy. To achieve this goal, the original problem is relaxed and
cast into a Constrained Markov Decision Problem (CMDP), which we solve using a
Lagrangian approach and Linear Programming. Inspired by this solution for the
relaxed problem, we propose a practical cache updating strategy that meets all
the constraints of the original problem. Under certain assumptions, the
practical updating strategy is shown to be optimal for the original problem in
the asymptotic regime of a large number of files.
  For a finite number of files, we show the gain of our practical updating
strategy over the traditional square-root-law strategy (which is optimal for
fixed non time-varying file popularities) through numerical simulations.
