강가 산책로를 다시 적자. 4줄 × 10칸 격자에서 물가 줄의 출발점 S부터 정자 G까지 걷고, 한 스텝마다 −1, 그 사이 물가 줄 여덟 칸의 강물에 빠지면 −50을 받고 출발점으로 돌아간다. 가끔 아무 방향으로나 걸으며 배운 SARSA의 표는 물가에서 두 줄 떨어진 13스텝 길을 골랐다. 열 스텝에 한 번꼴로 무작위 스텝을 밟으니 물가 바로 위를 걷기는 위험했으므로, 이 13스텝 길은 학습하는 동안에는 현명했다. 그런데 학습을 마치고 산책로를 정말 걸을 때는 무작위 스텝을 멈출 것이고, 무작위 스텝이 없다면 줄 2를 따라가는 11스텝 길이 −11로 가장 좋다. 시험 삼아 걷는 일은 배우는 동안의 사정일 뿐인데도, SARSA가 배운 값은 그 사정까지 담고 있다. 배우는 동안은 무작위 스텝을 밟으면서도, 무작위 스텝 없이 걷는 사람의 값을 배울 수는 없을까?
역사: 동물은 어떻게 최선의 행동을 배우나
1989년 5월, 크리스토퍼 왓킨스(Christopher Watkins)는 케임브리지 대학 킹스 칼리지에 박사 논문 「Learning from Delayed Rewards」(늦게 오는 보상으로 배우기)를 냈다. 그의 물음은 동물 행동학에서 나왔다. 행동생태학자들은 확률적 동적 계획법으로 동물에게 가장 좋은 행동 규칙을 셈할 수 있었다. 동물이 동적 계획법의 셈을 머릿속으로 한다고 보기는 어려웠기에, 왓킨스는 논문 요약에서 「그런데 동물은 경험에서 어떻게 그 규칙을 스스로 배울까?」라고 묻는다. 그가 내놓은 답은 환경의 모델을 만들 필요도, 지난 상황과 행동을 오래 기억할 필요도 없이 행동의 최적 가치를 경험에서 바로 배우는 방법이었다. 논문의 감사 글에는 동물 행동과 먹이 찾기 이론의 흥미로운 예를 많이 들려준 알렉스 카셀닉(Alex Kacelnik)과, 그가 이 일을 마칠 수 있게 도운 필립스 연구소의 상사가 나온다.
논문에는 이 방법이 들어맞는다는 증명이 실렸지만, 뒤에 서튼과 바토의 교과서가 「밑그림(outline)」이라 부르는 정도였다. 3년 뒤인 1992년, 왓킨스는 피터 다얀(Peter Dayan)과 함께 학술지 『Machine Learning』 8권에 짧은 기술 노트 「Q-learning」을 내어 그 증명을 엄밀하게 다듬었다. 결론은 모든 상태에서 모든 행동을 거듭 시험하고 값을 표에 따로따로 적는다면, 이 방법이 최적 행동 가치에 확률 1로 다가간다는 것이다. 증명에는 학습률에 대한 조건도 붙는다. 논문의 정오표에 적힌 꼴로는 같은 (상태, 행동) 짝에 쓰는 학습률이 점점 줄어 0으로 가되, 모두 더하면 끝없이 커져야 한다.
다음 칸에서 가장 좋은 방향을 가정한다
SARSA의 목표에서 바꿀 곳은 한 군데다. 다음 칸에서 실제로 고른 방향의 값 대신, 다음 칸의 네 방향 가운데 가장 큰 값을 넣는다. 다음 칸에서 내가 무엇을 골랐든, 「거기서부터는 최선을 다한다」고 가정하고 셈하는 것이다.
이 규칙으로 행동 가치를 배우는 방법을 Q-러닝 (다음 칸의 최선을 가정하는 시간차 학습 / Q-learning)이라 한다. 걷는 방식은 SARSA와 똑같이 둔다. 확률 ε = 0.1로 아무 쪽으로나 걷고, 나머지는 표에서 가장 큰 쪽으로 걷는다. 달라진 것은 목표뿐이다.
같은 조건(ε = 0.1, α = 0.1, 에피소드 500번, 학습 100번)으로 돌린 결과를 SARSA와 나란히 놓으면 이렇다.
학습이 끝난 표의 그리디 길
마지막 100 에피소드의 평균 리턴 (탐색하며 걸은 그대로)
에피소드당 강물에 빠진 횟수
SARSA
13스텝, 줄 1 (100번 가운데 94번)
−17.51
0.045
Q-러닝
11스텝, 줄 2 (100번 모두)
−27.19
0.265
두 결과가 엇갈린다. Q-러닝의 표는 100번 모두 무작위 스텝이 없을 때 가장 좋은 길인, 강물 바로 위를 지나는 11스텝 길을 가장 좋게 읽었다. 그런데 학습하는 동안 실제로 받은 리턴은 SARSA보다 10쯤 나빴다. Q-러닝도 열 스텝에 한 번꼴로 무작위 스텝을 밟는데, 그 무작위 스텝을 물가 바로 위에서 밟으니 에피소드 네 번에 한 번꼴로 강물에 빠진다. 목표가 「다음 칸부터는 무작위 스텝 없이 최선」을 가정하기 때문에, Q-러닝의 표에는 그 위험이 들어 있지 않다.
이렇게 경험을 모으는 정책(무작위 스텝이 섞인 걷기)과 값을 배우는 정책(늘 가장 큰 쪽만 고르는 걷기)이 다른 학습을 오프폴리시(off-policy)라 부른다. 무작위 스텝이 섞인 걷기를 행동 정책, 늘 가장 큰 쪽만 고르는 걷기를 목표 정책이라 가르기도 한다. Q-러닝은 행동 정책이 모든 방향을 계속 시험해 주기만 하면, 목표 정책의 값을 배운다.
아래 위젯에서 두 방법을 직접 돌려 보자(학습 20번씩이라 본문 표의 학습 100번과 숫자가 조금 다르다). ε을 바꾸면 위 격자의 두 길과 아래의 리턴 곡선이 함께 바뀐다.
왓킨스와 다얀의 증명이 붙인 학습률 조건은 확률적 경사하강이 손실의 최솟값에 닿는 조건과 같은 꼴이다. 노이즈 섞인 목표를 따라가며 값을 고치는 일이라, 학습률을 너무 오래 크게 두면 값이 목표의 노이즈를 따라 흔들리고, 너무 빨리 줄이면 참값에 닿기 전에 멈춘다. 시간차 학습에서 본 로빈스–먼로 조건, 곧 같은 (상태, 행동) 짝에 쓰는 학습률을 모두 더하면 끝없이 커지고 제곱해 더하면 유한해야 한다는 조건이 여기서도 그대로 쓰인다. 위젯의 학습률 α는 줄이지 않고 고정해 두었다.
ML에서: 남이 모은 경험으로도 배운다
Q-러닝의 목표에는 다음 칸에서 누가 무엇을 골랐는지가 들어가지 않는다. 그러니 한 스텝의 기록 (지금 칸, 고른 방향, 받은 보상, 닿은 칸)만 있으면, 그 기록을 남긴 것이 어제의 나든 다른 사람이든 업데이트에 쓸 수 있다. 지난 경험을 저장소에 모아 두고 거듭 꺼내 쓰는 방식(리플레이 버퍼)이 가치 기반 방법과 잘 맞는 것도 이 때문이다. 같은 기록 하나로 두 방법이 어떻게 갈리는지는 아래 문제 6에서 셈한다.
문제 4. 친구의 대국 기록으로 공부하기
서연은 체스를 친구들의 대국 기록으로 공부하는데, 어느 국면에서 친구가 둔 수 A의 값을 0으로 어림하고 있었다. 기록을 보니 수 A 뒤 상대가 응수했고(수 A에서 받은 보상 0), 이어진 국면에서 친구는 실수를 해 그 국면의 값이 −0.8인 수를 두었다. 그 국면에서 가장 좋은 수의 값은 +0.4이고, 학습률은 0.5다. (가) 친구가 실제로 둔 수로 배우면 수 A의 값은 얼마로 고쳐지나? (나) 그 국면에서 최선을 둔다고 가정하면? (다) 서연이 알고 싶은 것은 「내가 수 A를 두면 얼마나 좋은가」다. 어느 쪽이 맞는가?
선생님
서연 학생, 수 A 는 좋은 수인가요?
이서연
친구가 이 수를 둔 대국에서 결국 나빠졌으니까, 0.5 × (−0.8) = −0.4 로 낮추는 게 맞을 것 같아요.
선생님
그 −0.8 은 수 A 때문에 생긴 것인가요, 그다음 국면에서 친구가 둔 실수 때문에 생긴 것인가요?
이서연
그다음 실수 때문이에요. 그 국면에서 제대로 두면 +0.4 였으니까, 수 A 자체가 나빴던 건 아니에요. 최선을 가정하면 0.5 × 0.4 = +0.2 로 오히려 올려야 해요.
김민준
그럼 (다)는 (나)네. 서연이는 친구처럼 그 자리에서 실수할 생각이 없으니까. 친구 기록은 친구의 실수까지 섞인 기록이고.
선생님
그래요. 남이 둔 기록으로 「내가 최선을 다할 때의 값」을 배우려면, 남이 다음에 둔 수 대신 그 자리의 최선을 목표에 넣어야 해요.
김민준
선배 과제 코드를 참고할 때, 선배가 뒤에서 버그를 낸 걸 보고 앞의 설계까지 나쁘다고 버리면 안 되는 거랑 같네요.
정리 (가) 0 + 0.5 × (−0.8 − 0) = −0.4. (나) 0 + 0.5 × (0.4 − 0) = +0.2. (다) (나). 남의 다음 수를 목표에 넣으면 남의 실수까지 배운다. 다음 국면의 최선을 넣으면 누가 둔 기록이든 「최선을 다하는 나」의 값을 배울 수 있다. 경험을 모은 정책(친구)과 값을 배우는 정책(최선을 두는 서연)이 다른 이런 학습이 오프폴리시다.
문제 5. 무작위 스텝이 얼마나 드물면 물가 길이 나은가
강가 산책로에서 두 길을 정해 두고, 길 위의 칸마다 정한 방향으로 걷되 확률 ε로는 네 방향 가운데 아무 쪽으로나 걷는다고 하자(무작위 스텝으로 길을 벗어나면 벗어난 칸에서 다시 길 쪽으로 걷는다). 물가 길은 줄 2를, 안쪽 길은 줄 1을 따라갈 때, 연립방정식으로 푼 출발점의 기대 리턴은 다음과 같다.
ε
0
0.01
0.02
0.05
0.1
물가 길 (줄 2)
−11.00
−12.37
−13.80
−18.46
−27.67
안쪽 길 (줄 1)
−13.00
−13.31
−13.63
−14.68
−16.78
(가) 물가 길이 더 나은 ε의 범위는 대략 어디까지인가? (나) ε = 0.1일 때 두 값은 본문 표의 두 방법의 「마지막 100 에피소드의 평균 리턴」과 비교하면 어떤가? (다) 위젯에서 「문제 5 설정 불러오기」로 ε = 0.02를 넣고, SARSA의 길이 어떻게 바뀌는지 보라.
선생님
민준 학생, 무작위 스텝이 1% 만 있어도 물가 길이 위험할까요?
김민준
위험하죠. 강물이 −50 이니까요. 조금만 섞여도 안쪽 길이 낫지 않을까요?
선생님
표의 0.01 칸을 읽어 볼까요.
김민준
물가 −12.37, 안쪽 −13.31 이라 물가가 아직 나아요. 0.02 에서는 −13.80 대 −13.63 으로 뒤집히고요.
선생님
그럼 두 길이 같아지는 곳은요?
김민준
0.01 과 0.02 사이 어딘가네요. 스크립트로 이분법을 돌리면 0.0185 쯤이에요.
이서연
왜 하필 0.02 근처일까? 일단 물가 길은 두 스텝을 아끼니까 2점을 먼저 벌고 시작해.
선생님
그럼 물가 길은 무작위 스텝 때문에 얼마를 잃는지 어림해 볼 수 있어요?
이서연
무작위 스텝이 아래로 갈 확률은 스텝마다 ε/4 이고, 물가 옆을 아홉 칸쯤 지나요. 그러면 빠지는 기대 횟수가 대략 9 × ε/4 예요.
선생님
한 번 빠지면 얼마나 잃죠?
이서연
−50 에다 처음부터 다시 걸으니까… 60쯤 잃는다고 칠게요. 그럼 2 = 9 × ε/4 × 60 에서 ε ≈ 0.015. 어림으로도 비슷하네요.
선생님
(나)는요?
이서연
ε = 0.1 에서 물가 길 −27.67 은 Q-러닝의 −27.19 와, 안쪽 길 −16.78 은 SARSA 의 −17.51 과 가까워요.
선생님
Q-러닝이 받은 리턴은 왜 물가 길 쪽 값에 붙었을까요?
이서연
음… Q-러닝은 표로는 물가 길을 고르고, 걷기는 무작위 스텝을 섞어 걸으니까요. 실제로 받은 리턴이 「물가 길을 ε = 0.1 로 걸은 값」이 된 거예요. SARSA 는 무작위 스텝까지 셈에 넣고 그때 가장 좋은 길을 고른 거고요.
선생님
그래요. 같은 세상에서 「무작위 스텝을 셈에 넣을지」가 두 방법을 가른 것이에요. 무작위 스텝이 드물어지면 두 방법이 고르는 길도 가까워지고요. (다)는 위젯에서 직접 보세요.
김민준
시험 볼 때 계산 실수를 자주 하면 검산 시간을 넉넉히 잡는 안전한 풀이가 낫고, 실수가 거의 없으면 빠른 풀이가 나은 거랑 같네요.
정리 (가) ε가 0.0185쯤보다 작으면 물가 길, 크면 안쪽 길의 기대 리턴이 크다. (나) 물가 길 −27.67 ≈ Q-러닝의 −27.19, 안쪽 길 −16.78 ≈ SARSA의 −17.51. Q-러닝은 무작위 스텝이 없을 때의 최선(물가 길)을 배우고, SARSA는 지금의 무작위 스텝을 셈에 넣은 최선을 배운다. 탐색 확률이 0으로 줄면 두 방법이 고르는 길도 같아진다. (다) ε = 0.02는 갈림점 0.0185 바로 위라 두 길의 기대 리턴 차이가 0.17뿐이다. 위젯의 처음 난수에서 SARSA의 학습 20번은 한 길로 모이지 않고, 가장 많이 나온 길도 20번 가운데 6번뿐인 11스텝 물가 길이다.
문제 6. 어제 모은 경험 하나
리플레이 버퍼에 어제의 정책이 걸은 한 스텝이 저장되어 있다. 기록은 (칸 s, 방향 a, 보상 −1, 다음 칸 s′, 어제의 정책이 s′에서 고른 방향 a어제′)이다. 지금 표에서 Q(s,a) = −15, Q(s′,a어제′) = −20, maxa′Q(s′,a′) = −12이다(오늘의 정책은 s′에서 그 가장 큰 쪽을 고른다). 학습률 0.5. (가) 이 기록으로 SARSA와 Q-러닝이 각각 고친 값은? (나) 어느 쪽이 「오늘의 정책」의 값을 배우는가?
선생님
민준 학생, 기록에 다음 방향까지 적혀 있으니 SARSA 로도 이 기록을 쓸 수 있겠죠?
김민준
네, 다섯 개가 다 있으니까요. SARSA 는 목표 −1 + (−20) = −21, 고친 값 −15 + 0.5 × (−21 + 15) = −18 이요.
선생님
Q-러닝은요?
김민준
목표 −1 + (−12) = −13, 고친 값 −15 + 0.5 × (−13 + 15) = −14 예요. 둘 다 오늘의 표를 고치는 거니까 둘 다 오늘의 정책을 배우는 거고요.
선생님
SARSA 목표에 들어간 −20 은 누가 고른 방향의 값이죠?
김민준
어제의 정책이 s′ 에서 고른 방향이요. 오늘의 정책은 거기서 −12 짜리 방향을 고르는데요.
이서연
그럼 SARSA 가 이 기록으로 배우는 건 「여기서 a 로 가고, 그다음은 어제처럼 걷는」 정책의 값이야. 기록이 많이 쌓이면 표가 어제의 정책 쪽으로 끌려가.
선생님
Q-러닝은요?
이서연
Q-러닝 목표에는 −12 가 들어갔으니까… 기록에서 다음 방향을 아예 안 꺼냈네요.
선생님
그럼 Q-러닝은 기록을 어디까지 믿는 거예요?
이서연
다음 칸까지만이요. 그 칸의 최선은 지금 표로 셈하니까 어제 기록으로도 오늘 정책의 값을 배워요. 리플레이 버퍼가 Q-러닝이랑 짝이 맞는 까닭이 이거네요.
김민준
작년 기출 답안으로 공부할 때, 작년 학생의 풀이 순서를 그대로 따라가면 작년 학생의 점수를 배우는 거고, 문제만 가져와서 지금 제가 아는 최선으로 풀어 봐야 제 실력을 재는 거랑 같네요.
정리 (가) SARSA: 목표 −21, 고친 값 −18. Q-러닝: 목표 −13, 고친 값 −14. (나) Q-러닝. SARSA의 목표에는 기록 속 어제의 다음 행동이 들어가 어제의 정책 쪽 값을 배운다. Q-러닝의 목표는 기록에서 (칸, 방향, 보상, 다음 칸) 넷만 쓰고 다음 칸의 최선은 지금 표에서 셈하므로, 오래된 경험도 지금 목표 정책의 학습에 쓸 수 있다.
