Stanford CS234 Reinforcement Learning I Exploration 1 I 2024 I Lecture 11

Introduction to Reinforcement Learning and Data Efficiency

• Space repetition is helpful in learning, and periodically bringing up ideas from earlier in the course can aid in understanding (36s).
• Important sampling does not leverage the Markov assumption and can work with non-Markov systems, making it a general method that can be used to estimate the value of a policy through rollouts (3m21s).
• Important sampling can be used to estimate the value of a policy by using the advantage function of one policy and sampling from another policy, but this method is not exact due to the difference in states visited by the two policies (3m56s).
• The approximation error of using samples from one policy to estimate the value of another policy is bounded by the average difference between the two policies over the states visited by one policy (4m28s).
• Prior work has shown that it is possible to bound the error in approximating the value of a policy by using samples from another policy, which is a useful insight in reinforcement learning (4m46s).
• The course will now focus on learning from data that can be gathered, rather than relying on prior data or human feedback, and will discuss how to strategically gather data to learn good policies (5m15s).
• The next few lectures will discuss how to gather data for online reinforcement learning, including the influence of the data gathering process on the learning of good policies (5m39s).
• Computational efficiency is an important consideration in reinforcement learning, particularly in simulated environments, where computational time is equivalent to data (6m2s).
• In many domains, computation is separate from actual data, such as using mobile phones for health interventions, consumer marketing, educational technology, and climate or environmental applications, where real-world data is crucial and often limited (7m5s).
• In these cases, computers can be used to compute policies, and real-world data, referred to as samples or sample efficiency, is essential and needs to be utilized carefully to make good decisions (7m55s).

Challenges of Limited Data in Reinforcement Learning

• The data in these domains is often limited, unlike in cases like Atari or AlphaGo, where simulators can generate infinite data (8m17s).
• When working with limited data, it's essential to consider the performance of different algorithms, including whether they converge, converge to the optimal policy, and how quickly they do so (9m1s).
• The convergence of an algorithm is not always guaranteed, and even if it does converge, it may not be to the optimal policy, and the speed of convergence is also crucial (9m10s).
• Different reinforcement learning algorithms can be evaluated using various measures, and their performance can vary significantly, with some algorithms being smooth and consistent, while others may make periodic mistakes (9m47s).
• The performance of an algorithm can be illustrated using a graph of time versus reward, showing how different algorithms can have distinct performance profiles (9m52s).
• There are different types of behavior in algorithms, such as one that is always pretty good but never awesome, and one that guarantees a certain level of performance, which are important to consider when evaluating the quality of algorithms (10m25s).
• The performance guarantees of an algorithm can be thought of in terms of an AI clinician that helps manage blood pressure with a certain level of accuracy, and the difference between an algorithm that is 80% accurate on average versus one that completely manages blood pressure for 80% of the population (10m32s).

Introduction to Bandits and the Multi-Armed Bandit Problem

• The course will introduce different types of settings and ways to evaluate the quality of algorithms, starting with Bandits, which are simple reinforcement learning problems that have been studied since the 1920s and have been used in various application areas (11m11s).
• A Bandit is a simple RL problem with a finite set of arms, or actions, and a probability distribution over rewards for each arm, where the goal is to maximize cumulative reward over time steps (11m52s).
• The Bandit setting can be applied to various areas, such as clinical trials, ads, and treatment or control, where the goal is to randomize the next person or action to take (12m57s).
• A running example for the course will be a silly one, where the goal is to treat patients with broken toes, and there are three options: surgery, buddy taping the broken toe to another toe, or doing nothing, with a binary outcome measure of whether the toe is healed or not after 6 weeks (13m15s).
• The goal is to figure out the best strategy for healing broken toes over time, without doing a clinical trial, but rather by trying different options and observing the outcomes (13m47s).
• A problem can be modeled as a multi-arm bandit with three arms, where each arm is a newly introduced variable with an unknown parameter Theta, representing the probability of a successful outcome (13m56s).
• The multi-arm bandit framework is suitable for this problem because only one decision is made per patient, and the outcome for each patient is independent of the others (15m27s).
• The problem does not have sequential dependence, and each decision is made independently, like a new person arriving at a time point (15m46s).
• The parameter Theta can be between zero and one, indicating that the outcomes are not deterministic, and sometimes the patient will heal, while other times they won't (15m53s).
• The probability distribution of the reward is assumed to be stationary, meaning it remains the same at every time step, and does not change over time (16m15s).

Greedy Algorithms and the Need for Exploration

• A greedy algorithm can be used to solve the problem, which selects the action with the highest expected reward, denoted by Q, and repeats this process (17m11s).
• The expected reward Q can be estimated by counting and averaging the outcomes for each action (17m0s).
• The greedy algorithm starts by sampling all actions once, and then selects the action with the highest observed reward (17m47s).
• In the given example, the true set of parameters shows that surgery is the most effective action, followed by body taping, and then doing nothing (17m29s).
• When applying the greedy algorithm, the arm with the highest observed reward is selected next, which in this case would be arm two, with an observed reward of one (18m24s).
• A greedy algorithm that always chooses the action with the highest estimated value can get stuck in a suboptimal solution, never finding the optimal action, and will not converge to the optimal action (18m31s).
• This is because the algorithm's estimate of the true value of the actions is low, and it will never sample the suboptimal action again, even if it has a higher true value (19m0s).
• To avoid this, some form of exploration is needed to ensure the algorithm does not make an infinite number of bad decisions (19m30s).

Regret in Bandit Problems

• The concept of regret is used to quantify the difference between the decisions made by the algorithm and the optimal decisions, with regret being the opportunity loss or the difference between the expected reward of the optimal action and the expected reward of the action taken (19m44s).
• Regret is often used to score the algorithm based on the gap between the optimal value and the value achieved by the algorithm (19m59s).
• The optimal value is the maximum expected reward, and the regret is the difference between the expected reward of the optimal action and the expected reward of the action taken (20m10s).
• Regret is typically considered in expectation, due to stochasticity in the rewards, and is used to compare the expected reward of the optimal arm to the expected reward of the suboptimal arm (20m36s).
• The goal is to minimize total regret, which is equivalent to maximizing cumulative reward, and this is often the focus in bandit problems (21m7s).
• The regret can be computed by comparing the expected reward of the optimal action to the expected reward of the action taken over all time steps (21m1s).
• The number of times an action is selected, NTA, is used to calculate the regret, with the gap for a particular arm being the difference between the expected reward of the optimal action and the expected reward of the action taken (21m37s).
• The concept of the "Gap" is introduced, which refers to the difference in expected rewards between the optimal action and the action taken, and it plays a crucial role in learning which action is better, with larger gaps requiring fewer samples to figure out and smaller gaps requiring more data (22m29s).
• The Gap (G) is a function of the gaps and counts, representing the number of times each action is taken and the difference between the optimal action and the reward received (22m55s).
• The expected regret is the sum of the times each action is taken multiplied by the Gap, indicating that actions with large gaps should be avoided, while actions close to the optimal action are more acceptable (23m11s).
• Many algorithms aim to bound the regret quantity, which is challenging due to the unknown optimal action and its value, but algorithms can be designed to prove how the regret grows (23m35s).
• The regret can be visualized as a series of actions taken over time, with the true optimal action and observed rewards influencing the regret at each step (24m5s).
• The size of the regret is determined by the Gap between the optimal arm and the arm taken, and making bad decisions forever can result in linear regret (24m48s).
• Ideally, algorithms should strive for constant regret or zero regret, which means making a finite number of bad decisions before learning the optimal arm and taking it forever (25m31s).
• In the worst-case scenario, linear regret can occur if mistakes are made consistently (25m55s).

Epsilon-Greedy Algorithms and Regret Analysis

• Epsilon-greedy algorithms are used to balance exploration and exploitation, where the greedy action is chosen with probability 1 - Epsilon, and a random action is chosen with probability Epsilon (26m20s).
• The regret of Epsilon-greedy algorithms depends on the value of Epsilon, and it is possible to have linear regret if Epsilon is not chosen carefully (26m29s).
• In a setting where there is always at least one action with a non-zero gap, the regret of Epsilon-greedy can be analyzed to determine if it is sublinear or linear (28m14s).
• The value of Epsilon can affect the regret of the algorithm, and it is possible to have linear regret for certain values of Epsilon (28m36s).
• The algorithm's performance can be evaluated by considering the probability of choosing the greedy action versus a random action (27m3s).
• In a specific example, with Epsilon = 0.1, the algorithm chooses the greedy action with 90% probability and a random action with 10% probability (27m15s).
• The regret of the algorithm can be computed and analyzed to determine if it is sublinear or linear (28m1s).
• Epsilon-greedy algorithms have a lower bound on the number of times each arm is sampled, which is at least Epsilon divided by the number of actions times T, where T is the total number of decisions made, resulting in at least linear regret if Epsilon is greater than zero (31m47s).
• If Epsilon is set statically, it can be pretty bad, and decaying Epsilon over time can make a significant difference in the algorithm's performance (32m36s).
• The growth of regret over time steps can be visualized in plots, showing that greedy algorithms can have linear regret, while Epsilon-greedy algorithms can have slightly better but still linear regret, and decaying Epsilon can achieve sublinear regret (32m55s).

Problem-Dependent and Problem-Independent Regret Bounds

• A good algorithm should be able to guarantee sublinear regret without knowing the problem-dependent properties in advance, such as the gaps between rewards (33m34s).
• Problem-independent bounds describe how regret grows as a function of time steps for any possible problem, while problem-dependent bounds describe regret as a function of the gap between rewards (33m52s).
• Problem-dependent bounds are elegant because they don't require the algorithm to know the gaps, but rather adapt to the problem's difficulty, resulting in better regret if the problem is easier to learn (34m25s).
• The gap between rewards is usually less than one, and the consideration of rewards is typically between zero and one, depending on the domain (35m4s).
• In certain domains, the differences or gaps between optimal and suboptimal actions can be really tiny, requiring a lot of data and smart, data-efficient algorithms to optimize, whereas in other cases, the gaps can be large, making it easier to estimate them (35m21s).
• A lower bound by Robbins from the 1950s provides a minimum regret that any algorithm will suffer as a function of the problem, indicating that the regret will be at least log T, where T is the number of time steps or decisions made (36m4s).
• The lower bound also depends on the gap between the optimal and suboptimal arms, with the gap in the numerator, and is considered a problem-dependent or instance-dependent bound because it holds based on the unknown gaps (36m30s).

Optimism Under Uncertainty and Upper Confidence Bound (UCB) Algorithms

• The concept of optimism under uncertainty is a principle that shows why it's provably optimal to be optimistic about things, as it allows for sublinear regret (37m9s).
• Optimism in this context means choosing actions or arms that might have a high value, which can result in either getting high reward or learning something and improving estimates (37m29s).
• When choosing actions that might be good, two possible outcomes are getting high reward, which is the goal, or getting low reward, which allows for learning and improving estimates (37m51s).
• Both outcomes are valuable from the point of view of a reinforcement learning algorithm, as either the goal is achieved or something is learned to avoid making bad decisions in the future (38m48s).
• To leverage information from low rewards, an algorithm is needed to formalize uncertainty, which involves quantifying confidence intervals or uncertainty bounds to make decisions (39m4s).
• The approach involves estimating an upper confidence bound for each action value, ensuring it holds with high probability, and focusing on frequentist high-probability bounds (39m30s).
• The upper confidence bound (UCB) is dependent on the number of times an action has been taken, and the agent will choose the action with the highest UCB (39m48s).
• UCB algorithms are a suite of algorithms that follow this notion, and there are variants, including optimism in the face of uncertainty (OFU) (40m11s).
• The performance of this approach and the quantification of uncertainty will be evaluated, using Hoeffding's inequality, which is a useful inequality for understanding how different the observed average can be from the true mean (40m36s).
• Hoeffding's inequality states that the difference between the empirical estimate and the true estimate decreases exponentially as the number of samples increases, ensuring convergence to the true mean (41m14s).
• The inequality implies that the probability of a large difference between the empirical and true means decreases exponentially with the number of samples, allowing for the estimation of an upper bound on the true expected reward (41m52s).
• The goal is to determine how big the upper bound (u) needs to be set to get an upper bound on the true expected reward, using the equation derived from Hoeffding's inequality (42m26s).
• To construct an upper confidence bound that holds with a certain probability, we use the formula u = sqrt(1/n * log(2/Delta)), where u is the range, n is the number of samples, and Delta is the confidence level (43m9s).
• This formula gives us a range, and if we want the probability that our empirical estimate differs from the true mean by no more than u, it is sufficient to set u equal to this value (43m47s).
• We can then say that the empirical estimate is less than or equal to the expected value of x, which is less than or equal to the empirical estimate plus u, with a probability greater than or equal to 1 - Delta (44m6s).
• This creates an upper confidence bound, which we can use to estimate the upper limit of the true mean (44m9s).
• The UCB1 algorithm uses this upper confidence bound, adding a bonus term to the empirical average, which depends on the number of samples (44m39s).
• The UCB1 algorithm is used at every time step, computing the empirical average and adding the bonus term (44m44s).
• The bonus term is calculated as sqrt(2 * log(t) / n), where t is the time step and n is the number of samples (45m0s).
• The UCB1 algorithm is a variant of the Upper Confidence Bound algorithm, which was first introduced in a paper in 2002 (45m31s).
• The algorithm uses optimism under uncertainty, which is a concept that was around before the 2000s, but was first formally proven in the 2002 paper (45m56s).

UCB1 Algorithm and its Implementation

• The UCB1 algorithm can be used in different settings, such as sampling each arm once and then computing the upper confidence bounds for each arm (46m15s).
• The algorithm then selects the arm with the highest upper confidence bound, which is the argmax of the upper confidence bounds (47m10s).
• Upper confidence bounds (UCB) are used to balance exploration and exploitation in reinforcement learning, with UCB A2 being 1 + √(2 * log(1/Δ)) and UCB A3 being 0 + √(2 * log(1/Δ1)) (47m32s).
• The upper confidence bounds are reduced as more information is gathered, allowing for more informed decision-making (48m0s).
• The value of Δ is chosen to determine the confidence bounds, with the goal of having all confidence bounds hold for all time steps and arms (48m13s).
• Union bounding is used to ensure that all confidence bounds hold simultaneously, taking into account the number of arms and total decisions (Big T) (48m30s).
• The confidence intervals will change over time, causing the algorithm to alternate between arms based on the upper confidence bounds (49m1s).
• With a fixed number of time steps (Big T), Δ can be set to roughly Δ / (T * |A|) using a union bound, where |A| is the number of arms (49m43s).
• This approach is related to false discovery and other concepts in machine learning, and is used to ensure that the confidence bounds are valid at every time step (50m1s).
• The union bound is used to sum over the probability of each event, resulting in a bound of roughly the number of arms times Big T (50m29s).
• Dividing Δ by (T * |A|) is generally sufficient, but can result in a larger log term, which can be mitigated using approaches such as the law of iterated logarithms (50m50s).

Proof Sketch for Sublinear Regret in UCB Algorithms

• A proof sketch is provided to show how a specific type of idea can be used to achieve sublinear regret in reinforcement learning (51m18s).
• The proof is based on a result from a book on banded algorithms by Tor Lattimore and Csaba Szepesvári, which provides a rigorous version of the proof (51m53s).
• The result states that if an arm is suboptimal, the number of times it is pulled in Upper Confidence Bounds scales as a constant C' times log of 1/Delta, where Delta is the gap between the expected reward of the arm and the true reward (53m11s).
• The constant C' does not depend on the number of arms, gaps, or other domain-specific factors, and can be a fixed value such as 37 (53m33s).
• The result is interesting because it shows that if the gap is large, the suboptimal arm will be pulled fewer times, and if the gap is small, it may be sampled more (53m51s).
• Combining this result with another equation can lead to a sublinear regret bound, where the total expected regret is proportional to the number of actions times a constant (54m31s).
• The proof sketch focuses on showing that the number of times a suboptimal arm is pulled is bounded by a constant times log of 1/Delta (54m18s).
• The book by Lattimore and Szepesvári provides a more rigorous version of the proof, which is recommended for further reading (52m15s).

Formal Proof of Sublinear Regret in UCB Algorithms

• The formal proof of the total number of times a particular arm is pulled in a multi-armed bandit problem scales with one over the size of the gap squared, and this concept will be explored in more detail (55m14s).
• The proof relies heavily on the Hoeffding inequality and upper confidence bounds, which provide a way to estimate the expected value of an arm and bound the probability of the true expected value being outside of a certain range (55m36s).
• The Hoeffding inequality states that the difference between the true expected value of an arm and its empirical average is greater than a certain quantity (the upper confidence bound) with probability no more than 1 - Delta/T, where Delta is a small probability and T is the number of times the arm is pulled (56m26s).
• The goal is to bound the number of times a suboptimal arm is pulled, which is the only case where regret occurs, and this can be done by analyzing the times when a non-optimal arm is pulled and its upper confidence bound is higher than the optimal arm's upper confidence bound (57m5s).
• If the confidence interval holds, then the upper confidence bound of a suboptimal arm is higher than the true expected value of the optimal arm, and this can be used to bound the number of times the suboptimal arm is pulled (57m57s).
• Under the UCB algorithm, a suboptimal arm is only pulled if its upper confidence bound is higher than the optimal arm's upper confidence bound, and this can be used to derive a bound on the number of times the suboptimal arm is pulled (58m21s).
• By substituting the upper confidence bounds of the suboptimal and optimal arms, it can be shown that the number of times the suboptimal arm is pulled is bounded by a function of the gap between the two arms and the number of times the suboptimal arm is pulled (59m56s).
• The upper confidence bound on the optimal action also holds, so its upper confidence bound has to be higher than its true value (1h0m12s).
• Q of a plus two of the confidence intervals is going to be greater than Q of a star, which means 2 < TK C log 1 Delta over NT of a is greater than Q of a star minus Q of a, which is equal to Delta a (1h2m50s).
• Rearranging the equation, we get that 4 * C log 1 / Delta / NT of a is greater than equal to Delta a 2, which means NT of a is less than or equal to 4 C log 1 / Delta (1h3m48s).
• Intuitively, this means that if confidence bounds hold and are used to make decisions, then the only time a wrong decision is made is when the confidence bounds are large enough to overwhelm the gap, and the number of times this occurs is finite (1h4m6s).
• The size of the confidence intervals decreases over time, eventually becoming smaller than the gap, resulting in fewer suboptimal actions being taken (1h4m36s).
• The algorithm achieves logarithmic asymptotic regret as a function of log T, because the log T term is inside the number of times suboptimal actions are taken (1h5m11s).

Comparison of UCB with Other Approaches and Extensions

• Upper Confidence Bound (UCB) algorithms have a nice logarithmic shape if the constants are set correctly, but the constants can greatly affect the exploration time, and being more aggressive can result in better performance (1h5m41s).
• An alternative to UCB is to always select the arm with the highest lower bound, which can yield linear regret, and it's helpful to think about why this approach wouldn't work in the upper confidence bound case (1h6m11s).
• To demonstrate why selecting the arm with the highest lower bound can lead to linear regret, one can construct a multi-arm bandit case where this approach would result in linear regret, similar to the example shown for the greedy algorithm (1h7m30s).
• When the condition for UCB is not met, the expectation can be split into a high-probability event and a low-probability event, allowing for the regret to be bounded from those time points (1h8m41s).
• To achieve linear regret when selecting the arm with the highest lower bound, the upper bound and mean of the suboptimal arm (A2) should be placed such that the algorithm is pessimistic and never selects the optimal arm (A1), for example, by having a very high upper bound for A2 (1h11m18s).
• If the upper bound of A2 is higher than A1, the algorithm would learn to select A2 under UCB, but being pessimistic would prevent this, and the algorithm would never pull A2 (1h12m22s).
• The pessimistic view is that learning may not occur due to not updating other bounds (1h12m38s).
• The empirical average plus its upper confidence bound being bigger than the optimal arm's empirical average plus its upper bound is based on the equation that the empirical average is always less than or equal to the true value plus the upper confidence bound (1h12m54s).
• Substituting the empirical average with the true value plus the upper confidence bound results in Q of A plus 2 times the bound (1h13m15s).
• This algorithm has provably sublinear regret, which is a desirable property, and is also easy to implement, especially when counts are available (1h13m41s).
• The optimism under uncertainty principle can be extended to more complicated settings, such as function approximation and reinforcement learning (1h13m51s).
• The principle is used to make decisions when outcomes are uncertain, with the goal of reducing regret over time (1h14m1s).

Introduction to Bayesian Bandits

• The next topic to be covered is Bayesian Bandits, which involves thinking of the problem from a different perspective, using a prior over the distribution of rewards for each arm (1h14m19s).
• Bayesian Bandits can also involve algorithms that use prior information to quickly gather data and make good decisions, which can be similar to optimism in certain ways (1h14m33s).