Partially Observable Markov Decision Process (POMDP)

The state space is the set of all possible, hidden configurations of the environment. The agent cannot directly observe the true state s ∈ S. For example, in a robot navigation task, the state includes the robot's precise coordinates, orientation, and the location of obstacles—information that may be obscured by sensor noise or occlusions.

The action space is the set of all possible moves or decisions the agent can execute at each time step. Executing an action a ∈ A causes the environment to transition to a new hidden state according to the transition dynamics. Actions are the agent's mechanism for influencing the environment and achieving its goal, such as 'move forward', 'turn left', or 'ask for help'.

The observation space is the set of all possible sensory inputs or measurements the agent receives from the environment. After taking an action, the agent receives a partial and potentially noisy observation o ∈ O that provides clues about the underlying state. In a poker game, this could be the publicly visible cards; for a robot, it's a camera image or LiDAR scan.

The transition function, T(s' | s, a), defines the environment's dynamics. It is a probability distribution over next states s' given the current state s and the action taken a. This function models the uncertainty in how the world evolves. For instance, a robot's 'move forward' action may not always succeed due to wheel slippage, modeled by a probabilistic transition.

The observation function, Z(o | s', a), defines the sensor model. It is a probability distribution over observations o given the new state s' and the action a that led to it. This models the partial observability and sensor noise. For example, a faulty door sensor might have an 80% chance of correctly reporting 'open' and a 20% chance of reporting 'closed' when the door is actually open.

The reward function, R(s, a, s'), provides a scalar feedback signal to the agent. It defines the task's objective by specifying the immediate reward (or cost) received after taking action a in state s and transitioning to state s'. The agent's goal is to maximize the expected cumulative reward over time. A negative reward (penalty) might be given for hitting an obstacle, while a large positive reward is given for reaching a goal.

The belief state is a probability distribution over the state space S, representing the agent's internal estimate of the true world state given the history of actions and observations. It is a sufficient statistic for the history. The agent starts with a prior belief b₀ and updates it using the Bayes' rule after each action-observation pair. Maintaining and updating this belief is the central challenge of POMDPs.

A policy π(a | b) is a strategy that maps the current belief state to an action (or a distribution over actions). The value function V^π(b) estimates the expected cumulative future reward starting from belief b and following policy π. Solving a POMDP involves finding an optimal policy π* that maximizes the value function for all belief states, which is typically computationally intractable for large spaces, leading to approximate solvers.

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 state. Key components include:

• State Space (S): All possible configurations of the environment.
• Action Space (A): All actions the agent can take.
• Transition Function (T): The probability P(s'|s,a) of moving to state s' from state s after taking action a.
• Reward Function (R): The immediate scalar feedback R(s,a,s').
• Discount Factor (γ): Determines the present value of future rewards. An MDP's Markov Property states that the future depends only on the current state and action, not the history. POMDPs extend this by removing the assumption of full observability.

A belief state is a probability distribution over all possible underlying states of the environment, representing the agent's internal knowledge in a POMDP. Since the agent cannot directly observe the true state, it maintains this belief, which is a sufficient statistic for the history of actions and observations.

• It is updated using Bayes' theorem after each action and observation.
• A POMDP can be reformulated as a continuous-state MDP where the belief state is the new state space, though this is computationally intractable for large problems.
• Common representations include discrete probability vectors, parametric distributions (e.g., Gaussian), or particle filters for approximation. The agent's policy maps from this belief state to actions, making belief state estimation the core computational challenge in solving POMDPs.

A Hidden Markov Model (HMM) is a simpler statistical model that forms the observational core of a POMDP. It describes a system with an underlying Markov process (hidden states) that generates observable outputs.

• States: The hidden, unobserved variables that evolve according to Markov dynamics.
• Observations: The visible data emitted by each hidden state.
• Emission Probabilities: The probability of seeing a particular observation given the hidden state. While an HMM is used for modeling and inference (e.g., estimating the hidden state sequence from observations), a POMDP adds a decision-making layer. In a POMDP, the agent not only infers a belief state (like an HMM) but also selects actions to maximize cumulative reward, affecting the state transitions.

Observability refers to the degree to which an agent can perceive the true state of its environment, defining a spectrum of decision-making problems.

• Fully Observable: The agent's sensors give a complete, accurate description of the state (modeled as an MDP). Example: A chess board.
• Partially Observable: The agent receives incomplete or noisy sensory data (modeled as a POMDP). Example: A poker player who sees only public cards and their own hand.
• Unobservable: The state is entirely hidden, and the agent must rely solely on its actions' effects (closely related to bandit problems). The level of observability dictates the required agent architecture. POMDP agents must integrate perception (belief updating) with planning and control, often requiring memory or recurrent networks.

Recurrent Neural Networks (RNNs) and Long Short-Term Memory (LSTM) networks are deep learning architectures used to approximate the belief state and policy in POMDPs. Because a POMDP agent must remember history, these networks provide a learned memory mechanism.

• They process a sequence of observations and actions, maintaining a hidden state that acts as a compressed representation of the agent's history.
• This hidden state effectively functions as an approximate, non-parametric belief state.
• In Deep Reinforcement Learning for POMDPs (e.g., DRQN, POMDP-solving with neural networks), an RNN/LSTM is often the core of the policy or Q-network, allowing the agent to handle partial observability without explicitly calculating Bayesian belief updates.

An information state (or history) is the complete record of all actions taken and observations received by an agent since the start of an episode. In a POMDP, it is the raw data from which a belief state is derived.

• Formally, it is the sequence (a0, o1, a1, o2, ..., a_t-1, o_t).
• The belief state is a sufficient statistic of this history, meaning it contains all information needed for optimal decision-making.
• In practical algorithms, maintaining the full history is infeasible, leading to the use of belief states or recurrent network approximations. The concept underscores that in partially observable settings, an agent's policy cannot be a function of the current observation alone; it must be a function of this accumulated information.