Partially Observable Markov Decision Process (POMDP)

The State Space is the set of all possible, true configurations of the environment. The agent cannot directly observe this true state. It is the fundamental hidden variable the agent must reason about.

• Example: In robot navigation, the state could be the robot's precise (x, y) coordinates and orientation.
• Key Property: The state is assumed to evolve according to the Markov property, meaning the future state depends only on the current state and action, not the full history.

The Action Space is the set of all possible actions the agent can execute to influence the environment and transition between states.

• Example: For a robot, actions could be {move_north, move_south, move_east, move_west, stay}.
• The agent selects an action based on its belief state, not the true state. The choice of action is the core of the agent's policy.

The Observation Space is the set of all possible, partial, and often noisy sensory inputs the agent receives from the environment. This is the agent's only direct source of information about the hidden state.

• Example: A robot's camera provides a pixel image (observation), from which it must infer its location (state). A sensor might return a noisy distance reading.
• Observations are generated probabilistically based on the true state and the last action taken.

The Transition Function, T(s' | s, a), is a probability distribution that defines the dynamics of the environment. It specifies the probability of transitioning to state s' given the current state s and the action a taken by the agent.

• Formula: T(s' | s, a) = P(S_{t+1} = s' | S_t = s, A_t = a)
• This function encodes the world model of how actions change the hidden state. In Model-Based Reinforcement Learning, the agent may learn an approximation of this function.

The Observation Function, Z(o | s', a), is a probability distribution that models the agent's sensors. It specifies the probability of receiving observation o given that the environment transitioned to state s' after action a.

• Formula: Z(o | s', a) = P(O_{t+1} = o | S_{t+1} = s', A_t = a)
• This function accounts for sensor noise and partial observability. It is crucial for updating the belief state correctly.

The Reward Function, R(s, a, s'), provides a scalar feedback signal to the agent. It defines the immediate reward (or cost) received after taking action a in state s and transitioning to state s'.

• The agent's goal is to find a policy that maximizes the expected cumulative reward (the return) over time.
• The reward function formally encodes the task objective. In Inverse Reinforcement Learning, the reward function is inferred from expert demonstrations.

The Belief State, b(s), is a probability distribution over the state space S. It represents the agent's internal knowledge or 'belief' about which true state it is in, given the entire history of actions and observations.

• Formula: b_t(s) = P(S_t = s | A_0, O_1, ..., A_{t-1}, O_t)
• This is the sufficient statistic for the history. The POMDP problem is reformulated as a Belief MDP, where the belief state itself becomes the fully observable state upon which the agent plans.
• Belief updating is performed using Bayes' rule.

A Policy, π(a | b), is a strategy that maps the agent's current belief state b to an action a (or a distribution over actions). It is the solution to the POMDP.

• Objective: Find the optimal policy π* that maximizes the expected discounted sum of future rewards.
• Because the belief space is continuous and high-dimensional, finding optimal policies is computationally intractable for most problems. Solutions often involve approximation methods like point-based value iteration or using deep reinforcement learning to learn a policy network π_θ(a | b).

Autonomous robots operating in cluttered, dynamic environments are classic POMDP applications. The robot's sensors (e.g., LIDAR, cameras) provide partial and noisy observations of object positions, human movements, and its own state.

• Belief State: The robot maintains a probabilistic map of obstacle locations and its own pose.
• Planning: It must plan paths that balance reaching a goal with taking informative actions (active perception) to reduce localization uncertainty.
• Example: A warehouse robot navigating aisles with occluded views, deciding when to slow down or re-localize to avoid collisions.

POMDPs model sequential medical decision-making where a patient's true physiological state (e.g., disease progression, drug resistance) is not directly observable, only inferred through tests and symptoms.

• State: The true health status of a patient (e.g., tumor size, infection type).
• Observation: Results from blood tests, imaging scans, and reported symptoms, which can be imperfect or delayed.
• Action: Choosing treatments, dosages, or ordering diagnostic tests.
• Application: Personalized cancer therapy, where the model plans a sequence of drugs and testing schedules to manage side effects and tumor response under uncertainty.

Conversational agents use POMDPs to manage the unobserved user goal and level of understanding. The agent must infer intent from ambiguous utterances and plan dialog moves to efficiently achieve the task.

• State: The user's true goal, knowledge state, and level of satisfaction.
• Observation: The user's current utterance, which may be underspecified or contain errors.
• Action: The system's response: ask a clarifying question, confirm understanding, or execute a command.
• Use Case: Technical support chatbots that diagnose problems through a series of questions, balancing the cost of lengthy dialog against the risk of providing an incorrect solution.

Self-driving cars operate in a fundamentally partially observable world. Sensors like cameras and radar provide limited, occluded views of other agents' intentions, road conditions, and pedestrian behavior.

• Belief over Intent: The car maintains a probability distribution over whether a pedestrian will cross, a cyclist will swerve, or another vehicle will change lanes.
• Information Gathering Actions: Subtle maneuvers like a lane shift or slowing down can be chosen to gain a better view and reduce uncertainty about hidden objects.
• Core Challenge: Planning safe trajectories that are robust to the many possible true states of the environment, weighted by their belief probability.

Industrial systems use POMDPs for predictive maintenance and fault diagnosis. The true degradation state of a component (e.g., a jet engine or manufacturing robot) is hidden, revealed only through indirect sensor readings and occasional inspections.

• State: The actual wear level or fault mode of a machine.
• Observation: Vibration spectra, temperature readings, output quality metrics.
• Action: Choices include running normally, performing an intrusive inspection, or scheduling a repair.
• Objective: Optimize the policy to minimize total cost, balancing the risk of catastrophic failure against the expense of unnecessary maintenance downtime.

Financial markets are partially observable: the true value of an asset or the latent market regime is not directly known. A trading agent observes noisy price signals and must decide on buy/sell actions.

• Hidden State: The underlying market sentiment, liquidity, or the true value of an asset.
• Observation: Order book data, price ticks, and news sentiment scores.
• Action: Trading decisions (buy, sell, hold) and position sizing.
• POMDP Role: The model maintains a belief over market states and plans sequences of trades that manage risk (exploitation) while occasionally taking actions to probe the market for information (exploration).

A Markov Decision Process (MDP) is the foundational, fully observable framework upon which POMDPs are built. It models sequential decision-making where an agent has perfect knowledge of the environment's true state.

• Core Components: Defined by a tuple (S, A, P, R, γ) of states, actions, transition probabilities, rewards, and a discount factor.
• Key Assumption: The Markov Property—the future state depends only on the current state and action, not the history.
• Contrast with POMDP: In an MDP, the agent observes s_t directly. In a POMDP, it only receives an observation o_t that is a noisy function of s_t, requiring the maintenance of a belief state.

A belief state b(s) is a probability distribution over all possible true states of the environment, given the history of actions and observations. It is the POMDP's solution to partial observability.

• Function: Serves as a sufficient statistic for the history, compressing all past experience into a probability distribution.
• Update Mechanism: Updated recursively using Bayes' theorem upon taking an action a and receiving a new observation o: b'(s') ∝ O(o | s', a) Σ_s P(s' | s, a) b(s).
• Planning Dimension: Transforms the POMDP into a continuous-state MDP over the belief space, where policies map belief states to actions.

A Hidden Markov Model (HMM) is a simpler statistical model that shares the core 'hidden state' structure with a POMDP but lacks an active decision-making component.

• Structure: Models a sequence of hidden states that evolve via Markov dynamics, emitting observations at each step.
• Key Tasks: Primarily used for filtering (estimating the current hidden state), prediction, and smoothing.
• Relationship to POMDP: A POMDP can be viewed as an HMM controlled by an agent's actions, where the transition and observation models are influenced by the chosen action a. The belief update in a POMDP is directly analogous to the forward algorithm in an HMM.

Model-Based Reinforcement Learning (MBRL) is an RL paradigm where an agent learns an explicit model of the environment's dynamics (transition function P and reward function R) and uses it for planning.

• Connection to POMDP: In many real-world MBRL problems, the learned model is inherently a world model that predicts future latent states from observations. When the true state is not fully observable, the agent is effectively learning the dynamics of a POMDP.
• Planning: MBRL agents use their learned model for internal simulation, similar to how a POMDP solver uses the known P and O functions to evaluate policies over belief states.
• Sample Efficiency: By planning with a model, both MBRL and POMDP methods aim to be more sample-efficient than pure model-free RL.

Bayesian Filtering is the general algorithmic framework for recursively estimating the state of a dynamic system from noisy observations, which is the core inference problem in a POMDP.

• Algorithms: Encompasses the Kalman filter (for linear Gaussian systems), the Extended Kalman Filter (EKF), the Unscented Kalman Filter (UKF), and the Particle Filter.
• Role in POMDPs: The belief update step b' = τ(b, a, o) is a Bayesian filter. For discrete state spaces, it's a discrete Bayes update. For continuous states, a particle filter is often used to represent the belief distribution non-parametrically.
• Separation Principle: In optimal control, the separation of estimation (filtering) and control is explicit in POMDPs: first maintain the belief (filter), then act based on it (policy).

A Decentralized Partially Observable Markov Decision Process (Dec-POMDP) generalizes the POMDP framework to multiple cooperative agents, each with their own local observations and actions, operating under a shared global reward.

• Complexity: Dec-POMDPs are NEXP-complete, significantly harder than single-agent POMDPs (PSPACE-complete), due to the decentralized information structure.
• Challenge: Agents must reason about the evolving beliefs and likely actions of other agents without direct communication, leading to an explosion in the joint policy space.
• Applications: The standard model for multi-agent planning under uncertainty in areas like cooperative robotics, network routing, and sensor networks.