partially observable Markov decision process
In plain wordsA version of the standard decision-making model in which the decision-maker cannot see the whole situation — like a poker player who cannot see other hands — and must act on clues and memory.
An extension of the Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice. in which the agentagent, n.: Something that acts. In AI, a program that observes its situation and takes actions toward a goal: a game-playing learner, a software helper, or a chatbot that uses tools to complete tasks. does not observe the statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next. directly but receives observations drawn from an observation function O(o | s′, a), so the same observation can arise from different underlying states. Optimal behavior then depends on the whole history, which can be summarized by a belief state — a probability distribution over states updated by Bayes' rule after each action and observation — turning the problem into a continuous-state 'belief MDP'. Exact solution is intractable in general (finite-horizon planning is PSPACE-complete), so practice relies on approximate point-based solvers, online search or, in deep reinforcement learningdeep reinforcement learning, n.: Reinforcement learning in which a large neural network does the learning, letting an AI learn tasks such as video games or robot control directly from raw inputs like screen pixels or camera images., recurrentrecurrent neural network, n.: A neural network that reads a sequence, such as a sentence or an audio clip, one piece at a time, carrying a running summary forward so that what came earlier can shape how later pieces are understood. or transformertransformer, n.: The design behind today's chatbots and much of modern AI. It handles text by letting every word look at every other word and decide which of them matter for understanding it. policies that compress history into memory. Robot navigation with noisy sensors, dialogue and card games are typical examples.
Because the camera cannot see behind the box, we treat the task as a POMDP and give the policy an LSTM memory.
Origin
Karl Johan Åström formulated optimal control of Markov processes with incomplete state information in 1965, and Richard Smallwood and Edward Sondik gave an exact finite-horizon solution method in 1973. Leslie Kaelbling, Michael Littman and Anthony Cassandra's 'Planning and Acting in Partially Observable Stochastic Domains' (1998) brought POMDPs into mainstream AI.
Related
- Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice.
- Markov propertyMarkov property, n.: The assumption that the future depends only on the present situation, not on how you got there — so knowing the current state is enough to predict what happens next.
- statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next.
- hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.
- Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability.
- recurrent neural networkrecurrent neural network, n.: A neural network that reads a sequence, such as a sentence or an audio clip, one piece at a time, carrying a running summary forward so that what came earlier can shape how later pieces are understood.
- Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice.
Sources
- Åström, K. J. (1965). Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications 10, 174–205.
- Kaelbling, L. P., Littman, M. L. & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence 101(1–2), 99–134.
Mentioned in
environmentenvironment, n.: Everything an AI agent interacts with but does not control — a game, a simulator, a website, the physical world. It answers each of the agent's actions with a new situation and, in reinforcement learning, a score., Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice., Markov propertyMarkov property, n.: The assumption that the future depends only on the present situation, not on how you got there — so knowing the current state is enough to predict what happens next., statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next., agentic reinforcement learningagentic reinforcement learning, n.: Training an AI assistant by rewarding success on long, multi-step jobs where it must use tools, browse, run code and react to what happens, rather than answer in one go., cooperative inverse reinforcement learningcooperative inverse reinforcement learning, n.: A model of a human and an AI working as a team, where only the human knows the goal and the AI must work it out while helping.