Markov decision process

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A Markov decision process is a model of sequential decision-making defined by states, actions, transition probabilities, and rewards with future dynamics dependent only on the current state and action.

A Markov decision process (MDP) models decisions whose consequences unfold over time. An agent chooses an action in a state, receives a reward, and moves to a new state. The current state and action determine the probability distribution of that next state; an action need not produce the same outcome every time. section 12.1.1 section 12.1.2

Choosing a commute

Suppose driving to work takes 50 minutes in light traffic, 1 hour 7 minutes in medium traffic, or 2 hours in heavy traffic, with probabilities of 30%, 50%, and 20%. Biking has a more predictable estimate of 3 hours 16 minutes. The choice illustrates why planning must account for possible outcomes, not just a single travel-time estimate. section 12.1.1

To describe an agent’s interaction with an MDP, identify:

• The states and permissible actions: what the environment is like and what the agent can do. section 12.1.2
• The transition probabilities and rewards: what may happen after an action and what feedback the agent receives. section 12.1.2
• The policy: the strategy mapping states to actions, either deterministically or through action probabilities. section 12.1.2

In reinforcement learning, the agent tries actions and uses their rewards to improve a policy for expected cumulative reward. This differs from a multi-armed bandit problem: MDP actions affect future states, so later consequences matter. If the agent can observe only part of the environment’s state, a partially observable Markov decision process is the more appropriate model. section 12.1 section 12.1.2

Figure 12.3 An agent learns through interaction with the environment.

Follow the agent–environment loop to see how a chosen action leads to a reward and a new state. section 12.1.2

For a sequential optimization problem, framing states, actions, and rewards turns a search for good decisions into a search for a policy. Routing and dispatch are application areas. Whether the learner has a model of transition dynamics and rewards distinguishes model-based from model-free reinforcement learning. section 12.2 section 12.7

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes

Explains the transition condition and works through states, actions, rewards, and policies using an agent–environment loop.

Examples

Uses uncertain commute times to illustrate transitions and identifies routing and dispatch as optimization applications.

What it assumes

Introduces states, actions, rewards, and policies through basic agent–environment interaction rather than assuming those terms are already known.

What you can do after

Evaluate/understand whether a sequential decision problem needs states and future consequences when framing it for reinforcement learning.

How it connects

Contrasts multi-armed bandits and partially observable Markov decision processes, and connects MDPs to model-based and model-free reinforcement learning.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Reinforcement Learning from Human FeedbackA Markov decision process is a mathematical framework that models states, actions, rewards, and probabilistic transitions for sequential decision making under the Markov property.
• 

  liveBookmanning.com
  Transformers in ActionA Markov decision process is a mathematical model for sequential decision-making in which an agent selects actions in states, receives rewards, and undergoes probabilistic transitions.
• 

  liveBookmanning.com
  Causal AIA Markov decision process is a sequential decision model in which an agent selects actions in states and receives rewards, with future dynamics determined by the current state and action.

Compare how 4 books explain Markov decision process →

Related concepts

• reinforcement learningused by · Reinforcement learning is a machine-learning paradigm in which an agent learns actions or a policy through interaction with an environment and evaluative feedback, such as rewards.
• Markov chaincontrasts with · A Markov chain is a stochastic process of states whose transition probabilities depend on the current state rather than the full preceding history.
• Bellman equationuses · A Bellman equation recursively relates a state or action value to an immediate reward and the expected discounted value of successor states or actions.
• statehas part · State is information or a configuration describing the condition of a system, entity, or computation at a particular time and potentially influencing subsequent behavior or decisions.
• reward signaluses · A reward signal is an evaluative feedback value representing the desirability or payoff of an action, outcome, or state.

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.