(7) 살사(SARSA)와 큐러닝(Q-Learning)

본 포스트는 “파이썬과 케라스로 배우는 강화학습” 도서의 일곱번째 리뷰 포스트입니다.

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

4장 강화학습 기초 3: 살사(SARSA)와 큐러닝(Q-Learning)살사(SARSA)살사 코드 설명 살사의 한계 큐러닝 큐러닝 코드 설명 정리

4장 강화학습 기초 3: 살사(SARSA)와 큐러닝(Q-Learning)

정책 이터레이션과 가치 이터레이션은 살사로 발전한다. 살사부터 강화학습이라 부른다. 각 이터레이션들이 어떻게 살사로 발전하는지, 살사와 같은 강화학습 알고리즘을 통해 에이전트가 어떻게 학습하는지 알아보자.

살사(SARSA)

정책 이터레이션은 정책 평가 와 정책 발전 을 번갈아 가며 실행하는 과정이다. 벨만 기대 방정식을 이용해 현재의 정책에 대한 참 가치함수를 구하는 것이 정책 평가이며, 구한 가치함수에 따라 정책을 업데이트 하는 것이 정책 발전이다. 이러한 정책 이터레이션을 GPI(Generalized Policy Iteration)이라고 한다. GPI에서는 단 한번만 정책을 평가해서 가치함수를 업데이트하고 바로 정책을 발전하는 과정을 반복한다.

GPI에서는 벨만 방정식에 따라 정책을 평가한다. 그 대신 강화학습에서는 몬테카를로 예측 이나 시간차 예측 을 사용하여 정책을 평가한다. GPI의 탐욕 정책 발전 은 주어진 가치함수에 대해 모든 상태에 대한 정책을 얻는 과정이다. 시간차 방법 에서는 타임스텝마다 가치함수를 현재 상태에 대해서만 업데이트 하므로, 모든 상태의 정책을 발전시킬 수 없다.

때문에 시간차(Temporal-Difference) 방법에서는 가치 이터레이션의 방법을 도입한다. 가치 이터레이션에서는 정책 이터레이션과는 달리 별도의 정책 없이 가치함수에 대해 탐욕적으로 움직일 뿐 이었고, 시간차 방법에서도 에이전트는 현재 상태에서 가장 큰 가치를 지니는 행동을 선택하는 탐욕 정책 을 사용한다. 시간차 예측과 탐욕 정책이 합쳐진 것을 시간차 제어(Temporal-difference control)이라고 한다. 이들의 관계를 나타낸 것이 아래의 그림이다.

탐욕 정책에서 다음 상태의 가치함수를 보고 판단하는 것이 아닌 현재 상태의 큐함수를 보고 판단한다면 환경의 모델을 몰라도 된다. (GPI의 탐욕 정책 발전에 따르면 을 계산하기 위해서 상태 변환 확률인 를 알아야 했다. 행동을 했을 때, 이상한데로 튈 확률이랄까나. 요녀석은 환경의 일부로서 현실에서는 알기가 매우매우 힘든 정보이기 때문에, 이 녀석 없이 행동을 선택하게 하는 것이 필요하다!)시간차 제어에서는 아래의 큐함수를 사용한 탐욕 정책 을 통해 행동을 선택한다.

큐함수에 따라서 행동을 선택하려면 에이전트는 가치함수가 아닌 큐함수의 정보를 알아야 하므로, 업데이트의 대상은 가치함수가 아닌 큐함수가 되어야 한다. 때문에 시간차 제어의 식은 다음과 같다.

시간차 제어에서 큐함수를 업데이트 하려면 샘플이 필요하다. 시간차 제어에서는 을 샘플로 사용한다. 흐름을 한번 살펴보면

에이전트는 에서 탐욕 정책에 따라 를 선택

환경은 을 제공하고 다음상태 을 제공

에이전트는 에서 탐욕 정책에 따라 을 선택

샘플의 형태 때문에 시간차 제어를 다른말로 살사(SARSA)라고 부른다. 살사는 현재 가지고 있는 큐함수 를 토대로 샘플을 탐욕 정책으로 모으고, 그 샘플로 방문한 큐함수를 업데이트하는 과정을 반복하는 것이다.

초기의 에이전트에게 탐욕정책은 잘못된 학습으로 가게할 가능성이 크다. 때문에, 큐함수가 잘못된 값에 수렴하는 것을 막기 위해 에이전트가 충분히 다양한 경험을 하도록 해야하고, 이를 위해 -탐욕 정책 을 사용한다. 간단한 아이디어인데 의 확률로 탐욕적이지 않은 행동을 선택하게 하는 것이다.

(물론 -탐욕 정책은 최적 큐함수를 찾았다 하더라도 의 확률로 계속 탐험한다는 한계 가 있다. 따라서 학습을 진행함에 따라 값을 감소시키는 방법을 사용할 수도 있다.)

정리하자면, 살사는 간단히 두 단계로 생각하면 된다.

-탐욕 정책을 통해 샘플 을 획득

획득한 샘플로 다음 식을 통해 큐함수 를 업데이트

이제 코드를 한번 살펴보자

살사 코드 설명


class SARSAgent:
  def __init__(self,actions):
    self.actions = actions # 에이전트가 할 수 있는 행동 [상,하,좌,우]
    self.step_size = 0.01      # α
    self.discount_factor = 0.9 # γ
    self.epsilon = 0.1         # ϵ
    self.q_table  = defaultdict(lambda: [0.0, 0.0, 0.0, 0.0])

init을 통해 학습에 필요한 변수들을 할당해 주었다. 추가로 SARSAgent 에 어떤 함수가 필요한지를 알기 위해서는 에이전트가 환경과 어떻게 상호작용하고 학습하는지를 알아야 한다. 에이전트는 다음과 같은 순서로 상호작용한다.

현재 상태에서 -탐욕 정책에 따라 행동을 선택

선택한 행동으로 환경에서 한 타임스텝을 진행

환경으로부터 보상과 다음 상태를 받음

다음 상태에서 -탐욕 정책에 따라 다음 행동을 선택

(s,a,r,s’,a’)을 통해 큐함수 업데이트

get_action 함수는 -탐욕 정책에 따라 state를 입력으로 받아 action을 반환한다. q_table에 따라서 탐욕적으로 행동을 선택하며 이때 의 확률을 반영하여 무작위 행동을 반환하기도 한다.


# 입실론 탐욕 정책에 따라서 행동을 반환
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

현재 상태와 다음 상태에서의 행동을 선택해서 샘플(s,a,r,s’,a’)을 얻으면 에이전트는 학습을 진행한다. 즉 아래의 식의 역할을 하는 함수는 learn이며 코드는 다음과 같다.(굉장히 직관적이다!)


# <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

get_action과 learn 함수를 통해 에이전트는 메인 루프에서 다음과 같이 환경과 상호작용한다.


# 행동을 위한 후 다음상태 보상 에피소드의 종료 여부를 받아옴
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

살사의 한계

살사에서는 충분한 탐험(Exploration) 을 하기 위해 -탐욕 정책을 사용했다. 그런데 다음의 경우를 한번 생각해보자.

초기 에이전트가 만약 에서 라는 행동을 하고 다음 행동인 은 탐험을 통해서 가게 되었다고 생각해보자. 그럼 자연스럽게 초기 에이전트는 값을 낮출 것이고 이에 따라 에서 아래로 이동하는 행동이 안좋다고 판단할 것이다. 결국 에이전트가 특정 state에 갇혀버리는 현상 이 발생한다. 이렇게 자신이 행동한 대로 학습하는 것을 On-Policy 시간차 제어 라고 한다. 이러한 딜레마를 해결하기 위해 사용하는 것이 바로 오프폴리시 시간차 제어 , 큐러닝 이다.

큐러닝

큐러닝의 아이디어는 간단하다. 오프폴리시 의 말 그대로 현재 행동하는 정책과는 독립적으로 학습한다는 것이다. 즉, 행동하는 정책과 학습하는 정책을 따로 분리 한다. 이게 무슨 말일까? 예시로서 이해해보자.

에이전트가 현재 상황 에서 행동 를 -탐욕 정책에 따라 선택했다고 하자. 그러면 에이전트는 환경으로부터 보상 을 받고 다음 상태 을 받는다. 여기까지는 살사와 동일하다. 하지만 살사에서는 다음 상태 에서 또다시 -탐욕 정책에 따라 다음 행동을 선택한 후에 그것을 학습에 샘플로 사용한다. 큐러닝 에서는 에이전트가 다음 상태 을 알게 되면 그 상태()에서 가장 큰 큐함수를 현재 큐함수의 업데이트에 사용한다. 살사의 학습과정과 다르게 큐러닝은 아래와 같이 학습한다.

큐러닝은 실제 다음 상태 에서 다음 행동을 해보는 것이 아니라 다음 상태 에서 가장 큰 큐함수를 가지고 업데이트 하는 것이다. 자세히 살펴보면 벨만 최적 방정식과 비슷하다는 생각이 들 것이다.

벨만 최적 방정식은 아래의 수식과 같은데 큐러닝에서 보상 은 실제 에이전트가 환경에게서 받는 값이므로 기댓값을 빼면 동일하다.

벨만 기대 방정식 –> 정책 이터레이션 –> 살사

벨만 최적 방정식 –> 가치 이터레이션 –> 큐러닝

큐러닝은 샘플로서 [s,a,r,s’]을 사용하며 실제 환경에서 행동을 하는 정책과 큐함수를 업데이트할 때 사용하는 정책이 다르기 때문에 큐러닝을 오프폴리시라고 한다. 다른 오프폴리시 강화학습과 달리 큐함수가 간단하기 떄문에 이후에 많은 강화학습 알고리즘의 토대가 되었다.

큐러닝 코드 설명

큐러닝 코드에서 살사 코드에서와 다른 점은 에이전트가 샘플을 가지고 학습하는 부분이다.


# <s, a, r, s'> 샘플로부터 큐함수 업데이트
    def learn(self, state, action, reward, next_state):
        state, next_state = str(state), str(next_state)
        q_1 = self.q_table[state][action]
        # 벨만 최적 방정식을 사용한 큐함수의 업데이트
        q_2 = reward + self.discount_factor * max(self.q_table[next_state])
        self.q_table[state][action] += self.step_size * (q_2 - q_1)

learn 코드는 위에서 살펴본 큐러닝의 업데이트 식을 구현한 것이다. self.q_table[next_state]에서 max 값을 업데이트에 사용하기 때문에 오프폴리시가 됩니다. 또한 max값을 취하면 되기 때문에 다음 상태에서의 행동을 알 필요가 없다.

살사와 큐러닝의 차이는 온폴리시와 오프폴리시 의 차이라고 볼 수 있다. 온폴리시인 살사는 지속적인 탐험 으로인해 그리드월드 예제에서 왼쪽 위에 갇히곤 하지만 큐러닝은 현재 행동하는 정책과는 독립적으로 학습을 진행하기 때문에 갇히지 않고 벗어나는 정책을 학습할 수 있다.

정리

몬테카를로 예측: 기댓값을 샘플링을 통한 평균으로 대체

시간차 예측: 몬테카를로 예측과는 달리 타임스텝마다 큐함수를 업데이트

살사(SARSA): 강화학습 제어에서 큐함수를 사용하며 하나의 샘플로 (s,a,r,s’,a’)을 사용하는 시간차 제어

큐러닝(Q-learning): 오프폴리시 강화학습으로서 행동선택은 -탐욕 정책 , 큐함수의 업데이트에는 벨만 최적 방정식 사용