What are aExplain Markov decision processes. Show examples and formulars
Report
Chapters 10
Transcript
A cook picks tonight's dish, and that changes what's in the fridge tomorrow. So how do you choose an action by its future payoff rather than its taste? That's the question a Markov decision process answers. State, action, reward — and then a new state.
That loop is the whole idea. An MDP is six pieces in a row. Read them left to right. States: where the agent is.
Actions: what it may do. Transition probabilities: where it lands next. Rewards: what it gets. Policy: a rule for choosing.
And value: the long-run score. Those last two are the ones we actually solve for. An MDP has five parts, written as one tuple: M equals S, A, P, R, and gamma. S is the states — every situation the agent could be in.
A is the actions it can take. P is the transition probabilities. R is the reward. And gamma is the discount factor — how much the future matters.
Here's the heart of it, the Markov property: P of s prime, given s and a. The next state depends only on where you are and what you do — not on the whole history. Picture a three-by-three grid. The agent sits in the centre.
Four actions: up, down, left, right. Move right, and it lands one cell over, every time. Move into a wall, and it stays put. Quick tip: a state isn't everything that happened.
It's everything that matters, packed into one snapshot. Now the return. G is the reward now, plus the next one discounted, plus the one after that discounted twice, and so on. With gamma at zero point nine, a reward two steps away counts zero point eight one of its face value.
Gamma shrinks the future; it only deletes it if gamma is zero. The Bellman backup does this for one state: the reward, plus gamma times the value of where you land, taking the best action with a max. From the centre of our grid, right pays one and lands in a state worth five: one plus zero point nine times five, five point five. Up pays nothing and lands in four, so three point six.
Five point five wins, so the arrow points right. The Markov property: the present state already contains everything the past taught you. So the full history fades to grey — you never need to look back. Here's a real decision.
Cooking from a cold pan: it works eight times in ten, for a reward of plus two. It fails two times in ten, for minus one. So the expectation is 0. 8 times 2, plus 0.
2 times minus 1. That's 1. 6 minus 0. 2, which is 1.
4. A safe action guarantees 1. 2. The risky one is worth 0.
2 more. Set gamma to one, and something breaks. Take a loop that pays one per lap. The return is one, plus one, plus one — forever.
That sum never settles, so the Bellman update has no fixed point. The value is infinite. Back to our two recipes. Recipe A pays one now, and one tomorrow.
Recipe B pays nothing now, but three tomorrow. With gamma at one half, A is one plus a half times one — one point five. B is zero plus a half times three — also one point five. It's a tie.
So here, patience alone decides. Here's a second way to see the same problem. Unroll it into a tree — state, action, state, action, three steps deep — and tag every branch with its probability and its reward. When the horizon is short, or you need to see the whole sequence of choices, this is the better view.
But stretch the horizon and the tree explodes: twenty steps, millions of paths. There, the compact view wins. One value per state, instead of one per path. Six things, in order: states, actions, transitions, rewards, then the policy and value you solve for.
The Markov property: the next state depends only on this state and this action — P of s-prime given s and a. And value is the same idea, measured: the best over actions of reward plus gamma times the next value. The cook picks by value, not by taste. If a value looks wrong, check the discount first.
Still stuck on part of this?
Ask for a video on exactly the bit you need. Your first 2 are free.
Animated by Proverbit, planned with AI