COMP 3200 - Intro to Artificial Intelligence - Lecture 18 - Monte Carlo Methods
Overview
Dave Churchill explains Monte Carlo reinforcement learning as a model-free way to estimate state-action values from sampled episodes, then improve a policy using those estimates. A blackjack example shows how to record state-action-reward sequences, calculate returns, and apply every-visit or first-visit updates; the lecture then connects policy evaluation and greedy improvement through generalized policy iteration, with exploration needed to cover neglected state-action pairs.
Key takeaways
- Monte Carlo reinforcement learning estimates values from complete sampled episodes and does not require transition probabilities, making it useful when the environment is available only through interaction or a black-box simulator.
- Action values Q(s,a) directly support policy improvement: for each state, choose the action with the highest estimated return rather than trying to infer action quality from V(s) alone.
- In the blackjack example, the return for every step in a hand with rewards 0, 0, 0, +1 is +1, so each state-action pair in that episode is updated toward a winning outcome.
- First-visit Monte Carlo updates a state-action pair only at its first occurrence per episode; every-visit Monte Carlo updates it at every occurrence.
- Generalized policy iteration alternates policy evaluation through episode returns with greedy policy improvement based on Q values.
- Exploring starts and randomized action selection expose rarely visited states and actions; Monte Carlo ES can avoid convergence to a suboptimal policy under its assumptions, although practical learning may still be slow.
Chapters
- Monte Carlo methods estimate value functions and discover policies using sampled experience.
- Unlike dynamic programming, they do not require complete transition probabilities or a full model of the environment.
- Experience can come from a physical robot or a simulator that returns the next state after an action.
- Uniformly sample points in a unit square and use the fraction inside an inscribed circle to estimate its area ratio, giving pi approximately 4 times the inside fraction.
- The circle-to-square area ratio is pi/4; estimating another decimal place by this method requires substantially more samples.
- For integration, sample points in a bounding rectangle, count points below the function, and multiply their fraction by the rectangle's area.
- Monte Carlo methods are introduced for episodic tasks, where experience runs from an initial state to a terminal state.
- Unlike the earlier slot-machine updates, value estimates are updated only after the episode finishes.
- For a policy π, Vπ(s) is the expected return from state s, while Qπ(s,a) is the expected return after taking action a in s and then following π.
- The example assumes an infinite deck, a $1 bet, rewards of +1 for a win and -1 for a loss, and a 1.5 reward for a natural blackjack.
- Cards count at face value, face cards count as 10, and an ace counts as 1 or 11; the simplified player actions are hit and stand.
- The dealer follows a fixed rule, hitting below 17 and standing at 17 or more, so Churchill treats the dealer as part of the environment rather than an opponent with a changing strategy.
- A blackjack state is represented by the player's current total and the dealer's visible card, such as 7 versus 4.
- The dealer's hidden card is not included in the observed state, so hands with the same player total and upcard are grouped together.
- Hitting draws another card; standing ends the player's decisions and triggers the dealer's fixed policy, with rewards generally delayed until the hand resolves.
- Churchill traces a hand from player total 7 against dealer 4 through hits to 9, 14, and 20, followed by a stand.
- The sample action sequence is hit, hit, hit, stand, and the reward sequence is 0, 0, 0, +1 when the dealer busts.
- The same state and action can produce different outcomes: standing on 20 might win, lose, or push depending on the dealer's cards.
- The return at each time step is the sum of rewards from that point to the episode's end; for the winning blackjack hand, every recorded return is +1.
- Each visited state-action pair, such as player 7 versus dealer 4 with action hit, receives an update toward its observed return.
- Averaging returns across episodes estimates the expected value of each state-action pair; the assignment focuses on Q values rather than state-only V values.
- Every-visit prediction updates a state-action pair every time it occurs in an episode, averaging all returns observed for that pair.
- First-visit prediction updates only the first occurrence of a state-action pair in each episode and skips later occurrences.
- The pseudocode generates an episode under policy π, computes each return, stores it, and sets Q(s,a) to the average of stored returns.
- Dynamic programming needs the probabilities of outcomes such as winning, losing, or pushing after standing on 13 against a dealer 7.
- Monte Carlo methods can estimate those outcomes by playing sampled hands without knowing their probabilities in advance.
- Following one fixed policy can leave actions and states unexplored; Churchill uses unusual chess positions and untested blackjack choices to illustrate this coverage problem.
- Generalized policy iteration maintains both action-value estimates Q(s,a) and a current policy.
- Policy evaluation estimates how well the current policy performs by generating episodes and updating values.
- Policy improvement makes the policy greedy with respect to those estimates, choosing the highest-valued action at each state.
- The Monte Carlo policy-iteration loop starts with initial Q estimates and an equiprobable, or random, policy.
- It generates an episode, updates action values from episode returns, then changes the policy to select actions with maximal estimated Q values.
- With sufficient sampling, value estimates can approach the true values and greedy policy updates can approach an optimal policy; training may stop after a fixed episode count or when the policy stops changing.
- Monte Carlo exploring starts varies initial states so training can sample state-action pairs that the current policy rarely reaches.
- Churchill contrasts chess, which normally begins in one fixed position, with blackjack, where random deals naturally expose many starting states.
- Exploring starts can prevent convergence to a suboptimal policy in theory, but may converge slowly in practice; randomizing action choices also improves coverage.
- The recap emphasizes sampling complete episodes, updating values from returns, and improving policies from updated action values.
- Churchill lists potential exam topics including Monte Carlo definitions, V versus Q, calculations from samples, exploring starts, and generalized policy iteration.
- A matchbox-based MENACE demonstration is announced as supplementary material; its theoretical learning content may be examined, but the demonstration itself is not included in the recorded lecture.
Transcript excerpt
0:00 All right, lecture number 18. Uh we're continuing on with more reinforcement learning, and one of the more uh fun topics, I think, in reinforcement learning, uh which is called Monte Carlo methods. And [clears throat] if you'd like to read more about this or follow along in the textbook, then uh chapter five in the textbook is all about this, and it's one of my uh favorite chapters. If you could have a favorite chapter in a textbook, it seems a little weird, but I I really do like this chapter of the textbook. So what are Monte Carlo methods? They're methods for estimating value functions and discovering optimal policies. So they're one of the reinforcement learning methods that you can use to solve these type of problems. Um so unlike dynamic programming, which was the subject of the uh pre-recorded video that I posted,
0:48 uh Monte Carlo methods do not need um we don't need to assume that we have complete knowledge of the environment or a model of the environment or all of the state transition probabilities or any of that. So Monte Carlo methods um are super powerful in that regards. So they're only going to require experience, which means we have a sequence of states, actions, rewards. So you've seen those state transition diagrams, state action reward, state action reward. Um that's all we need. And we can get those from an actual environment or a simulated environment. And what do I mean by actual or simulated? So actual experience would be something like a physical robot, right? So we have something moving around in the real world. Uh we'll apply voltages to those uh wheels or whatever it uses to get
1:35 around, and it will take some action and then get some reward signal from the
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.