벨만 기대 방정식 - 술취한 사람 예제로 이해하는 가치 함수와 값 반복

현재 가치 = 지금 보상 + 미래 가치의 평균

벨만 기대 방정식(Bellman Expectation Equation) 은 어떤 상태의 가치(Value)가

현재 받을 보상 + (정책에 따라 도달할 다음 상태들의 가치의 기대값)

으로 표현된다는 관계식이다. 다음 상태가 확률적으로 결정되기 때문에, 그 확률을 고려한 평균(기대값) 을 쓰게 된다.

가장 단순화하면:

V(s) = R + γ V(s')

• (V(s)): 상태 (s)의 가치.
• (R): 지금 상태에서 받는 즉시 보상.
• (γ): 할인율(미래 보상을 얼마나 줄여서 볼지).
• (V(s')): 다음 상태 가치.

쉽게 말해 “현재 가치 = 지금 얻는 것 + 할인된 미래 가치의 평균” 이라는, 강화학습의 기본 원리를 수학으로 쓴 식이다.

---

1. 직관에서 식까지: 한 번, 두 번, 무한히 펼치기

1-1. 현재만 보기

지금 받는 보상만 고려하면:

V(s) ≈ R

하지만 강화학습에서는 미래에 받을 보상까지 고려해야 한다.

1-2. 한 번, 두 번 확장

한 단계 미래까지 보면:

V(s) = R + γ R'

두 단계까지 보면:

V(s) = R + γ R' + γ^2 R''

• 지금 보상 (R)
• 다음 보상 (R') 을 (γ) 로 할인해서 더함
• 그 다음 보상 (R'') 은 (γ^2) 로 더함

1-3. 무한 확장 → 벨만 기대 방정식

이 논리를 무한히 펼치면:

V(s) = R + γ R' + γ^2 R'' + γ^3 R''' + ⋯

이걸 한 줄 로 줄인 것이 벨만 기대 방정식이다.

V(s) = E[ R_t + γ R_{t+1} + γ^2 R_{t+2} + … | s_t = s ]

또는 재귀적으로:

V(s) = E[ R_t + γ V(s_{t+1}) | s_t = s ]

---

2. 현실 MDP에서의 벨만 기대 방정식

현실적인 MDP에서는:

• 행동이 여러 개 있고,
• 다음 상태가 확률적으로 여러 개 나오며,
• 정책에 따라 행동 확률이 달라지고,
• 보상도 확률적이다.

이때 상태 가치 함수 (V^π(s)) 는 대략 다음처럼 쓴다.

V^π(s) = ∑_a π(a|s) ∑_{s'} P(s'|s, a) [ R(s, a, s') + γ V^π(s') ]

한 줄로 쓰면 복잡해 보이지만, 실제로는 4단계 평균 을 차례대로 내는 구조다.

1. (∑_a π(a|s)):
   • 상태 (s) 에서 정책이 고르는 행동들의 평균(기대).
2. (∑_{s'} P(s'|s,a)):
   • 그 행동을 했을 때 나올 수 있는 다음 상태들의 평균(기대).
3. (R(s,a,s')):
   • 그 전이에서 받는 즉시 보상.
4. (γ V^π(s')):
   • 다음 상태 가치의 할인된 미래 부분.

기대값 표기로 쓰면 더 직관적이다.

V^π(s) = E_π[ R_t + γ V^π(s_{t+1}) | s_t = s ]

상태 (s) 에서 정책대로 움직일 때,
(지금 보상 + 할인된 다음 상태 가치) 의 평균이 (V^π(s)).

---

3. 술취한 사람 문제 (1차원)

3-1. 1차원 길과 상태 정의

술취한 사람 문제는 Markov 과정·강화학습에서 자주 나오는 예제다.

[Home] --- A --- B --- C --- [Bar]

• 맨 왼쪽 Home: 도착하면 좋은 상태 (종료).
• 맨 오른쪽 Bar: 도착하면 나쁜 상태 (종료).
• 중간 상태: A, B, C.
• 술취한 사람은 현재 위치에서 왼쪽/오른쪽으로 비틀거리며 이동(확률적).

상태 집합:

S = {Home, A, B, C, Bar}

3-2. 전이 확률과 보상

전이 확률 예시:

• A:
  • 50% → Home
  • 50% → B
• B:
  • 50% → A
  • 50% → C
• C:
  • 50% → B
  • 50% → Bar

보상 설정:

• Home에 도착: +1 (좋은 결과)
• Bar에 도착: -1 (나쁜 결과)
• 그 외 중간 이동: 0 (보상 없음)

할인율은 (γ = 1) 로 두어, 미래 보상을 그대로 다 반영한다고 하자.

3-3. 종료 상태 가치

종료 상태는 가치가 고정이다.

V(Home) = 1
V(Bar) = -1

중간 상태 A, B, C의 가치는 집/술집으로 갈 확률 에 따라 결정된다.

3-4. 벨만 기대 방정식으로 A, B, C 값 구하기

A에서는:

• 50% → Home(가치 1)
• 50% → B(가치 V(B))

V(A) = 0 + 1.0 × E[V(next) | A]
      = 0.5 × V(Home) + 0.5 × V(B)
      = 0.5 × 1 + 0.5 × V(B)

B에서는:

• 50% → A
• 50% → C

V(B) = 0.5 × V(A) + 0.5 × V(C)

C에서는:

• 50% → B
• 50% → Bar(-1)

V(C) = 0.5 × V(B) + 0.5 × V(Bar)
      = 0.5 × V(B) + 0.5 × (-1)

이 연립방정식을 풀면:

• (V(A) = 0.5)
• (V(B) = 0)
• (V(C) = -0.5)

Home(+1) --- A(+0.5) --- B(0) --- C(-0.5) --- Bar(-1)

• A는 집에 더 가까워 비교적 좋은 상태.
• B는 집·술집 사이 중립적인 상태.
• C는 술집에 더 가까워 나쁜 상태.

즉, 상태 가치 함수는 위치의 좋고 나쁨을 점수화한 것 이다.

---

4. 값 반복(Value Iteration)으로 가치 함수 구하기

위 연립방정식은 손으로 풀 수 있지만, 실제 강화학습에서는 상태가 매우 많으므로 반복 업데이트 로 근사한다.

초기값을 대충 두고,

V = {
    "Home": 1.0,
    "A": 0.0,
    "B": 0.0,
    "C": 0.0,
    "Bar": -1.0,
}

iterations = 10

for i in range(1, iterations + 1):
    u_V = V.copy()
    u_V["A"] = 0.5 * V["Home"] + 0.5 * V["B"]
    u_V["B"] = 0.5 * V["A"] + 0.5 * V["C"]
    u_V["C"] = 0.5 * V["B"] + 0.5 * V["Bar"]
    V = u_V
    print(f"{i:d}회 반복 -> A={V['A']:.4f}, B={V['B']:.4f}, C={V['C']:.4f}")

for state, value in V.items():
    print(f"{state}: {value:.4f}")

• A, B, C를 처음엔 0으로 두고,
• 벨만 기대 방정식대로 계속 업데이트하면,
• 점점 +0.5, 0, -0.5 근처로 수렴한다.

4-1. 시뮬레이션으로 근사 값 확인하기

랜덤 시뮬레이션으로도 (V(A), V(B), V(C)) 를 추정할 수 있다.

import random

def arriveA():
    choice = random.choice(['Home', 'B'])
    if choice == 'Home':
        return 1
    else:
        return arriveB()

def arriveB():
    choice = random.choice(['A', 'C'])
    if choice == 'A':
        return arriveA()
    else:
        return arriveC()

def arriveC():
    choice = random.choice(['B', 'Bar'])
    if choice == 'B':
        return arriveB()
    else:
        return -1

sum_result = 0
for i in range(10000):
    sum_result += arriveA()

print(sum_result / 10000)

또는 상태를 일반화한 형태로 작성할 수도 있다.

import random

def run(start_state):
    while True:
        if start_state == "Home":
            return 1
        elif start_state == "Bar":
            return -1
        move = random.choice(['left', 'right'])
        if start_state == "A":
            start_state = "Home" if move == "left" else "B"
        elif start_state == "B":
            start_state = "A" if move == "left" else "C"
        elif start_state == "C":
            start_state = "B" if move == "left" else "Bar"


def estimate_value(start_state, n=10000):
    total = 0
    for i in range(n):
        total += run(start_state)
    return total / n

print(f"A ≈ {estimate_value('A'):.4f}")
print(f"B ≈ {estimate_value('B'):.4f}")
print(f"C ≈ {estimate_value('C'):.4f}")

• 충분히 많이 반복하면, 이 값들도 0.5, 0, -0.5 근처로 수렴한다.
• 연립방정식으로 구한 값과, 시뮬레이션으로 근사한 값이 일치하는지 확인할 수 있다.

---

5. 5×5 술취한 사람 문제: 2D 격자에서의 값 반복

1차원 예제를 2D 격자(5×5)로 확장해 보자.

+-----+-----+-----+-----+-----+
| H   | A   | B   | C   | BAR |
+-----+-----+-----+-----+-----+
| D   | E   | F   | G   | I   |
+-----+-----+-----+-----+-----+
| J   | K   | L   | M   | N   |
+-----+-----+-----+-----+-----+
| O   | P   | Q   | R   | S   |
+-----+-----+-----+-----+-----+
| T   | U   | V   | W   | X   |
+-----+-----+-----+-----+-----+

5-1. 상태 의미와 보상

• (0, 0): Home(H) – 보상 +1, Terminal.
• (0, 4): Bar – 보상 -1, Terminal.
• 나머지: 일반 상태, 보상 0.

이동 규칙:

• 위/아래/왼쪽/오른쪽 중 하나로 이동하려고 한다.
• 격자 밖으로 나가면 제자리 유지.
• 네 방향을 동일 확률(0.25) 로 시도한다고 가정.

할인율은 (γ = 1) 이라고 두자.

5-2. 간단한 평균 업데이트 버전

아래 코드는 각 칸에서 주변 4칸의 가치 평균 으로 값을 업데이트한다.

V = [[0.0] * 5 for _ in range(5)]
V[0][0] = 1.0
V[0][4] = -1.0

for iteration in range(1000):
    new_V = [row[:] for row in V]

    for r in range(5):
        for c in range(5):
            if (r == 0 and c == 0) or (r == 0 and c == 4):
                continue

            sum_v = 0
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < 5 and 0 <= nc < 5:
                    sum_v += V[nr][nc]
                else:
                    sum_v += V[r][c]

            # 주변 4칸(또는 벽이면 자기자신)의 평균값
            new_V[r][c] = sum_v / 4

    diff = 0
    for r in range(5):
        for c in range(5):
            diff = max(diff, abs(new_V[r][c] - V[r][c]))

    V = new_V
    if diff < 0.0001:
        break

for row in V:
    print([round(val, 3) for val in row])

여기서 한 줄 주석:

# 벨만 방정식: 주변 4칸의 평균값 업데이트

이 부분이 바로,

V(s) = E[ R + γ V(s') ]

을 구현한 것이다.

• 각 방향으로 갈 확률이 0.25씩이므로,
• 보상은 대부분 0, Home/Bar 로 가면 +1/-1,
• 그 다음 상태 가치 (V(s')) 를 평균 내는 꼴.

5-3. 조금 더 명시적인 값 반복(value iteration) 코드

아래는 상태/보상/전이를 더 명확히 나눠 쓴 버전이다.

SIZE = 5
GAMMA = 1.0
ITERATIONS = 30

HOME = (0, 0)
BAR = (0, 4)

DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_terminal(state):
    return state == HOME or state == BAR


def move(state, direction):
    r, c = state
    dr, dc = direction
    nr, nc = r + dr, c + dc
    if nr < 0 or nr >= SIZE or nc < 0 or nc >= SIZE:
        return state
    return (nr, nc)


def get_reward(next_state):
    if next_state == HOME:
        return 1.0
    elif next_state == BAR:
        return -1.0
    else:
        return 0.0


def print_grid(values, title=""):
    if title:
        print(f"\n{title}")
    for r in range(SIZE):
        row = []
        for c in range(SIZE):
            state = (r, c)
            if state == HOME:
                row.append(" Home ")
            elif state == BAR:
                row.append(" Bar  ")
            else:
                row.append(f"{values[r][c]:6.2f}")
        print(" | ".join(row))
    print()


def value_iteration():
    V = [[0.0 for _ in range(SIZE)] for _ in range(SIZE)]
    V[HOME[0]][HOME[1]] = 1.0
    V[BAR[0]][BAR[1]] = -1.0

    print_grid(V, title="초기 상태 가치")

    for iteration in range(1, ITERATIONS + 1):
        new_V = [[V[r][c] for c in range(SIZE)] for r in range(SIZE)]

        for r in range(SIZE):
            for c in range(SIZE):
                state = (r, c)
                if is_terminal(state):
                    continue

                value = 0.0
                for direction in DIRECTIONS:
                    next_state = move(state, direction)
                    reward = get_reward(next_state)
                    nr, nc = next_state
                    # 각 방향으로 갈 확률이 0.25라서 1/4씩 평균
                    value += 0.25 * (reward + GAMMA * V[nr][nc])

                new_V[r][c] = value

        V = new_V

        if iteration in [1, 2, 5, 10, 20, 30]:
            print_grid(V, title=f"{iteration}회 반복 후 상태 가치")

    return V


if __name__ == "__main__":
    final_V = value_iteration()
    print_grid(final_V, title="최종 상태 가치")

여기서 핵심 한 줄은:

value += 0.25 * (reward + GAMMA * V[nr][nc])

즉,

V(s) ← E[ R + γ V(s') ]

을 네 방향에 대해 평균내어 업데이트하는, 벨만 기대 방정식을 이용한 값 반복(value iteration) 이다.

---

6. 강화학습 팀 프로젝트 아이디어

강화학습 수업에서 배운 개념을 실제로 적용해보기 위해, 팀 단위로 간단한 게임을 만들고 그 게임을 강화학습 에이전트가 학습하도록 하는 토이 프로젝트를 해 볼 수 있다.

예시 게임 아이디어:

• Grid 기반 미로 탈출 게임
• 장애물 피하기 게임
• 간단한 자동차 레이싱 게임

프로젝트 흐름:

1. 환경 설계: 상태·행동·보상 구조를 MDP로 정의.
2. 벨만 방정식 관점에서 가치 해석: 상태가 왜 좋은지/나쁜지 수치로 이해.
3. 값 반복 / 정책 반복 / Q-learning 등으로 에이전트 학습.
4. 학습 전·후 에이전트 행동 비교, 리워드/가치 함수 시각화.

벨만 기대 방정식과 술취한 사람 예제를 이해해 두면, 이런 프로젝트에서 상태 가치와 정책이 어떻게 연결되는지 를 훨씬 직관적으로 설명할 수 있다.

---

마치며

• 벨만 기대 방정식은 “현재 가치 = 현재 보상 + 할인된 미래 가치의 기대값” 이라는 단순한 문장을 수학으로 옮긴 것이다.
• 1차원·2차원 술취한 사람 예제는 이 방정식이 실제로 위치의 좋고 나쁨(집에 가까운지, 술집에 가까운지) 을 어떻게 수치로 표현하는지 잘 보여 준다.
• 값 반복(value iteration)과 시뮬레이션은 서로를 검증해 주는 도구로, 이 원리를 이해하면 이후 TD Learning, Monte Carlo, Q-learning 같은 강화학습 알고리즘을 받아들이기 훨씬 쉬워진다.