[강화학습] 07 - 살사(SARSA)

개요

처음부터 지금까지 꽤 많은 것을 배웠지만 충격적이게도 이 살사부터가 실제 강화학습 알고리즘입니다. 이전에 배웠던 것은 강화학습을 배우기 위한 기초 개념이었던 것이죠.

예전에 잠시 언급했지만 살사는 정책 이터레이션과 가치 이터레이션이 발전되어서 만들어졌습니다. 이번 포스팅에서는 이 살사의 발전 과정과 이전 포스팅에서 배운, 참 가치함수를 학습하는 2가지 예측 방법을 이용하여 에이전트가 어떻게 학습하는지에 대해서 다뤄볼려고 합니다.

살사

저희는 이전 포스팅에서 참 가치함수를 학습하는 몬테카를로 예측과 시간차 예측을 배웠습니다. 이 2가지 방법 중에 시간차 예측에 대해서 생각해봅시다.

정책 이터레이션에서는 한 번에 모든 상태의 가치함수를 업데이트하고 이를 이용해서 정책을 발전시켰습니다. 하지만 시간차 방법은 타임스텝마다 가치함수를 현재 상태에 대해서만 업데이트하기 때문에 정책 이터레이션처럼 모든 상태의 정책을 발전시킬 수 없습니다.

따라서 살사는 가치 이터레이션의 방법을 사용합니다. 별도의 정책을 두지 않고 현재 상태에서 가장 큰 가치를 지니는 행동을 선택하는 탐욕 정책을 사용합니다. 이렇게 시간차 예측과 탐욕 정책이 합쳐진 것을 시간차 제어라고 합니다. 살사를 부르는 다른 말이죠.

아래 그림은 살사가 정책 이터레이션과 가치 이터레이션의 어떤 특징들을 사용했는지 알려주는 표입니다. 주황색으로 표시한 부분이 살사에서도 사용된 특징입니다.

정책 이터레이션	가치이터레이션
벨만 기대 방정식	벨만 최적 방정식
정책 평가 + 탐욕 정책 발전	최적 가치함수를 목표로 업데이트
모든 상태에 정책 존재	별도의 정책 x

이전 포스팅에서 시간차 예측은 벨만 기대 방정식을 이용해서 가치함수를 업데이트하는 것이라고 배웠습니다. 이 가치함수를 이용해서 큐함수의 최댓값을 구하려면(탐욕 정책 발전) 원래 식이 아닌 아래와 같은 식을 사용해야 합니다.
$$π'(s) = argmax_{a∈A}q(s,a)$$ $$\downarrow$$
$$π'(s) = argmax_{a∈A}E_π[R_{t+1} + γP_{ss'}^av_π(S_{t+1}) | S_t = s, A_t = a ]$$
하지만 식을 살펴보면 저희는 환경의 모델인 $P_{ss'}^a$을 알아야만 사용할 수 있습니다. 따라서 살사는 다시 원래의 식대로, 가치함수 대신 큐함수를 사용해 탐욕 정책을 통해 행동을 선택합니다.
$$π(s) = argmax_{a∈A}Q(s,a)$$

시간차 예측에서 업데이트하는 대상도 가치함수가 아닌 큐함수가 돼야 하죠. 시간차 예측 식에서 가치함수를 큐함수로 바꾼 시간차 제어의 식은 다음과 같습니다.
$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + α(R_{t+1} + γQ(S_{t+1},A_{t+1})) - Q(S_t,A_t))$$
위의 식을 사용하기 위해서는 $Q(S_t,A_t)$를 위한 현재 상태($S_t$)와 행동($A_t$), $Q(S_{t+1},A_{t+1})$를 위한 다음 상태($S_{t+1}$)와 다음 상태에서의 행동($A_{t+1}$) 그리고 보상($R_{t+1}$)까지 알아야합니다.

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

즉 시간차 제어에서 큐함수를 업데이트하려면 $[S_t,A_t,R_{t+1},S_{t+1},A_{t+1}]$을 샘플로 사용합니다. 이것이 시간차 제어를 살사(SARSA)라고 부르는 이유기도 하죠.

살사는 현재 가지고 있는 큐함수를 토대로 샘플을 탐욕 정책으로 모으고 그 샘플로, 방문한 큐함수를 업데이트하는 과정을 반복하는 것입니다. 이 탐욕 정책은 많은 경험을 한 에이전트에게는 좋은 선택이겠지만 초기의 에이전트에게는 잘못된 학습으로 가게 할 가능성이 큽니다.

그리드월드를 예로 들어봅시다. 처음엔 모든 상태의 큐함수가 0으로 초기화되어있기 때문에 초기의 에이전트는 무작위로 행동을 결정할 것입니다.

에이전트가 아래 그림과 같이 검은색 경로로 계속 행동을 선택해서 우연히 목표점에 도달했다면 저 행동들의 큐함수는 양수로 업데이트될 것입니다.

그렇다면 이후 에피소드에서 에이전트는 큐함수의 최댓값만을 따라 행동하므로 목표로 가는 더 좋은 행동을 놔두고 검은색 경로와 같이 돌아갈 수 밖에 없는 것입니다.

이렇게 에이전트가 충분히 다양한 경험을 하지 못해서 잘못된 정책을 학습하는 문제를 탐험(Exploration)의 문제라고 합니다.

따라서 저희는 에이전트가 탐험하게 하기 위해서 탐욕 정책 대신 ε-탐욕 정책을 사용합니다.

이는 간단하게 ε만큼의 확률로 탐욕적이지 않은 행동을 선택하고 1-ε의 확률로는 큐함수의 최댓값을 따라 행동을 선택하게 하는 정책입니다. 이를 식으로 나타내면 다음과 같습니다.$$π(s) = \begin{cases} a^* = argmax_{a∈A}Q(s,a) &\text{1-ε의 확률로 } \\ a ≠ a^* &\text{ε의 확률로 } \end{cases} $$

ε-탐욕 정책은 최적 큐함수를 찾았다 하더라고 ε의 확률로 계속 탐험한다는 한계 때문에 학습을 진행함에 따라 ε의 값을 감소시키기도 하지만 이 책의 예시 코드에서는 ε를 일정한 값으로 사용합니다.

정리하면 살사는 큐함수를 이용한 시간차 예측을 사용해서 큐함수를 업데이트시키고, 이를 이용하여 ε-탐욕 정책으로 행동을 결정한 후 모인 샘플들로 다시 큐함수를 업데이트시키는 과정을 반복하는 강화학습 알고리즘입니다.

 

---

살사 코드 설명

이번에도 이전에 나왔던 그리드월드 문제에 적용되는 코드입니다. 그리드월드 환경에 대한 정보도 이전과 동일하게 Env라는 클래스로 정의되어 있습니다.

에이전트가 환경의 모든 정보를 알고 사용했던 정책 이터레이션, 가치 이터레이션 코드와는 다르게 강화학습의 에이전트는 환경의 정보를 미리 알고 사용하지 않습니다.

<변수 선언>

def __init__(self, actions):
    self.actions = actions
    self.step_size = 0.01
    self.discount_factor = 0.9
    self.epsilon = 0.1
    # 0을 초기값으로 가지는 큐함수 테이블 생성
    self.q_table = defaultdict(lambda: [0.0, 0.0, 0.0, 0.0]) #default 값을 [0.0, 0.0, 0.0, 0.0]으로 지정

actions는 에이전트가 할 수 있는 행동으로 환경으로부터 받아옵니다. 그리드월드에서는 [0, 1, 2, 3]으로 각각 상, 하, 좌, 우의 행동을 의미합니다.

스텝사이즈 step_size(α)는 0.01로, 할인율 discount_factor(γ)은 0.9로 그리고 ε-탐욕 정책에 사용할 epsilon(ε)은 0.1로 설정한 것을 확인할 수 있습니다.

큐함수를 저장하기 위해서 dictionary 자료형이 큐함수이고 [0.0, 0.0, 0.0, 0.0]의 기본값을 가지는 q_table을 사용합니다. (참고: difaultdict 함수는 dictionary 자료형에 기본값을 정의하는 함수이며 Lamda를 이용하면 dictionary 자료형의 기본값을 설정할 수 있습니다.)

<큐함수 업데이트>

# <s, a, r, s', a'>의 샘플로부터 큐함수를 업데이트
def learn(self, state, action, reward, next_state, next_action):
    state, next_state = str(state), str(next_state)
    current_q = self.q_table[state][action]
    next_state_q = self.q_table[next_state][next_action]
    td = reward + self.discount_factor * next_state_q - current_q
    new_q = current_q + self.step_size * td
    self.q_table[state][action] = new_q

현재 상태와 다음 상태에서의 행동을 ε-탐욕 정책으로 선택해서 샘플$(s, a, r, s', a')$을 얻으면 아래 식을 이용해서 큐함수를 업데이트 시키는 코드입니다.
$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + α(R_{t+1} + γQ(S_{t+1},A_{t+1})) - Q(S_t,A_t))$$
이때 dictionary의 키 값으로 상태를 string의 형태로 넣어야하기 때문에 state와 next_state를 str함수를 이용해서 string으로 변환시켜줘야 합니다.

<ε-탐욕 정책>

# 입실론 탐욕 정책에 따라서 행동을 반환
def get_action(self, state):
    if np.random.rand() < self.epsilon:
        # 무작위 행동 반환
        action = np.random.choice(self.actions)
    else:
        # 큐함수에 따른 행동 반환
        state = str(state)
        q_list = self.q_table[state] 
        action = arg_max(q_list)
    return action

ε-탐욕 정책에 따라서 행동을 결정하는 코드입니다. ε-탐욕 정책은 에이전트의 충분한 탐험을 위해서 ε의 확률로 무작위 행동을 하는 방법입니다.

np.random.rand()를 이용하면 0~1 사이의 값이 하나 나오는데, 이 값이 이전에 선언했던 ε값 0.1보다 작으면 무작위로 행동을 선택하고 0.1보다 크다면 큐함수의 최댓값을 가지는 행동을 선택합니다.

여기서 arg_max는 별도의 함수로 다음과 같습니다. 현재 상태의 큐함수 리스트에서 가장 큰 값에 해당하는 행동의 인덱스 값을 반환해줍니다.

# 큐함수의 값에 따라 최적의 행동을 반환
def arg_max(q_list):
    max_idx_list = np.argwhere(q_list == np.amax(q_list))
    max_idx_list = max_idx_list.flatten().tolist()
    return random.choice(max_idx_list)

<메인 루프>

for episode in range(1000):
    # 게임 환경과 상태를 초기화
    state = env.reset()
    # 현재 상태에 대한 행동을 선택
    action = agent.get_action(state)

    while True:
        env.render()

        # 행동을 취한 후 다음상태 보상 에피소드의 종료 여부를 받아옴
        next_state, reward, done = env.step(action)
        # 다음 상태에서의 다음 행동 선택
        next_action = agent.get_action(next_state)
        # <s,a,r,s',a'>로 큐함수를 업데이트
        agent.learn(state, action, reward, next_state, next_action)

        state = next_state
        action = next_action

에이전트가 현재 상태(s)에서 ε-탐욕 정책으로 행동(a)을 선택(a)하고 이동한 후에, 환경으로부터 다음 상태(s'), 보상(r), 에피소드의 종료 여부를 받아옵니다.

이후 다음 상태에서도 ε-탐욕 정책으로 다음 행동(a')을 선택하면 큐함수를 업데이트시키기 위한 샘플 $<s, a, r, s', a'>$이 모두 모이게 됩니다.

이를 이용해서 큐함수를 업데이트시키고 한 타임스텝마다 위 과정을 반복해나가다 보면 큐함수가 최적의 값으로 수렴하게 됩니다.

살사 알고리즘의 전체 코드는 아래 링크에서 찾아볼 수 있습니다.

https://github.com/rlcode/reinforcement-learning-kr-v2

GitHub - rlcode/reinforcement-learning-kr-v2: [파이썬과 케라스로 배우는 강화학습] 텐서플로우 2.0 개정판

 

---

살사를 실행시킨 결과는 다음과 같습니다.

에이전트가 방문한 상태에 대해서만 큐함수를 표시하기 때문에 왼쪽은 학습을 시작한지 얼마 안 된 그림이고 오른쪽은 일정 시간이 지나 에이전트가 모든 상태를 방문한 그림입니다.

당연하겠지만 에이전트는 모든 상태를 지속적으로 방문해야만 큐함수가 최적의 값으로 수렴하여 올바른 학습을 할 수 있습니다.

이렇게 저희는 강화학습의 첫 번째 알고리즘인 살사에 대해서 알아봤습니다. 하지만 겉으론 완벽해보이는 이 살사를 여러번 실행시키다보면 에이전트가 똑같은 상태를 반복하면서 갇히는 현상을 발견할 수 있습니다.

이는 바로 ε-탐욕 정책으로 발생한 문제로, 에이전트가 탐험을 하다가 큐함수가 의도한 바와 다르게 업데이트되었기 때문입니다. 이런 살사의 한계를 극복하기 위해서 나온 것이 큐러닝입니다.

살사의 문제점과 큐러닝에 대해서는 다음 포스팅에서 자세하게 설명드리도록 하겠습니다. 읽어주셔서 감사합니다~!

http://www.yes24.com/Product/Goods/44136413

파이썬과 케라스로 배우는 강화학습 - YES24

※ 이 글은 위의 책 내용을 바탕으로 작성한 글입니다.