We are going to show that, by coupling OMD methods with opportune rounding techniques, the service-cost regret guarantees derived for the fractional setting transfer (in expectation) to the integral one. A straightforward approach is to use OMD to update a fractional state \(\mathbf {x}_t\in \mathcal {X}\)  and then randomly sample an integral state \(Z_t \in \mathcal {Z} \)  after each round of requests so that \(\mathbb {E}[Z_t] = \mathbf {x}_t\) , for all \(t\ge 1\) .
A random variable \(Z_t\)  with the above marginals indeed exists, and can be sampled in polynomial time (see, e.g., [1]}, [2]}). In particular,
Caratheodory's theorem [3]} guarantees that, for any \(x_t\) , the support of \(Z_t\)  can be limited to at most \(N\)  cache configurations; Warmuth and Kuzmin provided a practical algorithm [4]}.
