Author: Akhtar, Dr. Engr. S.M. Farrukh
-
loc 382 - For example, a telecom company is very much interested in knowing which customers are going to terminate their service. If they are aware or can predict those customers, they can offer them special deals to retain them.
-
loc 462 - Some popular examples of unsupervised learning algorithms are: Apriori algorithm (association problems) K-means (clustering problems)
-
loc 483 - Reinforcement learning is a type of machine learning that determines the action within a specific environment in order to maximize a reward.
-
loc 485 - must continue to interact with the environment in order to determine the optimal policy through trial and error.
-
loc 495 - That is essentially unsupervised learning; you have lots of data and you figure out the patterns and try to execute those patterns. Cycling does not work that way! You have to get down to cycling and try it yourself. How to learn cycling? is neither supervised nor unsupervised learning. It’s a different paradigm. It is reinforcement learning, one that you learn by trial and error.
-
loc 505 - Reinforcement learning is actually a mathematical structure that captures this kind of trial-and-error learning. The goal here is to learn about the system through interaction with the system.
-
loc 519 - An agent in reinforcement learning always takes actions.
-
loc 521 - A state is the place or the situation in which the agent finds itself.
-
loc 686 - Exploration implies firm behaviors characterized by finding, risk taking, research, search, and improvement; while exploitation implies firm behaviors characterized by refinement, implementation, efficiency, production, and selection.
-
loc 689 - dilemma is how much more exploration is required, because when you try to explore the environment, you are most likely to keep hitting it negative rewards.
-
loc 798 - If you are interested to see the working of other environments all you need to do is replace CartPole-v0 with something like MsPacman-v0or MountainCar-v0 .
-
loc 888 - An MDP is a discrete time-state transition system.
-
loc 889 - Furthermore, finite MDPs or finite MDPs having the finite actions and state fulfill the requirement of a Markov property.
-
loc 897 - it represents all the states that one can be in.
-
loc 904 - The point is that your action set will represent all the things that the agent, robot, or person we are trying to model is allowed to do.
-
loc 909 - produces the probability that you end up transitioning s’ given that you were in state s and you took action a.
-
loc 913 - The model is really an important thing and the reason for its importance is that it describes the rules of the game. It tells us what will happen if we do something in a particular place. It captures everything we can know about the transition:
-
loc 913 - The model is really an important thing and the reason for its importance is that it describes the rules of the game. It tells us what will happen if we do something in a particular place. It captures everything we can know about the transition: T(s, a, s’) ~ Probability(s’| s, a)
-
loc 920 - Next is the reward. It is a scalar value that you get from being in a state.
-
loc 930 - Hence, in order to be prepared, it is typical to compute a whole policy rather than a simple plan.
-
loc 931 - A policy is a mapping from states to actions.
-
loc 932 - Because of the Markov property, we’ll find that the choice of action needs to depend only on the current state (possibly the current time as well) and not on any of the previous states.
-
loc 934 - A policy is a function that takes state and returns an action. In other words, for any given state you are in, it tells you the action you should take: π(s) -> a
-
loc 999 - If we want to design the MDP to capture some world, then we have to think carefully about how we set the rewards in order to get the behavior that we wish. No matter what you do, you have to inject the domain knowledge somehow; otherwise, there is no learning to do and, in this case, the reward is basically telling you how important it is to get to the end.
-
loc 1010 - Rather than going up, it makes sense to go the long way round because we get some negative reward, but it’s a small negative reward compared to the positive reward where we end up. This only makes sense if we will live long enough and we can afford to take the long route.
-
loc 1034 - These are two different sequences and, in the beginning we were comparing them with S0 in front of both the sequences. It means that S0 following by all the S and S0 following by all S primes, then we have the same preference when S0 is missing and it is called stationary of preferences.
-
loc 1034 - These are two different sequences and, in the beginning we were comparing them with S0 in front of both the sequences. It means that S0 following by all the S and S0 following by all S primes, then we have the same preference when S0 is missing and it is called stationary of preferences. Another way to look at it is as follows: if we prefer one sequence of states today over another sequence of states, then we will prefer that
-
loc 1034 - These are two different sequences and, in the beginning we were comparing them with S0 in front of both the sequences. It means that S0 following by all the S and S0 following by all S primes, then we have the same preference when S0 is missing and it is called stationary of preferences. Another way to look at it is as follows: if we prefer one sequence of states today over another sequence of states, then we will prefer that sequence of states over the same sequence tomorrow.
-
loc 1079 - The optimal policy is simply π*, the one that maximizes our long-term expected reward. We have an expected value of the sum of the discounted rewards at time t, given π: π* = argmaxπ E [∑∞t=0 γt R(St) | π ]
-
loc 1085 - utility in such a way that it’s going to help us to solve it. The utility of the particular state depends on the policy I am following and that’s simply going to be the expected set of states that I am going to see from that point on given I am following the policy:
-
loc 1093 - we are going to get from that point on. Let’s say I want to go
-
loc 1093 - Utility is both the reward we get for that state and all the rewards that we are going to get from that point on. Let’s say I want to go to a college for a master’s degree but it costs me $10,000. If I spend $10,000, at the end I get a degree. The point is that there is an immediate negative reward of $10,000. But at the end of the day, I get something positive out of it.
-
loc 1109 - Uπ*(s) = R(s) + γ maxa ∑s’ T(s, a, s’) Uπ*(s’) The true utility of the state s then is the reward that I get for being in the state; plus, I am now going to discount all of the reward that I get from that point on.
-
loc 1621 - In some sense, the states, actions, and transitions represent the physical world and the rewards and discount represent the kind of task description.
-
loc 1626 - The utilities factor in the long-term aspects, and the rewards just tell us at each moment. Utilities are like a group of rewards.
-
loc 1644 - Dynamic programming, like the divide-and-conquer method, solves problems by combining solutions to subproblems.
-
loc 1645 - Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem.
-
loc 1646 - contrast, dynamic programming is applicable when subproblems are not independent, that is, when subproblems share subproblems. In this context, a divide-and-conquer
-
loc 1646 - contrast, dynamic programming is applicable when subproblems are not independent, that is, when subproblems share subproblems.
-
loc 1653 - maps states to actions. The whole activity is called planning:
-
loc 1656 - However, a learner is going to do something different. Instead of taking a model as input, it’s going to take a transition.
-
loc 1657 - It’s going to take samples of being in some state, taking some action, observing a reward, and observing the state that is at the other end of that transaction. Using that information, we are going to learn a policy instead of computing it; we call this learning:
-
loc 1667 -
-
loc 1668 - Model-based reinforcement learning
-
loc 1673 -
-
loc 1674 - Model-free planner or RL-based planner
-
loc 1675 - We start off with a model and then we pretend that we don’t have a model. We are just in a learning situation by turning the model into transitions merely by simulating them. Then the learner interacts with the simulator and spits out a policy. We called this a model-free planner or RL-based planner.
-
loc 1693 - What was a sequence of sequences, or a set of sequences of states, and turn them into a single number?
-
loc 1694 - These are the four steps we need to evaluate a policy: State the transition to immediate rewards or R. Truncate according to the horizon or T. Summarize sequences or Return. Summarize over sequences or weighted average.
-
loc 1699 - In the third step, we need to take that list of truncated numbers, and for each of the sequences, turn it into a single number for that sequence. This is also called Return: Return = ∑Ti=1 γi Ri
-
loc 1703 - fourth step: we have to take those multiple numbers, one number for each of the sequences, and turn them into a single number that summarizes all of them. So, we just take the weighted average.
-
loc 1719 - Is the Bellman equation linear? No, because this equation contains max and that is problematic. This max operation makes the equation non-linear. So it’s looking really good for a moment there. We have got N equations and N unknowns and we know how to solve that, but the max operation makes it a very weird non-linearity.
-
loc 1720 - We have got N equations and N unknowns and we know how to solve that, but the max operation makes it a very weird non-linearity.
-
loc 1722 - This means we can’t solve it the way we want to.
-
loc 1723 - Here’s the algorithm that, sort of works. It’s really simple. We just start with some arbitrary utilities, but then we update them based on their neighbors.
-
loc 1726 - What does this based on neighbors mean? It actually means we are going to update the utility for a state based on all the states that it can reach.
-
loc 1728 - how to update them and it will be clear: Ut+1(s) = R(s) + γ maxa ∑s’ T(s, a, s’) Ut(s')
-
loc 1731 - estimate the utility of some state S by simply recalculating it to be the actual reward that I get for entering state S plus the discount utility that I expect given the original estimates of my utility.
-
loc 1736 - The next little step about updating utilities based on neighbors makes some sense because effectively a neighbor is any state that you can reach, which is determined by the transition function. But
-
loc 1747 - And if that gets better for any of the states, then eventually that betterness will propagate out to all the other states. That
-
loc 1754 - And so you keep iterating through this, the latest truth becomes more important than the past less truth.
-
loc 1791 - eventually we are going to figure out the utilities or the values for all the states. Goal state +1 going to propagate out towards the other states. Where the failure state -1 will propagate out less because we are going to try to avoid falling into the failure state.
-
loc 1796 - We don’t care about having the correct utilities, even though by having the correct utilities, we have the right policy.
-
loc 1799 - what you end up wanting to do is get a utility that’s good enough to get you to π. Which is one reason why you don’t have to worry about getting the absolute convergence in value iteration.
-
loc 1913 - Now it’s true that given the true utilities we can find a policy, but maybe we don’t have to find the true utilities in order to find the optimal policy. So, here is the algorithm; it’s going to look a lot like value iteration: Start with π0 <— Guess. Evaluate the given πt calculate Ut = Uπt. Improve πt+1 = argmaxa ∑ T(s, a, s’) Ut(s’).
-
loc 1920 - So, given a policy, we are able to evaluate it by figuring out what the utility of that policy is. Then we are actually going to improve that policy in a way similar to what we did with value iteration. We are going to update our policy, Time t plus 1, to be the policy that takes the action that maximizes the expected utility based on what we just calculated for πt.
-
loc 1924 - If we discover that in some state where there is a very good action That state gets you to some really nice place it gives you a really big reward. This continues and you do fairly well. Well, then all other states that can reach that state might end up taking a different action than they did before, because now the best action would be to move towards that state.
-
loc 1943 - This inversion can still be very painful if we don’t worry about being highly efficient. We know it’s roughly N cubed, and if there are a lot of states, this can be kind of painful. But it turns out that there’s a little trick we can do: a little step evaluate iteration here for a while to get an estimate.