NPFL122, Lecture 1 Introduction to ReinforcementLearning
22
0
0
Fulltext
(2) History of Reinforcement Learning Develop goal-seeking agent trained using reward signal. Optimal control in 1950s – Richard Bellman Trial and error learning – since 1850s Law and effect – Edward Thorndike, 1911 Shannon, Minsky, Clark&Farley, … – 1950s and 1960s Tsetlin, Holland, Klopf – 1970s Sutton, Barto – since 1980s Arthur Samuel – first implementation of temporal difference methods for playing checkers. Notable successes Gerry Tesauro – 1992, human-level Backgammon playing program trained solely by self-play IBM Watson in Jeopardy – 2011. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 2/22.
(3) History of Reinforcement Learning Recent successes Human-level video game playing (DQN) – 2013 (2015 Nature), Mnih. et al, Deepmind 29 games out of 49 comparable or better to professional game players 8 days on GPU human-normalized mean: 121.9%, median: 47.5% on 57 games A3C – 2016, Mnih. et al 4 days on 16-threaded CPU human-normalized mean: 623.0%, median: 112.6% on 57 games Rainbow – 2017 human-normalized median: 153% Impala – Feb 2018 one network and set of parameters to rule them all human-normalized mean: 176.9%, median: 59.7% on 57 games PopArt-Impala – Sep 2018 human-normalized median: 110.7% on 57 games. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 3/22.
(4) History of Reinforcement Learning Recent successes AlphaGo Mar 2016 – beat 9-dan professional player Lee Sedol AlphaGo Master – Dec 2016 beat 60 professionals beat Ke Jie in May 2017 AlphaGo Zero – 2017 trained only using self-play surpassed all previous version after 40 days of training AlphaZero – Dec 2017 self-play only defeated AlphaGo Zero after 34 hours of training (21 million games) impressive chess and shogi performance after 9h and 12h, respectively. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 4/22.
(5) History of Reinforcement Learning Recent successes Dota2 – Aug 2017 won 1v1 matches against a professional player MERLIN – Mar 2018 unsupervised representation of states using external memory partial observations beat human in unknown maze navigation FTW – Jul 2018 beat professional players in two-player-team Capture the flag FPS solely by self-play trained on 450k games each 5 minutes, 4500 agent steps (15 per second) OpenAI Five – Aug 2018 won 5v5 best-of-three match against professional team 256 GPUs, 128k CPUs 180 years of experience per day NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 5/22.
(6) History of Reinforcement Learning Recent successes Improved translation quality in 2016 Discovering discrete latent structures TARDIS – Jan 2017 allow using discrete external memory …. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 6/22.
(7) Multi-armed Bandits. http://www.infoslotmachine.com/img/one-armed-bandit.jpg. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 7/22.
(8) Multi-armed Bandits. Figure 2.1 of "Reinforcement Learning: An Introduction, Second Edition".. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 8/22.
(9) Multi-armed Bandits We start by selecting action. R1 . Let. A1 ,. which is the index of the arm to use, and we get a reward of. We then repeat the process by selecting actions. q∗ (a). be the real value of an action. A2 , A3 ,. …. a:. q∗ (a) = E[Rt ∣At = a]. Denoting. Qt (a). Qt (a). our estimated value of action. to converge to. q∗ (a).. at time. A natural way to estimate. def. Qt (a) = Following the definition of. a. t (before Qt (a) is. taking trial. t),. we would like. sum of rewards when action a is taken . number of times action a was taken. Qt (a),. we could choose a greedy action. At. as. def. At (a) = arg max Qt (a). a NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 9/22.
(10) ε-greedy. Method. Exploitation versus Exploration Choosing a greedy action is exploitation of current estimates. We however also need to explore the space of actions to improve our estimates. An. ε-greedy. method follows the greedy action with probability. random action with probability. NPFL122, Lecture 1. History. 1 − ε,. and chooses a uniformly. ε.. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 10/22.
(11) ε-greedy. Method 1.5. ε. =0 1 .. ε 1. ε. Average reward. =0 01 .. =0 (greedy). 0.5. 0 01. 250. 500. 750. 1000. Steps 100% 80%. % Optimal action. ε. =0 1 .. 60%. ε. 40%. ε. 20%. =0 01 .. =0 (greedy). 0% 01. 250. 500. 750. 1000. Steps Figure 2.2 of "Reinforcement Learning: An Introduction, Second Edition".. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 11/22.
(12) ε-greedy. Method. Incremental Implementation Let. Qn+1. be an estimate using. n. rewards. R1 , … , Rn . n. Qn+1. 1 = ∑ Ri n i=1 n−1. 1 n−1 = (Rn + ∑ Ri ) n n − 1 i=1 1 = (Rn + (n − 1)Qn ) n 1 = (Rn + nQn − Qn ) n 1 = Qn + (Rn − Qn ) n NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 12/22.
(13) ε-greedy. Method Algorithm. A simple bandit algorithm Initialize, for Q( a) ← 0 N ( a) ← 0. a = 1 to k:. Loop forever: ⇢ with probability 1 − ε a Q( a) A ← argmax a random action with probability ε R ← bandit(A) N ( A) ← N ( A) + 1 ⇥ ⇤ 1 Q ( A ) ← Q ( A) + N ( A ) R − Q ( A). (breaking ties randomly). Algorithm 2.4 of "Reinforcement Learning: An Introduction, Second Edition".. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 13/22.
(14) Fixed Learning Rate Analogously to the solution obtained for a stationary problem, we consider. Qn+1 = Qn + α(Rn − Qn ). Converges to the true action values if. ∞. ∞. ∑ αn = ∞ and. ∑ αn2 < ∞.. n=1. n=1. Biased method, because. n. Qn+1 = (1 − α)n Q1 + ∑ α(1 − α)n−i Ri . i=1. The bias can be utilized to support exploration at the start of the episode by setting the initial values to more than the expected value of the optimal solution.. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 14/22.
(15) Optimistic Initial Values and Fixed Learning Rate. 100%. Optimistic, greedy optimistic, greedy Q1 =5, ε =0 Q01 = 5, !!= 0. 80%. % Optimal action. ε -greedy Realistic, realistic, ! -greedy. 60%. Q1Q=0=, 0,ε =0!!.=1 0.1 01. 40% 20% 0% 01. 200. 400. 600. 800. 1000. Plays Steps Figure 2.3 of "Reinforcement Learning: An Introduction, Second Edition".. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 15/22.
(16) Upper Confidence Bound Using same epsilon for all actions in. ε-greedy. method seems inefficient. One possible. improvement is to select action according to upper confidence bound (instead of choosing a random action with probability. ε):. At = arg max [Qt (a) + c def. a. ln t ]. Nt (a). The updates are then performed as before (e.g., using averaging, or fixed learning rate. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. α).. 16/22.
(17) Motivation Behind Upper Confidence Bound Actions with little average reward are probably selected too often. Instead of simple. ε-greedy. approach, we might try selecting an action as little as possible, but. still enough to converge. Assuming random variables. Xi. bounded by. [0, 1]. and. ˉ = ∑N Xi , X i=1. (Chernoff-)Hoeffding's. inequality states that. −2nδ 2 ˉ ˉ P (X − E[X ] ≥ δ) ≤ e . Our goal is to choose. δ. such that for every action,. α. 1 P (Qt (a) − q∗ (a) ≥ δ) ≤ ( ) . t We can achieve the required inequality (with. δ≥ NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. α = 2). by setting. (ln t)/Nt (a). Non-stationary Problems. UCB. Gradient. Comparison. 17/22.
(18) Asymptotical Optimality of UCB We define regret as a difference of maximum of what we could get (i.e., repeatedly using action with maximum expectation) and what a strategy yields, i.e.,. N. regretN = N max q∗ (a) − ∑ E[Ri ]. def. a. i=1. It can be shown that regret of UCB is asymptotically optimal, see Lai and Robbins (1985), Asymptotically Efficient Adaptive Allocation Rules.. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 18/22.
(19) Upper Confidence Bound Results. UCB. 1.5. c=2. -greedy = 0.1 1. Average reward 0.5. 0 1. 250. 500. 750. 1000. Steps Figure 2.4 of "Reinforcement Learning: An Introduction, Second Edition".. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 19/22.
(20) Gradient Bandit Algorithms Let. Ht (a). be a numerical preference for an action. a. at time. t.. We could choose actions according to softmax distribution:. eHt (a) π(At = a) = softmax(a) = . H (b) t ∑b e def. Usually, all. H1 (a). are set to zero, which corresponds to random uniform initial policy.. Using SGD and MLE loss, we can derive the following algorithm:. Ht+1 (a) ← Ht (a) + αRt ([a = At ] − π(a)).. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 20/22.
(21) Gradient Bandit Algorithms 100%. α = 0.1. 80%. with baseline. α = 0.4 % Optimal action. 60%. α = 0.1 40%. without baseline. α = 0.4. 20% 0% 1. 250. 500. 750. 1000. Steps Figure 2.5:. Average performance of the gradient bandit algorithm with and without a reward. baseline on the 10-armed testbed when the q∗ (a) are chosen to be near +4 rather than near zero. Figure 2.5 of "Reinforcement Learning: An Introduction, Second Edition".. NPFL122, Lecture 1. History. Multi-armed Bandits. ε-greedy. Non-stationary Problems. UCB. Gradient. Comparison. 21/22.
(22) Method Comparison. 1.5. greedy with optimistic initialization α = 0.1. UCB 1.4. Average reward over first 1000 steps. 1.3. -greedy. gradient bandit. 1.2 1.1 1 1/128. NPFL122, Lecture 1. History. 1/64. Multi-armed Bandits. 1/32. 1/16. ε-greedy. 1/8. ε α. 1/4. c Q0. 1/2. 1. 2. 4. Figure 2.6 of "Reinforcement Learning: An Introduction, Second Edition".. Non-stationary Problems. UCB. Gradient. Comparison. 22/22.
(23)
Související dokumenty
• December 1th 1955, Montgomery, Alabama Rosa refused to give up her bus seat to a white man. (She broke Jim
Yankova points out that if career development is external, the visible to the individual and society secment, then professional qualification is internal, meaningful (Yankova,
5/2019 Security analysis of FPGAs designs through reinforcement learning Decision Processes to craft stealthy attack sequences.. against a
A.5 Example of an induced Greek dependency tree using unsupervised part-of-speech tags (100
However, the goal of machine learning is to perform well on previously unseen data, to achieve lowest generalization error or test error...
History of Reinforcement Learning Recent successes AlphaGo Mar 2016 – beat 9-dan professional player Lee Sedol AlphaGo Master – Dec 2016 beat 60 professionals, beat Ke Jie in May
• Milica Gašić’s slides (Cambridge University): http://mi.eng.cam.ac.uk/~mg436/teaching.html. • Sutton & Barto (2018): Reinforcement Learning: An Introduction (2 nd
Figure 3.6, page 76 of Deep Learning Book, http://deeplearningbook.org... Why Normal Distribution Central
