An Introduction to Q-Learning Part 1 (2024)

Back to Articles

PublishedMay 18, 2022

Update on GitHub

Upvote1

ThomasSimoniniThomas Simonini

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.

An Introduction to Q-Learning Part 1 (3)

⚠️ 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.
An Introduction to Q-Learning Part 1 (4)

This unit is divided into 2 parts:

An Introduction to Q-Learning Part 1 (5)

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.

An Introduction to Q-Learning Part 1 (6)

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.

An Introduction to Q-Learning Part 1 (7)

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.
An Introduction to Q-Learning Part 1 (8)

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.

An Introduction to Q-Learning Part 1 (9)

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.
An Introduction to Q-Learning Part 1 (10)

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.

An Introduction to Q-Learning Part 1 (11)

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.
An Introduction to Q-Learning Part 1 (12)

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:

An Introduction to Q-Learning Part 1 (13)

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).

An Introduction to Q-Learning Part 1 (14)

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:

An Introduction to Q-Learning Part 1 (15)
An Introduction to Q-Learning Part 1 (16)

We see that the difference is:

  • In state-value function, we calculatethe value of a state StS_tSt
  • In action-value function, we calculatethe value of the state-action pair ( St,AtS_t, A_tSt,At ) hence the value of taking that action at that state.
An Introduction to Q-Learning Part 1 (17)

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.

An Introduction to Q-Learning Part 1 (18)

With what we learned from now, we know that if we calculate the V(St)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(St)V(S_t)V(St), we need to make the sum of the expected rewards. Hence:

An Introduction to Q-Learning Part 1 (19)

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

An Introduction to Q-Learning Part 1 (20)

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 Rt+1R_{t+1}Rt+1 + the discounted value of the state that follows ( gammaV(St+1)gamma * V(S_{t+1}) gammaV(St+1) ) .

An Introduction to Q-Learning Part 1 (21)

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

An Introduction to Q-Learning Part 1 (22)

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(St)V(S_{t})V(St) = Immediate reward Rt+1R_{t+1}Rt+1 + Discounted value of the next state gammaV(St+1)gamma * V(S_{t+1})gammaV(St+1)

An Introduction to Q-Learning Part 1 (23)

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

  • The value of V(St+1)V(S_{t+1}) V(St+1) = Immediate reward Rt+2R_{t+2}Rt+2 + Discounted value of the next state ( gammaV(St+2)gamma * V(S_{t+2})gammaV(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 ( St,At,Rt+1,St+1S_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 GtG_tGt (return) and uses it asa target for updating V(St)V(S_t)V(St).

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

An Introduction to Q-Learning Part 1 (24)

If we take an example:

An Introduction to Q-Learning Part 1 (25)
  • 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 GtG_tGt(to see how well it did).

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

An Introduction to Q-Learning Part 1 (26)
  • Thenstart a new game with this new knowledge

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

An Introduction to Q-Learning Part 1 (27)

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
An Introduction to Q-Learning Part 1 (28)
  • The mouse made more than 10 steps, so the episode ends .
An Introduction to Q-Learning Part 1 (29)
  • We have a list of state, action, rewards, next_state,we need to calculate the return GtG{t}Gt
  • 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...
  • Gt=Rt+1+Rt+2+Rt+3G_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).
  • Gt=1+0+0+0+0+0+1+1+0+0G_t = 1 + 0 + 0 + 0+ 0 + 0 + 1 + 1 + 0 + 0Gt=1+0+0+0+0+0+1+1+0+0
  • Gt=3G_t= 3Gt=3
  • We can now update V(S0)V(S_0)V(S0):
An Introduction to Q-Learning Part 1 (30)
  • New V(S0)=V(S0)+lr[GtV(S0)]V(S_0) = V(S_0) + lr * [G_t — V(S_0)]V(S0)=V(S0)+lr[GtV(S0)]
  • New V(S0)=0+0.1[30]V(S_0) = 0 + 0.1 * [3 – 0]V(S0)=0+0.1[3–0]
  • New V(S0)=0.3V(S_0) = 0.3V(S0)=0.3
An Introduction to Q-Learning Part 1 (31)

Temporal Difference Learning: learning at each step

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

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

But because we didn't play during an entire episode, we don't have GtG_tGt (expected return). Instead, we estimate GtG_tGt by adding Rt+1R_{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(St+1)V(S_{t+1})V(St+1) and not a complete sample GtG_tGt.

An Introduction to Q-Learning Part 1 (32)

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

An Introduction to Q-Learning Part 1 (33)

If we take the same example,

An Introduction to Q-Learning Part 1 (34)
  • 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 Rt+1=1R_{t+1} = 1Rt+1=1 sinceit eats a piece of cheese
An Introduction to Q-Learning Part 1 (35)
An Introduction to Q-Learning Part 1 (36)

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

New V(S0)=V(S0)+lr[R1+gammaV(S1)V(S0)]V(S_0) = V(S_0) + lr * [R_1 + gamma * V(S_1) - V(S_0)]V(S0)=V(S0)+lr[R1+gammaV(S1)V(S0)]

New V(S0)=0+0.1[1+100]V(S_0) = 0 + 0.1 * [1 + 1 * 0–0]V(S0)=0+0.1[1+10–0]

New V(S0)=0.1V(S_0) = 0.1V(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.

An Introduction to Q-Learning Part 1 (37)

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 GtG_tGt that we don't have withan estimated return called TD target.
An Introduction to Q-Learning Part 1 (38)

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.
An Introduction to Q-Learning Part 1 (39)

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.
An Introduction to Q-Learning Part 1 (40)

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,

An Introduction to Q-Learning Part 1 (2024)

FAQs

How do you solve Q-learning problems? ›

Example Of Q-Learning
  1. Initialize the Q-table: Q = [ [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], ...
  2. Observe the state: Let's say the agent starts in position (0, 0).
  3. Choose an action: ...
  4. Execute the action: ...
  5. Update the Q-table: ...
  6. Repeat steps 2-5 until the agent reaches the goal state: ...
  7. Repeat steps 1-6 for multiple episodes:
Apr 27, 2023

What is Q-learning PDF? ›

The Q-value Q (S, A) of the action for the current state S is. updated with the sum of existing value Q (S, A) and the. equation which determines the best action in the current state. Q-learning is continued by updating the Q-value for each state. continuously using the above equation.

What is Q-learning easily explained? ›

Q-learning is a reinforcement learning algorithm that finds an optimal action-selection policy for any finite Markov decision process (MDP). It helps an agent learn to maximize the total reward over time through repeated interactions with the environment, even when the model of that environment is not known.

What is the formula for Q-learning? ›

The equation breaks down as follows: Q(s, a) represents the expected reward for taking action a in state s. The actual reward received for that action is referenced by r while s' refers to the next state. The learning rate is α and γ is the discount factor.

Why is Q-learning unstable? ›

Deep Q-learning

This instability comes from the correlations present in the sequence of observations, the fact that small updates to Q may significantly change the policy of the agent and the data distribution, and the correlations between Q and the target values.

Who invented Q-learning? ›

Finally, the temporal-difference and optimal control threads were fully brought together in 1989 with Chris Watkins's development of Q-learning.

Is Q-learning biased? ›

The overestimation bias occurs since the target maxa ∈A Q(st+1,a ) is used in the Q-learning update. Because Q is an approximation, it is probable that the approximation is higher than the true value for one or more of the actions. The maximum over these estimators, then, is likely to be skewed towards an overestimate.

What is the difference between Q-learning and deep learning? ›

The main difference between deep and regular Q-learning is the implementation of the Q-table. In deep Q-learning, this is replaced with two neural networks that handle the learning process. While these networks have the same overarching architectures, they have different weights.

What are the problems with Q-learning? ›

The problem

The mechanism driving Q-learning is that it selects the action that yields the highest expected value. Depending on initialization, this mechanism might get stuck at the first action that is tried, so we also select random actions with probability ϵ, typically set at 0.05 or so.

Which programming language is used for AI? ›

1. Python. Python has become the general-purpose programming language for AI development due to its data visualization and analytics capabilities. It has a user-friendly syntax that is easier for data scientists and analysts to learn.

Does Q-learning always converge? ›

We show that Q-learning converges to the optimum action-values with probability 1 so long as all actions are repeatedly sampled in all states and the action-values are represented discretely.

What is Q in AI? ›

This technique is part of reinforcement learning, which is about learning through interactions with an environment. In Q-learning, the 'Q' stands for 'quality,' which refers to the value or benefit of taking a certain action in a specific state. The agent is rewarded for good actions and penalized for bad ones.

Why is the Q-learning model-free? ›

Q-learning is a model-free algorithm in the sense that it has no transition model — the model of the environment to learn from — therefore the agent finds the best way to navigate the environment by its predictions.

What does Q-learning use instead of training or testing data? ›

Q-learning uses Temporal Differences(TD) to estimate the value of Q*(s,a). Temporal difference is an agent learning from an environment through episodes with no prior knowledge of the environment. The agent maintains a table of Q[S, A], where S is the set of states and A is the set of actions.

How do you solve machine learning problems? ›

9 Steps for solving any machine learning problem
  1. 1) Defining the problem. ...
  2. 2) Choosing a measure of success. ...
  3. 3) Data Splitting. ...
  4. 4) Deciding on an evaluation protocol. ...
  5. 5) Data Preparation.
  6. 6) Developing a model that does better than a baseline. ...
  7. 7) developing a model that overfits.
Aug 28, 2021

What is the Q-learning mechanism? ›

Q-learning (Watkins and Dayan, 1992) is a simple RL algorithm that given the current state, seeks to find the best action to take in that state. It is an off-policy algorithm because it learns from actions that are random (i.e., outside the policy).

What is the standard Q-learning algorithm? ›

Q-learning is an off policy reinforcement learning algorithm that seeks to find the best action to take given the current state. It's considered off-policy because the q-learning function learns from actions that are outside the current policy, like taking random actions, and therefore a policy isn't needed.

Top Articles
Latest Posts
Article information

Author: Van Hayes

Last Updated:

Views: 5437

Rating: 4.6 / 5 (66 voted)

Reviews: 89% of readers found this page helpful

Author information

Name: Van Hayes

Birthday: 1994-06-07

Address: 2004 Kling Rapid, New Destiny, MT 64658-2367

Phone: +512425013758

Job: National Farming Director

Hobby: Reading, Polo, Genealogy, amateur radio, Scouting, Stand-up comedy, Cryptography

Introduction: My name is Van Hayes, I am a thankful, friendly, smiling, calm, powerful, fine, enthusiastic person who loves writing and wants to share my knowledge and understanding with you.