Markov Decision Processes: States, Actions and Return
A Markov decision process describes states, actions, transition probabilities and rewards. In the discounted model, an agent seeks to maximize expected return. The discount controls the weights on later rewards without imposing a fixed stopping time.
What a learner can do afterwards
- Write a small described task as an MDP and say what each part holds
- Compute discounted returns along short trajectories and their probability-weighted expected return
- State the Markov assumption and identify when a chosen state representation omits information needed for the next outcome
1 · Read
A Markov chain describes state changes. A Markov decision process, or MDP, adds choices and rewards. A discounted MDP has five parts: states, available actions, a transition rule, a reward rule and a discount gamma. The state describes the situation. An action is a choice. A reward is the score received after an action; it can be negative. Gamma sets the weights on later rewards.
For each state and available action, the transition rule gives probabilities for the next state. Those probabilities must be nonnegative and sum to 1. Different actions can give different probabilities from the same state. A reward rule specifies the reward, or its distribution, for a transition. A policy specifies how the agent chooses actions.
A courier has states Depot, Road and Done. At Depot, Move reaches Road with reward 3; Wait stays at Depot with reward 0. At Road, Wait stays at Road with reward 6; Finish reaches Done with reward 4. Every listed transition is certain. Done is terminal, with no more actions or rewards. Set gamma to 0.5. The trace shows one episode: Move, Wait, Finish.
The return on one trajectory is its discounted sum of rewards. List rewards in the order received after actions. For rewards r0, r1 and r2, the return is G = r0 + gamma * r1 + gamma^2 * r2. The first reward has weight 1. Each additional step adds another factor of gamma. The agent's objective is expected return, averaged over possible trajectories.
To calculate a return, multiply each reward by its step's discount weight, then add. For the courier's rewards 3, 6 and 4 with gamma 0.5, the weights are 1, 0.5 and 0.25. The contributions are 3, 3 and 1, so G = 3 + 3 + 1 = 7. The third reward uses gamma squared, not gamma again.
For 0 <= gamma < 1, later reward weights decrease geometrically. A smaller gamma makes them decrease faster. It does not force rewards to stop after a fixed number of steps. Gamma 0 counts only the first reward. Gamma 1 gives equal weights in a finite episode; an infinite undiscounted sum needs separate conditions to be finite.
To find expected return for finitely many possible trajectories, calculate each trajectory's return, multiply it by that trajectory's probability, then add. For example, returns 4 and 8 with probabilities 0.25 and 0.75 have expectation 0.25 * 4 + 0.75 * 8 = 7. A high possible return is not the same as a high expected return.
The Markov assumption says that, given the current state and action, earlier history does not change the distribution of the next state and reward. It fixes probabilities, not the particular outcome sampled. To check a state representation, compare histories with the same state and action. If their outcome distributions differ, the representation omits relevant information.
Repair an incomplete state by including the missing information. If a machine's next outcome depends on whether a switch was activated earlier, include that switch status with the current location. If a rule depends only on the last two days, use their pair as the state. A state can contain past information and still satisfy the Markov assumption.
Describe states, actions, transitions and rewards. Discount each trajectory's rewards, then average returns by probability. A Markov state retains the information needed for the next outcome.
Lesson, questions and flashcards written for this dataset.
The reading and three additional questions were written for this dataset.
More to read
From a task to a decision model
Consider a robot that tries to complete a delivery. Its state is Ready or Done. In Ready, it can choose Try or Wait. Try leads to Done with probability 0.6 and reward 5. Otherwise it stays Ready with probability 0.4 and reward -1. Wait keeps it Ready and gives reward 0. Done is terminal, with no further actions or rewards.
This description separates the situation, the robot's choice and the world's response. The probabilities describe what can happen after a choice. The reward describes how the task scores that transition. A policy decides whether to Try or Wait in Ready.
Choose discount gamma = 0.9. A reward received after the first action has weight 1, one after the second has weight 0.9, and one after the third has weight 0.81. These weights do not change the transition probabilities or make the task end at a fixed step.
Each possible episode has its own return. Expected return averages those returns using their probabilities. The largest reward on one possible episode need not identify the best policy.
The state must also retain relevant information. If delivery success depends on a battery level that changes during the task, Ready alone may be insufficient. Include the battery information needed to predict the next state and reward distribution.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Optional connections
This opens up
11 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.