동적계획법 알고리즘과 강화학습 동적계획법

학교 수업을 통해 강화학습을 공부하고 있다. 이번 글은 동적 계획법에 대해서 정리해 본 글이다. 일반적으로 프로그래밍을 하면서 알고 있던 동적계획법과 강화학습에서 사용되는 동적 계획법은 기본 개념은 같지만, 쓰임새는 약간 다르다고 할 수 있다.

먼저 프로그래밍 관점에서 동적계획법을 정리 해본다.

동적 계획법(Dynamic Programming, DP)

프로그래밍에서의 동적 계획법(DP)은 문제를 작은 부분 문제들로 나누어 반복하여 해결하는 알고리즘 기법이다. 국내에서는 보통 동적 계획법이라는 용어로 쓰고 있는데, Dynamic Programming 을 그대로 번역해서 동적 프로그래밍이라고 애기하시는 분들도 있는 것 같다. 사실 영어 그대로 번역하면 동적 프로그래밍이 맞는것 같기는 하다.

이 다이나믹 프로그래밍은 같은 문제를 여러 번 푸는 대신, 한 번 계산한 결과를 메모이제이션하거나 테이블에 기록해, 중복 계산을 피하는 방식으로 효율성을 높힌다. 동적계획법은 문제를 작은 부분으로 쪼개어서 해결한다는 점에서, 분할정복하고 비슷하지만 부분 문제들이 중복될 수 있느냐에 따른 차이점이 존재한다. 분할정복은 부분문제들이 서로 중복되지 않는 경우에 각각 독립적으로 해결하여 그 결과를 합치는 것이라면,

동적계획법에서는 최적 부분 구조(Optimal Substructure)를 가지는 중복된 하위 문제들(Overlapping Subproblems)이 존재하는 문제일 때 사용한다. 핵심은 중복되는 문제의 결과를 저장해놓고 재사용한다는 것이다.

특징

• 최적 부분 구조: 원래 문제의 최적 해법이 부분 문제들의 최적 해법을 포함해야 함.

• 중복 부분 문제: 같은 문제를 여러 번 풀지 않고, 한 번 계산한 결과를 저장해 재사용.

• 탑다운(memoization) 혹은 바텀업(tabulation) 방식으로 구현 가능.

예시

• 피보나치 수열: 피보나치 수열의 각 항을 구할 때 이전 항을 이용하여 다음 항을 계산.

• 최소 비용 경로 찾기: 그래프 또는 행렬에서 최단 경로나 최소 비용을 찾는 문제에서 DP를 사용.

동적계획법 사용하지 않은 예시

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

시간복잡도 : O(2^n)

공간복잡도 : O(n)

가장 많이 알려진 재귀를 통한 피보나치 코드이지만, 꽤 비효율적인 코드이다.

최대 스택의 깊이가 n개이므로 공간복잡도는 O(n) 이며,

시간 복잡도는 아래처럼

fibonacci(5) = fibonacci(4) + fibonacci(3) = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1)) = ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))

각 트리마다 두번의 재귀호출로 이루어져 O(2^n) 의 시간복잡도를 가진다.

동적계획법을 사용하면 중복으로 계산되는 부분을 방지하여 시간복잡도를 획기적으로 낮출수가 있다.

동적계획법 (Top-Down)

# 피보나치 수열: 탑다운 방식 (메모이제이션)
def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(10)) 

시간 복잡도 : O(n)

공간 복잡도 : O(n)

동적계획법 (Bottom-Up)

def fib(n):
    # DP 테이블 초기화 (0으로 초기화된 리스트 생성)
    dp = [0] * (n + 1)
    
    # 초기 값 설정
    if n >= 1:
        dp[1] = 1  # F(1) = 1
    
    # 바텀업 방식으로 피보나치 수열 계산
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    # n번째 피보나치 수를 반환
    return dp[n]

시간 복잡도 : O(n)

공간 복잡도 : O(n)

Bottom-Up방식은 재귀호출 대신에 반복문을 사용해 작은 문제부터 순차적으로 해결한다. 위 방식은 DP 테이블에 저장하는 Bottom-Up 방식의 동적계획법 알고리즘이다. 그런데 테이블을 사용함으로써 공간 복잡도는 똑같이 O(n)이다.

Bottom-Up 방식은 다음과 같이 공간 복잡도 최적화를 통해 메모리 사용량을 줄일 수 있다.

공간최적화 된 동적계획법(Bottom-Up)

def fibonacci_optimized(n):
    if n <= 1:
        return n
   
    prev2, prev1 = 0, 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

시간 복잡도 : O(n)

공간 복잡도 : O(1)

메모리도 가장 덜 사용하고 계산에 들어가는 비용도 가장 적은 코드이다.

강화학습에서 동적계획법

강화학습(Reinforcement Learning, RL)에서의 동적 계획법은, 마르코프 결정 과정(MDP)에서 정책(policy)을 최적화하기 위해 사용하는 기법이라고 할 수 있다. 여기서 동적 계획법은 주로 벨만 방정식(Bellman equation)을 사용하여 최적의 정책을 찾기 위한 방법이다.

RL에서의 동적계획법은 모델기반 방식에서 환경에 대한 정보(상태 전이확률, 보상함수)가 주어졌을 경우에만 사용가능하고, 정책 평가(policy evaluation)와 정책 개선(policy improvement)을 반복하여 최적의 정책을 찾게 된다.

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

강화학습에서 가치 함수와 정책함수는 매번 동일한 상태와 행동에 대한 중복 계산을 피하기 위해 저장 해놓고 이를 재사용 하기 위한 알고리즘으로 동적계획법을 사용한다.

동적계획법이 사용 되는 예(정책 반복, 가치 반복)

• 정책 반복: 정책 평가 과정에서 각 상태의 가치를 계산한 후 그 값을 저장. 이를 통해 동일한 상태에 대해 중복 계산하지 않고 메모이제이션의 효과를 얻음.

• 가치 반복: 각 상태의 가치를 계산하고, 해당 값을 저장한 후 다음 상태의 가치 계산에 재사용.

  
  

프로그래밍 예제

환경설정

import numpy as np

# 상태, 행동, 전이 확률 및 보상 설정 
states = [0, 1, 2, 3]
actions = [0, 1]  # 왼쪽(0), 오른쪽(1)
P = {
    0: {0: [(1.0, 0, 0)], 1: [(1.0, 1, 0)]},
    1: {0: [(1.0, 0, 0)], 1: [(1.0, 2, 0)]},
    2: {0: [(1.0, 1, 0)], 1: [(1.0, 3, 1)]},
    3: {0: [(1.0, 2, 0)], 1: [(1.0, 3, 0)]},
}
gamma = 0.9  # 할인율
theta = 1e-6  # 가치 함수 수렴 기준

가치반복 구현

가치반복은 정책평가와 정책 개선을 명시적으로 분리하지 않으므로, 구현이 비교적 단순하다. 그리고 가치 함수가 직접 업데이트 되며 일반적으로 빠르게 수렴되는 경향이 있다.

import numpy as np

def value_iteration(states, P, gamma, theta):
    V = np.zeros(len(states))  # 가치 초기화
    while True:
        delta = 0
        for s in states:
            v = V[s]
            # 가치 업데이트 (벨만 방정식 적용)
            V[s] = max(sum([p * (r + gamma * V[s_]) for p, s_, r in P[s][a]]) for a in actions)
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    return V

V = value_iteration(states, P, gamma, theta)
print("최종 가치 함수:", V)

정책반복 구현

def policy_evaluation(policy, P, gamma, theta):
    V = np.zeros(len(states))  # 가치 함수 초기화
    while True:
        delta = 0
        for s in states:
            v = V[s]
            action = policy[s]
            V[s] = sum([p * (r + gamma * V[s_]) for p, s_, r in P[s][action]])
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    return V

def policy_improvement(V, P, gamma):
    policy = np.zeros(len(states), dtype=int)
    for s in states:
        # 모든 행동에 대해 기대 보상 계산 후 최대값을 선택
        action_values = np.zeros(len(actions))
        for a in actions:
            action_values[a] = sum([p * (r + gamma * V[s_]) for p, s_, r in P[s][a]])
        policy[s] = np.argmax(action_values)  # 최대 기대 보상 행동 선택
    return policy

def policy_iteration(P, gamma, theta):
    # 임의의 정책으로 초기화 (모든 상태에서 0번 행동을 취함)
    policy = np.zeros(len(states), dtype=int)
    while True:
        V = policy_evaluation(policy, P, gamma, theta)
        new_policy = policy_improvement(V, P, gamma)
        if np.array_equal(new_policy, policy):  # 정책이 변하지 않으면 종료
            break
        policy = new_policy
    return policy, V

policy, V = policy_iteration(P, gamma, theta)
print("최적 정책:", policy)
print("최종 가치 함수:", V)

레퍼런스

• Dynamic Programming in RL : https://yjjo.tistory.com/27