[RL] Dynamic Programming으로 MDP 풀기
Dynamic Programming(DP)은 Markov Decision Process(MDP) 같은 환경 모델이 완벽하게 주어졌을 때 optimal policy를 계산하는 알고리즘들을 가리킴.
- 고전적 DP는 완벽한 모델과 막대한 계산량을 요구하기 때문에 강화학습 실무에서 직접 쓰이는 일은 드묾
- Monte Carlo, TD 등이 “더 적은 계산으로 DP와 같은 효과를 내려는 시도”
환경이 finite MDP로 모델링된다고 가정하자
- 상태 집합 $\mathcal{S}$, 행동 집합 $\mathcal{A}$, 보상 집합 $\mathcal{R}$이 모두 유한하고, 환경의 dynamics가 모든 $s \in \mathcal{S}$, $a \in \mathcal{A}(s)$, $r \in \mathcal{R}$, $s’ \in \mathcal{S}^+$에 대해 확률 $p(s’, r \mid s, a)$로 주어진다
- $\mathcal{S}^+$는 episodic 문제에서 종료 상태까지 포함한 집합
RL에서는 value function을 사용해 좋은 policy를 찾는 과정을 체계화하고 싶음.
출발점은 Bellman optimality equation :
\[v_*(s) = \max_a \mathbb{E}\big[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s, A_t = a\big] = \max_a \sum_{s', r} p(s', r \mid s, a)\big[r + \gamma v_*(s')\big]\] \[q_*(s, a) = \mathbb{E}\Big[R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \mid S_t = s, A_t = a\Big] = \sum_{s', r} p(s', r \mid s, a)\Big[r + \gamma \max_{a'} q_*(s', a')\Big]\]DP의 모든 알고리즘은 이런 Bellman equation을 목표 value function에 근사시키기 위해서 갱신 규칙(assignment) 으로 변환.
- 벨만 방정식은 원래 등호로 성립하는 조건 방정식
- \[v_\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma v_\pi(s')]\]
- 등호를 할당으로 변환
- \[V(s) \leftarrow \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]\]
- 현재 추정값 V(s)를 오른쪽 계산 결과로 덮어써
- 이걸 모든 상태에 대해 반복하면, V가 점점 진짜 $v_\pi$에 수렴
- 수학에서 $x = f(x)$ 형태의 방정식을 analytically 풀기 어려울 때, 수치적으로 \(x_{t+1} \leftarrow f(x_t)\)를 반복해서 고정점(fixed point)을 찾는 것과 같은 논리
- 벨만 방정식의 해가 value function의 고정점
- DP는 이 반복 할당으로 그 고정점을 찾아
Policy Evaluation (Prediction)
그러면 이 변환이 어떻게 작동하는가
policy evaluation / prediction problem : 먼저 임의의 policy $\pi$에 대해 state-value function $v_\pi$를 계산하는 문제
$v_\pi$의 정의에서 출발해 Bellman equation 형태로 전개하면 다음과 같음 :
\[\begin{aligned} v_\pi(s) &\doteq \mathbb{E}*\pi[G_t \mid S_t = s] \\ &= \mathbb{E}*\pi[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ &= \mathbb{E}*\pi[R*{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s] \\ &= \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\big[r + \gamma v_\pi(s')\big] \end{aligned}\]- $\pi(a \mid s)$ : policy $\pi$ 하에서 상태 $s$에서 행동 $a$를 선택할 확률
- $\gamma < 1$이거나 $\pi$를 따를 때 모든 상태가 결국 종료에 도달하는 것이 보장되면 $v_\pi$의 존재와 uniqueness가 보장됨.
환경 dynamics를 완전히 안다면 이 Bellman equation은 미지수 $v_\pi(s)$가 $|\mathcal{S}|$개인 선형 연립방정식이 됨.
- iterative solution method으로 $|\mathcal{S}|$ 개의 방정식 계산
Iterative Policy Evaluation
근사 value function의 나열 $v_0, v_1, v_2, \dots$이 있을 때
초기값 $v_0$는 임의로 잡되(단, 종료 상태의 가치는 $0$), 이후 Bellman equation을 갱신 규칙으로 사용함.
\[v_{k+1}(s) \doteq \mathbb{E}_\pi[R_{t+1} + \gamma v_k(S_{t+1}) \mid S_t = s] = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\big[r + \gamma v_k(s')\big]\]- $v_k = v_\pi$일 때 Bellman equation 자체가 성립하므로 $v_\pi$는 이 갱신의 fixed point
- $v_\pi$ 존재를 보장하는 조건 아래서 $k \to \infty$이면 ${v_k}$는 $v_\pi$로 수렴함
- 이 알고리즘이 iterative policy evaluation
각 스텝에서 이전 추정값 전체 $v_k$ 를 입력으로 써서 새 추정값 전체 $v_{k+1}$ 를 계산
- 매 step에서 모든 상태에 동일한 연산을 적용함.
- 어떤 상태 $s$의 이전 가치를, “그 상태 이후에 나타나는 상태들의 이전 가치 + 즉각 보상”의 기댓값으로 대체함.
- 이런 종류의 갱신을 expected update라고 부름.
- 표본이 아니라 가능한 전체 상태에 대한 기댓값에 기반하기 때문임.
pseudocode
구현 관점에서 배열을 두 개 쓸 수도 있지만(이전 $v_k$, 새 $v_{k+1}$), 하나의 배열로 새 값이 이전 값을 덮어쓰는 in-place 방식이 더 간단하고, 보통 더 빨리 수렴함. 새 데이터가 생기는 즉시 활용되기 때문임.
1
2
3
4
5
6
7
8
9
10
11
입력: 평가할 policy π
파라미터: 정확도 기준값 θ > 0
초기화: 모든 s ∈ S+에 대해 V(s)를 임의로, 단 V(종료) = 0
loop:
Δ ← 0
for all s ∈ S:
v ← V(s)
V(s) ← Σ_a π(a|s) Σ_{s',r} p(s',r|s,a)[r + γV(s')]
Δ ← max(Δ, |v − V(s)|)
until Δ < θ
- 갱신은 상태 공간에 대해 sweep(일괄처리) 하는 방식으로 이루어짐.
- 형식적으로는 극한에서 수렴하지만, 실제로는 매 sweep 이후 $\max_s |v_{k+1}(s) - v_k(s)|$가 충분히 작으면 멈춤.
예제: 1×4 grid search
1×4 격자에서
1
[ G ][ 1 ][ 2 ][ 3 ]
G는 종료 상태(goal), 비종료 상태는 $\mathcal{S} = {1, 2, 3}$- 행동은 ${\text{Left}, \text{Right}}$, 결정론적 이동
상태 1에서 Left → G, 상태 3에서 Right는 벽이라 제자리(3→3)
- 모든 transition 보상 $r = -1$, $\gamma = 1$, $v(G) = 0$
Random policy를 evaluation
equiprobable random policy는 각 상태에서 Left 0.5, Right 0.5임. 갱신 식은 이렇게 펼쳐짐.
\[v(s) = \sum_a \pi(a\mid s)\big[r + \gamma, v(s')\big] = 0.5\big[-1 + v(s_L)\big] + 0.5\big[-1 + v(s_R)\big]\]각 상태의 이웃을 대입하면:
- 상태 1: $0.5[-1 + v(G)] + 0.5[-1 + v(2)]$
- 상태 2: $0.5[-1 + v(1)] + 0.5[-1 + v(3)]$
- 상태 3: $0.5[-1 + v(2)] + 0.5[-1 + v(3)]$ ← Right가 제자리라 $v(3)$이 자기 자신으로 들어감
이걸 $v_0 = [0,0,0]$에서 시작해 sweep하면:
| $k$ | $v(1)$ | $v(2)$ | $v(3)$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | -1 | -1 | -1 |
| 2 | -1.5 | -2 | -2 |
| 3 | -2 | -2.75 | -3 |
| … | … | … | … |
| ∞ | -6 | -10 | -12 |
수렴값은 연립방정식으로 바로 확인됨. 상태 3 식에서 $0.5\ v(3) = -1 + 0.5\ v(2)$, 즉 $v(3) = v(2) - 2$.
이걸 대입해 풀면 $v(2) = -10,\ v(1) = -6,\ v(3) = -12$가 나옴.
직관적으로도 이해 가능.
동전 던지듯 좌우로 헤매며 goal까지 가는 기대 step 수임. goal에서 멀수록(3번 칸) 더 오래 걸림.
1
2
3
random policy v_π:
[ G=0 ][ 1=-6 ][ 2=-10 ][ 3=-12 ]
↔ ↔ ↔ (각 칸 L/R 50:50로 헤맴)
그 $v_\pi$에 greedy를 씌움
이제 각 칸에서 $q_\pi(s,a) = -1 + v_\pi(s’)$를 두 행동에 대해 계산하고 큰 쪽을 고름.
| 상태 | Left | Right | greedy |
|---|---|---|---|
| 1 | $-1 + v(G)=0 \Rightarrow \mathbf{-1}$ | $-1 + v(2)=-10 \Rightarrow -11$ | Left ← |
| 2 | $-1 + v(1)=-6 \Rightarrow \mathbf{-7}$ | $-1 + v(3)=-12 \Rightarrow -13$ | Left ← |
| 3 | $-1 + v(2)=-10 \Rightarrow \mathbf{-11}$ | $-1 + v(3)=-12 \Rightarrow -13$ | Left ← |
세 칸 모두 Left가 이김. greedy policy는 전부 goal 쪽임.
1
2
greedy policy π':
[ G ][ ←1 ][ ←2 ][ ←3 ] (전부 왼쪽 = goal 직행)
두 policy 비교
| 칸 | random $v_\pi$ | greedy $v_{\pi’}$ (=goal까지 거리) |
|---|---|---|
| 1 | -6 | -1 |
| 2 | -10 | -2 |
| 3 | -12 | -3 |
random은 좌우로 헤매서 비용이 크게 쌓이지만, greedy는 곧장 직행해서 거리만큼만 듦. 모든 칸에서 $v_{\pi’} \geq v_\pi$이므로 policy improvement가 일어난 것임. 그리고 이 예제에선 한 번의 improvement만으로 곧장 optimal policy에 도달함(왼쪽으로 직행보다 빠른 길은 없으니까).
결론 : 이 $v_\pi$에 대해 greedy하게 행동하는 policy를 만들면 random policy보다 훨씬 좋아진다.
- 이게 policy improvement의 목적
Policy Improvement
value function을 계산하는 이유는 더 좋은 policy를 찾기 위해서임.
어떤 상태 $s$에서 현재 policy를 따르는 것이 얼마나 좋은지는 $v_\pi(s)$로 알지만, $s$에서 $a \neq \pi(s)$를 한 번 선택하고 그 후로는 $\pi$를 따른다면 결과가 어떨지 :
\[q_\pi(s, a) \doteq \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = a] = \sum_{s', r} p(s', r \mid s, a)\big[r + \gamma v_\pi(s')\big]\]이 값이 $v_\pi(s)$보다 크다면, $s$에 올 때마다 $a$를 선택하는 것이 더 나은 선택이고, 이 새로운 policy가 전반적으로 더 좋을 것이라 기대됨.
Policy Improvement Theorem
임의의 deterministic policy $\pi, \pi’$가 모든 $s \in \mathcal{S}$에 대해
\[q_\pi(s, \pi'(s)) \geq v_\pi(s)\]를 만족하면, $\pi’$은 $\pi$만큼 좋거나 그 이상으로 좋음.
\[v_{\pi'}(s) \geq v_\pi(s)\]가 모든 $s$에서 성립함.
- 어딘가에서 전제 부등식이 strict이면 결론 부등식도 적어도 한 상태에서 strict임.
증명 (전제 부등식을 반복 적용) :
\[\begin{aligned} v_\pi(s) &\leq q_\pi(s, \pi'(s)) \\ &= \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = \pi'(s)] \\ &= \mathbb{E}*{\pi'}[R*{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s] \\ &\leq \mathbb{E}*{\pi'}[R*{t+1} + \gamma, q_\pi(S_{t+1}, \pi'(S_{t+1})) \mid S_t = s] \\ &= \mathbb{E}*{\pi'}[R*{t+1} + \gamma, \mathbb{E}*{\pi'}[R*{t+2} + \gamma v_\pi(S_{t+2})] \mid S_t = s] \\ &= \mathbb{E}*{\pi'}[R*{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) \mid S_t = s] \\ &\leq \mathbb{E}*{\pi'}[R*{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 v_\pi(S_{t+3}) \mid S_t = s] \\ &\ \ \vdots \\ &\leq \mathbb{E}*{\pi'}[R*{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \mid S_t = s] \\ &= v_{\pi'}(s) \end{aligned}\]매 줄에서 $q_\pi$의 정의로 한 step 펼치고, 전제 부등식으로 다시 $q_\pi$를 끼워 넣는 것을 반복함.
결국 $v_\pi(s) \leq v_{\pi’}(s)$가 나옴.
Greedy Policy
한 상태가 아니라 모든 상태에서 모든 행동에 대해 $q_\pi(s, a)$가 가장 좋아 보이는 행동을 고르는 greedy policy $\pi’$ :
\[\begin{aligned} \pi'(s) &\doteq \arg\max_a q_\pi(s, a) \\ &= \arg\max_a \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = a] \\ &= \arg\max_a \sum_{s', r} p(s', r \mid s, a)\big[r + \gamma v_\pi(s')\big] \end{aligned}\]greedy policy는 한 step 앞만 보고 $v_\pi$ 기준 최선의 행동을 택하므로 정의상 policy improvement theorem의 전제를 만족함.
따라서 policy improvement theorem에 의해 원래 policy 이상으로 좋음.
이렇게 기존 value function에 대해 greedy하게 만들어 policy를 개선하는 과정을 policy improvement라고 부름.
만약 새 greedy policy $\pi’$이 기존 $\pi$와 같은 수준이라면($v_\pi = v_{\pi’}$), greedy policy 정의로부터 모든 $s$에서
\[v_{\pi'}(s) = \max_a \sum_{s', r} p(s', r \mid s, a)\big[r + \gamma v_{\pi'}(s')\big]\]가 성립하는데, 이것은 정확히 Bellman optimality equation임.
$v_{\pi’} = v_*$이고 $\pi, \pi’$ 모두 optimal policy임.
improvement가 멈추는 것은 이미 optimal일 때뿐
Policy Iteration
policy evaluation과 policy improvement를 번갈아 수행하면, 단조 개선되는 policy/value의 연쇄가 만들어짐.
\[\pi_0 \xrightarrow{E} v_{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} v_{\pi_1} \xrightarrow{I} \pi_2 \xrightarrow{E} \cdots \xrightarrow{I} \pi_* \xrightarrow{E} v_*\]- $\xrightarrow{E}$ :evaluation
- $\xrightarrow{I}$ : improvement
- finite MDP는 policy가 유한 개뿐이므로 이 과정은 유한 횟수의 반복으로 optimal에 수렴함.
- 이것이 policy iteration
각 evaluation 단계가 이전 policy의 value function에서 시작.
policy가 바뀌어도 value가 거의 변하지 않으므로 evaluation 수렴이 크게 빨라짐.
Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1. 초기화
모든 s ∈ S에 대해 V(s) ∈ ℝ, π(s) ∈ A(s)를 임의로 설정
2. Policy Evaluation
loop:
Δ ← 0
for all s ∈ S:
v ← V(s)
V(s) ← Σ_{s',r} p(s',r|s,π(s))[r + γV(s')]
Δ ← max(Δ, |v − V(s)|)
until Δ < θ
3. Policy Improvement
policy-stable ← true
for all s ∈ S:
old-action ← π(s)
π(s) ← argmax_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]
if old-action ≠ π(s): policy-stable ← false
if policy-stable: V ≈ v*, π ≈ π* 반환
else: 2번으로
- 두 개 이상의 optimal policy 사이를 무한히 oscillate하지 않도록, improvement 단계에서 “값이 같으면 기존 행동을 유지”하는 식의 tie-breaking 보정이 필요함.
Value Iteration
policy iteration의 단점은 매 주기마다 policy evaluation을 끝까지 수행한다는 것.
evaluation 자체가 반복적 sweep이라 비쌈.
evaluation을 극한까지 가지 않고 중간에 멈춰도 greedy improvement를 했을 때 나오는 policy가 동일한 경우가 많음
- value가 $v_\pi$에 완전히 수렴하지 않아도, 이미 “이 상태에선 action A가 제일 낫다”는 판단은 충분히 내릴 수 있음
- 굳이 극한까지 evaluation을 완성할 필요가 없을 수도
극단적으로 evaluation을 단 한 번의 sweep(각 상태를 한 번씩 갱신)으로 truncate하고 곧바로 improvement와 결합하면 value iteration이 됨
- Policy iteration의 한 주기
- \[\underbrace{v_0 \to v_1 \to \cdots \to v_\pi}_{\text{evaluation (수렴까지)}} \to \underbrace{\pi' = \text{greedy}(v_\pi)}_{\text{improvement}} \to \text{반복}\]
- Value iteration은 evaluation을 딱 1번 sweep에서 잘라버려
- \[\underbrace{v_k \to v_{k+1}}_{\text{evaluation 1 sweep}} \to \underbrace{\text{greedy 적용}}_{\text{improvement}} \to \underbrace{v_{k+1} \to v_{k+2}}_{\text{evaluation 1 sweep}} \to \cdots\]
- policy improvement와 truncated policy evaluation을 하나의 간단한 갱신으로 합친 것
임의의 $v_0$에 대해 $v_$ 존재 조건과 동일한 조건 아래서 ${v_k}$는 $v_$로 수렴함.
value iteration을 이해하는 또 다른 방법은 Bellman optimality equation을 그냥 갱신 규칙으로 바꾼 것으로 보는 것임.
- policy evaluation 갱신과 비교하면 모든 행동에 대해 $\max$를 취하는 것만 다름.
- Evaluation의 $\sum_a \pi(a|s)$로 평균 내던 걸, improvement의 $\max_a$로 대체
- “1 sweep evaluation + greedy improvement”가 $\max_a$ 하나로 압축
Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
파라미터: 정확도 기준값 θ > 0
초기화: 모든 s ∈ S+에 대해 V(s)를 임의로, 단 V(종료) = 0
loop:
Δ ← 0
for all s ∈ S:
v ← V(s)
V(s) ← max_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]
Δ ← max(Δ, |v − V(s)|)
until Δ < θ
output (deterministic policy):
π(s) = argmax_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]
- value function의 변화가 아주 작아지면 iteration stop
일반적으로 truncated policy iteration은 evaluation sweep과 improvement sweep을 섞는 알고리즘들의 한 종류이고, value iteration은 그중 “evaluation을 한 번만” 하는 특수한 경우.
두 알고리즘 모두 할인된(discounted) finite MDP의 optimal policy로 수렴.
Asynchronous DP
지금까지의 DP는 매 반복마다 상태 집합 전체를 체계적으로 sweep함.
- 상태 공간이 매우 크면 한 번의 sweep도 부담임.
Asynchronous DP는 상태 집합을 체계적으로 sweep하지 않는 in-place 반복 DP.
- 상태 가치를 임의의 순서로 갱신하고, 갱신에 쓰이는 다른 상태의 값은 그 시점에 가용한 어떤 값이든 사용함.
- 한 상태가 한 번 갱신되는 동안 다른 상태는 여러 번 갱신될 수도 있음.
- $0 \leq \gamma \leq 1$ 일 때 모든 상태가 무한 번 발생하면 asymptotically converge (점근적 수렴)
이 유연성 덕분에 갱신할 상태를 자유롭게 고를 수 있음. 예를 들어 agent가 실제로 MDP를 경험하면서 방문하는 상태에만 갱신을 적용하면, agent의 행동과 가장 관련 있는 상태에 계산을 집중할 수 있음.
Generalized Policy Iteration (GPI)
policy iteration은 evaluation과 improvement라는 두 과정의 상호작용으로 구성됨 :
evaluation : value function이 현재 policy를 잘 따르도록 만듦
improvement: policy가 현재 value function에 대해 greedy해지도록 만듦
GPI는 두 과정의 세부 주기나 정밀도에 관계없이, 이 둘이 서로 상호작용하게 하는 일반 개념을 가리킴.
거의 모든 강화학습 방법이 GPI로 설명됨.
식별 가능한 policy와 value function이 있고, 다음 다이어그램처럼 서로를 끌어당김.
1
2
3
4
5
6
7
8
9
evaluation
V → v_π
π ───────────────→ V
↖ ↙
π → greedy(V)
improvement
(둘 다 안정 → 최적)
π_* ←──────────→ v_*
evaluation과 improvement는 두 과정이 서로 반대 방향으로 당김
- policy를 value에 대해 greedy하게 만들면 보통 value가 변경된 policy에 대해 부정확해지고,
- value를 policy에 맞추면 보통 policy가 더 이상 greedy하지 않게 됨.
- 하지만 장기적으로는 둘이 함께 하나의 공통 해 — optimal value function과 optimal policy — 로 수렴함.
두 과정이 모두 안정되면(더 이상 변화가 없으면) value와 policy가 반드시 optimal임.
policy가 자기 자신의 value function에 대해 greedy해지는 그 지점이 바로 Bellman optimality equation이 만족되는 지점.
DP의 효율성
상태 공간이 아주 크면 DP가 비실용적일 수 있지만, MDP를 푸는 다른 방법과 비교하면 DP는 실제로 꽤 효율적임.
DP가 optimal policy를 찾는 시간은 (최악으로 잡아도) 상태 수 $n$과 행동 수 $k$에 대한 다항 함수임.
deterministic policy의 전체 개수가 $k^n$임에도 DP는 다항 시간(polynomial time) 안에 optimal을 찾음.
- curse of dimensionality가 문제로 지적되기도 하지만, 오히려 큰 상태 공간에서는 direct search나 linear programming 같은 경쟁자보다 DP가 비교적 더 적합함.
- 실무에서 현대 컴퓨터로 수백만 개 상태를 갖는 MDP도 DP로 풀 수 있고, 특히 초기 value/policy가 좋을 때 최악 추정보다 훨씬 빨리 수렴함.
요약
이 장의 핵심을 정리하면 다음과 같음.
- Policy evaluation은 주어진 policy의 value function을 반복적으로 계산하는 것임.
- Policy improvement는 주어진 value function에 대해 greedy하게 더 나은 policy를 만드는 것임.
- 이 둘을 합치면 가장 널리 쓰이는 두 방법, policy iteration과 value iteration이 됨. MDP에 대한 완전한 정보가 있으면 이들로 finite MDP의 optimal policy와 optimal value function을 확실히 계산할 수 있음.
- 고전적 DP는 상태 집합 전체에 대한 sweep으로 expected update를 수행함. 각 expected update는 해당 상태에서 파생될 수 있는 모든 후속 상태의 가치와 그 확률을 고려함. 이것은 Bellman equation을 대입(assignment)으로 바꾼 것에 지나지 않음.
- 모든 DP/강화학습 방법을 GPI라는 관점으로 보면 통찰을 얻음. evaluation과 improvement라는 두 과정이 근사 policy와 근사 value를 중심으로 상호작용하고, 어느 과정으로도 변하지 않는 지점에 도달하면 그것이 optimal임.
- 반드시 전체 sweep을 할 필요는 없음. Asynchronous DP는 임의 순서로 상태를 갱신하는 in-place 반복으로, fine-grained 형태의 GPI로 볼 수 있음.
- DP의 특별한 성질 하나는 bootstrapping임. 즉 어떤 상태의 가치 추정값을 갱신할 때, 후속 상태의 가치 추정값을 기반으로 함(다른 추정값에 기대어 추정값을 갱신). 이후 강화학습 방법들은 완전한 모델 없이도/bootstrapping 없이도 같은 일을 할 수 있음