[카카오AI리포트]알파고를 탄생시킨 강화학습의 비밀
강화학습(reinforcement learning) 스터디(1편)
AI 기술은 지금 이 순간에도 다양한 분야에서 진화를 거듭하고 있습니다. 자율주행, 추천 기술, 음성인식, 컴퓨터 비전 등 분야별로 다양한 AI 기반 기술들이 비약적인 발전을 이뤄가고 있습니다. 기계학습의 한 유형인 강화학습은 ‘알파고’ 덕분에 인공지능에 관심이 있는 사람들은 대부분 한 번쯤 들어봤을 법한 단어가 되었습니다. 이번 ‘카카오 AI 리포트' 4호에서는 알파고를 무적으로 만든 ‘강화학습’에 대해 공부할 수 있는 기회를 마련했습니다. 우리 실생활 속으로 성큼 들어온 AI 기술들의 비밀을 함께 풀어보시기 바랍니다.
[카카오 AI 리포트] Vol. 4 는 다음 내용으로 구성되어 있습니다.
[1] Review - AI와 여성: Women in AI
01. 정수헌 : 페이페이 리의 꿈과 도전, ‘모두를 위한 AI’
02. 김대원 : 여성 AI 개발자들이 말하는 ‘AI와 나’
[2] Industry - AI 알고리듬의 비밀
03. 전상혁, 김광섭 : 내 손안의 AI 비서, 콘텐츠 추천 알고리듬
04. 최성준, 이경재 : 알파고를 탄생시킨 강화학습의 비밀 (이번글)
[3] Information
[카카오 AI 리포트] Vol. 4 전체글 다운받기
내용 중간의 [ ] 는 뒷부분에 설명 및 관련 문헌의 소개 내용이 있음을 알리는 부호입니다. 예를 들어, [1]에 대한 설명은 '설명 및 참고문헌'의 첫 번째에 해당합니다.
2016년 자동차와 IT 업계의 화두 중 하나는 무인자동차였다. 도요타, 다임러-벤츠 등 굵직굵직한 자동차 제조 회사들뿐 아니라 테슬라, 구글, 애플등과 같은 IT회사들도 모두 무인 자동차를 연구 개발 중에있다. 만약 이들 회사에 자극을 받으신 회장님이 어느 날 갑자기 무인자동차에 탑재될 주행 알고리듬을 개발하라고 지시했다면, 어떻게 이 난관을 헤쳐나가야 할까? 테스트 드라이버 때 회장님이 직접 시승하겠다고 지시하셨다면 정말 안전하게 시험 주행을 마칠 수 있어야 한다. 위의 무인자동차용 주행 알고리듬과 연관된 인공 지능에 있어서 가장 중요한 문제 중 하나는 확률계(stochastic system)에서 순차적 의사결정(sequential decision) 문제를 푸는 것이다. 앞서 예를 든 자동차 운전을 생각해보자. 우리가 엑셀을 밟고 핸들을 돌렸을 때, 자동차는 우리가 제어하는 그대로 움직이지는 않는다. 강한 바람 등의 외인, 비포장 도로 등의 원인으로 바퀴가 미끄러질 수도 있다. 이렇듯 외부의 영향으로 자동차의 상태가 우리가 예상한 것과 일치하지 않는 상황을 확률계라 지칭한다. 또한 자동차를 안전하게 운전한다는 것은 사진을 보고 사진 속의 얼굴이 누군지 분류하는 것과는 다르다. 안전하게 운전하기 위해서는 매 순간, 연속적인 결정들을 내리고, 일련의 결정들의 결과로 얻어지는 상태들이 모두 안전해야 하는 것을 의미한다. 이번 글의 주제인 ‘강화학습(reinforcement learning)’은 확률적 의사결정(stochastic decision) 문제를 푸는 방법론들을 지칭한다. 다른 지도학습 방법론과는 차별되는 강화학습의 몇 가지 주요 특징들에 대해 알아보자.[1]
강화 학습의 의미
강화 학습을 본격적으로 다루기 전에 지도 학습(supervised learning)에 대해서 짧게 다뤄보자. 지도 학습은 학습 데이터를 통해서 유의미한 정보를 얻어내는 기계 학습 방법론에 속한다. 입력과 출력 데이터가 주어졌을 때 새로운 입력에 대한 출력을 예측하는 방법론을 지칭하며 입력과 출력 데이터가 모두 주어진 상태에서 학습을 한다고 해서 ‘지도 학습’이라 불린다. 예를 들어 강아지와 고양이 사진이 잔뜩 주어졌을 때, 새로운 사진에 있는 동물이 강아지인지 고양이인지를 맞추는 문제라 생각하면 크게 틀리지 않다. 강화 학습이 지도 학습과 대비되는 가장 큰 특징은 학습 데이터가 주어지지 않는다는 점이다. 그 대신 강화 학습 문제에 주어지는 것은 보상(reward) 함수이다. 그리고 강화 학습을 푼다는 것의 정의는 미래에 얻어질 보상값들의 평균을 최대로 하는 정책 함수를 찾는 것이다. ‘강화 학습을 푼다’의 정의는 이번 글의 가장 중요한 부분으로 다음과 같이 설명할 수 있다.
"강화 학습을 푼다는 것은 최적의 정책 함수를 찾는 것과 같다. 그리고 이 최적의 정책 함수는 불확실한 미래에 얻을 수 있는 보상 함수의 기대값을 최대로 하는 행동을 매번 고른다." 여기서 눈여겨볼 단어가 두 개 있는데 하나는 ‘미래’라는 것이고, 두 번째는 ‘기대값’이라는 것이다. 이 두 의미만 제대로 깨달아도 강화 학습에 대해서 어느 정도는 이해했다고 볼 수 있다. 연구자들은 이 강화 학습 문제를 풀기 위해서 수학적 모델을 하나 차용했는데, 그것이 바로 마코프 의사결정 과정(Markov decision process, MDP)이다. MDP는 우리가 앞서 다룬 순차적 의사결정(sequential decision) 문제를 다루기 위해 사용하는 일종의 수학적 기술 정도로 보면 될 것 같다.
마코프 의사결정 과정(Markov decision process, MDP)
MDP라는 이름만 가지고도 우리는 대략적으로 이것이 무엇인지 유추할 수 있다. MDP의 첫 번째 단어인 마코프(Markov)는 19세기 수학자 앤디 마코프(Andrey Markov)의 성을 딴 마코프 특징(Markov property)을 의미한다. 마코프 특징을 직관적으로 설명하자면 현재가 주어졌을 때, 과거와 미래가 독립적임을 의미한다. 예를 들어서 내가 내일 얻을 시험 점수는 현재 내 상태와 오늘 내가 공부하는 양에만 의존함을 의미한다. 얼핏 보면 이러한 세상이 참 아름다워 보일 수 있으나 현재 상태(지금까지 얼마나 공부를 했는지)에도 의존함을 주의하자.
물론 우리의 관심인 무인자동차는 나 자신의 상태만으로는 진정 한 의미의 최적을 알 수가 없다. 나뿐 아니라 도로 위 다른 운전자들 의 상태도 고려해야 하지만, 이 정보는 우리가 완벽히 파악할 수 없다. 이렇듯 나에게 주어진 것이 부분적인 정보라고 가정하는 MDP를 부분적으로 관찰가능한 마코프 의사결정 과정(partially observable Markov decision process, POMPD)이라 부른다. 최근 인텔에 약 17 조 원에 인수된 모빌아이는 이러한 마코프 특징을 가정하지 않고, 강 화 학습을 푸는 논문[2]을 발표하였다.
일반적인 MDP는 크게 보면 아래 네 가지로 구성된다.
1. A set of states
2. A set of actions
3. A transition function
4. A reward function
위의 네 가지를 아래의 예제를 통해 살펴보도록 하자.
MDP를 설명하는데 있어서 가장 흔하게 사용되는 예제는 아래와 같은 격자 공간 속에 로봇이 있는 상황이다.
[그림 1] 격자 세상 속의 로봇[3]위의 [그림 1]에 나와 있듯이 로봇이 있을 수 있는 상태는 12개의 격자 중 하나이고, 이것이 상태 공간(state space)이다. 각 격자에서 로봇은 상하좌우로 이동하거나 제자리에 있을 수 있고, 이 다섯 가지의 행동이 행동 공간(action space)에 해당한다. 로봇의 격자 이동이 결정된 경우에는 원하는 방향으로 이동하게 되지만, 확률적인 경우에는 로봇이 위로 이동하려고 해도, 일정 확률로 오른쪽 혹은 왼쪽으로 이동하게 된다. 이를 확률계(stochastic system)라고 하고, 아래 그림에서 왼쪽이 결정론 세계 (deterministic world), 오른쪽이 확률적 세계(stochastic world)를 나타낸다.
[그림 2]결정론적 세계(Deterministic world)와 확률적 세계(stochastic world)이렇듯 특정 상태에서 특정 행동을 했을 때, 다음 번에 도달할 상태들의 확률을 나타낸 것이 전이 함수(transition function)이다.
마지막으로 강화 학습에서 가장 중요한 보상 함수는 각 상태에 정의되는데, 위의 격자 공간에서 보석에 도달하면 +1의 보상을, 불에 도달하면 -1의 보상을 얻게 된다. 물론 조금 더 복잡한 모델에서는 각 상태에서 어떤 행동을 했을 때, 즉 R(s, a) R(s, a)에 보상 함수가 정의되기도 한다. MDP가 주어졌을 때, 강화 학습을 푼다는 것은 기대되는 미래 보상의 합(expected sum of future reward)을 최대로 하는 정책 함수를 찾는 것을 의미한다. 여기에는 여러 의미가 담겨있는데, 한 가지 중요한 점은 미래에 얻을 보상 (reward)이 포함되어 있다는 점이다. 즉 내가 현재 행동을 통해서 얻어지는 보상도 중요하지만, 궁극적으로는 현재뿐만 아니라 미래에 얻어지는 보상들도 다 고려를 해야 한다. 예를 들어서 바둑과 같은 게임을 예로 들어보면, 보상 함수는 경기가 끝나고, 계가(計家) 후에 한번 주어지게 된다. 즉 내가 현재 하는 행동의 결과가 상당히 먼 미래에 나타나게 되고, 이를 일반적으로 지연 보상(delayed return)이라 부른다. 바로 이 점이 강화 학습을 매우 어렵게 만든다. 이에 대해 자세히 살펴볼 예정이다.
다음으로 고려해야 하는 점은 우리가 확률계(stochastic system)를 가정한다는 점이다. 즉 내가 현재 어떤 행동을 한다고 해서 원하는 상태에 도달하지 못할 수도 있게 되고, 이는 같은 보상을 얻을 수 있다면, 최대한 ‘빨리’ 그 보상을 얻는 것이 더 좋음을 의미한다. 이러한 현상을 반영하는 것이 할인율(discount factor)이다. 이 값은 1보다 작은 값으로 설정되며, 시간이 지남에 따라서 얻어지는 보상에 이 값을 곱하게 된다. 만약 보상 함수에 대해 매번 보상 함수를 최대로 하는 행동을 선택하면, 그것이 최적의 정책 함수가 아닐까 하는 의문을 가질 수 있다. 하지만 이렇게 행동을 하는 것은 바둑을 둘 때 매번 상대방 돌을 잡을 수 있을 때마다 잡는 것과 비슷한 행동이다. 바둑을 잘 모르는 사람이라 하더라도, 이런 식으로 바둑을 둘 경우엔 이기기 힘들다는 것을 알고 있을 것이다. 이러한 근시안적인 방법이 잘 동작하지 않는 이유는 강화 학습의 목적이 기대되는 미래 보상의 합(expected sum of future reward)을 최대로 하는 정책 함수를 찾기 위해서이기 때문이다.
최적 정책 함수(optimal policy function)를 찾는 방법
그렇다면, 우리에게 MDP가 주어졌을 때, 최적의 정책 함수는 어떻게 찾을 수 있을까? 강화 학습을 푸는 가장 기본적인 방법 두 가지는 값 반복(value iteration)과 정책 반복(policy iteration)이다.[4] 이를 설명하기 위해서는 먼저 값(value)을 정의할 필요가 있다. 만약 우리가 특정 상태에서 시작했을 때, 얻을 수 있을 것으로 기대하는 미래 보상의 합을 구할 수만 있다면 어떨까? 즉 현재 내가 즉각적으로 얻을 수 있는 보상뿐만 아니라, 해당 상태에서 시작했을 때 얻을 수 있는 보상들의 합의 기대값을 알 수 있다면, 우리는 해당 함수를 매번 최대로 만드는 행동을 선택할 수 있을 것이고, 이렇게 최적의 정책 함수를 구할 수 있게 된다. 바로 이 미래에 얻을 수 있는 보상들 합의 기대값을 값 함수(value function), V(s)라고 부른다. 또한 비슷하게 현재 어떤 상태에서 어떤 행동을 했을 때, 미래에 얻을 수 있는 기대 보상을 행동값 함수(action value function) 혹은 Q function, Q(s,a)이라고 부른다. 값 반복(value iteration)은 바로 이 값 함수를 구하는 방법을 지칭한다. 값 함수는 현재 상태뿐 아니라 미래의 상태들, 혹은 그 상태에서 얻을 수 있는 보상을 구해야 하기 때문에 직관적으로 정의할 수 없다. 일반적으로 강화 학습에서는 이 값 함수를 구하기 위해서 벨만 이퀘이션(Bellman equation)을 활용하고, 그 식은 다음과 같다.
위의 수식은 좌변과 우변에 구하고 싶은 값 함수 V(s)가 들어가있는 재귀식(recursive equation)임을 알 수 있고, V(s)를 제외한 나머지는 MDP와 같은 내용이다. V(s)를 임의의 값으로 초기화하고, 모든상태s에대해서위의재귀식을수렴할때까지수행하면항상 최적의 V(s)를 구할 수 있다.
지금까지의 내용인 강화 학습 문제를 MDP 문제로 표현하고, 그 방법론으로 벨만 이퀘이션을 이용하여 해결하는 방식은 대부분의 교재에 나오는 내용이다. 이를 유도하는 과정에서 최적성의 원리(principle of optimality)에서 벨만 이퀘이션이 유도된다고 한 줄 적곤 한다. 최적성의 원리는 리차드 벨만(Richard Bellman, 벨만 이퀘이션의 창시자)이 정립한 내용으로, 최적의 정책 함수란, 초기 상태와 초기 행동 결정이 무엇이든지 간에 그 후에 이뤄지는 결정들이 최적의 정책 함수에서 기여를 해야한다는 내용이다.[5] 하지만 정말 ‘어떻게’ 벨만 이퀘이션이 유도되는지는 제대로 설명된 자료가 많지 않다. 신기하게도 MDP와 벨만 이퀘이션 사이의 관계는 MDP라는 최적의 정책 함수를 찾는 최적화 문제의 카루스-쿠-터커 조건(Karush–Kuhn–Tucker condition)을 통해서 유도가 가능하다. 이 과정이 상당히 흥미롭다. 먼저 MDP를 최적화 문제 형태로 써보면 다음과 같다.
최적화의 목적은 어떤 정책 함수 π(a|s)를 찾는 것인데, 그 함수가 주어진 MDP 조건에서 미래에 얻을 수 있는 보상의 할인된 합(discounted sum)의 기대값을 최대로 하게 하고 싶은 것이다. 위의 최적화 문제만 봐서는 벨만 이퀘이션과의 연결 고리가 쉽게 보이지 않지만, 위의 수식을 행렬 형태로 잘 변환한 후에 카루스- 쿠-터커 조건을 구해보면 최적의 정책 함수가 가져야 하는 조건이 바로 벨만 이퀘이션과 동일하게 된다. 또한 이 문제는 최적화에서 말하는 강한 이중성(strong duality)을 만족하기 때문에 MDP를 푸는 것과 벨만 이퀘이션을 푸는 것은 수학적으로 동치가 된다. 벨만 이퀘이션을 직접 이용해서 값 반복(value iteration) 문제를 풀어 값(value)을 구하고, 이 값을 최대로 하는 정책(policy)을 찾으면 이것이 최적의 정책이 된다. 하지만 값 함수(value function)는 MDP 문제의 해(solution)인 최적의 정책 함수를 구하기 위해서 필요한 것이지, 그 자체가 큰 의미가 있지는 않다. 앞서 강화 학습의 정의는 최적의 정책 함수를 찾는 것임을 상기하자. 그래서 직접 정책 함수를 찾는 정책 반복(policy iteration)이 등장하게 된다.
정책 반복은 값 반복과 다르게 현재 가지고 있는 정책 함수의 성능을 평가하는 정책 평가(policy evaluation)와 이를 바탕으로 정책을 개선하는 정책 개선(policy improvement)의 단계로 이뤄져 있고, 이 두 단계들을 정책 함수가 수렴할 때까지 번갈아가면서 수행한다. 일반적으로 정책 반복이 값 반복보다 빠르게 최적의 정책 함수로 수렴한다고 알려져 있다.
위에서 언급한 두 방법은 모두 모델기반 강화 학습(model- based reinforcement learning)으로 알려져 있다. 여기서 모델은 MDP에서 전이 모델(transition model)을 지칭한다. 즉 어떤 상태와 이 상태에서 어떤 행동을 한다고 했을 때, 다음 번 상태가 될 확률을 나타낸다. 얼핏 생각해서는 이 모델이 손쉽게 주어질 것이라고 예상될 수도 있다. 예를 들어 위에서 언급한 격자 공간 속에서는 각 셀에서 상하좌우로 이동을 하면 다음 번 상태가 직관적으로 유도된다. 하지만 실제 문제를 해결할 때 전이 모델은 쉽게 정의되지 않는다. 예를 들어서 강화 학습 문제를 자율주행에 적용한다고 해보자. 이 경우 MDP의 상태 공간(state space)은 어떻게 정의될까? 가장 먼저 떠오르는 것은, 자동차의 현재 위치로 정의하는 것이다. 하지만 이것은 굉장히 위험한 접근이다. 만약 MDP의 상태 공간(state space)을 자동차의 위치로 설정하게 되면 어떤 문제가 생길까? MDP에서 상태는 현재 내가 고려하고자 하는 내용들이 모두 함축적으로 담겨있는 상태이기 때문에, 내가 도로 위에서 어느 위치에 있는지, 혹은 주변 자동차들은 전혀 고려하지 않는 채 운전을 하겠다는 것과 동일한 의미이다. 그렇기 때문에 자율 주행 문제를 다룰 때 상태는 단순히 내 위치뿐만 아니라, 주변 자동차들의 상대적 위치, 도로 표지판 정보 등 운전에 필요한 모든 정보를 상태로 정의한다. 그리고 이렇게 상태 속에 여러 정보가 담겨 있기 때문에, 단순히 내가 어떤 행동을 했을 때(예를 들어, 핸들을 왼쪽으로 돌렸을 때) 미래에 내 상태가 어떻게 변하게 될지를 얻는 것은 매우 어려운 일이다.
모델 프리 강화 학습(model-free reinforcement learning)
이제부터는 이렇게 MDP에서 모델이 주어지지 않았을 때 어떻게 최적의 정책 함수를 찾아내는지 알아보도록 하자. 이러한 문제를 일반적으로 모델 프리 강화 학습(model-free reinforcement learning)이라고 부른다. 사실 여기서부터가 진정한 강화 학습의 시작이라고 생각한다.
[그림 3] 강화 학습이 가정하는 세상위의 [그림3]은 모델 프리 강화 학습에서 가정하는 세상을 그림으로 나타낸 것이다. 우리는 위의 그림 중 상단의 에이전트(agent)가 되어 앞과 동일한 기대되는 미래 보상의 합(expected sum of future reward)을 최대로 하는 정책 함수(policy function)를 찾고자 한다. 앞에서 설명했던 모델 기반 강화학습과의 가장 큰 차이는 더 이상 환경(environment)이 어떻게 동작되는지 알지 못한다는 점이다. 다시 말해서 우리는 주어진 상태에서 어떤 행동을 하고, ‘수동적으로’ 환경(environment)을 알려주는 다음 번 상태와 보상(reward)을 얻게 된다. 게임을 생각하면 이해가 쉬운데, 우리의 상태는 모니터 스크린이고, 행동은 키보드 입력에 해당한다. 우리가 모니터를 보고 어떤 행동을 하게 되면, (게임 내부 코드는 모르지만) 어떤 화면이 다음 번에 나타나고, 게임 스코어 등으로 보상을 얻을 수 있다. 이러한 모델 프리 강화 학습은 모델 기반 강화 학습에 비해 몇 가지 구별되는 특징들이 있는데, 그 대표적인 것이 바로 탐사(exploration)다. 우리는 더 이상 환경이 어떻게 동작하는지 알지 못한다. 그렇기 때문에 ‘직접’ 해보고 그 결과를 통해서 정책 함수를 점차 학습시켜야 한다. MDP 문제를 직접 푸는 모델 기반을 알지 못한다. 그렇기 때문에 ‘직접’ 해보고 그 결과를 통해서 정책 함수를 점차 학습시켜야 한다. MDP 문제를 직접 푸는 모델 기반 강화학습은 우리에게 마치 세상에 대한 모든 설명(description)을 주고 문제를 푸는 것과 같다. 그렇기 때문에 직접 해보지 않아도, 최적의 솔루션을 얻을 수 있다. 하지만 모델 프리 강화 학습에서는 그렇지 않다. 우리가 세상과 직접 맞닥뜨려서 행동을 해보고, 그 행동의 결과인 보상만을 받아야 한다.
[그림 4] 모델 기반 강화 학습(Model-based RL)과 모델 프리 강화 학습(Model-free RL)위의 [그림4]와 같이 모델 기반 강화 학습은 행동을 직접 해보지 않아도, 어디가 좋고, 어디가 나쁜지 알 수 있지만, 모델 프리 강화 학습은 직접 해보고 난 후에야 결과를 알 수 있다. 이 경우에는 새로운 것을 탐사하는 것이 상당히 중요한 이슈가 된다. 내가 현재까지 알고 있는 사실을 좀 더 파고 들어서 더 좋은 결과를 얻으려고 하는 것을 개척(exploitation), 새로운 것들을 시도하는 것을 탐사(exploration)라 하고, 이 둘 사이를 잘 조정하는 것을 개척과 탐사의 트레이드오프(exploitation and exploration tradeoff)라 한다. 실제 문제에 강화학습을 적용할 때 매우 중요한 부분이다.
이렇게 정의된 모델 프리 강화 학습을 어떻게 풀 수 있는지 생각해보자. 앞서 모델 기반 강화 학습에 사용된 벨만 이퀘이션을 적어보면 다음과 같다.
위의 수식에서 T(s,a,s′), 바로 이 부분을 우리가 모르기 때문에 벨만 이퀘이션을 직접 활용할 수는 없다. 정책 평가는 위에서 a를 π(s)로 치환해, 주어진 π를 평가하는 방법론이다. 이 수식을 다시 한번 적어보면 아래와 같다.
이 수식을 잘 들여다보면 새로운 V(s)에 대한 업데이트(update)는 R(s,π(s),s′)+γV(s′)의 가중치의 합(weighted sum)으로 볼 수 있다. 그리고 가중치에 해당하는 T(s,π(s),s′)는 사실 우리가 모르긴 하지만, 만약 우리가 다음 상태(state)인 s′이 이 T라는 모델에서 나왔다면, 우리는 이 가중치 합을 표본 평균(sample mean)으로 대체할 수 있게 된다. 이런 식으로 벨만 이퀘이션을 표본화(sampling)로 대체하는 방법론 중 하나가 temporal ifference(TD) 학습(learning)이다.
TD 학습의 제일 중요한 철학 중 하나는 모든 경험을 통해서 학습을 하자는 것이다. MDP에서 경험은 내가 어떤 상태 s에서 주어진 정책 함수를 통해서 어떤 행동을 하고(a=π(s)), 그리고 그 결과로 다음번 상태 s′과 보상 r을 받는 것을 의미한다. 그리고 이런 (s,a,s′,r)들로 이뤄진 경험들이 누적되었을 때, 이 데이터들을 바탕으로 값 함수(value function) V(s)와 행동 값 함수(action value function) Q(s,a)를 학습하게 된다.
구체적으로 TD 학습을 하면 값을 구할 때, 지수이동평균(exponential moving average, EMA)을 활용한다. 즉 나에게 새로운 값에 대한 추정값이 들어오면 이를 직접 사용하는 것이 아니라 기존 값과 α의 비율로 섞은 후에 업데이트하는 식이다. 정리해보자면 모델프리 강화학습에서 정책 평가는 다음과 같다.
더 이상 모델 T(s,a,s′)이 필요 없기 때문에 모델 없이도 주어진 정책 함수를 샘플링을 통해서 구할 수 있다. 하지만 이 방식엔 치명적인 단점이 하나 존재한다. 그것은 우리가 현재 가지고 있는 π에 대한 값 함수(value function) Vpi(s)를 구했다치더라도 이를 가지고 더 나은 정책 π′를 구할 수 없다는 것이다. 이는 내가 어느 상태가 좋은지는 분명 알고 있는데, 그 상태로 ‘어떻게’ 가야 하는지를 모르는 것과 같다. 대표적인 예가 루빅스 큐브일 것이다.
[그림 5] 루빅스 큐브분명 모든 면이 같은 색을 갖는 상태가 가장 좋은 상태임을 알고 있지만, 우리가 가지고 있는 값 함수 V(s)는 어떤 행동을 해야지 특정 상태로 가는지를 알 수 없기 때문에 좋은 상태로 ‘어떻게’
가야 하는지는 알 수가 없다. 하지만 행동 값 함수 Q(s, a)를 구할 수 있다면 얘기가 달라진다. 이 경우는 각 상태에서 어떤 행동을 했을 때, 얻을 수 있는 기대되는 미래 보상의 합(expected sum of future reward)을 구하기 때문에, 모델 없이도 최적의 행동을 구할 수 있다. 벨만 이퀘이션을 Q(s, a)에 대해서 구한 식은 다음과 같다.
바로 위의 수식을 이용해서 행동 값 함수 Q(s,a)를 업데이트 할 수 있다. 물론 위의 수식에 있는 T를 표본 추정(sample estimate)으로 교체할 수 있고, 이렇게 하면 다음과 같은 수식을 얻을 수 있게 된다.
위의 수식을 이용해서 강화 학습 문제를 푸는 것을 off-policy learning 혹은 Q러닝(Q-learning)이라고 한다. 위의 수식을 이용해서 Q함수를 업데이트하기 위해서 우리에게 필요한 것은 (s,a,s′,r)들의 경험이다. 즉 어떤 상태에서 어떤 행동을 하고, 다음 번 상태를 관측하고, 이때 얻어지는 보상까지만 있으면 위의 수식을 이용해서 Q함수를 구할 수 있다. Q러닝이 가지는 장점은 모델을 모르는 상태에서도 최적 정책 함수(optimal policy function)를 구할 수 있다는 점이다. 그리고 Q함수의 정의에 따라서 최적 정책(optimal policy)은 다음과 같이 구해진다.
여기서 증명을 하지는 않겠지만, (s,a,s′,r)에 있어서 우리가 각 상태에서 임의의 행동을 하면서 데이터를 수집해도, 이러한 경험들로 얻어지는 Q(s,a)는 항상 최적의Q(s,a)로 수렴하게 된다.[6] 내가 항상 임의의 행동을 하면서 경험을 수집해도 이런 엉망인 데이터로 얻어지는 Q(s,a)는 항상 최적의 값으로 수렴하고, 우리는 항상 최적의 정책 함수를 찾을 수 있게 된다. 그리 직관적이지는 않지만 이것은 증명된 사실이다. Q러닝이 절대 만능은 아니다. 모델 프리 강화 학습의 가장 큰 단점은 탐사(exploration)이다. 강화 학습 특징상 보상을 마지막에 한번, 혹은 띄엄띄엄 주는 경우가 있다. 이러한 경우에 우리의 경험이 유의미한 보상이 있는 지역을 가보지 못했다면 절대로 올바른 정책을 얻을 수가 없다. 이러한 탐사가 갖는 어려움은 상태 공간(state space)이 커짐에 따라서 더 부각된다.
이제부터 이러한 Q러닝을 딥러닝 기법과 결합한 방법론들을 살펴볼 것인데, 딥러닝과 강화 학습을 결합한 딥강화 학습(deep reinforcement learning, DRL)에서 가장 중요한 것 중 하나가 이 탐사(exploration)를 얼마나 잘 하는가라고 해도 전혀 부족함이 없을 것이다. DRL은 크게 두 가지 관점에서 바라볼 수 있다. 하나는 DeepMind사에서 발표해 유명해진 DQN이란 방법론이고, 다른 하나는 정책 경도(policy gradient) 방법론이다. 물론 각 방법마다 장점과 단점이 명확히 있다. 이제부터 하나씩 알아보도록 하자.
먼저 DQN에 대해서 살펴보자.[7] DQN은 현재의 DeepMind사를 최고의 AI회사로 만들어준 알고리듬이라 할 수 있다. 딥마인드의 알파고는 작년 이세돌과의 대국에 이어 커제와의 대국에서도 승리하였다. 만약 DQN이 없었다면 현재의 딥마인드도 없었을 수 있고, 현재의 알파고가 없었을 수도 있다(그리고 미래의 스카이넷도...).
사실 강화학습의 알고리듬적 관점에서 DQN은 그다지 새로울 것은 없다. 앞서 살펴본 Q러닝의 수식을 다시 한번 살펴보자.
위 수식이 가지는 가장 큰 장점이라면 우리가 환경(environment)에 대한 그 어떤 정보 없이도, 어떤 시뮬레이터나 프로그램을 통해서 구할 수 있다면, Q함수에 대한 업데이트를 할 수 있다는 점이다.
사실 이것은 생각보다 엄청난 의의를 가지고 있다. 왜냐하면 RL이 기존의 SL(지도학습)에 비해서 가지는 어려움이 기대되는 미래 보상의 합을 고려한다는 점인데, 위의 수식을 통해 단순히 하나의 경험만으로도 Q함수를 업데이트시킬 수 있다는 것이다. 게다가 (s,a,s′,r)에서 (s,a)를 고를 때 임의의 행동 a를 매번 고른다 하여도 무한한 시간이 흐른 뒤에 Q(s,a)는 항상 최적의 행동 값 함수(action value function)로 수렴한다는 점 역시 아주 좋다.
위 수식의 우변은 만약 우리가 현재 Q(s,a) 함수를 안다면 손쉽게 구할 수 있다(max a′Q(s′,a′) 을 구하기 위해서는 가능한 행동 a의 수가 유한해야 한다. 다시 말해 모든 가능한 행동을 다 집어 넣고, 제일 큰 Q값이 나오는 행동을 고르면 된다) 그리고 좌변의 Q(s,a)를 어떤 입력 (s,a)에 대한 Q 함수의 출력값이라 하고, 우변을 해당 입력에 대한 목적(target)이라고 본다면 위의 Q함수에 대한 벨만 이퀘이션은 우리가 SL에서 많이 사용하는 회귀 함수(regression function)에 대한 입출력 쌍을 만들어주는 것으로 해석할 수 있다(다음 호에서 계속됩니다).
글 | 최성준 : sungjoon.choi@cpslab.snu.ac.kr
서울대 전기 컴퓨터 공학부를 졸업하고, 동 대학원에서 박사 과정 중에 있다. 학부 때는 리눅스 커널을 열심히 팠었고, 회사에서 청소 로봇을 만들기도 하다가, 대학원에 와서는 기계학습과 로보틱스를 결합하는 연구를 진행하고 있다. 주로 연구하는 분야는 강화 학습과 모방 학습으로 비슷한 분야의 연구자들을 항상 찾고 있다(연구 얘기는 언제든 환영입니다). 주된 업무는 크게 두 가지로 나눌 수 있는데, 하나는 논문을 읽고 쓰는 것이고 다른 하나는 영수증 및 서류 처리이다. 아, 그리고 가끔씩 회사원들을 상대로 딥러닝 수업을 하기도 한다. 박사 졸업이 가까워짐에 따라 페이스북에 자주 출몰하며 최근 들어 그 정점을 찍고 있다.
글 | 이경재 : kyungjae.lee@cpslab.snu.ac.kr
서울대 전기 컴퓨터 공학부를 졸업한 뒤, 동 대학원 석박사 통합과정으로 입학하였다. 현재는 박사과정에 있으며, 주 연구 분야는 모방학습과 지능형 로보틱스이다. 좀 더 세부적으로는 역 강화 학습을 연구하고 있다. 나름 재미있는 분야라고 생각해서 시작했는데 한국에서는 비슷한 연구를 하는 연구자를 만나기 어려운 것 같아 아쉽다. 관심 있는 사람이나 이 연구를 하고 있는 사람과의 만남이라면 언제든 환영이다. 한동안 군대 문제를 해결하기 위해 연구를 접고 영어공부에 매진했으나 영어실력은 그대로라고 한다. 최근 다시 연구를 시작하였으며 인공지능 및 로보틱스 분야의 많은 사람들과 교류하고 싶다.
[1] 참고 | Andrew Ng, "Shaping and policy search in Reinforcement learning", PhD Thesis, 2003
[2] 논문 | Shai Shalev-Shwartz, Shaked Shammah, Amnon Shashua, "Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving", ArXiv, 2016
[3] 자료 | UC Berkeley CS188 Intro to AI 수업 자
료, http://ai.berkeley.edu/lecture_videos.html
[4] 논문 | Sutton, Richard S., and Andrew G. Barto. "Reinforcement learning: An introduction", Cambridge: MIT press, 1998.
[5] 책 | Richard Bellman, "Dynamic Programming". Princeton University Press, 1957
[6] 논문 | Steven Bradtke and Michael Duff "Reinforcement learning methods for continuous-time Markov decision problems." NIPS, 1995
[7] 논문 | Mnih, Volodymyr, et al. "Human-level control through deep reinforcement learning." Nature, 2015
[ 카카오 AI 리포트 Vol. 4 목차 ]
[1] Review - AI와 여성: Women in AI
01. 정수헌 : 페이페이 리의 꿈과 도전, ‘모두를 위한 AI’
02. 김대원 : 여성 AI 개발자들이 말하는 ‘AI와 나’
[2] Industry - AI 알고리듬의 비밀
03. 전상혁, 김광섭 : 내 손안의 AI 비서, 콘텐츠 추천 알고리듬
04. 최성준, 이경재 : 알파고를 탄생시킨 강화학습의 비밀 (이번글)
[3] Information
