Ch 8 딥강화학습

Chapter 8. 딥강화학습 < 기계학습개론 > 강의서울대학교컴퓨터공학부장병탁 교재 : 장교수의딥러닝, 홍릉과학출판사, 2017. Slides Prepared by 장병탁, 최진영 Biointelligence Laboratory School of Computer Science and Engineering Seoul National University Version 20171109 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 1

목차 8.1 강화학습과 MDP 문제... 4 8.2 MC 학습과 TD 학습.... 8 8.3 Sarsa와 Q학습알고리듬...... 11 8.4 딥큐넷 (DQN)...., 14 8.5 딥강화학습의활용 : AlphaGo.... 17 요약..... 19 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 2

들어가는질문 감독학습, 무감독학습과비교하여강화학습이다른점은무엇인가? 마코프결정문제 (MDP) 를정의하고다양한해결방법들을기술하시오. 벨만최적식, 동적프로그래밍의개념을설명하시오. MDP 문제해결을위한방법으로서의강화학습을설명하시오. 강화학습의다양한전략들을기술하고서로간의차이를설명하시오. 모델기반 vs. 모델프리 RL의차이를설명하시오. 오프라인 vs. 온라인 RL의차이를설명하시오. On-policy vs. Off-policy RL의차이를설명하시오. MC학습 ( 몬테칼로기반동적프로그래밍방식 ) 방법을설명하시오. TD학습방법을기술하고 MC 방법과의차이를설명하시오. TD 학습, Sarsa, Q 학습알고리듬을설명하고차이점을기술하시오 알파고가사용한딥강화학습 DQN 의핵심아이디어들을설명하시오. 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 3

8.1 강화학습과 MDP 문제 (1/4) Introduction 감독학습 : y = f( x) 무감독학습 : x= f( x) or 강화학습 (RL): p(a s) x ~ p( x) 강화학습의특징 에이전트의상태 (s) 와행동 (a) 에대해보상 (r) 을최대화하는정책 p(a s) 를찾는문제 환경과상호작용하는에이전트 ( 로봇 ) 순차적의사결정문제, 행동제어문제 미래보상고려, 지연된보상 (delayed reward) 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 4

8.1 강화학습과 MDP 문제 (2/4) Introduction n RL의 활용: 로보틱스, 게임 등 2017, 장교수의 딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 5

8.1 강화학습과 MDP 문제 (3/4) Markov Decision Process (MDP) - Markov Decision Process = { S, A, P, R, γ} S : States of the agent A : Actions of the agent a P : State transition probability Pss' = P(S t+ 1 = s' S t = s,a t = a) a R : Reward Rs =Ε (R t+ 1 S t = s, A t = a) γ : Discount factor - Markov Property: P(S S ) = P(S S ) t+ 1 + 1 1,..., t 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 6

8.1 강화학습과 MDP 문제 (4/4) 반환 (return, G): Discounted accumulated mean reward G = R +γ R +... = γ R = R +γg + 1 t+ 2 k = 0 t+ k+ 1 t+ 1 t+ 1 k π π t π t+ k+ 1 k = 0 Q (, s a) = E [ G S = s, A = a] = E [ γ R S = s,a = a] 정책 π (policy of the agent): π ( a s) = P( A = a S = s) t t 가치함수 V (Value function = 장기적반환 ): k π π π t+ k+ 1 t k = 0 V () s = E [ G S = s] = E [ γ R S = s] 최적정책 : Value function 을최대화하는정책을찾음 * π = arg max π V ( s) 벨만최적식 (Bellman optimality equation) see text: page 175 π * π = arg max Q π π ( s, a) 동적프로그래밍 (dynamic programming, DP) 강화학습 RL = Approximate Solution to MDP 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 7

8.2 MC 학습과 TD 학습 (1/3) Policy Iteration 강화학습의학습패러다임 - Evaluation: Q (, s a) 를현재의정책 π() s 를통해학습 π - Improvement: π() s 를현재의가치함수 Q (, s a) 를통해학습 π - Improvement 의예 : Greedy improvement arg max π ( ) (, ) k + 1 s = Qk s a a 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 8

Monte-Carlo RL (MC 학습 ) 8.2 MC 학습과 TD 학습 (2/3) Methods for RL - DP 방법에서에피소드의 Return (G) 을 Value function 으로부터 Sampling 하여근사 (MC 근사 ) G = [ R +γ R +... S = s, A = a] + 1 t+ 2 q ( s, a) E[G ( s, a) G ( s, a)... S s, A a] π = 1 + 2 + t = t = - 에피소드가끝나야학습이가능 - 에피소드의길이가길거나무한한경우사용하기어려움 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 9

8.2 MC 학습과 TD 학습 (3/3) Methods for RL Temporal Difference RL (TD 학습 ) V () s = E[ R +γ V ( s ) S = s] π t+ 1 π t+ 1 t Q (, s a) = E[ R +γ Q ( s,a ) S = s,a = a] π t+ 1 π t+ 1 t+ 1 - Bootstrapping 을사용해에피소드가끝나지않아도학습가능 - MC 방법에비해효율적 모델기반 vs. 모델프리 RL MC: 모델기반 ( 전이확률필요 ) TD: 모델프리 ( 전이확률불필요 ) 오프라인 vs. 온라인학습 MC: 오프라인 ( 샘플모아서 update) TD: 온라인 ( 바로 update) 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 10

8.3 SARSA 와 Q 학습알고리듬 (1/3) Value Based RL Bootstrapping Value Based RL - Value function만을학습 - Action의선택은 greedy policy를사용 : - 대표적으로 SARSA 와 Q-learning 이있음 arg max π ( ) (, ) k + 1 s = Qk s a - Table 을사용하는방법과 Approximation 을사용하는방법이있음 a 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 11

8.3 SARSA 와 Q 학습알고리듬 (2/3) Value Based RL SARSA Qs (, a) Qs (, a) [ r Qs (, a ) Qs (, a)] = + α t + 1+γ t + 1 t + 1 알고리즘 1: Sarsa 학습알고리즘 Q(s,a) 를임의값으로초기화 For 에피소드 =1,, n do s 초기화 s에따르는 Q( 예, ε-greedy) 를통해유래된 a를선택 For 시퀀스 t =1,,T do a 선택, 보상 r과다음상태 s 관측 s =s t+1 에따르는 Q ( 예, ε-greedy) 를통해유래된 a =a t+1 을선택 Qs (, a) Qs (, a) [ r Qs (, a ) Qs (, a)] s s ;; a a ;; End For End For = + α t + 1+γ t + 1 t + 1 - On-policy 알고리듬 : 경험을모으는 policy 가현재 policy 임 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 12

8.3 SARSA 와 Q 학습알고리듬 (3/3) Value Based RL Q-learning Qs (, a) Qs (, a) [ r max Qs (, a) Qs (, a)] = + α t + 1+γ t + 1 a 알고리듬 2;; Q-Learning 알고리듬 Q(s,a) 를임의값으로초기화 For 에피소드 =1,, n do s 초기화 For 시퀀스 t =1,,T do s 에따르는 Q ( 예, ε-greedy) 를통해유래된 a 를선택 a 선택, 보상 r 과다음상태 s =s t+1 관측 s s ;; End For End For Qs (, a) Qs (, a) [ r max Qs (, a) Qs (, a)] = + α t + 1+γ t + 1 a - Off-policy 알고리듬 : 경험을모으는 policy 가현재 policy 와다름 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 13

8.4 딥큐넷 (DQN) (1/3) Q-learning 의업데이트식 Qs (, a) Qs (, a) [ r max Qs (, a) Qs (, a)] = + α t + 1+γ t + 1 a DQN 은 Q 학습의오류함수최소화에딥신경망과오류역전파알고리듬을사용 1 [ max ( ', ) (, )] 2 L= r+γ Q s a Q s a 2 a Q(State,Action=0) Q(State,Action=1) State... Q(State,Action=K) 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 14

8.4 딥큐넷 (DQN) (2/3) Target Network Trick 학습초기 Q(s,a ) 이부정확하고변화가심함 è 학습성능저하 DQN과동일한구조를가지고있으며학습도중 weight값이변하지않는별도의네트워크 (Target Network) 에서 Q(s,a ) 를계산 - Target Network의 weight값들은주기적으로 DQN의것을복사 Replay Memory Trick Changing Data Distribution: Agent의행동에따라들어오는데이터의분포가변화함 (e.g. 어떤 mini batch를학습한후무조건왼쪽으로가도록 policy가변화 è 이후왼쪽으로가지않는경우의데이터를얻을수없게되어학습이불가능 ) (State, Action, Reward, Next State) 데이터를 Buffer에저장해놓고그안에서 Random Sampling하여 mini batch를구성하는방법으로해결 Reward Clipping Trick 도메인에따라 Reward 의크기가다르기때문에 Q value 의크기도다름 Q value 의크기 variance 가매우큰경우신경망학습이어려움 Reward 의크기를 [-1, +1] 사이로제한하여안정적학습 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 15

8.4 딥큐넷 (DQN) (3/3) Atari 2600 비디오게임에서실험절반이상의게임에서사람보다우수기존방식 (linear) 에비해월등한향상일부게임은실패 (reward가 sparse, 복잡한단계를필요 ) Paper Mnih, Volodymyr, et al. "Human-level control through deep reinforcement learning." Nature 518.7540 (2015): 529-533. Video https://www.youtube.com/watch?v=tmpftpjtdgg Open source https://github.com/gliese581gg/dqn_tensorflow 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 16

8.5 딥강화학습의활용 : AlphaGo (1/2) AlphaGo A3C와 Monte-Carlo Tree Search 알고리즘을조합탐색공간이매우큰바둑에서학습을통해서인간을뛰어넘는성능데모정책망 (policy network, actor) 과가치망 (value network, critic) 을따로학습정책망은프로기사들의기보를사용해지도학습후강화학습적용 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 17

8.5 딥강화학습의활용 : AlphaGo (2/2) Monte-Carlo Tree Search - Selection: a = arg max( Q( s, a) + u( s, a)), t a Ps ( t, a) us ( t, a) 1 + Ns (, a ) - Expansion: 잎노드에도착하면정책망을통해새로운잎노드생성 - Evaluation: V( sl) = (1 λ) vθ ( sl) + λzl - Backup: 1 i Nsa (, ) = 1(, sai,) Qsa (, ) = 1(, saiv,) ( sl) Nsa (, ) i i t Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G.,... & Dieleman, S. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484-489. 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 18

요약 강화학습과 MDP 문제 MDP: State, Action, Reward, Transition, Discount 로구성. 순차적의사결정 강화학습은 MDP 문제를근사적으로해결하는머신러닝방법 Reward 기대치를최대화하는방향으로 Agent 의행동을선택하도록학습 Sarsa 와 Q-Learning Value Function 을 Approximation 하고이를최대화하는 Action 선택 Sarsa, Q-Learning DQN: Deep Neural Network 로 Q 값을근사 딥강화학습의활용 AlphaGo 바둑 AI RL 과 Monte Carlo Tree Search 정책망, 가치망에딥러닝을활용 2017, 장교수의딥러닝, SNU CSE Biointelligence Lab., http://bi.snu.ac.kr 19