Current Issue

창고지기라 불리는 소코반은 일종의 운송 퍼즐이다. 창고에서 창고지기의 역할을 하는 에이전트가 상자를 밀어 목표 위치로 상자를 옮겨 퍼즐을 해결하고자 한다[6].

에이전트의 목표는 제한 스텝 수 안에 모든 상자를 목표 위치들로 옮기는 것이다. 이 과정에서 에이전트가 준수해야 하는 조건들은 다음과 같다. 첫째, 상자가 교착 상태에 빠지면 상자는 더 이상 움직일 수 없다. 둘째, 두 개 이상의 상자를 동시에 움직일 수 없다. 셋째, 상자 뒤에 다음 공간이 비어 있는 경우에 한해서만 인접한 상자 밀기를 시도할 수 있다.

본 논문에서는 소코반에 강화학습 알고리즘인 Q-학습을 적용한다. 강화학습은 행동 심리학에서 영감을 받은 기계학습의 한 분야이다[7]. 지도학습이 정답이 주어진 데이터를 이용하여 규칙을 학습한다면, 강화학습은 입력값과 쌍이 되는 출력값을 준비할 필요 없이 행동에 대한 보상을 이용하여 학습한다. 에이전트 행동이 환경에 영향을 주며, 행동은 환경의 상태를 변화시켜 그에 따른 보상을 받는다.

Q-학습은 에이전트가 환경이 주는 보상을 사용하여 주어진 상태에서 행동할 수 있는 최상의 행동을 학습한다. 현재 상태에서 행동에 대해 보상 받은 후 Q-값을 업데이트 하여 해당 행동이 유익한 지 여부를 기억한다. 또한, Q-학습은 오프-정책(Off-policy)을 사용하여 학습 과정과 행동 평가를 분리한다.

Q-테이블에 저장되는 값을 Q-값이라 하며(상태, 행동) 쌍에 매핑된다. 상태는 에이전트의 관측 가능한 상태 s(State)들의 집합을 가진다. 행동은 상태 s에서 가능한 행동 a(Action)들의 집합이다. 모든 상태에서 에이전트들이 가질 수 있는 행동들은 동일하다. Q-값은 0으로 초기화되어 있으며, 에이전트가 여러 환경에 노출되고 각기 다른 행동을 실행함으로써 다양한 보상을 받게 된다. 초기화되어 있던 Q-값들은 식 (1)을 이용하여 연속적으로 업데이트된다[8].

현재 상태 s에 대한 행동 a의 Q-값 Q(s, a)는 기존 Q(s, a)에 가중치 (1-α)를 준 값에 할인된 미래 최대 보상을 결정하는 식 (2)와 합으로 갱신된다. 이 과정을 반복하여 Q-테이블이 특정 값으로 수렴되도록 한다. 그러므로 한 상태에서 더 큰 Q-값을 가진 행동이 더 큰 보상을 받을 수 있다.

• - α: 학습율 (0 ≤ α ≤ 1)
• - γ: 할인율 (0 ≤ γ ≤ 1)
• - R: 보상

Q-학습은 단순하고 단일 에이전트 환경에서 우수한 학습 능력을 나타낸다. 본 논문에서는 소코반 풀이를 위한 Q-학습과정에서 소코반 학습 성공률에 대한 영향을 조사하기 위해 학습율과 할인율의 값의 변경을 수행한다.

ϵ-그리디 알고리즘은 감소율에 따라 탐험에 의한 행동을 선택하거나 또는 학습 결과를 활용하여 행동을 선택한다. 학습 초기에는 탐험에 의해 행동을 선택하다가 시간이 지남에 따라 지금까지 학습한 결과를 활용하여 행동을 선택하도록 한다. 감소율은 이러한 탐험과 활용 비율을 조정한다.

• - ϵ: 감소율 (0 ≤ ϵ ≤ 1)

감소율이 1이면 완전히 무작위 탐험하며 0이면 현재 학습 결과를 그대로 활용한다. 본 논문에서는 감소율의 영향을 조사하기 위해 감소율 값을 변경해 가면서 소코반 풀이를 학습한다.

본 논문에서는 강화학습을 위해 고안된 Gym-Sokoban의[9] 환경을 이용한다. 소코반 퍼즐 맵을 나타내는 스테이지 요소로는 벽, 바닥, 상자, 목표 위치 및 에이전트가 있다. 추가로 상자가 목표 위치 위에 있는 경우와 없는 경우, 에이전트가 목표 위치 위에 있는 경우와 없는 경우에 따라 7가지 상태를 가진다. 그림 1은 소코반 스테이지의 예시이다:

Fig. 1. 
Sokoban stage

소코반 스테이지로는 직관적인 5X5 사이즈(80X80 픽셀)의 가장 작은 스테이지를 이용한다. 하나의 상자, 하나의 에이전트 그리고 하나의 상자 목표 위치가 존재한다. 해당 스테이지의 상태공간은 5000으로 정의한다. Q-테이블의 행의 크기가 결정되었다. 또한 실제로 에이전트가 움직이는 공간은 벽을 제외한 3X3으로 소코반 풀이 시 너무 많은 스텝을 제공할 필요가 없기 때문에 최대 스텝은 150으로 정하였다.

본 논문에서는 소코반 스테이지를 풀이하기 위해 에이전트가 수행해야 할 행동의 연속을 알고자 그림 2 알고리즘을 따라 Q-학습한다. 학습된 Q-값은 현재 행동을 수행했을 때의 보상 및 다음 상태부터 할인된 최대 보상을 결합한다.

Fig. 2. 
Algorithm for Q-learning

1) 가장 처음에 Q-학습을 진행하고자 하는 소코반 스테이지 환경을 불러온다. 그리고 0으로 초기화된 상태공간X행동공간의 Q-테이블을 생성한다. 이어서 세 가지 하이퍼-파라미터의 값을 설정한다.

2) 학습시킬 에피소드 수를 설정한다. 환경을 초기상태로 재설정하고 시작한다. 에이전트는 상자가 교착상태에 빠져 최대 스텝을 달성하거나, 상자를 목표에 넣는 걸 성공할 때마다 해당 에피소드는 끝나고 새로운 에피소드가 시작된다.

3) ϵ-그리디를 적용하기 위해 0과 1사이의 임의의 값을 이용해 ϵ값보다 작으면 탐험을 통해 새로운 무작위 행동을 선택하고, ϵ값보다 크다면 현재 상태에서 가장 큰 Q-값을 가지는 행동을 선택해 활용한다.

4) 에이전트가 선택된 행동을 바탕으로 스텝을 진행한다. 해당 스텝을 통한 상태 변화에 따라 보상 값과 다음 상태 값을 반환한다.

5) 현재 상태에 대한 Q-값을 prev_q에 저장한다. 그리고 다음 상태에 대해 이미 학습됐던 Q-값 중에서 가장 큰 값을 가져와 next_max_q에 저장한다. 이제 Q-값에 식 (1)에 맞게 업데이트를 수행한다. 다음 상태 값을 상태로 넣어주고 3), 4), 5)를 에피소드가 끝나기 전까지 반복한다.

소코반에 Q-학습을 진행하기 위해서는 세 가지 하이퍼-파라미터 α, γ 그리고 ϵ에 대한 값을 설정한다. α는 지도학습 설정과 같이 Q-값들이 매 반복마다 업데이트 되는 것의 기대 정도이다. 현재 Q-값과 미래 Q-값 중에 새로운 값을 얼마나 학습에 받아들일 것인지를 나타낸다. γ은 찾은 행동에 대한 Q-값에 곱해지는 값으로 0에 가까울수록 현재의 Q-값을 중시하고 1에 가까울수록 미래의 Q-값을 중시한다. ϵ는 경험해보지 않은 행동에 따른 경로를 찾기 위한 탐험 그리고 활용의 균형 정도를 설정한다. 이렇게 서로의 역할이 다르기 때문에, 각자 의미에 따라 적절한 값을 지정해주어야 해당 스테이지에 대해 더 좋은 Q-학습이 진행된다.

Q-학습을 통해 만들어진 Q-테이블의 Q-값이 소코반 풀이 과정을 나타낸다. 본 논문에서는 소코반 풀이를 평가하기 위해 한 번의 에피소드를 초기 상태에서부터 가장 큰 Q-값으로 행동을 선택해 한 스텝씩 풀이한다. 평가 결과로 학습된 Q-테이블이 소코반 풀이에 성공한다면, Q-테이블 평가 성공 보상 값과 Q-테이블 평가 성공 스텝 수를 반환한다. 상자가 교착 상태에 빠졌거나, 최대 스텝 이내로 상자를 목표 위치에 옮기지 못한다면 좋지 않은 학습 과정에서 Q-값이 업데이트되어 결국 소코반 풀이에 실패한다.

본 논문에서는 최적의 Q-테이블을 만들기 위한 과정에서 학습에 영향을 미치는 세 가지 하이퍼-파라미터인 α, γ 그리고 ϵ에 대한 값을 변경하며 두 단계에 걸쳐 학습 성공률을 비교한다.

첫 번째 단계에서는 각 하이퍼-파라미터들의 값을 모두 0에서부터 1까지 0.1 단위로 지정하며 얻은 모든 조합의 학습 성공률 값 분포를 구한다. 그림 3에 나타난 분포를 살펴보면 학습율의 값은 0.3 그리고 할인율의 값은 0.9가 안정적이며 감소율의 값은 0.9에서 높은 학습 성공률을 가짐을 확인하였다. 이를 이용하여 두 번째 단계로, α, γ 그리고 ϵ에 대한 값을 변경하는 과정에서 변경할 값을 제외하고 나머지 값은 표 2의 고정 값을 주고 0.01 단위로 세분화시켜 각 1000번의 에피소드를 통해 Q-테이블을 학습시킨다:

Fig. 3. 
Learning success rate by Hyper-parameters

그림 4 그래프의 x축은 각 0에서부터 1까지 α,γ와 ϵ의 값이며 y축은 학습 성공률을 나타낸다.

Fig. 4. 
Success rate by changing Hyper-parameters

3가지 모두 대부분 30%의 학습 성공률을 가지고 있다. 1000개의 에피소드에서 기본적으로 300개 정도의 에피소드가 학습 과정에서 소코반 풀이에 성공한 것이다. 특히 ϵ의 경우, 0.2 부근의 값으로 지정되었을 때, 50% 이상의 학습 성공률을 보이는 모습을 살펴볼 수 있다. 0.2라면 1보다는 0에 가까운 수치이기 때문에, 무작위 탐험으로 9가지의 행동을 살펴보며 스텝 수를 낭비하기보다 지금까지 학습한 해당 상태에 대한 Q-값을 더 가치를 두는 경우이다. 이렇게 값을 비교해보니 3가지 하이퍼-파라미터는 모두 시간이 지남에 따라 감소하는 형식으로 제공됨이 좋다는 것을 알 수 있다. 에이전트가 계속 학습함에 따라 정보가 축적되기 때문이다. 만약 에피소드 수를 늘리게 된다면 시간에 따라 값들을 감소시키는 방향이 Q-학습을 이용한 소코반 풀이에 유용하다.

이번에는 α, γ 그리고 ϵ의 값을 바꿔가며 학습시킨 이후 생성된 Q-테이블을 평가한다. Q-테이블의 값에 따라서 소코반 풀이는 성공하거나 실패한다. 그 중에서도 성공한 경우의 결과 값을 분석한다. α는 100개의 Q-테이블에서 14개가 풀이에 성공하였다. γ는 100개 중에 12개, ϵ는 100개 중에 20개로 가장 많이 성공하였다(표 3-5).

그리고 50% 이상의 학습 성공률을 갖는 대부분은 Q-테이블 평가에서 성공한다. 이 점에서 하이퍼-파라미터 값을 적절히 조정하여 학습 과정에서 더 나은 Q-값을 만드는 작업의 중요성이 드러난다. 가능한 한 빨리 최대 보상을 얻을 수 있는 풀이를 해내고자 하기 때문에, 최고의 보상을, 시간을 나타내는 스텝 수로 나눈 비율을 구하여 얻을 수 있는 가장 좋은 하이퍼-파라미터의 값들을 선택하도록 하는 것이 바람직하다. 그리고 성공 스텝 수가 길어질수록 패널티를 받기 때문에 성공 보상 값이 작아진다. γ과 ϵ는 20 스텝 이내로 성공한 경우가 다수 존재한다. 이는 해당 스테이지에서 에이전트가 행동 가능한 가장 짧은 스텝인 5 스텝에 가까운 수준으로 학습에 성공하였다는 것이다.

앞의 성공한 경우 중 가장 잘 학습된 Q-테이블을 분석한다. ϵ의 No.96 인 0.96으로 값을 지정하고 학습을 시킨 경우의 성공 스텝 과정은 다음과 같다: 초기 상태에는 1의 보상을 갖고 시작한다. 에이전트는 위로 이동하고 우측으로 상자를 민다. 이어서 우측으로 이동을 시도한 뒤, 아래로 이동하고 우측으로 이동한다. 마지막으로 위로 상자를 밀어 상자를 목표에 위치시켰다. 이렇게 총 11.4의 보상으로 6 스텝만에 종료되었다. 이용된 상태의 Q-값들은 모두 0 이상의 좋은 양수의 값을 가지고 있다.

그리고 모든 경우의 Q-테이블에서, 가장 첫 번째 상태에서의 행동은 0~249(상태)에서 Q-값이 0인 경우를 제외하고 모두 한 가지의 행동을 가리킨다. 무작위 행동을 탐험하는 과정에서 선택되는 첫 행동이 중요함을 알 수 있다. 상대적으로 더 많은 스텝으로 풀이한 Q-테이블의 값은 표 6의 수치보다 작은 값의 Q-값을 갖고 있음을 확인할 수 있다. 이는 대부분의 스텝이 효율적으로 사용되지 못하고, 패널티의 보상을 많이 받은 것을 의미한다.