벨만 기대 방정식 (Bellman Expectation Equation)

1. 벨만 기대 방정식이란?

벨만 기대 방정식(Bellman Expectation Equation)은 어떤 상태의 가치(Value)가
“지금 받는 보상 + (미래 상태들의 가치의 기대값)”으로 표현된다는 관계식입니다.

한 줄로 말하면:

현재 가치 = 즉시 보상 + 할인된 미래 가치의 평균

강화학습에서 상태 가치 함수 (V^\pi(s))는 “정책 (\pi)를 따를 때, 상태 s에서 시작했을 때의 기대 Return”이었죠.
이걸 재귀적으로 쓰면 다음과 같이 됩니다.

• 단순화된 형태(직관용):

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

여기서

• (R): 지금 받는 보상
• (γ): 할인율 (0~1)
• (V(s′)): 다음 상태의 가치

실제 MDP에서는 행동도 여러 개, 다음 상태도 여러 개, 전이도 확률적이라서
모든 경우의 기대값(평균)을 취한 식으로 확장됩니다.

---

2. “현재만 보기”에서 “미래까지 보기”로

2.1 지금 보상만 보면

가장 단순하게, “지금 받는 보상만 본다”고 하면:

V(s) ≈ R

이 상태가 좋은지 나쁜지를 즉시 보상만 보고 판단하는 느낌입니다.

2.2 한 번, 두 번 확장

한 스텝만 더 보면:

V(s) = R + γ R′

두 스텝까지 보면:

V(s) = R + γ R′ + γ² R′′

• 지금 보상 (R)
• 다음 스텝 보상 (R′), 그다음 보상 (R′′)를 할인해서 더해 준 형태입니다.

2.3 무한히 확장 → 벨만 기대 방정식

이걸 무한히 늘리면:

V(s) = R + γ R′ + γ² R′′ + γ³ R′′′ + …

이 아이디어를 기댓값(확률 평균)으로 깔끔하게 정리한 것이
강화학습 교과서에 나오는 벨만 기대 방정식입니다.

---

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

현실 MDP에서는:

• 행동이 여러 개 있고
• 같은 행동을 해도 다음 상태가 확률적으로 여러 개 나오고
• 정책에 따라 행동 선택 확률이 달라지고
• 보상도 전이마다 다를 수 있습니다.

이걸 모두 포함하면, 정책 (\pi) 하에서의 상태 가치 (V^\pi(s))는:

현재=(행동확률평균)(전이확률평균)(보상+감마×다음가치)

조금 풀어서 읽으면:

1. Σₐ π(a|s)
   → 상태 s에서 정책이 선택할 행동들의 “평균” (정책의 기대)
2. Σₛ′ P(s′|s,a)
   → 그 행동을 했을 때 나올 수 있는 다음 상태들의 “평균”
3. R(s,a,s′)
   → 그 전이에서 받는 즉시 보상
4. γ Vπ(s′)
   → 그 다음 상태에서의 미래 가치(할인된 부분)

기댓값 기호 ( ∑ )로 쓰면 더 직관적입니다.

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

---

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

강화학습/마르코프 과정에서 자주 나오는 고전 예제입니다.

4.1 환경 설정

[집] --- A --- B --- C --- [술집]

• 맨 왼쪽 Home: 도착하면 좋은 상태 (+1)
• 맨 오른쪽 Bar: 도착하면 나쁜 상태 (−1)
• 중간 상태: A, B, C
• 술취한 사람은 매 스텝마다 왼쪽/오른쪽으로 한 칸 움직이는데,
  이 방향이 50:50 확률로 랜덤입니다.

상태 집합:

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

4.2 전이 확률

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

4.3 보상 설정

• Home 도착: +1
• Bar 도착: −1
• 나머지 이동: 0

종료 상태 가치:

V(Home) = 1
V(Bar)  = −1

4.4 A, B, C에 대한 벨만 기대 방정식

할인율은 (\gamma = 1) (미래를 그대로 다 본다고 가정)입니다.

• A에서:
  • 50%로 Home, 50%로 B
• B에서:
  • 50%로 A, 50%로 C
• C에서:
  • 50%로 B, 50%로 Bar

이 구조를 식으로 쓰면, 각 상태는 “양옆 상태들의 평균값” 형태로 정리됩니다.
결과적으로:

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

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

• A: 집 쪽에 더 가까워서 긍정적인 상태
• C: 술집에 더 가깝기 때문에 부정적인 상태
• B: 딱 중간이라 0 근처

즉, “그 위치에서 시작했을 때, 앞으로 좋은 결과를 얼마나 기대할 수 있는가”를 점수로 표현한 것이 바로 상태 가치입니다.

4.5 값 반복(Value Iteration)으로 풀기

A, B, C의 초기값을 0으로 두고, 벨만 기대 방정식을 반복해서 업데이트하면
위의 값들로 수렴합니다.

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

for i in range(1, 11):
    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}회 반복 -> A={V['A']:.4f}, B={V['B']:.4f}, C={V['C']:.4f}")

반복이 진행되면:

• A → 0.5
• B → 0.0
• C → −0.5

로 안정적으로 수렴합니다.

4.6 몬테카를로 시뮬레이션으로 검증

같은 환경을 직접 시뮬레이션해서 평균 보상을 구해 보면,
벨만 방정식으로 계산된 값과 거의 같아집니다.

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 _ 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}")

실행하면 예를 들어:

A ≈ 0.50xx
B ≈ 0.00xx
C ≈ -0.50xx

처럼, 이론값(0.5, 0, −0.5)에 매우 가깝게 나옵니다.

즉, 벨만 기대 방정식으로 계산한 값 = 실제 에피소드를 많이 돌렸을 때의 평균 Return
이라는 걸 실험으로 확인할 수 있습니다.

---

5. 5×5 술취한 사람 문제 (2D Grid)

이번에는 같은 아이디어를 2차원 격자로 확장해 봅니다.

+-----+-----+-----+-----+-----+
| 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 상태와 보상

• H (0,0): Home (집) → +1
• BAR (0,4): 술집 → −1
• 나머지 칸: 일반 상태 → 0
• Home, Bar는 종료 상태(terminal)

5.2 이동 규칙

술취한 사람은 매 스텝마다 4방향 중 하나를 시도합니다.

• 위 / 아래 / 왼쪽 / 오른쪽 (각각 25% 확률)
• 격자 밖으로 나가려고 하면 → 제자리

할인율은 (\gamma = 1)로 두고, 각 칸의 가치 (V(s))를 구합니다.

5.3 값 반복으로 상태 가치 구하기

노트북에서는 다음과 같이 구현합니다.

• V를 5×5 2D 배열로 두고
• HOME과 BAR만 각각 1, −1로 고정
• 나머지는 0에서 시작해서, 벨만 기대 방정식에 따라 반복 업데이트

핵심 업데이트 부분은:

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
            value += 0.25 * (reward + GAMMA * V[nr][nc])

        new_V[r][c] = value

• 네 방향으로 갈 수 있는 모든 경우에 대해
  ((보상 + γ × 다음 상태 가치))를 평균 냅니다.
• 그 평균값이 곧 현재 칸의 새로운 가치 (V(s)).

반복 횟수를 늘리면, Home 주변은 양수, Bar 주변은 음수,
그리고 가운데에 가까울수록 0 근처 값으로 수렴하는 패턴이 나옵니다.

노트북 출력 예시(요약):

• 1회 반복 후:

HOME |  0.50|  0.00| -0.50| BAR
...

• 30회 반복 후:

HOME |  0.85|  0.00| -0.85| BAR
 1.04|  0.56|  0.00| -0.56| -1.04
 0.57|  0.33|  0.00| -0.33| -0.57
 0.33|  0.20|  0.00| -0.20| -0.33
 0.24|  0.14|  0.00| -0.14| -0.24

• Home 쪽으로 갈수록 점점 양수에 가까워지고
• Bar 쪽으로 갈수록 점점 음수에 가까워지는 형상이 나옵니다.

결국, 벨만 기대 방정식 + 값 반복만으로
“이 격자에서 어느 위치가 더 유리한지/위험한지”를
수치로 그려낼 수 있는 셈입니다.

[ 오늘의 정리 ]

• 벨만 기대 방정식은 강화학습에서
  “현재 가치 = 즉시 보상 + 할인된 미래 가치의 기대값”
  이라는 기본 원리를 수학적으로 표현한 식입니다.
• 1차원/2차원 술취한 사람 예제처럼,
  상태 전이와 보상이 정의된 마르코프 과정에 이 식을 적용하면
  각 위치(상태)가 얼마나 좋은지/나쁜지를 점수로 계산할 수 있습니다.
• 값 반복(Value Iteration)으로 방정식을 반복 적용하면
  이론적으로 정의된 (V^\pi(s))에 가까운 값을 실제로 구할 수 있고,
  몬테카를로 시뮬레이션으로 그 값이 맞는지 검증할 수도 있습니다.

다음 단계로는, 기대 방정식을 최대값 형태(벨만 최적 방정식)로 바꿔서 최적 정책을 찾는 방법(가치 반복, Q-learning 등)으로 이어질 수 있습니다.