Introduction to Reinforcement Learning - cs.ucsb.edu

1 Introduction to Reinforcement LearningX I N WA N GU C S B C S 2 8 1 BSlides adapted from Stanford CS231n1 Supervised LearningData: (x, y)xis data, y is label Goal: learn a function to map x yExamples:Classification, regression, object detection, semantic segmentation, image captioning, LearningData: xJust data, no label! Goal: learn some underlying hidden structure of the dataExamples:Clustering, dimensionality reduction, feature Learning , density estimation, LearningProblems involving an agent interacting with an environment, which provides numeric reward signals Goal: Learn how to take actions in order to maximize reward 4 OverviewWhat is Reinforcement Learning ?Markov Decision ProcessQ-LearningPolicy GradientActor Critic5agentenvironment6 Sequential Decision Making Goal: select actions to maximize total future reward Actions may have long term consequences Reward may be delayed It may be better to sacrifice immediate reward to gain more long-term reward Examples: A financial investment (may take months to mature) Refueling a helicopter (might prevent a crash in several hours) Blocking opponent moves (might help winning chances many moves from now) 7 Cart-Pole Problem8 Objective: Balance a pole on top of a movable cartState: angle, angular speed, position, horizontal velocityAction: horizontal force applied on the cartReward: 1 at each time step if the pole is uprightRobot Locomotion9 Objective: Make the robot move forward State: Angle and position of the joints Action.

2 Torques applied on jointsReward: 1 at each time step upright + forward movementAtari Games10 Objective: Complete the game with the highest reward State: Raw pixel inputs of the game stateAction: Game controls Left, Right, Up, DownReward: Score increase/decrease at each time stepGo11 Objective: Win the gameState: Positions of all pieces Action: Where to put the next piece downReward: 1 if win at the end of the game, 0 otherwiseMarkov Decision Process12 Markov Decision Process13A Simple MDP: Grid World14A Simple MDP: Grid World15 Optimal Policy 16 Optimal Policy 17 Value Function and Q-value Function18 Value Function and Q-value Function19 Value Function and Q-value Function20 Bellman Equation21 Bellman Equation22 Bellman Equation23 Solving The Optimal Policy24 Solving The Optimal Policy25 Solving The Optimal Policy26 Solving The Optimal Policy27 Solving The Optimal Policy: Q-learning28 Solving The Optimal Policy: Q-learning29 Solving The Optimal Policy: Q-learning30 Solving The Optimal Policy: Q-learning31 Solving The Optimal Policy: Q-learning32 Solving The Optimal Policy: Q-learning33 Case Study: Playing Atari Games34 Objective: Complete the game with the highest reward State: Raw pixel inputs of the game stateAction: Game controls Left, Right, Up, DownReward: Score increase/decrease at each time stepDeep Q-Network35 Deep Q-Network36 Input.

3 State stDeep Q-Network37 Conv + FC layersDeep Q-Network38 Last FC layer has 4-doutput (if 4 actions), corresponding to Q(st, a1), Q(st, a2), Q(st, a3), Q(st, a4)Deep Q-Network39 Last FC layer has 4-doutput (if 4 actions), corresponding to Q(st, a1), Q(st, a2), Q(st, a3), Q(st, a4)Number of actions between 4-18 depending on Atari game Deep Q-Network40 Last FC layer has 4-doutput (if 4 actions), corresponding to Q(st, a1), Q(st, a2), Q(st, a3), Q(st, a4)A single feedforward pass to compute Q-values for all actions from the current state => efficient! Number of actions between 4-18 depending on Atari game Training DQN: Loss Function41 Training DQN: Experience Replay42 Training DQN: Experience Replay43 Deep Q- Learning with Experience Replay44 Initialize replay memory, Q-network Deep Q- Learning with Experience Replay45 Play M episodes (full games)Deep Q- Learning with Experience Replay46 Initialize state (starting game screen pixels) at the beginning of each episode Deep Q- Learning with Experience Replay47 For each timestept of the gameDeep Q- Learning with Experience Replay48 With small probability, select a random action (explore), otherwise select greedy action from current policy Deep Q- Learning with Experience Replay49 Take the action (at), and observe the reward rtand next state st+1 Deep Q- Learning with Experience Replay50 Store transition in replay memory Deep Q- Learning with Experience Replay51 Experience Replay.

4 Sample a random minibatchof transitions from replay memory and perform a gradient descent step Value-based and Policy-based RL52 Value Based Learnt Value Function Implicit Policy ( -greedy) Policy Based No Value Function Learnt Policy Actor-Critic Learnt Value Function Learnt PolicyAdvantages of Policy-Based RL53 Advantages: Better convergence properties Effective in high-dimensional or continuous action spaces Can learn stochastic policiesDisadvantages: Typically converge to a local rather than global optimum Evaluating a policy is typically inefficient and high variance Policy Gradient54 Policy Gradient55 Policy Gradient56 REINFORCE algorithm57 REINFORCE algorithm58 REINFORCE algorithm59 Difficult to compute!!!REINFORCE algorithm60 Difficult to compute!!!REINFORCE algorithm61 REINFORCE algorithm62 REINFORCE algorithm63 Intuition64 Intuition65 Intuition66 Policy Gradient with Baseline67 Idea:Introduce a baseline function dependent on the state to reduce the variance (whether a reward is better or worse than what you expect to get) Policy Gradient with Baseline68 Idea:Introduce a baseline function dependent on the state to reduce the variance (whether a reward is better or worse than what you expect to get) A simple baseline: constant moving average of rewards experienced so far from all trajectories Actor-Critic69 Actor-Critic70 Actor-Critic71 Actor-Critic72 Case Study: Image Captioning with Policy Gradient73 Supervised Learning .

5 GT word as the input (the previous word) of the RNN language model Maximize the probability of the GT word given the current hidden stateReinforcement Learning (Policy Gradient): Sampled word as the previous word Maximize the defined reward ( CIDE rscore) of the whole sentence74 Summary75-Policy gradients: very general but suffer from high variance so requires a lot of samples. Challenge: sample-efficiency -Q- Learning : does not always work but when it works, usually more sample-efficient. Challenge: exploration -Guarantees: -Policy Gradients: Converges to a local minima of J( ), often good enough! -Q- Learning : Zero guarantees since you are approximating Bellman equation with a complicated function approximator76 Thank You !Xin Course CS231n: materials by David Silver: derivative trick.