Markov decision problem

The Markov decision problem ( MEP , also Markov decision process or MDP for Markov decision process) is a model of decision problems named after the Russian mathematician Andrei Andrejewitsch Markow , in which the usefulness of an agent depends on a sequence of decisions. The Markov assumption applies to the state transitions, i. H. the probability of reaching a state from state depends only on and not on predecessors of . ${\displaystyle s'}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$

Formal definition

A MEP is a tuple , where ${\displaystyle (S,A,T,r,p_{0})}$

• ${\displaystyle S}$ a lot of states
• ${\displaystyle A}$ a lot of actions,
• ${\displaystyle T}$is the action model (also transition probability ) , so that the probability is from the state and execution of the action to get into the state . ${\displaystyle T\colon S\times A\times S\rightarrow [0,1]}$ ${\displaystyle T(s,a,s')=p(s'|s,a)}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s'}$
• ${\displaystyle r\colon S\times A\times S\rightarrow \mathbb {R} }$ is the reward function that assigns a reward to every transition from the last to the current state and
• ${\displaystyle p_{0}\colon S\rightarrow \mathbb {R} }$ is the start distribution that indicates for each state how likely it is to start in this state.

example

An MEP is when a robot has to navigate a maze to a destination. The set of states is the set of positions of the robot and the actions are the possible directions in which the robot can move.

solution

The solution to an MEP is a function that outputs the action for each state that maximizes profit over time. Well-known solution methods include the value iteration method and reinforcement learning . ${\displaystyle \pi \colon S\rightarrow A}$

Web links

• PPT presentation (English) (PDF; 739 kB)