--- title: "Markov Decision Processes: States, Actions and Return" description: "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 lat" canonical: https://lightmysky.com/learn/computing/markov-decision-processes-states-actions-and-return-mt_bTCO27sgc6 source: https://lightmysky.com/learn/computing/markov-decision-processes-states-actions-and-return-mt_bTCO27sgc6.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Machine Learning · Ages 22 to 24 Page: https://lightmysky.com/learn/computing/markov-decision-processes-states-actions-and-return-mt_bTCO27sgc6 ## Ready when they can - 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 ## Lesson: Writing a choice problem down 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. **Example.** 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. **Example.** 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. *(drawing: Discount weights apply to rewards. They do not change transition probabilities.)* 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. *(drawing: These weights are trajectory probabilities. The returns already include any discount.)* 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. **Recap.** 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.* ## Practice 11 questions on this page, each with its working shown. ## Needs first - [Markov Chains and the Memoryless Assumption](https://lightmysky.com/learn/mathematics/markov-chains-and-the-memoryless-assumption-mt_2wDa_JxJ_o) ## Optional connections - [Dynamic Programming: Optimal Substructure and Overlapping Subproblems](https://lightmysky.com/learn/computing/dynamic-programming-optimal-substructure-and-overlapping-subproblems-mt__hWkCDnzNY) ## Opens up - [Temporal-Difference Learning and Q-Learning](https://lightmysky.com/learn/computing/temporal-difference-learning-and-q-learning-mt_Z78E2llE0C)