POMDP (Partially Observable Markov Decision Process)

The observation space is the set of all possible perceptual inputs or measurements the agent receives. After taking an action, the agent receives an observation o ∈ O that provides noisy, incomplete evidence about the new hidden state. For instance, a camera image or a lidar scan is an observation, not the true state.

The transition model is a probability function T(s' | s, a) that defines the dynamics of the environment. It specifies the likelihood of transitioning to state s' given the current state s and the action taken a. This model captures the inherent uncertainty in how the world evolves.

The observation model is a probability function Z(o | s', a) that defines the sensor's reliability. It specifies the likelihood of receiving observation o given that the action a was taken and resulted in the new (hidden) state s'. This model accounts for sensor noise and partial observability.

The reward function R(s, a) provides an immediate scalar feedback signal received when action a is taken from state s. The agent's objective is to maximize the expected cumulative sum of discounted rewards over time, trading off immediate and future gains.

The belief state is a probability distribution over the state space S, representing the agent's internal estimate of the world. Since the state is hidden, the agent maintains b(s), the probability of being in each state s. This belief is updated using Bayes' rule after each action and observation.

A policy π is a mapping from belief states to actions (a = π(b)). It defines the agent's strategy. An optimal policy maximizes the expected total reward. In POMDPs, policies are functions over the continuous, high-dimensional space of belief states, making computation complex.

Conversational agents use POMDPs to manage the belief state of user intent, which is never directly observed but must be inferred from ambiguous utterances.

• Spoken Dialogue Systems: Handling speech recognition errors and linguistic ambiguity. The agent chooses clarification questions or confirmations to reduce uncertainty about the user's goal efficiently.
• Tutoring Systems: Modeling a student's hidden knowledge state and selecting the next pedagogical action (hint, example, new problem) to maximize learning gains.
• Customer Service Bots: Navigating complex service menus and troubleshooting trees where the customer's actual problem is revealed gradually.

Financial markets are partially observable; true asset values and market maker intentions are hidden. POMDPs model this to execute trades optimally.

• Optimal Trade Execution: Minimizing market impact and transaction costs when liquidating a large position, where the true liquidity and other traders' actions are unknown.
• Market Making: Setting bid-ask spreads based on a belief about the true price and inventory risk.
• Portfolio Rebalancing: Under hidden macroeconomic regimes, deciding asset allocations to maximize long-term returns while managing risk.

Contingent planning is a classical planning paradigm that deals with partial observability and sensing actions. Unlike a POMDP's probabilistic model, it often uses a deterministic model with unknown initial conditions or nondeterministic action effects.

• Solutions are conditional plans (e.g., policy trees) that specify different future actions based on the outcomes of specific sensing actions.
• It is closely related to POMDPs but typically avoids explicit probability distributions, focusing on guaranteed achievement of goal conditions for all possible contingencies.
• Used in domains like robotics and diagnosis where certain informative observations can be made.

Model-Based Reinforcement Learning refers to RL agents that learn an internal model of the environment's dynamics (transition function) and reward function. This model can then be used for planning, such as via simulated rollouts.

• A POMDP can be seen as the formal model for a model-based RL problem under partial observability.
• Algorithms like POMCP (Partially Observable Monte Carlo Planning) combine Monte Carlo Tree Search with a learned or known POMDP model to plan in belief space.
• This approach is often more sample-efficient than model-free RL but requires accurate model learning.

A Hidden Markov Model is a simpler statistical model that forms a core component of the POMDP's observation model. An HMM models a system with an unobserved (hidden) state that evolves via Markov dynamics and emits observable outputs.

• A POMDP extends the HMM by adding actions (which influence state transitions) and rewards (which define objectives).
• The belief update in a POMDP is directly analogous to the filtering problem in an HMM (e.g., solved by the Forward Algorithm or Kalman Filter for continuous states).
• Understanding HMMs is foundational for grasping state estimation in POMDPs.

QMDP and Point-Based Value Iteration are two major classes of approximate algorithms for solving POMDPs.

• QMDP is a simple but effective approximation that assumes full observability after one step. It solves the underlying MDP to get a Q-function, Q(s,a), and then acts based on the expected Q-value over the current belief. It ignores the information-gathering value of actions.
• Point-Based Value Iteration (PBVI) algorithms (e.g., HSVI, SARSOP) are a more advanced family. They sample a set of reachable belief points and perform value iteration only over this set, representing the value function as a set of alpha-vectors. This makes solving larger POMDPs computationally tractable.