Ch09. Temporal Difference Learning

Monte Carlo Method에 이어, Temporal Difference Learning이라는 강화 학습 방법을 살펴보자.

 

https://jjuke-brain.tistory.com/79?category=957313 

Ch08. Monte Carlo Methods (2)

 

 

목차

 

 

 

 

1. Temporal Difference Learning

 

이전 포스팅까지 MDP(Markov Decision Process) 문제를 해결하기 위한 여러 방법론을 살펴보았다.

가장 최근 내용인 Monte Carlo Method는 dynamic programming과 달리 모델의 dynamics를 모르는 경우에 학습을 시킬 수 있는 방법이었다.

 

하지만 Monte Carlo 방법 또한 'episodic task'여야 한다는 단점이 있다. 각 에피소드에서 샘플을 추출해야 할 필요가 있기 때문이다.

일반적인 강화 학습 상황에서는 한 에피소드가 매우 길거나, 심지어 에피소드가 없는 경우가 많다.

이때 사용 가능한 학습 알고리즘 중 하나가 바로 'Temporal Difference Learning'이다.

 

TD Learning(Temporal Difference Learning)은 model-free learning, 즉 모델에 대한 정보(dynamics)가 없어도 학습할 수 있으며, 에피소드 하나가 끝날 때까지 기다릴 필요가 없다(non-episodic task에도 적용 가능).

 

우선, TD Learning은 Monte Carlo의 아이디어와 Dynamic Programming의 아이디어를 함께 사용한다.

• Monte Carlo 방법의 idea : 환경에 대한 dynamics 없이 raw experience에서 직접적으로 학습이 가능하다.
• Dynamic Programming 방법의 idea : episode 끝까지 기다리지 않고, 학습된 추정값으로 추정값을 update할 수 있다.
• Bootstrapping : 강화 학습, 특히 TD Learning에서의 bootstrapping이란, 이전 추정값으로 현재 추정값을 근사하는 방법을 말한다. (Decision Tree, Computer Science에서의 Bootstrapping이 조금씩 의미가 다름에 유의!)

 

보통 policy evaluation과 prediction을 시작할 때, 주어진 policy \(\pi\)에 대한 value function \(v_\pi\)를 추정하는 문제를 해결해야 한다.

즉, optimal policy를 찾는 'control'문제에서는 DP, TD, MC 방법 모두 GPI(Generalized Policy Iteration, policy eval → policy improvement 과정을 반복하는 것) 알고리즘을 사용한다.

따라서 각각 방법의 차이는 'prediction' 문제 해결 과정에서 나타난다.

 

TD 학습 방법은 어떤 방식으로 Agent를 학습시키는지 알아보자.

 

 

 

1) Incremental Implementation

 

Incremental Implementation이란, 코딩에서 메모리를 효율적으로 활용하기 위한 방식이다.

 

일반적으로 평균을 계산할 때는 다음과 같은 식을 사용할 것이다.

$$ Q_n = \frac{R_1 + R_2 + \cdots + R_{n-1}}{n-1} $$

 

하지만 위와 같은 방식은 \(R_1, R_2, \cdots, R_{n-1} \) 등 모든 값을 메모리에 저장해야 하므로 비효율적이다.

n, 즉 값의 개수가 늘어날 때마다 memory도, 계산량도 계속해서 증가해야하기 때문이다.

 

따라서 Incremental Implementation을 통해 다음과 같이 값이 하나씩 추가될 때마다 평균을 간단히 계산해줄 수 있다.

 

\(\begin{align*} Q_{n+1} &= \frac{1}{n} \overset{n}{\underset{i=1}{\sum}} R_i \\ &= \frac{1}{n}(R_n + \overset{n-1}{\underset{i=1}{\sum}} R_i) \\ &= \frac{1}{n}(R_n + (n-1) \frac{1}{n-1} \overset{n-1}{\underset{i=1}{\sum}} R_i) \\ &= \frac{1}{n}(R_n +(n-1) Q_n) \\ &= \frac{1}{n} (R_n + nQ_n - Q_n) \\ &= Q_n + \frac{1}{n} [R_n - Q_n] \end{align*} \)

 

이와 같이 계산하면, \(Q_n, n\) 두 변수에 대한 메모리만 할당하면 되므로 데이터 개수에 상관없이 계산량(메모리 용량)이 일정하다.

 

 

 

 

2) TD Prediction

 

고정된 policy \(\pi\)를 따르는 experience가 주어졌을 때, TD와 MC 모두 nonterimnal state \(S_t\)에 대한 \(v_\pi\)값을 통해 \(V\)값을 추정한다.

 

이때, Monte Carlo method는 총 Return인 \(G_t\)를 구해야 하므로, 한 에피소드가 끝날 때까지 기다려야 한다.

\(V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)] \)

• \(G_t\) : time step \(t\)의 actual return을 의미한다.
• \(\alpha\) : learning rate의 개념으로, actual return과 이전 step의 \(V\)값의 차이를 말한다. 즉 에러(\(G_t - V(S_t)\)) 개념을 얼마나 반영해줄 것인지를 정해준다.

 

위와 같은 방법을 'constant-\(\alpha\) MC'라 부른다.

이때 \(G_t\)를 안다는 것은 결국 한 에피소드의 Return을 구한다는 것이므로, 에피소드가 끝나야 계산이 가능하다.

 

하지만 TD 방법은 에피소드의 끝이 아닌, 다음 몇 번의 time step까지만 결과를 얻으면 계산이 가능하다.

간단히 TD(0) (또는 one-step TD)를 살펴보자. 이는 바로 다음 time step 하나만 가지고 계산을 진행하는 방법이다.

\(V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] \)

• \(R_{t+1} \) : \(S_t\)에서 \(S_{t+1}\)로 갈 때의 reward
• \(V_(S_{t+1}) \) : State \(S_{t+1}\)에서의 value
• \(G_t\) 대신 '\(R_{t+1} + \gamma V(S_{t+1}) \)'를 사용 (return 값 대체)

 

위 과정을 통해 \(V(S_t)\)를 incremental하게 update한다.

이는 곧 추정값을 통해 추정을 진행하는 것이므로 bootrstrapping 개념으로 볼 수 있다.

 

	Monte Carlo Prediction	TD Prediction
Prediction 식	\(V(S_t) \leftarrow \) \( V(S_t) + \alpha [G_t - V(S_t)] \)	\(V(S_t) \leftarrow \) \( V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] \)
Update할 Target	\(G_t\)	\(R_{t+1} + \gamma V(S_{t+1})\)

 

또한 다음 time step 하나만 보기 보다, 일반적으로 여러 개의 time step을 통해 update를 진행하는데, 이를 TD(\(\lambda\)) 또는 n-step TD method라 한다. (총 n개, \(\lambda - 1\)개의 time step을 고려한다.)

 

learning rate \(\alpha\))는 0에서 1사이의 값으로, 모델 설계자가 지정해주는 hyperparameter이다. 높으면 발산, 낮으면 episode 하나를 진행하는 데 걸리는 시간이 오래 걸리게 된다.

TD error (\delta_t\))는 \(R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\)로, actual value와 predicted value의 차이를 말한다. 이 에러를 최소화하는 것이 바로 value function이 수렴하는 것을 의미한다.

 

 

 

 

3) Advantages of TD Prediction

 

TD Prediction은 Bootstrapping, 즉 추정치를 통해 새로운 값을 추정함으로써 에피소드 내 전체의 time step이 아닌, 다음 몇몇의 time step만 경험하면 학습을 진행할 수 있게 된다.

또한 다음 state의 transition probability 등의 모델 정보가 필요하지 않다.

 

이러한 방식을 통해 정답 값으로 수렴한다고 수학적으로 증명이 되어있다. 즉, TD(0) 과정은 \(v_\pi\)로 수렴함이 증명되어 있다.

 

 

 

 

 

2. On-policy and Off-policy for TD Control

 

TD Prediction에 대해 살펴보았으니, Control로 넘어가보자. 

앞서 Monte Carlo, Dynamic Programming, Temporal Difference 세 방법 모두 GPI 방법으로 Control 문제를 해결한다고 하였다.

 

Monte Carlo 방법에서 Control 문제 해결 시 exploration과 exploitation의 trade-off 관계를 직면했을 때 다음과 같은 두 가지 방법론을 제시했었다.

• SARSA (On-policy)
• Q-learning (Off-policy)

 

이와 비슷한 맥락으로 TD Control에서 On-policy를 어떻게 진행하는지 알아보자.

 

 

 

 

1) SARSA: On-policy TD Control

 

On-policy는 policy evaluation은 TD 방법으로, policy improvement 과정은 \(epsilon\)-greedy policy로 진행한다.

 

앞서 Prediction의 식에서 state-value function 대신 action-value function (Q Function)을 사용하여 \(q_\pi (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)] \)

 

nonterminal state \(S_t\)에서 transition이 일어날 때마다 위 식으로 update되며, 만약 \(S_{t+1}\)이 terminal state라면 \(Q(S_{t+1}, A_{t+1})\) 값은 0이 된다.

위 식은 \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\)의 과정으로, 하나의 time step만 고려하는 경우를 의미하며, 구체적으로 다음과 같은 과정을 거친다.

1. step size \(\alpha\), small value \(\epsilon\) 정함
2. terminal state가 아닌 \(s, a\)를 랜덤으로 골라 \(Q(s, a)\) 초기화
3. 각 에피소드에 대한 Loop
   1. \(S\) 초기화
   2. \(\epsilon\)-greedy policy로 \(Q\)로부터 \(A, S\)를 고름
   3. episode 내부에서 각 step에 대한 Loop
      1. \(A\)로 \(R, S'\) 얻음
      2. \(\epsilon\)-greedy policy로 \(Q\)로부터 \(A', S'\) 고름
      3. 위 식에 따라 \(Q\) update
      4. \(S \leftarrow S'\); \(A \leftarrow A'\);
      5. until \(S\) is terminal state

 

target policy와 behaviour policy가 \(\pi\)로 동일하므로, on-policy 방법으로 볼 수 있다.

 

 

 

 

2) Q-learning: Off-policy TD Control

 

이어서 Off-policy는 어떤 과정을 거쳐 학습이 진행되는지 알아보자.

 

앞서 MC Control에서와 마찬가지로, Off-policy Control은 target policy와 behaviour policy를 따로 둔다.

모든 과정이 똑같지만, behavior policy는 그대로 \(epsilon\)-greedy policy를 사용하고, \(Q\)값을 update할 때에는 단순히 maximum 값을 사용하는 target policy를 사용한다.

 

Q function을 update하는 식은 다음과 같다.

\( Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha[R_{t+1} + \gamma \underset{a}{\max} Q(S_{t+1}, a) - Q(S_t, A_t)] \)

 

식에서도 알 수 있듯이, target policy에서는 behaviour policy와 달리 \(epsilon\)-greedy policy를 따르지 않는다.

 

구체적인 과정은 다음과 같다.

1. step size \(\alpha\), small value \(\epsilon\) 정함
2. terminal state가 아닌 \(s, a\)를 랜덤으로 골라 \(Q(s, a)\) 초기화
3. 각 에피소드에 대한 Loop
   1. \(S\) 초기화
   2. \(\epsilon\)-greedy policy로 \(Q\)로부터 \(A, S\)를 고름 (behavior policy)
   3. \(A\)로 \(R, S'\) 얻음
   4. 위 식에 따라 \(Q\) update (target policy)
   5. \(S \leftarrow S'\)
   6. until \(S\) is terminal state