[강화학습] 시간차 학습, SARSA, Q-Learning

시작하기 전에, 간단하게 강화학습에서의 몬테 카를로와 DP의 특징에 대해 짚고 넘어가겠다.

DP

• 다이나믹 프로그래밍의 점화식을 통한 증분 계산을 활용한다.
• 장점
  • 따라서 에피소드 진행 중 평가와 개선을 번갈아가며 최적 정책을 얻을 수 있다.
  • 이 과정에서 반복되는 계산을 하나로 합쳐 진행하는 최적화(가치 반복법) 또한 가능하다.
• 단점
  • 환경 모델(상태 전이 확률과 보상 함수)이 확실하게 알려져 있어야 계산이 가능하다.
  • 계산량에 대한 부하가 심하다.

몬테 카를로

• 실제 시나리오를 돌려보면서 환경을 추론한다. (비정상 Multi-Armed Bandit 문제)
• 장점
  • 환경 모델이 확실하지 않더라도 평가/개선이 가능하다.
• 단점
  • 몬테 카를로의 특성 상, 하나의 에피소드가 끝나야 평가 후 개선이 가능하다.
  • 일회성 과제에서만 사용이 가능하고, 지속적 과제에서는 사용이 불가능하다.

TD 기법(Temporal Difference, 시간차) 기법은 환경 모델을 사용하지 않으며, 행동을 한번 수행할 때마다 가치 함수를 갱신한다.
즉, DP + 몬테 카를로의 방식으로 구현된다.

TD법으로 정책 평가하기

TD법 도출

그럼 TD법을 수식으로 도출해보자.
이는 다음과 같은 과정으로 구성된다.

1. '수익'과 '상태 가치 함수'의 정의
2. 몬테 카를로법의 수식
3. DP의 수식
4. TD법의 도출

먼저 수익에 대해 복습해보자.

이 수익을 적용하면 가치 함수는 다음과 같이 정의된다.

위 식의 각 부분을 통해 몬테 카를로와 DP를 통한 정책 평가 식이 도출된다.

몬테 카를로법의 도출

몬테 카를로는 아래 식에서 도출된다.

몬테 카를로에서는 기댓값을 계산하는 대신 실제 수익의 샘플 데이터를 평균하여 위 식의 기댓값을 근사한다.

 

평균에는 표본 평균과 지수 이동 평균이 있는데, 비정상 문제에서는 일반적으로 지수 이동 평균을 사용한다.
그 수식은 아래와 같다.

여기서 V는 현재의 가치 함수이고, V'는 갱신 후의 가치 함수이다.

이후 아래 나오는 ' 마크는 'next'를 의미한다.

 

그래서 위 식은 V를 Gt쪽으로 갱신하고 있다.
Gt쪽으로 얼마나 갱신할지는 alpha로 조정한다.

이러한 방식은 하나의 시나리오가 끝나야 가능하므로, DFS 개념과 유사하다.

DP의 도출

DP로 수행하는 정책 평가는 아래 식에서 도출된다.

수식으로는 아래와 같다.

참고로 전개된 식은 벨만 장정식이다.
즉, DP를 통한 정책 평가는 벨만 방정식을 기반으로 가치함수를 순차적으로 갱신한다.

 

갱신 식은 다음과 같다.

이와 같은 다음 가치 함수의 추정치를 이용하여 현재 가치 함수를 갱신하는 기법을 부트스트랩이라 한다.

이러한 방식은 시나리오 내 1스텝마다 해당 상태의 가치 함수를 갱신하므로, BFS 개념과 유사하다.

TD법의 도출

TD법은 DP와 몬테카를로를 어느정도 합친다.

• DP처럼 부트스트랩을 통해 가치 함수를 순차적으로 갱신
• 몬테 카를로처럼 환경에 대한 정보 없이 샘플링된 데이터만으로 가치 함수 갱신

위 식의 첫번째 줄은 모든 후부에 대해 "중괄호 부분", 즉 보상과 다음 가치 함수를 계산해야 한다.
이를 기댓값 E의 형태로 다시 쓰면 아래 식처럼 변형된다.

TD법에서는 아래 항을 '샘플 데이터에서 근사'한다.

그래서 TD 갱신식을 수식으로 표현하면 다음과 같다.

여기서 해당 부분을 TD Target이라 한다.

그리고 TD법은 V를 TD Target 방향으로 갱신한다.

여기서는 1단계 앞의 정보를 TD Target으로 사용했다.
이 아이디어를 확장하면 2단계 앞, 3단계 앞과 같이 n단계 앞의 정보를 이용하는 것도 생각할 수 있다.
이를 n단계 TD법이라고 한다.

MC법과 TD법 비교

환경 모델을 모를 때 사용할 수 있는 도구로 MC(몬테-카를로)법과 TD법이 있다.
그렇다면 둘 쭝 어느 방법이 나을까?

대부분은 TD법이 더 좋다.

• 지속성 과제
  • MC법 사용 불가
  • TD법 사용
• 일회성 과제
  • 성능이 어느쪽이 항상 더 나은지는 증명되지 않음
  • 하지만 현실의 많은 문제에서 TD법이 더 빠르게 학습한다.(가치 함수의 갱신이 빠르다.)

TD법이 더 나은 이유

이는 MC법과 TD법이 각각 무엇을 Target으로 하는지를 보면 그 이유를 알 수 있다.

• MC법의 가치함수 증분 식

• TD법의 가치함수 증분 식

 

이 위에서 알 수 있듯이 MC법은 수익 G를 Target으로 하여 그 방향으로 V를 갱신한다.
반면 TD법의 Target는 한 단계 앞의 정보를 이용해 계산한다.

 

즉, 전체 수익을 알아야 하는 MC와 달리, 한 단계만 진행해도 갱신할 수 있는 TD가 유리하다.

 

또한, MC법의 Target G는 많은 시간을 쌓아서 얻은 결과이기 때문에 값의 분산이 큰 편이다.
하지만 TD법의 Target은 한 단계 앞의 데이터만을 기반으로 하기 때문에, 분산이 작은 편이다;.

TD법에 문제는 없는가?

TD Target은 자세히 보면, 추정치인 V가 사용되고 있다.
즉, TD법은 '추정치로 추정치를 갱신'하는 부트스트래핑이다.

 

이처럼 TD Target은 추정치를 포함하기 때문에 정확한 값이 아니고, 이를 학문적으로는 편향이 있다라고 한다.
하지만 편향은 갱신이 반복될 때마다 점점 작아져 결국에는 0으로 수렴하게 된다.

 

반면, MC법의 Target에는 추정치가 포함되지 않기 때문에 '편향이 없다'라고 할 수 있다.

TD법 구현

TD법은 대략 아래와 같은 방식으로 구현된다.

SARSA

앞 절에서는 TD법으로 정책을 평가했다.
정책 평가가 끝나면 다음 단계는 정책 제어이다.

 

TD 정책에 사용하는 정책 제어 알고리즘을 SARSA라고 한다.
이는 아래와 같은 유래에서 왔다.

이 다섯가지 데이터는 TD에서 사용하는 5가지 데이터에서 온 것이다.

---

 

SARSA에는 크게 두가지 방식이 있다.

• On-Policy SARSA
• Off-Policy SARSA

On-Policy SARSA

앞 절에서는 상태가치함수 V를 평가했다.
하지만 정책을 제어할 때는 V가 아닌 행동 가치 함수 Q를 사용해야 한다.

 

개선 단계에서는 정책을 탐욕화해야 하며, V의 경우 환경 모델이 필요하다.
반면, Q라면 다음과 같이 계산할 수 있고, 환경 모델이 필요하지 않다.

그 이유와 바꾸는 방법은 해당 링크에서 알 수 있다.

[강화학습] 강화학습에서 최적 정책을 찾는 방법

 

그러므로 위에서 정의한 이 가치 함수 증분 식을 Q 함수로 바꾸자.

이는 단순히 V를 Q로 바꾸고, 인자로 A를 추가해주기만 하면 된다.

Q함수는 State와 Action을 묶은 데이터를 하나의 단위로 삼는다.
즉, SARSA를 모두 획득했다면 이를 식에 대입하여 Q를 즉시 갱신할 수 있다.
그리고 이 갱신이 끝나면 바로 '개선' 단계로 넘어갈 수 있다.
구체적으로 알아보자면, 상태 S에서의 정책은 다음과 같이 개선될 수 있다.

이상이 간단한 On-Policy SARSA 이다.

On-Policy SARSA 구현

SARSA 에이전트는 아래와 같이 구현 가능하다.

특이 사항으로는 덱의 사용인데,
파이썬의 덱은 지정된 원소 수를 초과하여 원소가 추가되면 FIFO 원칙에 따라 가장 오래된 원소를 삭제한다.
이 특성을 이용하여 가장 최근의 경험 데이터만 보관할 수 있다.

 

SARSA Agent를 실행하는 코드는 아래와 같다.

문제를 푼 모습을 보자.
현재 문제는 다음과 같이 구성되어 있다.

회색 칸은 벽을 의미한다.

 

행동 가치 함수 Q의 분포 결과

 

정상적으로 폭탄에서 멀어지고, 사과쪽으로 다가가도록 구현된 것을 확인할 수 있었다.

Off-Policy SARSA

사실 Off-Policy SARSA는 위에서 설명한 On-Policy SARSA에 Target 정책과 Behavior 정책 분리만 잘 끼얹으면(?)된다.

 

그래서 어떤 데이터를 샘플링하고, 어떻게 보정하는지에 집중해서 설명하도록 하겠다.

Off-Policy와 중요도 샘플링

Off-Policy에서는 에이전트가 Behavior 정책과 Target 정책을 따로 가지고 있다.
그리고 이 샘플 데이터를 이용하여 Target 정책을 탐욕스럽게 갱신한다.
이때 주의할 점이 두 가지 있다.

• Behavior 정책과 Target 정책의 확률 분포가 비슷할수록 결과는 안정적이다.
  이 점을 고려하여 현재의 Q 함수에 대해 Behavior 정책은 입실론-그리디 정책으로 갱신하고, Target 정책은 탐욕 정책으로 갱신한다.
• 두 정책이 서로 다르기 때문에 중요도 샘플링을 활용하여 가중치 rho로 보정한다.

자세한 내용은 해당 링크를 참고 바랍니다.

[강화학습] Off-Policy, On-Policy, 중요도 샘플링

 

그러면 어떤 데이터를 샘플링해야 할까?

---

우선 Q_pi를 갱신하는 경우를 살펴보자.
이때 SARSA의 갱신식은 다음과 같다.

• 즉, (S_t, A_t)가 갱신 대상이다.
• 이때 이 S_t, A_t는 임의로 선택할 수 있다.
• 그리고 이때 다음 상태 S_t+1는 환경의 상태 전이 확률 p(s'|s, a)에 따라 샘플링된다.
• 그리고 상태 S_t+1에서 선택되는 행동은 대상 정책 pi(또는 행동 정책 b)에 따라 샘플링된다.
• 이때 행동이 정책 pi에 따라 선택됨을 명시하면 SARSA의 갱신식을 다음처럼 작성할 수 있다.

위 식은 Q_pi를 R_t + gamma * Q_pi(S_t+1, A_t+1) 방향으로 갱신함을 나타낸다.

---

다음으로 행동 A_t+1 이 정책 b에 따라 샘플링된 경우를 생각해보자.
이 경우, 가중치 rho로 목표를 보정한다.(중요도 샘플링)

따라서 Off-Policy SARSA의 갱신식은 다음과 같다.

이렇게 타겟 정책 pi 에 대한 계산값을 행동 정책 b에서 샘플링하여 구할 수 있게 되었다.

Off-Policy SARSA 구현

Off-Policy SARSA 의 구현은 다음과 같다.

이번에도 On-Policy때와 같은 문제를 풀어보자.

결과는 아래와 같다.

Q 함수의 값. 폭탄을 강하게 피하고 있지는 않다.

 

제대로 폭탄을 피하지 않고 있는 모습을 볼 수 있다.
약간의 아쉬움이 남는다.

Q-Learning

사실 '중요도 샘플링'은 가급적이면 피하고 싶은 기법이다.

• 중요도 샘플링은 결과가 불안정하기 쉽다.
  • 두 정책의 확률분포가 다를수록 샘플링에서 사용하는 가중치 rho도 변동성이 커진다.
  • 이에 따라 SARSA의 갱신식에 등장하는 Target도 변동되기 때문에 Q 함수의 갱신 역시 불안정해진다.

이 문제를 해결해주는 것이 바로 Q-Learning이다.
Q 러닝의 대표적인 특징은 다음 세가지로 요약 가능하다.

1. TD법
2. Off-Policy
3. 중요도 샘플링을 사용하지 않음

Q러닝을 기존에 배웠던 개념들과 연결지으면 아래와 같은 형태가 된다.

지금부터 벨만 방정식과 SARSA의 관계를 확인하고, 벨만 최적 방정식에서 Q 러닝을 도출해보도록 하겠다.

벨만 방정식과 SARSA

먼저 벨만 방정식과 SARSA의 관계부터 보자.

 

정책 pi에서의 Q함수를 q_pi라고 했을 때, 벨만 방정식은 다음 식으로 표현된다.

이 벨만 방정식에서 중요한 점은 두가지이다.

• 환경의 상태 전이 확률 p에 따른 다음 단계의 '모든' 상태 전이를 고려한다.
• 에이전트의 정책 pi에 따른 다음 단계의 '모든' 행동을 고려한다.

간단하게 벨만 방정식의 백업 다이어그램을 그려봤다.
이 그림에서 형광펜으로 색칠된 영역을 보면, 얼마나 넓게 커버하고 있는지 감이 잡힐 것이다.

위와 같이 벨만 방정식은 다음 상태와 다음 행동의 '모든' 후보를 고려한다.

따라서 SARSA는 벨만 방정식의 '샘플링 버전'으로 볼 수 있다.

모든 전이가 아닌 '샘플링된 데이터'를 사용한다는 뜻이다.

 

 

SARSA에서 다음 상태 S_t+1 은 p(s'|s, a)로부터 샘플링된다.
그리고 다음 행동 A_t+1은 정책 pi(a|s)로부터 샘플링한다.

이때 SARSA의 TD Target은 위 식이 된다.
이 목표 방향으로 Q함수를 조금만 갱신하면 된다.

 

벨만 방정식이 SARSA에 대응한다면, 벨만 최적 방정식에 대응하는 개념도 생각할 수 있을 것 같지 않은가?
그것이 바로 Q 러닝이다.

벨만 최적 방정식과 Q-Learning

먼저 Q함수의 벨만 최적 방정식을 보자.

벨만 최적 방정식은 벨만 방정식과 달리 max 연산자를 사용한다.
이를 백업 다이어그램으로 표현하면 다음과 같다.

즉 그림과 같이, 행동 A_t+1로는 Q함수가 가장 큰 행동이 선택된다.

 

이를 기반으로 SARSA도 벨만 최적 방정식 형태로 바꿔보자.

위 식에 따라 Q 함수를 반복 갱신하면 최적 정책의 Q 함수에 가까워진다.
여기서 다음 상태 s′에서 실제로 고른 행동이 무엇이든 상관없이, 업데이트는 항상 “거기서 최적 행동을 했을 때”의 값(max)을 향해 간다.
즉, '탐색' 정책과 '최적' 정책이 분리된 Off-Policy 형태로 동작한다.

Q-Learning 구현

구현은 아래와 같다.

update의 맨 아랫줄을 확인해보면, behavior 정책과 target 정책을 따로 갱신해주는 것을 알 수 있다.
즉, behavior 정책에서만 epsilon-greedy 정책으로 갱신하고, target 정책에선 greedy 정책으로 갱신하고 있다.

 

이제 이 코드를 돌려보자.

 

 

Off-Policy SARSA보다 훨씬 나아진 것을 확인할 수 있었다.

정리

이번 내용을 키워드로 정리해보자.

• 강화 학습 기법
  • 몬테 카를로
  • DP
    • 부트스트랩
  • TD (시간차 학습)
    • Target(목표)
    • TD Target
    • 편향
• TD의 정책 제어 방법
  • SARSA
    • On-Policy SARSA
    • Off-Policy SARSA
  • Q-Learning
    • TD
    • OFF-Policy
    • 중요도 샘플링 없음

본 내용은 밑바닥부터 시작하는 딥러닝 4를 참고하여 작성되었습니다.

밑바닥부터 시작하는 딥러닝 4 - 예스24