Q-러닝은 상태와 행동의 짝마다 행동 가치 Q(그 상태에서 그 행동을 하고 나서 앞으로 받을 보상의 합의 기댓값)를 표 한 칸에 적어 두고, 한 스텝을 겪을 때마다 그 칸을 「받은 보상 + 할인율 × 다음 상태에서 가장 큰 Q」 쪽으로 조금 옮긴다. 다른 정책이 둔 수의 기록으로도 최선의 수의 값을 배울 수 있다(배우려는 정책과 데이터를 모은 정책이 달라도 되는 오프폴리시 방법이다). 격자 길 찾기처럼 상태가 수십 개뿐이면 표는 작고, 칸마다 여러 번 들르며 값을 고칠 수 있다.
게임 화면을 상태로 삼으면 칸의 수가 셀 수 없이 불어난다. 오래된 가정용 게임기 아타리 2600의 화면은 가로 160, 세로 210 픽셀이고 픽셀마다 128가지 색 가운데 하나다. 픽셀이 33,600개이니 나올 수 있는 화면은 12833,600, 자릿수로 1070,802가지다. 관측 가능한 우주의 원자 수를 흔히 1080 정도로 어림하니, 표의 칸을 하나씩 만들기는커녕 같은 화면을 두 번 만날 일도 거의 없다. 변수가 늘 때마다 채울 칸이 곱으로 불어나는 이 어려움을 벨먼은 「차원의 저주」라고 불렀다.
그런데 사람은 처음 보는 화면에서도 공이 내 막대 쪽으로 빠르게 내려오면 위험하다는 것을 안다. 비슷한 화면은 값도 비슷하기 때문이다. 그렇다면 칸마다 따로 적는 대신, 화면을 받아 행동마다 Q를 내놓는 함수(신경망)를 배우면 된다. 그 함수는 파라미터를 여러 화면이 나눠 쓰므로, 한 화면의 값을 고치면 비슷한 화면의 값도 함께 움직인다. 처음 보는 화면에도 값을 매길 수 있는 힘이 바로 여기서 나온다.
칸마다 따로 적던 Q를 파라미터를 나눠 쓰는 함수로 바꾸면, 한 칸을 고칠 때 다른 칸이 따라 움직인다. 그 일이 학습을 망칠 수도 있을까?
망친다면, 무엇을 덧대야 신경망으로 어림한 Q-러닝이 게임 화면에서 배울 수 있을까?
이 장은 표를 함수로 바꾸면 값이 어떻게 불안정해지는지부터 숫자로 본 뒤, 그 불안정을 누르려고 덧댄 두 장치(지난 경험을 섞어 다시 쓰기, 과녁을 잠시 얼리기)와 그 결과인 DQN을 따라간다. 끝으로 언어 모델의 출력 하나하나를 행동 가치로 읽는 관점을 본다.
함수 근사와 위험한 세 조합: 셋이 겹치면 값이 한없이 커진다
표에서는 한 칸을 고쳐도 다른 칸의 값은 바뀌지 않았는데, Q-러닝의 목표값에는 다음 상태의 추정값이 들어간다. 정답을 끝까지 기다리지 않고 지금의 추정으로 목표를 만드는 이 방식이 시간차 학습의 부트스트랩이다. 칸이 따로일 때는 방금 고친 칸이 다음 칸의 추정값을 건드리지 않았기 때문에 이 방식이 안전했다. 함수로 바꾸면 방금 고친 파라미터가 다음 칸의 추정값까지 함께 움직여서, 목표를 쫓아가는 동안 목표가 내 손으로 움직인다. 그래도 결국 맞는 값에 닿을까?
역사: 백개먼에서 거둔 성공, 그다음의 반례들
1990년대 초 IBM 연구소의 제럴드 테사우로(Gerald Tesauro)는 주사위를 굴려 말을 옮기는 보드게임 백개먼을 신경망에게 가르쳤다. 판의 모양을 입력받아 이길 확률을 내놓는 신경망을 만들고, 그 신경망끼리 대국을 시키며 시간차 학습으로 고쳤다. 한 수 뒤 판에 대한 신경망 자신의 예측을 이번 판의 목표로 삼은 것이다. 테사우로는 1992년 『머신러닝(Machine Learning)』에 실은 「Practical Issues in Temporal Difference Learning」과 1995년 『ACM 통신(Communications of the ACM)』의 글로 이 프로그램 TD-개먼(TD-Gammon)을 알렸다.
결과는 놀라웠다. 백개먼 지식을 거의 넣지 않은 첫 판(은닉 유닛 40개)이 자기 자신과 약 30만 판을 둔 뒤, 당시 가장 강한 프로그램들과 비슷한 수준에 이르렀다. 그 가운데에는 전문가의 기보로 학습시킨 테사우로 자신의 신경망 프로그램 뉴로개먼도 있었다. 여기에 전문가가 쓰는 특징을 더하고 150만 판을 둔 TD-개먼 3.0은 세계 최상위 선수들에 가깝거나 그 이상으로 둔다는 평을 들었다.
이 성공을 보고 여러 연구자가 신경망과 시간차 학습을 다른 문제에 옮겼지만 잘 되지 않는 일이 잦았다. 저스틴 보얀(Justin Boyan)과 앤드루 무어(Andrew Moore)는 NIPS 7(1995년 논문집)에 실은 글에서, 표 대신 신경망 같은 함수로 가치함수(상태마다 앞으로 받을 보상의 기댓값)를 어림하는 방법이 백개먼에서는 통했지만 수렴한다는 보장이 없다고 짚었다. 그리고 동적 계획법과 함수 근사를 섞으면 단순한 태스크에서도 틀린 정책이 나오거나 값이 불어날 수 있음을 보였다. 같은 해 리먼 베어드(Leemon Baird)는 상태 일곱 개, 파라미터 여덟 개짜리 작은 문제를 내놓았다. 보상이 모두 0이라 참값은 0이고 파라미터를 0으로 두면 정확히 맞는데도, 학습률을 아무리 작게 해도 파라미터가 한없이 커졌다. 1997년 존 치치클리스(John Tsitsiklis)와 벤 판로이(Ben Van Roy)는 이 일을 정리했다. 선형 함수로 어림한 시간차 학습은 정책을 따라 실제로 들르는 상태의 비율대로 업데이트하면 한 점에 모이지만, 다른 비율로 업데이트하면 한없이 커질 수 있다.
그러면 TD-개먼은 왜 됐을까? 조던 폴락(Jordan Pollack)과 앨런 블레어(Alan Blair)는 1996년 「Why did TD-Gammon Work?」에서, 시간차 학습 없이 파라미터 약 4,000개짜리 신경망을 무작위로 조금씩 바꿔 이긴 쪽을 남기는 단순한 방법으로도 꽤 강한 프로그램이 나온다고 보고했다. TD-개먼의 성공은 시간차 학습 자체보다, 자기 자신과 겨루며 함께 나아가는 학습 구조와 백개먼이라는 게임의 성질 덕이 컸다는 해석이다. 뒤의 정리로 보면 하나가 더 있다. TD-개먼은 자기 자신과 둔 대국으로만, 다시 말해 지금 정책이 실제로 만나는 판으로만 배웠다.
칸 둘, 숫자 하나
무엇이 값을 불어나게 하는지 보려면 가장 작은 함수 근사가 필요하다. 칸이 하나면 다른 칸이 따라 움직일 일이 없고, 칸마다 숫자를 따로 주면 표와 같으므로, 칸 둘이 숫자 하나를 나눠 쓰는 꼴을 골라 칸 A와 B의 가치를 파라미터 하나 w로 어림한다. 신경망이 화면을 숫자로 요약하듯, 두 칸의 요약값을 A는 1, B는 1.5로 두고 가치를 「w × 요약값」으로 매긴다. 그러면 V(A) = w, V(B) = 1.5w다. A에서 B로 가는 스텝의 보상은 0이고 다른 보상도 모두 0이라, 두 칸의 참값은 0이고 w = 0이면 정확히 맞는다. 리플레이 버퍼(지난 경험을 모아 둔 저장소)에는 A에서 B로 간 기록만 있다. 데이터를 모은 정책은 B에 닿으면 늘 다른 길로 갔다고 하자.
업데이트 규칙은 시간차 학습의 규칙과 같다. 목표와 지금 추정의 차이(TD 오차)에 학습률과 요약값을 곱해 파라미터를 옮긴다.
w←w+αδh(s),δ=r+γV(s′)−V(s),V(s)=wh(s)wh(s)V(s)δrγαs,s′두칸이나눠쓰는파라미터하나 (신경망의파라미터자리)칸s의요약값 (A는 1, B는 1.5)칸s의가치추정TD 오차: 목표r+γV(s′)와지금추정의차이그스텝의보상 (여기서는 0)할인율 (0.9)학습률 (0.1)지금칸과다음칸 (여기서는 A와 B)
처음 w = 1에서 시작하자. V(A) = 1, V(B) = 1.5이므로 A의 목표는 0 + 0.9 × 1.5 = 1.35이고 TD 오차는 0.35다. A가 덜 평가됐다고 보고 w를 1.035로 올린다. 그런데 w를 올리면 B의 추정도 1.5525로 올라가고, 다음 업데이트의 목표는 1.3972, TD 오차는 0.3622로 처음보다 커진다. 셋째 업데이트의 TD 오차는 0.3749로, A를 목표에 맞추려 할수록 목표가 더 멀리 달아난다.
업데이트 한 번마다 w에는 1 + 0.1 × (0.9 × 1.5 − 1) = 1.035가 곱해진다. 10번 뒤 1.41, 50번 뒤 5.59, 100번 뒤 31.19다. 참값 0을 정확히 나타낼 수 있는 파라미터가 있는데도 학습은 그 반대쪽으로 한없이 커진다. 어림이 거칠어서 생긴 오차가 아니다.
이 두 칸 장난감에는 세 가지가 함께 들어 있다. 칸 둘이 숫자 하나를 나눠 쓰는 함수 근사, 다음 칸의 추정값을 목표에 쓰는 부트스트랩, 그리고 B에서 나가는 스텝은 한 번도 배우지 않는 데이터 분포의 편향(지금 정책과 다른 비율로 모은 오프폴리시 데이터)이다. 지금 정책대로라면 B에서도 스텝이 이어져 B의 추정을 끌어내릴 텐데, 버퍼에는 그 기록이 없다. 함수 근사, 부트스트랩, 오프폴리시 데이터가 겹친 것을 위험한 세 조합 (값이 한없이 커질 수 있는 세 재료 / deadly triad)이라 한다. 리처드 서튼(Richard Sutton)이 2015년 강연에서 붙이고 서튼과 바토의 교과서 2판(2018)이 정리한 이름이다.
셋 가운데 둘만 있으면 이런 일을 막을 수 있다고 알려져 있다(서튼과 바토의 교과서 11장). 재료를 하나씩 뺄 때 장난감의 w가 어떻게 되는지, 왜 그렇게 되는지는 아래 문제 2에서 직접 셈한다.
ML에서: DQN은 세 재료를 모두 가졌다
신경망으로 Q를 어림하는 순간 함수 근사가 들어오고, 목표값 「보상 + 할인율 × 다음 상태에서 가장 큰 Q」는 부트스트랩이다. 그리고 데이터는 지난 정책들이 탐색하며 모은 기록이고, 목표 속의 max는 지금 가장 좋아 보이는 행동만 따르는 다른 정책을 가정하니 오프폴리시다. 그래서 신경망 Q-러닝은 세 재료를 모두 안고 시작한다. 2018년 딥마인드의 하도 판하설트(Hado van Hasselt)와 동료들은 「Deep Reinforcement Learning and the Deadly Triad」에서 DQN의 변형 수백 가지를 아타리 57개 게임에 돌려, 가치 추정이 그 게임에서 나올 수 있는 범위를 훌쩍 넘는 일이 얼마나 자주 생기는지 쟀다. 범위가 얼마인지는 아래 문제 3에서 직접 구한다. 이 장의 나머지 두 장치는 세 재료를 하나도 버리지 않은 채, 셋이 겹친 자리에서 값이 오르내리거나 불어나는 일을 누르는 방법이다.
문제 1. 실거래 없는 두 아파트
감정사가 길 하나를 사이에 둔 두 아파트 A(24평)와 B(32평)의 값을 평당 단가 하나로 매긴다. 처음 단가는 평당 2,500만 원이라 A는 6억, B는 8억인데, 두 단지 모두 최근 실거래가 없다. 감정사의 규칙은 「A의 값은 B 값의 0.8배쯤이어야 한다」이고, 달마다 A의 감정가를 그 목표 쪽으로 10%씩 옮기도록 단가를 고친다. B의 값도 같은 단가로 매긴다. (가) 12달 뒤 단가와 두 아파트의 감정가는? (나) 몇 배여야 단가가 오르지도 내리지도 않는가? (다) 이웃 단지 C(32평)에 실거래 8억이 생겨, 달마다 단가를 그 실거래 단가 쪽으로도 10% 맞추기로 했다. 단가는 어디에 머무는가?
선생님
민준 학생, A의 목표가 B의 0.8배면 A가 B보다 싸다는 뜻이죠. 단가는 내려갈까요, 올라갈까요?
김민준
A를 싸게 맞추는 거니까 내려가겠죠. 6억이 6.4억 쪽으로… 어, 잠깐만요.
김민준
8억의 0.8배가 6.4억이라 A의 목표가 지금 6억보다 높아요. 단가를 올려서 A를 6.04억으로 맞추면, 같은 단가로 매기는 B도 올라서 다음 달 목표가 또 올라가네요.
선생님
한 달에 단가가 몇 배가 되죠?
김민준
A를 목표 쪽으로 10% 옮기니까 1 + 0.1 × (0.8 × 32/24 − 1) = 1.00667배요.
선생님
12달이면요?
김민준
1.00667¹² 해서 평당 2,707만 원, A는 6.50억, B는 8.66억이에요. 거래가 한 건도 없는데 1년에 8% 넘게 올랐어요.
이서연
(나)는 0.8 × 32/24 가 1 이면 되니까 24/32 = 0.75 배야. 그보다 크면 오르고 작으면 내리고. 0.7 배였으면 오히려 1년에 2,307만 원까지 내려가.
선생님
서연 학생, 어느 쪽이든 단가가 움직이는 까닭은 무엇이죠?
이서연
A의 목표를 B의 감정가로 만드는데, B의 감정가를 A와 같은 단가가 정하니까요. A를 고치면 목표도 같이 움직여요. 0.8 × 32/24 가 1보다 크면 목표가 늘 앞서 달아나고요.
선생님
(다)는요?
김민준
실거래 쪽으로 10%씩 당기니까 한 달 곱이 1.00667 × 0.9 로 1보다 작아져요.
선생님
곱이 1보다 작아지면, 단가는 어디에서 멈추죠?
김민준
실거래가 달마다 끌어당기는 몫이랑 곱이 줄이는 몫이 맞먹는 곳이요. u = 250 / (1 − 1.00667 × 0.9) 해서 평당 2,660만 원이에요. 실거래 2,500만 원보다는 조금 높지만 더 오르지 않아요.
이서연
해석학에서 수열이 an+1=can 꼴이면 ∣c∣<1 이어야 수렴하잖아. 진짜 값이 하나 끼면 c가 1 밑으로 내려가는 거고.
정리 (가) 달마다 1 + 0.1 × (0.8 × 32/24 − 1) = 1.00667배, 12달 뒤 평당 2,707만 원(A 6.50억, B 8.66억). (나) 0.75배(= 24/32). (다) 평당 2,660만 원에서 머문다. 목표를 내 추정으로 만들고(부트스트랩) 그 추정을 같은 숫자 하나로 매기면(함수 근사), 진짜 값이 끼지 않는 한 목표가 함께 달아날 수 있다.
문제 2. 세 재료에서 하나씩 빼 보기
본문의 두 칸 장난감(요약값 A 1, B 1.5, γ = 0.9, 학습률 0.1, 처음 w = 1, 보상 모두 0)에서 재료를 하나씩 뺀다. 각각 업데이트 100번(또는 에피소드 100개) 뒤 어떻게 되는가? (가) 함수 근사를 뺀다: 버퍼에는 여전히 A → B 기록만 있는 채로, 두 칸에 숫자를 따로 준다(V(A) = 1, V(B) = 1.5에서 시작). (나) 부트스트랩을 뺀다: 목표로 실제 리턴 0을 쓴다. (다) 오프폴리시를 뺀다: 지금 정책대로 A에서 시작해 B로 가고, B에서는 스텝마다 0.9의 확률로 B에 머물고 0.1의 확률로 끝나는 에피소드를 돌리며 들르는 스텝을 모두 배운다. (라) 세 재료가 모두 있을 때, γ가 얼마보다 작으면 w가 커지지 않는가?
선생님
서연 학생, (가)부터요. 숫자를 따로 주면 무엇이 달라지죠?
이서연
A를 고쳐도 B는 그대로 1.5예요. B는 기록이 없어 한 번도 안 고쳐지고요. 그럼 A는 0.9 × 1.5 = 1.35 를 향해 가다가 거기서 멈춰요. 100번 뒤 1.3500.
선생님
참값은 0인데 1.35에서 멈췄어요. 그래도 괜찮은 건가요?
이서연
틀린 값이긴 하지만 커지지는 않아요. B의 추정이 틀린 만큼만 A가 틀린 거니까, 잘못이 그 자리에 머물러요.
김민준
(나)는 목표가 늘 0이니까 w ← w − 0.1w 라서 0.9 를 곱하기만 해요. 0.9¹⁰⁰ = 2.66 × 10⁻⁵, 거의 0이요.
선생님
(다)는요?
김민준
A에서는 TD 오차가 0.35w 라서 올라가요.
선생님
B에서는요?
김민준
머물 때 0.9 × 1.5w − 1.5w = −0.15w, 끝날 때 0 − 1.5w = −1.5w 예요.
선생님
에피소드 하나로 모으면요?
김민준
들를 때마다 평균 0.9 × (−0.15) + 0.1 × (−1.5) = −0.285w, B에 평균 10번 들르니까 0.35 − 2.85 = −2.5w 로 줄어요.
선생님
방향은 맞아요. 그런데 업데이트 식에서 TD 오차 뒤에 무엇을 곱했죠?
김민준
그 칸의 요약값이요. B는 1.5 를 한 번 더 곱해야 해요. 머물 때 −0.15 × 1.5 = −0.225w, 끝날 때 −1.5 × 1.5 = −2.25w, 평균 −0.4275w.
선생님
다시 에피소드 하나로 모으면요?
김민준
0.35 − 4.275 = −3.925w 예요. 씨앗 0으로 에피소드 100개 돌리니까 3.9 × 10⁻²⁰ 이에요.
이서연
A에서 B의 값을 근거로 기대를 부풀리면, B에 실제로 들러서 그 기대를 확인당해야 하는구나. 오프폴리시 버퍼에는 그 확인이 빠져 있었던 거고.
선생님
그래요. (라)는요?
이서연
커지느냐 마느냐는 한 번 업데이트에 w 에 곱하는 수로 보면 될 것 같아요. 1 + 0.1 × (1.5γ − 1) 이 1보다 크지 않으면 되니까 1.5γ ≤ 1, γ < 2/3 이에요.
선생님
경계 근처에서도 그런지 볼까요.
김민준
γ = 0.67 이면 1.0005 로 아주 천천히 커지고, 0.66 이면 0.9990 으로 줄어요.
김민준
조별 과제에서 서로 상대 몫이 잘 되고 있겠거니 하고 확인을 안 하면 다 같이 망하는 거랑 같네요. 한 명이라도 실제 결과를 보거나(부트스트랩 빼기), 각자 자기 것만 책임지거나(함수 근사 빼기), 돌아가며 서로 확인하면(온폴리시: 지금 정책이 실제로 들르는 비율대로 배우기) 괜찮고요.
정리 (가) 표: V(A)는 0.9 × 1.5 = 1.35에서 멈춘다(틀리지만 커지지 않는다). (나) 실제 리턴: w = 0.9¹⁰⁰ = 2.66 × 10⁻⁵. (다) 온폴리시: 에피소드당 기대 그래디언트 0.35 − 10 × 0.4275 = −3.925 (w에 곱하는 양), 100개 뒤 3.9 × 10⁻²⁰. (라) γ < 2/3. 세 재료 가운데 하나만 빠져도 장난감의 w는 커지지 않았으므로, 세 조합의 위험은 셋이 겹친 자리에서 생긴다.
문제 3. 가치가 3,000이라는 DQN
DQN은 아타리 게임의 점수 변화를 보상으로 쓰되, 양수는 모두 +1, 음수는 모두 −1로 잘라 쓴다. 할인율은 γ = 0.99다. (가) 어느 상태든 Q의 참값은 얼마를 넘을 수 없는가? (나) 학습 도중 어떤 상태의 Q 추정이 3,000으로 찍혔다. Q 추정 3,000을 어떻게 읽어야 하는가? (다) DQN의 어느 부분이 위험한 세 조합의 어느 재료인가?
선생님
민준 학생, 보상이 한 스텝에 아무리 커도 1이면 Q는 얼마까지 될 수 있을까요?
김민준
게임이 길면 끝없이 커질 수 있지 않나요? 벽돌을 계속 깨면 점수가 계속 오르잖아요.
선생님
그 점수를 할인율 0.99 로 할인해 더하면요? 매 스텝 +1을 끝없이 받는다고 해 봐요.
나올 수 없는 값이니까 그건 학습이 틀어진 신호야. 그래도 판이 잘 풀려서 점수가 높은 거라고 읽으면 안 되겠다.
선생님
판하설트와 동료들은 바로 그 100을 기준으로 삼았어요. 추정값이 100을 넘으면 「부드러운 폭주(soft divergence)」라 부르고 얼마나 자주 생기는지 셌죠. 과녁을 지금 신경망으로 계산하는 보통의 Q-러닝은 실험의 61%에서 이 일이 생겼고, 추정이 백만을 넘었다가 다시 100 밑으로 내려오는 일도 흔했어요. 끝까지 한없이 커진 실행은 없었고요.
이서연
그럼 (다)는 이렇게 짝지어져요. 합성곱 신경망이 함수 근사, 목표의 「보상 + 0.99 × 다음 상태의 max Q」가 부트스트랩, 지난 정책들이 모은 리플레이 버퍼와 max가 가정하는 그리디 정책이 오프폴리시예요.
선생님
그 논문은 부트스트랩을 줄이면 어떻게 되는지도 봤어요. 한 스텝 대신 n스텝의 실제 보상을 더한 뒤에야 추정을 쓰게 하면, 보통의 Q-러닝에서 한 스텝(n = 1)일 때 94%이던 폭주 비율이 n = 10 에서 21%로 줄었어요.
김민준
시험 만점이 100점인데 채점 프로그램이 3,000점을 찍으면 학생을 칭찬할 게 아니라 프로그램을 의심해야 하는 거랑 같네요.
정리 (가) 보상을 −1~1로 잘랐으므로 ∣Q∣≤1/(1−0.99)=100. (나) 3,000은 나올 수 없는 값이라 학습이 틀어진 신호다(부드러운 폭주). (다) 합성곱 신경망 = 함수 근사, 「보상 + γ × max Q」 = 부트스트랩, 리플레이 버퍼와 max = 오프폴리시. 판하설트 외(2018)의 실험에서 보통 Q-러닝의 부드러운 폭주는 61%였고, 보통 Q-러닝의 폭주 비율은 n스텝 리턴의 n을 1에서 10으로 늘리자 94%에서 21%로 줄었다.
