[RL] 1. Reinforcement Learning Overview & Terminology

1. Reinforcement Learning Overview & Terminology

뭘 배워도 뒤돌면 까먹는 30대 중반의 뇌를 가진 나.

최근에 학습한 Reinforcement Learning을 최대한 안까먹기 위해 복습 차원에서 이 글을 남긴다.

본 글의 내용은 도서 *'Reinforcement Learning (R. Sutton, A. Barto)'** 를 참고했습니다.

1.1 Overview

Reinforcement Learning(강화학습): Agent가 인간의 지도 없이 스스로 Environment와 trial and error 방식으로 상호작용 함으로써 누적 reward 가 maximize 될 수 있도록 학습시키는 기법.

전통적으로 정의되어 온 Machine Learning 의 세가지 대표적인 패러다임들 - Supervised Learning, Unsupervised Learning, Reinforcement Learning(이하 RL) 중 하나이다. 요즘에는 Semi-supervised learning 처럼 기존의 세가지 패러다임으로 정의되지 않는 기법도 있긴 하다.

RL이 엄청 유명해진 계기는 아마 알파고와 이세돌 9단의 대국이 아닐까 싶다. 나도 그걸 보고 이 분야에 팍 꽃힌거고. 알파고 역시 어떠한 상황이 주어졌을 때 어떤 수를 두는 것이 누적 reward를 maximize 시키는지를 학습하여 만들어진 것이다.

실생활에서 RL이 유용할 수 있는 분야의 쉬운 예를 들면, 어떤 곳을 찾아갈 때 최단경로를 찾고싶다고 치자. 단순히 거리만 보고 결정할 수도 있지만, 도로 위에는 속도를 늦출 수 있는 수많은 요인들이 존재한다. 신호등, 방지턱, 스쿨존 등등... 여기서 RL을 적용하면, Agent는 a 지점에서 b 지점까지 갈 수 있는 모든 경로를 탐험하여 실제 달려야 하는 거리와 관계없이 b까지 도달하는 시간이 가장 짧은 하나의 경로를 유추해낼 수 있다.

다음의 도표가 아마 RL의 개념을 설명하는 가장 간단한 방법이 아닐까 생각이 든다.

(이미지 출처: https://i.stack.imgur.com/eoeSq.png)
Agent: 학습을 하고 결정을 내리는 개체.
Environment: Agent가 상호작용하는 모든 것을 가리킴.

어느 시점(t)에 주어진 상태(state, $S_{t}$)에서 Agent는 어떤 action을 취할것인지 결정을 내린다($A_{t}$). 그러면 Environment는 그에따라 Agent에게 해당 결정에 따른 reward ($R_{t+1}$)를 부여하고, 새로운 상태($S_{t+1}$)를 제시한다.

여기서 'state' 라는 것은 '현재 agent가 가지고 있는 정보' 정도로 해석할 수 있다. 달 착륙선을 예를 들면, state에는 현재 하강속도, 연료량, 착륙선의 각도, 착륙선과 달 표면의 거리 등등의 정보가 모두 포함된다. 바둑을 예로 들면 현재 흑과 백의 바둑돌 배치 상태를 들 수 있겠다.

이처럼 RL은 어떤 시스템이 Markov Decison Process(이하 MDP) 문제로 정의될 수 있을 때 그 위력을 발휘한다.

MDP라는 것은, 간단히 말하면 '현재 내리는 결정은 현재의 상태(state)만 고려한다'는 것이다. 길찾기를 예로 들면, 지금 여기서 {우회전, 좌회전, 직진} 중 하나를 선택할 때는 과거나 미래 시점의 차의 상태, 도로 상태, 장애물, 잔여 기름 양 등 까지 고려하는 것이 아닌 현재 차의 상태, 현재 도로 상태, 현재 보이는 장애물, 현재 잔여 기름 양만을 고려하여 결정을 내린다는 것이다. MDP에서는 현재의 state가 과거의 정보를 모두 포함한 결과라고 가정하기 때문이다.

MDP를 구성하는 요소는 현재 state, action, reward, 그리고 현재 state에서 다음의 어떤 state로 넘어가는지에 대한 확률이 있다. 이 확률을 수식으로 나타내면, 어떤 시점 t에서 state s와 action a가 주어졌을 때, agent가 어떤 새로운 state s' $\in$ S 와 r 을 가질 확률은 다음과 같이 정의할 수 있다.

$$ p(s',r | s, a) \doteq Pr \{ S_{t} = s', R_{t} = r | S_{t-1} = s, A_{t-1} = a \}$$

그리고 이는 확률이므로, $\sum_{s', r} p(s', r | s, a) = 1$ 를 만족한다.

RL은 이 MDP의 구성요소들을 이용하여 누적 reward를 최대로 하는 action을 판별해낼 수 있게 한다.

이처럼 RL은 MDP 문제를 해결하는데에 촛점이 맞추어져 있기 때문에 supervised learning이나 unsupervised learning과는 그 목적이 조금 다르다는 것이 특징이다.

---

1.2 Terminology

RL의 알고리즘들을 소개하기에 앞서 필수적으로 알아야 하는 용어들이 있다.

Return($G_{t}$) : Reward의 합으로, Agent가 궁극적으로 maximize 하고자 하는 대상이다.

Agent는 바로 눈앞에 놓인 reward만 maximize 할 것이 아니라, 장기적인 안목을 가질 필요가 있다. Return은 시간이 흐름에 따라 Agent가 갖게 되는 reward의 합을 나타내고, expected return은 다음과 같이 정의한다.
$$G_{t} \doteq R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} + \dots = \sum_{k=0}^{T} \gamma^{k} R_{t+k+1}$$
여기서 $\gamma$(감마) 는 discount factor 라고 하고, $0\leq \gamma \leq1$ 을 만족한다. 이는 agent가 현재의 return을 계산할 때 미래의 reward에 얼마만큼 비중을 둘 것인가를 고려하는 것이다. 만약 $\gamma=1$이라면, 먼 미래의 reward(예를들어 $R_{1000}$)도 바로 눈앞의 reward인 $R_{t+1}$과 같은 비중을 가지고 return에 더해진다. 즉, 장기적인 안목을 갖고 action을 취하게 된다. 만약 $\gamma=0$이라면, return은 미래의 reward를 전혀 고려하지 않게 되어 agent는 눈앞의 이익만 쫓게 된다. 체스를 예를 들면, $\gamma=1$인 agent는 지금 queen을 희생시켜 5턴 뒤 checkmate를 잡는 플레이가 가능할 것이고, $\gamma=0$인 agent는 눈앞에 놓인 pawn을 잡느라 다음 턴에 있었을 수도 있는 checkmate를 포기하게 되는 것이다.

여기까지 보면 '그럼 $\gamma$를 무조건 1로 두면 되는거 아닌가?' 하는 생각이 들 수도 있다. 하지만 그러면 위의 수식에서 T=$\infty$인 경우 return이 무한대로 뻗어나가고 converge 하지 않게 된다. 만약 agent가 어떤 확률 p<1에 의해 action a를 선택하면 reward 1이 주어진다고 하자. 그럼 $G_{t}=\sum_{k=0}^{\infty} \gamma^{k} p$가 되고, 이는 geometric series 에 따라 $\frac{p}{1-\gamma}$ 가 된다. 여기서 $\gamma$가 1이라면 converge하지 않아 return이 undefined가 되어버려 agent가 처리할 수 없다. 따라서 $\gamma$는 대개 1로 두지 않고, 0.9 같은 수로 둔다.

Episode: 쉽게 말하면 '한 판', '회차'. 통계학에선 trial로 부른다.

Agent가 탐험하는 environment에 시작 state와 끝(terminal) state가 정해져 있을 경우 그 task를 Episodic task라고 부른다. terminal state가 없이 계속 이어지면 Continuous task라고 부른다. 앞서 return 부분에서 $T=\infty$인 경우가 continuous이고, 그렇지 않은 경우가 episodic이라고 보면 되겠다.

체스의 경우를 보면, 한판의 게임이 하나의 episode이고, checkmate 가 발생하면 게임이 끝나기 때문에 checkmate가 발생하는 state가 terminal state가 되어 하나의 episode가 끝난다. 따라서 체스는 episodic task이다.

반면, 인공지능 비서의 경우를 보면, 딱히 시작과 끝이라는 개념이 없다. 이런 경우가 continuous task이다.

Policy($\pi$): Agent가 어떤 action을 선택하게 하는 법칙(함수)을 의미한다.

$\pi(a|s)$: 어떤 state $S_{t}=s$ 가 주어졌을 때 어떤 특정한 action a $\in A_{t}$를 선택할 확률.

---

일단은 여기까지 하고, 나머지는 알고리즘을 하나씩 소개하면서 더 설명해볼까 한다.