POMDP (Partially Observable Markov Decision Process)

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.

A Markov Decision Process is the fully observable foundation for the POMDP. It is a mathematical framework for modeling sequential decision-making, defined by a tuple (S, A, P, R, γ).

• S: A finite set of states.
• A: A finite set of actions.
• P: Transition probabilities, P(s'|s,a), defining the dynamics.
• R: A reward function, R(s,a,s').
• γ: A discount factor. The agent always knows the exact current state s. The core solution is an optimal policy π(s) that maximizes expected cumulative reward, found via algorithms like Value Iteration or Policy Iteration using the Bellman equation.

A belief state is a probability distribution over all possible states of the world, representing the agent's internal knowledge in a POMDP. Since the true state is hidden, the agent maintains this belief, b(s), which is a sufficient statistic for the history of actions and observations.

• It is updated after each action a and observation o using Bayes' rule via a belief update function.
• The POMDP problem is reformulated as a belief MDP, where the continuous belief space becomes the new state space.
• Planning algorithms like POMCP or QMDP operate directly over this belief space to choose actions.

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.