Markov decision process
In plain wordsA 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.
The standard formalism for sequential decision-making under uncertainty with fully observed states, defined by a set of statesstate, 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., a set of actionsaction, 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., transition probabilities p(s′ | s, a), a reward functionreward function, n.: The rule that decides how many points an AI agent earns for each situation and action — in effect, the written-down definition of the task it is being trained to do. and usually a discount factordiscount factor, n.: A number between 0 and 1 that makes an AI agent value future rewards less than immediate ones — like preferring a dollar today to a dollar next year. γ, sometimes with an initial-state distribution and a horizon. Its defining assumption is the 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.: the next state and reward depend only on the current state and action, not on earlier history. A solution is a 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. that maximizes expected returnreturn, n.: The total reward an AI agent collects from now until the end of a task, usually counting near-term rewards more than distant ones. Agents are trained to make this total as large as possible.. With a known model, finite MDPs are solved by dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step. (value iterationvalue iteration, n.: A step-by-step method for finding the best strategy when all the rules and rewards of a problem are known: repeatedly re-score every situation from the scores of the situations it can lead to, until the scores stop changing., policy iterationpolicy iteration, n.: A method for finding the best strategy in a fully known problem by alternating two steps: work out how good the current strategy is, then switch to better choices wherever possible, until nothing improves.) or linear programming; reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time. addresses the case in which the agent must learn from sampled experience instead. Extensions include the 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., semi-MDPs for actions of varying duration, constrained MDPs, and stochastic (Markov) games with several agents.
We framed inventory control as an MDP whose state is the stock level and whose actions are order sizes.
Origin
Richard Bellman introduced the framework in 'A Markovian Decision Process' (Journal of Mathematics and Mechanics, 1957), building on his dynamic programming and on Lloyd Shapley's stochastic games (1953). Ronald Howard's book Dynamic Programming and Markov Processes (1960), with its policy-iteration algorithm, popularized MDPs in operations research; RL adopted them as its foundation in the late 1980s.
Usage note
Real problems are rarely exactly Markov; practitioners make them approximately so by enriching the state, for example by stacking recent frames or adding memory.
Related
- 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.
- 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.
- Bellman equationBellman 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.
- dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step.
- 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.
- reward functionreward function, n.: The rule that decides how many points an AI agent earns for each situation and action — in effect, the written-down definition of the task it is being trained to do.
- 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.
Sources
- Bellman, R. (1957). A Markovian Decision Process. Journal of Mathematics and Mechanics 6(5), 679–684.
- Howard, R. A. (1960). Dynamic Programming and Markov Processes. MIT Press.
- Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley.
Mentioned in
reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time., automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., Bellman equationBellman 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., discount factordiscount factor, n.: A number between 0 and 1 that makes an AI agent value future rewards less than immediate ones — like preferring a dollar today to a dollar next year., dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step., 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., intelligent agentintelligent agent, n.: In AI theory, a decision-maker, such as a robot, a self-driving car, a chess program or a helpful piece of software, that notices what is going on around it and responds in ways that serve its goals., linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input., 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 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., multi-agent reinforcement learningmulti-agent reinforcement learning, n.: Reinforcement learning with several AI agents learning at once in a shared world, where each must adapt to the others — as teammates, rivals or both., 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., power-seekingpower-seeking, n.: The tendency of a goal-pursuing AI to gather resources, influence and options — and to resist being stopped — because these help with almost any goal it might have., reward functionreward function, n.: The rule that decides how many points an AI agent earns for each situation and action — in effect, the written-down definition of the task it is being trained to do., Richard BellmanRichard Bellman, prop. n.: An American mathematician who invented dynamic programming, a way of solving long chains of decisions step by step, which became the mathematical core of reinforcement learning., 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., Chris WatkinsChris Watkins, prop. n.: A British computer scientist who invented Q-learning in 1989, a simple way for an agent to learn which action is best in each situation purely from trial and error., decision theorydecision theory, n.: The study of how to make the best choice when outcomes are uncertain, by weighing how likely each result is against how much it matters., hierarchical reinforcement learninghierarchical reinforcement learning, n.: Reinforcement learning organized in layers, where a high-level part chooses goals or skills — 'go to the kitchen' — and lower-level parts handle the detailed actions to achieve them., 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., policy iterationpolicy iteration, n.: A method for finding the best strategy in a fully known problem by alternating two steps: work out how good the current strategy is, then switch to better choices wherever possible, until nothing improves., reward hypothesisreward hypothesis, n.: The idea that every goal can be expressed as maximizing a single running score — that whatever we want an agent to do, we can say it with points., safe reinforcement learningsafe reinforcement learning, n.: Reinforcement learning designed to avoid dangerous or unacceptable behavior — both in what the finished agent does and in the risky experiments it might try while still learning., value iterationvalue iteration, n.: A step-by-step method for finding the best strategy when all the rules and rewards of a problem are known: repeatedly re-score every situation from the scores of the situations it can lead to, until the scores stop changing.