An Introduction to Q-Learning Part 1 (2024)

Unit 2, part 1 of theDeep Reinforcement Learning Class with Hugging Face 🤗

⚠️ A new updated version of this article is available here 👉 https://huggingface.co/deep-rl-course/unit1/introduction

This article is part of the Deep Reinforcement Learning Class. A free course from beginner to expert. Check the syllabushere.

⚠️ A new updated version of this article is available here 👉 https://huggingface.co/deep-rl-course/unit1/introduction

This article is part of the Deep Reinforcement Learning Class. A free course from beginner to expert. Check the syllabushere.

In thefirst chapter of this class, we learned about Reinforcement Learning (RL), the RL process, and the different methods to solve an RL problem. We also trained our first lander agent toland correctly on the Moon 🌕 and uploaded it to the Hugging Face Hub.

So today, we're going todive deeper into one of the Reinforcement Learning methods: value-based methodsand study our first RL algorithm:Q-Learning.

We'll alsoimplement our first RL agent from scratch: a Q-Learning agent and will train it in two environments:

1. Frozen-Lake-v1 (non-slippery version): where our agent will need togo from the starting state (S) to the goal state (G)by walking only on frozen tiles (F) and avoiding holes (H).
2. An autonomous taxi will needto learn to navigatea city totransport its passengers from point A to point B.

This unit is divided into 2 parts:

In the first part, we'lllearn about the value-based methods and the difference between Monte Carlo and Temporal Difference Learning.

And in the second part,we'll study our first RL algorithm: Q-Learning, and implement our first RL Agent.

This unit is fundamentalif you want to be able to work on Deep Q-Learning(unit 3): the first Deep RL algorithm that was able to play Atari games andbeat the human level on some of them(breakout, space invaders…).

So let's get started!

• What is RL? A short recap
• The two types of value-based methods
  • The State-Value function
  • The Action-Value function
• The Bellman Equation: simplify our value estimation
• Monte Carlo vs Temporal Difference Learning
  • Monte Carlo: learning at the end of the episode
  • Temporal Difference Learning: learning at each step

What is RL? A short recap

In RL, we build an agent that canmake smart decisions. For instance, an agent thatlearns to play a video game.Or a trading agent thatlearns to maximize its benefitsby making smart decisions onwhat stocks to buy and when to sell.

But, to make intelligent decisions, our agent will learn from the environment byinteracting with it through trial and errorand receiving rewards (positive or negative)as unique feedback.

Its goalis to maximize its expected cumulative reward(because of the reward hypothesis).

The agent's decision-making process is called the policy π:given a state, a policy will output an action or a probability distribution over actions. That is, given an observation of the environment, a policy will provide an action (or multiple probabilities for each action) that the agent should take.

Our goal is to find an optimal policy π*, aka., a policy that leads to the best expected cumulative reward.

And to find this optimal policy (hence solving the RL problem), thereare two main types of RL methods:

• Policy-based methods:Train the policy directlyto learn which action to take given a state.
• Value-based methods:Train a value functionto learnwhich state is more valuableand use this value functionto take the action that leads to it.

And in this chapter,we'll dive deeper into the Value-based methods.

The two types of value-based methods

In value-based methods,we learn a value functionthatmaps a state to the expected value of being at that state.

The value of a state is theexpected discounted returnthe agent can get if itstarts at that state and then acts according to our policy.

If you forgot what discounting is, you can read this section.

But what does it mean to act according to our policy? After all, we don't have a policy in value-based methods, since we train a value function and not a policy.

Remember that the goal of anRL agent is to have an optimal policy π.

To find it, we learned that there are two different methods:

• Policy-based methods:Directly train the policyto select what action to take given a state (or a probability distribution over actions at that state). In this case, wedon't have a value function.

The policy takes a state as input and outputs what action to take at that state (deterministic policy).

And consequently,we don't define by hand the behavior of our policy; it's the training that will define it.

• Value-based methods:Indirectly, by training a value functionthat outputs the value of a state or a state-action pair. Given this value function, our policywill take action.

But, because we didn't train our policy,we need to specify its behavior.For instance, if we want a policy that, given the value function, will take actions that always lead to the biggest reward,we'll create a Greedy Policy.

Consequently, whatever method you use to solve your problem,you will have a policy, but in the case of value-based methods you don't train it, your policyis just a simple function that you specify(for instance greedy policy) and this policyuses the values given by the value-function to select its actions.

So the difference is:

• In policy-based,the optimal policy is found by training the policy directly.
• In value-based,finding an optimal value function leads to having an optimal policy.

In fact, most of the time, in value-based methods, you'll usean Epsilon-Greedy Policythat handles the exploration/exploitation trade-off; we'll talk about it when we talk about Q-Learning in the second part of this unit.

So, we have two types of value-based functions:

The State-Value function

We write the state value function under a policy π like this:

For each state, the state-value function outputs the expected return if the agentstarts at that state,and then follow the policy forever after (for all future timesteps if you prefer).

The Action-Value function

In the Action-value function, for each state and action pair, the action-value functionoutputs the expected returnif the agent starts in that state and takes action, and then follows the policy forever after.

The value of taking action an in state s under a policy π is:

We see that the difference is:

• In state-value function, we calculatethe value of a state $S_t$St​
• In action-value function, we calculatethe value of the state-action pair ( $S_t, A_t$St​,At​ ) hence the value of taking that action at that state.

In either case, whatever value function we choose (state-value or action-value function),the value is the expected return.

However, the problem is that it implies thatto calculate EACH value of a state or a state-action pair, we need to sum all the rewards an agent can get if it starts at that state.

This can be a tedious process, and that'swhere the Bellman equation comes to help us.

The Bellman Equation: simplify our value estimation

The Bellman equationsimplifies our state value or state-action value calculation.

With what we learned from now, we know that if we calculate the $V(S_t)$V(St​) (value of a state), we need to calculate the return starting at that state and then follow the policy forever after.(Our policy that we defined in the following example is a Greedy Policy, and for simplification, we don't discount the reward).

So to calculate $V(S_t)$V(St​), we need to make the sum of the expected rewards. Hence:

Then, to calculate the $V(S_{t+1})$V(St+1​), we need to calculate the return starting at that state $S_{t+1}$St+1​.

So you see, that's a pretty tedious process if you need to do it for each state value or state-action value.

Instead of calculating the expected return for each state or each state-action pair,we can use the Bellman equation.

The Bellman equation is a recursive equation that works like this: instead of starting for each state from the beginning and calculating the return, we can consider the value of any state as:

The immediate reward $R_{t+1}$Rt+1​ + the discounted value of the state that follows ( $gamma * V(S_{t+1})$gamma∗V(St+1​) ) .

If we go back to our example, the value of State 1= expected cumulative return if we start at that state.

To calculate the value of State 1: the sum of rewardsif the agent started in that state 1and then followed thepolicy for all the time steps.

Which is equivalent to $V(S_{t})$V(St​) = Immediate reward $R_{t+1}$Rt+1​ + Discounted value of the next state $gamma * V(S_{t+1})$gamma∗V(St+1​)

For simplification, here we don't discount, so gamma = 1.

• The value of $V(S_{t+1})$V(St+1​) = Immediate reward $R_{t+2}$Rt+2​ + Discounted value of the next state ( $gamma * V(S_{t+2})$gamma∗V(St+2​) ).
• And so on.

To recap, the idea of the Bellman equation is that instead of calculating each value as the sum of the expected return,which is a long process.This is equivalentto the sum of immediate reward + the discounted value of the state that follows.

Monte Carlo vs Temporal Difference Learning

The last thing we need to talk about before diving into Q-Learning is the two ways of learning.

Remember that an RL agentlearns by interacting with its environment.The idea is thatusing the experience taken, given the reward it gets, willupdate its value or policy.

Monte Carlo and Temporal Difference Learning are two differentstrategies on how to train our value function or our policy function.Both of themuse experience to solve the RL problem.

On one hand, Monte Carlo usesan entire episode of experience before learning.On the other hand, Temporal Difference usesonly a step ( $S_t, A_t, R_{t+1}, S_{t+1}$St​,At​,Rt+1​,St+1​ ) to learn.

We'll explain both of themusing a value-based method example.

Monte Carlo: learning at the end of the episode

Monte Carlo waits until the end of the episode, calculates $G_t$Gt​ (return) and uses it asa target for updating $V(S_t)$V(St​).

So it requires acomplete entire episode of interaction before updating our value function.

If we take an example:

• We always start the episodeat the same starting point.

• The agent takes actions using the policy. For instance, using an Epsilon Greedy Strategy, a policy that alternates between exploration (random actions) and exploitation.

• We getthe reward and the next state.

• We terminate the episode if the cat eats the mouse or if the mouse moves > 10 steps.

• At the end of the episode,we have a list of State, Actions, Rewards, and Next States

• The agent will sum the total rewards $G_t$Gt​(to see how well it did).

• It will thenupdate $V(s_t)$V(st​) based on the formula

• Thenstart a new game with this new knowledge

By running more and more episodes,the agent will learn to play better and better.

For instance, if we train a state-value function using Monte Carlo:

• We just started to train our Value function,so it returns 0 value for each state
• Our learning rate (lr) is 0.1 and our discount rate is 1 (= no discount)
• Our mouseexplores the environment and takes random actions

• The mouse made more than 10 steps, so the episode ends .

• We have a list of state, action, rewards, next_state,we need to calculate the return $G{t}$Gt
• $G_t = R_{t+1} + R_{t+2} + R_{t+3} ...$Gt​=Rt+1​+Rt+2​+Rt+3​...
• $G_t = R_{t+1} + R_{t+2} + R_{t+3}…$Gt​=Rt+1​+Rt+2​+Rt+3​… (for simplicity we don’t discount the rewards).
• $G_t = 1 + 0 + 0 + 0+ 0 + 0 + 1 + 1 + 0 + 0$Gt​=1+0+0+0+0+0+1+1+0+0
• $G_t= 3$Gt​=3
• We can now update $V(S_0)$V(S0​):

• New $V(S_0) = V(S_0) + lr * [G_t — V(S_0)]$V(S0​)=V(S0​)+lr∗[Gt​—V(S0​)]
• New $V(S_0) = 0 + 0.1 * [3 – 0]$V(S0​)=0+0.1∗[3–0]
• New $V(S_0) = 0.3$V(S0​)=0.3

Temporal Difference Learning: learning at each step

• Temporal difference, on the other hand, waits for only one interaction (one step) $S_{t+1}$St+1​
• to form a TD target and update $V(S_t)$V(St​) using $R_{t+1}$Rt+1​ and $gamma * V(S_{t+1})$gamma∗V(St+1​).

The idea withTD is to update the $V(S_t)$V(St​) at each step.

But because we didn't play during an entire episode, we don't have $G_t$Gt​ (expected return). Instead, we estimate $G_t$Gt​ by adding $R_{t+1}$Rt+1​ and the discounted value of the next state.

This is called bootstrapping. It's called this because TD bases its update part on an existing estimate $V(S_{t+1})$V(St+1​) and not a complete sample $G_t$Gt​.

This method is called TD(0) orone-step TD (update the value function after any individual step).

If we take the same example,

• We just started to train our Value function, so it returns 0 value for each state.
• Our learning rate (lr) is 0.1, and our discount rate is 1 (no discount).
• Our mouse explore the environment and take a random action:going to the left
• It gets a reward $R_{t+1} = 1$Rt+1​=1 sinceit eats a piece of cheese

We can now update $V(S_0)$V(S0​):

New $V(S_0) = V(S_0) + lr * [R_1 + gamma * V(S_1) - V(S_0)]$V(S0​)=V(S0​)+lr∗[R1​+gamma∗V(S1​)−V(S0​)]

New $V(S_0) = 0 + 0.1 * [1 + 1 * 0–0]$V(S0​)=0+0.1∗[1+1∗0–0]

New $V(S_0) = 0.1$V(S0​)=0.1

So we just updated our value function for State 0.

Now wecontinue to interact with this environment with our updated value function.

If we summarize:

• With Monte Carlo, we update the value function from a complete episode, and so weuse the actual accurate discounted return of this episode.
• With TD learning, we update the value function from a step, so we replace $G_t$Gt​ that we don't have withan estimated return called TD target.

So now, before diving on Q-Learning, let's summarise what we just learned:

We have two types of value-based functions:

• State-Value function: outputs the expected return ifthe agent starts at a given state and acts accordingly to the policy forever after.
• Action-Value function: outputs the expected return ifthe agent starts in a given state, takes a given action at that stateand then acts accordingly to the policy forever after.
• In value-based methods,we define the policy by handbecause we don't train it, we train a value function. The idea is that if we have an optimal value function, wewill have an optimal policy.

There are two types of methods to learn a policy for a value function:

• Withthe Monte Carlo method, we update the value function from a complete episode, and so weuse the actual accurate discounted return of this episode.
• Withthe TD Learning method,we update the value function from a step, so we replace Gt that we don't have withan estimated return called TD target.

So that’s all for today. Congrats on finishing this first part of the chapter! There was a lot of information.

That’s normal if you still feel confused with all these elements. This was the same for me and for all people who studied RL.

Take time to really grasp the material before continuing.

And since the best way to learn and avoid the illusion of competence is to test yourself. We wrote a quiz to help you find where you need to reinforce your study. Check your knowledge here 👉 https://github.com/huggingface/deep-rl-class/blob/main/unit2/quiz1.md

In the second part , we’ll study our first RL algorithm: Q-Learning, and implement our first RL Agent in two environments:

1. Frozen-Lake-v1 (non-slippery version): where our agent will need togo from the starting state (S) to the goal state (G)by walking only on frozen tiles (F) and avoiding holes (H).
2. An autonomous taxi will needto learn to navigatea city totransport its passengers from point A to point B.

And don't forget to share with your friends who want to learn 🤗 !

Finally, we want to improve and update the course iteratively with your feedback. If you have some, please fill this form 👉 https://forms.gle/3HgA7bEHwAmmLfwh9

Keep learning, stay awesome,