[강화학습] 정책이터레이션과 가치이터레이션의 차이점

강화학습에서 정책 이터레이션과 가치 이터레이션의 차이점

강화학습은 에이전트가 환경과 상호작용하며 최적의 행동을 배우는 과정입니다. 이 과정에서 "정책"과 "가치 함수"라는 두 가지 중요한 개념이 등장합니다. 정책 이터레이션(Policy Iteration)과 가치 이터레이션(Value Iteration)은 이 두 개념을 활용하여 최적 정책을 찾기 위한 알고리즘입니다. 두 알고리즘은 비슷한 목적을 가지고 있지만, 그 방식에는 차이가 있습니다.

1. 정책 이터레이션(Policy Iteration)

정책 이터레이션은 "정책 평가"와 "정책 개선"을 번갈아 가며 반복하여 최적의 정책을 찾는 방법입니다. 정책은 에이전트가 각 상태에서 취할 행동을 정의한 규칙입니다. 정책 이터레이션은 다음 두 단계로 구성됩니다:

1. 정책 평가(Policy Evaluation): 주어진 정책에 대해 각 상태에서의 가치를 계산합니다. 이때, 상태 가치 함수 \(V^\pi(s)\)를 구하게 됩니다.
2. 정책 개선(Policy Improvement): 현재 가치 함수에 기반하여, 각 상태에서 최적의 행동을 선택하고, 정책을 개선합니다.

정책 이터레이션은 이 두 단계를 반복하면서 점점 더 나은 정책을 찾게 됩니다. 이 방식은 비교적 직관적이고, 작은 상태 공간에서는 빠르게 수렴할 수 있습니다.

2. 가치 이터레이션(Value Iteration)

가치 이터레이션은 가치 함수 \(V(s)\)를 직접 갱신하여 최적 정책을 찾는 알고리즘입니다. 정책 이터레이션과 달리, 가치 이터레이션은 정책을 바로 개선하는 대신, 각 상태에서의 가치를 반복적으로 업데이트합니다. 이 알고리즘의 주요 단계는 다음과 같습니다:

1. 가치 함수 갱신(Value Update): 각 상태에 대해 벨만 기대 방정식을 사용하여 가치 함수를 갱신합니다. 이때, 정책은 암묵적으로 최적화됩니다.

가치 이터레이션은 정책을 명시적으로 개선하지 않고, 대신 가치 함수가 충분히 수렴할 때까지 반복합니다. 가치 함수가 수렴되면, 그때서야 최적 정책을 도출할 수 있습니다.

3. 정책 이터레이션과 가치 이터레이션의 차이점

정책 이터레이션과 가치 이터레이션의 주요 차이점은 정책 개선이 언제 이루어지는지에 있습니다:

구분	정책 이터레이션	가치 이터레이션
정책 평가	정책 평가 단계에서 가치 함수 \(V^\pi(s)\)를 구합니다.	정책을 직접 평가하지 않고, 가치 함수만 업데이트합니다.
정책 개선	정책 개선 단계에서 각 상태에서의 최적 행동을 선택하여 정책을 개선합니다.	가치 함수가 수렴할 때까지 반복하고, 그 후에 최적 정책을 도출합니다.
수렴 속도	작은 상태 공간에서는 빠르게 수렴하지만, 큰 상태 공간에서는 느릴 수 있습니다.	상태 공간이 크더라도, 점진적으로 수렴하지만 더 느릴 수 있습니다.
장점	정책과 가치 함수가 분리되어 있어 이해하기 쉬운 구조입니다.	가치 함수만 업데이트하므로 메모리 사용이 상대적으로 적습니다.

4. 요약

정책 이터레이션과 가치 이터레이션은 최적 정책을 찾기 위한 두 가지 방법입니다. 정책 이터레이션은 정책을 명시적으로 평가하고 개선하는 반면, 가치 이터레이션은 가치 함수만을 갱신하며 정책을 암묵적으로 개선합니다. 둘 다 강력한 알고리즘이지만, 상태 공간이 크거나 복잡할 때는 다른 방식이 더 효율적일 수 있습니다.

[강화학습] 가치이터레이션

강화학습에서 가치 이터레이션(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. 가치 이터레이션 알고리즘

가치 이터레이션 알고리즘은 다음과 같은 순서로 진행됩니다:

1. Step 1: 가치 함수 \( V(s) \)를 초기화합니다. 일반적으로 모든 상태의 초기 가치는 0으로 설정합니다.
2. Step 2: 벨만 최적 방정식을 사용하여 각 상태의 가치를 반복적으로 업데이트합니다.
3. 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. 결론

가치 이터레이션은 강화학습에서 중요한 알고리즘으로, 가치 함수를 반복적으로 갱신하여 최적의 정책을 찾는 방법입니다. 벨만 최적 방정식을 기반으로 하며, 각 상태에서 최적 행동을 선택하는 데 유용합니다. 상태 공간이 작은 경우 효율적으로 동작하지만, 상태 공간이 커지면 계산 자원을 많이 소모할 수 있다는 단점이 있습니다.