Multi-Armed Bandit

The simplest MAB algorithm for cache admission control. With probability ε, the cache explores by randomly selecting a new content item to store. With probability 1-ε, it exploits current knowledge by caching the item with the highest estimated cache hit ratio.

• Implementation: A single tunable parameter (ε) controls the exploration rate
• Typical values: ε starts at 0.1 and decays over time (ε-decay scheduling)
• Limitation: Explores uniformly at random, potentially wasting cache space on clearly unpopular items
• Use case: Baseline comparison for more sophisticated caching policies in MEC Caching environments

A deterministic algorithm that selects content based on an optimistic estimate of potential reward. UCB computes an upper confidence bound for each item's expected hit rate, combining the observed average with an exploration bonus that shrinks as more data is collected.

• Formula: Score = μ̂ + √(2 ln(t) / n), where μ̂ is the estimated reward, t is total rounds, and n is times the item was cached
• Advantage: Eliminates the need for random exploration; systematically tests uncertain items
• Variants: UCB1 for stationary popularity, Sliding-Window UCB for Content Freshness scenarios
• Application: Effective when Zipf's Law popularity distributions shift gradually over time

A Bayesian approach that maintains a probability distribution over each content item's true popularity rather than a point estimate. At each decision point, the cache samples from these posterior distributions and selects the item with the highest sampled value.

• Mechanism: Typically uses Beta-Bernoulli conjugacy—modeling cache hits as Bernoulli trials with Beta-distributed priors
• Key property: Naturally balances exploration; items with high uncertainty have wider distributions and are more likely to produce high samples
• Empirical performance: Often outperforms UCB in practice, especially with Temporal Locality patterns
• Extension: Contextual Thompson Sampling incorporates Context-Aware Caching features like device type and time of day

Extends standard MABs by incorporating side information (context) into the caching decision. Instead of learning a single best item, the algorithm learns a mapping from context vectors to optimal content selections.

• Context features: User location, time of day, device type, recent browsing history, and Mobility-Aware Caching trajectory predictions
• Linear UCB: Assumes expected reward is a linear function of context features with a learned parameter vector
• Neural Bandits: Uses a deep neural network to model complex, non-linear relationships between context and content popularity
• Integration: Pairs naturally with Sequence-Aware Recommendation systems to predict next-request probabilities conditioned on user context

Addresses the realistic constraint that a cache stores a set of items simultaneously, not just one. The action space is the power set of all content, and the reward is the aggregate Cache Hit Ratio across the entire stored collection.

• Challenge: Naive enumeration is intractable; the number of possible cache configurations grows exponentially with cache capacity
• Solution: Exploits submodularity of caching rewards—the marginal benefit of adding an item decreases as the cache fills
• Algorithm: CUCB (Combinatorial UCB) approximates the oracle solution with polynomial complexity using greedy selection on UCB scores
• Synergy: Models interactions between cached items, such as when Coded Caching creates multicast opportunities across stored content

Designed for non-stationary environments where content popularity can change arbitrarily, even adversarially. Unlike stochastic bandits that assume fixed reward distributions, EXP3 (Exponential-weight algorithm for Exploration and Exploitation) guarantees performance against any sequence of rewards.

• Mechanism: Maintains an exponential weight for each content item, updated based on observed rewards divided by selection probability (importance sampling)
• Robustness: Provides worst-case regret bounds of O(√T), making it suitable for viral content spikes and flash crowds
• Application: Ideal for Cache Warming scenarios where initial popularity estimates are unreliable or when facing Cache Eviction Policy attacks
• Hybrid approach: Often combined with change-point detection to switch between stochastic and adversarial strategies based on detected distribution shifts

The fundamental trade-off at the heart of the Multi-Armed Bandit problem. Exploitation involves choosing the best-known content to cache based on current knowledge, maximizing immediate cache hit ratio. Exploration involves testing less-requested or new content to discover potentially higher long-term value. An optimal caching strategy must balance these competing objectives to minimize regret—the difference between the reward achieved and the reward that would have been achieved by always caching the truly optimal content from the start.

A Bayesian probabilistic algorithm for action selection. Instead of maintaining a single point estimate of content popularity, Thompson Sampling models the uncertainty around each content item's reward probability as a Beta distribution. At each decision step, it samples a value from each distribution and selects the content with the highest sample. This naturally balances exploration and exploitation: items with high uncertainty have wider distributions and are occasionally sampled higher, leading to exploration. It is known for strong empirical performance and robustness in non-stationary caching environments.

A deterministic algorithm that selects content based on an optimistic estimate of its potential reward. The UCB score for each cacheable item is calculated as the empirical mean reward plus an exploration bonus proportional to the square root of (ln(t) / n), where t is the total number of decisions and n is the number of times the item was selected. This bonus shrinks as an item is chosen more often, naturally shifting the system from exploration to exploitation. The UCB1 variant is widely analyzed for its theoretical regret bounds.

An extension of the standard Multi-Armed Bandit that incorporates side information—or context—into the decision-making process. In caching, context features might include time of day, user location, device type, or network congestion level. The algorithm learns a function mapping context to expected reward, often using linear models or neural networks. This allows the cache to personalize content placement decisions, such as pre-fetching sports highlights to a cell near a stadium on game day, rather than relying solely on global popularity.

Standard bandit algorithms assume reward distributions are static. In real-world caching, content popularity is highly dynamic, exhibiting concept drift due to viral trends, breaking news, or diurnal patterns. Non-stationary bandit variants address this by using sliding windows that discard old observations or discount factors that exponentially weight recent rewards more heavily. This allows the cache to rapidly adapt to shifts in demand, forgetting obsolete content like yesterday's news while quickly latching onto emerging popular items.

The primary mathematical objective for evaluating a bandit algorithm's performance. Regret is formally defined as the cumulative difference between the reward obtained by an oracle policy that always selects the truly optimal content and the reward obtained by the learning algorithm. A well-designed caching bandit aims for sub-linear regret, meaning the average regret per time step tends to zero as time goes to infinity. This guarantees the algorithm's long-term average performance converges to that of the optimal static cache configuration.