Introduction of Reinforcement Learning - 國立臺灣大學

1 Introduction of Reinforcement Learning Deep Reinforcement Learning Reference Textbook: Reinforcement Learning : An Introduction Lectures of David Silver ml (10 lectures, around 1:30 each). t_learning/ (Deep Reinforcement Learning ). Lectures of John Schulman Scenario of Reinforcement Learning Observation Action State Change the environment Agent Don't do Reward that Environment Scenario of Reinforcement Learning Agent learns to take actions maximizing expected reward. Observation Action State Change the environment Agent Thank you. Reward Environment to-clean-site-structure/. Machine Learning Looking for a Function Actor/Policy Observation Action Action =. Function Function ( Observation ) output input Used to pick the Reward best function Environment Learning to play Go Observation Action Reward Next Move Environment Agent learns to take Learning to play Go actions maximizing expected reward. Observation Action Reward reward = 0 in most cases If win, reward = 1.

2 If loss, reward = -1. Environment Learning to play Go Supervised: Learning from teacher Next move: Next move: 5-5 3-3 . Reinforcement Learning Learning from experience First move many moves Win! (Two agents play with each other.). Alpha Go is supervised Learning + Reinforcement Learning . Learning a chat-bot Machine obtains feedback from user How are Hello you? Bye bye Hi . -10 3. Chat-bot learns to maximize the expected reward Learning a chat-bot Let two agents talk to each other (sometimes generate good dialogue, sometimes bad). How old are you? How old are you? See you. I am 16. See you. I though you were 12. See you. What make you think so? Learning a chat-bot By this approach, we can generate a lot of dialogues. Use some pre-defined rules to evaluate the goodness of a dialogue Dialogue 1 Dialogue 2 Dialogue 3 Dialogue 4. Dialogue 5 Dialogue 6 Dialogue 7 Dialogue 8. Machine learns from the evaluation Deep Reinforcement Learning for Dialogue Generation Learning a chat-bot Supervised Hello Say Hi.

3 Bye bye Say Good bye . Reinforcement .. Hello Bad Agent Agent More applications Flying Helicopter Driving Robot Google Cuts Its Giant Electricity Bill With DeepMind- Powered AI. giant-electricity-bill-with-deepmind-pow ered-ai Text generation Example: Playing Video Game Widely studies: Gym: Universe: Machine learns to play video games as human players What machine observes is pixels Machine learns to take proper action itself Example: Playing Video Game Termination: all the aliens are killed, Space invader or your spaceship is destroyed. Score (reward). Kill the aliens shield fire Example: Playing Video Game Space invader Play yourself: l How about machine: zx4 HRyqgTCVk9ltw Example: Playing Video Game Start with observation 1 Observation 2 Observation 3. Obtain reward Obtain reward 1 = 0 2 = 5. Action 1 : right Action 2 : fire . (kill an alien). Usually there is some randomness in the environment Example: Playing Video Game Start with observation 1 Observation 2 Observation 3.

4 This is an episode. After many turns Game Over Learn to maximize the (spaceship destroyed). expected cumulative reward per episode Obtain reward . Action . Properties of Reinforcement Learning Reward delay In space invader, only fire obtains reward Although the moving before fire is important In Go playing, it may be better to sacrifice immediate reward to gain more long-term reward Agent's actions affect the subsequent data it receives Exploration Alpha Go: policy-based + value-based Outline + model-based Model-free Approach Policy-based Value-based Learning an Actor Actor + Critic Learning a Critic Model-based Approach Policy-based Approach Learning an Actor Three Steps for Deep Learning Step 1: Step 2: Step 3: pick define Neural a set Network goodness of the best ofasfunction Actor function function Deep Learning is so simple . Neural network as Actor Input of neural network: the observation of machine represented as a vector or a matrix Output neural network : each action corresponds to a neuron in output layer NN as actor left Probability right of taking fire the action pixels What is the benefit of using network instead of lookup table?

5 Generalization Three Steps for Deep Learning Step 1: Step 2: Step 3: pick define Neural a set Network goodness of the best ofasfunction Actor function function Deep Learning is so simple . Goodness of Actor Total Loss: . Review: Supervised Learning = . Training Example =1. 1 . x1 y1 As close as 1. x2 possible Given a set . of Softmax y2 0. parameters target .. Loss x256 y10 0. Goodness of Actor Given an actor with network parameter . Use the actor to play the video game Start with observation 1. Machine decides to take 1. Total reward: = =1 . Machine obtains reward 1 Even with the same actor, Machine sees observation 2 is different each time Machine decides to take 2. Machine obtains reward 2 Randomness in the actor Machine sees observation 3 and the game . Machine decides to take We define as the Machine obtains reward END expected value of R . evaluates the goodness of an actor . We define as the Goodness of Actor expected value of R.

6 = 1 , 1 , 1 , 2 , 2 , 2 , , , , . | =. 1 1 | 1 , 1 , 2 | 1 , 1 2 | 2 , 2 , 3 | 2 , 2 .. = " "| , . = 1 | , , +1 | , = =1. left Actor right not related Control by . to your actor your actor fire Goodness of Actor An episode is considered as a trajectory . = 1 , 1 , 1 , 2 , 2 , 2 , , , , . = =1 . If you use an actor to play the game, each has a probability to be sampled The probability depends on actor parameter : | .. 1 Use to play the = | game N times, . =1 obtain 1 , 2 , , . Sum over all Sampling from | . possible trajectory N times Three Steps for Deep Learning Step 1: Step 2: Step 3: pick define Neural a set Network goodness of the best ofasfunction Actor function function Deep Learning is so simple . Gradient Ascent Problem statement = max .. Gradient ascent = 1 , 2 , , 1 , . Start with 0. 1 0 + 0 1. 2 1 + 1 2. = .. 1.. Policy Gradient = | =? . | . = | = | . | .. do not have to be differentiable It can even be a black box.

7 = | | 1 . =.. 1 Use to play the game N times, | . Obtain 1 , 2 , , . =1. Policy Gradient | =? = 1 , 1 , 1 , 2 , 2 , 2 , , , , .. | = 1 | , , +1 | , . =1. | .. = 1 + | , + , +1 | , . =1.. Ignore the terms | = | , . not related to . =1. | .. Policy Gradient = | , . + =1.. 1 1. | = | , .. =1 =1 =1.. 1 What if we replace = | , . with . =1 =1. If in machine takes when seeing in is positive Tuning to increase | . is negative Tuning to decrease | . It is very important to consider the cumulative reward of the whole trajectory instead of immediate reward . Policy Gradient Update Model Given actor parameter . 1 : 11 , 11 1 + . 21 , 21 1. =.. 2 1. : 12 , 12 2 | , .. 22 , 22 2 =1 =1.. Data Collection Policy Gradient 3. Considered as Minimize: . Classification Problem =1.. left 1. right 0. s fire 0. Maximize: =. " "| . + " "| . + . Policy Gradient =.. 1. | , . Given actor parameter . =1 =1. 1 : 11 , 11 1. 11 = . 21 , 21 1. left 1.. 11 NN right 0.

8 2: 12 , 12 2 fire 0. 22 , 22 2 12 = .. left 0. 12 NN right 0. fire 1. + . Policy Gradient =.. 1. | , . Given actor parameter . =1 =1. 1 : 11 , 11 1 2. Each training data is 21 , 21 1 2 weighted by .. 11 NN 11 = . 2: 12 , 12 2 1. 22 , 22 2 1 11 NN 11 = .. 12 NN 12 = . It is possible that . Add a Baseline is always positive. + .. 11.. | , | , .. =1 =1. =1 =1. It is probability . Ideal case a b c a b c Not The probability of the sampled actions not sampled Sampling will decrease. a b c a b c Value-based Approach Learning a Critic Critic A critic does not determine the action. Given an actor , it evaluates the how good the actor is An actor can be found from a critic. Q- Learning Critic State value function . When using actor , the cumulated reward expects to be obtained after seeing observation (state) s . s . scalar is large is smaller Critic = bad = good How to estimate . Monte-Carlo based approach The critic watches playing the game After seeing , Until the end of the episode.

9 The cumulated reward is . After seeing , Until the end of the episode, . the cumulated reward is . How to estimate . Temporal-difference approach , , , +1 . + = +1.. - +1 . +1 +1. Some applications have very long episodes, so that delaying all Learning until an episode's end is too slow. MC TD . Larger variance . unbiased + +1 +1. Smaller variance May be biased [Sutton, v2, MC TD Example ]. The critic has the following 8 episodes , = 0, , = 0, END. , = 1, END. = 3/4. , = 1, END. , = 1, END =? 0? 3/4? , = 1, END. , = 1, END Monte-Carlo: = 0. , = 1, END. , = 0, END Temporal-difference: + = . 3/4 0 3/4. (The actions are ignored here.). Another Critic State-action value function , . When using actor , the cumulated reward expects to be obtained after seeing observation s and taking a , = . s , . s , = . scalar a , = . for discrete action only Q- Learning interacts with the environment = TD or MC. Find a new actor Learning , . better than.

10 ? Q- Learning Given , , find a new actor better than .. Better : , for all state s . = max , .. does not have extra parameters. It depends on Q. Not suitable for continuous action a Deep Reinforcement Learning Actor-Critic Actor-Critic interacts with the environment = TD or MC. Update actor from Learning ' based on , , . , , . Actor-Critic Tips The parameters of actor and critic . can be shared left Network right Network fire Network . Asynchronous Source of image: future/simple- Reinforcement - Learning -wit h- tensorflow-part-8-asynchronous-actor-cri tic- 1 + . agents-a3c-c88f72a5e9f2#.68x6na7o9. 2. 1. Copy global parameters (other workers also 2. Sampling some data update models). 3. Compute gradients . 4. Update global 1. models 1.. Demo of A3C Racing Car (DeepMind). Demo of A3C. Visual Doom AI Competition @ CIG 2016. Concluding Remarks Model-free Approach Policy-based Value-based Learning an Actor Actor + Critic Learning a Critic Model-based Approach