[RL] n-step TD 구현하기

이 포스팅은 학교수업과 노승은 저자의 "바닥부터 배우는 강화 학습"을 바탕으로 정리하였고

 

 

저자의 책에 나오는 TD 예제에서 n-step TD를 구현해보았다.

---

소스코드

class GridWorld:
    def __init__(self):
        self.x = 0
        self.y = 0

    def step(self, a):
        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
        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

 

일단 GridWorld와 Agent에 대한 소스코드는 책에 TD 예제에서 나오는 것과 동일하다.

 

내가 바꿔줘야할 건 main에서 어떻게 동작할 것인지이다.

def main():
    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
    n = 6

    for _ in range(50000):
        env.reset()
        state = env.get_state()
        states = [state]
        rewards = []

        while True:
            action = agent.select_action()
            next_state, reward, done = env.step(action)

            states.append(next_state)
            rewards.append(reward)

            # n번 움직이고 밸류 업데이트, n+1인 이유는 그 다음 위치를 예측하기 위함
            if len(states) > n + 1 or done:
                if done:
                    G = 0
                else:
                    G = data[next_state[0]][next_state[1]] 
                for i in range(len(rewards) - 1, -1, -1):
                    G = rewards[i] + gamma * G  # 마지막 부터 누적합을 해야 감마가 지수곱 적용
                    if i < len(states) - 1:  # 마지막 상태 제외
                        # n+1스텝(액션)을 추가 검사하여 마지막 에피소드인지 확인
                        x, y = states[i]
                        data[x][y] += alpha * (G - data[x][y])  # data = V_t

                states = states[-1:]
                # 마지막 states 원소, 마지막 원소는 실제 이동한 거리의 마지막 기억값
                rewards = []

            if done:
                break

    # 최종 상태 가치 출력
    for row in data:
        print(row)

 

주석이 형편없어 보이지만 이해도 제대로 안되었기 때문에 잘 정리해서 적기가 힘들었다.

 

이게 맞는지는 디버깅을 통해서 이해했다.

 

 

처리 과정

---

우선 n-step TD는 간단하게 말해서 MDP를 모를 때의 가치평가를 n 스텝 이동 후 이루어진다.

 

그 과정을 살펴 보자.

우선 이해를 돕기 위해 n=2로 설정하고 while 부분에 breakpoint를 지정하고 디버깅을 돌려보자.

 

n스텝 움직이기 및 액션 취하기

그러면 states에 이렇게 4개의 원소가 담기게 되는데 n=2인데 왜 4개가 담겼을까?

 

그 이유는 다음과 같다.

 

1번째, 시작점은 (0, 0)에서 시작하기 때문에 처음부터 현재 위치의 값도 넣어 준다.

 

2,3번째가 이제 실제로 움직인 값이다. 이제 바로 n(=2) 스텝을 움직인 것이다.

((0, 0)로 두 번 연속되는 이유는 (0, 0)의 왼쪽 위쪽으로 움직이면 다시 0으로 초기화되게 해놨기 때문)

그저 그런 상황이 나왔는데 위와 같은 상황인 것이다.

 

그럼 이제 4번째가 뭔지 알아보자.

 

 

디버깅을 돌리다 보니 x,y에 저장되어 grid의 가치를 나타내는 data에 계산되어 들어간다.

데이터는 이런 역뱡향 순서대로 들어가게 된다.

 

그 이유는 먼저 4번째가 뭔지 알아보고 가자.

states = states[-1:]

 

data에 밸류를 모두 담고 결국 states에는 마지막 원소 하나만 남았다.

 

뭔가 익숙한 상황이 생기지 않았는가?

 

처음과 같이 (0, 0) 기본값으로 넣은 상태가 되었다.

 

실제로 움직이는 env의 x,y 값도 (0, 0)으로 초기화 되어 있었다.

 

사실은 env의 x, y값이 마지막에 한 번 더 움직여서 다음 시작점을 미리 계산하여 저장한 것이다.

 

이러한 이유는 n스텝을 하였는데 n번째가 (3, 3)에서의 밸류까지 계산 해버리면 안되기 때문에

 

n번째 값이 마지막(done)이 되는 것을 막기 위함이다.

 

또한 이 값은 n=2 이지만 n=2스텝에 대한 가치를 반영한 후에 액션을 취한 값을 나타낸다.

 

그림으로 표현하면 다음과 같다.

4번째 값은 다시 다음 스텝에서의 현재 위치로 나타낸다.

 

즉, 다시 states의 1번째가 되는 것이다. 

 

 

states 아래쪽에 있는 지역변수 x,y는 data에 저장하기 위한 index용 x,y이므로 실제로 움직이는 env의 x,y와는 구분해야 한다.

 

n-step TD의 밸류 업데이트 방식

$N = 1: R_{t+1} + γV(S_{t+1})$

$N = 2: R_{t+1} + γR_{t+2} + γ^2V(S_{t+2})$

$...$

$N = n: R_{t+1} + γR_{t+2} + γ^2R_{t+3} + ... + γ^nV(S_n)$

 

이 식은 벨만 기대 방정식 중 일부이다. 이 공식을 활용할 것이다.

 

코드에서 역방향으로 하는 것에 대한 이해를 돕기 위해 왜 그렇게 되는 지 보일 것이다.

G = data[next_state[0]][next_state[1]]

1번에 대해서 먼저 밸류를 G에 저장한다.

G = rewards[i] + gamma * G

즉,

$G(S_{t}) = R_{t+1} + γV(S_{t+1})$
여기서 우항의 V를 이전 G값이라고 생각하자. (G는 밸류기대방정식에서 누적보상을 의미)

 

예시로, 1스텝의 누적보상은 2스텝 누적합 * gamma + R 이므로

 

2스텝 누적보상을 먼저 계산하기 위해 역방향을 사용한 것이다.

 

그리고, 가치를 계산하는 식은

$V(S_t) += V(S_t) + α(G^{(n)}_t - V(S_t))$ 같은식을 풀어쓴 것→  $V(S_t) += (1-α)V(S_t) + G^{(n)}_t$

 

출처: 바닥부터 배우는 강화 학습(노승은 저자)

 

이 식은 MC에서도 사용되는 공식으로 밸류를 1에피소드가 끝날 때 업데이트 해주는 형식을 n-step 후 업데이트 해주는 형식으로 만든 것이다. 

 

그러면 위의 식이 코드에서는,

 data[x][y] += alpha * (G - data[x][y])  # data = V_t

이렇게 생긴 것이다.

 

 

결과

---