11강. 강화학습(reinforcement learning; RL)
추천글 : 【알고리즘】 알고리즘 목차
1. 개요 [본문]
2. Markov decision process [본문]
1. 개요 [목차]
⑴ 정의
① (참고) supervised learning
○ 데이터 : (x, y) (단, x는 feature, y는 label)
○ 목표 : 맵핑 함수 x → y의 계산
② (참고) unsupervised learning
○ 데이터 : x (단, x는 feature이고 label은 없음)
○ 목표 : x의 underlying structure에 대한 학습
③ reinforcement learning
○ 데이터 : (s, a, r, s') (단, s는 state, a는 action, r은 reward, s'은 다음 상태)
○ 목표 : 여러 시간에 걸친 reward의 총합을 최대화
⑵ 특징 : supervised learning, unsupervised learning과는 차별성이 있음
① 정답을 묵시적으로 제공받음 : reward의 형태로 제공받음
② 환경과의 상호작용을 고려해야 함 : delayed feedback 등이 문제가 됨
③ 이전의 결정이 미래의 상호작용에 영향을 줌
④ 적극적으로 정보를 얻는 알고리즘 : 강화학습은 데이터를 얻는 과정까지를 포함함
⑶ 요소 1. reward
⑷ 요소 2. policy
① 정의 : agent의 행동. 즉, state를 입력으로 action을 출력으로 하는 맵핑
② 종류 1. deterministic policy
③ 종류 2. stochastic policy
○ 이유 1. learning에서 최적의 행위를 모르므로 exploration을 하기 위함
○ 이유 2. 최적의 상황이 stochastic한 걸 수도 있음 (예 : 가위바위보, 상대방이 역이용하는 경우)
⑸ 요소 3. value function
① 정의 : 미래의 reward에 대한 기댓값
② 수식화 : state s, policy π, 미래가치를 현재가치로 보정하기 위한 계수 γ에 대하여,
③ state가 좋은지 나쁜지를 평가하여 action을 선택하는 근거를 제공
⑹ 요소 4. model
① 정의 : 환경(environment)의 행동
② 주어진 state와 action에 대하여 model은 다음 state와 reward를 결정함
③ model-free method와 model-based method가 있음을 유의
2. Markov decision process [목차]
⑴ 정의 : transition과 관련하여, t+1에서의 상태가 오직 t에서의 상태의 함수로 결정되는 것
① state : st ∈ S
② action : at ∈ A
③ reward : rt ∈ R(st, at)
④ policy : at ~ π(· | st)
⑤ transition : st+1 ~ P(· | st, at)
⑥ 사실상 거의 대부분의 문제 상황이 Markov decision process에 해당함
⑵ 종류 1. Q-learning
① 정의 : 모든 state에 대하여 value function Vπ(s)를 학습하는 것
○ transition probability P(s' | s, a)는 알려져 있지 않음
○ reward function R(s, a)는 알려져 있지 않음
② 방법 1.
○ 모든 state / action pair의 추정량을 초기화 : Q̂(s, a) = 0
○ 초기 반복 scheme
○ 랜덤한 action a를 취함
○ 다음 상태 s'를 관찰하고 환경으로부터 R(s, a)를 받음
○ Q̂(s, a)를 업데이트
○ 후기 반복 scheme
○ a = arg maxa Q̂(s, a)를 취함
○ 다음 상태 s'를 관찰하고 환경으로부터 R(s, a)를 받음
○ Q̂(s, a)를 업데이트
○ random restart
③ 방법 2. ε-greedy (epsilon greedy)
○ 모든 state / action pair의 추정량을 초기화 : Q̂(s, a) = 0
○ 반복 scheme
○ 1 - ε의 확률로 a = arg maxa Q̂(s, a)를 취하고, ε의 확률로 random action을 취함
○ 다음 상태 s'를 관찰하고 환경으로부터 R(s, a)를 받음
○ Q̂(s, a)를 업데이트
○ 후기 반복일 경우 random restart
④ DQN(deep Q-network)
○ 정의 : Q learning을 deep learning으로 구현한 것
○ 수많은 게임에 적용됨 : DQN on Atari 2600 (2013), AlphaGo (2016) 등
⑶ 종류 2. policy gradient
① 정의 : policy π(s)를 직접 학습하는 것
② 특징
○ Q-learning은 state가 continuous해도 되는 반면 action은 discrete해야 함
○ policy gradient는 action 및 state가 continuous해도 됨
③ 알고리즘
○ step 1. frame을 받음
○ step 2. P(action)을 얻기 위해 forward를 propagate함
○ step 3. P(action)으로부터 a를 샘플링
○ step 4. 게임의 나머지를 진행
○ step 5. 만약 게임에서 이기면 ∇θ 방향으로 진행
○ step 6. 만약 게임에서 지면 -∇θ 방향으로 진행
⑷ 기타 종류
① deep O-network (DON)
② A3C
③ genetic algorithm
④ SARSA
입력: 2021.12.13 15:20
'▶ 자연과학 > ▷ 알고리즘·머신러닝' 카테고리의 다른 글
【알고리즘】 27강. 기타 알고리즘 (0) | 2022.01.11 |
---|---|
【알고리즘】 12-1강. DIP(Deep Image Prior) (0) | 2021.12.31 |
【알고리즘】 6강. 분류 알고리즘 (0) | 2021.12.11 |
【알고리즘】 23강. MAB(multi-armed bandits) (0) | 2021.12.10 |
【알고리즘】 7강. 차원 축소 알고리즘 (0) | 2021.12.03 |
최근댓글