Partially Observable MDP (POMDP)

The core abstraction of a POMDP. Since the agent cannot directly observe the true environmental state, it maintains a probability distribution over all possible states. This belief is a sufficient statistic for the entire history of actions and observations. After each action and observation, the agent performs a belief update using Bayes' rule to compute the posterior distribution. This transforms the original POMDP into a continuous-state MDP over the belief space, where planning becomes computationally intensive due to the curse of dimensionality.

The observation function defines the probabilistic relationship between the hidden state and the agent's sensor readings. Formally denoted as O(o | s', a), it specifies the probability of observing o given that action a resulted in state s'. In cognitive radio, this models the uncertainty in spectrum sensing—a received signal strength indicator (RSSI) reading might be noisy, or a primary user signal could be missed due to the hidden node problem. This model explicitly captures sensor imperfection.

Identical to a standard MDP, the transition function T(s' | s, a) defines the probability of moving to state s' after taking action a in state s. In a dynamic spectrum access scenario, this models the stochastic arrival and departure of primary users on a frequency channel. The agent does not observe these transitions directly; it must infer them from the observation sequence. This hidden state evolution is what distinguishes a POMDP from a fully observable MDP or a simpler Multi-Armed Bandit model.

A POMDP policy maps belief states to actions, not physical states to actions. Since the belief space is continuous, representing the optimal policy is non-trivial. Common approaches include:

• Finite-State Controllers (FSCs): A directed graph where nodes represent memory states and edges define action-observation transitions.
• Policy Graphs: Acyclic graphs used in online solvers like DESPOT.
• Deep Neural Networks: A Deep Q-Network (DQN) or Actor-Critic architecture that takes the belief vector as input and outputs action values, enabling end-to-end learning in high-dimensional spaces.

The reward signal R(s, a) defines the agent's objective. In a POMDP, the agent cannot observe s directly, so it must optimize the expected cumulative reward over its belief distribution. For cognitive radio, a typical reward function penalizes collisions with primary users, rewards successful throughput, and may include a small cost for channel switching or sensing. Reward shaping is often critical to accelerate learning in sparse-reward environments where positive outcomes are rare.

Solving POMDPs optimally is PSPACE-complete, making exact solutions intractable for all but the smallest problems. Practical solvers fall into two categories:

• Offline Point-Based Solvers: Algorithms like SARSOP and PBVI sample reachable belief points and compute value functions only at those locations.
• Online Tree Search: Methods like POMCP and DESPOT use Monte Carlo tree search to plan from the current belief in real-time, avoiding the need to pre-compute a policy for the entire belief space. Online methods are preferred for dynamic spectrum access where the environment model may be learned.

A probability distribution over all possible true environmental states that an agent maintains when it cannot directly observe the world. After each action and noisy observation, the agent updates this belief using Bayesian inference. In a POMDP, the belief state is a sufficient statistic—it contains all information from the agent's history needed to make optimal decisions. For cognitive radios, the belief state encodes the likelihood that each frequency band is currently occupied by a primary user.

A model-free reinforcement learning algorithm that learns the optimal action-value function without requiring a model of transition probabilities. The agent iteratively updates Q(s,a) values using the Bellman equation:

• Observes current state and selects action
• Receives reward and observes next state
• Updates Q-value toward the experienced reward plus discounted future value In partially observable domains, Q-learning can be applied directly to observation histories or belief states, though convergence guarantees weaken without full observability.

The fundamental dilemma where an agent must balance trying new actions to discover potentially better rewards against leveraging known actions that already yield high returns. In POMDPs, exploration serves a dual purpose:

• Reward exploration: finding actions with higher payoffs
• Information exploration: reducing uncertainty about the hidden state Cognitive radios face this tradeoff when deciding whether to sense a rarely-used frequency band or transmit on a known idle channel. Algorithms like Thompson Sampling and Upper Confidence Bound (UCB) provide principled exploration strategies.

A hybrid reinforcement learning architecture combining two neural networks:

• Actor: the policy network that selects actions based on the current belief or observation
• Critic: the value network that evaluates how good the current situation is, providing a baseline to reduce variance in policy gradient estimates This architecture is particularly effective for continuous action spaces in POMDPs, such as adjusting transmission power or modulation schemes. Algorithms like Proximal Policy Optimization (PPO) and Advantage Actor-Critic (A2C) extend this paradigm with stable training mechanisms.