TD Learning

1. TD Learning

TD Learning(Temporal Difference Learning)은 환경의 상태 전이 확률을 알지 못하는 상황에서 에피소드가 끝날 때까지 기다리지 않고 현재 상태와 다음 상태의 가치 차이를 이용해 상태 가치를 점진적으로 업데이트하는 강화학습 방법입니다. 즉, 현재 상태의 가치 V(s)를 바로 다음 상태 s′의 가치 V(s′)와 받은 보상 r을 이용해 조금씩 수정하는 방식이며, 이때 사용되는 값의 차이를 TD Error라고 합니다. Monte Carlo 방법이 에피소드 종료 후 전체 Return을 사용해 학습하는 것과 달리, TD Learning은 매 스텝마다 즉시 업데이트가 가능하기 때문에 학습 속도가 빠르고 긴 에피소드에서도 효율적으로 사용할 수 있으며, Q-learning이나 SARSA 같은 많은 강화학습 알고리즘의 기반이 되는 방법입니다.

 

 

2. TD Learning이 필요한 이유

강화학습에서는 어떤 상태가 좋은 상태인지 알고 싶습니다. 예를 들어 미로에서 어떤 칸이 출구에 가까운 좋은 칸인지 알고 싶습니다. 그런데 문제는 미래를 정확히 모른다는 것입니다.

• 지금 이 칸이 좋은 칸인지
• 앞으로 어떻게 흘러갈지
• 결국 성공할지 실패할지

그래서 TD Learning은 이렇게 생각합니다.

“지금은 정답을 모르니까,
일단 다음 상태를 참고해서 현재 상태를 조금 수정하자.”

이게 TD Learning의 핵심입니다.

 

 

3. TD Learning의 핵심 아이디어

예를 들어 현재 상태가 A이고, 다음 상태가 B라고 해보겠습니다.

• 지금 상태 A의 가치가 3이라고 생각하고 있었는데
• 실제로 한 번 움직여보니
  • 보상 r = 1을 받고
  • 다음 상태 B의 가치가 5라면

그럼 TD Learning은 이렇게 생각합니다.

“아, A는 내가 생각한 것보다 좀 더 좋은 상태였네.
왜냐하면 바로 보상도 받고, 다음 상태도 꽤 좋으니까.”

그래서 A의 가치를 조금 올립니다. 따라서 현재 추정값과 새로 관찰한 정보의 차이를 이용해 수정하는 것이 TD Learning입니다.

 

4. Monte Carlo와 TD Learning의 가장 큰 차이

Monte Carlo

• 에피소드가 끝난 후 학습
• 최종 결과를 알고 나서 업데이트

TD Learning

• 매 스텝마다 학습
• 끝나기 전에도 계속 업데이트 가능

이 차이 때문에 두 방법의 성격이 완전히 달라집니다.

 

import random
import numpy as np

class GridWorld():
    def __init__(self):
        self.x=0
        self.y=0
    
    def step(self, a):
        # 0번 액션: 왼쪽, 1번 액션: 위, 2번 액션: 오른쪽, 3번 액션: 아래쪽
        if a==0:
            self.move_left()
        elif a==1:
            self.move_up()
        elif a==2:
            self.move_right()
        elif a==3:
            self.move_down()

        reward = -1 # 보상은 항상 -1로 고정
        done = self.is_done()
        return (self.x, self.y), reward, done

    def move_right(self):
        self.y += 1  
        if self.y > 3:
            self.y = 3
      
    def move_left(self):
        self.y -= 1
        if self.y < 0:
            self.y = 0
      
    def move_up(self):
        self.x -= 1
        if self.x < 0:
            self.x = 0
  
    def move_down(self):
        self.x += 1
        if self.x > 3:
            self.x = 3

    def is_done(self):
        if self.x == 3 and self.y == 3:
            return True
        else :
            return False

    def get_state(self):
        return (self.x, self.y)
      
    def reset(self):
        self.x = 0
        self.y = 0
        return (self.x, self.y)

class Agent():
    def __init__(self):
        pass        

    def select_action(self):
        coin = random.random()
        if coin < 0.25:
            action = 0
        elif coin < 0.5:
            action = 1
        elif coin < 0.75:
            action = 2
        else:
            action = 3
        return action


def main():
    #TD
    env = GridWorld()
    agent = Agent()
    data = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    gamma = 1.0
    reward = -1
    alpha = 0.01

    for k in range(50000):
        done = False
        while not done:
            x, y = env.get_state()
            action = agent.select_action()
            (x_prime, y_prime), reward, done = env.step(action)
            x_prime, y_prime = env.get_state()
            data[x][y] = data[x][y] + alpha*(reward+gamma*data[x_prime][y_prime]-data[x][y])
        env.reset()
            
    for row in data:
        print(row)

if __name__ == '__main__':
    main()