A Markov decision process (MDP) models sequential decisions when actions have uncertain outcomes. This lesson introduces the components that describe the situation, the choices available, their consequences, and the rewards received.
A Markov chain describes how a system moves between states according to probabilities. An MDP extends this idea by adding actions chosen by a decision maker. Actions can influence which transitions are likely, while uncertainty can remain in the outcome.
All flashcards
What is a Markov decision process?
A mathematical model for sequential decision-making under uncertainty, in which actions influence transitions between states and outcomes are associated with rewards.
What is the Markov property?
The next state depends on the current state and action, not on the complete history of the process.
What is the state space?
The set S of possible situations or configurations the system can occupy; it can be discrete or continuous.
What does a transition model specify?
It specifies the probability of each next state given the current state and chosen action, such as Pa(s,s′).
What does a reward function describe?
The immediate reward, or expected immediate reward, associated with a transition caused by an action.
Quiz questions
What does a deterministic policy specify in an MDP?Answer: One action to take in each state.
What is the effect of using a smaller discount factor in a discounted-return objective?Answer: It gives less relative weight to rewards farther in the future.
What distinguishes a generative model from an episodic simulator?Answer: A generative model can sample an outcome for a supplied state-action pair.
How does value iteration update state values in a finite MDP?Answer: It maximizes expected immediate reward plus discounted next-state value over actions.
Which problem does a partially observable Markov decision process address?Answer: The decision maker cannot directly observe the true state.