rl-tutorial.ps (mpage)

A Reinforcement Learning Tutorial forGame Strategy AcquisitionThomas Philip RunarssonMarch 17, 2005T.P. Runarsson (tpr@hi.is)version 0.0.3 March 17, 2005IntroductionThis tutorial is based on:• the book by Richard S. Sutton and Andrew G. Barto,Reinforcement Learning An Introduction. MIT Press, 1998.Also available on-line here:http://www.cs.ualberta.ca/~sutton/book/the-book.html• the computational intelligence course taught at the Universityof Iceland.1version 0.0.3 March 17, 2005 version 0.0.3 March 17, 2005The n-armed Bandit Problem 1.5ε=0.1ε=0.011ε=0You must choose between n different options or actions. Havingperformed that action a you receive a reward r. The reward is 0.5sampled from a stationary probability distribution that depend onthe action made. 00 200 400 600 800 1000plays∗Let Q (a) denote the mean (expected) reward received when100action a is selected, this is also known as the value of action a. ε=0.1Q (a) is the estimated value at the tth play, that istε=0.0150r +r +...+r1 2 kaQ (a) = =E[r]t ε=0ka0where tth play action a has been chosen k times prior to t,a 0 200 400 600 800 1000playsyielding rewards r ,r , ..., r .1 2 kaWith = 0.1 the optimal action is never selected more than91% of the time, but will find the optimal action earlier than = 0.01. However, in the end = 0.01 will perform better,it may in this case be a good idea to start with a large anddecrease it over time. The greedy method performs ...