본 포스팅은 “Do it! 강화 학습 입문” - (이지스퍼블리싱, 조규남, 맹윤호, 임지순 지음)을 바탕으로 공부한 내용을 정리한 것입니다.
- 모델 기반 vs 모델 프리
- 몬테카를로 학습 (MC, Monte Carlo Learning)
- 몬테카를로 학습의 개념
- 몬테카를로 학습의 특징
- 시간차 학습 (TD, Temporal Difference Learning)
- Q 학습 (Q-Learning)
1. 모델 기반 vs 모델 프리
모델 기반 (Model-Based) 강화 학습은 에이전트가 환경 안에서 가질 수 있는
모든 상태와 각 상태 간의 전이 확률을 미리 안다는 전제가 깔려 있다.
MDP를 이루는 구성 요소 중 모델에 대한 모든 지식을 미리 알고 있다는 것이다.
종단 상태로부터 역추적해 모든 상태와 행동의 가치를 계산하는 완전 탐색이라는 특징까지도,
가치 반복법과 정책 반복법은 현실 세계에 적용하기 어렵다.
그렇다면
종단 상태로부터 역추적이 아닌, 초기 상태로부터 탐색을 진행하며 경험을 누적하는 정책은?
완전 탐색이 필요하지 않으므로 계산양을 크게 줄일 수 있다.
이렇게 모델에 대한 완전한 지식이 필요치 않은 모델 프리 (Model-Free) 강화 학습에는
대표적으로 몬테카를로 (MC, Monte Carlo) 학습과 시간차 (Temporal Difference) 학습이 있다.
2. 몬테카를로 학습 (MC, Monte Carlo Learning)
몬테카를로 학습의 개념
완전한 가치 함수를 구할 수 없으므로, 가치 함수의 추정치를 구하는 방식으로 문제 해결에 접근한다.
정책을 초기에 무작위로 설정하고, 이를 이용해 가치 함수를 추정하고, 이로 정책을 개선한다.
개선한 정책으로 가치 함수를 추정하고, 추정한 가치 함수로 다시 정책을 개선한다.
가치 함수와 정책이 모두 수렴할 때까지 반복하는데 정책 반복법과는 큰 차이점이 있다.
- MC는 완전한 가치 함수가 아닌 가치 함수의 추정치만 얻을 수 있다.
- MC는 환경내 모든 상태의 가치 추정이 아닌, 에이전트가 거쳐간 상태의 가치 함수만 추정한다.
이렇게 에이전트가 직접 에피소드를 겪어 나가며 모델을 추정하기 때문에,
환경의 모든 상태를 거친다고 보장하지 못한다.
몬테카를로 학습의 특징
- 알려진 모델이 없다고 가정. 즉, 에이전트는 주어진 상태에서 행동을 취했을 때, 어떤 상태로 전이할지, 보상이 주어질지 모른다.
- 에이전트는 경험의 표본으로부터 학습.
- 현재까지 겪은 모든 에피소드에 대해 상태의 이익 \(G\)를 평균하여 상태의 가치 함수를 구함. (경험적 평균)
- 에피소드 하나를 완전히 끝낸 다음 업데이트.
- 에피소드 단위 문제에 한하여 적용 가능.
이렇듯 MC의 핵심은 에피소드이고, 기본 학습 단위가 에피소드 완주이므로 무한한 환경에서는 적용이 불가하다.
또한, 모델을 모르기 때문에, 전이 확률을 모르고, 따라서 가치 함수의 의미가 없다.
즉, 특정한 행동이 그 상태의 최선 행동이라 말할 수 없다. 그래서 나온 것이,
상태 \(s\)에서 행동 \(a\)를 취했을 때의 장기적 보상에 대한 평균, 행동-가치 함수, Q 함수 \(Q(s,a)\)다.
상태 \(s\)만을 입력으로 하는 가치 함수 \(V(s)\)에 행동 \(a\)를 추가했다고 생각하자.
3. 시간차 학습 (TD, Temporal Difference Learning)
에피소드가 무한히 지속되거나 하나의 에피소드가 종료되기까지 시간이 오래 걸릴때,
에피소드 자체가 길다면 시간차 (TD) 학습을 사용하자.
MC는 하나의 에피소드가 끝날 때 마다 Q 함수를 업데이트 한다면,
TD는 상태 변화가 있을 때마다 업데이트한다.
하나의 에피소드가 끝나지 않아도, 단계마다 학습이 가능하다는 뜻이다.
MC, TD와 분산, 편향
분산 (Variance)은 학습 데이터가 얼마나 넓게 퍼져있는지를 나타내고,
분산이 크면 잡음이나 오류가 많이 포함되고 과대 적합 (overfitting)이 발생한다.
편향 (Bias)은 데이터의 일부만을 학습해 잘못된 가정이 만들어지는 것이고,
과소 적합 (underfitting) 문제가 발생할 수 있다.
MC는 에피소드가 끝나야만 Q 함수를 업데이트 가능하고,
에피소드마다 서로 다른 상태를 갈 수 있으므로 분산이 크고 편향이 작다.
TD는 다음 단계의 영향만 받아 가치 함수를 업데이트 하므로, 분산이 작고 편향이 크다.
이러한 문제를 인지하고 넘어가자.
수식
MC에서 \(N\)회의 에피소드에 대한 \(G_{t+1}\)값에 할인율 \(\gamma\)를 곱한 다음 평균하여 \(Q(S,A)\)를 구했다.
\[Q(S,A)=(1-1/N)Q(S,A)+\gamma G_{t+1}/N\]여기서 \(1-1/N\)을 \(\alpha\)로 치환하면 다음과 같다.
\[Q(S,A)=Q(S,A)+\alpha (\gamma G_{t+1}-Q(S,A))\]TD의 Q 함수 업데이트 공식도 이와 유사하다.
TD는 에피소드 종료 이전에 업데이트가 가능하므로 \(G_{t+1}\)을 구할 수 없고, \(\alpha\)도 \(1-1/N\)일 필요가 없다.
다음 단계 보상 \(R_{t+1}\)과 \(Q(S_{t+1},A_{t+1})\)가 반환하는 값으로 현재의 \(Q(S_{t},A_{t})\)를 업데이트 한다.
\[Q(S_{t},A_{t})=Q(S_{t},A_{t})+\alpha (R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S,A))\]엡실론-탐욕 (Epsilon-Greedy) 알고리즘
모델 프리 학습들은 에이전트가 거치는 상태와 행동에만 Q 함수를 갱신하므로, 샘플링으로 볼 수 있다.
\(A_{t+1}\)을 선택하는 기준은 무엇이 있을까? 그냥 Q를 최대로 할까?
가치 반복법과 같이 더 큰 Q 함수, 가치 함수를 얻기 위한 행동을 선택하는 것을
탐욕 알고리즘 (Greedy Algorithm)이라 한다.
상태, 행동 공간이 넓은 환경에서는 탐욕 알고리즘이 좋을 수 있다.
하지만 MC, TD 모두 자신의 상태, 행동을 샘플링하여 학습에 반영하기 때문에
샘플링 범위를 줄이는 탐욕 알고리즘이 최적의 정책을 찾을 가능성을 낮춘다.
이 때, 에이전트가 가치 함수를 이용하며, 새로운 영역을 탐험할 수 있도록 여지를 주면
최적의 행동과 정책을 찾아낼 가능성이 높아질 것으로 볼 수 있다.
이를 엡실론-탐욕 (Epsilon-Greedy) 알고리즘이라 한다.
| 탐욕 알고리즘 | 가장 높은 가치 함수 또는 Q 함수를 추구하는 방향으로 행동을 결정. 탐험을 배제한 이용. |
| 랜덤 노이즈 알고리즘 | 에이전트가 지나는 각 단계마다 가치 함수의 추정치에 무작위 값을 더함. 더한 노이즈로 탐험을 진행 |
| 엡실론-탐욕 알고리즘 | 엡실론 확률을 통해 가장 높은 가치 함수를 추구하지 않는 행동중에 하나를 무작위로 선택. |
TD에서는 엡실론-탐욕 알고리즘을 통해 탐색이 덜 진행된 상태에서 학습 결과가 수렴하는 것을 막을 수 있다.
4. Q 학습 (Q-Learning)
행동 정책과 학습 정책
TD에서 임의의 정책인 \(\pi (s)\)를 사용해서 행동 \(A_{t}\)를 취하고,
다음 단계에서 \(Q\)를 추정할 때 같은 \(\pi (s)\)를 사용하여 행동 \(A_{t+1}\)을 선택한다.
움직이기 위한 정책 (행동정책)과 학습하기 위한 정책 (학습 정책)이 같다는 뜻이다.
행동 정책에 탐험 요소를 어느 정도 넣는 것은 바람직하지만,
학습 수렴 속도가 느려지기때문에 학습 정책에는 탐험 요소가 필요치 않다.
둘 모두를 탐욕 알고리즘을 사용하면 학습은 빠르게 수렴하지만,
탐험 요소가 없으므로 최적 정책 수렴은 힘들다. Q 학습은 여기서 고안 되었다.
Q 학습은
행동 정책과 학습 정책을 서로 다르게 하는 Q 학습의 Q 함수 업데이트 공식은
앞선 TD 학습의 Q 함수 업데이트 수식과 거의 비슷하다.
\[Q(S_{t},A_{t})=(1-1/N)Q(S_{t},A_{t})+(R_{t+1}+\gamma max_{a}Q(S_{t+1},a))/N\]수식에서 우리는 행동 정책 (행동 \(A_{t}\)를 선택)과 학습 정책(\(a\)를 선택)이 다름을 볼 수 있다.
행동 정책은 엡실론-탐욕, 학습 정책은 탐욕 알고리즘을 따른다.
DQN (Deep Q-Networks)가 바로 이 Q 학습에 딥러닝을 접목한 것이다.
참고
“Do it! 강화 학습 입문” - (이지스퍼블리싱, 조규남, 맹윤호, 임지순 지음)