[강화시스터즈 1기] SARSA / Q-러닝
강화학습이란.
다이나믹 프로그래밍 → 강화학습
MDP 문제를 해결하기 위해 고안된 다이나믹 프로그래밍은 MDP 문제를 수학적으로 엄밀하게 설명할 수 있다는 장점이 있다. 하지만 반복을 통한 문제 해결은 엄청난 계산양을 요구했고, 모델이 없는 상황에서 사용할 수 없는 한계가 존재했다.
이러한 다이나믹 프로그래밍의 한계를 보완한 학습이 강화학습이다. 강화학습은 다이나믹 프로그래밍과 달리, 가치 함수를 계산하지 않고 경험을 통해 가치를 찾는다. 이때 경험은 환경과의 상호작용으로 발생한 상태,행동,보상을 일컫는 표현이며, 강화학습의 핵심이다. 강화학습의 기본적인 경험의 구조는 다음과 같다.
- 일단 어떤 행동을 시도한다.
- 보상에 따라 행동의 가치를 평가한다.
- 평가한 값을 기준으로 정책을 업데이트한다.
- 1-3 과정을 반복한다.
경험으로 가치 함수를 계산하기 때문에, 강화학습은 엄밀하게 모든 전이가 정의된 모델 없이도 환경의 입출력 사이의 관계를 학습할 수 있다.
-
환경의 입출력이란?
환경의 입력값은 에이전트가 현재 위치한 State와 선택한 Action이고,
출력값은 환경으로부터 주어지는 Reward다.
정책 이터레이션 (GPI)와 강화학습
강화학습은 GPI와 가치함수를 찾는 과정이 다를 뿐, 현재 정책에 따라 가치를 찾고, 찾은 가치를 바탕으로 정책을 수정하는 GPI의 구조를 동일하게 따른다.
정책 이터레이션에서 주어진 정책에 따라 가치 함수를 학습하는 정책 평가를 강화학습은 예측이라 부르고, 가치함수를 바탕으로 정책을 발전시켜 최적 정책을 찾는 정책 평가 및 발전을 강화학습은 제어라 표현한다.
| 정책 이터레이션 | 강화학습 | 의미 |
|---|---|---|
| 정책 평가 | 예측 | 주어진 정책에 대한 가치 함수를 학습 |
| 정책 평가 및 발전 | 제어 | 가치 함수를 바탕으로 정책을 발전시켜 최적 정책을 찾는 과정 |
모델 유무에 따른 가치 함수 종류
모델이 없는 상황에서 상태 가치 vs 행동 가치??
모델이 없는 상황에서는 상태 가치보다 행동 가치가 유용하다. 모델이 있는 경우엔 상태 가치만으로 정책을 구할 수 있다. 정의된 모델을 바탕으로 어떤 행동이 더 좋은지 선택할 수 있기 때문이다. 하지만 모델이 존재하지 않는다면, 명확히 상태-행동에 대한 가치가 매칭되어 있는 행동 가치가 더 정책을 선택하기에 유리하다.
몬테 카를로
몬테 카를로(Monte Carlo)
몬테 카를로는 랜덤 추출방식을 이용해 함수를 모르는 상황에서 값을 근사하기 위한 시뮬레이션 방법이다. 몬테 카를로는 표본의 수가 커짐에 따라 표본 평균이 기댓값에 수렴한다는 큰 수의 법칙을 따른다.
몬테 카를로와 강화학습
몬테 카를로 방식은 상태-행동 쌍에 대한 이득의 표본을 모으고 평균을 계산해 가치 를 구한다. 이 방식은 가치 함수를 구할 때 값을 순차적으로 계산하는 다이나믹 프로그래밍과 달리, 표본 이득으로 가치 함수를 학습할 수 있다는 점에서 강화학습과 맞닿아 있다.
몬테 카를로는 한 번의 에피소드가 진행됨에 따라 경험(상태-행동-보상)이 축적되기 때문에, 한 에피소드가 종결된 이후에 가치 함수를 업데이트한다. 다시 말해, 몬테 카를로 방법은 에피소드와 에피소드 사이에서만 가치 함수 업데이트가 발생한다.
몬테 카를로 예측
특정 상태의 가치는 현 상태 이후 계산된 이득의 기댓값(이득 = 할인된 미래 보상 누적)이다. 이 값은 몬테 카를로의 기본 정의에서 유도할 수 있다. 몬테 카를로는 표본의 개수가 증가하면 그 평균값이 기댓값과 동일해진다는 큰 수의 법칙을 따른다. 따라서 몬테 카를로 방식으로 모든 상태의 행동 가치를 구하기 위해서는 많은 양의 상태-행동 표본이 필요하며, 이를 수집하기 위해 많은 에피소드를 반복한다.
보강 다이어그램
몬테 카를로 예측을 위한 보강 다이어그램은 다음과 같다. 이 보강 다이어그램은 단일 에피소드의 시작 시점부터 끝 시점까지 모사한다.
예측 : 가치 함수 업데이트
각 상태별 가치 함수의 업데이트는 새로운 표본이 들어올 때마다 발생한다. 그 관계를 나타낸 식이 아래와 같다.
- $V_{\pi}(s)$ : 오차를 포함하고 있는 가치 함수
- $N(s)$ : 전체 실행된 에피소드에서 상태 s를 방문한 횟수
- $G_i(s)$ : 현재 받은 반환값이자, 가치 함수 입장에서 업데이트를 통해 도달하고자하는 목표
- $G_n - V_n$ : 오차
- $\frac{1}{n}$ : step size
몬테 카를로 방식은 가치 함수를 구하기 위해 새로운 표본이 들어올 때마다 업데이트를 진행한다. 맨 마지막 수식을 풀어서 이해하면 다음과 같다.
$V_{n+1} =V_n + \frac{1}{n}(G_n - V_n)$
새로운 표본 이득이 들어올 때 가치 함수를 업데이트를 하는 방식은 기존의 가치에 현재 받은 반환값과 기존 가치 사이의 오차를 평균으로 나누어 더하는 방식이다. 다시 말해 기존의 가치 함수에 $\frac{1}{n}(G_n - V_n)$ 를 더해 업데이트한다.
- step size
| step size인 $\frac{1}{n}$는 $\alpha$로 일반화가능하다. | $V(s) ← V(s) + \alpha ( G(s) - V(s))$ |
step size $\alpha$ 를 일반화해서 표현하는 이유는 이 값에 따라 업데이트 정도를 조절할 수 있기 때문이다. step size $\alpha$ 는 몬테 카를로 이론을 바탕의 $\frac{1}{n}$과 상수로 나뉜다. 상수인 step size $\alpha$ 은 과거의 반환값보다 현재 에피소드로 얻은 반환값을 중요하게 보고 업데이트하겠다는 의미로 해석할 수 있다. 또한 상수의 값이 클수록, 과거의 값을 지수적으로 감소하는 역할을 한다.
예측 방법
정책 $\pi$ 아래서 이뤄지는 한 에피소드에서 상태 $s$가 발생하는 것을 $s$와의 접촉이라 표현한다. 동일 에피소드 안에서 $s$를 여러 번 마주칠 수 있으며, 첫 접촉을 $s$와의 최초 접촉이라 부른다.
몬테카를로 예측 방법은 접촉 시점에 따라 두 개로 나뉜다. 최초 접촉 이후에 발생하는 이득의 평균을 구하는 최초 접촉 MC 방법과, $s$와의 모든 접촉 이후, 다시 말해 마지막 $s$와의 접촉 이후에 발생하는 이득의 평균을 구하는 모든 접촉 MC 방법이 있다. 두 방법은 유사하지만, 이론적으로 특성에 차이가 존재하며 일반적으로는 최초 접촉 MC 방법이 더 널리 사용된다.
input : Current Policy
init:
모든 s에 대한 가치 함수를 초기화
모든 s의 표본 담는 리스트 초기화
loop:
현재 정책을 따르는 에피소드 생성
G = 0
for t in range(len(sample),-1): # 뒤부터 훑음, [0,T-1]
G = (할인율)*G + Reward
만약 현재 상태 s가 전 타임스텝에 없다면(=최초 접촉이라면):
s 이득의 표본으로 G를 저장
s의 가치 함수 = 쌓인 이득의 표본의 평균
- 최초 접촉 MC 방법의 추정 방법은 다음과 같다.
몬테 카를로 제어
몬테 카를로 제어는 행동 가치 함수를 이용하기 때문에 모델 없이도, 탐욕적인 정책을 구할 수 있다. 하지만 몬테 카를로 방법은 전체 상태-행동 표본을 확보하기 위해 시작 탐험이 필요하며, 예측이 무한대로 시행될 수 있다는 한계가 있다. 이런 이론적인 한계를 벗어나는 여러 방법론들이 정의되고, 사용되고 있지만 현 단계에서는 제어 부분은 구체적으로 언급하지 않고 넘어가도록 한다.
시간차 학습
시간차 학습은 몬테 카를로의 표본을 통한 가치 함수 추정과 다이나믹 프로그래밍의 부분적 갱신을 합친 학습 방법론이다. 몬테 카를로 방법은 가치 함수의 값을 계산하지 않고 표본을 통해 예측한다. 이는 모델 없이도 모든 상태의 가치를 알 수 있기 때문에 유용하다. 하지만 몬테 카를로 방법은 에피소드 종결 이후에만 가치 함수 업데이트가 가능하기 때문에 에피소드가 끝나지 않거나, 길이가 긴 경우에 적합하지 않다. 반대로 다이나믹 프로그래밍은 타임 스텝 별로 각 가치 함수를 갱신해 나간다. 하지만 이 방법론은 모델이 없으면 계산이 불가능하다는 단점이 있다. 이 두 학습 방법의 장점을 합친 것이 시간차 학습이다.
| 장점 | 단점 | |
|---|---|---|
| 몬테 카를로 | 모델 없이 표본 이득을 통해 가치 함수 추정 | 길이가 길거나 무한대인 에피소드에 적합하지 않음 |
| 다이나믹 프로그래밍 | 시간 단계 별로 업데이트가 가능함 | 모델을 바탕으로 계산해야 함 |
| 시간차 학습 | 몬테 카를로 + 다이나믹 프로그래밍 장점을 합한 방법론 | - |
시간차 예측(TD)
시간차 예측 (몬테 카를로 예측, 정책 평가과 함께)
- 가치 함수
시간차 예측은 벨만 기대 방정식에서 출발한다.
다이나믹 프로그래밍의 정책 평가 과정에서는 벨만 기대 방정식을 풀기 위해 값들을 계산하지만, 시간차 예측은 $R_{t+1}+\gamma V_{\pi}(S_{t+1})$ 값을 샘플링해 가치 함수의 값을 구한다.
- 가치 함수의 업데이트
가치 함수는 몬테 카를로 예측처럼 각 상태의 표본이 쌓일 때마다 업데이트가 발생한다. 먼저 몬테 카를로 예측에서 가치 함수를 업데이트하는 식은 다음과 같다.
$V(s) ← V(s) + \alpha ( G(s) - V(s))$
이 식은 몬테 카를로 예측에서 업데이트 시 학습의 방향을 제시해주는 값이 $G(s)$임을 알려준다.
시간차 예측에서 가치 함수를 업데이트하는 식은 다음과 같다.
$V(S_t) ← V(S_t) + \alpha ( 𝑅_{t+1}+\gamma V(S_{t+1}) - V(S_t))$
시간차 예측은 몬테 카를로 예측과 달리 $𝑅_{t+1}+\gamma V(S_{t+1})$을 학습 방향으로 삼는다. 이런 식의 표현은 몬테 카를로와 달리, 움직이는 타임 스텝마다 가치 함수를 갱신할 수 있게 만든다.
input : current Policy
모든 s의 가치 함수 값을 임의의 수로 초기화. 단, V(종단) = 0
for epi in range(EPISODE):
S 초기화
while epi_end == False:
A = 현 S에서의 정책에 따라 결정
Reward, next_state <- 행동 A를 취함
v(S) 업데이트
S = next_state
보강 다이어그램
보강 다이어그램으로 나타낸 시간차 제어는 위와 같이 표현된다. 시간차 제어는 몬테 카를로처럼 표본을 이용해 가치 함수를 학습하지만, 타임 스텝 단위로의 갱신이 일어난다. 따라서 현재 상태의 가치 함수는 바로 이어지는 다음 상태로의 표본 전이 이후에 계산될 수 있다.
활성 정책(on-Policy) vs 비활성 정책(Off-Policy)
-
On Policy
활성 정책 방법은 결정을 내리는 데 사용되는 정책을 평가하고 향상시킨다.
-
Off Policy
비활성 정책 방법은 활성 정책과 달리 정책을 행동 정책과 목표 정책으로 분리한다. 행동 정책은 자료를 생성하는 데 사용하는 정책이며(주로 탐험함), 목표 정책은 가장 좋은 정책을 향해 학습하는 정책이다.
시간차 제어(SARSA)
SARSA는 온폴리쉬 시간차 제어 방식이다.
시간차 학습은 몬테 카를로와 마찬가지로 model-free한 방식이다. 따라서 정책을 효과적으로 선택하기 위해서는 상태 가치 함수보단 행동 가치 함수가 효과적이다. 행동 가치 함수를 기준으로 시간차 예측을 표현하면 다음과 같다.
$𝑄(𝑠,𝑎) ← 𝑄(𝑠,𝑎) + 𝛼(𝑅_{𝑡+1} + 𝛾𝑄(𝑠’,𝑎’) − 𝑄(𝑠,𝑎))$
이런 업데이트는 비종단 상태 $S_t$로부터 전이가 일어날 때마다 전이 이후에 행해진다. 따라서 현 상태-행동의 가치를 구하기 위해서는 현재 상태(S), 행동(A), 보상(R), 다음 상태(S’), 다음 상태에서의 행동(A’)가 필요하다. SARSA는 이 알고리즘에 필요한 요소들의 앞글자를 따 명명되었다.
SARSA의 구조는 단순하다. 모든 활성 정책과 마찬가지로, 행동 정책 $\pi$에 대하여 $q_{\pi}$를 생성하는 동시에, $q_{\pi}$을 바탕으로 탐욕 선택을 해 행동 정책 $\pi$을 갱신해 나간다.
모든 s,a의 행동 가치 함수 값을 임의의 수로 초기화. 단, Q(종단,.) = 0
for epi in range(EPISODE):
S 초기화
현 정책에 따라 탐욕적인 A를 선택 : 정책(S) = A
while epi_end == False:
Reward, S' <- 행동 A를 취함
현 정책에 따라 A'를 선택 : 정책(S') = A'
Q(S) 업데이트 by SARSA
S, A = S', A'
부트스트랩
시간차 예측은 부트스트랩 기법을 이용한다. 통계적인 방법론인 부트스트랩은 표본집합에서 반복적으로 표본을 추출하여, 모수를 찾고자하는 방법론이다. 시간차 예측은 이전 추정값에 기반해 현재 자신의 추정값을 갱신한다. SARSA의 경우, 𝑄(𝑠,𝑎)를 갱신하기 위해 𝑅𝑡+1+𝛾𝑄(𝑠′,𝑎′) 를 사용한다. 이 업데이트 관계는 Q 함수의 값을 예측하기 위해 또 다른 Q함수를 이용한다는 점에서 부트스트랩 기법과 상응한다.
탐험
SARSA는 처음부터 탐욕 정책으로 행동하기 때문에 초기 가중치에 영향을 많이 받는다. 이 문제는 탐험으로 해결할 수 있다.
$\epsilon$-탐욕 정책은 대표적인 탐험 정책으로, (100-$\epsilon$)% 는 정책에 대해 탐욕적인 행동을 취하지만, $\epsilon$%로 랜덤 action을 취한다.
SARSA의 한계
SARSA는 행동 가치 함수 기반이며, 다음 행동 가치의 값이 현 행동 가치 값 갱신에 이용된다. 따라서 만약 s’의 행동이 -의 행동 가치를 갖고 있었다면, s-a 행동 가치에도 영향을 끼친다. 이는 두 행동 가치 함수가 공통으로 긍정적인 값을 갖거나 부정적인 값을 가질 때엔 상관없지만, 상반된 성질을 지니고 있다면 잘못된 방향으로 학습되는 문제가 발생한다. 이런 SARSA의 한계를 극복한 것이 Q-러닝이다.
Q-러닝
Q-러닝은 비활성 정책 시간차 제어 방식이다. Q-러닝은 다른 비활성 정책처럼 행동하는 정책과 학습하는 정책을 분리한다.
- 행동 정책 : 지속적인 탐험을 하며 데이터를 만들 때 사용하는 정책
- 목표 정책 : 학습하고자하는 정책
Q-러닝의 행동 가치 함수 업데이트 식은 아래와 같다.
$𝑄(𝑠,𝑎) ← 𝑄(𝑠,𝑎) + 𝛼(𝑅_{𝑡+1} + 𝛾max_a𝑄(𝑠’,𝑎’) − 𝑄(𝑠,𝑎))$
Q-러닝은 활성 정책 시간차 제어 방식인 SARSA와 달리, 에이전트가 다음 상태 s’를 알게됐을 때 그 상태에서 가장 큰 큐함수를 현재 큐함수의 업데이트에 이용한다. 따라서 <S,A,R,S’,A’>가 필요했던 SARSA와 달리, <S,A,R,S’> 집합만으로 학습이 가능하다.
모든 s,a의 행동 가치 함수 값을 임의의 수로 초기화. 단, Q(종단,.) = 0
for epi in range(EPISODE):
S 초기화
while epi_end == False:
현 정책에 따라 탐욕적인 A를 선택 : 정책(S) = A
Reward, S' <- 행동 A를 취함
현 정책에 따라 탐욕적인 A'를 반환 : 정책(S') = A'
Q(S) 업데이트
S = S'
다이나믹 프로그래밍 vs 시간차 제어
SARSA는 벨만 기대 방정식을 근사한다. 반대로 Q-러닝은 벨만 최적 방정식을 근사한다. 따라서 다이나믹 프로그래밍과 시간차 제어 방법론을 대응시킨다면 SARSA와 정책 이터레이션을, 가치 이터레이션과 Q-러닝을 대응시킬 수 있다.