Reinforcement Learning: Multi-Armed Bandits

00:00:07,300 --> 00:00:10,500

Welcome back to a new module of Stochastic Modeling! In

00:00:10,500 --> 00:00:14,000

this Module 6, we are going to analyze the third backbone

00:00:13,200 --> 00:00:16,900

of reinforcement learning algorithms. Remember

00:00:16,900 --> 00:00:19,600

that in Module 4, we covered the concepts of

00:00:19,600 --> 00:00:22,500

Markov processes; in Module 5,

00:00:22,500 --> 00:00:25,400

we studied dynamic programming; and now we are

00:00:25,400 --> 00:00:28,200

going to study algorithms where we do

00:00:28,200 --> 00:00:31,200

not have perfect knowledge about the dynamics of the

00:00:31,200 --> 00:00:35,500

environment so that the agent learns potentially optimal

10
00:00:34,500 --> 00:00:36,800
choices from experience.

00:00:37,800 --> 00:00:40,300

With this third piece of knowledge, we will

00:00:40,300 --> 00:00:43,900

be able to build fully-fledged reinforcement learning

00:00:43,900 --> 00:00:45,600

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 1
algorithms in Module 7.

00:00:46,400 --> 00:00:49,400

We will develop the main intuitions in this

00:00:49,400 --> 00:00:52,700

module using the Multi-Armed bandit

00:00:52,700 --> 00:00:55,800

problems, which give us a simple benchmark

00:00:55,800 --> 00:00:58,900

to develop intuitions and more advanced techniques that

00:00:58,900 --> 00:01:01,500

we will deal with in the final module

00:01:01,500 --> 00:01:02,300

of this course.

00:01:03,500 --> 00:01:06,300

So, as we have just mentioned, one of

00:01:06,300 --> 00:01:09,400

the most essential ingredients in most of

00:01:09,400 --> 00:01:12,500

the reinforcement learning applications is the lack

00:01:12,500 --> 00:01:15,600

of knowledge about the dynamics that drive the

00:01:15,600 --> 00:01:18,200

transitions across states and how the

00:01:18,200 --> 00:01:21,700

agent's action determines those transitions.

00:01:22,500 --> 00:01:25,700

In the previous module, we understood the

00:01:25,700 --> 00:01:28,500

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 2
workings of dynamic programming methods,

00:01:28,500 --> 00:01:31,800

where we "inserted" the dynamics

00:01:31,800 --> 00:01:34,500

of the environment to obtain the optimal solution.

00:01:36,300 --> 00:01:40,200

For instance, you can think that in the gridworld problem analyzed

00:01:39,200 --> 00:01:42,500

in Module 5, the agent knew

00:01:42,500 --> 00:01:46,000

were they would end up after each movement or

00:01:45,600 --> 00:01:48,700

in the investor's problem, the agent

00:01:48,700 --> 00:01:52,000

knew the transition probabilities across different realizations

00:01:51,300 --> 00:01:53,600

of the asset's payoff.

00:01:54,600 --> 00:01:58,000

In most reinforcement learning applications, however, these

00:01:57,600 --> 00:01:59,700

dynamics are not known.

00:02:00,600 --> 00:02:03,900

Most of the advances in reinforcement learning

00:02:03,900 --> 00:02:07,100

use as

00:02:06,100 --> 00:02:10,200

a testbed the analysis of how agents reach

00:02:09,200 --> 00:02:12,400

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 3
the optimal actions in video

00:02:12,400 --> 00:02:14,600

games and in table games such as chess.

00:02:15,600 --> 00:02:19,100

Most of these environments have a complex

00:02:18,100 --> 00:02:21,500

structure. So, an efficient and natural

00:02:21,500 --> 00:02:24,600

way to obtain the optimal actions is to allow

00:02:24,600 --> 00:02:27,700

the agent to repeatedly interact with

00:02:27,700 --> 00:02:30,900

the environment and come up with candidate optimal

00:02:30,900 --> 00:02:33,200

courses of action from that experience.

00:02:34,500 --> 00:02:37,900

The Multi-Armed bandits problem represents one

00:02:37,900 --> 00:02:40,500

of the most basic setups of analysis in

00:02:40,500 --> 00:02:41,400

reinforcement learning.

00:02:41,900 --> 00:02:44,300

In this problem, the agents must

00:02:44,300 --> 00:02:47,100

at each time step take an action,

00:02:47,100 --> 00:02:50,900

among a set of possible actions "k" to maximize

00:02:50,900 --> 00:02:52,300

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 4
the expected reward;

00:02:53,100 --> 00:02:57,200

by taking actions over time, the agent updates their

00:02:56,200 --> 00:02:59,500

beliefs on which action among

00:02:59,500 --> 00:03:02,900

the "k" options yields the greatest reward.

00:03:04,300 --> 00:03:07,100

The Multi-Armed bandit name comes from

00:03:07,100 --> 00:03:10,300

the analogy of the problem of a

00:03:10,300 --> 00:03:13,500

gambler who faces a row of slot machines

00:03:13,500 --> 00:03:16,500

in a casino and has to decide which machines to

00:03:16,500 --> 00:03:17,900

play at each time step.

00:03:18,500 --> 00:03:21,900

Each machine offers a random payoff, but perhaps

00:03:21,900 --> 00:03:24,200

some machines offer a higher

00:03:24,200 --> 00:03:28,000

expected payoff than others. The gambler's objective

00:03:27,300 --> 00:03:30,300

is to make a sequence of choices of

00:03:30,300 --> 00:03:33,600

machines that maximizes the expected payoff.

00:03:36,200 --> 00:03:39,200

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 5
So, let's formally describe the elements of

00:03:39,200 --> 00:03:41,600

the Multi-Armed bandit problem.

00:03:42,400 --> 00:03:45,600

Suppose you repeatedly face a choice

00:03:45,600 --> 00:03:48,400

between "k" different actions, each

00:03:48,400 --> 00:03:51,800

of which offers some expected reward for the agent.

00:03:52,900 --> 00:03:55,300

The objective is to maximize the

00:03:55,300 --> 00:03:58,900

expected total reward over some time period where the agent

00:03:58,900 --> 00:03:59,400

takes actions.

00:03:59,800 --> 00:04:02,700

In an equivalent analogy, an investor

00:04:02,700 --> 00:04:05,300

wants to pick a stock in which to invest their money. In

00:04:05,300 --> 00:04:08,800

this case, each action is represented by the stock

00:04:08,800 --> 00:04:11,500

selected and the reward will be the return of

00:04:11,500 --> 00:04:12,600

obtained from the investment.

00:04:13,700 --> 00:04:16,200

Actually, we will take this analogy into

00:04:16,200 --> 00:04:19,600

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 6
practice at the end of this model with an application with real data.

00:04:20,700 --> 00:04:23,500

Now, because the investor will pick

00:04:23,500 --> 00:04:26,900

different stocks at each time step, they may

00:04:26,900 --> 00:04:29,100

be able to learn about which stock

00:04:29,100 --> 00:04:32,800

generates the highest return on average and select

00:04:32,800 --> 00:04:33,800

them appropriately.

00:04:34,500 --> 00:04:37,700

Obviously, this is not going to be easy since

00:04:37,700 --> 00:04:40,700

stock returns tend to follow an unpredictable pattern

00:04:40,700 --> 00:04:41,900

as we already know.

00:04:43,100 --> 00:04:46,600

Going back to our general formulation of the problem, we are going

00:04:46,600 --> 00:04:50,000

to denote actions by the letter "a" and the

00:04:49,600 --> 00:04:52,200

expected reward of that action by the letter "Q".

00:04:53,700 --> 00:04:56,700

The actual value of the action, "Q star"

00:04:56,700 --> 00:05:00,300

is going to be represented by the expected reward

00:04:59,300 --> 00:05:03,200

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 7
conditional on the agent choosing

00:05:02,200 --> 00:05:06,100

that action, as you have mathematically expressed,

00:05:05,100 --> 00:05:09,000

right here. We are completely ignorant

00:05:08,200 --> 00:05:11,300

about the value of Q star for each

00:05:11,300 --> 00:05:15,100

action, but our aim is to reach precise

00:05:14,100 --> 00:05:16,500

estimates of it.

00:05:17,800 --> 00:05:20,100

So, the question now is how are we

00:05:20,100 --> 00:05:21,700

going to estimate "Q star"?

00:05:22,700 --> 00:05:25,700

At each time step what we are going to do is simply define

00:05:25,700 --> 00:05:28,700

it as the average reward

00:05:28,700 --> 00:05:31,200

obtained from each action conditional on

00:05:31,200 --> 00:05:32,900

the agent having chosen that action.

00:05:34,100 --> 00:05:37,200

Thus, a reasonable course of action for the

00:05:37,200 --> 00:05:40,300

agent is that they take the action in each time step

00:05:40,300 --> 00:05:43,500

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 8
that has the highest estimated average reward.

00:05:44,200 --> 00:05:47,200

This is what we can call a "greedy" action selection.

00:05:48,500 --> 00:05:51,900

You can imagine that if the agent always exploits

00:05:51,900 --> 00:05:54,200

the greedy policy, it will reduce the

00:05:54,200 --> 00:05:57,200

extent of exploration of other actions that

00:05:57,200 --> 00:05:59,700

may yield the greatest expected reward.

00:06:00,900 --> 00:06:03,000

Now, this captures the main trade-off of

00:06:03,600 --> 00:06:06,400

reinforcement learning. We want the agent to

00:06:06,400 --> 00:06:09,700

efficiently explore the rewards of different actions

00:06:09,700 --> 00:06:12,600

to exploit those that indeed

00:06:12,600 --> 00:06:15,500

generate the highest rewards. If we were to

00:06:15,500 --> 00:06:18,600

allow the agent to follow a fully greedy

00:06:18,600 --> 00:06:21,400

policy, you can think that most of the time they will

00:06:21,400 --> 00:06:24,500

get stuck choosing inferior actions.

00:06:24,800 --> 00:06:27,400

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 9
To increase the extent of exploration, we can

00:06:27,400 --> 00:06:30,900

devise what are called "epsilon-greedy"

00:06:30,900 --> 00:06:33,300

policies. Where at each time step,

00:06:33,300 --> 00:06:36,500

the agent chooses an action at random

00:06:36,500 --> 00:06:38,600

with probability "epsilon."

00:06:40,300 --> 00:06:43,800

Now, from a computational perspective, updating the

00:06:43,800 --> 00:06:46,300

average reward of an action that does not

00:06:46,300 --> 00:06:49,300

require us to store the full

00:06:49,300 --> 00:06:52,100

history of rewards obtained by the agent.

00:06:52,700 --> 00:06:55,500

Indeed, we just need to keep an array

00:06:55,500 --> 00:06:58,500

that updates the expected reward of each

00:06:58,500 --> 00:07:01,300

action when it is chosen by the agent and another

00:07:01,300 --> 00:07:04,400

array that gives us the number of times

00:07:04,400 --> 00:07:07,500

that an action was taken up to the current time step.

00:07:08,700 --> 00:07:11,500

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 10
Now, equation 4 here, in this slide,

00:07:11,500 --> 00:07:14,400

gives us an updating rule for

00:07:14,400 --> 00:07:17,200

the reward of an action "a", which is

00:07:17,200 --> 00:07:20,300

just a function of the average reward of the

00:07:20,300 --> 00:07:23,300

action "a" estimated up to step

00:07:23,300 --> 00:07:26,700

"t-1". The number of steps that action "a"

00:07:26,700 --> 00:07:29,100

has been chosen by the agent up to step "t",

00:07:30,600 --> 00:07:34,000

and the reward obtained in step "t" if

00:07:33,500 --> 00:07:35,500

action "a" was chosen.

00:07:36,300 --> 00:07:40,300

This updating rule is useful in stationary setups

00:07:39,300 --> 00:07:42,700

where the reward of each action do

00:07:42,700 --> 00:07:44,100

not change over time.

00:07:45,100 --> 00:07:48,200

However, in financial applications, we do

00:07:48,200 --> 00:07:51,400

not encounter these stationary setups so often.

00:07:53,200 --> 00:07:56,500

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 11
Now, in non-stationary setups, it is usually

00:07:56,500 --> 00:07:59,300

relevant to ignore information that was

00:07:59,300 --> 00:08:02,400

gathered in the distant past. Thus, we

00:08:02,400 --> 00:08:05,900

can use a parameter "alpha" that modulates the importance of

00:08:05,900 --> 00:08:08,900

the past in the updating of the expected reward

00:08:08,900 --> 00:08:11,400

of an action as it appears here in equation 5.

00:08:12,600 --> 00:08:15,500

The higher the "alpha", the more weight

00:08:15,500 --> 00:08:18,500

we give to most recent realizations of

00:08:18,500 --> 00:08:21,300

the rewards and the less weight we give to

00:08:21,300 --> 00:08:23,800

more distant realizations of the reward.

00:08:24,600 --> 00:08:27,600

So that's all for Lesson 1. Let's now

00:08:27,600 --> 00:08:30,100

advance to Lesson 2, where we will

00:08:30,100 --> 00:08:33,900

cover a practice example of a k-bandit problem in a stationary setup.

00:08:34,800 --> 00:08:35,600

See you all there!

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 12
MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 13