Markov Decision Process (MDP)

The defining assumption of an MDP: the future is independent of the past given the present. Formally, a state (S_t) is Markov if and only if (P(S_{t+1} | S_t) = P(S_{t+1} | S_1, ..., S_t)). This implies the current state captures all relevant history for decision-making.

• Sufficient statistic: The state must encode position, velocity, and context—no hidden memory required.
• Practical implication: In a wireless scheduler, the state must include queue backlogs and channel quality indicators (CQI); omitting either breaks the Markov assumption.
• Contrast: Partially Observable MDPs (POMDPs) relax this by maintaining a belief state over hidden variables.

The state space (\mathcal{S}) is the complete set of all possible configurations the agent can encounter. It defines the input dimensionality for the policy and value function approximators.

• Discrete states: Finite sets, such as grid-world cells or buffer occupancy levels (e.g., 0–100 packets).
• Continuous states: Real-valued vectors, such as SINR measurements, user positions, or battery levels.
• RAN example: A deep reinforcement learning agent for load balancing may define state as a vector of per-cell PRB utilization, active user counts, and average throughput—typically a high-dimensional continuous space requiring neural network function approximation.

The action space (\mathcal{A}) enumerates every possible decision available to the agent at each time step. Its structure directly determines which reinforcement learning algorithms are applicable.

• Discrete actions: A finite set of choices—e.g., select cell A, B, or C for handover; choose MCS index 1 through 15.
• Continuous actions: Real-valued parameters—e.g., transmit power in dBm, beamforming angle in radians, or cell individual offset (CIO) in decibels.
• Hybrid spaces: Common in RAN optimization, where an agent might discretely select a user and continuously adjust power allocation. Algorithms like Soft Actor-Critic (SAC) handle continuous actions natively, while Deep Q-Networks (DQN) require discretization.

The transition function (P(s' | s, a)) defines the probability of moving to state (s') after taking action (a) in state (s). This encodes the environment's stochasticity.

• Model-based RL: The agent learns or is given an explicit model of (P), enabling planning via rollouts or dynamic programming.
• Model-free RL: The agent learns directly from sampled transitions without modeling (P)—dominant in wireless applications where channel dynamics are too complex to model explicitly.
• Deterministic transitions: A special case where (P(s' | s, a) = 1) for exactly one (s'). Rare in real networks due to fading, mobility, and traffic randomness.

The reward function (\mathcal{R}(s, a)) is the scalar signal that defines the agent's objective. It is the only mechanism for communicating design intent to the learning algorithm.

• Dense rewards: Provided at every time step—e.g., instantaneous throughput or negative energy consumption—enabling faster credit assignment.
• Sparse rewards: Given only at terminal states or rare events—e.g., successful handover completion or call drop—requiring sophisticated exploration strategies.
• Shaping risks: Poorly designed rewards cause reward hacking, where the agent maximizes the signal without achieving the true objective. In RAN energy optimization, a naive reward of "minimize transmit power" may cause the agent to serve zero users—the reward must jointly consider power and QoS constraints.

The discount factor (\gamma \in [0, 1)) determines the present value of future rewards, controlling the agent's planning horizon. The objective is to maximize the expected discounted return: (\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t r_t]).

• (\gamma \approx 0): Myopic agent—prioritizes immediate reward. Suitable for fast-fading channel decisions where future states are nearly irrelevant.
• (\gamma \approx 1): Far-sighted agent—values long-term outcomes. Essential for energy-saving strategies where powering down a cell now yields cumulative savings over hours.
• Episodic vs. continuing: Finite-horizon tasks (e.g., a fixed-duration video stream) may use (\gamma = 1) with terminal states; infinite-horizon tasks require (\gamma < 1) to ensure convergence.

An MDP is rigorously defined by the tuple (S, A, P, R, γ). S represents the finite set of all possible network states (e.g., buffer levels, SINR measurements). A is the set of actions (e.g., power adjustments, scheduling decisions). P(s'|s, a) is the state transition probability function. R(s, a) is the immediate reward signal. γ ∈ [0,1] is the discount factor that balances immediate versus future rewards.

The core assumption is that the future state depends only on the current state and action, not the full history. In RAN optimization, this is a practical approximation: the next SINR depends primarily on the current interference pattern and power allocation, not on conditions from minutes ago. This property makes the problem computationally tractable for real-time control loops operating on millisecond timescales.

The goal of solving an MDP is to find an optimal policy π(a|s)—a mapping from states to actions that maximizes expected cumulative reward. Two key functions guide this search:

• State-value function V(s): Expected return starting from state s and following policy π thereafter
• Action-value function Q(s, a): Expected return starting from state s, taking action a, then following π Deep Q-Networks directly approximate Q(s,a) to handle the high-dimensional state spaces of modern cellular deployments.

The reward function R(s, a) translates network operator goals into a scalar signal. Effective designs often combine multiple objectives:

• Throughput maximization: +reward proportional to bits successfully transmitted
• Energy penalty: -reward for each watt of transmission power consumed
• SLA violation cost: -reward when latency exceeds a threshold
• Handover penalty: -reward for each unnecessary cell transition Careful weighting prevents reward hacking where the agent exploits a single metric at the expense of overall network health.

In real RAN deployments, the agent rarely has access to the true global state. A POMDP extends the MDP framework with an observation function O(o|s, a) and a belief state—a probability distribution over possible true states. For example, a base station observes CQI reports but not the exact interference from hidden nodes. Practical solutions use recurrent neural networks to maintain an implicit belief state over time.

The recursive heart of MDP solving: Q(s, a) = R(s, a) + γ Σ P(s'|s, a) max_a' Q(s', a')**. This equation states that the optimal action-value equals the immediate reward plus the discounted expected value of the best action in the next state. Deep reinforcement learning algorithms like DQN and PPO iteratively approximate this equation using neural networks and stochastic gradient descent, enabling learning without an explicit model of the wireless environment.

A model-free, off-policy reinforcement learning algorithm that learns the value of taking a specific action in a given state. It iteratively updates a Q-table or Q-function based on the Bellman equation without requiring a model of the environment's transition probabilities.

• Learns optimal action-value function Q*(s,a) directly
• Off-policy: learns from actions not taken by current policy
• Foundation for more advanced algorithms like DQN

The complete set of all possible configurations or observations that an agent can encounter within its environment. In wireless networks, the state space may include channel quality indicators (CQI), buffer statuses, interference levels, and user positions.

• Defines input dimensionality for the policy network
• Can be discrete, continuous, or hybrid
• High-dimensional state spaces require deep function approximators

The set of all possible moves or decisions available to a reinforcement learning agent at each time step. For RAN optimization, actions might include transmission power levels, modulation and coding scheme (MCS) selection, or resource block allocations.

• Discrete: finite set of choices (e.g., select MCS 1-15)
• Continuous: real-valued parameters (e.g., power from 0-40 dBm)
• Hybrid: combination of both types

A scalar signal r(s,a) that defines the goal of a reinforcement learning agent by assigning a numerical value to each state-action pair. The agent's objective is to maximize the cumulative discounted reward over time.

• Shapes agent behavior toward desired outcomes
• In RAN: reward may combine throughput (+), latency (-), and energy (-)
• Sparse vs. dense rewards affect learning speed
• Poorly designed rewards lead to reward hacking

The fundamental dilemma where an agent must balance trying new actions to discover better strategies (exploration) against leveraging known actions that yield high rewards (exploitation).

• ε-greedy: select random action with probability ε
• Boltzmann exploration: sample actions from softmax over Q-values
• Upper Confidence Bound (UCB): prioritize uncertain actions
• Critical in non-stationary wireless environments where channel conditions change rapidly