Partially observable Markov decision process

Key takeaways

Partially observable Markov decision process belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Partially observable Markov decision process to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Partially observable Markov decision process from memory before moving on to harder problems.

Reference excerpt

A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process (MDP). A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot directly observe the underlying state. Instead, it must maintain a sensor model (the probability distribution of different observations given the underlying state) and the underlying MDP. Unlike the policy function in MDP which maps the underlying states to the actions, POMDP's policy is a mapping from the history of observations (or belief states) to the actions. The POMDP framework is general enough to model a variety of real-world sequential decision processes. Applications include robot navigation problems, machine maintenance, and planning under uncertainty in general. The general framework of Markov decision processes with imperfect information was described by Karl Johan Åström in 1965 in the case of a discrete state space, and it was further studied in the operations research community where the acronym POMDP was coined. It was later adapted for problems in artificial intelligence and automated planning by Leslie P. Kaelbling and Michael L. Littman. An exact solution to a POMDP yields the optimal action for each possible belief over the world states. The optimal action maximizes the expected reward (or minimizes the cost) of the agent over a possibly infinite horizon. The sequence of optimal actions is known as the optimal policy of the agent for interacting with its environment.

Definition

Formal definition A discrete-time POMDP is a 8-tuple ( S , A , O , T , T 0 , O , R , N ) {\displaystyle ({\mathcal {S}},{\mathcal {A}},{\mathcal {O}},\mathbb {T} ,\mathbb {T} _{0},\mathbb {O} ,R,N)} , where

S {\displaystyle {\mathcal {S}}} is a set, denoting the state-space,

A {\displaystyle {\mathcal {A}}} is a set, denoting the action-space,

O {\displaystyle {\mathcal {O}}} is a set, denoting the observation-space,

T ( s t + 1 | s t , a t ) : S × S × A → [ 0 , 1 ] {\displaystyle \mathbb {T} (s_{t+1}|s_{t},a_{t}):{\mathcal {S}}\times {\mathcal {S}}\times {\mathcal {A}}\to [0,1]} is a probability measure, defining the (Markovian) system dynamics

T 0 ( s ) : S → [ 0 , 1 ] {\displaystyle \mathbb {T} _{0}(s):S\to [0,1]} is a probability measure, defining the distribution of initial states.

O ( o t + 1 | s t + 1 , a t ) : O × S × A → [ 0 , 1 ] {\displaystyle \mathbb {O} (o_{t+1}|s_{t+1},a_{t}):{\mathcal {O}}\times {\mathcal {S}}\times {\mathcal {A}}\rightarrow [0,1]} is a probability measure of observations in a given state and after a given action,

R : ( O × A ) N × O → R {\displaystyle R:({\mathcal {O}}\times {\mathcal {A}})^{N}\times {\mathcal {O}}\to \mathbb {R} } is the reward function for episodes τ ∈ ( O × A ) N × O {\displaystyle \tau \in ({\mathcal {O}}\times {\mathcal {A}})^{N}\times {\mathcal {O}}}

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Partially observable Markov decision process

Start with the simplest possible case. Write down what Partially observable Markov decision process claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Partially observable Markov decision process before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Partially observable Markov decision process ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Partially observable Markov decision process

In research: Partially observable Markov decision process appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Partially observable Markov decision process in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Partially observable Markov decision process is common in secondary-school and first-year university syllabi. It links to neighbouring topics Dynamic programming, Markov processes, Stochastic control, so understanding it makes those chapters shorter.
In everyday life: Look for Partially observable Markov decision process outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Partially observable Markov decision process in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Partially observable Markov decision process means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Partially observable Markov decision process out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Partially observable Markov decision process in simple terms?

A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process (MDP). A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot directly observe the underlying state.

Why does Partially observable Markov decision process matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Partially observable Markov decision process?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Partially observable Markov decision process.