Reinforcement Learning
A recap of Andrew Ng course (Machine Learning Specialization) on Coursera
Course 3 Week 3
Reinforcement learning hasn’t been used a lot in commercial settings, but it is a nice one for situations when it is hard to create the input features (X) and the golden labels (y). For example, write a algorithm which flies an autonomous helicopter or operates a Mars rover, or to train a robot that plays Chess.
There are 6 key concepts in refinforcement learning which are
- State: could be the set of possible positions and orientations and speeds and so on for the helicopter
- Action: possible ways to move the control stick of the helicopter
- Rewards: the rewards the algorithm get for each action
- Discount factor: adding a discount factor while calculating the final return of the action in order to let the algorithm pick actions that maximize the return.
- Return: rewards and discount factor together calculates the return
- Policy: help you pick actions so as to maximize return. This is the goal of the refinforcement algorithm, it learns which actions to take based on certain states.
Let’s take Mars rover as an example, there are 6 states and the reward for state 1 is 100. Similarly the rewards are 0,0,0,0,40 from state 2 to state 6 respectively. (Assuming the policy for this example is to always go left) If the mars rover is currently on state 4 and takes three actions to move left onto state 1, we calculate the final return with discount factor 0.9 or 0.5 as shown below.
This type of learning algorithm is called the Markov Decision Process (MDP) which refers to the future only depends on the current state and not on anthing that might have occurred prior to getting to the current state. (In other word, the algorithm cares only about where you are now and it doesn’t care about how you got here)
The learning algorithm tried to compute the “State action value function” which is often written as Q function, Optimal Q function, Q*, or Q(). Q is a function of the state we might be in and the action we might take in that state: Q(s, a).
After the first action was taken, the model then moves by maximizing the return (Namely, just follow the policy). This sounds a bit like a circular function and also sounds like the model ALREADY knows what the OPTIMAL paths are, why bother learning that? We will resolve this later.
We can put down the Q value of state 2 when we pick the left and right move. It turns out that if we compute the Q values for each state we can use the values to pick the best policy. (We want the learning algorithm to enjoy the action that results in highest return for a certain state) The policy of a state is taking action that results in the highest return.
Bellman Equation: an equation that helps us compute the state-action value function, Q(s, a).
The following is some examples of the Q function values for different status and actions. The Q function value of the terminal state will just be the return of the terminal state, Q(s, a) = R(s), we don’t need to take actions.
To recap, Q(s, a) calculates the final return if we start from status s and take action a and then behave optimally after the first action starting from state S prime. We can re-write the equation for return by factoring out gamma in math, and in fact [R2 + rR3 + …] actually is equal to the return if we were to start from state S prime and behave optimally. So the summation of R1 + gamma * (the total return of starting from state S prime and behave optimally) is the total return for Q(s, a).
here is an example
The action we take at each state could have some random stochastic effect, for example, when we tell the robot to go left, it might not always go left but slightly up because of wind blowing it off course. The following example shows that it has a 0.9 chance of ending up in state 3 and a 0.1 chance of ending up in state 5. (It could also happen in opposite)
Because the robot might not always follow the sequence as we thought, we are more interested in the average return of Q(s, a) when it is tested thousands of times instead of just one execution. The average return is called the expected return in statistics, and the mathematical notation for the expected return is to write it as E.
The job of the reinforcement learning algorithm (or a Markov decision process) is to choose a policy to maximize the average of the expected sum of discounted rewards. In addition to getting the average of the final return, we also need to take the average for rewards after R(s).
The larger the chance the robot would go in wrong direction, the lower the expected return would be.
Get Aimyo’s stories in your inbox
Join Medium for free to get updates from this writer.
Continuous state application
In the mars rover example, there are only 6 discrete state; however, for a real-world car, the state would comprise this vector of six numbers, and any of these six numbers can take on any value within its valid range. X denotes the north-south direction, y denotes the east-west direction and theta denotes for the rotation; besides, we also need to track how fast the state is, the speed of moving on x, y axes and the speed of making turns.
Building a Lunar Lander through deep reinforcement learning
The goal of the reinforcement learning model is to learn a policy that picks action so as to maximize the return when given a continuous state vector as input. The state is comprised of 8 numbers which correspond to north-south, east-west, rotation, how fast it moves on north-south axis, how fast it moves on east-west axis, how fast the angle changes and whether the left leg has landed on the surface and whether the right leg has landed on the surface.
We use the following neural network architecture to build the algorithm. The input vector consists of the 8 numbers mentioned above and 4 additional numbers indicating the possible actions to take. The output of the neural network would be the state action value. We will prepare the input and output pairs using Belleman equation.
The following shows how we prepare the x and y values. In the beginning, when we don’t have a good policy yet, we just start with trying different actions randomly. We can try as many actions as we like and each of the actions brings us to a new status and get return. We then record all these as our inputs and outputs. Now we may be wondering where does Q(S prime, A prime) come from. Initially, we don’t know what the Q function is, but we can start off with taking a total random guess of what the Q function is. And the algorithm still works nonetheless. At every step we try, the Q function will just be a random guess which will get better over time and turns out to be the actual Q function
The learning algorithm (normally called the DQN network, deep Q network)looks as below. We store the most recent 10,000 moves (we picked 10,000 just to save computation resources) and each action randomly guesses the Q function, we then train a neural network (Q new function) with these 10,000 pairs and then update our Q function to be the Q new function we just trained. When we run this process long enough, the Q function will actually become a pretty good estimate of the true value of Q(s,a), so that we can use this updated Q function to pick actions for the reinforcement learning algorithm.
there is a slight modification that will make the neural network architecture more efficient. Currently, we inference the nerual network 4 times to pick an action that maximizes the Q value, we can actually build another network that output the q values corresponding to each 4 action simultaneously.
next we will learn about how to choose actions
While we are still learning/building a neural network, we need to pick actions. if the model is still learning, we don’t really know what actions to take in each state, if we did know, we would already be done learning. Even we are still learning and don’t have a good estimate of Q(s,a) yet, there are some options that show how we implement the part of the algorithm that “takes actions.”
option 1 just pick action a that maximizes whatever Q function available to us during the training even though the Q function is not the best one, this option works but is not the best. this option is also called greedy policy or exploitation policy in reinforcement literature, because we try to always get the best Q(s,a).
because of the randomization we implemented in the beginning, it is possible that the model never ever get exposed to fire the main thruster, so it won’t have chance to learn that firing the main thruster could be a good option. so option 2 adds some randomization to picking actions so that the neural network can learn to overcome its own possible preconceptions about whay might be a bad idea that turns out not to be the case. the second option is also called epsilon greedy policy which is the most common way to make reinforcement learning algorithm explore a little bit. It is also common to start epsilon high and then gradually decrease so the model get to explore more options in the beginning and then gradually aim for the best q values.
next, we will learn about how to tune the parameters to make the algorithm runs more efficiently. The first technique is mini-batch, and this technique could also be applied for supervised learning to make it run faster, no matter it is a traditional machine learning model or neural network model. the second technique is soft update which helps the model converge at a better solution
Mini-batch
in supervised learning, every step of gradient descent needs to calculate the average of the loss function across the whole dataset. if there are millions of data points, the process will be time-consuming. the idea of mini-batch gradient descent is to not use all data points to calculate average of loss. instead, we pick a small number, like 1000, to calculate the derivitive.
what mini-batch does is to pick a different subset of data at each iteration. sometimes we might pick a bad subset and the loss will not move towards the optimal direction, but every iteration is much more computationally inexpensive.
soft update
in the above algorithm, we set Q to be the new Q after each iteration, but it is possible the the new one is worse than the current one due to some poor randomization. Q function is consist of parameters w and b, so we can update our Q function by setting w and b to be the new w and b. Instead of changing them abruptly, soft update changes them gradually as shown below. it turns out that soft update makes the algorithm converge more reliably and prevent from diverging.
