4장 강화학습 기초 3: 그리드월드와 큐러닝

MostlyFor·2023년 2월 6일

강화학습

목록 보기

7/12

3장에서 본 dynamic programming은 환경에 대한 모든 정보를 가지고 모든 경우의 수를 계산하기 때문에 시간이 오래 걸린다. 반면 인간의 경우 오목이나 바둑을 둘 때, 모든 경우의 수를 계산하지 않고 일단 해보고 복기를 한다.

강화학습도 마찬가지로 에이전트가 겪은 경험으로부터 가치함수를 업데이트 한다.

예측

환경과의 상호작용을 통해 주어진 정책에 대한 가치함수를 학습하는 것! (정책 평가)

1. 몬테카를로 예측

몬테카를로 근사(Monte - Carlo Approximation)는 '무작위로 무엇인가를 해봐서 그걸 토대로 추측한다' 라는 뜻을 가진다. 예를 들어, 원의 넓이를 구하기 위해 넓이가 1인 종이 위에 반지름이 r인 원을 그려놓고 점을 무작위로 찍어서 들어간 점의 비율을 계산하여 원의 넓이를 구하는 방법이 몬테카를로 근사의 예시이다.

이를 에이전트에 적용하여 가치함수를 추정하는게 몬테카를로 예측이다.
가치함수란 본래 현재 상태에서 얻을 보상의 합의 기댓값이다. 만약 무한에 가까운 에피소드를 샘플링한다면 우리는 가치함수의 참 값에 근접해갈 수 있다.

이때 알아두면 좋을 점은 하나의 에피소드를 통해 출발 상태에 대한 에피소드만 진행되는 것이 아니라 출발 이후에 들린 상태의 에피소드도 진행했다고 생각할 수 있다는 점이다.
예를 들어, 상태 S에서 시작하여 S'을 거쳐서 종료가 된 에피소드는 두 가지 계산, V(S) , V(S')을 모두 계산할 수 있다.
계산은 다음과 같은 식으로 진행해볼 수 있는데, 이때 $V_{n+1}$ 은 n개의 반환값을 통해 평균을 취한 가치함수이다. 대문자는 추정값이라는 것을 의미한다.

V_{n+1} = \frac{1}{n}\sum^n_{i=1}G_i = \frac{1}{n} (G_n+\sum^{n-1}_{i=1}G_i)

V_{n+1} =\frac{1}{n} (G_n+(n-1)\frac{1}{n-1}\sum^{n-1}_{i=1}G_i)

여기서 $\frac{1}{n-1}\sum^{n-1}_{i=1}G_i$ 의 의미는 n-1개의 반환값을 통해 평균을 취한 가치함수 이므로 $V_{n}$ 과 같다 . 따라서 다음과 같이 쓸 수 있다.

V_{n+1} =\frac{1}{n} (G_n+(n-1)V_n)\\ = \frac{1}{n}(G_n + nV_n - V_n) \\ = V_n + \frac{1}{n}(G_n-V_n)

위 식을 살펴보면 n번째 시행에서의 가치함수를 n번째 시행에서의 반환값과 n-1번째 시행에서의 가치함수 값을 통해 바로 계산할 수 있다.

이런 방법을 이동평균이라고 하는데, 머신러닝과 마찬가지로 $\frac{1}{n}$ 을 step size라고 하고, step size에 다른 값을 넣어서 평균의 계산 방식을 조절할 수 있다.

만약 step size에 1을 넣은 경우를 생각해보자.
$V_{n+1} = G_n$ 이 된다. 즉, 이전의 보상과는 관계없이 현재 샘플링된 에피소드의 반환값이 가치함수가 되는 것이다.

만약 step size를 일정한 숫자로 고정하게 되면 과거의 반환값보다 현재 에피소드로부터 얻은 반환값을 중요시한다는 것이다.

원래 step size는 점점 작아지는 값이다. 그래야 각 에피소드마다의 비율이 동일하다는 뜻인데, 만약 일정한 숫자로 고정할 경우 원래 작았어야 할 step size보다 더 커져서 그 때 에피소드의 반환값이 더 크게 작용한다. 그래서 현재를 중요시하게 학습하는 것이다.

만약 환경이 지속적으로 변화한다면 1/n로 평균을 구하는 것보다 일정한 숫자로 고정하여 현재의 비중을 높이는 것이 낫다.

이렇게 달라질 수 있는 step size를 알파로 놓고 쓰는게 일반적이다.

V(s) \leftarrow V(s) + \alpha(G(s) - V(s))

단점

실시간이 아니다.
만약 에피소드의 길이가 무한할 경우 실행할 수가 없다.
그리고 에피소드의 길이가 너무 긴 경우 적합하지 않다.

2. 시간차 예측

사람은 항상 모든 상황에서 예측하고 있다. 이와 마찬가지로 에이전트도 실시간으로 예측과 현실의 차이로 학습할 수 있다.

가치함수의 업데이트는 실시간으로 이뤄지며, 몬테카를로 예측과는 다르게 한 번에 하나의 가치함수만 업데이트 된다.

가치함수의 업데이트는 다음과 같은 방식으로 업데이트 된다.

V(S_t) = V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) -V(S_t))

이때 $\alpha(R_{t+1} + \gamma V(S_{t+1}) -V(S_t))$ 가 업데이트의 크기인데, 이걸 시간차 에러 Temporal-Difference Error 라고 한다.

업데이트의 목표는 $R_{t+1} + \gamma V(S_{t+1})$ 로 예측하고 있는 값을 목표로 삼는다.

다른 상태의 가치함수 예측값을 통해 지금 상태의 가치함수를 예측하는 이러한 방식을 부트스트랩이라고 한다.

몬테카를로 방식보다 더 효율적이고 빠른 시간 안에 참 가치함수에 근접한다고 알려져있다.

단점

몬테카를로 예측보다 초기 가치함수 값에 따라 예측 정화도가 많이 달라진다.

제어

예측한 가치함수를 통해서 정책을 끊임없이 발전시켜서 최적 정책을 학습하는 것

1. 살사 - 시간차 제어

보통 살사부터 강화학습이라고 부른다.

우리가 정책 이터레이션 방법을 사용할 때 현재 policy에 대한 state value를 업데이트 해나가면서 수렴하면 policy improvement를 적용한다.

그러나 정책 평가 과정에서 참 가치함수에 수렴할 때까지 계산하지 않아도 정책 평가와 정책 발전을 한 번씩 번갈아 가면서 실행하면 가치함수가 참 가치함수에 수렴한다.

이러한 정책 이터레이션을 GPI (Generalized Policy Iteration) 이라고 한다.

우리는 이제 환경을 잘 모르는 상황이라고 가정을 하고 생각을 해보자.

환경을 잘 모르는 상황에 policy evaluation을 하기 위해선 prediction을 진행해야 한다. 그 중 시간차 제어를 쓰게 되면, 한 타임 스텝마다 s의 가치 함수만 바뀌므로 s에 대해서만 업데이트를 할 수 있다.

이러한 문제를 가치 이터레이션 방법을 사용하면 해결할 수 있다.

가치 이터레이션에서는 정책 이터레이이션에서와 달리 벨만 최적 방정식을 이용하여 정책을 신경쓰지 않고 오로지 최고 상태로 움직이는 greedy한 방법이었다.

이를 이용하여 시간차 예측과 탐욕 정책이 합쳐진 것을 시간차 제어 Temporal-difference control 또는 SARSA 라고 한다.

기존 GPI 에서는 우리가 환경을 알 것을 전제하고 가치함수를 계산할 수 있었다. 하지만 환경을 잘 모르는 상황에서는 우리는 기댓값을 계산할 수 없다.

하지만 탐욕 정책에서는 큐함수를 보고 판단하므로 이땐 환경의 모델을 몰라도 된다.
물론 이때 Q가 대문자로 쓰인 이유는 추정값이기 때문에 그렇다.

\pi(s) = argmax_{a \in A} Q(s,a)

가치함수에 따라 행동하는게 아닌 큐함수에 따라 행동하기 위해서는 우리는 큐함수를 업데이트 해야한다. 업데이트하는 수식은 다음과 같다.

Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t))

업데이트 하는 식을 자세히 살펴보면 우리에게 필요한 정보는 S,A,R,S',A' 이다.
그래서 SARSA 라고 부른다.

이때 greedy한 정책만 가는게 과연 옳은 것인가? 라는 생각을 해볼 수 있다.

이미 충분히 많은 경험을 한 에이전트의 경우에는 탐욕 정책이 좋은 선택이 될 수도 있지만 아직 초기 에이전트에게 탐욕 정책은 오류가 발생할 수 있다.

극단적으로 2등인 길과 1등인 길이 있는데 2등인 길을 처음에 가게 되면 매번 2등을 greedy 하게 선택하기 때문이다.

이를 방지할 수 있는 방법이 바로 $\epsilon$ -탐욕 정책이다. 다음과 같은 식을 따른다.

\pi(s) = \begin{cases} a^* = argmax_{a \in A} Q(s,a), & 1-\epsilon \\ a\ne a*, & \epsilon \end{cases}

입실론을 계속 유지한다면 충분히 많은 행동을 하여 최적 정책을 찾았음에도 불구하고 계속 입실론만큼 다른 행동을 할 수 있다. 따라서 학습시간에 따라 입실론을 줄여나가는 방법도 있다.

SARSA는 정책 평가를 큐함수를 이용한 시간차 예측으로, 탐욕 정책 발전을 $\epsilon$ - 탐욕 정책으로 변화시킨 알고리즘이다.

2. 큐러닝 - 오프폴리시 제어

SARSA에서는 단점이 있는데, 한 타임스탭마다 action value function을 업데이트 하다가 최적 정책이 아닌 입실론의 확률로 에이전트가 잘못된 action value update를 하게 되고 원래 정답인 길을 가지 않으려는 경향이 나타날 수도 있다.

SARSA는 On-Policy Temporal-Diference Control, 즉 자신이 행동하는 대로 학습하는 시간차 제어다.

이러한 문제를 해결하기 위해 사용하는 것이 바로 Off-Policy Temporal-Difference Control이다.
이를 다른 말로 Q-Leaning이라고 한다.

off - policy의 뜻은 행동하는 정책과 학습하는 정책을 분리하여 학습한다는 것이다.

Q-learning에서는 다음과 같은 업데이트를 따른다.

Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha(R_{t+1}+\gamma max_{a'}Q(S_{t+1},a') -Q(S_t,A_t))

sarsa에서와의 차이점은 다음 상태에서의 a는 포함이 되지 않는다는 것이다.
다음 상태에서 입실론을 주지 않고 바로 가장 가치가 높은 최적 행동을 하는 것이다.

MostlyFor

이전 포스트

3장 강화학습 기초 2: 그리드월드와 다이내믹 프로그래밍

다음 포스트