Partially Observable Markov Decision Process (POMDP)

The State represents the complete, ground-truth configuration of the environment that is relevant to the agent's task. In language-guided navigation, this is the agent's precise pose (x, y, θ) and the full layout of the environment.

• Key Point: The agent never directly observes the true state; it is hidden or partially observable.
• Example: For a robot in a house, the state includes the robot's exact room, its coordinates within that room, and the status of all doors and objects.

The set of Actions defines all possible moves the agent can execute at each timestep. These are the low-level control commands that transition the agent between states.

• Navigation Examples: move_forward, turn_left, turn_right, stop.
• Stochastic Transitions: Executing an action leads to a new state based on a transition model T(s' | s, a), which encodes environmental dynamics and uncertainty (e.g., wheel slippage).

An Observation is the sensory data the agent receives, which provides noisy, incomplete clues about the hidden state. The Observation Model Z(o | s', a) defines the probability of receiving observation o after taking action a and landing in state s'.

• In Navigation: An observation is often an egocentric visual panorama or a depth scan.
• Partial Observability: Two different states (e.g., two identical-looking corridors) can produce the same observation, creating ambiguity.

The Belief State is a probability distribution over all possible states S, representing the agent's internal knowledge about the world. It is the POMDP's solution to partial observability.

• Bayesian Update: The belief is updated using the Bayes filter: b'(s') ∝ Z(o | s', a) Σ_s T(s' | s, a) b(s).
• Core Function: In language-guided navigation, the instruction ("go to the kitchen") conditions the initial belief and the ongoing belief update, focusing probability mass on states consistent with the language.

A Policy π(b) maps the current belief state to an action. The optimal policy maximizes the expected cumulative reward. The Value Function V(b) estimates the expected future reward starting from belief b and following policy π.

• Planning Challenge: The policy must reason over the infinite space of possible beliefs.
• Goal: To find π* = argmax_π E[ Σ γ^t R(s_t, a_t) ], where future rewards are discounted by factor γ.

The Reward Function R(s, a) provides a scalar signal defining the task's objective. It encodes what the agent should accomplish (e.g., reach a goal) and what it should avoid (e.g., collisions).

• Sparse Rewards: Common in navigation: e.g., +100 for reaching the goal, -1 per step to encourage efficiency, -100 for a collision.
• Language Integration: The reward function is often conditioned on the language instruction, providing positive reward only when the agent's state satisfies the grounded instruction.

A POMDP is formally defined as a 7-tuple (S, A, T, R, Ω, O, γ). S is the set of states (e.g., true robot poses). A is the set of actions (e.g., move forward, turn). T is the state transition function P(s'|s,a). R is the reward function R(s,a). Ω is the set of observations (e.g., camera images). O is the observation function P(o|s',a). γ is the discount factor. The agent never directly observes s, only o, leading to the central concept of a belief state b(s)—a probability distribution over S.

The belief state b_t is the agent's internal estimate of the true world state at time t. It is updated using Bayes' theorem after taking action a_t and receiving observation o_{t+1}. This is the belief update or filtering equation: b_{t+1}(s') = η * O(o_{t+1} | s', a_t) * Σ_s T(s' | s, a_t) * b_t(s) where η is a normalizing constant. This process is computationally intensive, requiring integration over the state space, which is why approximate inference methods like particle filters are essential for real-world robotics.

A POMDP policy π(b) maps a belief state b to an action a. The optimal policy maximizes the expected cumulative discounted reward. Because the true state is unknown, planning occurs over belief space, not state space. The value function V(b) represents the expected future reward starting from belief b. Solving a POMDP exactly involves finding V(b), often represented as a set of hyperplanes over belief space (the value iteration algorithm). For real-world problems, point-based value iteration and online planning methods like POMCP are used.

In Vision-and-Language Navigation (VLN), the POMDP framework is directly applicable. The state S includes the agent's pose and the environment layout. The observation Ω is an egocentric visual panorama. The action A is a set of navigable movements. Crucially, the natural language instruction is treated as part of the observation model O, providing noisy, semantic clues about the goal. The agent's belief must therefore fuse visual data with linguistic constraints to infer its likely location and the target. This makes VLN a quintessential POMDP problem.

Exact POMDP solvers are intractable for most robotics problems. Key approximate algorithms include:

• Monte Carlo Tree Search (MCTS) for POMDPs (POMCP): An online planner that uses Monte Carlo simulations in belief space, represented by particles.
• QMDP & FIB: Simplified methods that assume full observability on the next step, making them computationally cheaper but less optimal.
• Point-Based Value Iteration (PBVI): An offline solver that approximates the value function by updating it only at a sampled set of belief points.
• Deep Reinforcement Learning: End-to-end training of a policy network π(o, h) where h is a history embedding that implicitly represents the belief.

POMDPs are foundational for any robotic task with sensor noise and uncertainty:

• Dexterous Manipulation: When a robot hand grasps an object with tactile uncertainty.
• Human-Robot Interaction: Modeling uncertain human intentions and beliefs.
• Autonomous Driving: Tracking other vehicles' intentions (a hidden state) with noisy sensor data.
• Active Sensing & Information Gathering: Where actions are chosen specifically to reduce uncertainty (e.g., a robot moving its head to get a better view). This links to information-theoretic rewards like maximizing expected entropy reduction.

A Markov Decision Process (MDP) is the fully observable precursor to a POMDP. It is a mathematical framework for modeling sequential decision-making where an agent has perfect knowledge of the environment's state.

• Core Components: Defined by a set of states, actions, transition probabilities, rewards, and a discount factor.
• Key Property: The Markov property states the future depends only on the present state, not the history.
• Contrast with POMDP: An MDP assumes the agent's observation perfectly reveals the true state, which is unrealistic for real-world navigation where sensors are partial or noisy.

A Belief State is a probability distribution over all possible true states of the environment, given the history of actions and observations. It is the core information state in a POMDP.

• Function: Represents the agent's internal estimate of where it is and what the world is like, compensating for partial observability.
• Update Mechanism: Maintained using Bayesian filtering (e.g., a Bayes filter or Kalman filter) each time the agent takes an action and receives a new, ambiguous observation.
• Example in Navigation: A robot might have a belief that it's 70% likely in the kitchen and 30% likely in the dining room based on a glimpsed countertop and its movement history.

The Belief Space is the continuous space of all possible belief states. Solving a POMDP involves finding an optimal policy that maps from this belief space to actions.

• Dimensionality: If there are N discrete states, the belief space is an (N-1)-dimensional simplex (as probabilities sum to 1).
• Planning Challenge: Policies are functions over this high-dimensional, continuous space, making exact solutions intractable for all but the smallest problems.
• Solution Approach: Advanced algorithms like point-based value iteration sample a set of representative belief points to approximate the optimal value function over the entire belief space.

The Observation Model (or sensor model) defines the probability P(o | s', a) of receiving a specific observation o given that the agent took action a and landed in true state s'. It quantifies sensor noise and uncertainty.

• Role in POMDP: It is a core tuple element (S, A, T, R, Ω, O, γ) where Ω is the observation set and O is the observation model.
• Real-World Analogy: For a robot's camera, the model describes the likelihood of seeing a 'blurry blue blob' given it is actually looking at a chair.
• Impact on Belief: This model is used alongside the transition model (T) within the Bayes filter to update the belief state after each action-observation cycle.

A Policy in a POMDP is a function π(b) that maps the current belief state b to an action a. The goal is to find the optimal policy π* that maximizes the expected cumulative discounted reward.

• Complexity: Unlike an MDP policy that maps states to actions, a POMDP policy must reason over the entire probability distribution (belief).
• Representation: Often represented as a set of alpha-vectors, where each vector is associated with an action and defines a linear function over the belief space. The policy selects the action whose alpha-vector gives the highest value for the current belief.
• Execution: The agent continually updates its belief and consults this policy to decide its next move, enabling information-gathering actions.

The Value Function V(b) for a POMDP gives the expected cumulative reward an agent can obtain starting from belief state b and following a specific policy thereafter. Finding V* is the objective of solving the POMDP.

• Shape: The optimal value function V*(b) is piecewise-linear and convex (PWLC) in the belief space for finite-horizon problems.
• Alpha-Vectors: This PWLC property means V*(b) can be represented by a finite set of alpha-vectors: V*(b) = max_α (α · b). Each alpha-vector is a hyperplane over the belief simplex.
• Planning Algorithms: Methods like Witness, Incremental Pruning, and Point-Based Value Iteration work by iteratively refining this set of alpha-vectors to approximate V*.