단단한 강화학습 Chapter6_시간차 학습(Temporal-Difference Learning)

시간차 학습(Temporal Difference Learning, TD Learning)은 강화학습에서 가장 핵심이 되는 개념 중 하나로, 몬테카를로(Monte Carlo) 방법과 동적 계획법(Dynamic Programming, DP)을 결합한 알고리즘입니다.

 

TD 방법은 몬테카를로 방법처럼 환경의 동역학 모델 없이 데이터 샘플들로부터 직접 학습을 수행할 수 있습니다. 또한, 종단 상태(Terminal State)에 도달하지 않아도 다른 학습된 추정치를 기반으로 추정치를 업데이트할 수 있습니다(이를 부트스트랩이라고 합니다).

 

 

정책 평가(Policy Evaluation)와 정책 개선(Policy Improvement) 과정을 번갈아 진행하는 제어(Control) 문제에 대해서는 MC, DP, TD 모두 일반화된 정책 개선(Generalized Policy Improvement, GPI) 과정을 조금 변형해서 사용하므로 큰 차이가 없습니다.

책 에서는 주어진 정책에 대해 가치함수를 수렴시키는 예측(Prediction, 또는 Evaluation) 문제에 초점을 맞춰 설명하고 있습니다.

 

 

 

 

◆목차

◎ TD 예측(TD Prediction (or Prediction))

◎ TD 예측방법의 좋은점 (Advantages of TD Prediction Methods)

◎ TD(0)의 최적성(Optimality of TD)

◎ SARSA : 활성정책 TD 제어(Sarsa: On-Policy TD Control)

◎ Q-Learning: 비활성 정책 TD 제어(Q-Learning: Off-Policy TD COntrol)

◎ 기댓값 살사 (Expected Sarsa)

 

 

 

 

 

 

◎ TD 예측(TD Evaluation (or Prediction))

 

먼저 DP와 MC에 대해 간략하게 설명하겠습니다.

 

DP와 MC에서의 Value Update과정을 그림으로 표현하면 아래와 같습니다.

 

 

DP는 환경 모델에 관한 모든 정보를 알고 있기 때문에, 여러 Sample이 필요하지 않고 Evaluation 과정만 진행하면 됩니다. 반면, MC는 환경을 전혀 알 수 없다고 가정하고, 추정을 통해 파악하기 때문에 많은 Episode와 Sample이 필요합니다.

 

 

 

MC에서는
Gt 값이 해당 시점으로부터 에피소드가 끝날 때까지의 미래 보상의 합계를 나타내는 값으로, Episode가 완전히 종료된 후에야 파악할 수 있습니다. 따라서, Value Update 과정은 에피소드가 종료된 후에 도달했던 State에 대해 일괄적으로 이루어집니다.

 

반면, DP는

환경 모델에 대한 모든 정보를 알고 있기 때문에, 굳이 끝까지 에이전트가 도달하지 않더라도 Value를 Update할 수 있습니다. 이러한 방식을 부트스트랩 방식(Bootstrapping Method)이라고 합니다.

 

 

 

 

TD는 Model Based DP방식과 Model Free MC 방식을 합친 Value Update과정입니다.

아래 그림을 통해 보도록 하겠습니다.

TD 방식은 MC처럼 Model Free 방식이면서 DP에서처럼 Bootstrap 방식으로 가치가 업데이트 되는 것이라 할 수 있습니다. 

MC의 아래 수식에서

에피소드가 완전히 종료된 후에야 파악할 수 있었던 Gt를 아래와 같이 변환해줌으로서

에피소드가 끝날때 까지가 아닌, 한스텝만 더 나아감으로서 St값을 파악할 수 있도록 되어있습니다.

여기서, Rt+1은 한스텝을 더 나아가 관측된 값이고, V(St+1)은 이전 State에 저장되어있는 Value값입니다.

(나중에 정리하겠지만, 여기서 몇스텝까지 더 나아가는지에 따라 TD-n step 이라 불립니다)

 

그리고 이때 고정된 시간간격 α (Learning Rate)에 대한 TD-Error는 아래와 같이 정의되며,

이 형태는 강화학습 전반에 걸쳐서 다양한 형태로 제시됩니다.

 

 

<Pseudo-Code>

 

 

 

◎ TD 예측방법의 좋은점 (Advantages of TD Prediction Methods)

 

책에서 이야기하는 TD 예측의 좋은점은 아래와같이 정리할 수 있습니다.

 

1. 환경에 대한 모델 불필요:
TD 방법은 DP 방법과 달리 환경의 보상과 다음 상태 확률 분포에 대한 모델이 필요하지 않습니다.

 

2. 온라인(Online) 방식으로 구현가능 :

앞서 언급한 것처럼, TD 방법은 에피소드의 끝까지 기다릴 필요가 없으므로, MC와 달리 온라인 방식의 점진적(Incremental) 구현이 가능합니다
긴 Episode를 요구하는 일부 Application에서는 모든 학습을 Terminal State까지 지연시키는 것이 너무 느릴 수 있으며,
Continous한 타입의 Application의 경우(Episodic Task가 아닌경우), Episode라는 개념이 없을 수도 있습니다.

TD 방법은 이러한 문제에서 자유롭습니다.

 

3. 수렴의 타당성:
TD 방법이 정확한 답에 수렴한다는 사실은 증명되어 있습니다.
고정된 정책 π에 대해 TD(0)는 충분히 작은 Constant Step-Size 매개 변수에 대해 평균적으로 vπ로 수렴하며, 스텝 사이즈 매개 변수가 일반적인 확률론적 근사 조건(Section 2.7)에 따라 감소하면 확률 1로 수렴합니다.

4. 빠른 학습:
TD와 MC 모두 정확한 예측에 점진적으로 수렴하므로, 어떤 방법이 더 빠르게 수렴하는지에 대한 질문이 자연스럽게 제기됩니다. 현재로서는 수학적으로 어떤 방법이 다른 방법보다 빠르게 수렴한다는 것을 증명할 수 없지만, 많은 실제 상황에서 TD 방법이 확률적인 작업에서 Constant-α Monte Carlo 방법보다 일반적으로 더 빠르게 수렴하는 것으로 나타났습니다.

 

 

 

◎ TD(0)의 최적성(Optimality of TD)

만약 한정된 경험이 가능하다고 가정하면, 예를 들어 10개의 에피소드나 100개의 타임 스텝으로 제한된다고 생각해봅시다.

이런 경우, 증분 학습 방법에 대한 일반적인 접근법은 방법이 답에 수렴할 때까지 경험을 반복적으로 제공하는 것입니다.

 

근사치 값 함수 V가 주어진 상태에서, Terminal State에 도달하기전 방문된 시간 스텝 t에서

α * (Rt+1 + γ * V(St+1) - V(St))를 계산합니다.

 

 

Batch Update는 모든 Time Step에 대해서 위의 α * (Rt+1 + γ * V(St+1) - V(St))를 계산하고, 누적한 다음 Batch Size 크기만큼의 Sample의 α * (Rt+1 + γ * V(St+1) - V(St)) 합을 한번에 업데이트 하는 방식을 말하며, 이를 여러번 반복하여 값을 수렴시킵니다.

 

여기서 핵심은, 배치 업데이트에서는 과거에 사용된 데이터가 재사용된다는 점입니다.

전체 학습 데이터를 여러 번 반복하여 처리하면서 값 함수를 수렴시키는 과정에서, 이전에 사용된 경험 데이터를 계속 활용합니다. 이 방식은 한정된 양의 데이터를 가지고 있을 때 효과적인 학습 방법으로 사용됩니다.

 

배치 업데이트를 사용하면, TD(0)는 Step-Size 매개변수 α에 관계없이 단일 답변으로 Deterministic하게 수렴합니다.

단, α가 충분히 작게 선택되어야 합니다. Constant-α MC 방법도 동일한 조건에서 Deterministic하게 수렴하지만, 다른 답변에 수렴합니다. 

(책에서는 이 두 가지 방법 간의 차이를 이해하기위해 예제를 통해 설명하고있으나, 이부분은 Skip하도록 하겠습니다)

 

 

 

+ Batch Update 방식에서,. α * (Rt+1 + γ * V(St+1) - V(St))를 여러 샘플의 합 값을 통해 업데이트 한다고 하였는데, 이때 Batch Sample은 무슨기준으로 정하나? 에대한 궁금증이 자연스럽게 따라옵니다.

 

일반적으로 샘플은 무작위로 선택되거나, 에이전트가 경험한 에피소드와 시간 스텝에 따라 순차적으로 선택됩니다. 무작위 샘플링을 사용하면 에이전트가 다양한 상황에서 학습할 수 있어서 종종 더 좋은 결과를 얻을 수 있습니다. 그러나 어떤 기준으로 샘플을 선택하느냐에 따라 학습 속도와 결과가 달라질 수 있으므로, 특정 문제에 적합한 샘플 선택 전략을 찾는 것이 중요합니다.

 

 

 

◎ SARSA : 활성정책 TD 제어(Sarsa: On-Policy TD Control)

지금까지 Policy Evaluatiion을 다뤘다면, 이제부터는 Control 문제로 이야기를 옮겨보도록 하겠습니다.

 

Control 문제에서 늘 그래왔듯, Generalized Policy Iteration(GPI)과정을 따르되, Evaluation 문제에는 TD 방법이 사용 되고, MC Evaluation에서처럼, Exploration과 Explotation 사이의 균형을 잘 바로잡아야하는 고려사항이 생깁니다.

 

MC에서 Off-Policy와 On-Policy 접근법을 다뤘던 것처럼,

TD 에서도 마찬가지로 구분지을 수 있는데

SARSA는 그중 On-Policy에 해당하는 접근법입니다.

 

 

앞선 내용들과 달라지는 내용중 첫번째는 State Value가 아닌, Action Value를 고려한다는 점입니다.

특히 On-Policy정책을 적용할 경우에는 현재의 Policy π와 모든 State-Action 쌍에대한 Qπ(s,a)를 추정해야합니다.

 

 

에피소드가 아래 그림과 같이 진행될 때,

SARSA 알고리즘의 Action Value Update 수식은 아래와 같이 정리될 수 있습니다.

이러한 Update는 Terminal State가 아닌 모든 상태 St로부터 State Transition이 이루어 질 때마다 해당 Transition 이후에 행해집니다. 만약 St+1이 Terminal State라면, Q(St+1, At+1)은 0으로 정의됩니다.

 

SARSA 알고리즘의 이름은 이러한 Update 규칙을 구성하는 5개의 Event

(St , At , Rt , St+1 , At+1)의 알파벳 기호로부터 차용되었습니다.

 

 

 

이러한 Evaluation 방법을 기반으로 On-Policy Control을 설계하는 것은 간단합니다.

행동정책 π에 대해서 Qπ(s,a)를 추정하고, 그와 동시에 π가 Qπ에 대해서 탐욕적이 되도록 π를 변화시키기만 하면 됩니다.

 

 

 

◎ Q-Learning: 비활성 정책 TD 제어(Q-Learning: Off-Policy TD COntrol)

Q-Learning은 TD Control의 Off-Policy 알고리즘으로, 아래와 같은 수식에 의해 정의됩니다.

그런데, Off Policy MC 방식에서 살펴봤던 Importance Sampling이 보이지 않습니다.

 

https://roboharco12.tistory.com/59

단단한 강화학습 Chapter5_몬테 카를로 방법 (Monte Carlo Methods)

원래대로라면, Importance Sampling기법을 통해 Behavior Policy로 Target Policy에 대한 Value Update를 수행할 수 있도록 해줘야 할텐데, 관련 텀이 전혀 없는데요,

 

우선 Q-Learning이 왜 Off Policy 방식이 되는 이유부터 정리해보도록 하겠습니다.

 

On-Policy 방법은 현재 Policy를 평가하고 개선하는 동안 동일한 정책을 따르는 방법입니다.

위 섹션에서 다룬 SARSA는 On-Policy TD 학습 방법입니다.

반면에 Off-Policy 방법은 다른 Policy를 따르는 동안 현재 정책을 평가하고 개선하는 방법입니다.

 

아래의 Q-Learning Update식에서,

Q(s, a) ← Q(s, a) + α(R + γ * max(Q(s', a')) - Q(s, a))

max(Q(s', a'))는 다음 상태 s'에서 모든 행동 a'에 대한 Q-value 중 최대값을 선택하는 것입니다.

 

여기서 Q-Learning이 Off-Policy가 되는 이유는,

Q-Learning에서 사용되는 두가지 정책으로 나눠보면 쉽게 이해할 수 있습니다.

 

1. Behavior Policy: 에이전트가 "실제로 행동을 선택할 때 사용"되는 정책.

일반적으로 입실론-그리디와 같은 탐험적인 정책을 사용합니다. 이를 통해 에이전트가 다양한 상태와 행동을 경험하게 됩니다.

2. Target Policy: 이 정책은 에이전트가 "학습하는데 사용하는 정책", 최적의 정책을 찾기 위해 사용됨.

이때 탐욕적인 정책을 사용하여 Q(s', a') 중에서 가장 큰 값을 선택합니다.

 

에이전트가 실제 움직이는건 Behavior Policy를 따르지만, 학습시 사용되는 즉, Value Update에 사용되는 Policy는 Greedy한 정책만을 따른다는 것입니다.

 

 

MC에서 사용했던 Importance Sampling방식과는 사뭇 다른 Off-Policy 인데,

MC의 경우, Episode가 Terminal state에 도달해야만 Gt값을 정확히 알수가 있기때문에,
Behavior Policy를 따라 Action을 선택하는 동시에 다른 Target Policy (Greedy)를 통해 Value Update하는 것이 불가능하기 때문입니다.

 

TD에서는 DP에서처럼 Terminal State에 도달하지 않고도 Value를 Update하는 Bootstrapping Method이기 때문에,

Importance Sampling을 사용하지 않고도 Off-Policy 학습이 가능한 것입니다.

 

 

 

◎ 기댓값 살사 (Expected Sarsa)

기대값 살사(Expected Sarsa)는 강화학습의 여러 알고리즘 중 하나로, 살사(Sarsa)와 Q-러닝(Q-learning) 사이에 위치합니다. 기대값 살사는 살사 알고리즘과 비슷한 On-policy 학습 방법을 사용하면서도, Q-러닝처럼 다음 상태의 Q-value의 기댓값을 계산하여 업데이트를 수행합니다.

 

즉, 현재의 Policy에 따라 Action도 선택하고, Value도 Update하지만, MC 방식처럼 Episode가 끝날때까지 기다리지 않고, 다음 상태의 Q 값을 통해 가치를 업데이트 하는것입니다.

 

기대값 살사의 업데이트 공식은 아래와 같습니다.

여기서 E[Q(St+1, At+1)]는 다음 상태 St+1에서 가능한 모든 행동 At+1에 대한 Q-value의 기댓값입니다. 이 기댓값은 현재 정책에 따라 가중치가 적용된 Q-value의 합으로 계산됩니다. 이렇게 하면, 기대값 살사는 현재 정책을 따르면서도 다음 상태의 Q-value를 사용하여 가치 업데이트를 효율적으로 수행할 수 있습니다.

 

기대값 살사는 다음과같은 장점을 가집니다

 

1. 기대값 살사는 SARSA와 Q-Learning 사이의 Trade-Off를 제공합니다.

이로 인해, 특정 상황에 대해 기대값 살사가 더 적합한 해결책이 될 수 있습니다.

 

2. 기대값 살사는 상황에 따라 SARSA와 Q-Learning보다 성능이 더 좋을 수 있습니다.
기대값 살사는 SARSA보다 더 낮은 분산을 가지며, Q-Learning보다 작은 최적화 오버슈트(optimization overshoot)를 보입니다.

 

(자세한 내용은 책의 예제에서 다루고있지만 이부분은 Skip하였습니다.)

 

 

지금까지 다뤘던 Tabular 파트는

이번 Chapter6를 끝으로 마무리짓는 것으로 하고,

 

다음 포스팅에서는 
Approximate Solution Methods 파트의

Chapter9이후 내용부터 정리해보도록 하겠습니다.