확률적 동적 계획법과 마르코프 결정 과정: 스탠퍼드 AA203 9강의 벨만 재귀와 Q 함수 정리

핵심 메시지

• 외란이 있는 시스템에서는 비용 자체가 확률변수가 되므로, 기댓값을 취해 최적화 가능한 하나의 숫자로 바꾼 뒤 정책을 찾는다.
• 마르코프 가정은 외란의 확률분포가 과거 이력이 아니라 현재 상태와 현재 제어에만 의존하도록 제한해, 문제를 단계별로 쪼갤 수 있게 해 준다.
• 확률적 동적 계획법은 결정론적 버전과 형태가 같고, 각 단계에서 그 단계의 외란 하나에 대해서만 기댓값을 계산하면 된다는 점이 결정적인 계산 이점이다.
• 외란이 평균 0인 가우시안인 LQR에서는 최적 제어 법칙이 결정론적 해와 완전히 같고, 비용만 공분산에 비례하는 상수만큼 늘어난다.
• 강화학습으로 넘어가기 위해 무한 구간 MDP와 할인율을 도입하며, Q 함수는 전이 확률을 몰라도 최적 행동을 고를 수 있게 해 주는 재구성이다.

쉽게 이해하기

스탠퍼드 온라인이 공개한 AA203 '최적 제어와 학습 기반 제어' 9강에서 마르코 파보네 교수는 지금까지 다룬 결정론적 동적 계획법을 불확실성이 있는 세계로 확장한다. 상태 방정식에 외란 W가 추가되는데, 항공기를 제어한다면 돌풍이, 금융시장이라면 시장의 불확실성이 여기에 해당한다. 순서는 상태를 관측하고, 제어를 선택하고, 그 뒤에 자연이 외란 값을 결정하는 식으로 고정된다.

이 설정에서 핵심 제약은 외란의 확률분포가 현재 상태와 현재 제어에만 의존할 수 있고 과거 상태에는 의존할 수 없다는 점이다. 강의는 이를 '온건한 제약'이라고 부른다. 과거의 모든 정보가 현재 상태라는 하나의 값으로 매개되기 때문인데, 이 마르코프 가정을 포기하면 일반성은 늘지만 실제로 계산 가능한 알고리즘을 얻기 어려워진다. 문제를 얼마나 일반적으로 세울지와 얼마나 풀 수 있게 만들지 사이의 타협인 셈이다.

비용은 외란에 의존하므로 그 자체가 확률변수가 된다. 강의는 이를 기댓값으로 눌러 하나의 결정론적 수치로 바꾸는 위험 중립 정식화를 택한다. 평균만 보고 최악의 경우나 변동성은 따로 보지 않는 방식이며, 분산 항을 더하는 위험 민감 정식화도 있지만 그렇게 하면 최적성의 원리가 그대로 성립하지 않아 별도의 분석이 필요하다고 설명한다.

실제 계산은 창고 재고 관리 예제로 손으로 따라간다. 보관 용량이 2개뿐인 창고에서 수요가 각각 10퍼센트, 70퍼센트, 20퍼센트 확률로 0개, 1개, 2개 발생할 때 3단계 동안의 최적 구매 정책을 벨만 재귀로 뒤에서부터 풀어 나간다. 재고가 0인 상태에서는 1개를 사는 것이 최적으로 나오는데, 수요가 1개일 확률이 70퍼센트로 높다는 점을 생각하면 직관과도 맞는 결과다.

후반부는 강화학습으로 이어지는 다리를 놓는다. 유한 구간에서 무한 구간으로 넘어가면 문제가 정상성을 갖게 되어 최적 정책이 시점에 의존하지 않고, 벨만 방정식은 재귀식이 아니라 고정점 방정식이 된다. 이때 Q 함수를 도입하면 전이 확률을 모르는 상황에서도 최적 행동을 고를 수 있는데, 파보네 교수는 이 재구성이 학습 기반 알고리즘을 끌어내는 데 결정적이었다고 말한다.

주요 인사이트

• 벨만 재귀의 진짜 이점은 전체 외란 수열에 대한 기댓값을 각 단계의 외란 하나에 대한 기댓값으로 쪼개 준다는 데 있다. 강의는 이를 계산량의 극적인 감소라고 표현한다.
• 동적 계획법은 무차별 대입보다 크게 절약되지만 상태 차원이 늘어나면 계산량이 지수적으로 커진다. 상태 공간이 연속이면 모든 상태를 열거할 수 없으므로 이산화하거나 저차원 표현으로 사상한 뒤 수치 최적화를 해야 한다.
• 확률적 LQR에서 정책이 결정론적 해와 같아지는 이유는 외란이 평균 0이라 교차항의 기댓값이 사라지고, 남는 항이 제어와 무관한 상수이기 때문이다. 반대로 외란의 분산이 제어에 의존하면 이 성질은 깨진다.
• 제어이론, 컴퓨터과학, 운영과학은 같은 대상을 다른 기호로 부른다. 강의는 표기 차이 때문에 헷갈리지 말라며 스토캐스틱 최적화의 '로제타 스톤' 논문을 참고 자료로 든다.
• 최적 가치 함수를 안다고 해도 최적 행동을 뽑으려면 전이 확률이 필요하지만, Q 함수를 알면 그 자리에서 최댓값을 주는 행동만 고르면 된다. 모델을 모르는 학습 상황에서 Q 함수가 널리 쓰이는 이유가 여기에 있다.

자주 묻는 질문

관련 AI 소식