Finite Markov Decision Processes
Use the Markov-property condition to identify an MDP.
From History to State
Reinforcement learning problems can involve an agent making decisions over time. To organize such problems, ask a fundamental question: does the current state contain all the information needed to predict what happens next, without requiring the entire history? If the task satisfies this Markov property, it belongs to the class of Markov decision processes, or MDPs.
The Markov property is the first classification test. Start with a reinforcement learning task, identify its current state, and then ask whether that state provides all the information needed to predict the next state and reward. If it does, the task is an MDP. This definition says what makes a problem an MDP; it does not yet say that the problem is finite.
A Step Through an MDP
Once a problem is represented as an MDP, its interaction can be described as a repeated movement from a current state to a next state. The agent selects an action. The environment responds with a state transition and a reward. The important organizational point is that the current state is the information used to describe and predict the next part of this interaction.
Classifying a State-Based Task
A reinforcement learning task describes a current state, an action selected by an agent, a resulting next state, and a reward. The current state is intended to contain the information needed to predict the next state and reward. What classification follows?
Check the Markov property: The task states that the current state contains the information needed to predict the next state and reward, so it satisfies the Markov-property condition.
Identify the MDP class: A reinforcement learning task that satisfies the Markov property is an MDP.
Check finiteness separately: To decide whether the MDP is finite, inspect whether both its state space and action space are finite.
The task is an MDP. It is a finite MDP only if both its state space and action space are finite.
What do you think happens?
A task satisfies the Markov property, but its state space is not finite. Is it a finite MDP?
Reveal answer
Answer: No, because finiteness requires both the state space and action space to be finite.
The Markov property identifies the task as an MDP. The additional label finite applies only when both the state space and action space are finite.
What Makes an MDP Finite
A finite Markov decision process is an MDP whose state space and action space are both finite. The word finite therefore describes the available states and actions, not the Markov property itself.
| Question | MDP | Finite MDP |
|---|---|---|
| Does the task satisfy the Markov property? | Yes | Yes |
| Must the state space be finite? | Not required by the definition given here | Yes |
| Must the action space be finite? | Not required by the definition given here | Yes |
Use a two-stage classification habit. First ask whether the Markov property holds. If it does, classify the task as an MDP. Then inspect the state and action spaces to decide whether the MDP is finite.
Why Finite MDPs Matter
Finite MDPs are especially important because they provide a general multiple-state formulation for reinforcement learning problems. They narrow the setting by requiring finite state and action spaces, while preserving a large portion of the theory learners need. The source emphasizes that understanding finite MDPs is sufficient for understanding 90% of modern reinforcement learning, making them a practical foundation for study.
Value functions and Bellman equations are central ideas associated with finite Markov decision processes. At this stage, the key connection is organizational: once a reinforcement learning problem has been expressed as a finite MDP, these ideas become central tools for studying the values of states and the relationships among decisions, rewards, and possible future states.
Bandits and Multiple States
A bandit problem is the special case of a reinforcement learning problem with only one state. Finite MDPs provide the general formulation for reinforcement learning problems with multiple states. The central difference is therefore the number of states: one state for the bandit special case, multiple states for the general finite MDP formulation.
Bandit or Multiple-State Problem?
Classify each described formulation using only the number of states provided.
Formulation A: The problem has one state. This matches the special-case definition of a bandit problem.
Formulation B: The problem has multiple states. This matches the general multiple-state formulation provided by finite MDPs, assuming the other finite-MDP conditions are satisfied.
Keep the classification narrow: Do not infer additional properties that are not stated. Use the one-state versus multiple-state distinction first, then check the Markov and finiteness conditions when they are provided.
Formulation A is a bandit problem. Formulation B is a multiple-state problem formulation associated with finite MDPs when its state and action spaces are finite and it satisfies the Markov property.
Common Classification Mistakes
Treating every MDP as finite
The Markov property identifies an MDP, but finiteness additionally requires both a finite state space and a finite action space.
Fix:
Classify the task as an MDP first, then check both spaces separately.Using finite to describe the Markov property
That description concerns the Markov property, not the sizes of the state and action spaces.
Fix:
Use Markov property for the information condition and finite for the state-space and action-space conditions.Treating a bandit as unrelated to MDP-based reinforcement learning
A bandit problem is the special case with only one state.
Fix:
Remember that finite MDPs provide the general multiple-state formulation, while bandits provide the single-state special case.Ignoring the number of states when classifying a problem
The source emphasizes beginning with the one-state versus multiple-state distinction.
Fix:
Check the number of states first, then apply the Markov and finiteness checks that are supported by the description.
When a problem description is incomplete, make only the classification that the description supports. If it states only that there is one state, classify it as the bandit special case. If it states that there are multiple states, continue by checking the Markov property and whether both spaces are finite before calling it a finite MDP.
Practice Classification
A reinforcement learning task has multiple states. Its current state is sufficient for predicting the next state and reward, and both its state space and action space are finite. Classify the task and name the central ideas that become associated with this formulation.
Hints
- Check the Markov property first.
- Then check whether both spaces are finite.
- The source names two central ideas associated with finite MDPs.
A second task has only one state. Should it be classified as a general multiple-state finite MDP or as the special bandit case? Explain your answer using the number of states.
Hints
- Begin with the state count.
- A bandit problem is defined in the source as a one-state special case.
Essential Takeaways
- A reinforcement learning task is an MDP when it satisfies the Markov property.
- An MDP is finite only when both its state space and action space are finite.
- Finite MDPs provide the general multiple-state formulation for reinforcement learning problems.
- A bandit problem is the special single-state case.
- Value functions and Bellman equations are central ideas associated with finite MDPs.
Key Takeaways
- Use the Markov property to identify an MDP.
- Use the state-space and action-space conditions to identify a finite MDP.
- Think of bandits as the one-state special case and finite MDPs as the general multiple-state formulation.
- Treat value functions and Bellman equations as central ideas for studying finite MDPs.
- Classify problems in order: state count, Markov property, then finiteness.