COMP 3200 - Intro to Artificial Intelligence - Lecture 17 - MDP + Dynamic Programming
Overview
Dave Churchill explains how finite Markov decision processes represent reinforcement-learning tasks using states, actions, transition probabilities, rewards, and a discount factor, then derives how policies determine state and action values. He connects those ideas to Bellman-based dynamic programming for evaluating values and improving policies, while noting that exact dynamic programming requires a complete environment model and motivates temporal-difference learning when that model is unavailable.
Key takeaways
- A Markov state must contain enough information to predict the next state and reward from the current state and action; otherwise, decision-making may require history.
- A finite MDP is defined by S, A, P, R, and gamma, where P is the transition model, not the policy.
- State value is policy-dependent: for neighboring values 20, 0, 10, and 30, equal probabilities produce value 15, while choosing only the action leading to 30 produces value 30.
- The Bellman expectation equation evaluates a policy by combining action probabilities, transition probabilities, immediate rewards, and discounted next-state values.
- Policy improvement assigns probability only to actions leading to maximum-value outcomes, splitting probability evenly across ties.
- Exact dynamic programming needs a complete model of transitions and rewards; temporal-difference learning can apply related value-propagation ideas when that model is unavailable.
Chapters
- A state is Markov when it contains all information needed for an optimal decision, so the full state history is unnecessary.
- Chess illustrates the property: the current board captures relevant information, regardless of the sequence of moves that produced it.
- Dave Churchill contrasts this with a League of Legends Baron attempt, where earlier observations of enemy health and damage may be needed.
- A finite Markov decision process is specified by S, A, P, R, and gamma, remembered as “SAPRI.”
- S and A are the finite state and action sets; P gives the probability of reaching state S-prime after taking action A in state S.
- R specifies reward for a transition, while gamma is the discount factor; partially observable settings are called POMDPs.
- A teleport example assigns 50% probability each to landing in a gold chest or a fire room after an action.
- The MDP objective is to choose a policy that maximizes expected discounted future rewards.
- Gamma weights a reward k steps ahead by gamma to the power k: gamma = 0 values only the next reward, while gamma = 1 treats future rewards equally.
- With gamma = 0.5, successive rewards receive weights 1, 0.5, 0.25, and so on.
- Factoring gamma from the return shows the recurrence: current return equals the next reward plus gamma times the following return.
- Episodic tasks, such as one hand of Blackjack or one maze run, end at a terminal state and have a finite return.
- Continuing tasks, such as a factory robot operating indefinitely, do not naturally divide into episodes.
- The unified treatment converts an episodic task into an infinite sequence by adding an absorbing state that loops forever with zero reward.
- An action value Q depends on both the state and chosen action, because moving up can be useful in one location and harmful in another.
- A reward describes an immediate outcome, while a value estimates expected future return and therefore depends on what the policy does next.
- The same state can be valuable under a policy that chooses a reward-bearing action and poor under one that leads to fire or a dragon.
- V-pi(S) is expected return from state S while following policy pi; Q-pi(S,A) additionally fixes the first action as A.
- Dynamic programming computes solutions through relationships between a state’s value and values of neighboring states.
- A fall from an airplane can have modest immediate reward but a highly negative overall value because the future state is catastrophic.
- The method first computes a value function, then uses those values to select a policy.
- For neighboring values 20, 0, 10, and 30, an equiprobable policy over four actions gives the center state value (20 + 0 + 10 + 30) / 4 = 15.
- A deterministic policy that moves right gives value 10, while a policy split equally between left and up gives value 25.
- The example assumes zero immediate rewards and gamma = 1, isolating how policy probabilities weight neighboring values.
- A risky unicycle example also shows that a 10% chance of a -10,000 outcome can outweigh a 90% chance of a +10 outcome.
- The Bellman expectation equation computes V-pi(S) by summing over actions and possible next states.
- Each contribution combines policy probability pi(A|S), transition probability P(S-prime|S,A), reward R, and discounted next-state value gamma V-pi(S-prime).
- For deterministic transitions, the transition probability is 1; in Churchill’s grid example, zero rewards and gamma = 1 reduce the calculation to averaging neighboring values.
- For an equiprobable four-action policy, each action contributes probability 0.25; a deterministic policy assigns probability 1 to its chosen action.
- The pseudocode initializes V(S) to zero, loops over each legal action, and adds its policy probability times reward plus gamma times the next-state value.
- In the four-neighbor example, each action contributes 0.25 times its neighboring value, producing 5, 0, 2.5, and 7.5 for a total of 15.
- The loop directly implements the Bellman summations, making the equation a practical calculation rather than only a formula.
- Policy improvement chooses actions that lead to the highest-valued next states, using the current value estimates.
- The update tracks all maximizing actions: a newly higher value clears the previous candidates, an equal value is added, and a lower value is ignored.
- When actions tie, probability is divided evenly among them; a tie between up and left gives each probability 0.5.
- For action values 7, 0, 10, 5, and 10, the improved policy assigns 0.5 to actions three and five, and zero to the others.
- Exact dynamic programming requires storing state values and knowing transition probabilities, which is often infeasible in complex environments.
- In Blackjack, determining the probability of reaching a winning state from 16 against a dealer’s 4 may require solving the game first.
- Churchill identifies temporal-difference learning as a practical way to reuse dynamic-programming ideas without a complete transition model.
- Policy iteration alternates value evaluation under the current policy with policy improvement based on those values, repeating until convergence.
- The reinforcement-learning loop begins with a policy, takes actions, observes states and rewards, updates values, then updates the policy.
- Churchill flags exam questions on Q versus V, the SAPRI definitions, Bellman value calculations, and policy updates from maximizing actions.
Transcript excerpt
0:00 Lecture number 18. Um just let you know this lecture we're going to be talking about what's here, continuing tasks, MDPs, and dynamic programming. But uh this lecture it's a bit strange because I talk about sort of three independent things, and then at the end we sort of tie them all together. So, if it seems a bit strange, why is he talking about this? It's in the order that the book introduces it. And uh what I've done here, which I probably should have been doing from the beginning, also I'm just linking you to the chapters in the book where this is talked about because if you're studying for the exam, it's nice to be able to just go straight there. Um like I mentioned before, has anyone actually looked at the textbook at all yet? Nobody? Okay. I know that you don't want to, but uh trust me, it's actually like
0:47 a really good read. And if you follow these links, you'll be taken to the HTML version, but if you um if you either go back to the start of the book and the HTML version, or you just Google reinforcement learning textbook, you'll be met with the free downloadable PDF. Um but here are the sections because it does go into more detail, and even though the exam isn't going to talk about that extra detail, knowing that extra detail certainly will make you understand it more when it comes to answering questions on the exam. So, that's why I put it there. So, we'll be talking about uh Markov decision processes, uh continuing tasks, and dynamic programming. So, first uh MDPs, what is an MDP? Well, I'll get to that first, but in order to talk about MDPs, we need to know what uh Markov means. And Markov
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.