벨만 방정식

미래의 보상까지 고려한 최적 의사결정을 수학적으로 표현한 식

 

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

                    (a)

 

즉, “지금 어떤 행동을 하면, 장기적으로 얼마나 좋은 결과를 얻을까?”를 계산하는 식입니다.

예를 들어,

 

1. 당신이 게임을 한다고 합시다.

2. 지금 바로 점수를 얻을 수도 있고,

3. 조금 손해를 보더라도 다음 턴에 더 큰 점수를 얻을 수도 있죠.

벨만 방정식은 “현재 보상 + 미래 기대 보상”을 합쳐서 최적의 선택을 찾는 원리입니다. 

 

 

이 식을 해석하

• V(s): 현재 상태 s의 가치(value)
• R(s): 지금 상태에서 얻는 즉시 보상(reward)
• γ: 미래 보상에 대한 할인율 (0~1 사이 값)
• V(s′): 다음 상태의 가치
• max(⁡a)​: 가능한 행동 중 가장 좋은 행동

현재 가치 = 지금 보상 + (미래 가치의 최댓값 × 할인율)

 

예를 들어 “시험 공부” 상황을 생각해 봅시다.

 

- 지금 놀면 → 지금은 행복(보상 ↑), 나중에 성적 ↓

- 지금 공부하면 → 지금은 힘듦(보상 ↓), 나중에 성적 ↑

 

벨만 방정식은 이 두 가지 선택의
“즉시 보상 + 미래 보상의 기대값”을 비교해서
장기적으로 가장 큰 총보상을 주는 선택(정책, policy)을 찾는 방법입니다. 

 

강화학습에서는 이 방정식을 이용해 각 상태(state)마다 “가치(Value)”를 업데이트하며 최적 정책(Optimal Policy)을 학습합니다.

 

벨만 방정식 → Q-learning 업데이트

 

- 상태–행동 가치 Q(s,a)를 학습할 때, 한 스텝에서의 업데이트

 

- 여기서 r은 즉시 보상, s′는 다음 상태, γ는 할인율, α는 학습률입니다.

- 대괄호 안은 “TD 오차(목표 − 현재)”이고, 그 목표가 바로 벨만 최적 방정식 형태입니다.

 

 

 

import random
from collections import defaultdict

# ----- 환경 정의 (4x4 GridWorld) -----
N = 4
START = (0, 0)
GOAL = (3, 3)
ACTIONS = [(0,1), (1,0), (0,-1), (-1,0)]  # R, D, L, U
ACTION_SYMBOLS = {0:"→", 1:"↓", 2:"←", 3:"↑"}

def step(state, action_idx):
    if state == GOAL:
        return state, 0, True  # 이미 도착
    (dx, dy) = ACTIONS[action_idx]
    x, y = state
    nx, ny = x + dx, y + dy
    # 격자 밖이면 이동 무효(제자리)
    if not (0 <= nx < N and 0 <= ny < N):
        nx, ny = x, y
    next_state = (nx, ny)
    # 보상
    if next_state == GOAL:
        reward, done = 10, True
    else:
        reward, done = -1, False
    return next_state, reward, done

# ----- 하이퍼파라미터 -----
alpha = 0.1     # 학습률
gamma = 0.90    # 할인율
epsilon = 0.10  # 탐험 확률(epsilon-greedy)
episodes = 2000

# ----- Q 테이블 -----
Q = defaultdict(lambda: [0.0]*len(ACTIONS))  # Q[(x,y)][a]

def epsilon_greedy_action(state, eps=epsilon):
    if random.random() < eps:
        return random.randrange(len(ACTIONS))
    # 다수 최대값 처리(무작위 타이브레이크)
    qs = Q[state]
    max_q = max(qs)
    candidates = [i for i, v in enumerate(qs) if v == max_q]
    return random.choice(candidates)

# ----- 학습 루프 -----
for ep in range(episodes):
    s = START
    done = False
    while not done:
        a = epsilon_greedy_action(s)
        s_next, r, done = step(s, a)
        # 벨만(최적) 목표: r + gamma * max_a' Q(s', a')
        target = r + (0 if done else gamma * max(Q[s_next]))
        # Q-learning 업데이트
        Q[s][a] += alpha * (target - Q[s][a])
        s = s_next

# ----- 학습된 정책 시각화 -----
policy = [["  " for _ in range(N)] for __ in range(N)]
for x in range(N):
    for y in range(N):
        s = (x, y)
        if s == GOAL:
            policy[x][y] = "G "
        else:
            best_a = max(range(len(ACTIONS)), key=lambda a: Q[s][a])
            policy[x][y] = ACTION_SYMBOLS[best_a] + " "

print("학습된 정책(→↓←↑):")
for row in policy:
    print("".join(row))

print("\n샘플 Q값(START):", Q[START])