§ 1TD-Gammon — 스스로 두며 배우다
지금까지 강화학습의 가장 인상적인 응용 하나는 Gerald Tesauro의 백개먼 프로그램 TD-Gammon이다(1992~2002). 백개먼에 대한 지식이 거의 필요 없었음에도, 극도로 잘 배워 세계 그랜드마스터 수준에 근접했다.
백개먼은 강화학습에 좋은 부합이다. 약 1020개의 가능한 위치 — 조회 테이블은 불가능하다. 전형적 주사위 결과마다 20가지 정도의 수가 있고, 미래 수를 고려하면 게임 트리의 유효 분기 계수는 약 400 — 체스의 휴리스틱 탐색 방법으로는 너무 크다. 그러나 게임 상태는 항상 완전히 관찰 가능하고, 게임은 일련의 위치를 거쳐 한쪽의 승리로 끝난다.
TD-Gammon은 비선형 TD(λ)를 썼다. 표준 다층 인공신경망(ANN)으로 가치 함수 v̂(s,w) — 상태 s에서 시작하는 승률 — 을 표현하고, 보상은 승리하는 시간 스텝을 제외한 모든 곳에서 0으로 두었다. TD 오차는 역전파 알고리즘으로 가중치 전체에 전파되었다.
Tesauro는 학습 중인 플레이어를 자기 자신과 두게 해 끝없는 게임 시퀀스를 얻었다. 수를 고를 때 TD-Gammon은 가능한 20가지 후상태(afterstate)를 검토하고, 신경망에 각각의 가치를 묻고, 가장 높은 가치의 위치로 가는 수를 골랐다.
가중치는 작은 무작위 값에서 출발했다 — 초기 평가는 완전히 자의적이었고 초기 게임은 수천 수가 걸리기도 했다. 그러나 자기 대국 약 30만 게임 후, TD-Gammon 0.0은 — 백개먼 지식이 본질적으로 0이었음에도 — 광범위한 지식을 손으로 넣은 이전 최고 프로그램과 대등하게 두었다.
| 버전 | 은닉 단위 · 훈련 게임 | 상대 · 결과 |
|---|---|---|
| 0.0 | 40 · 30만 | 다른 프로그램 — 최고와 동점 |
| 1.0 | 80 · 30만 (전문 특징 추가) | 인간 전문가와 잘 경쟁 |
| 2.1 | 80 · 150만 (2단 탐색) | Robertie — 40게임 +1점 |
| 3.0 | 160 · 150만 (3단 탐색) | 세계 최강 인간 수준에 근접/초과 |
§ 2사무엘의 체커, 그리고 Watson의 베팅
TD-Gammon의 중요한 선례는 Arthur Samuel의 체커 플레이 프로그램(1959, 1967)이다. 사무엘은 휴리스틱 탐색과 — 우리가 지금 시간차 학습이라 부르는 것 — 을 효과적으로 쓴 최초의 인물 중 하나다. 1952년 IBM 701에 작성된 이 프로그램은 1956년 텔레비전에 시연되었다.
사무엘의 프로그램은 각 위치에서 미니맥스 선행 탐색을 하고, 최종 위치를 선형 함수 근사("점수 다항식")로 평가했다. 두 학습 방법 중 "일반화에 의한 학습"은 — Tesauro가 TD-Gammon에서 쓴 것과 개념적으로 동일하게 — 각 수 후 가치를 다음 위치에서 시작된 탐색의 미니맥스 가치 쪽으로 갱신했다.
IBM Watson은 2011년 퀴즈쇼 Jeopardy!에서 인간 챔피언을 이겼다. 그 승리는 자연어 능력만이 아니라 정교한 의사결정 — 특히 데일리 더블(DD) 베팅 — 에 의존했다. DD는 플레이어가 베팅액을 정하고, 맞히면 따고 틀리면 잃는다.
왜 TD-Gammon식 자기 대국을 쓰지 않았나? Jeopardy!는 불완전 정보 게임이다 — 상대가 각 카테고리에 얼마나 확신하는지 알 수 없다. 자기 대국은 상대와 같은 패를 들고 포커를 치는 것과 같았을 것이다.
그래서 Watson 팀은 약 30만 개 문제의 아카이브에서 인간 상대 모델(평균/챔피언/그랜드 챔피언)을 만들었다. 행동 가치를 최대화하면 "경악할 위험"이 생겨, 후상태 표준편차의 작은 분수를 빼 위험을 줄였다. 휴리스틱 베팅의 승률 61%가 학습된 가치로 64%, 실시간 신뢰도로 67%까지 올랐다.
§ 3DRAM 메모리 제어 최적화
강화학습은 게임 밖에서도 일한다. Ipek, Mutlu, Martinez, Caruana(2008)는 강화학습 메모리 컨트롤러를 설계했다 — 컴퓨터의 주 메모리인 DRAM에 대한 읽기/쓰기 요청을 스케줄링하는 칩 위의 에이전트다.
기존 컨트롤러의 한계는 — 과거 경험을 활용하지 않고 스케줄링 결정의 장기적 결과를 고려하지 않는다는 것이다. 같은 행이 열려 있을 때의 읽기/쓰기는 빠르지만(행 국소성), 다른 행으로 가려면 사전충전과 활성화 명령이 더 필요하다. 즉각 보상이 없는 행 명령을 지금 선택해야 나중에 보상받는 읽기/쓰기를 할 수 있다 — 전형적인 지연된 보상 문제다.
상태 — 트랜잭션 큐의 내용(읽기/쓰기 요청 수 등 6개 정수 특징). 행동 — 사전충전, 활성화, 읽기, 쓰기, NoOp. 보상 — 읽기/쓰기 행동에 1, 그 외 0(외부 데이터 버스로 데이터를 전송하는 것만 처리량에 기여하므로).
스케줄링 에이전트는 Sarsa로 행동 가치를 학습했고, 타일 코딩으로 선형 함수 근사를 구현했다. 결정적으로 — 타이밍·자원 제약을 위반하는 행동을 허용 행동 집합 A(St)에서 미리 배제해, 탐색이 물리 시스템의 무결성을 위협할 수 없게 했다.
결과 — 학습 컨트롤러는 9개 작업 부하에서 표준 FR-FCFS 정책보다 평균 19% 빨랐고, 모든 제약을 무시하는 이상적 컨트롤러와의 격차를 27% 좁혔다. 온라인 학습은 고정 정책보다 8% 더 나았다.
§ 4인간 수준 비디오 게임 — DQN
강화학습을 실제 문제에 적용할 때 가장 큰 도전은 — 가치 함수와 정책을 어떻게 표현할지다. 대부분의 성공적 응용은 인간의 지식으로 세심하게 설계한 특징 집합에 크게 의존했다. TD-Gammon 0.0이 원시 보드만으로 이전 최고 수준에 닿았지만, 인간 전문가를 잘 상대한 것은 전문 특징을 더한 1.0이었다.
구글 딥마인드 팀(Mnih 등, 2013, 2015)은 심층 신경망이 그 특징 설계 과정 자체를 자동화할 수 있음을 인상적으로 시연했다. 그들의 에이전트 DQN(Deep Q-Network)은 Q-학습을 심층 합성곱 신경망과 결합한다.
DQN은 게임 에뮬레이터와 상호작용해 49개의 서로 다른 아타리 2600 게임을 배웠다. 게임마다 다른 정책을 배웠지만(학습 전 가중치를 무작위 재설정), 모든 게임에 동일한 원시 입력, 네트워크 구조, 매개변수를 썼다.
입력은 게임 화면 픽셀뿐 — 게임별 특징은 없다. 심층 합성곱 신경망(3개 합성곱 층 + 완전 연결 층 + 출력 18단위)이 모든 게임에 공통인 원시 픽셀을, 높은 점수에 필요한 행동 가치 표현으로 바꾸는 법을 스스로 배웠다. 보상은 게임 점수 변화 — 증가 +1, 감소 −1, 그 외 0 — 로 표준화했다.
경험 재생(experience replay) — 매 스텝의 경험 (St,At,Rt+1,St+1)을 재생 메모리에 저장하고, 갱신할 때 거기서 무작위로 미니배치를 뽑는다. 각 경험을 여러 번 재사용해 효율적이고, 연속 갱신의 상관을 깨 분산을 줄인다. Q-학습이 비정책(off-policy)이라 연결된 궤적을 따를 필요가 없어 가능한 일이다.
대상 네트워크(target network) — Q-학습 목표가 갱신 중인 바로 그 가중치에 의존하면 진동할 수 있다. 그래서 가중치를 별도 네트워크에 복사해 C번 갱신 동안 고정하고, 그 출력을 목표로 쓴다 — 학습이 더 단순한 지도학습에 가까워진다.
두 기법 모두 단독으로도 성능을 크게 올렸고, 함께 쓰면 극적으로 올랐다. DQN은 다수의 게임에서 인간 수준 이상에 도달했다.
§ 5알파고와 알파고 제로 — 바둑을 정복하다
고대 게임 바둑은 수십 년간 인공지능의 도전 과제였다. 19×19 격자, 위치당 합법 수 약 250(체스는 35), 게임당 약 150수(체스 80) — 그러나 탐색 공간 크기가 진짜 어려움은 아니다. 진짜 장벽은 — 좋은 위치 평가 함수를 정의하기 어렵다는 것이다. Müller(2002)는 "바둑에 대한 단순하면서 합리적인 평가 함수는 결코 발견되지 않을 것"이라 썼다.
주요 진전은 바둑 프로그램에 MCTS(몬테카를로 트리 탐색)를 도입한 것이었다. 8장에서 보았듯 MCTS는 전역 평가 함수를 학습·저장하지 않는 결정 시점 계획 절차다 — 각 수마다 전체 게임의 몬테카를로 시뮬레이션을 많이 실행하고, 트리의 에지 통계로 안내되며 점진적으로 탐색 트리를 키운다. 그래도 마스터 수준은 멀었다.
딥마인드 팀(Silver 등, 2016)은 — 심층 신경망, 지도 학습, MCTS, 강화학습을 결합한 — AlphaGo로 그 장벽을 돌파했다. 유럽 챔피언 Fan Hui를 5:0으로, 이어 18회 세계 챔피언 이세돌을 4:1로 이겼다.
SL 정책 네트워크 — 인간 전문가 수 3천만 개에서 지도 학습. 57.0% 정확도(이전 최고 44.4%).
RL 정책 네트워크 — SL 정책으로 초기화한 뒤, 정책 경사 강화학습으로 자기 자신의 옛 버전과 대국하며 개선. SL 정책을 80% 이상 이김.
가치 네트워크 — RL 정책으로 둔 자기 대국 데이터에서 몬테카를로 정책 평가로 훈련. 위치의 승리 확률을 추정.
롤아웃 정책 — 빠르지만 단순한 선형 네트워크. APV-MCTS 실행 중 빠른 게임 시뮬레이션에 사용.
APV-MCTS는 새 노드의 가치를 두 방식으로 섞었다 — v(s) = (1−η)vθ(s) + ηG, 가치 네트워크 평가와 롤아웃 리턴 G의 혼합. 최고의 플레이는 η = 0.5 — 둘을 결합할 때였다.
AlphaGo Zero(Silver 등, 2017)는 게임 규칙 외에는 인간 데이터나 지도를 일절 쓰지 않았다(이름의 Zero가 그 뜻). 보드의 원시 표현만 입력으로, 순전히 자기 대국 강화학습으로 배웠다.
AlphaGo와의 핵심 차이 — AlphaGo Zero는 학습 내내 수 선택에 MCTS를 썼다(AlphaGo는 학습 후 실제 플레이에만). 단 하나의 신경망("두 개의 헤드" — 수 확률 p와 가치 v를 출력)을 쓰고, MCTS는 롤아웃 없이 더 단순했다.
이것은 정책 반복의 한 형태다 — MCTS가 네트워크의 정책 p를 개선해 새 정책 π를 반환하고, 네트워크는 p를 π 쪽으로, v를 실제 승자 z 쪽으로 갱신한다. Silver 등의 말로 — "MCTS는 강력한 정책 개선 연산자로 볼 수 있다."
약 490만 자기 대국 게임(3일) 후, AlphaGo Zero는 이세돌을 이긴 AlphaGo를 100:0으로 이겼다. 인간이 두는 방식과 다른 전략을 발견한 것이다. 더 큰 네트워크로 40일 훈련한 버전은 Elo 5,185에 도달해, 당시 최강 AlphaGo Master를 89:11로 이겼다.
§ 6개인화 웹 서비스, 그리고 열 상승 비행
강화학습은 게임과 칩을 넘어 — 우리가 매일 보는 웹페이지에도, 그리고 새의 비행에도 닿는다.
뉴스·광고 전달의 개인화는 강화학습의 자연스러운 도메인이다. 사용자 클릭을 실시간 피드백으로 삼는다. 마케팅의 A/B 테스트는 단순한 강화학습이지만 — 비연관적이라 개인화하지 못한다.
Li 등(2010)은 개별 사용자 컨텍스트를 더한 문맥적 밴딧(연관적 강화학습, 2장)으로 Yahoo! 첫 페이지를 개인화해, 비연관 밴딧보다 클릭률을 12.5% 올렸다.
그러나 Theocharous 등(2015)은 더 멀리 갔다 — 개인화를 MDP로 공식화하면 더 낫다고. 문맥적 밴딧 정책은 행동의 장기 효과를 무시하는 탐욕적 정책이다. 같은 사용자가 사이트를 거듭 방문한다는 사실을 활용하지 못한다. 그들의 평생 가치(LTV) 최적화는 fitted Q iteration으로 여러 방문에 걸친 클릭을 최대화했고 — 높은 신뢰도 비정책 평가로 안전성을 보장해 — Adobe Marketing Cloud의 표준 구성요소가 되었다.
새와 글라이더는 상승 기류인 서멀(thermal)을 타고 에너지를 거의 쓰지 않고 고도를 얻는다. Reddy 등(2016)은 강화학습으로 — 서멀에 동반되는 강한 대기 난류 속에서 — 효과적인 소어링 정책을 조사했다.
소어링 문제를 할인이 있는 연속 MDP로 모델링하고, Sarsa로 Q 함수를 학습했다. 글라이더는 받음각과 뱅크 각을 제어하며(증가/감소/유지의 32개 행동), 정책은 Q 함수로부터 Boltzmann 유사 표현으로 얻어진다. 온도 매개변수를 점점 낮추는 어닐링으로 국소 극값에 갇히는 것을 막았다.
이 갱신은 흐름이나 비행의 사전 모델 없이 온라인으로 이루어진다 — 바로 그 점이 동물의 의사결정 과정을 모델링하는 데 특히 잘 맞는다. 자율 글라이더 기술에도, 새가 어떤 단서를 감지하는지에 대한 통찰에도 기여한다.