동적계획법·Bellman·값과 정책

당장 싼 행동이 장기적으로도 쌀까

작업을 시도하는 두 방법을 생각해 봅시다. 하나는 비용이 싸지만 같은 상태로 돌아올 수 있고, 다른 하나는 비싸지만 확실하게 다음 상태로 진행합니다. 지금 지불하는 비용만 보면 싼 방법이 좋아 보입니다. 그러나 재시도가 반복되면 미래 비용이 더 커질 수 있습니다. 동적계획법은 가능한 모든 과거 경로를 늘어놓는 대신, 현재 상태에서 남은 비용을 재귀적으로 평가합니다.

먼저 미래 예측에 충분한 상태를 정의해야 합니다. Markov 의사결정 과정에서는 현재 상태와 행동이 다음 상태의 조건부 확률과 즉시 비용을 정합니다. 과거에 숨은 정보가 더 필요하다면 모형이 불완전한 것이며 Bellman 갱신만으로 해결되지 않습니다. 부분 관측의 belief state는 뒤의 단원에서 다룹니다.

작은 모형의 모든 조건을 읽는다

의사결정 상태 S0,S1,S2와 종단 상태 S3를 사용합니다. 상태 s에서 행동 0을 택하면 즉시 비용 c0(s)를 지불하고, 확률 p로 같은 상태에 남거나 확률 1-p로 다음 상태 s+1로 갑니다. 세 상태의 비용은 각각 1,2,4입니다. 행동 1은 사용자가 지정한 비용 c를 지불하고 반드시 다음 상태로 갑니다. 종단 S3에서는 이후 비용과 값이 모두 0입니다.

확률은 알려져 있으며 표본으로 추정하지 않습니다. 도식은 선택한 한 상태의 행동과 결과만 보여줍니다. 확률 0이라고 표시한 화살표는 실제로 발생하는 경로가 아닙니다. 굵은 행동 테두리는 현재 값으로 선택한 greedy 행동이며, 표본 경로가 실제로 그쪽으로 움직였다는 표시도 아닙니다.

정책의 목적은 다음 기대 할인 비용을 최소화하는 것입니다.

비용을 먼저 지불한 뒤 전이합니다. 정책은 상태를 보고 행동을 고르는 규칙이며 하나의 고정된 행동 수열과 다릅니다. 할인은 같은 상태로 영원히 돌아오더라도 유계인 단계 비용의 합을 유한하게 만들 수 있습니다. 그러나 목적 자체도 바뀝니다. 할인 비용의 최적성이 비할인 비용 최소화나 종단 도달을 자동으로 뜻하지 않습니다.

조건부 기대값에서 Bellman 갱신을 얻는다

미래 값 벡터 V가 주어지면 각 행동의 비용을 계산합니다.

기대값은 가장 가능성이 높은 다음 상태 하나를 고르는 것이 아니라 다음 상태들의 값을 확률로 가중 평균합니다. 행동을 고르는 시점에는 무작위 결과를 아직 알지 못합니다. 따라서 결과별로 가장 싼 행동을 먼저 고른 뒤 평균하는 것으로 바꾸면 의사결정자에게 없는 정보를 준 셈이 됩니다.

최적성 원리는 전이 이후 도착한 충분한 상태에서 최적의 나머지 결정을 계속할 수 있다는 뜻입니다. 가산적인 비용과 Markov 상태가 이 재귀를 가능하게 합니다. 유한 할인 MDP에는 최적의 결정론적 정상 정책이 존재하므로, 모든 정상 정책을 평가하는 다른 경로로도 답을 구할 수 있습니다.

동시 값 반복의 시계를 명시한다

비종단 상태의 V0를 사용자가 정한 값으로, 종단 값은 0으로 놓습니다. V_(k+1)=T(V_k)를 적용할 때 모든 새 성분은 같은 이전 벡터를 읽습니다. 하나를 갱신한 뒤 바로 다른 상태 계산에 사용하는 제자리 갱신과는 일정이 다릅니다.

파란 그래프는 실제 N번 갱신한 V_N입니다. N=0에서는 초기 추측을 그대로 표시합니다. V0=0이면 V_N은 N단계만 평가하고 끝의 비용을 0으로 두는 유한 시간 최적값입니다. V0가 일반적인 벡터이면 끝에 gamma^NV0(S_N)을 더하는 종단 평가가 포함됩니다. 둘 다 곧바로 무한 시간 최적값 V라는 뜻은 아닙니다.

비용이 음수가 아니고 V0=0이면 반복값은 최적값을 향해 증가합니다. 그러나 임의의 초기 추측은 단조롭게 움직일 필요가 없습니다. 두 번째 예제의 초기 수준을 8로 바꾸면 최적 V*(S0)는 약 7.023077인데도 첫 갱신 V1(S0)=8.2로 오히려 증가합니다. 수렴은 수축성의 결론이며 매 상태에서 매번 같은 방향으로 개선된다는 약속은 아닙니다.

행동 readout은 Q_(V_N)에서 구한 greedy(V_N)입니다. 이미 N번 갱신한 값으로 한 단계를 더 내다보므로 V_N 자체와 시간 범위가 다릅니다. 이 greedy 규칙을 고정해 무한히 실행하는 정책의 값도 별개의 양입니다. 실습은 그 정책 비용을 따로 계산하며 현재 반복값을 정책 비용으로 바꾸어 부르지 않습니다.

여덟 개의 정상 정책을 별도로 평가한다

세 의사결정 상태에서 각각 두 행동을 고를 수 있으므로 결정론적 정상 정책은 여덟 개입니다. 정책을 고정하면 Bellman 식은 선형입니다.

V(S3)=0에서 거꾸로 대입하면 각 정책의 값을 얻습니다. 정한 범위에서는 분모가 양수입니다. 주황 V*는 여덟 벡터의 상태별 최소값입니다. 유한 할인 MDP의 최적 정상 정책은 이 최소값들을 동시에 달성하며, 실습은 그 벡터의 greedy 정책을 평가해 같은 값을 복원하는지도 확인합니다.

값 반복을 충분히 많이 했다는 이유만으로 그것을 정답으로 삼지 않습니다. 테스트에서는 별도로 전체 정책 선형계를 풀고 할인된 전이 분포의 합도 계산해 정책 평가기를 검산합니다. 부동소수점 Q가 정확히 같으면 행동 0을 택합니다. 동률에 아주 가까운 작은 수치 차이를 실질적으로 큰 행동 우위라고 해석하지 마세요.

할인율이 값 오차의 인증을 가능하게 한다

확률 행의 합이 1이면 가중 평균은 최대 성분 차이를 늘리지 않습니다. 행동별 최소값을 취하는 연산도 최대 차이보다 결과를 더 벌리지 않습니다. 따라서

입니다. 이 수축성은 유일한 고정점과 반복의 수렴을 설명합니다. Bellman residual을 r=||TV-V||inf로 정의하고 TV를 더하고 빼면

를 얻습니다. 화면은 실제 최대 값 오차와 residual 인증을 따로 표시합니다. gamma가 1에 가까우면 경계가 느슨해질 수 있습니다. 이 식은 현재 값 벡터의 오차를 제한하며 greedy 정책 손실을 바로 제한하는 같은 식은 아닙니다. 정책 손실은 그 정책을 별도로 평가한 값과 V*의 최대 차이로 계산합니다. gamma=1에서는 이 일반적인 수축 논증과 분모를 쓸 수 없으므로 실습 범위에서 제외합니다.

손계산 문제와 해설

gamma=0.5,p=0.5,c=3,V0=0으로 놓습니다. 첫 갱신은 V1=(1,2,3,0)입니다. S2에서는 행동 1의 비용 3이 행동 0의 4보다 작습니다. V2(S1)을 구하려면 행동 0의 2+0.5*(0.52+0.53)=3.25와 행동 1의 3+0.5*3=4.5를 비교합니다. 따라서 V2(S1)=3.25입니다. 모든 상태에서 같은 이전 벡터를 사용하면 V2=(1.75,3.25,3,0)을 얻습니다.

해설 검산. 무한 시간 최적값은 V*(S2)=3, V*(S1)=(2+0.253)/0.75=11/3, V(S0)=(1+0.25*(11/3))/0.75=23/9입니다. 두 번 갱신한 값은 아직 이 답에 도달하지 않았지만, 그때의 greedy 정상 정책은 이미 최적 정책과 같습니다. 값 오차가 남았는데 정책 손실은 0일 수 있다는 구체적인 예입니다.

다음으로 gamma=0.9,p=0.75,c=3을 사용하세요. S1에서 신뢰할 수 있는 행동 1의 최적 비용은 3+0.93=5.7입니다. 그 상태에서 행동 0만 계속 선택하면 (2+0.90.253)/(1-0.90.75), 약 8.230769의 비용이 듭니다. 즉시 비용은 행동 0을 지지하지만 반복해서 돌아올 미래를 고려하면 행동 1이 유리합니다. 반복 표와 현재 Q를 보며 greedy 선택이 언제 바뀌는지 확인하세요.

AI 학습과 계획으로의 연결

이 실습은 알려진 모형의 정확한 기대값으로 계획합니다. 표본 전이에서 배우는 TD 학습이나 Q-learning을 구현한 것은 아닙니다. 그런 방법은 관련 조건부 기대를 데이터로 근사하며 탐색·추정·최적화 문제를 추가합니다. 일부 표본 상태에서 측정한 residual만으로는 여기의 전체 상태 공간 오차를 바로 인증할 수 없습니다. 큰 학습 시스템으로 옮길 때에도 상태 표현, 목적, 전이 support와 오차 보장의 적용 범위를 명확히 유지해야 합니다.

원전과 읽을거리

Russ Tedrake의 Dynamic Programming, 특히 할인 비용과 유한 MDP 절은 넓은 계획 배경을 제공합니다. 이 교재의 작은 chain, 여덟 정책 비교기, 예제, 수축 논증과 도식은 직접 구성했습니다.