Part III: 가치 기반 (마르코프 결정 과정에서 DQN까지)

정책 그래디언트는 “점수를 어떻게 올리나” 를 물었다. 이 파트는 다른 물음에서 출발한다: “지금 이 자리는 앞으로 얼마나 좋은가?”

Chapter 4: 마르코프 결정 과정: 지금만 보고 고르고, 앞날을 셈한다

의문

정책 그래디언트에 베이스라인을 더하면 그래디언트 추정의 표준편차가 준다. 같은 프롬프트에서 뽑은 응답들의 평균 점수를 빼면 「이 문제에서 평소보다 잘했나」를 물을 수 있다. 그런데 그 평균은 프롬프트 하나에 숫자 하나다. 풀이를 절반쯤 써 내려간 자리에서 「여기까지 쓴 풀이가 얼마나 유망한가」를 알려 주지는 않는다. 그런 숫자를 풀이의 자리마다 매기려면, 먼저 「자리」와 「앞으로」가 무엇인지 정확히 적어야 한다.

언어 모델만 보면 이 일은 쉬워 보이는데, 토큰을 하나 고르면 다음 자리는 그 토큰을 뒤에 붙인 문장으로 딱 정해진다. 하지만 모델이 사람과 대화하거나 도구를 부르면 다음 자리를 모델 혼자 정하지 못한다. 모델이 되물으면 사용자는 설명을 덧붙일 수도, 창을 닫을 수도 있다. 검색 도구가 무엇을 돌려줄지도 모델이 정하지 않으니, 다음 자리는 세상이 확률로 정한다. 게다가 점수는 대개 맨 끝에 한 번 온다.

고르는 것은 내가 하고 다음 자리는 세상이 뽑을 때, 지금의 선택은 어떻게 적을까?
점수가 한참 뒤에 오거나 여러 번 나눠 올 때, 지금 놓인 처지(상태)의 값은 무엇으로 셈할까?

이 장은 이 두 물음에 답할 말을 세운다. 상태와 행동과 전이 확률로 문제를 적는 틀, 그 틀이 기대는 「지금만 보면 된다」는 가정, 앞으로 받을 보상을 하나로 묶는 셈, 그리고 그 셈으로 매기는 자리의 값이다.

마르코프 결정 과정: 마르코프 체인에 고르는 손을 더한다

택시 운전사를 떠올려 보자. 손님을 내려 준 자리에서 운전사는 다음 손님을 어떻게 찾을지 정해야 한다. 거리를 천천히 돌며 손을 드는 손님을 태울 수도 있고, 가까운 승차장 줄에 설 수도 있다. 어느 쪽을 골라도 다음 손님이 어디로 갈지는 운전사 마음대로 되지 않고, 고른 방식에 따라 「어디로 가자는 손님을 만날 확률」이 달라질 뿐이다. 그리고 그날 번 돈은 손님 한 명의 요금이 아니라 하루 동안의 요금을 모두 더한 것이다. 고를 수 있는 것과 고를 수 없는 것이 섞인 이런 문제는 무엇으로 적을까?

역사: 멈추는 게임에서 택시 운전사까지

이런 문제를 처음 수학으로 적은 쪽은 게임 이론이었다. 로이드 섀플리(Lloyd Shapley)는 1953년 『미국 국립과학원 회보(PNAS)』에 낸 짧은 논문 「Stochastic Games」에서, 두 사람이 판을 거듭하며 겨루는 게임(한 사람이 얻는 만큼 다른 사람이 잃는다)을 다뤘다. 판마다 지금 놓인 처지(상태)가 있고, 두 사람이 고른 수에 따라 이번 판의 보수와 다음 처지의 확률이 정해진다. 게임이 끝나지 않으면 보수의 합이 끝없이 불어날 수 있는데, 섀플리는 판마다 0보다 큰 확률로 게임이 멈춘다고 두었다. 그러면 게임은 확률 1로 유한한 판 안에 끝난다. 그리고 이런 게임에는 값(두 사람이 모두 최선을 다할 때 한쪽이 기대할 수 있는 보수)이 있고, 지금 처지만 보고 수를 정하는 전략만으로 그 게임의 값에 닿는다는 것을 보였다. 과거의 수를 모두 기억하는 복잡한 전략이 필요 없다는 뜻이다.

게임에서 상대를 빼고 결정하는 사람 하나만 남긴 틀은 리처드 벨먼(Richard Bellman)이 정리했다. 1957년 『수학·역학 저널(Journal of Mathematics and Mechanics)』 6권에 실린 그의 논문 제목이 「A Markovian Decision Process」다. 오늘날의 이름 「마르코프 결정 과정」을 제목에 단 논문으로 잘 알려진 첫 자리에 이 논문이 꼽힌다(벨먼이 이 이름을 더 일찍 썼다는 기록도 있다). 랜드 연구소 보고서로 먼저 나온 이 논문은 단계마다 결정을 내리는 문제를 되풀이 식으로 적고, 그 되풀이가 오래 가면 어떻게 되는지를 따졌다.

이 틀을 손에 잡히는 예로 보인 사람은 로널드 하워드(Ronald Howard)다. MIT 박사 논문을 다듬어 1960년에 낸 책 『Dynamic Programming and Markov Processes』에 택시 문제가 나온다. 운전사의 구역은 세 마을이고, 마을마다 거리를 돌거나, 승차장에 줄을 서거나, 무전 호출을 기다릴 수 있다. 한 마을에는 무전 호출 서비스가 없어 고를 수 있는 것이 둘뿐이고, 고른 방식마다 다음 손님이 어느 마을로 갈 확률과 요금이 다르다. 아래 장난감 예제는 이 택시 문제의 짜임을 본떴지만, 고를 수 있는 것을 둘로 줄였고 확률과 요금은 이 책이 정한 숫자다. 하워드의 원래 숫자가 아니다.

세 구역 택시

이 장 내내 쓸 예제로, 운전사가 역, 시장, 대학가 세 구역에서 일한다고 하자. 왜 하필 이렇게 작은 예일까? 구역이 하나면 어디로 갈지가 문제가 되지 않고, 고를 것이 하나면 고르는 손이 없다. 구역 셋과 행동 둘은 「고른 것에 따라 다음 자리가 달라진다」는 일이 생기는 가장 작은 크기에 가깝고, 그러면서도 손으로 셈할 수 있다.

• 손님을 내려 준 구역이 지금 놓인 자리다.
• 운전사는 배회(거리를 돌며 손을 드는 손님 태우기)나 승차장(승차장 줄에 서서 기다리기) 가운데 하나를 고른다. 승차장에서는 기다리는 동안 벌지 못하는 돈을 2천 원으로 친다.
• 손님은 확률에 따라 세 구역 가운데 한 곳으로 간다. 요금(천 원)은 출발 구역과 도착 구역으로 정해진다: 같은 구역 안이면 역 4, 시장 3, 대학가 4. 역–시장 7, 시장–대학가 6, 역–대학가 10.
• 손님을 내려 줄 때마다 1/10 확률로 그날 일을 마친다(퇴근).

역에서 손님을 내려 준 운전사가 무엇을 고르느냐에 따라 다음이 이렇게 갈린다.

배회하면 대개 역 근처를 오가는 짧은 손님을 만나고, 승차장에 서면 대학가로 가는 먼 손님을 자주 만난다. 확률 0.54는 「일이 이어질 확률 0.9 × 역 안에서 가는 손님 0.6」이다. 기대 보상 6.80은 승차장 손님의 요금 평균 0.1 × 4 + 0.2 × 7 + 0.7 × 10 = 8.80에서 기다리는 비용 2를 뺀 값이다.

그림 왼쪽은 운전사가 「늘 배회」로 행동을 정해 둔 경우다. 그러면 남는 것은 지금 구역에서 다음 구역으로 옮겨 가는 확률뿐이고, 이것은 마르코프 체인이다. 마르코프 체인은 지금 상태만 보고 다음 상태를 뽑는 과정이고, 옮겨 가는 확률을 모은 표(행마다 합이 1)를 전이 행렬이라 부른다.

그림 오른쪽에는 마르코프 체인에 없던 것이 하나 더 있다. 지금 상태에서 다음 상태로 가기 전에 손이 행동을 하나 고르고, 고른 행동마다 다음 상태의 확률이 다르다. 이렇게 상태, 행동, 행동에 따라 달라지는 전이 확률, 보상으로 적은 문제를 마르코프 결정 과정 (고르는 손이 있는 마르코프 체인 / Markov decision process, MDP)이라 한다. 머리글자를 따 MDP라고도 부른다.

셋째 식이 그림 왼쪽과 오른쪽을 잇는다. 정책 $\textcolor{#1565c0}{\pi}$(파이)를 정해 두면 행동이 더는 열린 선택이 아니므로, MDP는 전이 행렬이 $\textcolor{#8877ff}{P}^{\textcolor{#1565c0}{\pi}}$인 마르코프 체인으로 줄어든다. 「늘 배회」 정책이면 체인의 전이 행렬은 아래와 같고(퇴근 칸은 뺐다), 역에서 시작해 손님 둘을 태운 뒤에도 아직 일하면서 시장에 있을 확률은 이 행렬을 두 번 곱한 칸에서 0.3078로 읽힌다.

거꾸로 말하면, 정책을 정하기 전의 MDP에는 「그 전이 행렬」이 하나로 정해져 있지 않다. 구역마다 행동을 하나씩 고르는 정책만 2 × 2 × 2 = 8가지이고, 그 여덟 체인은 서로 다르게 움직인다. 정책을 고르는 일이 곧 여러 체인 가운데 하나를 고르는 일이다.

ML에서: 다음 상태를 누가 정하나

언어 모델이 응답 하나를 쓰는 과정도 MDP로 적힌다. 프롬프트와 지금까지 쓴 토큰이 상태 $\textcolor{#0093b8}{s_t}$이고, 다음 토큰이 행동 $\textcolor{#1c9c60}{a_t}$, 언어 모델의 다음 토큰 분포가 정책이다. 그렇다면 이 MDP에서 세상은 다음 상태를 얼마나 뽑을까? 토큰 $\textcolor{#1c9c60}{a_t}$를 하나 고른 뒤 다음 상태가 될 수 있는 문장이 몇 개인지 떠올려 보면 전이 확률 $\textcolor{#8877ff}{P}$의 모양이 보인다. 그 모양을 식으로 적는 일이 아래 문제 3의 (다)다.

모델이 사람이나 도구와 주고받으면 다음 상태를 모델 혼자 정하지 못한다. 모델이 되물은 뒤 사용자가 무엇이라 답할지, 코드를 돌린 도구가 어떤 오류를 돌려줄지는 모델이 고를 수 없다. 이때 다음 상태는 세상이 확률로 뽑으므로 모델은 택시 운전사와 같은 처지가 된다. 같은 질문에 바로 답할지 되물을지를 고르는 일이 아래 문제 3이다.

문제 1: 전단지를 돌릴까

민준 학생, (가)는 얼마가 나왔어요?

오늘 적은 날에 전단을 돌리면 0.5, 내일 또 돌리면 많은 날 + 전단이라 0.8이니까 0.5 × 0.8 = 0.4요.

0.5 × 0.8 은 내일 손님이 어땠다는 경우예요?

내일이 많은 경우만이네요. 내일 적을 확률 0.5 도 있고, 그러면 모레 많을 확률은 적음 + 전단의 0.5 예요. 0.4 + 0.5 × 0.5 = 0.65 요.

(나)는 0.2 × 0.6 + 0.8 × 0.2 = 0.28. 전단 하나로 0.65 대 0.28 이면 차이가 크네. 그런데 (다)는 좀 이상해. 내일 저녁에 무엇을 할지가 내일 손님에 따라 달라지잖아.

그래서 셈이 안 되나요?

아니요, 규칙만 정해 두면 돼요. 내일 많으면 안 돌리니까 0.6, 적으면 돌리니까 0.5. 오늘은 적으니까 돌리고요. 0.5 × 0.6 + 0.5 × 0.5 = 0.55 예요.

그래요. 상태마다 무엇을 할지를 정한 규칙이 정책이고, 정책을 정하면 손님 많음·적음은 확률만 남은 마르코프 체인이 돼요. 규칙이 셋이면 체인도 셋이고요.

동아리 홍보도 그래요. 「신입이 적은 학기에만 부스를 연다」고 정해 두면 그다음 학기 신입 수는 그냥 확률 계산이 되죠.

정리 (가) 0.5 × 0.8 + 0.5 × 0.5 = 0.65. (나) 0.2 × 0.6 + 0.8 × 0.2 = 0.28. (다) 0.5 × 0.6 + 0.5 × 0.5 = 0.55. 행동이 다음 상태의 확률을 바꾸는 문제에서는 상태마다 무엇을 할지(정책)를 먼저 정해야 「모레의 확률」이 하나로 정해진다. 정책마다 다른 마르코프 체인이 생긴다.

문제 2: 늘 승차장에 서면

(가)부터 볼까요. 민준 학생은 어떻게 셈했어요?

역에서 승차장에 서면 0.9 × 0.7 = 0.63 으로 대학가에 가요. 대학가에서 또 승차장에 서도 대학가 근처에 있겠죠. 그래서 0.63 쯤이요.

대학가 승차장 줄의 손님은 어디로 가죠? 문제의 확률을 다시 읽어 볼까요.

(0.7, 0.3, 0) 이니까 대학가 안으로 가는 확률이 0 이네요. 첫 손님이 대학가로 가면 둘째 손님 뒤에는 대학가에 있을 수가 없어요.

그럼 둘째 손님 뒤에 대학가에 있으려면 첫 손님 뒤에 어디 있어야 해요?

역이나 시장이요. 거기서 둘째 손님에 대학가로 가는 것뿐이네요. 역 → 역 → 대학가가 0.09 × 0.63 = 0.0567, 역 → 시장 → 대학가가 0.18 × 0.36 = 0.0648, 더하면 0.1215 요.

첫 손님만 보면 대학가에 갈 확률이 0.63 이었는데, 손님 둘 뒤에는 0.1215 네. 한 스텝의 확률을 둘째 스텝에 그대로 쓰면 안 되는구나.

(나)는요? 이번에는 역의 행동은 그대로 두고 시장·대학가의 행동만 바꿨어요.

일단 바뀐 곳부터 볼게요. 대학가에서 배회하면 0.9 × 0.6 = 0.54 로 대학가에 남아요. 아까는 0이던 길이 열린 거죠. 역 → 대학가 → 대학가가 0.63 × 0.54 = 0.3402 예요.

길이 그것 하나뿐이에요?

아, 역 → 역 → 대학가는 그대로 0.0567 이고, 시장에서도 이제 배회하니까 역 → 시장 → 대학가가 0.0162 로 바뀌어요. 셋을 더하면 0.4131 이에요.

역에서 한 일은 같은데, 다른 구역의 규칙이 바뀌니 결과가 세 배 넘게 달라졌어요.

(다)는요?

퇴근은 어느 행동이든 손님마다 1/10 이니까, 둘 안에 퇴근할 확률은 1 − 0.9 × 0.9 = 0.19 로 정책과 상관없어요.

확률 그 자체는 MDP가 주고, 어느 확률표를 쓸지는 정책이 고르는 거네요. 선형대수에서 같은 행렬 집합 가운데 어느 행렬을 곱하느냐에 따라 결과가 달라지는 것처럼요.

정리 (가) 0.09 × 0.63 + 0.18 × 0.36 = 0.1215 (대학가 승차장 손님은 대학가 안으로 가지 않는다). (나) 0.0567 + 0.0162 + 0.3402 = 0.4131. 역에서 고른 행동이 같아도 다른 상태의 행동이 바뀌면 두 스텝 뒤가 크게 달라지므로, 정책은 상태 하나의 선택이 아니라 모든 상태의 선택을 묶은 것이다. (다) 0.19. 행동과 상관없는 확률은 정책을 바꿔도 0.19로 같다.

문제 3: 바로 답할까, 되물을까

민준 학생, 둘 가운데 어느 정책이 나을 것 같아요?

바로 답이요. 되물으면 한 차례를 그냥 쓰는 거잖아요. 두 번밖에 말을 못 하는데 한 번을 질문에 쓰면 손해죠.

셈해 보면요?

바로 답은 첫 차례에 0.5, 다시 물으면(0.4) 또 0.5 라서 0.5 + 0.4 × 0.5 = 0.7. 되묻기는 0.85 × 0.85 = 0.7225 …

되묻는 정책이 더 높네요.

되묻기는 이번 차례에 만족을 하나도 못 주지만, 다음 상태를 「분명한 질문」으로 옮겨 놓잖아. 거기서는 바로 답이 0.85 로 먹혀. 이번 보상만 보면 지는 행동이 다음 상태를 바꿔서 이기는 거야.

그래요. (가)는 어떻게 갈라요?

바로 답과 되묻기 가운데 무엇을 할지는 정책이고, 만족·다시 물음·떠남 가운데 무엇이 일어날지는 사용자, 곧 세상이 정하는 전이 확률이에요.

(다)에서 토큰 하나를 고를 때는 그 세상이 어디 있죠?

없어요. 토큰을 고르면 다음 상태는 그 토큰을 붙인 문장 하나라서, 그 문장에 1, 나머지 모든 문장에 0 이에요. 세상이 뽑는 무작위가 없는 MDP네요.

조별 과제에서 팀원한테 일을 바로 나눌지, 먼저 각자 할 수 있는 게 뭔지 물어볼지랑 같아요. 묻는 데 한 번을 써도 그다음 분배가 훨씬 잘 맞으니까요.

정리 (가) 바로 답·되묻기는 정책, 사용자의 반응은 전이 확률이다. (나) 0.5 + 0.4 × 0.5 = 0.70, 0.85 × 0.85 = 0.7225. 이번 차례의 보상이 0인 행동도 다음 상태를 더 좋은 곳으로 옮기면 더 나을 수 있다. (다) 고른 토큰을 붙인 문장 하나에만 확률 1. 토큰 단위 MDP에서는 모든 무작위가 정책에서 나오고, 사용자·도구가 끼어들면 전이 확률이 다시 여러 칸에 퍼진다.