SARSA와 Q러닝 차이 정리: 온폴리시와 오프폴리시, 함수 근사부터 DQN까지 스탠퍼드 강의 해설

핵심 메시지

• 동역학 모델을 모르는 상황에서 상호작용만으로 배우는 것이 강화학습이고, 몬테카를로와 시간차 학습이 그 두 축이다.
• 몬테카를로 제어의 가치 추정을 시간차 갱신으로 바꾸면 곧바로 SARSA가 되며, 이름은 갱신에 필요한 다섯 요소에서 나왔다.
• SARSA는 실제로 쓰는 정책을 개선하는 온폴리시, Q러닝은 행동 정책과 목표 정책을 분리한 오프폴리시 알고리즘이다.
• 상태 공간이 커지면 표 형태의 가치 함수는 메모리와 차원의 저주에 막히고, 매개변수를 가진 근사 함수가 대안이 된다.
• DQN을 실제로 작동하게 만든 것은 경험 재생과 고정된 목표 신경망이라는 두 가지 안정화 장치였다.

쉽게 이해하기

강의는 이전까지의 흐름을 정리하며 시작한다. 정책이 주어졌을 때 가치를 추정하는 예측 문제와 최적 정책 자체를 찾는 제어 문제를 구분했고, 동적 계획법에 기반한 정책 반복과 가치 반복을 정확해법으로 다뤘다. 다만 이 방법들은 상태 전이 확률을 완전히 안다는 전제가 필요하고, 그 전제를 버리고 환경과의 상호작용만으로 배우는 길이 몬테카를로 학습과 시간차 학습이다. 둘의 차이는 표본을 어디까지 쓰느냐에 있다. 몬테카를로는 종료 상태에 도달할 때까지 궤적을 끝까지 굴린 뒤 관측된 보상의 합을 목표로 삼고, 시간차 학습은 한 걸음만 나아간 보상에 다음 상태의 추정 가치를 더해 목표를 만든다. 추정치를 다른 추정치로 갱신하는 부트스트래핑 덕분에 시간차 학습은 분산이 낮고, 에피소드가 끝나기를 기다리지 않고 온라인으로 갱신할 수 있으며, 완결되지 않은 시퀀스도 쓸 수 있다.

그렇다면 몬테카를로 제어에서 가치 추정 부분만 시간차 갱신으로 바꾸면 어떻게 될까. 그것이 SARSA다. 행동 가치 함수를 갱신하려면 현재 상태와 행동, 그로부터 받은 보상, 다음 상태와 그 상태에서 고를 다음 행동이 필요한데, 이 다섯 요소의 머리글자가 그대로 이름이 됐다. 강의는 바람이 부는 격자 세계 예제로 이를 확인한다. 아래에서 위로 부는 바람이 있는 칸에서는 대각선으로 질러가는 직관이 틀리고, 오히려 천장까지 밀려 올라간 뒤 되돌아오는 경로가 최적이 된다.

같은 예제는 몬테카를로의 한계도 드러낸다. 몬테카를로는 에피소드가 끝나야 갱신할 수 있는데, 목표에 도달해야만 끝나는 환경에서 정책이 순환 고리에 빠지면 영원히 갱신되지 않는다. 시간차 학습은 매 걸음 갱신하므로, 같은 고리에 빠져도 음의 보상이 계속 쌓이면서 그 행동이 다른 선택보다 나쁘다는 것을 스스로 알게 된다. 여기서 온폴리시와 오프폴리시의 구분이 등장한다. SARSA는 입실론 그리디 정책으로 행동하면서 바로 그 정책을 개선하므로 온폴리시다. 반면 오프폴리시는 데이터를 만들어내는 행동 정책과 배우고 싶은 목표 정책을 분리한다. 로봇처럼 환경과 무한히 상호작용할 수 없는 경우, 과거 버전의 정책이 남긴 데이터를 버리지 않고 재활용하려는 경우, 그리고 탐험적인 행동 정책과 결정적인 최적 정책을 떼어놓고 싶은 경우가 모두 그 동기다. Q러닝은 목표 정책을 Q에 대한 그리디 정책으로, 행동 정책을 입실론 그리디로 두어 이를 구현한다.

차이는 절벽이 있는 격자 세계에서 극적으로 드러난다. 매 걸음 마이너스 1, 절벽에 빠지면 마이너스 100인 환경에서 Q러닝은 절벽에 바짝 붙은 최단 경로로, SARSA는 천장 쪽으로 도는 안전한 경로로 수렴한다. 그런데 학습 중 누적 보상 그래프에서는 SARSA가 더 좋아 보인다. 학습 중에는 둘 다 입실론 확률로 무작위 행동을 하므로, 절벽에 붙어 있는 Q러닝은 가끔 떨어지기 때문이다. SARSA는 자신의 탐험성까지 감안한 최적의 입실론 그리디 정책으로 수렴한 셈이다.

마지막은 규모의 문제다. 바둑의 반상 배치가 10의 170제곱 가지에 이르는 것처럼 실제 문제의 상태 공간에서는 표를 저장하는 것도, 모든 칸을 방문해 갱신하는 것도 불가능하다. 그래서 매개변수 세타를 가진 근사 함수로 가치를 표현하고, 몬테카를로 목표나 시간차 목표를 회귀 문제의 정답으로 삼아 학습한다. 2014년 무렵의 DQN은 여기에 합성곱 신경망을 붙여 아타리 게임을 화면 이미지만 보고 학습했고, 상태를 입력받아 가능한 모든 행동의 Q값을 한 번에 내놓는 형태를 택했다. 다만 그대로는 학습이 흔들린다. 에이전트가 스스로 데이터를 만들기 때문에 연속된 표본이 서로 강하게 상관되어 있어 지도학습의 전제가 깨지고, 매개변수를 갱신할 때마다 회귀의 목표값도 함께 움직이기 때문이다. DQN은 전이를 버퍼에 쌓아 두고 무작위로 뽑아 쓰는 경험 재생으로 첫 문제를, 목표 계산용 신경망을 따로 두고 늦게 갱신하는 방식으로 두 번째 문제를 풀었다. 강의는 요즘은 목표망을 통째로 교체하기보다 폴리악 평균처럼 이동 평균으로 서서히 옮기는 쪽이 더 널리 쓰인다고 덧붙인다.

주요 인사이트

• SARSA와 Q러닝의 차이는 수식 한 줄, 즉 다음 행동을 실제 정책에서 뽑느냐 최댓값으로 대체하느냐에서 갈린다.
• 학습 중 점수가 낮다고 나쁜 알고리즘인 것은 아니다. 무엇을 향해 수렴하는지와 수렴 과정에서 무엇을 감수하는지는 다른 문제다.
• 온폴리시는 자신의 탐험 습관까지 포함한 최적을 찾고, 오프폴리시는 탐험을 걷어낸 순수한 최적을 찾는다.
• 함수 근사가 해결하는 것은 저장 공간만이 아니다. 비슷한 상태끼리 학습이 전이되어 방문하지 않은 상태의 가치도 짐작할 수 있게 된다.
• 강화학습 알고리즘들은 표본을 만들고, 목표를 추정하고, 정책을 개선하는 같은 골격 위에서 부품만 바꿔 끼운 변형으로 볼 수 있다.

자주 묻는 질문

관련 AI 소식