Constrained Markov Decision Processes for Wireless Resource Allocation

41 concepts42 papers1 proposal

Wireless networks operate under a perpetual tug-of-war between performance and resource consumption. For instance, a transmitter can minimize packet latency by boosting its transmission rate, but doing so rapidly drains its battery. Conversely, conserving power requires slowing down transmissions, which causes data queues to back up and increases latency. This "speed vs. battery" tradeoff is a fundamental challenge in modern communications, as explored by Chen et al. in Delay-Optimal Buffer-Aware Scheduling with Adaptive Transmission.

Beyond traditional latency, modern applications like the Internet of Things (IoT) and remote sensing prioritize data freshness, quantified as the Age of Information (AoI). Minimizing AoI requires frequent status updates, which directly conflicts with strict transmission or energy budgets (Gunduz et al. in A Reinforcement Learning Approach to Age of Information in Multi-User Networks). In some scenarios, being fresh is not enough; the system must also avoid maintaining stale, incorrect states. To capture this, Maatouk et al. introduced the "Age of Incorrect Information" (AoII) in The Age of Incorrect Information: A New Performance Metric for Status Updates, adding another layer to the optimization problem.

Greedy scheduling strategies—which optimize only for the immediate time step—fail in these environments. A greedy policy might exhaust all available energy to transmit a low-priority packet over a faded channel, leaving no power for a critical packet arriving a moment later. To find truly optimal trade-offs, the system must anticipate future packet arrivals, channel fluctuations, and energy availability.

Mapping Network Dynamics to State Spaces

To make forward-looking decisions, researchers model wireless scheduling as a Markov Decision Process (MDP). The power of the MDP framework lies in its state space, which acts as a mathematical summary of the network's history and current capacity. A typical wireless MDP state vector integrates three critical dimensions:

  1. Queue Backlog and Buffer Occupancy: Represents the current accumulation of data awaiting transmission, which directly relates to packet delays (Chen et al. in Delay-Optimal Probabilistic Scheduling in Green Communications with Arbitrary Arrival and Adaptive Transmission; Lu et al. in Optimal weighted-delay scheduling in 2˟ 2 input-queued switches).
  2. Energy Storage and Battery Levels: Tracks remaining power, which is vital for self-sustaining Radio Frequency Energy Harvesting Networks (RF-EHNs) (Lu et al. in Resource allocation in wireless networks with RF energy harvesting and transfer).
  3. Channel State Information (CSI): Captures the time-varying, memory-driven nature of wireless fading channels (Zhan et al. in Delay Optimal Cross-Layer Scheduling Over Markov Channels with Power Constraint).

By combining these elements, the state space allows an agent to evaluate the long-term consequences of its actions. For instance, Holliday demonstrated in Joint Source and Channel Coding for MIMO Systems: Is it Better to be Robust or Quick? that minimizing end-to-end distortion requires dynamically balancing multiplexing rate and retransmission windows based on the current queue backlog and message age.

Actions are not limited to simple "transmit or idle" choices; they can include adjusting transmission rates, varying network coding block sizes (Yang et al. in Adaptive network coding for scheduling real-time traffic with hard deadlines), or dynamically switching between operational modes. For example, in RF-powered cognitive radio networks, an agent can choose to actively transmit data, backscatter ambient signals, or remain idle to harvest energy from primary users (Lu et al. in Dynamic spectrum access in cognitive radio networks with RF energy harvesting).

Managing Hard Constraints via Lagrangian Relaxation

While standard MDPs maximize a single unconstrained reward, wireless networks must satisfy strict, long-term physical constraints, such as a maximum average power consumption or a hard Quality of Service (QoS) reliability target. This requires a Constrained Markov Decision Process (CMDP) formulation, as demonstrated by Song et al. in Dynamic Virtual Resource Allocation for 5G and Beyond Network Slicing.

To solve a CMDP, researchers frequently employ Lagrangian relaxation. This mathematical mechanism converts a hard constraint (e.g., average power must not exceed $P_{\text{max}}$) into a soft penalty within an unconstrained objective function. The optimization problem becomes:

$$\min \mathbb{E} \left[ \sum_{t=0}^{\infty} \gamma^t ( \text{Delay}_t + \lambda \cdot \text{Power}_t ) \right]$$

Here, $\lambda$ is a Lagrange multiplier that acts as a dynamic price for resource consumption. If the system consumes too much power, $\lambda$ increases, penalizing power-heavy actions and forcing the policy to prioritize energy conservation. Conversely, if the power budget is underutilized, $\lambda$ drops, allowing the policy to focus entirely on minimizing delay or maximizing data freshness (Zhao et al. in Age of Information Analysis for Dynamic Spectrum Sharing). Alternatively, when the state space is finite, the CMDP can be mapped directly to a Linear Programming (LP) problem to compute the exact optimal baseline policy (Zhou et al. in Age-Optimal Multi-Channel-Scheduling under Energy and Tolerance Constraints).

The Structural Elegance of Threshold Policies

A major reason why the MDP formulation is so valuable is that the resulting optimal policies often possess an intuitive, easily implementable threshold structure. Instead of requiring a device to perform complex matrix calculations in real time, the optimal action can often be determined by checking whether a state variable has crossed a specific boundary.

However, researchers have also uncovered surprising exceptions to this structural simplicity. In energy-harvesting systems, common sense suggests that having more energy or more packets should monotonically increase transmission rates. Yet, Mahajan et al. provided rigorous counterexamples in Counterexamples on the Monotonicity of Delay Optimal Strategies for Energy Harvesting Transmitters, proving that optimal policies can be non-monotone. An agent might choose to remain idle even with a full battery and a loaded queue to save energy for future time steps when channel conditions are expected to improve (Gindullina et al. in Age-of-Information with Information Source Diversity in an Energy Harvesting System).

Learning Policies in Unknown Environments

Computing exact MDP or CMDP solutions requires perfect prior knowledge of the system's transition probabilities—meaning the exact statistical distributions of packet arrivals, channel fading, and energy harvesting rates must be known. In real-world deployments, these statistics are rarely static or known in advance.

To overcome this limitation, researchers leverage Reinforcement Learning (RL) to learn the optimal policy online through trial and error. Blasco et al. demonstrated in A Learning Theoretic Approach to Energy Harvesting Communication System Optimization that Q-learning can converge to near-optimal transmission strategies without any prior statistical knowledge.

When the state space scales up or incorporates hybrid automatic repeat request (HARQ) protocols, deep reinforcement learning models like Deep Q-Networks (DQNs) are deployed to handle the complexity (Gunduz et al. in A Reinforcement Learning Approach to Age of Information in Multi-User Networks With HARQ). By mapping high-dimensional network states directly to optimal resource allocation actions, RL allows the underlying mathematical insights of the CMDP framework to function dynamically in unpredictable, real-world environments (Ong et al. in Cognitive Radio Network Throughput Maximization with Deep Reinforcement Learning).

Key Foundational Work

Optimization of Reliability and Power Consumption in Systems on a Chip (2005) — contributed 1 concept elements to this direction.
Battery-aware power management based on Markovian decision processes (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_markov_decision_process_formulation_cons_1a9d0b7f,
  title = {Markov Decision Process formulation (constrained markov decision process)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markov-decision-process-formulation-constrained-markov-decision-process/rdr_1a9d0b7f63ba4cbea0a1875ad904adf9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_markov_decision_process_formulation_cons_1a9d0b7f_v1,
  title = {Markov Decision Process formulation (constrained markov decision process)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markov-decision-process-formulation-constrained-markov-decision-process/rdr_1a9d0b7f63ba4cbea0a1875ad904adf9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake