지난 10월 알파고 제로의 등장으로 안그래도 뜨겁던 딥러닝이 이제 한 마그마 정도 되는 것 같다. 하지만 딥러닝은 언론에서 좋아하는 단어인데다 포괄적인 분야에 가까우니, 실제 우리는 거기 쓰인 기술의 기초를 공부해야 한다. 그 중의 하나가 오늘 다룰 Reinforced learning이다. 물론 구글에서 사용한 강화학습 기법을 공부하는 것이 아니라, 강화학습의 기초부터 일단…

1. Intro

강화학습은 기존 두가지 머신 러닝의 분류 - 지도학습과 비지도학습 - 와는 또 다른 분류의 러닝 방식이다. 지도 학습이 입력에 따른 출력을 주고 학습하게 하는 것이고, 비지도 학습은 출력 정보를 모르고 학습하게 하는 것이라면, 강화학습은 머신의 행동과 그 결과(상태)에 대해서 reward와 punishment를 부여함으로서 머신이 문제 해결 방법을 학습하게 하는 것이다.

알파고를 예로 들어보면, 알파고 제로 전까지의 기존 알파고들은 지도학습으로 바둑을 배웠다. 즉, 바둑의 대가들의 기보 수십만건을 제공받아 바둑 두는 방법을 깨우쳤다. 반면에 알파고 제로는 바둑을 배우는 단계에서 아무런 바둑 기록을 제공받지 않고, 이기게 되는 상태(reward)의 개념을 가지고 어떻게 하면 잘 둘 것인가를 스스로 학습하였다. 이것이 바로 지도학습과 강화학습의 핵심적인 차이이며, 이 때문에 알파고 제로가 학계에 한 차례 센세이션을 불러일으킨 것이다.

이러한 특징 때문에, 강화학습은 인간도 정확한 과정을 잘 모르는 문제들을 머신이 배우게 하기 좋다. 바둑을 포함한 게임들이 그렇고, 복잡하게 얽혀있는 교통체증을 해결하기 위한 교통 시스템 역시도 강화학습의 좋은 대상이 된다.

2. Reinforced Learning

강화학습의 핵심 키워드 세가지를 먼저 알아보자.

  1. State: 현재, 과거, 미래의 특정 상태. 아래 바둑판 각각이 하나의 상태이다.
  2. Action: 한 상태에서 다른 상태로 전이되기 위한 행동. 아래 바둑판 제일 왼쪽 상태에서 바로 오른쪽 상태로 가기 위해서는 검은 바둑돌을 한 점에 놓는 행동이 필요하다.
  3. Reward: 한 상태에서 행동을 취하고 다른 상태로 되었을 때 받는 보상. 보상은 +일 수도, -일 수도, 0일 수도 있다.

alt text

이 세가지를 반복해가며 머신이 원하는 최종 상태(높은 보상을 받을 수 있는 상태)에 도달하는 최적의 방법을 찾도록 하는 것이 강화 학습의 핵심이다. 이것은 간단해보이지만, (3가지 내용이 조합된 컴비네이션이다) 사실 제대로 강화학습을 이해하기 위해서는 조금 더 다룰 내용들이 있다.

강화학습을 통해 최종상태까지 가기 위해서 머신은 연속적인 선택을 하게 된다. 즉 하나의 상태에서 행동을 선택하여 다음 상태에 해당하는 보상을 받고, 새로운 상태에서 다시 행동을 선택하고.. 하는 과정의 반복으로 볼 수 있다는 것이다. 이러한 연속적인 과정을 어떻게 최적화할 수 있을까? 특정 상태의 보상 값을 어떻게 설정해야 좋을까? 어떤 선택이 몇십번의 선택 후에 어떤 효과를 불러일으키는지 어떻게 알 수 있을까? 이런 물음들을 해결하기 위해 우리는 Markov Decision Process (MDP)를 도입한다.

Markov Decision Processes

마르코프 결정 과정은 출력이 일부는 decision maker의 제어에, 일부는 랜덤 값에 의존하는 경우에 대한 수학적인 모델을 제공한다. 설명만으로는 어려우니까 그림1을 보자.

alt text

머신이 상태 0에서 어떤 행동 A를 취한다면 새로운 상태 1로 전이된다. 이 때, 머신은 상태 전이에 해당하는 보상인 1을 받게 된다. 이 때 행동 A 또는 B를 취하는 것은 확률에 따른다(어떤 확률인지는 뒤에서 소개한다).

따라서 다음 상태 1은 이전 상태 0과 머신의 행동 A에 영향을 받게 된다. 각 상태에서 가능한 행동이 한 가지만 존재한다면, 다시 말해 현재 상태가 과거의 상태에만 영향을 받는다면 이것은 단순한 Markov Chain2이며, 현재 상태가 과거의 상태 + 행해진 행동, 두 가지에 영향을 받는 것이 MDP이다.

위에서 설명한 강화학습의 핵심 키워드는 바로 MDP의 핵심 개념들에서 비롯된 것이다. MDP를 핵심 개념을 통해 formal하게 정의하면 다음과 같다.

  • 상태의 집합: \(S = \{s_1, s_2, ... , s_n\}\)
  • 행동의 집합: \(A = \{a_1, a_2, ... , a_m\}\)
  • 보상 함수: \(S\times A\times S\to R\)
  • 전이 함수: $$P(s_{t+1}∣s_t, a_t)

결국 MDP에서 우리의 목표는 최적의 경로 선택을 찾는 것이다. 위 그림으로 다시 올라가보자. 0부터 5까지 도달하는 방법은 아래 세 가지이다.

  1. 0 - 1 - 3 - 5 (3)
  2. 0 - 1 - 4 - 5 (12)
  3. 0 - 2 - 4 - 5 (-988)

각각의 방법을 하나의 policy 𝞹라고 하며, 결국 최적값인 policy 2를 찾아내는 것이 목표가 되는 셈이다.

Value functions

policy를 실제 머신이 처리할 수 있도록 상태와 값을 연동하는 것이 바로 value functions이다. 아래 그림을 보면 1초만에 이해가 될 것이다.

alt text

이것을 state value function이라고 한다. 식으로 나타내 보면,

\[V^\pi(s) = R(s, a, s') + V^\pi(s')\]

그런데 우리는 이미 상태, 행동들의 충분히 많은 조합을 가지고 있다. 이것만 계산해도 버거울 지경인데, state value function은 policy값을 또 끌고 들어와서 복잡하다. 하지만 이것도 결국 상태 전이와 행동에 따른 보상 값들을 가지고 계산되는 것이기 때문에, 상태와 행동만 가지고 이 함수를 단순화시켜보자.

alt text

state value function과 달리 하나의 상태에 모든 경로 값을 다 저장하는 것이 아니라, 그 상태가 선택할 수 있는 두 행동 각각에 대해 해당 행동을 선택했을 때 구할 수 있는 최적값만 표현하고 있다. 예를 들어 상태 0에서 1로 갈 때 가능한 policy는 2가지이지만, 그 중 최적 보상값인 12만 고려하여 상태에 저장한 것을 볼 수 있다. 이것이 Q function이다. 역시 식으로 나타내 보자.

\[Q(s, a) = R(s, a, s') + max_{a'}Q(s', a')\]

최적의 policy 𝞹*(s)도 우리의 value function을 가지고 표현할 수 있다.

\[\pi^*(s) = argmax_aQ(s, a)\]

짜잔! 완성! … 된 것 같지만 이 방법에는 문제가 하나 있다.

alt text

위 그림의 상태 2에서 3까지 가기 위한 최적의 policy를 위의 Q function을 이용해서 찾으면, 우리는 무한 루프에 빠진다. 상태 3으로 가는 행동 B보다 행동 A가 더 보상이 크기 때문. 이러한 문제를 방지하기 위하여 우리는 discount factor 𝞬를 도입한다.

\[Q(s, a) = R(s, a, s') + \gamma max_{a'}Q(s', a')\]

0에서 1 사잇값을 갖는 𝞬는 다음 스텝을 확인하는 것에 대한 확률값으로 MDP가 적용되는 문제들의 불확실성을 계량할 수 있게 해준다.

문제를 풀기 위해 MDP를 도입하고, 문제에 대한 식을 세웠으니, 문제를 푸는 일만 남았다.

Dynamic Programming

MDP를 실제로 풀기 위해서 자주 쓰이는 방법이 dynamic programmin(동적 계획법)이다. 동적계획법은 한 문제를 풀 때, 그 문제의 세부 문제들을 미리 다 계산하고, 그 세부 문제들의 결과들을 활용하여 재귀적으로 전체 최적값을 찾는 알고리즘이다. 따라서 greedy와는 다르게 부분 최적값에 봉착하는 문제는 발생하지 않는다는 것이 장점. 대신 문제를 전부다 풀어보고 제일 나은 것을 선택해야하기 때문에 문제가 복잡할 경우 걸리는 시간이 지수 스케일로 폭발한다! 동적계획법은 어려운 개념이 아니니 이 정도로만 하고, 추가로 궁금하다면 여기를 참조.

MDP에 동적계획법을 적용해서 풀려면, 가능한 모든 상태에서 다음 상태로 가는 행동에 대한 보상들을 미리 다 확인해 보아야 한다. 식 4를 다시 보면, $\gamma max_{a’}Q(s’, a’)$ 이 부분에 동적계획법이 잘 녹아들어가 있는 것을 볼 수 있다. 첫번째로, 다음 상태로부터의 Q function 값을 모두 확인해서 그 중 최대값을 취한다는 것, 둘째로는 이 과정이 재귀적이라는 점에서 그렇다.

그런데 동적계획법의 단점이 여기서 문제가 된다. 우리가 강화학습으로 풀려는 문제들은 대부분 굉장히 복잡한데, 그 경우의 수를 모두 계산해서 문제를 풀겠다는 접근 방식은 한계가 있다는 것. 바둑을 보아도 수많은 수(행동) 끝에 경기에서 승리(보상)하는 경우, 어떤 행동이 어떻게 영향을 미쳤는지 알기는 굉장히 어려울 것이다. 이걸 모두 배우는 프로그램을 만든다면, 아마 그 프로그램은 지금부터 돌려도 내가 죽기 전에 다 안 끝날 것이다. 바둑에서 존재 가능한 상태(바둑판)는 한 점의 가능한 상태 (흰 돌, 검은 돌, 없음) 세 가지와 바둑판 위에 돌을 놓을 수 있는 점의 개수를 고려하면 $3^{19^2} \approx 1.7 \times 10^{172}$이다. (이 숫자가 가늠이 안 된다면, 관측 가능한 우주의 추정 원자 수 $10^{80}$과 비교해보자.)

그래서 강화학습에서는 discount function, 𝞬값을 도입하여 다음 스텝들에서 영향 받는 정도를 제한하고, 더 나아가 고려하는 스텝 수 자체를 제한하기도 한다. 이것은 완전한 동적계획법은 아니지만 그것에 기반을 두고 있기 때문에 강화학습을 Approximate Dynamic Programming (ADP)라고도 부른다.

3. Q-Learning

Q function에 관한 식 4로 우리가 필요로 하는 건 다 배운 것 같은 느낌이지만, 사실 막상 적용해보려면 문제에 봉착한다. Reward를 어떻게 정할 것인가? 한 행동마다 다른 보상 값을 부여해야 할까? 새로운 상태를 배워가면서 value function을 업데이트해야 하지 않을까? 이 문제를 해결하기 위한 시도가 크게 네가지 있었다.

  1. Certainty equivalence: 전체 MDP를 고려하여 최적 value function을 직접 계산하고 그로부터 최적 policy를 계산하는 알고리즘.
  2. TD 𝞴 learning: MDP를 직접 고려하지 않고 value function (state)을 직접 계산하여 최적 policy를 찾는 알고리즘.
  3. SARSA: value function과 policy를 동시에 배워가는 알고리즘. Q function을 사용하며 경험에 의거해 Q값을 업데이트하고, 이 값은 exploration policy에 영향을 받음.(off-policy)
  4. Q-learning: value function과 policy를 동시에 배워가는 알고리즘. Q function을 사용하며, 경험이 축적되는대로 Q값을 업데이트하며, 이 값은 exploration policy에 영향을 받지 않음.(on-policy)

간단한 특성은 적어두었지만, 각각의 디테일을 여기서 모두 다루기는 (내가) 힘들어서, 여기서는 Q-learning만 공부해 본다. 그 전에 간단하게 짚고 넘어갈 부분들이 있다.

Reward whole policies?

모든 보상 값을 하나하나 다 정해야 하는가? 어떤 기준으로? 바둑에서 다음에 두는 수가 어떤지에 따라 현재 수의 보상값은 달라질 수 있는데, 그럼 모든 policy 내의 모든 행동들의 보상값을 모두 추정해야 하는가?

더 깊이 생각해보지 않아도 하고 싶지 않다는 부정적인 감정을 느낄 수 있다. 이것을 극복하기 위해 정말 달성해야 하는 goal에만 reward를 부여하고 (하지 말아야 할 것이 있다면 penalty를 부여한다) 나머지 값들은 별도로 reward를 부여하지 않는 방법도 있고, 사람의 개입 없이 점차 증가하는 reward를 부여하는 방법도 있다. 이 디자인 이슈는 실제 모델을 디자인할 때 정말 잘 고민해야 할 부분이다.

여기서는 일단 goal 외에는 모두 0의 보상을 부여하는 방식을 택한다. 그런데 그럼 또다른 문제가 발생한다. reward를 모르는데 다음 값을 어떻게 선택하는가? 항상 랜덤인가?

식 4를 다시 보면, 최종 보상에 한 번 도달하면 그 값이 이전 Q function 값에 영향을 미치고, 다시 그 값이 그보다 더 전의 Q function 값에 영향을 미치게 된다는 점을 알 수 있다.

여기서 또다시 문제점을 발견할 수 있다. 그럼 한 번 우연히 goal을 달성하면 주구장창 그쪽으로만 선택하지 않겠는가? 이 문제는 어떻게 회피할 수 있을까?

Exploration vs. Exploitation

탐험할 것이냐, 이용할 것이냐, 그것이 문제로다.

햄릿은 두 가지 사이에 고민을 했지만, 우리는 수없이 계산을 반복해주는 기계를 쓰는 사람들. 고민 따위 없다. 확률 값을 넣어서 좋은 값 위주로 선택하다가 가끔씩 탐험도 좀 해서 새로운 길도 개척하도록 하면 그만이다. 마냥 탐험만 하게 해도 문제는 있다. 완전 랜덤으로 값을 구해보겠다는 것과 다를 바가 없기 때문. 하지만 적절한 exploration / exploitation 비를 정해서 학습을 시킨다면 머신은 효과적으로 학습이 가능할 것이다. 이 두 가지는 사실 서로 상충되기 때문에 우리는 통상 exploration-exploitation trade-off라고 부르고, 이 비율을 잘 정하는 것이 러닝을 유도하는데 굉장히 중요한 부분이 된다.

위에서 SARSA는 off-policy, Q-learning은 on-policy라고 하였는데, 이 차이가 바로 exploration policy를 어떻게 정하느냐에 의해 비롯된다. exploration이 지금의 policy를 준수해야하면, 다시 말해, exploration 단계 또한 우리가 원하는 final policy에 가까워져야 하면 on-policy인 것이고, exploration은 지금까지의 policy와 아무 관련없이 무작위로 수행될 수 있다면 off-policy인 것이다. 사실 부분 최적값이 존재할 것이 확실시 되는 실제 세계의 문제들에서는 on-policy는 빠르긴 하지만 부분 최적값에 수렴하기 좋은, 다시 말해 지금 당장은 이득을 보는 것 같지만 결국은 게임에서 질 가능성 높은 수로 머신을 유도하게 된다. 반면, off-policy는 러닝 과정이 좀더 지난할 수는 있지만, 파라미터를 잘 설정하면 부분 최적값에 봉착하지 않는다.

Epsilon-greedy strategy

exploration과 exploitation의 비율을 𝞮 (epsilon)으로 정하여 이에 따라 pseudo-greedy 탐색을 하는 전략이 바로 epsilon-greedy strategy다. exploitation은 1-𝞮의 비율로 선택되고, exploration (greedy)은 𝞮의 비율로 선택된다. 일반적으로 𝞮=0.1 이다. 이름은 거창하지만 사실 별 거 없다.

Q-learning algorithm

드디어 Q-learning까지 왔다. 이 알고리즘은 다음의 스텝을 따른다.

  1. Q(s,a)를 (보상에 영향을 미치지 않도록) 작은 값으로 초기화 한다.
  2. 현재 상태 s를 관찰 (보상, 선택 가능한 행동)한다.
  3. 𝞮 greedy 비율로 행동 a를 선택한다.
  4. 다음 상태 s’를 관찰한다
  5. 선택을 바탕으로 Q(s,a)를 업데이트 한다.
  6. s를 s’로 업데이트하고 2부터 다시 반복한다.

이 스텝에서 중요한 것은 Q(s,a)의 업데이트 방법이다. 기본적으로 Q function 식(식 4)에 기반을 두고 있다. 다음 식을 보자.

\[Q(s,a) \leftarrow (1-\alpha)Q(s,a) + \alpha(r + \gamma max_{a'}Q(s',a'))\]

여기서 𝞪는 학습률이다. 𝞪가 작을수록 과거의 지식을 많이 활용하는 것이고, 클수록 새로 배우는 것을 더 많이 활용하는 것이다. 이 값을 잘 정하는 것도 중요하겠다.

𝞪와 𝞮, 𝞬를 잘 정하기만 하면, 이 알고리즘을 문제 풀이에 바로 적용하여 사용할 수 있다.

4. 정리

강화학습은 경우에 따라 유용한 문제해결 수단이나, 몇 가지 점을 유의하여 사용해야 한다.

  1. 파라미터를 잘 정하기 위해 머신 트레이닝 경험이 충분히 필요하다.
  2. 러닝에 시간이 오래 걸린다.
  3. 무작위 값들을 무작정 사용하는 것은 전혀 효과적이지 않다.
  4. MDP 프레임웤에 맞는 경우3에만 사용해야 한다.

뿐만 아니라 여기서 다루지 않은, 개별 행동들을 평가하지 않고 전체 policy에 대한 보상을 부여하는 강화학습 방법도 있으니, 관심이 있다면 더 찾아보는 것도 좋겠다.


I acknowledge that contents of this posting is based on 2017 Fall EECS349 course by Prof. Bryan Pardo at Northwestern Universtiy. I post this for the learning purpose of myself.


  1. These graphs are taken from the slide in 2017 Fall EECS349 class at NU. ↩

  2. MDP를 살펴보기 전에 Markov chain에 대해서 먼저 간단하게 이해할 필요가 있다. 마르코프 연쇄까지는 여기서 다루지 않는다. ↩

  3. 마르코프 특성을 만족하는지 확인해야 한다. 2번 각주의 링크 참조. ↩