Markov Decision Process (MDP)

The complete set of distinct configurations the environment can occupy at any time step. In caching, a state encodes the current contents of the cache, pending user requests, and channel conditions. The Markov property requires that each state captures all information necessary to make an optimal decision—the future depends only on the present state, not the history of how it was reached.

• Cache example: A binary vector of length N indicating which files are stored locally
• Mobility-aware example: State includes user position, velocity vector, and signal-to-noise ratio
• Dimensionality challenge: State space grows exponentially with cache size, requiring function approximation via deep neural networks

The set of all possible decisions the agent can execute at each decision epoch. Actions transition the environment from one state to another. In proactive caching, actions determine which content to evict, prefetch, or retain. The action space may be discrete (evict file X, cache file Y) or continuous (allocate cache capacity percentages).

• Finite actions: Select one of K content items to cache
• Compound actions: Simultaneously evict multiple items and prefetch a batch
• Constraint handling: Actions must respect cache capacity limits, often enforced via masking in deep RL implementations

The state transition function P(s' | s, a) defines the probability of arriving in state s' after taking action a in state s. This captures the stochastic dynamics of the environment—user request patterns, mobility trajectories, and network fluctuations. In model-free reinforcement learning, the agent learns optimal behavior without explicitly modeling these probabilities.

• Deterministic transitions: Evicting file X always removes it from cache
• Stochastic transitions: User content requests follow an unknown probability distribution
• Model-based approaches: Learn an explicit world model to plan ahead using techniques like Dyna-Q

A scalar signal R(s, a, s') that quantifies the immediate desirability of a state transition. The reward function encodes the cache utility—the benefit of serving content from local storage versus fetching from the origin server. Well-designed rewards align agent behavior with system objectives like minimizing latency, reducing backhaul load, or maximizing cache hit ratio.

• Hit reward: +1 for serving a request from cache, 0 for a miss
• Penalty terms: Negative reward for cache churn or excessive prefetching overhead
• Multi-objective: Weighted sum of latency reduction, bandwidth savings, and energy efficiency

A parameter γ ∈ [0,1] that determines the present value of future rewards. A value close to 1 makes the agent farsighted, valuing long-term cache optimization over immediate gains. A value near 0 produces myopic behavior, optimizing only the next request. In infinite-horizon caching problems, γ ensures the cumulative return remains finite.

• Typical range: 0.9–0.99 for caching applications
• Interpretation: γ=0.95 means a reward 20 steps in the future is worth ~36% of an immediate reward
• Connection to average reward: As γ→1, the discounted objective approximates the long-run average reward per step

A mapping from states to actions—or probability distributions over actions—that defines the agent's behavior. The goal of solving an MDP is to find an optimal policy π* that maximizes expected cumulative reward. Policies can be deterministic (always cache the predicted popular content) or stochastic (sample actions to explore alternative caching strategies).

• Value-based: Derive policy implicitly by selecting actions with highest Q-value
• Policy gradient: Directly parameterize and optimize the policy using neural networks
• Actor-critic: Combine both approaches, with the critic evaluating the actor's caching decisions

The finite set of all possible situations the caching agent can encounter. In an MDP, the state must capture all information necessary to make a decision. For proactive caching, a state typically encodes:

• Current cache contents: A vector of content IDs currently stored.
• Content popularity distribution: The estimated request probability for each item.
• Network conditions: Current backhaul load or channel quality. The Markov property holds that the future depends only on the current state, not the history of how it was reached.

The set of all possible decisions the agent can make in a given state. In caching MDPs, actions are discrete and typically include:

• Fetch and cache: Retrieve a specific content item from the origin server and store it locally.
• Evict and replace: Remove a cached item to make room for a new one.
• Serve from cache: Deliver content directly without modifying state.
• Do nothing: Maintain the current cache configuration. The action space size grows combinatorially with cache capacity, making function approximation essential for practical systems.

The probability of moving from state s to state s' after taking action a, denoted as P(s' | s, a) . This model captures the stochastic nature of the environment:

• User request dynamics: The probability that a specific content item will be requested next, often modeled with Zipf's Law.
• Content popularity evolution: How the popularity distribution shifts over time due to trends or time-of-day effects.
• Network variability: Changes in backhaul capacity or latency. In model-free reinforcement learning, these probabilities are never explicitly learned; the agent learns directly from experience.

A scalar signal R(s, a) that quantifies the immediate benefit of taking action a in state s. The agent's goal is to maximize cumulative reward over time. In caching, the reward function is engineered to reflect business objectives:

• Cache hit: +1 reward for serving content locally, reflecting latency reduction.
• Cache miss: -1 penalty for fetching from the origin, representing backhaul cost.
• Energy-aware reward: A weighted function that penalizes high-power cache writes.
• Freshness bonus: Additional reward for serving content within its TTL window. The discount factor γ (gamma) determines how much future rewards are valued relative to immediate ones.

A mapping from states to actions, denoted as π(a|s) for stochastic policies or π(s) for deterministic ones. The policy is the core output of solving an MDP—it dictates exactly what to cache or evict in every situation. Key policy types include:

• Optimal policy π*: Maximizes expected cumulative reward from any starting state.
• Greedy policy: Always selects the action with the highest estimated value.
• ε-greedy policy: Selects a random action with probability ε to maintain exploration. In Deep Q-Networks, the policy is implicitly defined by selecting the action with the maximum Q-value.

The expected cumulative discounted reward starting from a state and following a policy thereafter. Two variants exist:

• State-value function V(s) : Expected return from state s under policy π.
• Action-value function Q(s, a) : Expected return from taking action a in state s, then following π. The Bellman equation defines the recursive relationship: V(s) = max_a [R(s,a) + γ Σ P(s'|s,a) V(s')]. Solving this equation is the central computational challenge of MDPs. In deep reinforcement learning for caching, a neural network approximates Q(s,a) to handle large state spaces.