강화학습에서 정책 이터레이션(Policy Iteration) 설명
강화학습에서 정책 이터레이션(Policy Iteration)
강화학습에서 정책 이터레이션(Policy Iteration)은 최적의 정책을 구하기 위한 알고리즘입니다. 이 알고리즘은 주어진 환경에서 최적 정책을 찾아내기 위해, 주기적으로 두 가지 주요 단계를 반복합니다. 첫 번째는 정책 평가(Policy Evaluation) 단계이고, 두 번째는 정책 개선(Policy Improvement) 단계입니다. 정책 이터레이션은 가치 반복(Value Iteration)보다 더 빠르게 수렴할 수 있는 경우가 많습니다.
1. 정책 이터레이션의 개념
정책 이터레이션은 두 가지 중요한 단계를 반복적으로 실행합니다. 그 과정은 다음과 같습니다:
- 정책 평가(Policy Evaluation): 주어진 정책에 대한 가치 함수를 계산합니다. 이 단계에서는 현재 정책이 각 상태에서 얻을 수 있는 예상 보상값을 계산합니다.
- 정책 개선(Policy Improvement): 가치 함수가 주어졌을 때, 각 상태에서 최적의 행동을 선택하여 정책을 개선합니다.
2. 정책 이터레이션 알고리즘
정책 이터레이션 알고리즘은 다음과 같은 단계로 진행됩니다:
- Step 1: 초기 정책 \( \pi_0 \)를 설정합니다.
- Step 2: 주어진 정책 \( \pi \)에 대해 가치 함수 \( V^{\pi} \)를 계산합니다. (정책 평가 단계)
- Step 3: 가치 함수 \( V^{\pi} \)에 기반하여 각 상태에서 최적 행동을 선택하고 정책을 개선합니다. (정책 개선 단계)
- Step 4: 정책이 더 이상 변경되지 않을 때까지, 정책 평가와 정책 개선을 반복합니다.
3. 정책 평가 (Policy Evaluation)
정책 평가 단계에서는 주어진 정책에 대한 각 상태의 가치를 계산합니다. 이때 벨만 기대 방정식(Bellman Expectation Equation)을 사용하여, 각 상태에서 얻을 수 있는 보상의 총합을 계산합니다. 벨만 기대 방정식은 다음과 같습니다:
$$ V^{\pi}(s) = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^{\pi}(s') \right] $$
여기서:
- \( V^{\pi}(s) \): 상태 \( s \)에서의 정책 \( \pi \)에 대한 가치 함수
- \( \pi(a|s) \): 상태 \( s \)에서 행동 \( a \)를 선택할 확률
- \( P(s'|s,a) \): 상태 \( s \)에서 행동 \( a \)를 취했을 때 상태 \( s' \)로 전이될 확률
- \( R(s,a,s') \): 상태 \( s \)에서 행동 \( a \)를 취하고 상태 \( s' \)로 전이될 때 얻는 보상
- \( \gamma \): 할인율 (0과 1 사이의 값)
4. 정책 개선 (Policy Improvement)
정책 개선 단계에서는 정책 평가에서 계산된 가치 함수 \( V^{\pi} \)를 사용하여 각 상태에서 최적의 행동을 선택합니다. 즉, 주어진 가치 함수에 대해 각 상태에서 최적 행동을 찾고, 그 행동을 새로운 정책에 반영합니다. 이때 정책 개선은 다음과 같은 방식으로 이루어집니다:
$$ \pi'(s) = \arg\max_{a} \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^{\pi}(s') \right] $$
여기서 \( \pi'(s) \)는 상태 \( s \)에서의 최적 행동입니다. 정책 개선은 가치 함수가 수렴한 후, 최적의 정책을 도출하는 과정입니다.
5. 정책 이터레이션 알고리즘의 수학적 표현
정책 이터레이션의 알고리즘을 수학적으로 표현하면 다음과 같습니다:
# 정책 이터레이션 알고리즘 (Python)
import numpy as np
# 상태와 행동 정의
states = [0, 1, 2, 3]
actions = [0, 1]
P = {...} # 상태 전이 확률
R = {...} # 보상 함수
gamma = 0.9 # 할인율
theta = 1e-6 # 수렴 기준
# 초기 정책과 가치 함수
policy = np.zeros(len(states), dtype=int)
V = np.zeros(len(states))
def policy_evaluation(policy, V, P, R, gamma, theta):
while True:
delta = 0
for s in range(len(states)):
v = V[s]
V[s] = sum(P[s, a] * (R[s, a] + gamma * V[s_next]) for a in actions)
delta = max(delta, abs(v - V[s]))
if delta < theta:
break
return V
def policy_improvement(V, P, R, gamma):
policy_stable = True
for s in range(len(states)):
old_action = policy[s]
policy[s] = np.argmax([sum(P[s, a] * (R[s, a] + gamma * V[s_next]) for s_next in range(len(states))) for a in actions])
if old_action != policy[s]:
policy_stable = False
return policy_stable
def policy_iteration(P, R, gamma, theta):
policy = np.zeros(len(states), dtype=int)
V = np.zeros(len(states))
while True:
V = policy_evaluation(policy, V, P, R, gamma, theta)
policy_stable = policy_improvement(V, P, R, gamma)
if policy_stable:
break
return policy, V
policy, V = policy_iteration(P, R, gamma, theta)
print("최적 정책:", policy)
print("최적 가치 함수:", V)
6. 정책 이터레이션의 장점과 단점
장점
- 정책 평가와 개선이 분리되어 있어, 큰 상태 공간에서도 안정적으로 작동할 수 있습니다.
- 정책 이터레이션은 빠르게 최적 정책에 수렴할 수 있습니다.
단점
- 정책 평가 단계에서 수학적 계산이 많이 필요하여, 계산 비용이 높을 수 있습니다.
- 상태 공간이 매우 클 경우 메모리와 계산 자원이 많이 소모될 수 있습니다.
7. 결론
정책 이터레이션은 강화학습에서 최적 정책을 찾기 위한 중요한 알고리즘입니다. 정책 평가와 정책 개선의 두 단계를 반복함으로써, 에이전트는 점차 최적 정책을 학습할 수 있습니다. 가치 반복보다 더 효율적인 경우도 있지만, 상태 공간이 커지면 계산 비용이 높아질 수 있다는 단점이 있습니다.