COMP 3200 - Intro to Artificial Intelligence - Lecture 16 - Bandit Algorithms + Explore vs Exploit
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
- Exploration can be worthwhile even when it produces a low reward, because learning that an action is poor can prevent repeated losses later.
- Sample averages are appropriate when reward distributions are stationary, while a constant step size alpha adapts more readily when those distributions change.
- Greedy selection can lock onto an initially favored action and leave alternatives unexplored; epsilon-greedy prevents this by assigning a nonzero probability to random trials.
- Fixed epsilon creates a lasting exploration cost, so reducing epsilon as estimates become more reliable can improve long-run reward.
- Upper confidence bounds combine estimated reward with an uncertainty bonus, prioritizing actions that may be promising but have been sampled relatively few times.
- In a sequential decision problem, an action's value depends on the state where it is taken, making Q(s,a) the relevant representation rather than Q(a) alone.
Chapters
- Exploitation chooses actions already believed to have high value, while exploration tries unfamiliar or less-tested actions.
- Trying an action can yield a lower reward but still provide useful information about what to avoid.
- Repeatedly observing the same reward can increase confidence in an estimate, so learning includes strengthening existing knowledge.
- An N-armed bandit offers N actions, each producing rewards from its own stationary probability distribution.
- With a limited budget such as $100 or a fixed number of trials, the goal is to choose actions that maximize cumulative reward.
- The problem has two parts: maintaining action-value estimates and deciding which action to test next.
- The greedy action is the action with the largest current estimated value, written Q_t(a).
- Q*(a) denotes an action's true expected reward, while Q_t(a) is the estimate available after t steps.
- As repeated samples accumulate, an estimate can converge toward the true mean under the law of large numbers.
- For four actions, an array of four Q values can store the current estimate for each action.
- A common initialization sets every estimate to zero, although later examples show that initialization can affect which actions are selected.
- A high estimate after many trials does not guarantee certainty if other actions have been sampled only a few times.
- The example's four reward distributions are constant 5, either -20 or 20, uniform from 0 to 10, and uniform from -10 to 10.
- Their expected rewards are 5, 0, 5, and 0 respectively, so actions 1 and 3 tie for the highest long-run mean.
- A single reward can be misleading: the high-variance second action may produce either a large loss or a large gain.
- If action a has been selected K_a times, its sample-average estimate is the sum of its observed rewards divided by K_a.
- When K_a is zero, the estimate needs a default value, set to zero in the lecture's worked example.
- After eight selections across four actions, the example updates each action's estimate using only the rewards observed for that action.
- Storing and resumming every reward becomes impractical when training involves millions or billions of actions.
- The sample average can be updated using the previous estimate and one new reward: Q_{k+1} = Q_k + 1/(k+1)(R_{k+1} - Q_k).
- This update requires only the current estimate, the new reward, and the action count rather than the full reward history.
- A fixed step size alpha replaces 1/(k+1) in the incremental update: Q_new = Q_old + alpha(R - Q_old).
- If a machine changes from paying 5 to paying 100 after a million trials, a full-history average will respond extremely slowly.
- A constant alpha gives recent rewards more influence, making it useful when reward distributions may change over time.
- With an old estimate of 50 and a new sample of 100, alpha = 1 moves the estimate to 100, while alpha = 0.5 moves it to 75.
- Alpha = 0 leaves the estimate unchanged; alpha = 1 trusts the latest sample completely.
- A smaller learning rate, often below 0.1 in practice, reduces the impact of a single unusually lucky or unlucky reward.
- Greedy selection always chooses the action with the highest current Q value and therefore exploits without deliberately testing alternatives.
- With zero initial values, selecting the first action and receiving reward 5 can make it remain greedy indefinitely, leaving other actions untested.
- Optimistic initial values can encourage early exploration in some settings, but their usefulness depends on reward scales and whether the task seeks maximums or minimums.
- Epsilon-greedy selects a random action with probability epsilon and otherwise directly selects a greedy action.
- When epsilon is 0.1 and there are four actions, random selection chooses the greedy action 2.5% of the time, in addition to the 90% direct-greedy selections.
- A nonzero fixed epsilon ensures every action is sampled repeatedly over an unlimited run, although convergence may take a long time.
- With epsilon = 0, an agent may fail to discover better actions because it never explores beyond its initial greedy choice.
- Epsilon = 0.1 can learn quickly but continues making random choices 10% of the time, reducing reward even after good estimates are available.
- A smaller value such as epsilon = 0.01 may learn more slowly but can achieve higher long-run reward; a practical strategy is to reduce epsilon over time.
- The training loop initializes Q values and per-action counts N, then chooses an action using epsilon-greedy selection.
- After receiving reward R, it increments N_a and updates Q_a with Q_a + (1/N_a)(R - Q_a) for the sample-average version.
- The same algorithm structure can use a fixed alpha instead of 1/N_a when recent rewards should receive greater weight.
- Upper confidence bound selection scores an action using its estimated value plus an uncertainty bonus, commonly Q_t(a) + C√(ln(T)/N_t(a)).
- The bonus grows when total trials T increase without additional samples of action a, and shrinks as N_t(a) increases; C controls the exploration tradeoff.
- For reinforcement-learning environments, action value depends on the current state, so Q(s,a) is more informative than a state-independent Q(a).
- Exam topics include incremental updates, worked bandit calculations, greedy and epsilon-greedy selection, UCB, and bandit-algorithm pseudocode.
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.