  We study an online caching problem in which requests can be served by a local
cache to avoid retrieval costs from a remote server. The cache can update its
state after a batch of requests and store an arbitrarily small fraction of each
file. We study no-regret algorithms based on Online Mirror Descent (OMD)
strategies. We show that bounds for the regret crucially depend on the
diversity of the request process, provided by the diversity ratio R/h, where R
is the size of the batch, and h is the maximum multiplicity of a request in a
given batch. We characterize the optimality of OMD caching policies w.r.t.
regret under different diversity regimes. We also prove that, when the cache
must store the entire file, rather than a fraction, OMD strategies can be
coupled with a randomized rounding scheme that preserves regret guarantees,
even when update costs cannot be neglected. We provide a formal
characterization of the rounding problem through optimal transport theory, and
moreover we propose a computationally efficient randomized rounding scheme.
