강화학습 기초: 에이전트, 환경, 보상의 언어

지난 글에서 수십억 개 아이템을 투타워와 ANN으로 수백 개까지 좁힌 뒤, 그 좁혀진 자리에서 LLM이 최종 순위와 추천 이유를 만드는 2단계 서빙 구조를 봤다. 그 파이프라인 전체가 깔고 있는 전제는 과거 로그가 정답이라는 것이었다 — 보여 주지 않은 아이템은 클릭될 기회조차 없으니 영영 0으로 남는다. 행동을 직접 고르고 그 결과로 돌아온 신호에서 배우는 틀이 필요하다는 뜻이다. 이번 글부터는 그 틀, 강화학습(Reinforcement Learning, RL)을 다룬다. 정답 레이블이 없고, 스스로 고른 행동이 받아 온 점수만으로 배운다. 바둑에서 인간 챔피언을 꺾은 AlphaGo, ChatGPT를 다듬은 RLHF, 로봇 제어의 의사결정까지 이 틀 위에 서 있다.

강화학습의 틀

시행착오 학습

어린아이가 자전거를 배우는 과정을 떠올려 보자. 누구도 매 순간 「지금은 핸들을 3도 왼쪽으로」라고 정답을 붙여 주지 않는다. 아이는 핸들을 이리저리 돌리고, 넘어지고, 균형을 잡으면서 어떤 움직임이 오래 달리게 해 주는지를 스스로 알아낸다. 넘어지면 아프고 잘 달리면 즐겁다는 신호만 있을 뿐, 어느 동작이 넘어짐의 원인이었는지는 아무도 가르쳐 주지 않는다.

지도학습과 갈리는 자리가 여기다. 지도학습의 데이터는 「이 입력의 정답은 이것」이라는 쌍이고, 모델은 틀린 만큼 정확히 고쳐진다. 강화학습에는 그런 쌍이 없다. 받는 것은 점수 하나이고, 그 점수는 늦게 오고 뭉뚱그려져 온다. 바둑에서 이겼다는 +1은 200수를 둔 뒤에 한 번 오는데, 200수 가운데 어느 수가 승리를 만들었는지는 스스로 가려내야 한다. 이 「공로를 어느 행동에 돌리나」 문제를 신용 할당(credit assignment)이라 부르고, 이 글의 뒤쪽 도구들 — 할인율, 가치 함수, 벨만 방정식 — 은 전부 이 문제를 푸는 장치다.

또 하나의 차이는 데이터가 스스로의 선택에 달려 있다는 점이다. 지도학습의 데이터셋은 모델이 무엇을 예측하든 그대로지만, 강화학습에서는 어느 쪽으로 가 보느냐가 다음에 볼 데이터를 정한다. 한 번도 안 가 본 길의 점수는 영영 모른다. 지난 글의 추천 로그가 빠졌던 함정과 같은 모양이고, 뒤에서 볼 탐험 전략이 이 문제를 맡는다.

구성 요소

그림의 두 상자부터 이름을 붙인다. 결정을 내리는 쪽이 에이전트(agent)이고, 에이전트 바깥의 모든 것이 환경(environment)이다. 로봇이라면 제어 프로그램이 에이전트이고, 모터와 바닥과 중력은 전부 환경 쪽이다. 둘은 한 걸음마다 세 가지를 주고받는다.

환경이 에이전트에게 지금 상황을 보여 주는 것이 상태(state) $s$ 다. CartPole에서는 카트 위치·카트 속도·막대 각도·막대 각속도의 네 숫자가, 체스에서는 판 위 말의 배치 전체가 상태다. 에이전트는 그 상태를 보고 행동(action) $a$ 하나를 고른다. CartPole의 행동은 카트를 왼쪽이나 오른쪽으로 미는 두 가지뿐이고, 로봇 팔이라면 관절마다 가할 토크처럼 연속된 값이다. 행동을 받은 환경은 다음 상태로 넘어가면서 숫자 하나를 돌려주는데, 이것이 보상(reward) $r$ 이다. CartPole은 막대가 서 있는 걸음마다 +1을, 바둑은 대국이 끝날 때 이기면 +1 지면 −1을 준다.

에이전트가 상태를 보고 행동을 고르는 규칙이 정책(policy) $\pi$ 다. 정책은 에이전트 안에 든 유일한 결정 장치이고, 강화학습에서 학습이란 곧 이 정책을 고치는 일이다. 확률로 적으면 $\pi(a \mid s)$ 는 상태 $s$ 에서 행동 $a$ 를 고를 확률이다. 그리고 어떤 상태에서 출발해 그 정책을 계속 따랐을 때 앞으로 받을 보상을 모두 더한 것의 평균이 그 상태의 가치(value)다. 가치는 상태만의 성질이 아니라 정책에 딸린 값이라는 점이 중요하다. 같은 칸이라도 서툰 정책으로 서 있으면 가치가 낮고 능숙한 정책으로 서 있으면 높다. 그래서 두 개념은 서로를 고치며 돈다 — 정책을 정하면 가치가 정해지고, 가치를 보면 더 나은 정책이 보인다. 뒤의 동적 계획법 절이 이 순환을 실제 숫자로 돌린다.

Gymnasium 루프

Gymnasium은 OpenAI Gym을 이어받은 강화학습 환경 라이브러리이고, 위 그림의 루프를 reset과 step 두 함수로 그대로 옮겨 놓았다.

import gymnasium as gym
import numpy as np

# CartPole 환경: 막대를 쓰러뜨리지 않고 카트를 움직이는 문제
env = gym.make("CartPole-v1")

# 환경 정보 확인
print(f"상태 공간: {env.observation_space}")   # Box(4,) — 4차원 연속
print(f"행동 공간: {env.action_space}")         # Discrete(2) — 0: 왼쪽, 1: 오른쪽
print(f"최대 스텝: {env.spec.max_episode_steps}")  # 500

# 랜덤 에이전트 테스트
episode_rewards = []
for episode in range(20):
    state, _ = env.reset()
    total_reward = 0
    step = 0

    while True:
        # 랜덤 정책: 행동 공간에서 균등 샘플링
        action = env.action_space.sample()

        # 환경 스텝: 행동 실행 → (다음상태, 보상, 종료여부, 잘림여부, 정보)
        next_state, reward, done, truncated, info = env.step(action)

        total_reward += reward
        step += 1
        state = next_state

        if done or truncated:
            break

    episode_rewards.append(total_reward)

print(f"평균 보상: {np.mean(episode_rewards):.1f}")  # 약 20~25 (랜덤이라 낮음)
# 최적 에이전트: 500 달성 가능

env.step(action)이 돌려주는 다섯 값이 한 걸음의 전부다. next_state는 행동 뒤의 새 상태, reward는 그 걸음의 보상이다. 시작부터 끝까지 한 판을 에피소드(episode)라 부르는데, 에피소드가 끝나는 방식이 둘이라 플래그도 둘이다. done(Gymnasium의 이름으로는 terminated)은 막대가 쓰러지는 것처럼 과제 안에서 진짜로 끝난 경우이고, truncated는 500걸음 제한처럼 바깥에서 끊은 경우다. 이 둘을 섞으면 안 되는 이유가 뒤의 가치 계산에서 드러난다 — 진짜로 끝난 뒤에는 미래가 0이지만, 시간 제한으로 끊긴 뒤에는 미래가 여전히 남아 있다.

무작위 정책은 평균 20걸음 남짓에서 막대를 쓰러뜨린다. 매 걸음 +1이니 에피소드 보상 20 안팎이고, 잘 학습한 에이전트는 상한인 500을 채운다. 이 스물다섯 배 차이를 메우는 것이 정책을 고치는 일이다.

MDP

마르코프 성질

강화학습 문제를 수학으로 다룰 때는 MDP(Markov Decision Process, 마르코프 결정 과정)라는 틀에 담는다. 이 틀이 기대는 가정은 하나다. 다음 상태는 지금 상태와 지금 행동만으로 정해지고, 거기까지 어떻게 왔는지는 상관없다는 것이다. 이것을 마르코프 성질이라 부른다.

$$P(s_{t+1} \mid s_t, a_t) = P(s_{t+1} \mid s_0, a_0, \ldots, s_t, a_t)$$

체스와 바둑은 이 성질을 그대로 만족한다. 판 위의 배치만 보면 다음에 무엇이 가능한지 다 알 수 있고, 어떤 순서로 그 배치에 왔는지는 필요 없다. CartPole도 네 숫자에 속도가 들어 있어서 만족한다. 만약 상태에서 속도를 빼고 위치와 각도만 준다면 성질이 깨진다 — 막대가 지금 오른쪽으로 쓰러지는 중인지 되돌아오는 중인지 한 장면으로는 알 수 없기 때문이다. Atari 게임을 배울 때 화면 한 장이 아니라 연속된 네 장을 겹쳐 상태로 쓰는 것이 바로 이 구멍을 메우려는 조치다.

포커처럼 상대의 패가 가려진 게임은 아무리 겹쳐도 관측만으로 상태가 다 드러나지 않는다. 이런 경우를 부분 관측 MDP(POMDP)라 부르고, 에이전트는 가려진 부분에 대한 믿음을 따로 들고 다녀야 한다.

전이 확률과 보상 함수

MDP는 다섯 가지로 적는다.

MDP = (S, A, P, R, γ)
  S: 상태 공간
  A: 행동 공간
  P(s'|s,a): 상태 전이 확률
  R(s,a): 보상 함수
  γ: 할인율

상태 공간과 행동 공간은 앞 절의 상태와 행동을 모아 놓은 집합이다. 나머지 둘이 환경의 규칙이다. 전이 확률 $P(s' \mid s, a)$ 는 상태 $s$ 에서 행동 $a$ 를 했을 때 다음 상태가 $s'$ 일 확률이고, 보상 함수 $R(s, a)$ 는 그때 받는 보상의 기댓값이다. 환경이 결정론이면 전이 확률은 한 칸만 1이고 나머지가 0이다.

FrozenLake의 미끄러운 모드가 확률 전이의 좋은 예다. 오른쪽으로 가라고 해도 얼음 위라 셋 중 하나의 확률로만 오른쪽에 가고, 나머지는 위나 아래로 미끄러진다. 그래서 $P(\text{오른쪽 칸} \mid s, \rightarrow) = 1/3$ 이다. 같은 행동이 같은 결과를 보장하지 않으므로, 좋은 정책은 「가장 빠른 길」이 아니라 「미끄러져도 구멍에 안 빠지는 길」이 된다.

이 전이 확률과 보상 함수를 통틀어 환경의 모델이라 부른다. 모델을 알면 걸어 보지 않고도 머릿속에서 계산으로 답을 낼 수 있고, 모르면 직접 걸어 보고 배워야 한다. 이 갈림이 뒤의 동적 계획법과 MC·TD를 가른다.

누적 보상

에이전트의 목표는 이번 걸음의 보상이 아니라 앞으로 받을 보상 전체다. 시점 $t$ 부터 받을 보상을 할인해 더한 것을 반환값(return) $G_t$ 라 부른다.

$G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}$

$k$ 걸음 뒤의 보상은 $\gamma^k$ 배로 깎여 들어온다. 앞 절의 가치를 이 낱말로 다시 적으면, 가치는 정책을 따랐을 때 반환값의 기댓값이다. 반환값은 한 번의 에피소드에서 실제로 나온 숫자이고, 가치는 그 숫자를 여러 번 뽑았을 때의 평균이다.

반환값이 등장하는 순간 신용 할당이 수식이 된다. 마지막에 받은 +1은 그 앞 모든 걸음의 반환값에 조금씩 들어간다. 한 걸음 앞에는 $\gamma$ 만큼, 열 걸음 앞에는 $\gamma^{10}$ 만큼. 가까운 행동일수록 공을 더 많이 받는다.

할인율

$\gamma$ 가 할인율(discount factor)이고, 0과 1 사이의 값이다. 할인율이 필요한 이유는 둘이다. 첫째, 끝나지 않는 과제에서 합이 무한대로 가지 않게 막는다. 매 걸음 보상이 많아야 $r_{\max}$ 라면 반환값은 $r_{\max} / (1 - \gamma)$ 를 넘지 못한다. 둘째, 먼 미래일수록 불확실하다는 사실을 반영한다. 지금 받는 100원이 1년 뒤의 100원보다 낫다는 시간 선호와 같은 발상이다.

할인율을 고르는 손잡이로 읽으려면 실질 지평선으로 바꿔 보면 된다. 에이전트가 사실상 몇 걸음 앞까지 신경 쓰는지를 나타내는 값이고, 대략 $1/(1-\gamma)$ 다. $\gamma = 0.9$ 면 10걸음, $\gamma = 0.99$ 면 100걸음, $\gamma = 0.999$ 면 1,000걸음이다. 근거는 무게가 줄어드는 속도에 있다. $0.9^{10} \approx 0.35$ 이고 $0.99^{100} \approx 0.37$ 이다. 지평선만큼 떨어진 보상은 어느 경우든 무게가 약 $1/e$ 로 줄어 있고, 그 뒤로는 빠르게 사라진다.

CartPole에 대입해 보면 숫자가 딱 맞게 떨어진다. 매 걸음 +1을 받고 $\gamma = 0.99$ 면 끝없이 서 있을 때 반환값의 상한이 $1/0.01 = 100$ 이다. 500걸음에서 끊기는 실제 에피소드는 $(1 - 0.99^{500})/0.01 \approx 99.3$ 이다. 500걸음을 버틴 것과 무한히 버틴 것이 에이전트 눈에는 거의 같다는 뜻이고, 이 과제의 지평선이 100걸음이면 충분하다는 뜻이기도 하다.

반대로 지평선이 과제보다 짧으면 학습이 무너진다. 목표까지 최소 50걸음이 걸리는 미로에 $\gamma = 0.9$ 를 쓰면 출발점에서 보는 목표 보상은 $0.9^{50} \approx 0.005$ 다. 값의 대부분이 반올림 오차와 구분이 안 되는 크기라, 정책은 목표 쪽과 반대쪽을 가려내지 못한다. 그래서 흔한 출발점은 이렇다.

• 짧은 게임·보상이 촘촘한 과제: 0.9~0.95
• Atari·CartPole 같은 표준 벤치마크: 0.99
• 수천 걸음 뒤에야 결과가 나는 과제: 0.995~0.999

$\gamma$ 를 1에 가깝게 올리는 것도 공짜가 아니다. 먼 미래까지 더하는 만큼 반환값의 분산이 커지고, 학습이 불안정해진다. 지평선은 과제가 요구하는 만큼만 늘리는 값이다.

가치 함수

상태 가치와 행동 가치

가치를 적는 함수는 둘이다. 상태 가치 함수 $V^\pi(s)$ 는 상태 $s$ 에서 출발해 정책 $\pi$ 를 따를 때의 기대 반환값이고, 행동 가치 함수 $Q^\pi(s, a)$ 는 상태 $s$ 에서 첫 행동만 $a$ 로 정해 두고 그 뒤로 $\pi$ 를 따를 때의 기대 반환값이다. $Q$ 는 $V$ 에서 첫 걸음의 선택권만 떼어 낸 것이다.

그래서 둘은 서로 바꿔 적을 수 있다. $V$ 는 정책이 각 행동을 고를 확률로 $Q$ 를 평균 낸 것이다.

$$V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a)$$

거꾸로 $Q$ 는 한 걸음 걸어 받은 보상에 다음 상태의 $V$ 를 할인해 더한 것이다.

$$Q^\pi(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s')$$

두 번째 식에는 전이 확률 $P$ 가 들어 있다. $V$ 만 들고 있으면 행동을 고를 때 「이 행동을 하면 어디로 갈까」를 모델에 물어야 하지만, $Q$ 를 들고 있으면 각 행동의 값이 이미 적혀 있어 모델 없이도 고를 수 있다. 모델을 모르는 대부분의 알고리즘이 $V$ 가 아니라 $Q$ 를 배우는 까닭이다.

벨만 기대 방정식

위 두 식을 하나로 합치면 $V$ 가 자기 자신으로 적힌다.

$$V^\pi(s) = \sum_a \pi(a \mid s) \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s') \right]$$

이것이 벨만 기대 방정식이다. 「지금 칸의 가치 = 이번 걸음 보상의 평균 + 다음 칸 가치의 할인된 평균」이라는 한 줄이다. 반환값 $G_t$ 가 $r_t + \gamma G_{t+1}$ 로 쪼개지는 것을 기댓값으로 옮겨 적은 것뿐이지만, 효과는 크다. 무한히 이어지는 미래의 합이 이웃 칸들 사이의 관계식으로 바뀐다. 상태가 $n$ 개면 미지수 $n$ 개짜리 연립 일차방정식이 되고, 원리상 한 번에 풀 수 있다.

손으로 풀어 볼 예제를 하나 세운다. 칸이 1·2·3으로 일렬로 놓인 복도이고, 3번 칸 오른쪽에 목표가 있다. 행동은 왼쪽과 오른쪽 둘이고 전이는 결정론이다. 1번 칸에서 왼쪽으로 가면 벽에 막혀 제자리에 남는다. 3번 칸에서 오른쪽으로 가 목표에 들어설 때만 보상 1을 받고 에피소드가 끝나며, 나머지 걸음은 전부 보상 0이다. $\gamma = 0.9$ 로 둔다.

정책은 왼쪽과 오른쪽을 반반으로 고르는 무작위 정책이다. 벨만 기대 방정식을 칸마다 쓰면 이렇다.

$$\begin{aligned} V(1) &= 0.5 \times 0.9\,V(1) + 0.5 \times 0.9\,V(2) \\ V(2) &= 0.5 \times 0.9\,V(1) + 0.5 \times 0.9\,V(3) \\ V(3) &= 0.5 \times 0.9\,V(2) + 0.5 \times 1 \end{aligned}$$

세 식을 풀면 $V(1) \approx 0.43$, $V(2) \approx 0.52$, $V(3) \approx 0.74$ 다. 목표 바로 옆인 3번 칸도 0.74에 그치는 것은 반쯤은 왼쪽으로 돌아가 버리기 때문이다. 이 숫자들이 무작위 정책의 성적표다.

벨만 최적 방정식

정책을 고정하지 않고 「매 칸에서 가장 좋은 행동을 고른다」고 하면 평균이 최댓값으로 바뀐다.

$$V^*(s) = \max_a \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^*(s') \right]$$

이것이 벨만 최적 방정식이고, $V^*$ 는 어떤 정책으로도 넘을 수 없는 가치, 곧 최적 가치 함수다. 기대 방정식과 모양은 거의 같지만 성질이 다르다. 기대 방정식은 정책이 정해져 있어 일차방정식이고 한 번에 풀린다. 최적 방정식은 $\max$ 가 끼어 비선형이라 한 번에 안 풀리고, 되풀이해서 다가가야 한다.

복도에서는 답을 눈으로 알 수 있다. 어디서든 오른쪽으로 가면 되므로 3번 칸은 1, 2번 칸은 한 걸음 더 멀어 $0.9$, 1번 칸은 $0.81$ 이다. 무작위 정책의 0.43·0.52·0.74와 견주면 정책 하나가 가치를 얼마나 바꾸는지 보인다. 같은 방정식을 $Q$ 로 적은 형태, 곧 $Q^*(s, a)$ 에 대한 벨만 최적 방정식은 다음 글에서 Q-러닝의 출발점으로 다시 만난다.

동적 계획법

정책 평가

모델을 안다면 벨만 방정식을 되풀이 계산으로 풀 수 있다. 이 방법들을 묶어 동적 계획법(dynamic programming, DP)이라 부른다. 큰 문제를 겹치는 작은 문제로 쪼개 그 답을 재활용한다는 뜻이고, 여기서 작은 문제는 이웃 칸의 가치다.

첫 번째 도구는 정해진 정책의 가치를 구하는 정책 평가다. 모든 칸의 값을 0으로 두고, 벨만 기대 방정식의 오른쪽을 계산해 왼쪽에 덮어쓰는 일을 모든 칸에 한 바퀴씩 되풀이한다. 한 바퀴를 스윕(sweep)이라 부른다. 복도의 무작위 정책으로 돌리면 이렇게 된다.

• 스윕 1: 3번 칸만 오른쪽 보상의 절반을 받아 $(0, 0, 0.5)$
• 스윕 2: 2번 칸이 3번의 0.5를 반만 할인해 받아 $(0, 0.225, 0.5)$
• 스윕 3: 1번이 $0.45 \times 0.225 \approx 0.101$, 3번이 $0.5 + 0.45 \times 0.225 \approx 0.601$ 이 되어 $(0.101, 0.225, 0.601)$

값이 목표 쪽에서 한 칸씩 거꾸로 번지는 것이 보인다. 스윕을 계속하면 앞 절에서 연립방정식으로 푼 $(0.43, 0.52, 0.74)$ 에 한없이 다가간다. $\gamma < 1$ 이면 한 스윕마다 오차가 적어도 $\gamma$ 배로 줄어든다는 것이 증명되어 있어, 수렴은 보장된다.

정책 개선

가치를 알았으면 정책을 고친다. 각 칸에서 행동마다 「이번 보상 + 할인된 다음 칸 가치」를 계산해 가장 큰 쪽을 고르는 것, 곧 가치에 대해 욕심껏 행동하는 새 정책을 만드는 것이 정책 개선이다.

무작위 정책의 가치로 해 보자. 3번 칸에서 오른쪽은 보상 1, 왼쪽은 $0.9 \times 0.52 \approx 0.47$ 이니 오른쪽이다. 2번 칸에서 오른쪽은 $0.9 \times 0.74 \approx 0.66$, 왼쪽은 $0.9 \times 0.43 \approx 0.39$ 이니 오른쪽이다. 1번 칸에서 오른쪽은 0.47, 왼쪽은 벽에 막혀 제자리라 $0.9 \times 0.43 \approx 0.39$ 이니 역시 오른쪽이다. 한 번 개선했는데 벌써 최적 정책 「언제나 오른쪽」이 나왔다.

이 두 걸음, 평가하고 개선하고 다시 평가하는 순환을 정책 반복(policy iteration)이라 부른다. 개선된 정책은 적어도 옛 정책만큼은 좋다는 정책 개선 정리가 있어서, 정책이 더는 안 바뀔 때 그것이 최적이다. 복도는 한 바퀴로 끝났고, 작은 격자에서도 정책은 대개 몇 바퀴 만에 멈춘다. 대신 바퀴마다 정책 평가를 수렴할 때까지 돌려야 해서 한 바퀴가 비싸다.

가치 반복

정책 평가를 끝까지 돌리지 않고 한 스윕만 한 뒤 바로 개선해도 된다는 것이 가치 반복(value iteration)의 발상이다. 평가와 개선을 한 식에 접으면 벨만 최적 방정식의 오른쪽을 그대로 덮어쓰는 모양이 된다. 정책은 따로 들고 있지 않고, 값이 수렴한 뒤에 각 칸에서 최선의 행동을 한 번 읽어 내면 끝이다.

그림 1이 복도에서 가치 반복을 돌린 결과다. 모든 칸의 값을 0으로 두고 시작한다. 스윕 1에서 3번 칸은 오른쪽이 보상 1, 왼쪽이 $0.9 \times 0 = 0$ 이라 1이 되고, 나머지 칸은 이웃이 아직 0이라 그대로 0이다. 스윕 2에서 2번 칸이 $0.9 \times 1 = 0.9$ 를 받는다. 스윕 3에서 1번 칸이 $0.9 \times 0.9 = 0.81$ 을 받고, 스윕 4에서는 아무 값도 안 바뀌어 멈춘다. 앞 절에서 눈으로 구한 $(0.81, 0.9, 1)$ 과 같다.

값이 번지는 방향과 속도가 정책 평가 때와 같다는 점을 짚어 두자. 목표에서 $k$ 칸 떨어진 칸은 $k$ 번째 스윕에야 처음으로 값을 받는다. 동적 계획법의 약점도 여기서 보인다. 스윕 한 번이 모든 상태를 훑고, 칸마다 가능한 다음 상태를 전부 더한다. 상태가 셋이면 손으로 되지만 바둑처럼 상태가 $10^{170}$ 개쯤 되면 한 스윕도 못 끝낸다. 그리고 무엇보다, 이 계산 전체가 전이 확률 $P$ 를 안다는 전제 위에 서 있다.

MC와 TD

모델 프리

현실의 과제는 대개 모델을 주지 않는다. 로봇이 바닥에서 얼마나 미끄러질지, 사용자가 추천을 보고 무엇을 누를지는 식으로 적혀 있지 않다. 모델 없이 경험만으로 가치나 정책을 배우는 방법을 모델 프리(model-free)라 부른다. 할 수 있는 것은 실제로 걸어 보고 나온 상태와 보상을 기록하는 것뿐이다.

모델이 빠지면 벨만 방정식의 $\sum_{s'} P(s' \mid s, a)$ 를 계산할 수 없다. 두 갈래의 대안이 있다. 하나는 기댓값을 에피소드 끝까지 실제로 받은 반환값의 평균으로 바꾸는 것이고, 다른 하나는 한 걸음만 걸어 보고 나머지는 지금 추정한 가치로 메우는 것이다. 앞쪽이 몬테카를로, 뒤쪽이 TD다. 둘 다 여기서는 정해진 정책의 $V$ 를 추정하는 평가 문제로 본다 — 평가를 정책 개선과 엮어 정책까지 배우는 일은 다음 글의 Q-러닝이 맡는다.

몬테카를로 평가

몬테카를로(Monte Carlo, MC) 평가는 가장 곧이곧대로인 방법이다. 에피소드를 끝까지 돌리고, 지나간 칸마다 거기서부터 실제로 받은 반환값을 계산해, 그 칸의 추정값을 반환값 쪽으로 옮긴다.

$$V(s_t) \leftarrow V(s_t) + \alpha \left[ G_t - V(s_t) \right]$$

$\alpha$ 는 학습률로, 새 반환값과 옛 추정의 차이 가운데 몇 할을 반영할지 정한다. 복도에서 무작위 정책으로 에피소드 하나를 돌려 보자. 2번에서 오른쪽으로 3번, 왼쪽으로 다시 2번, 오른쪽으로 3번, 오른쪽으로 목표에 들어가 보상 1을 받았다. 처음 2번에 섰던 시점에서 목표까지 네 걸음이고 보상은 마지막에 한 번이니 반환값은 $0.9^3 = 0.729$, 처음 3번에 섰던 시점의 반환값은 $0.9^2 = 0.81$ 이다. $\alpha = 0.1$ 로 처음 방문만 반영하면 $V(2)$ 는 0에서 0.0729로, $V(3)$ 은 0.081로 오른다.

MC의 장점은 추정이 치우치지 않는다는 것이다. 반환값은 진짜 가치에서 뽑은 표본 그대로라, 평균을 충분히 내면 정확히 참값에 간다. 단점은 둘이다. 에피소드가 끝나야 갱신할 수 있어 끝나지 않는 과제에는 못 쓰고, 반환값에 에피소드 전체의 운이 다 쌓여 분산이 크다. 같은 칸에서 출발해도 운 좋게 네 걸음 만에 끝나면 0.729, 열 걸음을 헤매면 $0.9^9 \approx 0.39$ 이니 표본끼리 차이가 두 배 가까이 난다.

TD와 부트스트래핑

TD(Temporal Difference, 시간차) 학습은 한 걸음만 걷고 곧바로 고친다. 가장 단순한 형태인 TD(0)의 갱신식은 이렇다.

$$V(s_t) \leftarrow V(s_t) + \alpha \left[ r_t + \gamma V(s_{t+1}) - V(s_t) \right]$$

MC의 $G_t$ 자리에 $r_t + \gamma V(s_{t+1})$ 이 들어갔다. 끝까지 가서 받을 반환값을 기다리는 대신, 받은 보상 하나에 다음 칸의 지금 추정값을 붙여 그 자리를 채운 것이다. 이렇게 추정값으로 추정값을 고치는 것을 부트스트래핑(bootstrapping)이라 부른다. 대괄호 안이 한 걸음 사이에 예상이 빗나간 정도이고, 이 차이가 TD라는 이름의 출처다.

그림 2는 같은 에피소드를 두 방식으로 처리한 결과를 나란히 놓았다. TD로 돌리면 앞의 세 걸음은 보상이 0이고 다음 칸의 추정값도 아직 0이라 타깃이 0이다. 아무것도 안 바뀐다. 마지막 걸음에서만 $V(3)$ 이 $0.1 \times 1 = 0.1$ 로 오른다. 에피소드 하나가 끝났을 때 MC는 지나간 두 칸을 다 고쳤고, TD는 목표 옆 한 칸만 고쳤다. 대신 다음 에피소드부터는 TD에서 $V(3) = 0.1$ 이 2번 칸으로 번지기 시작하고, 앞의 동적 계획법에서 본 한 칸씩 거꾸로 번지는 모양이 모델 없이 다시 나타난다.

두 방법의 성격은 거울처럼 맞선다. TD의 타깃은 틀릴 수 있는 추정값을 섞어 쓰므로 치우침이 있지만, 한 걸음의 운만 들어가 분산이 작다. 에피소드가 끝나기를 기다리지 않으니 끝없는 과제에서도 걸음마다 배운다. 실제로는 TD 쪽이 대개 빨리 수렴해서, Q-러닝·DQN·액터-크리틱처럼 뒤에 나올 알고리즘 대부분이 TD의 부트스트래핑 위에 서 있다. 둘 사이를 잇는 방법도 있다. $n$ 걸음까지 실제 보상을 쓰고 그 뒤를 추정값으로 메우는 n-step TD가 그것이고, $n$ 이 1이면 TD(0), 에피소드 길이면 MC가 된다.

앞 절에서 미뤄 둔 truncated의 쓰임이 여기서 나온다. 막대가 쓰러져 진짜로 끝났으면 다음 칸이 없으니 타깃은 $r_t$ 하나다. 500걸음 제한으로 끊겼을 뿐이면 그 뒤의 미래가 남아 있으므로 $\gamma V(s_{t+1})$ 을 그대로 더해야 한다. 둘을 같게 처리하면 에이전트는 499걸음째 상태를 「곧 세상이 끝나는 곳」으로 잘못 배운다.

탐험 전략

ε-greedy 감쇠

추정한 가치가 가장 높은 행동만 고르는 것을 활용(exploitation), 가치가 낮거나 모르는 행동을 일부러 해 보는 것을 탐험(exploration)이라 부른다. 활용만 하면 처음에 우연히 좋아 보인 길에 갇히고, 탐험만 하면 배운 것을 써먹지 못한다. 이 줄다리기가 앞에서 말한 「안 가 본 길은 영영 모른다」 문제의 실체다.

가장 흔한 답은 ε-greedy다. 확률 $\varepsilon$ 으로 아무 행동이나 고르고, 나머지 확률로는 가장 가치 높은 행동을 고른다. 학습 초기에는 가치 추정이 엉터리이니 $\varepsilon = 1$ 에서 시작해 점점 줄인다. 예컨대 500 에피소드에 걸쳐 1.0에서 0.01까지 선형으로 내리면, 250 에피소드째에는 절반쯤 무작위로 걷고 500 에피소드 이후에는 100걸음에 한 번만 딴 길로 샌다. 곱셈으로 줄이는 방식과 바닥값을 남기는 이유는 다음 글이 Q-러닝의 숫자로 자세히 따라간다.

ε-greedy의 약점은 탐험이 눈먼 무작위라는 것이다. 행동이 둘일 때 $\varepsilon = 0.1$ 이면 최선의 행동을 0.95, 나머지를 0.05의 확률로 고른다. 두 행동의 가치가 1.0과 0.99로 거의 같든 1.0과 −100으로 하늘과 땅 차이든 확률은 똑같다. 절벽이 뻔히 보이는 칸에서도 5%의 확률로 뛰어든다.

볼츠만 탐험

볼츠만 탐험(softmax 탐험)은 가치 차이를 확률에 반영한다. 각 행동을 고를 확률을 가치의 지수에 비례하게 둔다.

$$\pi(a \mid s) = \frac{\exp\big(Q(s, a)/\tau\big)}{\sum_b \exp\big(Q(s, b)/\tau\big)}$$

$\tau$ 는 온도로, 확률을 얼마나 고르게 펼지 정한다. 두 행동의 가치가 1.0과 0.5일 때 $\tau = 0.5$ 면 확률이 약 0.73과 0.27이다. $\tau = 0.1$ 로 식히면 0.993과 0.007로 거의 늘 좋은 쪽을 고르고, 온도를 높이면 반반에 가까워진다. 가치가 1.0과 −100이면 어떤 적당한 온도에서도 나쁜 쪽 확률이 사실상 0이다. ε-greedy가 못 하던, 「조금 나쁜 행동은 가끔 해 보고 아주 나쁜 행동은 안 한다」가 저절로 된다.

대가는 온도라는 손잡이가 가치의 크기에 묶여 있다는 점이다. 보상 단위를 100배 키우면 같은 $\tau$ 가 전혀 다른 행동을 만든다. 그래서 과제마다 온도를 다시 맞춰야 하고, ε처럼 에피소드에 따라 식히는 일정도 따로 정해야 한다.

UCB

앞의 둘은 「얼마나 좋아 보이나」만 본다. UCB(Upper Confidence Bound)는 「얼마나 모르나」도 본다. 가치 추정값에 불확실성만큼의 보너스를 더해 가장 큰 쪽을 고른다.

$$a_t = \arg\max_a \left[ Q(a) + c \sqrt{\frac{\ln t}{N(a)}} \right]$$

$N(a)$ 는 그 행동을 지금까지 해 본 횟수, $t$ 는 전체 걸음 수, $c$ 는 보너스의 세기다. 적게 해 본 행동일수록 분모가 작아 보너스가 크다. 숫자로 보면 $t = 100$ 에서 행동 A는 90번 해 보고 평균 0.6, 행동 B는 10번 해 보고 평균 0.5다. $c = 1$, $\ln 100 \approx 4.61$ 로 계산하면 A의 점수는 $0.6 + \sqrt{4.61/90} \approx 0.83$, B는 $0.5 + \sqrt{4.61/10} \approx 1.18$ 이다. 평균이 낮은 B를 고른다. 열 번의 표본으로 얻은 0.5는 아직 믿을 수 없고 실제로는 A보다 좋을 수도 있으니, 한 번 더 확인할 값어치가 있다는 판단이다. 확인할수록 $N(B)$ 가 커져 보너스가 줄고, B가 정말 나쁘면 자연히 덜 고르게 된다.

UCB는 상태가 하나뿐인 슬롯머신 문제, 곧 멀티암드 밴딧에서 이론적으로 가장 잘 다듬어진 방법이다. 상태가 많고 신경망으로 가치를 근사하는 과제에서는 칸마다 방문 횟수를 세기 어려워 그대로는 못 쓰고, 방문 횟수를 흉내 낸 보너스를 보상에 얹는 식으로 변형해 쓴다. 게임 트리 탐색에서는 원형 그대로 살아 있다. AlphaGo의 몬테카를로 트리 탐색이 어느 수를 더 깊이 읽을지 정할 때 쓰는 규칙이 UCB 계열이다.

알고리즘 지도

온·오프 정책

데이터를 모으는 정책과 배우려는 정책이 같은가 다른가로도 알고리즘이 갈린다. 같으면 온-정책(on-policy), 다르면 오프-정책(off-policy)이다.

두 부류의 차이가 가장 선명하게 드러나는 예가 서튼과 바르토의 교과서에 나오는 절벽 걷기다. 4×12 격자의 아래쪽 가장자리가 절벽이고, 한 걸음마다 −1, 절벽에 떨어지면 −100을 받고 출발점으로 돌아간다. 가장 짧은 길은 절벽 바로 위 줄을 따라가는 13걸음이다. 이 격자에서 $\varepsilon = 0.1$ 의 ε-greedy로 두 알고리즘을 돌린다. 온-정책인 SARSA는 자기가 실제로 할 행동, 곧 가끔 무작위로 발을 헛디디는 행동까지 가치에 넣는다. 절벽 옆 칸은 10% 확률로 떨어질 수 있는 위험한 칸으로 값이 매겨지고, 결과적으로 절벽에서 멀찍이 떨어진 먼 길을 배운다. 오프-정책인 Q-러닝은 「다음부터는 최선만 한다」고 가정하고 값을 매기므로 절벽 바로 옆 최단 경로를 배운다. 그런데 학습 중에는 여전히 ε 확률로 헛디디니, 걷는 동안 받는 점수는 오히려 SARSA 쪽이 높다.

어느 쪽이 옳은가는 무엇을 원하느냐에 달렸다. 배운 뒤 탐험을 끄고 쓸 거라면 Q-러닝의 최단 경로가 맞는 답이다. 배우는 동안의 실수가 실제 손해인 로봇이라면 SARSA의 조심성이 맞는 답이다. 오프-정책에는 한 가지 큰 이점이 더 있는데, 예전 정책이나 다른 에이전트가 모은 기록도 학습 재료로 쓸 수 있다는 것이다. 이 자유가 DQN의 경험 재생을 가능하게 하는 과정은 다음 글에서 따라간다.

세 갈래 분류

알고리즘을 나누는 축은 셋이다. 첫째는 앞 절들의 갈림, 곧 모델을 쓰는가다. 모델을 알거나 배워서 계획에 쓰면 모델 기반, 경험만으로 배우면 모델 프리다. AlphaGo는 바둑의 규칙이라는 완벽한 모델로 수를 미리 읽어 보는 모델 기반이고, 실제 응용의 대부분은 모델 프리다.

둘째는 무엇을 배우는가다. 가치 함수를 배우고 정책은 거기서 가장 가치 높은 행동을 뽑아 쓰면 가치 기반, 정책 자체를 매개변수로 두고 반환값이 커지는 쪽으로 직접 고치면 정책 기반이다. 둘을 합쳐 정책(액터)과 가치(크리틱)를 함께 배우는 것이 액터-크리틱이다. 셋째가 방금 본 온·오프 정책이다.

알고리즘	유형	특징
Q-Learning	가치 기반, 오프-정책	표로 푸는 이산 행동
DQN	가치 기반, 오프-정책	신경망 + 경험 재생
REINFORCE	정책 기반, 온-정책	단순하지만 분산 높음
PPO	액터-크리틱, 온-정책	이산·연속 모두, 안정적
SAC	액터-크리틱, 오프-정책	연속 행동, 엔트로피 보너스

표의 줄은 이 글의 도구가 어디로 이어지는지도 보여 준다. Q-러닝과 DQN은 벨만 최적 방정식을 TD로 푸는 것이고, REINFORCE는 몬테카를로 반환값으로 정책을 직접 밀어 올리며, PPO와 SAC는 TD로 배운 크리틱이 정책의 갱신 방향을 알려 준다. 어느 줄에 서든 반환값·가치·벨만 방정식·탐험이라는 같은 부품을 다르게 조립한 것이다.

다음 걸음

이 글에서 세운 것을 한 줄로 묶으면 이렇다. 에이전트는 정책으로 행동을 고르고, 환경은 상태와 보상으로 답하며, 가치는 그 정책이 앞으로 받을 반환값의 기댓값이고, 벨만 방정식이 그 가치를 이웃 칸들 사이의 관계로 바꿔 계산할 수 있게 만든다. 모델을 알면 동적 계획법으로 풀고, 모르면 MC나 TD로 경험에서 추정한다.

비어 있는 자리는 하나다. 여기서 TD는 정해진 정책을 평가하는 데까지만 썼다. 모델 없이 경험만으로 최적 정책까지 찾아가려면 $V$ 가 아니라 $Q$ 를 TD로 배워야 한다. 다음 글은 그 방법인 Q-러닝을 FrozenLake의 예순네 칸 표에서 따라가고, 상태가 너무 많아 표가 무너지는 자리를 신경망으로 넘어서는 DQN까지 경험 재생과 타겟 네트워크를 곁들여 다룬다.

---

읽어주셔서 감사합니다. 😊