강화학습 Part 3 Planning by Dynamic Programming

본 정리는 팡요랩(Pang-Yo Lab) 의 강화학습 강의(David Silver의 Reinforcement Learning Lecture 3: Planning by Dynamic Programming)

 

1. Introduction — DP가 뭐고 왜 MDP에 쓰나

Dynamic Programming이라는 말

Dynamic Programming(DP, 동적 계획법)은 복잡한 문제를 여러 개의 작은 부분 문제로 나누고, 각 부분 문제의 해를 이용해 전체 문제의 최적해를 구하는 방법이다.

DP가 하는 일은 결국 세 단계다.

1. 복잡한 문제를 작은 부분 문제(subproblem)로 쪼갠다
2. 부분 문제를 푼다
3. 그 답들을 합쳐 전체 문제를 푼다

DP를 쓸 수 있는 두 가지 조건

DP는 아무 문제에나 통하지 않는다. 다음 두 성질이 있어야 한다.

1. 최적 부분 구조 (Optimal substructure)
   • 최적성의 원리(principle of optimality)가 성립해야 한다.
   • 전체의 최적 해를 부분 문제들의 최적 해로 분해할 수 있다는 뜻이다. 쉽게 말해 전체가 최고이려면 그 안의 조각들도 각각 최고여야 한다.
2. 겹치는 부분 문제 (Overlapping subproblems)
   • 부분 문제가 여러 번 반복해서 등장한다.
   • 그래서 한 번 푼 답을 저장(cache)해두고 재사용할 수 있다. 만약 부분 문제가 딱 한 번씩만 나온다면 저장할 이유가 없다. 반복되니까 저장이 이득이다.

그리고 핵심은, MDP는 이 두 조건을 모두 만족한다는 점이다.

• Bellman equation이 재귀적 분해(recursive decomposition)를 제공한다 → 최적 부분 구조 충족. 현재 상태의 가치를 "즉시 보상 + 다음 상태의 가치"로 쪼개는 게 정확히 재귀 분해다.
• 가치 함수(value function)가 풀어둔 답을 저장·재사용하는 그릇이 된다 → 겹치는 부분 문제 충족.

즉 MDP라는 못은 DP라는 망치에 딱 맞는다.

Planning과 Prediction / Control

DP는 MDP를 완전히 알고 있다(full knowledge) 고 가정한다. 어떤 행동을 하면 어떤 상태로 갈 확률(전이확률 P)과 어떤 보상(R)을 받는지 미리 다 안다는 뜻이다. 그래서 실제로 환경을 돌아다니며 배우는 게 아니라 책상에서 미리 계산하는 것이고, 이걸 planning(계획) 이라고 부른다. (환경을 모르고 경험으로 배우는 learning은 뒤 강의들의 주제다.)

DP로 푸는 문제는 두 종류로 나뉜다. 이 구분이 중요하다.

• Prediction (예측)
  • 입력: MDP <S, A, P, R, γ> 와 정책 π
  • 출력: 그 정책의 가치 함수 vπ
  • "이 전략을 따르면 얼마나 좋은가?" 를 평가 (전략은 이미 주어져 있음)
• Control (제어)
  • 입력: MDP <S, A, P, R, γ> (정책 없음)
  • 출력: 최적 가치 함수 v* 와 최적 정책 π*
  • "가능한 모든 전략 중 최고는 무엇인가?" 를 찾기

정리하면 입력에 π가 있으면 prediction, 없으면 control이다.

 

---

2. Policy Evaluation (정책 평가)

무엇을, 왜

Prediction 문제를 푸는 방법이 정책 평가다. 목표는 주어진 정책 π의 가치 vπ를 구하는 것.

문제는, vπ를 정의식대로 직접 구하려면 "그 상태에서 시작해 미래에 받을 모든 보상의 기댓값"을 계산해야 하는데 미래가 무한히 뻗어 있어 한 번에 못 구한다는 점이다. 그래서 꼼수를 쓴다. 아무 초기값에서 시작해, Bellman expectation backup을 계속 적용하면 진짜 vπ로 수렴한다. 수렴한다는 보증은 강의 맨 끝(contraction mapping)에서 증명하고, 일단은 방법부터 익힌다.

Backup이라는 말

backup은 데이터 복사가 아니라, 미래(다음 상태)의 값을 끌어다 현재 상태의 값을 갱신한다는 뜻이다. 미래 정보가 현재로 거꾸로(back) 흘러오는 느낌이라 backup이다.

평가는 synchronous backup을 쓴다. 즉 한 번의 반복에서 모든 상태를 동시에, 각자 이전 단계(k)의 값만 보고 갱신한다. k+1을 계산하는 동안 방금 새로 계산한 값을 끼워 쓰지 않는다.

Backup diagram

• 맨 위 흰 동그라미 = 지금 값을 계산할 상태 s. v_{k+1}(s)를 구한다.
• 검은 점 = 행동(action) a. 상태에서 갈래가 갈라지는데 각 갈래가 선택 가능한 행동이다.
• 검은 점에서 다시 내려오는 선 = 그 행동을 했을 때 갈 수 있는 다음 상태들. 환경이 확률적이라 한 행동에서도 여러 곳으로 갈라진다.
• 선 옆 r = 그 전이에서 받는 보상.
• 맨 아래 흰 동그라미 = 다음 상태 s'. 여기엔 이전 단계 값 v_k(s')가 들어간다.

여기서 핵심 한 가지. 갈림길이 두 단계인 이유는 두 가지 질문에 답해야 하기 때문이다.

갈래누가 결정하나기호

상태 → 행동	내가 고른다	π (정책)
행동 → 다음 상태	세상(환경)이 정한다	P (전이확률)

흰 동그라미(상태)와 검은 점(행동)을 다르게 그린 이유가 이것이다. π는 내가 행동을 고를 확률, P는 행동 후 환경이 나를 어디로 보낼 확률. 하나는 나, 하나는 세상이다. 이 둘을 헷갈리면 안 된다.

또 하나, 이 나무는 딱 한 단계(one-step)만 내려간다. 다음 상태 s'가 그 뒤로 어디 가는지는 파고들지 않고, 그냥 이전 표에 적힌 v_k(s')를 읽어온다. 그 값 안에 이미 s'의 (어제까지 계산한) 미래가 담겨 있기 때문이다. 무한히 깊은 나무를 한 번에 펼치는 대신, 1층짜리 얕은 나무를 여러 번 쌓아서 무한한 깊이를 만드는 셈이다.

수식

정책 평가의 갱신식은 다음과 같다.

v_{k+1}(s) = Σ_a π(a|s) [ R_s^a + γ Σ_s' P_{ss'}^a · v_k(s') ]

기호는 이렇게 읽는다.

• v_{k+1}(s) : 상태 s의 새 값
• Σ_a : 모든 행동 a에 대해 더한다
• π(a|s) : 상태 s에서 행동 a를 고를 확률
• R_s^a : s에서 a를 했을 때 받는 즉시 보상
• γ : 할인율(0~1). 미래 보상은 현재보다 가치를 깎아서 본다. "지금 받는 만 원"이 "1년 뒤 만 원"보다 좋다는 직관을 수식으로 표현한 것
• Σ_s' : 갈 수 있는 모든 다음 상태 s'에 대해 더한다
• P_{ss'}^a : s에서 a를 했을 때 s'로 갈 확률
• v_k(s') : 다음 상태 s'의 이전 단계 값

말로 풀면 이렇다. 상태 s의 새 값 = (내가 할 수 있는 각 행동에 대해) [그 행동을 고를 확률] × [즉시 보상 + 할인율 × (다음 상태들의 옛 가치를 확률로 가중평균한 값)] 을 전부 합한 것. 더 짧게는 "지금 당장의 보상 + 깎아본 미래의 가치"를 행동과 다음 상태에 대해 확률로 평균낸 것이다.

이 "즉시 보상 + γ × 다음 상태 가치" 구조가 Bellman equation의 심장이다. 가치를 "지금 한 입 + 나머지는 미래에 위임"으로 쪼개는 것, 이게 앞에서 말한 재귀적 분해다.

같은 식을 모든 상태에 대해 한꺼번에 행렬로 쓰면 이렇게 된다.

v^{k+1} = R^π + γ P^π v^k

• v^{k+1} : 모든 상태의 새 값을 줄세운 벡터
• R^π : 정책 π를 따를 때 각 상태의 기대 즉시 보상 벡터
• P^π : 정책 π를 따를 때의 상태 전이 확률 행렬

두 식은 다른 게 아니라 "낱개 버전"과 "전체 묶음 버전"의 차이일 뿐이다. 행렬이 부담스러우면 첫 식만 확실히 이해해도 된다.

짚고 넘어갈 점 — "환경을 다 아는데 왜 부정확하다고 하나"

정책 평가를 보면 "처음엔 부정확하고 점점 정확해진다"는 말이 나오는데, 환경(P, R)이 다 정의돼 있다면 정답도 정해져 있는 것 아닌가? 라는 의문이 생긴다.

여기서 두 가지를 구분해야 한다.

• 환경의 규칙(P, R) : 이미 다 알고 있다. 절대 안 변한다.
• 가치 함수 vπ : 그 규칙으로부터 나오는 "답"이고, 아직 계산 안 했다.

수학 문제집에 비유하면, 문제(환경)는 또렷하게 다 인쇄돼 있지만 답(가치)은 아직 안 풀었다. "정답이 존재한다"와 "내가 정답을 손에 쥐고 있다"는 다른 얘기다. 부정확한 건 환경이 아니라, 우리가 표에 적어놓은 중간 추측값이다. 반복할수록 변하는 건 우리 노트의 숫자뿐이고, 환경은 한 글자도 안 변한다.

왜 한 번에 정답을 못 적나? 각 상태의 가치가 서로 꼬리에 꼬리를 물고 얽혀 있는 연립방정식이기 때문이다. 사실 환경을 다 알면 행렬로 한 번에 풀 수도 있다.

vπ = (I − γ P^π)^(−1) R^π

그런데 이 역행렬 계산이 상태 수 n에 대해 O(n³)으로 너무 비싸다. 상태가 백만 개면 불가능하다. 반복법은 O(n²)로 훨씬 싸고, 큰 문제에서도 작동하고, 나중에 배울 model-free 방법으로도 자연스럽게 확장된다. 그래서 반복법을 쓴다.

---

3. Small Gridworld 예시

문제 설정

• 4×4 격자, 좌상단과 우하단이 같은 하나의 종료 상태(회색칸). 나머지 14칸이 비종료 상태
• 할인 없음(γ = 1), episode형 MDP
• 행동은 상하좌우, 격자 밖으로 나가면 제자리
• 보상은 종료까지 매 이동 −1 (빨리 끝낼수록 손해가 적다)
• 평가 대상 정책: 균등 랜덤. π(n|·) = π(e|·) = π(s|·) = π(w|·) = 0.25

표가 채워지는 과정

• k=0 : 전부 0 (초기값)
• k=1 : 종료칸 빼고 전부 −1 (한 번 움직이면 −1)
• k=2 : 종료에서 먼 칸은 −2.0, 종료 바로 옆은 −1.7
• k=3, k=10, ..., k=∞ : 종료에서 멀수록 점점 큰 음수(−14, −20, −22)로 수렴

여기서 -1.7이 어떻게 나오는지 직접 계산해보면 감이 확실히 잡힌다. k=1 상태(전부 -1, 종료칸 0)에서 좌상단 종료칸 바로 오른쪽 칸(슬라이드의 1번 칸)의 새 값을 구해본다. γ=1, 보상 -1, 확률적 전이가 없으니 P는 그 방향 한 칸으로 100%다.

• 왼쪽(종료칸, 값 0) : −1 + 0 = −1
• 오른쪽(값 −1) : −1 + (−1) = −2
• 아래(값 −1) : −1 + (−1) = −2
• 위(격자 밖, 제자리 값 −1) : −1 + (−1) = −2

행동을 0.25씩 평균내면

v_2(1) = 0.25×(−1) + 0.25×(−2) + 0.25×(−2) + 0.25×(−2) = −7/4 = −1.75 ≈ −1.7

슬라이드의 −1.7이 정확히 이렇게 나온다. 종료칸의 좋은 정보(0점)가 평균을 끌어올려서 다른 칸(−2.0)보다 덜 나쁜 −1.7이 된 것이다. 종료칸 근처부터 값이 정확해지고, 그 정보가 매 반복마다 한 칸씩 바깥으로 번진다. 

Greedy Policy — 갑자기 등장하는 화살표

슬라이드를 보면 왼쪽엔 숫자표, 오른쪽엔 화살표 그림이 나온다. 이 화살표가 바로 Greedy Policy w.r.t. v_k, 즉 "그 값표를 보고 각 칸에서 어느 방향으로 가야 하는가"를 나타낸 행동 지도다.

화살표를 정하는 규칙은 하나다. 각 칸에서 이웃 칸들의 값을 보고, 가장 값이 높은(0에 가장 가까운) 칸 방향으로 화살표를 그린다. 이게 greedy(탐욕적)의 뜻이다. 그리드월드는 값이 다 음수라 "가장 높은 값 = 가장 덜 나쁜 칸"이 된다.

• k=0 : 모든 칸 값이 0으로 똑같다. 전부 동점이라 사방 화살표(어디로 가도 똑같다 = random policy)
• k=1 : 종료칸 바로 옆 칸들은 "종료칸이 0으로 제일 좋다"는 걸 알아채 종료칸 방향 화살표가 하나 생긴다. 먼 칸은 여전히 동점이라 사방 화살표
• k=2 : 정보가 한 칸 더 퍼져 두 칸 떨어진 곳까지 방향이 잡힌다

여기서 사방 화살표는 "좋은 칸"이 아니라 "이웃이 다 동점이라 아직 우열을 못 가렸다"는 신호라는 점을 헷갈리면 안 된다.

그리고 이 예시의 가장 중요한 통찰. k=3쯤 되면 화살표(greedy 정책)가 이미 최적 정책과 똑같아진다. 값(v_k)은 아직 −2.4 수준으로 진짜 값(−14, ...)과 한참 다른데도, 그 값을 보고 뽑은 행동은 벌써 최적이다. 화살표를 정할 때 중요한 건 값의 정확한 크기가 아니라 이웃 간 대소 관계뿐이기 때문이다. 가치를 완벽히 평가하지 않아도 충분히 평가하면 더 좋은 정책을 뽑을 수 있다는 것, 이게 다음에 나올 policy iteration의 출발점이다.

---

4. Policy Iteration (정책 반복)

두 단계의 반복

정책 평가는 점수만 매긴다. 우리가 진짜 원하는 건 최고의 전략 찾기(control)다. 그래서 한 단계 더 나간다. 점수를 매겼으니 그 점수를 보고 더 나은 전략으로 갈아타자는 것.

정책 반복은 두 단계를 무한히 번갈아 한다.

1. 정책 평가(evaluation) : 현재 정책 π의 가치 vπ를 계산
2. 정책 개선(improvement) : vπ를 보고 탐욕적으로 새 정책 생성, π' = greedy(vπ)

위 화살표가 evaluation(π에서 V를 얻음), 아래 화살표가 improvement(V에서 새 π를 얻음)다. 이 둘을 번갈아 돌리면 π → vπ → π' → vπ' → ... 식으로 진행되어 결국 π와 V가 서로 딱 맞아떨어지는 안정점에서 멈춘다. 그리고 그 안정점은 반드시 최적이다.

왜 개선이 반드시 통하는가

정책 개선은 결정적 정책에 대해 탐욕적으로 행동을 바꾸는 것이다.

π'(s) = argmax_a q_π(s, a)

여기서 q_π(s, a)는 상태 s에서 행동 a를 했을 때의 가치(행동가치)이고, argmax는 최댓값을 주는 행동 자체를 고른다는 뜻이다.

한 걸음만 봐도 이득인 이유는 간단하다.

q_π(s, π'(s)) = max_a q_π(s, a) ≥ q_π(s, π(s)) = v_π(s)

가장 좋은 행동을 골랐으니 최소한 손해는 아니다(최댓값은 항상 그 자체보다 작지 않다). 이걸 한 걸음, 두 걸음 계속 펼치면 결국 모든 상태에서 v_{π'}(s) ≥ v_π(s), 즉 새 정책이 옛 정책보다 좋거나 같다. 매 갈림길에서 더 좋은 선택을 하면 전체 여정도 더 좋아진다는 당연한 얘기지만, 이걸 수학적으로 못 박은 게 중요하다.

그럼 언제 멈추나? 개선해도 정책이 안 바뀌는 순간이 오면 이렇게 된다.

q_π(s, π'(s)) = max_a q_π(s, a) = q_π(s, π(s)) = v_π(s)

이는 곧

v_π(s) = max_a q_π(s, a)

인데, 이게 바로 Bellman optimality equation이다. 이 방정식이 성립한다는 건 현재 가치가 곧 최적 가치(v_π = v*)라는 뜻이고, 따라서 π가 최적 정책이다. "더 개선할 게 없는 지점"과 "최적 지점"이 수학적으로 같다는 것, 그래서 정책 반복은 최적이 아닌 곳에서는 멈추지 않고 최적에 도달하면 자동으로 멈춘다.

확장 — 평가를 끝까지 안 해도 된다

개선 전에 평가를 vπ까지 완전히 수렴시켜야 하나? 그렇지 않다. ε-수렴(거의 안 변하면)에서 멈추거나 아예 k번만 평가하고 개선해도 된다. 그리드월드는 k=3번 평가면 이미 최적 정책이 나왔다. 극단적으로 평가를 딱 한 번만(k=1) 하고 바로 개선하는 게 바로 다음에 나올 value iteration이다.

여기서 한 발 더 나가면 Generalised Policy Iteration(GPI) 이다. 평가도 어떤 방법이든(any), 개선도 어떤 방법이든(any) 써서 번갈아 하면 된다는 일반 원리다. 앞으로 배울 수많은 알고리즘(SARSA, Q-learning 등)이 전부 "평가 방법 + 개선 방법"의 조합이고, GPI는 그 모두의 공통 뼈대다.

---

5. Value Iteration (가치 반복)

아이디어

정책 반복은 강력하지만 평가를 매번 (거의) 끝까지 돌리는 게 번거롭다. 그 평가를 딱 한 번으로 줄이고, 정책을 명시적으로 만들지도 않고, 그냥 값표만 갱신하는 게 value iteration이다.

이론적 토대는 Principle of Optimality다. 최적 정책은 "최적의 첫 행동 + 그 다음 상태에서의 최적 정책"으로 쪼개진다. 곧 전체 최적은 부분 최적들로 분해된다는, 앞에서 본 최적 부분 구조와 같은 얘기다.

그래서 만약 부분 문제의 답 v*(s')를 안다면 한 단계 내다보기로 v*(s)를 구할 수 있다.

v*(s) ← max_a [ R_s^a + γ Σ_s' P_{ss'}^a · v*(s') ]

물론 다음 칸의 최적값도 처음엔 모르니, 이 갱신을 반복 적용한다. 직관은 "최종 보상에서 시작해 거꾸로 일한다"이다. 종료/목표 지점의 값은 확실히 아니까, 그 값을 한 칸씩 거꾸로 퍼뜨린다. 루프가 있고 확률적인 일반 MDP에서도 작동한다.

예시: Shortest Path

이 예시가 value iteration을 눈으로 보게 해준다.

좌상단이 목표 g, 매 이동 보상 −1, γ = 1이다. 각 칸을 "−1 + (이웃 중 가장 큰 값)"으로 갱신한다. 여기서 가장 중요한 점 하나.

새 값을 계산할 때 쓰는 건 그 칸 자신의 값이 아니라, 이웃 칸들의 (이전 표) 값이다.

직접 손으로 따라가보면 숫자가 어디서 나오는지 분명해진다. 칸 번호를 이렇게 두자.

[ g ] [ 1 ] [ 2 ] [ 3 ]
[ 4 ] [ 5 ] [ 6 ] [ 7 ]
[ 8 ] [ 9 ] [10 ] [11 ]
[12 ] [13 ] [14 ] [15 ]

V2에서 V3를 만들 때, 칸2의 새 값을 구한다. 이때 칸2 자신의 값(−1)이 아니라 칸2의 이웃들의 V2 값을 본다. V2는 g만 0이고 나머지가 전부 −1이다.

• 왼쪽(칸1, 값 −1) : −1 + (−1) = −2
• 오른쪽(칸3, 값 −1) : −1 + (−1) = −2
• 아래(칸6, 값 −1) : −1 + (−1) = −2
• 위(격자 밖, 제자리) : −1 + (−1) = −2

이웃에 0이 없으니 전부 −2, max = −2다. 반면 g 바로 옆인 칸1은 왼쪽 이웃이 g(0)이라 −1 + 0 = −1로 멈춘다. 그래서 V3에서 g 옆 칸들은 −1, 두 칸 떨어진 칸들은 −2가 된다.

다음 단계 V3에서 V4를 만들 때, 칸3의 값을 보면 −3이 처음 등장한다. 칸3의 이웃은 V3에서 전부 −2이므로 −1 + (−2) = −3이 최선이다. −3이 나오려면 가장 좋은 이웃이 −2여야 한다는 점을 확인할 수 있다.

여기서 자주 하는 착각 하나를 정리하면, "현재 칸이 −2니까 −1 더해서 −3"이 아니다. 새 값은 내 값이 아니라 이웃 값으로 계산하고, 무엇보다 −1 + (−1)은 −2이지 −3이 아니다. −3은 가장 좋은 이웃이 −2일 때 나온다.

각 숫자의 정체를 한 줄로 정리하면 이렇다.

값계산의미

−1	−1 + 0 (이웃에 g)	g까지 1걸음
−2	−1 + (−1)	g까지 2걸음
−3	−1 + (−2)	g까지 3걸음
−4	−1 + (−3)	g까지 4걸음
−5	−1 + (−4)	g까지 5걸음
−6	−1 + (−5)	g까지 6걸음

전부 똑같은 "−1 + 가장 좋은 이웃값" 계산의 반복일 뿐이다. g(0)에 가까운 칸부터 확정되고, 그 확정값이 다음 반복에서 더 바깥 칸의 재료가 되어 정보가 한 칸씩 번진다. 우하단 칸은 g에서 6걸음 떨어져 있어 V7에서야 정확한 −6이 채워지며 완성된다. 결국 각 칸 값은 "g까지 최단 걸음 수 × (−1)"이 된다. (사실상 다익스트라 최단경로의 사촌이다.)

수식과 backup diagram

v_{k+1}(s) = max_a [ R_s^a + γ Σ_s' P_{ss'}^a · v_k(s') ]
v_{k+1}   = max_a [ R^a + γ P^a v_k ]

정책 평가 식과 딱 한 군데만 다르다.

정책 평가 :  Σ_a π(a|s) (...)   ← 정책 확률대로 가중평균
가치 반복 :  max_a (...)        ← 가장 좋은 행동 하나만 선택

이 한 글자(평균 → max)가 "평가"를 "최적화"로 바꾼다. 앞의 그리드월드 -1.7 계산이 평가(평균)였다면, 가치 반복에서는 같은 칸이 max를 골라 -1로 깔끔하게 떨어진다. 평균은 동점이 아닌 행동까지 다 섞지만, max는 가장 짧은 길만 채택하기 때문이다. backup diagram(맨 위 그림의 오른쪽)에서 상태 노드에 호(arc)가 추가된 게 이 max를 뜻한다. 평가에는 이 호가 없다(다 더해 평균내니까).

정책 반복과의 차이

구분Policy IterationValue Iteration

평가	여러 번(또는 끝까지)	딱 1번
핵심 연산	π로 평균(평가) + max(개선)	매번 max
명시적 정책	있음	없음 (끝나고 추출)
기반 방정식	Bellman expectation	Bellman optimality
중간 결과	항상 실제 정책에 대응	어떤 정책에도 대응 안 할 수 있음

핵심 관계는 value iteration = 평가를 1스텝만 하는 policy iteration이다. 그리고 value iteration은 계산 내내 명시적 정책이 없다. 우리는 V1~V7을 계산하는 동안 화살표(방향)를 한 번도 정하지 않았다. 그냥 숫자만 계속 고쳤고, 중간 단계의 값표는 어떤 실제 정책에도 대응하지 않을 수 있다. 최종 정책 π는 수렴한 v에 대해 마지막에 한 번 argmax로 뽑으면 된다.

---

6. Synchronous DP 알고리즘 정리

지금까지의 세 알고리즘을 한 표로 정리하면 이렇다.

ProblemBellman EquationAlgorithm

Prediction	Bellman Expectation Equation	Iterative Policy Evaluation
Control	Bellman Expectation Equation + Greedy Policy Improvement	Policy Iteration
Control	Bellman Optimality Equation	Value Iteration

• 세 알고리즘 모두 state-value function vπ(s) 또는 v*(s)에 기반한다.
• 복잡도는 한 번의 iteration당 O(m n²)이다 (m = 행동 수, n = 상태 수). 한 상태를 갱신할 때 모든 행동(m)과 모든 다음 상태(n)를 보고, 그걸 모든 상태(n)에 대해 하므로 m × n × n이다.
• action-value function qπ(s, a) 또는 q*(s, a)에 적용할 수도 있는데, 이 경우 복잡도는 O(m² n²)로 커진다.

여기서 짚어둘 점. 위 알고리즘들은 전부 synchronous backup(모든 상태를 동시에 갱신)을 가정한다.

 

출처: 팡요랩(Pang-Yo Lab) 강화학습 강의 David Silver의 Reinforcement Learning Lecture 3: Planning by Dynamic Programming