동적 프로그래밍은 벨만 방정식의 문제점을 해결하기위해 나온 방식입니다. 보통 벨만 방정식을 이용해 가치함수를 구하는 흐름을 보면 상태전이확률 p(s'|s,a), 보상함수 r(s,a,s'), 정책 π(a|s)이라는 세가지 정보로 연립방정식 풀이로 가치함수를 구합니다. 그런데 상태와 행동 수가 많아질때 계산량이 감당할 수 없을 정도로 늘어나기에 이럴 때도 가치함수를 구할 수 있는 방법이 동적 프로그래밍입니다. 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 기법은 각 부분 문제를 한 번만 풀고, 그 결과를 저장하여 재활용함으로써 전체 문제를 효율적으로 해결합니다. 동적 프로그래밍은 주로 최적화 문제에 사용되며, 이러한 문제들은 하나의 큰 문제가 유사한 형태의 작은 부분 문제들로 구성될 때 효과적입니다. 동적 프로그래밍의 주요 개념 최적 부분 구조(Optimal Substructure): 큰 문제의 최적 해결책이 그 문제의 부분 문제들의 최적 해결책에서 파생될 수 있음을 의미합니다. 즉, 전체 문제의 최적 해결책은 부분 문제의 최적 해결책을 조합해서 얻을 수 있습니다. 중복 부분 문제(Overlapping Subproblems): 동일한 부분 문제가 여러 번 발생하므로, 한 번 계산한 부분 문제의 해결책을 메모리에 저장하고 필요할 때마다 재사용함으로써 계산 시간을 절약할 수 있습니다. 동적 프로그래밍의 접근 방법 동적 프로그래밍은 두 가지 주요 방법을 통해 구현될 수 있습니다: Top-Down (메모이제이션): 문제를 작은 부분으로 나누고, 각 부분의 해결책을 메모리에 저장해 나가면서 전체 문제를 해결합니다. 이 방법은 재귀적인 방식으로 구현되며, 메모리에 저장된 결과를 재활용함으로써 중복 계산을 피합니다. Bottom-Up (Tabulation): 가장 작은 부분 문제부터 시작하여 차례대로 문제의 해결책을 테이블에 저장해 나가면서 점진적으로 더 큰 문제를 해결합니다. 이 방법은 반복적인 방식으로 구현되며, 문제의 크기를 점점 늘려가면서 해결합니다. 예시: 피보나치 수열 피보나치 수열 문제를 동적 프로그래밍을 사용하여 해결할 수 있습니다. 피보나치 수열에서 각 숫자는 이전 두 숫자의 합으로 구성됩니다. 순수 재귀적 방법으로 피보나치 수를 계산하면 많은 중복 계산이 발생합니다. 하지만 동적 프로그래밍을 사용하면 각 숫자를 한 번만 계산하고 그 결과를 저장하여 필요할 때 재사용할 수 있습니다. 동적 프로그래밍은 이처럼 복잡한 문제를 단순화하고, 효율적으로 해결할 수 있는 강력한 도구로, 다양한 최적화 문제 및 계산 문제에서 널리 사용됩니다. 이 방법은 특히 정책 평가(Policy Evaluation)와 정책 제어(Policy Control) 또는 정책 개선(Policy Improvement) 과정에 사용됩니다. 이 두 과정을 통해 강화학습 에이전트는 주어진 환경에서 최적의 행동 방침을 학습할 수 있습니다. 정책 평가 (Policy Evaluation) 정책 평가는 주어진 정책의 가치 함수를 계산하는 과정입니다. 강화학습에서는 에이전트가 어떤 정책을 따를 때 각 상태의 가치, 즉 그 상태에서 시작하여 향후 얻을 수 있는 예상 리턴을 계산하는 것을 목표로 합니다. 과정 초기화: 각 상태에 대한 가치 함수 V(s)를 임의의 값으로 초기화합니다. 일반적으로 0으로 초기화하는 것이 흔합니다. 반복 계산: 다음의 벨만 기대 방정식을 사용하여 각 상태의 가치를 반복적으로 업데이트합니다. V(s)= a∈A ∑ π(a∣s) s′,r ∑ p(s′,r∣s,a)[r+γV(s′)] 여기서 π(a∣s)는 상태 s에서 행동 a를 선택할 정책의 확률, p(s′,r∣s,a)는 상태 s에서 행동 a를 취했을 때 상태 s′로 이동하고 보상 r을 받을 확률, γ는 할인율입니다. 수렴: 가치 함수 V(s)의 변경이 충분히 작아질 때까지 (즉, 가치 함수가 수렴할 때까지) 위 과정을 반복합니다. 정책 제어 (Policy Control) / 정책 개선 (Policy Improvement) 정책 제어는 평가된 가치 함수를 사용하여 현재 정책을 개선하는 과정입니다. 목표는 최적의 정책을 찾는 것이며, 이 과정은 정책 평가와 번갈아 가며 수행됩니다. 과정 정책 평가: 위에서 설명한 정책 평가 과정을 통해 현재 정책 π에 대한 가치 함수 Vπ(s)를 계산합니다. 정책 개선: 계산된 가치 함수를 사용하여 각 상태에서 최적의 행동을 선택하는 새로운 정책 π'를 만듭니다. 최적의 행동은 다음과 같이 선택됩니다: π′(s) = argmax a s′,r∑ p(s′,r∣s,a)[r+γV(s′)] 여기서 argmax a는 행동 a에 대해 최대값을 반환하는 행동을 선택합니다. 반복: 새로운 정책 π′가 이전 정책 π보다 더 나은 성능을 보이면, 이 새로운 정책을 사용하여 다시 정책 평가를 수행합니다. 이 과정을 정책이 더 이상 개선되지 않을 때까지 (즉, 최적 정책에 도달할 때까지) 반복합니다. 이렇게 동적 프로그래밍은 복잡한 강화학습 문제를 구조화된 방식으로 접근하며, 계산적으로 정책을 평가하고 개선하는 데 사용됩니다. 동적 프로그래밍의 장점은 그 정확성과 완전성에 있지만, 상태 공간이나 행동 공간이 매우 클 때는 계산적으로 제약을 받을 수 있습니다.
벨만 방정식은 현재상태 s의 가치함수 Vπ(s)와 다음상태 s'의 가치함수 Vπ(s')의 관계를 나타냅니다. 무한대로 반복되는 가치함수를 탈출하는 방법이 벨만 방정식이었고 이를 다시 복습하면 다음 식을 볼수 있습니다. Vπ(s) = Eπ[Rt + γGt+1 | St = s] = Eπ[Rt|St=s] + γEπ[Gt+1|St=s] = Σa Σs'π(a|s)p(s'|s,a)r(s,a,s') + γΣa Σs'π(a|s)p(s'|s,a)Vπ(s') = Σa Σs'π(a|s)p(s'|s,a) * {r(s,a,s') + γVπ(s')} 이것을 다음 상태의 가치함수 Vk(s')을 이용해 지금 상태의 가치함수 Vk+1(s)를 갱신한다는 점입니다.(이것을 부트스트래핑이라 함) Vk+1(s)는 k+1번째로 갱신된 가치함수를 의미하며 k번째로 갱신된 가치함수는 Vk(s)로 표시합니다. Vk+1(s)과 Vk(s)는 추정치라서 실제 가치함수인 V(s)와는 다릅니다. Vk+1(s) = Σa Σs' p(s'|s,a) * {r(s,a,s') + γVk(s')} 동적 프로그래밍에서 부트스트래핑은 중요한 개념 중 하나로, 강화학습의 맥락에서는 에이전트가 자신의 현재 추정치를 사용하여 미래의 가치 추정을 업데이트하는 과정을 의미합니다. 부트스트래핑은 추정된 가치 함수를 기반으로 새로운 추정치를 생성함으로써 학습 과정을 지속하게 합니다. 부트스트래핑의 핵심 개념 부트스트래핑은 주로 시간차(Temporal Difference, TD) 학습과 같은 강화학습 알고리즘에서 사용됩니다. 이는 에이전트가 완전한 에피소드를 경험할 필요 없이, 한 스텝 또는 몇 스텝의 데이터만으로 가치 함수를 업데이트할 수 있게 합니다. 부트스트래핑은 이전의 가치 추정치를 현재의 보상과 결합하여 미래의 가치 추정치를 생성하는 데 사용됩니다. 동적 프로그래밍에서의 부트스트래핑 동적 프로그래밍에서는 벨만 방정식을 사용하여 부트스트래핑을 구현합니다. 벨만 방정식은 현재 상태의 가치를 그 상태에서 취할 수 있는 행동에 따른 가능한 모든 결과의 기대값을 통해 계산합니다. 이 과정에서 부트스트래핑은 다음과 같이 나타납니다: 벨만 기대 방정식: V(s)= a∈A∑ π(a∣s) s',r∑ p(s′,r∣s,a)[r+γV(s′)] 여기서 V(s′)는 이전에 계산된 상태 s′의 가치 추정치를 사용하여 현재 상태 s의 가치를 업데이트합니다. 벨만 최적 방정식: V∗(s)= max a s′,r∑ p(s′,r∣s,a)[r+γV∗(s′)] 이 방정식은 가능한 모든 행동 a에 대해 최대 가치를 반환하며, 다음 상태 s′의 최적 가치 추정치 V∗(s′)를 사용합니다. 부트스트래핑의 중요성 부트스트래핑은 특히 계산 자원이 제한적이거나 완전한 에피소드를 기다리지 않고 빠르게 학습을 진행해야 할 때 유용합니다. 이 기법을 통해 에이전트는 실시간으로 정보를 업데이트하며, 보다 효율적으로 학습할 수 있습니다. 또한, 동적 프로그래밍과 같은 강화학습 알고리즘에서는 이를 통해 더 정확하고 일관된 가치 추정치를 제공할 수 있습니다. 부트스트래핑은 강화학습에서 에이전트가 불완전한 정보와 제한된 경험을 최대한 활용하도록 돕는 중요한 도구입니다. 이를 통해 에이전트는 자신이 경험한 것보다 더 많은 정보를 학습 결과에 반영할 수 있으며, 이는 효과적인 정책 개선과 빠른 학습 속도로 이어집니다. 여기서 DP의 구체적 알고리즘을 흐름대로 설명하겠습니다. 먼저 V0(s) = 0으로 초기화합니다. 다음 위 벨만방정식에서 갱신식으로 변형한 아래 식을 이용해 V0(s)에서 V1(s)로 갱신하고, 이어서 V1(s)을 기반으로 V2(s)로 갱신합니다. Vk+1(s) = Σa Σs' p(s'|s,a) * {r(s,a,s') + γVk(s')} 이와같이 반복하다보면 최종 목표인 Vπ(s)에 가까워지고, 이 알고리즘을 반복적 정책평가라고 합니다. DP의 핵심은 같은 계산을 두번하지 않는다는 것으로, 구현 방법에는 하향식 Top-Down (메모이제이션)과 상향식 Bottom-Up (Tabulation) 방법이 있고, 위에서 기재한 내용과 같습니다.
이번에는 동적 프로그래밍 의사결정 코드를 작성해 보겠습니다. 기본 덮어쓰기 방식으로 작성합니다. 초기값을 설정합니다. V = {'L1':0.0, 'L2':0.0} V를 복사한 것을 new_V에 대입시킵니다. new_V = V.copy() cnt = 0 #갱신횟수 기록 while True: 이 반복문 아래 다음 코드를 넣습니다. V0(s)에 대한 값을 먼저 넣습니다. t = 0.5 * (-1 + 0.9*V['L1']) + 0.5 * (1 + 0.9*V['L2']) V0(s)의 가치함수 식을 작성하고 갱신 전 V['L1']과의 차이 절대값을 계산하여 delta 함수에 넣습니다. delta = abs(t-V['L1']) 그 다음 계산된 t를 V['L1']에 대입 덮어쓰기합니다. V['L1'] = t V1(s)에 대한 값을 먼저 넣습니다. t = 0.5 * (0 + 0.9 * V['L1']) + 0.5 * (-1 + 0.9 * V['L2']) V1(s)의 가치함수 식을 작성하고 갱신 전 V['L2']과의 차이 절대값을 계산하여 delta 함수에 넣습니다. delta = max(delta, abs(t - V['L2'])) V['L2'] = t cnt += 1 if delta < 0.0001: #임계값 = 0.0001 print(V) print('갱신 횟수 :', cnt) break