Skip to content
Last Dictionary
Plane
Reinforcement LearningMathematics & Statistics

Markov property

nounAlso: Markov assumption, memorylessness

In plain wordsThe 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.

  1. The property of a stochastic process whose future is conditionally independent of its past given its present 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.. In decision processes the condition includes the current actionaction, n.: A choice an AI agent makes at one moment — move left, place a stone, type a command — which changes its situation and may earn it a reward. and extends to the rewardreward, n.: The score an AI system receives after an action, telling it how good the outcome was. Reinforcement learning trains the system to collect as much reward as possible over time.. The property is what lets a 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. be solved with recursive Bellman equationsBellman equation, n.: A rule saying that how good a situation is equals the reward you get now plus how good the next situation is, slightly discounted — so long-term planning can be solved one step at a time. and lets an optimal policypolicy, n.: An AI agent's strategy: the rule it follows to pick an action in each situation. Training in reinforcement learning means improving this rule until it earns high rewards. depend on the current state alone. Whether it holds depends on how the state is defined: a single Atari frame is not Markov because it hides velocities, but a stack of recent frames approximately is; any process can be made Markov by putting enough history into the state, at the cost of a larger state space. When observations lack the property, the problem is a partially observable Markov decision processpartially observable Markov decision process, n.: A 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..

    A single frame violates the Markov property, so the agent cannot tell which way the ball is moving.

Pr⁡(St+1∣St,At,St−1,At−1,…,S0)=Pr⁡(St+1∣St,At)\Pr\left( S_{t+1} \mid S_t, A_t, S_{t-1}, A_{t-1}, \ldots, S_0 \right) = \Pr\left( S_{t+1} \mid S_t, A_t \right)

Origin

Named after the Russian mathematician Andrey Markov, who from 1906 studied sequences of dependent random variables now called Markov chainsMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example.. The eponymous name for the conditional-independence property spread through probability theory in the following decades, and Bellman's 1957 'Markovian decision process' carried it into decision-making.

Related

See also
  • Markov chainMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example.
  • 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.
  • 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.
  • partially observable Markov decision processpartially observable Markov decision process, n.: A 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.
  • 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.

Mentioned in

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., 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., partially observable Markov decision processpartially observable Markov decision process, n.: A 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.