Partially Observable MDP (POMDP)

The set of all possible, true configurations of the environment. In a POMDP, the agent cannot directly observe which state s ∈ S it is in. This is the fundamental source of uncertainty.

• Example: In robot navigation, S includes every possible (x, y) coordinate and orientation of the robot, plus the locations of all dynamic obstacles.
• Contrast with MDP: In an MDP, the agent knows s exactly. In a POMDP, s is hidden.

The set of all possible sensory inputs or measurements the agent receives. Observations provide partial, noisy information about the underlying true state.

• Key Property: Observations are generated by the observation function Z(s, a, o) = P(o | s', a), which defines the probability of receiving observation o after taking action a and transitioning to state s'.
• Example: A robot's camera provides a pixel image (the observation) from which it must infer its true position (the state). The image may be blurry or occluded, making the mapping from state to observation probabilistic.

A probability distribution over the state space S. This is the POMDP's core innovation: since the state is unknown, the agent maintains a belief b(s), which is the probability it is in state s. The belief state is a sufficient statistic—it summarizes all past observations and actions.

• Update Rule: The belief is updated using Bayes' rule after each action a and observation o: b'(s') = η * P(o | s', a) * Σ_s P(s' | s, a) * b(s), where η is a normalizing constant.
• Example: A robot might have a belief that it is 70% likely in Room A and 30% likely in Room B. This belief is updated as it moves and receives new sensor data.

A mapping from belief states to actions: π(b) -> a. Unlike an MDP policy that maps states to actions, a POMDP policy must reason under uncertainty, choosing actions based on the entire belief distribution.

• Optimal Policy: The policy that maximizes the expected cumulative discounted reward from any initial belief. Finding this is the primary goal of solving a POMDP.
• Complexity: The belief space is continuous and high-dimensional (a simplex over |S|), making finding the optimal policy computationally intractable for large problems. Solutions often involve approximate methods or finite policy graphs.

The expected cumulative reward achievable starting from belief state b and following a specific policy thereafter. The optimal value function V*(b) satisfies the Bellman optimality equation for POMDPs:

V*(b) = max_a [ R(b, a) + γ * Σ_o P(o | b, a) * V*(b'_a,o) ]

Where:

• R(b, a) = Σ_s b(s) * R(s, a) is the expected immediate reward.
• b'_a,o is the updated belief after taking a and seeing o.
• P(o | b, a) = Σ_s' P(o | s', a) * Σ_s P(s' | s, a) * b(s) is the probability of observing o.

This equation shows that optimal action selection requires planning over future beliefs, not just states.

A POMDP can be transformed into a fully observable, but continuous-state, Belief MDP. This is a crucial conceptual and algorithmic tool.

• States: The belief states b.
• Actions: The same action space A.
• Transitions: Deterministic given a and o. The next belief b' is computed via the Bayesian update rule.
• Rewards: R(b, a) as defined above.

Implication: Any MDP planning algorithm can, in theory, be applied to the Belief MDP. However, because the belief space is continuous and high-dimensional, exact solutions are only possible for very small problems. This transformation underpins approximate solution methods like point-based value iteration, which samples a set of reachable belief points to approximate V*(b).

A robot navigating a warehouse or home must estimate its precise location (localization) using noisy sensors like wheel encoders, cameras, or LiDAR. The true state (exact pose) is hidden; the robot only receives observations (e.g., a blurry image of a wall, a LiDAR point cloud). The POMDP solution maintains a belief state—a probability distribution over possible locations—and plans actions (move forward, turn) that maximize the chance of reaching a goal while avoiding collisions, despite sensor uncertainty and potential actuator slip.

• Key Challenge: Data association (is that landmark the same one I saw before?).
• Solution Approach: Often uses a particle filter to represent the belief distribution.

A robot arm tasked with assembling parts from a bin cannot see every object directly due to occlusion. Its camera provides a partial, top-down view. The true state (exact poses and identities of all parts) is partially observable. The POMDP policy must sequence actions like pushing to reduce uncertainty, regrasping, and inserting a part, all while reasoning about what might be hidden. This is critical for bin picking and kitting tasks in manufacturing.

• Key Challenge: The need for information-gathering actions (e.g., a push to reveal hidden objects) that have no immediate reward but reduce future uncertainty.
• Real System: Early POMDP applications were tested on robotic manipulation tasks at institutions like MIT and CMU.

A collaborative robot (cobot) working alongside a human must infer the human's goal and internal state (e.g., intention, next action, fatigue) from ambiguous cues like gaze, gesture, and speech. This is a classic POMDP where the human's mental state is the hidden variable. The robot's observations are imperfect interpretations from its vision and audio systems. The optimal policy allows the robot to anticipate needs (handing over a tool) or avoid unsafe interference.

• Key Challenge: Modeling the human as a stochastic agent within the POMDP transition function.
• Application: Assistive robotics, assembly line teamwork.

An autonomous drone searching a disaster zone for survivors operates under extreme perceptual uncertainty due to smoke, dust, and poor lighting. Its camera and thermal sensors provide noisy, low-fidelity observations. The true state (locations of survivors, structural integrity of paths) is partially observable. The POMDP policy optimizes a flight path that balances exploration of unknown areas, exploitation of likely survivor locations based on the belief map, and recharging constraints.

• Key Challenge: The belief space over survivor locations is vast and continuous.
• Solution Approach: Often uses online POMDP solvers that focus planning on the current most probable belief.

While not strictly robotics, this is a canonical AI POMDP example. A system recommending treatment sequences for a chronic disease (e.g., chemotherapy for cancer) has a hidden true state: the precise disease progression and patient response. Observations are noisy medical tests (blood work, biopsies with error rates). Actions are treatment choices (Drug A, Drug B, pause). Rewards are based on patient health outcomes and quality of life. The POMDP finds a policy that optimally sequences tests and treatments under uncertainty.

• Key Challenge: Defining an accurate observation model that encapsulates test sensitivity/specificity.
• Impact: Demonstrates POMDPs' utility for sequential decision-making under diagnostic uncertainty.

The fundamental complexity of POMDPs stems from the belief state—a probability distribution over all possible true states, updated via Bayes' theorem after each action and observation. The optimal policy is a mapping from this continuous, high-dimensional belief space to actions. Exact solving is computationally intractable for most real problems.

• Key Algorithms: Approximate solvers like POMCP (Monte Carlo Tree Search in belief space), QMDP, and Point-Based Value Iteration (PBVI).
• Relation to MDP: A POMDP can be reduced to an MDP over belief states (the belief MDP), but its state space is continuous and infinite.
• Modern Link: Deep Reinforcement Learning approaches now train neural networks to approximate the value function or policy directly over belief representations.

The foundational mathematical framework for sequential decision-making under certainty. An MDP is defined by the tuple (S, A, T, R, γ) where:

• S is a finite set of states.
• A is a finite set of actions.
• T(s' | s, a) is the state transition probability function.
• R(s, a, s') is the reward function.
• γ is the discount factor.

The core assumption is the Markov Property: the future depends only on the present state and action, not the full history. POMDPs relax the requirement that the agent knows s, but the underlying environment is still assumed to be an MDP.

A belief state b is a probability distribution over all possible true states s ∈ S. It is the POMDP's solution to partial observability, serving as a sufficient statistic for the history of actions and observations.

• It is updated using the Bayes filter: b'(s') ∝ O(o | s', a) Σ_s T(s' | s, a) b(s).
• The belief space is continuous, even for discrete state POMDPs, transforming the problem into planning in a high-dimensional continuous space.
• Optimal policies for POMDPs are functions from this belief space to actions: π*(b) → a.

Formally defined by the observation function O(o | s', a), which gives the probability of receiving observation o after taking action a and landing in state s'. This model encodes the agent's sensors and their limitations.

Key characteristics include:

• Noisy Sensors: Observations are probabilistic (e.g., a camera misclassifying an object 5% of the time).
• Partial: The observation may not disambiguate between states (e.g., a robot seeing a 'wall' but not knowing which room it's in).
• Action-Dependent: Some sensors are active (e.g., a laser rangefinder's reading depends on where it's pointed). The quality of the observation model directly impacts the entropy of the belief state.

A conceptual transformation that turns a POMDP into a fully observable, but continuous-state, MDP. This is the standard method for solving POMDPs theoretically and algorithmically.

Transformation:

• State Space: The continuous space of belief states b.
• Actions: Same as the original POMDP actions A.
• Transitions: Defined by the deterministic belief update b' = τ(b, a, o), where the probability of reaching b' depends on the probability of observation o.
• Reward: The expected reward over the belief: ρ(b, a) = Σ_s b(s) Σ_s' T(s'|s,a) R(s,a,s').

Solving this Belief MDP yields the optimal POMDP policy, but the continuous state space makes it computationally challenging.

A Decentralized Partially Observable Markov Decision Process is the multi-agent extension of a POMDP. It models a team of agents cooperating under partial observability without a central controller that can share all observations instantaneously.

Core Challenges:

• Each agent i has its own local observation o_i and action a_i.
• The team shares a joint reward.
• The policy for each agent (π_i) can only condition on its own local action-observation history.
• The solution is a joint policy, and the problem is NEXP-Complete.

This framework is critical for multi-robot coordination where communication is limited or delayed.

A simple but effective approximation method for POMDPs that assumes full observability will be restored on the next step. It uses the optimal Q-function Q*(s, a) from the underlying MDP (assuming full state s is known).

The Q-MDP policy acts in the POMDP by taking the action that maximizes the expected Q-value under the current belief: π(b) = argmax_a Σ_s b(s) Q*(s, a).

Properties:

• Computationally Efficient: Requires only solving the base MDP.
• Short-sighted: Performs well for tasks where information gathering is not critical, but fails in problems requiring active perception (e.g., searching).
• Often used as a baseline or in hybrid methods.