[강화 학습] Monte Carlo(MC) & Temporal Difference(TD)

목표는 Value Function 추정

강화학습의 목표는 "환경과 상호작용하면서, 누적 보상을 최대화하는 정책을 찾는 것" 입니다. 이 목표를 달성하기 위해서 Agent는 매 순간 "지금 상태에서 어떤 행동이 장기적으로 가장 이득이 되는 행동일까?" 를 판단하여야 합니다.물론 지금 당장 눈앞의 보상만 보고 판단하면 안되며, 미래에 어떤 일이 일어날지 생각하며 행동해야 합니다.

 

이와 같이 최적의 행동을 하기 위해 등장한 것이 바로 Value Function 입니다.

 

Value Function은 크게 "State Value Function", "Action Value Function" 두 가지 종류가 있습니다.

 

1. State Value Function

: 상태 $s$에 있을 때, 정책 $\pi$를 따를 경우 앞으로 받을 보상의 총합의 기대값

 

$$
V^\pi(s) = \mathbb{E}_\pi [G_t \mid s_t = s]
$$

 

2. Action Value Function 

: 상태 $s$에서 행동 $a$를 했을 때, 앞으로 받을 보상의 기대값

 

$$
Q^\pi(s, a) = \mathbb{E}_\pi [G_t \mid s_t = s, a_t = a]
$$

 

 

그렇다면 이와 같은 Value Function 은 왜 필요한걸까요?

 

 

1. Action 선택을 위한 기준점

Agent는 이득이 높은 행동을 골라야 하며, 각 행동의 장기적 이득을 추정하는 Value function이 곧 "판단 기준" 이 됩니다. 

 

예를 들어,

오른쪽으로 가면 당장은 0점이지만, 3턴 뒤에 보상을 받을 수 있음.
아래로 가면 바로 1점을 얻지만, 더 이상 보상이 없음.

 

이럴 때, Agent가 판단할 수 있는 기준이 Value function이 됩니다. 

 

 

2. 정책을 평가 및 개선

강화학습을 할 때는 보통 다음 순서를 반복합니다. 

• 정책 평가: 현재 정책이 얼마나 좋은 지 평가
• 정책 개선: 가치가 높은 행동을 더 선택하도록 정책을 수정

여기서 정책을 평가할 때 Value function을 사용하게 됩니다.

 

Value function을 구하기 위해서는 환경의 모든 상태의 전이 확률, 보상 함수, 정책을 알아야 구할 수 있지만, 현실에서는 환경 모델이 없기 때문에 직접 계산이 불가능합니다. 그래서 샘플링을 통해 가치 함수를 추정해야 합니다. 이런 샘플링을 통해 추정하는 방식이 크게 "Monte Calro" 방식과 "Temporal Difference" 방식이 있습니다. 

 

 

 

 

 

 

Monte Calro (MC)

MC는 확률적 기대값을 샘플 평균으로 근사하는 방법입니다.

 

$$ \mathbb{E}[f(X)] = \int f(x) p(x) \, dx \approx \frac{1}{N} \sum_{i=1}^{N} f(x_i) $$

 

여기서 추정하고 싶은 Action Value Function은 다음과 같습니다.

 

$$ Q^\pi(s_t, a_t) = \int_{s_{t+1}:a_\infty} G_t \cdot P(s_{t+1}:a_\infty \mid s_t, a_t) \, d_{s_{t+1}:a_\infty} $$

 

이를 샘플링 기반으로 근사하는 것을 다음과 같이 나타낼 수 있습니다.

 

$$ Q^\pi(s_t, a_t) \approx \frac{1}{N} \sum_{i=1}^{N} G_t^{(i)} $$

 

즉, $s_t, a_t$에서 시작되는 여러 에피소드에서의 실제 리턴 $G_{t}^{(i)}$를 평균해서 $Q$값을 추정하는 것이죠. 

 

하지만 이런 MC 방식은 에피소드가 끝날 때까지 매번 기다려야 합니다. Reward를 찾을 때까지 현재 상태에서 random하게 행동을 취하여 얻은 대량의 sample을 통해 기대값을 추출하는 것이기 때문에, 효율이 떨어진다는 단점이 있죠.

 

 

 

 

 

 

Temporal Difference (TD)

MC는 전체 에피소드가 끝난 후 업데이트되지만, TD 방식은 한 스텝 이후에 바로 Q를 업데이트할 수 있기 때문에 더 효율적인 방식이라 볼 수 있습니다. 

 

우선 Action Value function의 기대값은 다음과 같이 정의됩니다. 

 

$$ Q^\pi(s_t, a_t) = \int_{s_{t+1}, a_{t+1}} \left( R_t + \gamma Q^\pi(s_{t+1}, a_{t+1}) \right) \cdot P(s_{t+1} \mid s_t, a_t) P(a_{t+1} \mid s_{t+1}) \, ds_{t+1} da_{t+1} $$

 

이를 샘플 기반으로 근사하는 것을 다음과 같이 수식으로 나타낼 수 있습니다. 

 

$$ Q^\pi(s_t, a_t) \approx \frac{1}{N} \sum_{i=1}^N \left( R_t^{(i)} + \gamma Q(s_{t+1}^{(i)}, a_{t+1}^{(i)}) \right) $$

 

여기서 $R_t^{(i)}$ 의 경우 같은 행동을 취하더라도 다른 상황에 직면할 수 있기 때문에 샘플링을 해주어야 합니다. 바둑을 두는 행위라고 생각했을 때, 같은 좌표값에 돌을 두더라도 상대가 어디에 두느냐에 따라 상황은 달라지는 것을 생각하면 될 것 같습니다. 

 

또한 MC 방법의 경우 $G_t = R_t + \gamma R_{t+1} + r^{2}R_{t+2} + \cdots$ 를 매 step별로 샘플링해야하기 때문에 최종 target에 도달해야만 샘플링이 가능했습니다. 하지만 TD의 경우 $ (t+1) $ 상태에서의 샘플링만으로 끝나기에 굳이 target까지 도달하지 않아도 되기 때문에 더 효율적이라 할 수 있습니다. 

 

앞서 정의하였던 평균 TD-target을 $\bar{Q}_N$ 를 다음과 같이 전개할 수 있습니다. 

 

$$ \bar{Q}_N = \frac{1}{N} \sum_{i=1}^{N} \left( R_t^{(i)} + \gamma Q(s_{t+1}^{(i)}, a_{t+1}^{(i)}) \right) $$

$$ = \frac{1}{N} \left( \bar{Q}_{N-1} \cdot (N - 1) + R_t^{(N)} + \gamma Q(s_{t+1}^{(N)}, a_{t+1}^{(N)}) \right) $$

 

위 식에서 $ \bar{Q}_{N-1} $은 총 N번만큼의 샘플링 중 N-1 번의 샘플링을 따로 분리한 것입니다. N-1만큼의 샘플링과 N번째 샘플링으로 구분한 것이죠.

 

$$= \bar{Q}_{N-1} + \frac{1}{N} \left( R_t^{(N)} + \gamma Q(s_{t+1}^{(N)}, a_{t+1}^{(N)}) - \bar{Q}_{N-1} \right)$$

 

최종적으로 위와 같이 전개할 수 있습니다. 위 식을 보면, 현재 시점인 $(N)$과 과거 시점인 $(N-1)$과의 차이를 이용한 것을 확인할 수 있으며, 이런 이유로 Temporal Difference (TD) 방식이라 불리는 것입니다. 

 

위 식에서 $ \frac{1}{N} $ 을 $\alpha$로 치환하면 다음과 같이 나타낼 수 있습니다. 

 

$$\bar{Q}_N = (1 - \alpha) \bar{Q}_{N-1} + \alpha \left( R_t^{(N)} + \gamma Q(s_{t+1}^{(N)}, a_{t+1}^{(N)}) \right)$$