  This paper introduces a novel caching analysis that, contrary to prior work,
makes no modeling assumptions for the file request sequence. We cast the
caching problem in the framework of Online Linear Optimization (OLO), and
introduce a class of minimum regret caching policies, which minimize the losses
with respect to the best static configuration in hindsight when the request
model is unknown. These policies are very important since they are robust to
popularity deviations in the sense that they learn to adjust their caching
decisions when the popularity model changes. We first prove a novel lower bound
for the regret of any caching policy, improving existing OLO bounds for our
setting. Then we show that the Online Gradient Ascent (OGA) policy guarantees a
regret that matches the lower bound, hence it is universally optimal. Finally,
we shift our attention to a network of caches arranged to form a bipartite
graph, and show that the Bipartite Subgradient Algorithm (BSA) has no regret
