Partially Observable MDP (POMDP)

In a POMDP, the agent never sees the true state. Instead, it maintains a belief state—a probability distribution over all possible underlying states. This belief is updated using a Bayesian filter after each action and observation.

• The belief state is a sufficient statistic for the entire history of actions and observations
• It transforms the POMDP into a continuous-space belief MDP
• Dimensionality grows with the number of possible states, making exact solutions computationally intractable for large problems

The observation function defines the probabilistic relationship between the hidden environment state and what the agent perceives. Formally, it is the probability of receiving observation o given the agent took action a and landed in state s'.

• Captures sensor noise, occlusion, and partial visibility
• In logistics: a GPS reading may be noisy, or a package may be temporarily unscanned
• The agent must reason backward: 'Given what I saw, what state am I likely in?'

Because the agent is uncertain, actions can have epistemic value—they reduce uncertainty. A POMDP agent may deliberately take information-gathering actions that yield no immediate reward but improve future decisions.

• Example: A drone may deviate from its route to visually confirm inventory levels before committing to a delivery schedule
• This trade-off is absent in fully observable MDPs
• The optimal policy balances exploitation of known rewards against exploration to refine the belief state

Solving POMDPs exactly is PSPACE-complete for finite horizons and undecidable for infinite horizons in the worst case. Practical solvers rely on approximation techniques.

• Point-based value iteration samples reachable belief points to approximate the value function
• Monte Carlo methods use particle filters to represent beliefs as sets of weighted samples
• Modern deep learning approaches use recurrent neural networks to compress the belief state history into a latent representation

A refrigerated truck's internal temperature is a hidden state when sensors have latency or intermittent connectivity. The POMDP framework models this uncertainty explicitly.

• The belief state tracks the probability that cargo is still within safe temperature bounds
• The agent chooses actions: continue, reroute to a backup facility, or accelerate delivery
• The observation model accounts for sensor accuracy and transmission gaps
• This prevents both unnecessary waste from false alarms and spoilage from undetected excursions

POMDPs generalize MDPs by adding partial observability. In Multi-Agent POMDPs, each agent has its own private observations, creating a Dec-POMDP where agents must coordinate under decentralized information.

• Centralized Training Decentralized Execution (CTDE) is a common solution paradigm for Dec-POMDPs
• In warehouse robotics, each robot sees only its local sensor data but must coordinate globally
• The belief state becomes a joint distribution over all agents' possible configurations

A POMDP agent maintains a belief distribution over the true internal temperature of a pharmaceutical shipment. The agent only receives noisy sensor readings and must decide whether to preemptively re-ice or reroute the cargo. The policy balances the cost of intervention against the catastrophic risk of spoilage, optimizing actions based on the probability of a hidden excursion rather than a single threshold breach.

The true mechanical health of a truck is a hidden state. The POMDP agent observes indirect signals—vibration telemetry, fuel efficiency, and mileage—and maintains a belief about component degradation. It decides when to pull a vehicle for service, minimizing the expected cost of a road failure versus the opportunity cost of unnecessary downtime. The policy naturally adapts to different driver behaviors and route severities.

A procurement agent cannot directly observe a supplier's financial health or production capacity. It receives delayed and imperfect signals such as late deliveries or quality defects. The POMDP framework models this as a hidden state, allowing the agent to optimally decide when to dual-source, increase safety stock, or trigger an audit. The resulting policy hedges against hidden disruption risks without overreacting to noise.

The POMDP agent dispatches drivers without knowing their true fatigue level or local traffic knowledge. Observations include app acceptance rates and delivery time deviations. The agent learns a policy that offers incentives or reassigns tasks based on the inferred probability of driver overload, optimizing for on-time delivery while preventing burnout and churn in the gig-economy workforce.

An autonomous mobile robot operates with partial observability due to shelf occlusion and sensor noise. The POMDP maintains a probabilistic occupancy grid as its belief state. The policy selects actions—move, scan, request human assist—that actively reduce uncertainty about blocked aisles while progressing toward the pick location. This yields robust navigation that does not freeze when temporarily blinded.

The true on-hand inventory is a hidden state due to theft, misplacement, and scanning errors. A POMDP agent observes sales and periodic cycle counts to maintain a belief over actual stock levels. It decides when to trigger a full physical audit, balancing audit labor costs against the risk of stockouts or excess holding costs. The policy optimizes the timing and granularity of costly verification actions.

The foundational framework from which POMDPs extend. An MDP assumes the agent has perfect, noise-free observation of the true state. It is defined by a tuple (S, A, T, R) where the agent observes the state directly. POMDPs generalize this by adding an observation function and a belief state, making them applicable to real-world logistics where sensors are imperfect and environments are partially occluded.

The core mechanism that distinguishes a POMDP from an MDP. Since the agent cannot observe the true state, it maintains a probability distribution over all possible states. After taking an action and receiving an observation, the agent applies Bayes' rule to update this belief. This transforms the POMDP into a continuous-space 'belief MDP' where the state is the belief vector itself.

A scalable online planning algorithm that extends Monte Carlo Tree Search (MCTS) to POMDPs. Instead of planning over the full belief space, POMCP uses a particle filter to represent the belief as a set of unweighted state samples. It builds a search tree of observation-action histories, making it tractable for large state spaces like dynamic vehicle routing under uncertainty.

A probabilistic model O(o|s', a) that defines the likelihood of receiving observation o after taking action a and arriving in state s'. In logistics, this models sensor noise—for example, the probability that an RFID scanner correctly reads a pallet tag given interference. This function is what introduces perceptual aliasing, where different true states can generate the same observation.

A key concept in POMDP planning that quantifies the benefit of reducing uncertainty. An optimal POMDP agent may take information-gathering actions—like sending a drone to inspect a warehouse aisle—even if they have no immediate reward. This contrasts with MDPs, where all actions directly affect the physical state. The agent trades off exploitation against reducing entropy in its belief.