Chapter 1 Flashcards
2 most important characteristics of RL
- Trial and Error search
2. Delayed reward
Difference between RL + SL
SL - Objective: Generalize its responses so that it acts correctly in situations not present in the training set.
Learn from a training set of labeled examples provided by a knowledgeable external supervisor. Each example is a description of a situation together with a label of the correct action that the system should take in that situation.
RL -> For interactive problems, we cannot obtain examples of desired behavior that are both correct and representative of all the situations in which the agent has to act. In uncharted territory, an agent must be able to learn from its own experience
Difference between RL + UL
UL ->
Finding structure hidden in collections of unlabeled data
RL ->
Maximize reward instead of trying to find hidden structure
challenge with RL
One of the challenges that arise in reinforcement learning, and not in other kinds of learning, is the trade-off between exploration and exploitation. To obtain a lot of reward, a reinforcement learning agent must prefer actions that it has tried in the past and found to be effective in producing reward. But to discover such actions, it has to try actions that it has not selected before. The agent has to exploit what it has already experienced in order to obtain reward, but it also has to explore in order to make better action selections in the future. The dilemma is that neither exploration nor exploitation can be pursued exclusively without failing at the task. The agent must try a variety of actions and progressively favor those that appear to be best.
Share features of RL examples
All involve interaction between an active decision-making agent and its environment, within which the agent seeks to achieve a goal despite uncertainty about its environment.
The agent’s actions are permitted to affect the future state of the environment (e.g., the next chess position, the level of reservoirs of the refinery, the robot’s next location and the future charge level of its battery), thereby affecting the actions and opportunities available to the agent at later times.
Correct choice requires taking into account indirect, delayed consequences of actions, and thus may require foresight or planning.
6 subelements of RL
Agent
Environment
Policy -
- Mapping from perceived states of the environment to actions to be taken when in those states.
- Corresponds to what in psychology would be called a set of stimulus–response rules or associations.
- simple function or lookup table
- core of a reinforcement learning agent in the sense that it alone is su fficient to determine behavior.
- policies may be stochastic, specifying probabilities for each action.
Reward Signal -
- defines the goal of a reinforcement learning problem.
- On each time step, the environment sends to the reinforcement learning agent a single number called the reward. The agent’s sole objective is to maximize the total reward it receives over the long run.
- primary basis for altering the policy; if an action selected by the policy is followed by low reward, then the policy may be changed to select some other action in that situation in the future. In general, reward signals may be stochastic functions of the state of the environment and the actions taken.
Value Function -
- Whereas the reward signal indicates what is good in an immediate sense, a value function specifies what is good in the long run.
- Roughly speaking, the value of a state is the total amount of reward an agent can expect to accumulate over the future, starting from that state.
- Whereas rewards determine the immediate, intrinsic desirability of environmental states, values indicate the long-term desirability of states after taking into account the states that are likely to follow and the rewards available in those states.
- To make a human analogy, rewards are somewhat like pleasure (if high) and pain (if low), whereas values correspond to a more refined and farsighted judgment of how pleased or displeased we are that our environment is in a particular state.
- We seek actions that bring about states of highest value, not highest reward, because these actions obtain the greatest amount of reward for us over the long run.
- Rewards are basically given directly by the environment, but values must be estimated and re-estimated from the sequences of observations an agent makes over its entire lifetime. In fact, the most important component of almost all reinforcement learning algorithms we consider is a method for efficiently estimating values.
Model (optional)
- This is something that mimics the behavior of the environment, or more generally, that allows inferences to be made about how the environment will behave.
- Models are used for planning, by which we mean any way of deciding on a course of action by considering possible future situations before they are actually experienced.
How does RL differ from genetic algorithms, genetic programming, simulated annealing, and other optimization methods
ONLY RL estimate value functions
These methods apply multiple static policies each interacting over an extended period of time with a separate instance of the environment. The policies that obtain the most reward, and random variations of them, are carried over to the next generation of policies, and the process repeats.
Explain how tic tac toe is solved with classical optimization methods
Classical optimization methods for sequential decision problems, such as dynamic programming, can compute an optimal solution for any opponent, but require as input a complete specification of that opponent, including the probabilities with which the opponent makes each move in each board state.
About the best one can do on this problem is first to learn a model of the opponent’s behavior, up to some level of confidence, and then apply dynamic programming to compute an optimal solution given the approximate opponent model.
Explain how tic tac toe is solved with evolutionary methods
The frequency of wins gives an unbiased estimate of the probability of winning with that policy, and can be used to direct the next policy selection. But each policy change is made only after many games, and only the final outcome of each game is used: what happens during the games is ignored
directly search the space of possible policies for one with a high probability of winning against the opponent.
Here, a policy is a rule that tells the player what move to make for every state of the game—every possible configuration of Xs and Os on the three-by-three board.
For each policy considered, an estimate of its winning probability would be obtained by playing some number of games against the opponent.
This evaluation would then direct which policy or policies were considered next. A typical evolutionary method would hill-climb in policy space, successively generating and evaluating policies in an attempt to obtain incremental improvements. Or, perhaps, a genetic-style algorithm could be used that would maintain and evaluate a population of policies. Literally hundreds of different optimization methods could be applied.
Explain how tic tac toe is solved with a value function
Set up a table of numbers, one for each possible state of the game. Each number will be the latest estimate of the probability of our winning from that state. We treat this estimate as the state’s value, and the whole table is the learned value function.
State A has higher value than state B, or is considered “better” than state B, if the current estimate of the probability of our winning from A is higher than it is from B.
Assuming we always play Xs, then for all states with three Xs in a row the probability of winning is 1, because we have already won. Similarly, for all states with three Os in a row, or that are filled up, the correct probability is 0, as we cannot win from them. We set the initial values of all the other states to 0.5, representing a guess that we have a 50% chance of winning.
We then play many games against the opponent. To select our moves we examine the states that would result from each of our possible moves (one for each blank space on the board) and look up their current values in the table. Most of the time we move greedily, selecting the move that leads to the state with greatest value, that is, with the highest estimated probability of winning. Occasionally, however, we select randomly from among the other moves instead. These are called exploratory moves because they cause us to experience states that we might otherwise never see.
While we are playing, we change the values of the states in which we find ourselves during the game. We attempt to make them more accurate estimates of the probabilities of winning. To do this, we “back up” the value of the state after each greedy move to the state before the move. More precisely, the current value of the earlier state is updated to be closer to the value of the later state.
Exercise 1.1: Self-Play: Suppose, instead of playing against a random opponent, the reinforcement learning algorithm described above played against itself. What do you think would happen in this case? Would it learn a different way of playing?
The algorithm will continue to adapt until it reaches an equilibrium, which may be either fixed (always making the same moves), or cyclical. It is possible to reach a higher skill level than against a fixed opponent but it may also take miss paths toward stronger over all play because it is reacting to itself
if two players always choose the best move for themself then they reach what is called a nash equilibria.
A nash equilibria happens when no player is willing to change his moves because his objective function will decrease (More or less ).
If an agent is playing against itself, since they are using the same policy, in my opinion they will reach a nash equilibria because they will learn the best moves based on the same policy, and so both will always use the best move possible
Exercise 1.2: Symmetries Many tic-tac-toe positions appear different but are really the same because of symmetries. How might we amend the learning process described above to take advantage of this? In what ways would this change improve the learning process? Now think again. Suppose the opponent did not take advantage of symmetries. In that case, should we? Is it true, then, that symmetrically equivalent positions should necessarily have the same value?
We could improve our reinforcement learning algorithm by taking advantage of symmetryby simplifying the definition of the “state” and “action” upon which the algorithm wouldworks. By simplifying the state in such a way that the dimension decreases we can be moreconfident that our learned results will be statistically significant since the state space weoperate in is reduced. If our opponentwastaking advantage of symmetries in the gametic-tac-toe our algorithm should also since this fact, would enable us to be a better gameplayer against this type of player. If our player doesnotuse symmetries then our algorithmshould not either (except to reduce the state space as discussed above) since enforcing asymmetry on our opponent (that is not in fact there) should decrease our performance whenplaying against this type of opponent
Exercise 1.3: Greedy Play Suppose the reinforcement learning player was greedy, that is, it always played the move that brought it to the position that it rated the best. Might it learn to play better, or worse, than a nongreedy player? What problems might occur?
As will be discussed later in this book a greedy approach willnot be able to learn moreoptimal moves as play unfolds. Thus there is a natural trade-off between attempting toexplore the space of possibilities and selecting the actionon this step that has the greatestreward. Problems with direct greedy play would be that our player fails to be able tocapture moves that result in improved rewards because we never take a chance on unknown(or unexplored) actions.
Exercise 1.4: Learning from Exploration Suppose learning updates occurred after all moves, including exploratory moves. If the step-size parameter is appropriately reduced over time (but not the tendency to explore), then the state values would converge to a different set of probabilities. What (conceptually) are the two sets of probabilities computed when we do, and when we do not, learn from exploratory moves? Assuming that we do continue to make exploratory moves, which set of probabilities might be better to learn? Which would result in more wins?
If we do not learn from exploratory moves then the state probabilities learned would effectively be random in that we are not updating our undertaking of what happens when in a given state and a given action is taken.
If we learn from our exploratory moves then our limiting probabilities should be those from the desired distribution of state and action selections. Obviously a more complete understanding of the probability densities should result in a better play since the player better understands the “game” he or she is playing
Exercise 1.5: Other Improvements Can you think of other ways to improve the reinforcement learning player? Can you think of any better way to solve the tic-tac-toe problem as posed?
One possible way would be to have a saved library of scripted plays. For example the logic would be something like, when in a set of known states always execute the following moves. This is somewhat like the game of chess where there are various “opening” positions that expert players have deemed good. Hopefully this might expedite the total learning processor at least improve our reinforcement players initial play.
Since the the tic-tac-toe problem is so simple we can solve this problem (using recursion) and computing all possible opponents moves and selecting at each step the move that optimizes our chance of winning.
