Exercises

$\mathcal{R}_T = \sum_t C^{(t)}(\mathcal{A}^{(t)}) - \min_\mathbf{Z} \sum_t C^{(t)}(\mathbf{Z})$. Extra cumulative cost vs best-hindsight placement.

$\mathcal{R}_T = o(T)$ as $T \to \infty$. E.g., $\sqrt{T}$ (adversarial), $\log T$ (stochastic). Average regret per round $\to 0$: online matches offline asymptotically.

$\mathcal{R}_T = O(\sqrt{T K \log N})$.

$\sqrt{10^4 \cdot 20 \cdot \log 100} = \sqrt{10^4 \cdot 20 \cdot 4.6} \approx \sqrt{9.2 \times 10^5} \approx 960$.

Average extra cost per round $\approx 960/10^4 = 0.096$ files/use. About 3% over MAN rate in this regime.

LRU delivers uncoded: $\sim K(1 - \mu)$ per round (if hit rate $\approx \mu$).

$\sim K(1-\mu)/(1+K\mu)$.

$\Delta_t \approx K(1-\mu) \cdot K\mu/(1+K\mu)$ per round. Constant gap → $\Theta(T)$ cumulative regret.

LRU fundamentally cannot achieve the multicasting gain. Structural, not tunable.

For finite action set of size $m$: $\eta^* = \sqrt{\log m / T}$.

Action = placement choice; with per-user MAN, up to $\binom{K}{t}$ choices per user. $m \sim \binom{K}{t}$. So $\eta \sim \sqrt{\log \binom{K}{t}/T}$.

$\log \binom{K}{t} \approx K h(t/K)$ where $h$ is binary entropy. $\eta \sim \sqrt{K/T}$.

Under Zipf-$\alpha = 0.8$: effective support size $\sim N^{0.2}$ (concentrated on popular).

KL $\propto 1/T$. For KL = 0.01: $T \sim 100 \cdot \text{effective support}$.

$N = 1000$: effective support $\sim 1000^{0.2} \approx 4$. $T \sim 400$ rounds for 1% KL. Very fast.

At round $t$, cache placed based on $\hat\pi^{(t-1)}$. Regret per round: cost with $\hat\pi$-optimal minus cost with $\pi$-optimal.

Cost is smooth in $\pi$: regret $\propto \|\hat\pi^{(t-1)} - \pi\|^2$ near optimum.

$\mathbb{E}[\|\hat\pi^{(t-1)} - \pi\|^2] = O(1/t)$.

$\sum_{t=1}^T O(1/t) = O(\log T)$. $\blacksquare$

$\sqrt{T \log K} = \sqrt{10^6 \cdot \log K} \sim \sqrt{5} \cdot 10^3 \approx 2200$ (for $K = 20$).

$\log T = \log 10^6 \approx 14$. Vastly tighter.

Strictly i.i.d. demand (rare in practice). Or piecewise-stationary where within-piece bound applies.

Anything else: worst-case bound always holds. Pessimistic for real workloads.

Demand is i.i.d. within each of $S$ pieces. Change points unknown.

Restart estimator when detected. Cost: $\log T$ per piece.

$S \cdot \log T$ from within-piece + $O(\sqrt{S T})$ from transitions. Total $O(S \log T + \sqrt{ST})$.

For $S \ll T$: near-stochastic performance. For $S = T$: degrades to adversarial.

FTPL selects from a finite set of placements; $O(|\text{space}|)$ per round is feasible.

Exponential perturbation $\boldsymbol{\xi}$ introduces randomness: rarely-chosen placements still selected occasionally, preventing getting stuck.

Standard FTPL regret $O(\sqrt{T \log |\text{space}|})$. Scales with space but logarithmically — works for huge spaces.

Standard LRU decides which files to cache locally.

On a miss: server coordinates with other users' caches; sends coded XOR combinations where possible.

Requires server to know each cache's current LRU state. Metadata-heavy; not how real CDN works. Alternative: decentralized caching + coded delivery.

Hybrid schemes studied in the literature — variable gains depending on workload. Active area.

Narrow $W$: empirical estimate has variance $\sim 1/W$. Wide $W$: drift accumulates, bias $\sim V_T \cdot W/T$.

Balance: $1/W \approx V_T W / T$ $\Rightarrow W \sim \sqrt{T/V_T}$.

$O(\sqrt{T V_T})$. Matches general dynamic-regret bound.

Cumulative sum of deviations; alarm when sum exceeds threshold. Detects abrupt shifts in demand distribution.

On alarm: restart empirical estimator. Within stable phase: log-regret applies.

Restart cost: constant per change point. If $S$ change points: total regret $O(S \log T)$. Much better than $\sqrt{T V_T}$ if changes are discrete rather than smooth drift.

Online: cache updates per round. Privacy: mask demands. Two orthogonal concerns.

Apply Wan-Caire demand masking per round. Server sees shuffled demands; updates cache based on empirical distribution of shuffled demands.

If masking is consistent: server's empirical estimate is over shuffled index space. Cache placement pattern robust under uniform permutation.

Unchanged from non-private online: $O(\sqrt{T})$. Privacy is free in the online setting too.

Admission: standard LRU (uncoordinated). Delivery: on miss, server picks best coded combinations over requesting users.

Coded delivery opportunities depend on cache overlap. LRU's random / per-user structure doesn't guarantee MAN's combinatorial overlap.

Coded gain reduced: effective $(1 + K\mu_\text{eff})$ where $\mu_\text{eff}$ is the overlap rate (not $\mu$). Typically $\mu_\text{eff} \ll \mu$.

Hybrid is $2-5\times$ better than uncoded LRU, but $5-10\times$ worse than coded MAN with proper coordinated placement.

Current bounds are worst-case. Can we tighten regret based on observed problem instance (e.g., "easy" traces)?

Online coded caching in a hierarchical network (edge + regional caches). Each level has its own online dynamics. Joint algorithm unknown.

Coded delivery favors users with overlapping demands. Users with rare requests may be systematically under-served. Fair online coded caching is open.