강화학습에서 가치 이터레이션(Value Iteration) 설명
강화학습에서 가치 이터레이션(Value Iteration)
가치 이터레이션(Value Iteration)은 강화학습에서 사용되는 중요한 알고리즘 중 하나로, 최적 정책을 찾기 위한 방법입니다. 이 방법은 동적 프로그래밍의 한 종류로, 벨만 최적 방정식(Bellman Optimality Equation)을 반복적으로 적용하여 최적 가치 함수를 계산합니다. 이를 통해 최적 정책을 도출할 수 있습니다.
1. 가치 이터레이션의 개념
가치 이터레이션의 핵심은 가치 함수를 업데이트하면서, 각 상태에서 최적 행동을 선택할 수 있도록 만드는 것입니다. 강화학습의 목표는 에이전트가 주어진 환경에서 최적의 행동을 취하도록 하는 것입니다. 이를 위해서는 각 상태에 대해 예상되는 보상을 최대화하는 정책을 찾아야 합니다.
(1) 벨만 최적 방정식
가치 이터레이션은 벨만 최적 방정식을 반복적으로 적용하여 최적 가치 함수 \( V^*(s) \)를 계산합니다. 벨만 최적 방정식은 다음과 같습니다:
$$ V^*(s) = \max_{a} \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^*(s') \right] $$
여기서:
- \( V^*(s) \) : 상태 \( s \)에서의 최적 가치 함수
- \( \gamma \) : 할인율 (0과 1 사이의 값)
- \( P(s'|s,a) \) : 상태 \( s \)에서 행동 \( a \)를 취했을 때 다음 상태 \( s' \)로 전이될 확률
- \( R(s,a,s') \) : 상태 \( s \)에서 행동 \( a \)를 취하고 상태 \( s' \)로 전이될 때 얻는 보상
(2) 가치 함수 업데이트
벨만 최적 방정식을 사용하여 각 상태에 대한 가치 함수를 반복적으로 업데이트합니다. 초기에는 가치 함수가 모두 0으로 설정되며, 그 후 각 상태에서의 가치를 점진적으로 개선합니다.
2. 가치 이터레이션 알고리즘
가치 이터레이션 알고리즘은 다음과 같은 순서로 진행됩니다:
- Step 1: 가치 함수 \( V(s) \)를 초기화합니다. 일반적으로 모든 상태의 초기 가치는 0으로 설정합니다.
- Step 2: 벨만 최적 방정식을 사용하여 각 상태의 가치를 반복적으로 업데이트합니다.
- Step 3: 가치 함수가 충분히 수렴하면, 각 상태에서 최적 행동을 선택하여 최적 정책을 도출합니다.
가치 이터레이션의 반복 과정
각 상태 \( s \)에 대해 벨만 최적 방정식을 적용하여 가치 함수를 업데이트합니다. 이 과정은 모든 상태의 가치 함수가 수렴할 때까지 반복됩니다. 수렴 기준은 각 상태의 가치 함수 변화가 미세할 때로 설정할 수 있습니다.
$$ \text{새로운 가치}(s) = \max_{a} \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V(s') \right] $$
3. 가치 이터레이션의 Python 코드 예시
# 가치 이터레이션 구현 (Python)
import numpy as np
states = [0, 1, 2, 3] # 상태 목록
actions = [0, 1] # 가능한 행동 목록
transition_prob = {
(0, 0): [(1.0, 0, -1)],
(0, 1): [(1.0, 1, 0)],
(1, 0): [(1.0, 0, -1)],
(1, 1): [(1.0, 2, 0)],
(2, 0): [(1.0, 1, -1)],
(2, 1): [(1.0, 3, 10)],
(3, 0): [(1.0, 3, 0)],
(3, 1): [(1.0, 3, 0)]
}
gamma = 0.9 # 할인율
theta = 1e-6 # 수렴 기준
V = np.zeros(len(states)) # 초기 가치 함수
# 가치 이터레이션 반복
while True:
delta = 0
for s in states:
v = V[s]
V[s] = max(sum(prob * (reward + gamma * V[s_next]) for prob, s_next, reward in transition_prob.get((s, a), [])) for a in actions)
delta = max(delta, abs(v - V[s]))
if delta < theta:
break
# 최적 정책 도출
policy = np.zeros(len(states), dtype=int)
for s in states:
policy[s] = np.argmax([sum(prob * (reward + gamma * V[s_next]) for prob, s_next, reward in transition_prob.get((s, a), [])) for a in actions])
print("최적 가치 함수:", V)
print("최적 정책:", policy)
4. 가치 이터레이션의 장점과 단점
장점
- 상태가 적당히 크면 수렴이 빠르고 안정적입니다.
- 정책 없이 직접적으로 최적 가치 함수를 계산할 수 있습니다.
단점
- 상태 공간이 커지면 수렴 속도가 느려질 수 있습니다.
- 큰 상태 공간을 처리하기 위해 메모리와 계산 자원이 많이 소모될 수 있습니다.
5. 결론
가치 이터레이션은 강화학습에서 중요한 알고리즘으로, 가치 함수를 반복적으로 갱신하여 최적의 정책을 찾는 방법입니다.
벨만 최적 방정식을 기반으로 하며, 각 상태에서 최적 행동을 선택하는 데 유용합니다. 상태 공간이 작은 경우 효율적으로 동작하지만, 상태 공간이 커지면 계산 자원을 많이 소모할 수 있다는 단점이 있습니다.