Save this video free

COMP 3200 - Intro to Artificial Intelligence - Lecture 16 - Bandit Algorithms + Explore vs Exploit

Dave Churchill · 1:12:30 · Watch on YouTube

Part of Memorial University of Newfoundland COMP 3200. See all 19 lectures and search them

These notes were made with YouTube Collector. Paste any YouTube link and get the same: a summary, chapters and a searchable transcript.

Overview

David Churchill explains the multi-armed bandit problem as a model for balancing exploitation of known high-value actions with exploration to learn uncertain values. He develops sample-average and constant-step-size updates, compares greedy, epsilon-greedy, and upper confidence bound action selection, and connects bandit values to state-action values Q(s,a) in reinforcement learning.

Key takeaways

Chapters

0:00 Exploration and Exploitation as a Learning Tradeoff
5:00 The N-Armed Bandit as a Limited-Resource Problem
10:00 Greedy Actions and Q-Value Estimates
15:00 Representing Bandit Values and Initial Estimates
20:00 Comparing Rewards in a Four-Action Example
25:00 Sample-Average Estimation from Observed Rewards
30:00 Incremental Updates Avoid Storing Every Reward
35:00 Step Size and Non-Stationary Reward Distributions
40:00 Choosing Alpha to Control How Quickly Estimates Move
45:00 Greedy Action Selection Can Stop Exploration
50:00 Epsilon-Greedy Selection and Random Action Probabilities
55:00 How Epsilon Changes Learning Speed and Long-Run Reward
1:00:00 Bandit Training Loop and Incremental Average Pseudocode
1:05:00 Upper Confidence Bounds and State-Action Values

Keep these chapters and the full searchable transcript in your own library.

Transcript excerpt

0:00 So, today's lecture um exploitation versus exploration and bandit algorithms. So, we talked about this last time, this idea of exploitation versus learning. And that's one of the main challenges uh in reinforcement learning. And we also talked about how that's a challenge in real life and we gave the example of, you know, you go to the restaurant that you're sort of familiar with because you know it'll be at least decent, but you could have gone to another restaurant to see if that one might be better, right? And so we've got to try new things in order to potentially increase our long-term value um in life. So, obtain to obtain a lot of reward, agents have to prefer actions that it knows produce good results. And in order to learn which actions produce good results, you have to try them first. And so we have to balance these two things

0:47 somehow and we'll talk a little bit how to do that in this class. So, we have to exploit the knowledge that we have, but we also have to explore in order to gain more knowledge. And uh so this process of gaining more knowledge we're going to call learning. And so learning is the process of gaining new or modifying existing knowledge. And within the concept or the context of this class, we've learned something if we have information that we didn't have before. So, this is pretty basic. We all know the general concept of learning. But something that may not be obvious is that even if we're given the same results that we saw last time, we're still learning. Because let's say I tried something once and it gave me a value of 100 versus uh I tried it a 100 more times

1:35 and each time it gave me the value of

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.

Want the full transcript?

Save this video in YouTube Collector to get its complete searchable transcript, your own AI summaries, and a library that keeps every video you collect in one place.