News & Events
다양한 강화 학습 알고리즘 (Q-Learning, SARSA, DQN)
강화학습(RL)은 다음 단계에서 에이전트가 지연된 보상을 받아 이전 행동을 평가하는 일종의 머신러닝 방식을 말한다. 게임(예: 아타리, 마리오)에서 주로 사용되었으며 인간과 동등하거나 그 이상의 성능을 보였다. 최근에는 알고리즘이 신경망의 조합과 함께 발전함에 따라 진자 문제와 같은 보다 복잡한 작업을 해결할 수 있게 되었다.
수많은 RL 알고리즘이 있지만, 각각의 알고리즘 사이에는 포괄적인 비교가 없는 것 같다. 특정 작업에 어떤 알고리즘을 적용할 지 불분명했다. 이 포스팅은 RL 셋업에 대해 간략히 논의하고 잘 알려진 알고리즘 중 일부를 소개하여 이 문제를 해결하는 것을 목표로 한다.
1. 강화 학습 101
일반적으로 RL 셋업은 에이전트와 환경의 두 가지 구성 요소로 이루어진다.
환경(environment)은 에이전트(agent)가 동작하는 객체(예: 아타리 게임 자체)를 참조하는 반면, 에이전트는 RL 알고리즘을 나타낸다. 환경은 상태를 에이전트로 보내는 것으로 시작하여 해당 상태(state)에 대응하여 작업을 수행하는 데 필요한 지식을 기반으로 한다. 그 후 환경은 한 쌍의 다음 상태를 보내고 에이전트에게 보상을 준다. 에이전트는 환경에서 반환된 보상으로 지식을 업데이트하여 마지막 작업을 평가한다. 이 루프는 환경이 종료 상태를 보낼 때까지 계속 진행되며 에피소드로 끝난다.
대부분의 RL 알고리즘은 이 패턴을 따른다. 다음 단락에서는 RL에 사용된 몇 가지 용어에 대해 간략히 설명할 것이다.
정의
- 행동(A): 에이전트가 수행할 수 있는 모든 이동
- 상태(S): 현재 환경에서 반환된 상황
- 보상(R): 마지막 작업을 평가하기 위해 환경에서 즉시 반환하는 것
- 정책(π): 에이전트가 현재 상태에 따라 다음 작업을 결정하기 위해 사용하는 전략
- 값(V): 단기 보상 R과 반대로 할인된 장기 수익 기댓값
- Q-값 또는 작업-값(Q): Q-값은 현재 행동 a인 추가 모수를 사용한다는 점을 제외하고는 V와 유사하다. Qπ(s, a)는 정책 π에 따라 행동 a를 취하면서 현 상태 s의 장기적인 반환을 의미한다.
모델 프리 v.s. 모델 기반
모델은 환경의 역학 시뮬레이션을 나타낸다. 즉, 모델은 현재 상태 s0과 다음 상태 s1의 쌍에서 전이 확률 T(s1|(s0, a))를 학습한다. 전이 확률이 성공적으로 학습되면 에이전트는 현재 상태와 행동이 주어진 특정 상태로 진입할 가능성을 알게 된다. 그러나 모델 기반 알고리즘은 상태 공간과 작업 공간이 커짐에 따라 실용적이지 않게 된다.
반면에 모델이 없는 알고리즘은 지식을 업데이트하기 위해 시행착오에 의존한다. 따라서 상태와 행동의 모든 조합을 저장할 공간이 필요하지 않다. 다음 섹션에서 설명하는 모든 알고리즘은 이에 속한다.
On-policy v.s. Off-policy
on-policy agent는 현재 정책에서 파생된 현재 작업을 기반으로 값을 학습하는 반면 off-policy counter part는 다른 정책에서 가져온 작업 a*를 기반으로 값을 학습한다. Q-러닝에서 그러한 정책은 greedy policy이다. (이에 대해서는 Q-Learning과 SARSA에서 더 자세히 설명할 것이다)
2. 다양한 알고리즘의 그림
2.1 Q-Learning
Q-러닝은 잘 알려진 벨만 방정식을 기반으로 하는 off-policy, 모델이 없는 RL 알고리즘이다.
벨만 방정식
위의 방정식에서 E는 기대치를 의미하고, ƛ는 할인율을 나타낸다. Q-값의 형태로 다시 작성할 수 있다:
Q-값 형식의 벨만 방정식
Q*로 표기되는 최적의 Q 값은 다음과 같이 표현할 수 있다:
목적은 Q-값을 최대화하는 것이다. Q-값 최적화 방법에 대해 살펴보기 전에 Q-러닝과 밀접한 관련이 있는 두 가지 가치 업데이트 방법에 대해 논의하고자 한다.
정책 반복
정책 반복은 정책 평가와 정책 개선 사이의 루프를 실행한다.
정책 평가는 마지막 정책 개선에서 얻은 그리디 정책으로 V를 추정한다. 반면에 정책 개선은 각 상태에 대해 V를 최대화하는 작업으로 정책을 업데이트한다. 업데이트 방정식은 벨만 방정식을 기반으로 한다. 수렴될 때까지 계속 반복된다.
값 반복
값 반복에는 하나의 구성 요소만 포함된다. 최적 벨만 방정식을 기반으로 V를 업데이트한다.
수렴된 후, 최적의 정책은 모든 상태에 대해 argument-max 함수를 적용하여 직접적으로 도출된다.
이 두 가지 방법에는 전이 확률 p에 대한 지식이 필요하며, 이는 이 알고리즘이 모형 기반 알고리즘임을 나타낸다. 그러나 앞서 언급했듯이 모델 기반 알고리즘은 확장성 문제로 어려움을 겪고 있다. 그렇다면 Q-러닝은 이 문제를 어떻게 해결할 수 있을까?
α는 학습 속도(즉, 목표에 얼마나 빨리 접근하고 있는지)를 나타낸다. Q-러닝의 아이디어는 값 반복에 크게 의존한다. 그러나 업데이트 방정식은 위의 공식으로 대체된다. 결과적으로 우리는 더 이상 전이 확률에 대해 걱정할 필요가 없다.
다음 행동 a’는 현재 정책을 따르는 대신 다음 상태의 Q-값을 최대화하기 위해 선택된다. 따라서 Q-러닝은 off-policy에 속한다.
2.2 SARSA
SARSA는 Q-러닝과 매우 유사하다. SARSA와 Q-러닝의 중요한 차이점은 SARSA가 정책 알고리즘이라는 것이다. SARSA가 그리디 정책 대신 현재의 정책이 수행하는 행동을 바탕으로 Q값을 학습한다는 의미를 담고 있다.
행동 a_(t+1)은 현재 정책에서 다음 상태 s_(t+1)에서 수행되는 작업이다.
위의 유사 코드에서는 항상 현재 정책을 따르는 두 가지 행동을 선택할 수 있다. 대조적으로 Q-러닝은 다음 상태에 대한 Q-값을 최대화하는 한 다음 동작에 대한 제약이 없다. 따라서, SARSA는 on-policy 알고리즘이다.
2.3 DQN
Q-러닝은 매우 강력한 알고리즘이지만, 일반성이 부족하다는 것이 가장 큰 약점이다. Q-러닝을 2차원 배열(작업 공간 * 상태 공간)의 숫자를 업데이트하는 것으로 본다면 실제로 동적 프로그래밍과 유사하다. 이는 Q-러닝 에이전트가 이전에 보지 못한 상태의 경우 어떤 행동을 취해야 할지 알 수 없다는 것을 나타낸다. 즉, Q-러닝 에이전트는 보이지 않는 상태의 값을 추정할 수 없다. 이를 해결하기 위해 DQN은 신경망을 도입해 2차원 배열을 없앴다.
DQN은 신경망을 활용하여 Q-값 함수를 추정한다.
2013년에 딥마인드는 위 그림과 같이 아타리 게임에 DQN을 적용하였다. 입력은 현재 게임 상황의 원시 이미지이다. 컨볼루션 레이어뿐만 아니라 완전 연결 레이어를 포함한 여러 레이어를 거쳤다. 출력은 에이전트에서 수행할 수 있는 각 작업에 대한 Q-값다.
질문은 네트워크를 어떻게 훈련시키느냐로 요약된다.
답은 Q-러닝 업데이트 방정식을 기반으로 네트워크를 교육하는 것이다. Q-러닝의 목표 Q-값은 다음과 같다.
ϕ는 상태 s와 동일한 반면, θ는 신경망의 매개 변수를 나타내며, 이는 논의의 영역에 속하지 않는다. 따라서 네트워크의 손실 함수는 목표 Q 값과 네트워크의 Q 값 출력 사이의 제곱 오차로 정의된다.
또 다른 두 가지 기술은 DQN 훈련에 필수적이다.
- Experience Replay: 일반적인 RL 셋업에서 훈련 샘플은 높은 상관관계가 있고 데이터 효율성이 낮기 때문에 네트워크의 수렴이 더 어려워진다. 샘플 분배 문제를 해결하는 방법은 Experience Replay을 채택하는 것이다. 기본적으로 샘플 트랜지션이 저장되며, 이 트랜지션은 지식을 업데이트하기 위해 “트랜지션 풀”에서 무작위로 선택된다.
- Separate Target Network: 타겟 Q 네트워크는 값을 추정하는 네트워크와 구조가 동일하다. 위의 유사 코드에 따라 C 단계마다 타겟 네트워크가 다른 네트워크로 재설정된다. 따라서 변동이 덜해 보다 안정적인 훈련이 이뤄진다.
3. 결론
지금까지 Q-러닝, SARSA, DQN의 몇 가지 기본 개념에 대해 논의했다. 다음 포스팅에서는 NAF, A3C 등을 포함한 다른 최첨단 강화 학습 알고리즘에 대해 계속 논의할 것이다. 관련하여 문제나 질문이 있으면, 주저하지 말고 아래 댓글을 남기거나 트위터를 팔로우하길 바란다.
번역 – 핀인사이트 인턴연구원 강지윤(shety0427@gmail.com)
원문 보러가기>
