조지아텍 온라인 석사과정 CS7647 ‘딥 러닝’ Lesson 17 필기 내용
- 워낙 방대한 내용을 빠르게 다루고 있다 보니, 강의만으로는 이해가 어려운 부분이 많았다. 이에 David Silver의 구글 딥마인드 강의 시리즈를 참고했다.
Lesson 17. 강화학습 (Reinforcement Learning)
1. 강화학습 소개
1) 강화학습 소개
- 과업 : 연속적 의사결정
- ‘보상(Reward)’ 형식으로 평가 피드백 수령
2) 강화학습의 개념들
- Agent : 의사결정의 주체
- Environment
- State : Agent에게 주어지는 Stimulus, Situation. 예: 로봇의 시각적 인풋.
- Action : Agent가 Environment에 대해 취하는 행동.
- Reward : Environment로부터 Agent에게 주어지는 보상. Gain, Payoff, Cost로 나뉨. (즉 비용도 Reward에 포함됨)
- Evaluative Feedback (평가 피드백) :
- action을 취하고 보상을 받음 (negative 즉 음의 보상도 있음)
- 지도학습에서와 달리, “올바른”행동에 대한 지도가 없음
- Sequential Decisions (연속적 의사결정) :
- 연속된 state에 대해 action을 계획하고 취함
- 보상이 지연될 수도 있음. 그러므로 장기적인 누적 보상을 고려한 최적화, 즉 장기 계획이 필요함.
3) 강화학습의 도전과제
- 평가 피드백 : 올바른 action을 찾을 때 까지 trial-and-error 방식으로 가능한 모든 action을 검토해야 함.
- 피드백 지연 : action이 즉각적인 보상으로 이어지지 않을 수 있음.
- 유동성 (Non-stationarity) : Policy가 변경되면 이미 방문한 state에 대한 데이터 분포 또한 변경됨
- 온라인 데이터는 모두 흘러가는 데이터임. 시간도 마찬가지임. Agent는 해당 state를 단 한번만 보게 될 수 있음. 과거의 실수에서 학습하기가 어려움.
4) 강화학습 API
- Agent는 각 시간 스텝 t마다 :
- 관찰내역 o_t를 수령함
- 액션 a_t를 실행함
- Environment는 각 시간 스텝 t마다:
- 액션 a_t를 수령함
- 관찰내역 o_t+1 을 발산함
- 보상 r_t+1을 발산함. (스칼라값)
5) 예시 : 아타리 게임 플레이하는 AI
- 목표 : 가장 높은 점수로 게임을 끝내라
- State : 게임 상태에 대한 raw pixel input
- Action : 게임 조작 (예: 위아래 왼오른)
- Reward : 각 시간 스텝 별 점수
2.마르코프 결정 과정 (Markov Decision Process)
1) MDP 소개
- MDP는 강화학습 기저에 깔린 이론적 프레임워크이다.
- 정의 : 튜플 (S, A, R, T, γ)
- S: 가능한 State의 집합
- A: 가능한 Action의 집합
- R(s,a,s’): Reward의 분포
- T(s,a,s’): Transition 확률분포. p(s’ | s,a)라고도 씀
- γ: 할인 계수 (Discount Factor)
- 순서 : … s_t, a_t, r_t+1, s_t+1, a_t+1, r_t+2, s_t+2 …
- 마르코프 속성: 현 state가 Environment의 state를 온전히 규정한다
- 전제 : 가장 최근의 관측내용이 기존의 역사를 모두 함축하고 있다
2) 강화학습에서의 MDP
강화학습에서 우리는 기저에 MDP가 깔려있다고 가정한다.
이 MDP에서 R과 T는 미지의 속성이다.
그래서 피드백이 주어지며, trial-and-error 가 필수적이다.
다만, 이 강의에서는 우리가 R과 T를 안다고 가정하고 MDP를 푸는 알고리즘, 즉 최적의 Policy를 찾는 방법을 알아본다. 아래 항목들이 전제된다.
- Rewards : 모든 상태에서의 보상 알고있음. 평가핏백 없음
- Transition : Environment가 어떻게 작동하는지, 즉 모든 transition을 완전히 알고 있음
3) 예시 : 그리드에서의 MDP
- Environment : 2d 그리드
- State : Agent(세모)의 2d 좌표
- Action : 동서남북
- Reward : 우측상단에 기재된 +1, -1
- 복잡요소 : Agent가 동작의 왼쪽/오른쪽으로 drift할 확률 20% 존재
Policy를 어떻게 짤 수 있을까?
한 가지 방법은 맵과 동일한 2d행렬을 구현하는 것이다.
4) 최적의 Policy 찾기
- Policy : State -> Action 매핑.
- Deterministic : π(s) = a
- Stochastic : π(a|s) = P(A_t = a | S_t = s)
어떤 Policy가 좋은 Policy인가? 가까운 reward를 최대화하는것? 모든 미래의 reward를 동일하게 합하는 것?
답은 ‘할인된 미래 보상의 총합’이다.
policy에 대한 할인계수 * 보상의 총합의 기대값이 최대인 policy.
5) 최적 Policy 예시
그리드 맵을 다시 살펴보자. 모든 non-absorbing state에 대해 reward 값을 설정해 주자.
6) 가치 함수 (Value Function)
- 가치 함수 : 미래 보상의 합에 대한 예측
- State 가치함수 : V-함수. V : S -> R
- 이 State의 가치는?
- 이 State에서 내가 이길/질 가능성은?
- State-Action 가치함수 : Q-함수. Q : S*A -> R
- 이 State-Action 쌍의 가치는?
- 이 State에서 이 Action이 내 미래에 미치는 영향은?
3. MDP 해결 알고리즘
1) Recursive Bellman Expansion
- Q의 정의에 Recursive Bellman expansion을 적용하면 Q와 V를 아래와 같이 바꿀 수 있다.
- 이는 Value Iteration이라는 dynamic programming algorithm의 근원이 된다.
2) Value Iteration
- 알고리즘 단계:
- 모든 State의 값을 초기화한다
- Converge되지 않은 동안 모든 State에 대해 :
- Convergence까지 반복한다. (Convergence = 값 변화 없음)
- Time complexity : O( |S|^2 |A| )
3) Q-Iteration
Value iteration과 거의 같지만 state뿐만 아니라 action에 대해서도 반복된다.
4) Policy Iteration
- 랜덤한 policy π_0에서 시작하여 점차 개선해나간다.
- 2개 단계를 반복한다.
- Policy Evaluation : V^π 계산 (Value Iteration과 유사)
- Policy Refinement : 그리디 방식으로, V^π에 따라 다음 state에서의 action을 변경함
- V^π_i 보다 π_i의 converge속도가 더 빠를 때가 많다. 그래서 policy iteration을 하는 것이다.
5) Space/Time complexity
- 앞서 봤듯 Value iteration의 time complexity가 매우 크다. 그래서 복잡한 상황이 될 수록 알고리즘을 조정할 필요가 있다.
4. Deep Q-Learning
매우 흔히 사용되는 Value 기반의 강화학습 방식이다.
1) 예시: 아타리 게임
- 알고리즘은 2개의 작업을 하는 중이다.
- Policy Refinement
- 수집한 데이터를 통해 Deep-Q Network를 업데이트, 보다 나은 전략을 알아냄. (예: 칼럼별로 적을 없애기)
2) Deep Q-Learning
- 요약 : 데이터로부터, 파라미터를 받는 Q-함수를 학습한다.
- 가장 간단한 선형함수 형태:
-
- 혹은 Deep 한 신경망 (Deep Q-Network : Q(s,a; θ))도 있다
- 실제로 잘 작동한다
- RGB 이미지를 인풋으로 받을 수 있다 (합성곱 신경망)
- 손실함수는 아래와 같다. 다만, 실 적용시에는 안정성을 위해 두 단계로 나눈다.
- Q_old를 그대로 두고 Q_new 의 파라미터들을 갱신한다
- 정기적으로 Q_old를 Q_new 값으로 세팅한다.
- 실제 적용시 미니배치를 사용한다.
- Forward Pass :
- 손실함수 : 배치 평균 사용
- Backward Pass : Q_new parameters 에 대한 Loss의 derivative
- 고정 데이터셋에 대해 MSE 손실은 최적화될 수 있다. (Fitted Q-Iteration 알고리즘)
- 하지만 ‘어떻게 경험/데이터를 축적할 것인가?’의 문제는 아직 해결되지 않았다. 이게 강화학습의 가장 어려운 부분이다!
3) 어떻게 경험을 쌓을 것인가?
- 예시: 데이터 수집 정책 “π_수집” -> Environment -> Data -> 훈련 -> “π_훈련” -> “π_수집” 갱신
- 문제점 1. Exploration vs Exploitation : Exploration 부분이 없음
- 문제점 2. 보상을 받을법한 방향으로만 움직인 데이터이므로 독립적이지 않고 correlation 이 높은 데이터임
4) Exploration 문제
- 단순 그리디 알고리즘을 구현할 시 Exploration 측면이 없음
- 대안 : ε-그리디 알고리즘
5) Correlation 문제
- Correlation이 높은 데이터들만 축적되어 학습이 비효율적임.
- 현재 Q-network의 파라미터가 다음 훈련 샘플을 결정지으므로 feedback loop에 빠질 수 있음.
- 예: 아래 예시에서 모든 훈련 샘플이 일단 우측으로 향하게 되어 local minima에 빠질 수 있음.
6) 해결책 : Experience Replay
- Replay buffer에 transition을 저장
- 경험이 쌓일때마다 replay buffer를 업데이트
- Q-network는 리플레이 메모리에서 추출한 랜덤한 transition 미니배치로 훈련시킴. (비연속적인 샘플)
- 버퍼가 클수록 correlation이 낮아짐.
지금까지 배운 내용을 종합하면 아타리 미니게임 논문에 사용된 알고리즘을 이해할 수 있다!
5. Policy Gradients, Actor-Critic
1) 파라미터를 받는 Policy
- 파라미터 목록 θ로 정의되는 Policy들 :
θ는 예를 들어 선형변환이나 딥 네트워크 등의 파라미터들일 수 있다
- 우리는 J(π)를 최대화하고자 한다.
* 여기서 감마는 1인것으로 처리한다.
- 이제 최적의 Policy에 대한 공식을 아래와 같이 바꿔쓸 수 있다.
2) Policy Gradient : 손실 함수
지도학습과 비교하면 아래와 같다.
3) REINFORCE 알고리즘
- 3단계로 진행된다
- Policy 실행 및 데이터 수집
- Policy gradient 계산
- Policy 갱신
- 그럼 Policy gradient는 어떻게 계산하는가?
4) Policy gradient 계산
5) Policy Gradient의 단점
- High Variance : 어떤 행동이 보상 증진으로 이어졌는지 정확한 파악이 어려워 high variance 나타남. 훈련 불안정.
- Variance 낮추기 : 보상으로부터, action과 무관한 baseline을 뺌.
- 이 Baseline을 무엇으로 하는지에 따라 알고리즘이 여러가지로 나뉨.
