벨만 방정식과 동적 계획법, 일반화 정책 반복까지: 강화학습 기초 이론 한 번에 정리

핵심 메시지

• 벨만 방정식은 한 상태의 가치를 한 걸음 떨어진 상태들의 가치로 표현한다. 상태값들이 그물처럼 엮이기 때문에 일부를 풀면 나머지도 풀린다.
• 최적성 버전은 구조가 거의 같고, 상태값이 행동값들의 최댓값이라는 조건 하나만 바뀐다. 에이전트가 항상 최고 행동값을 골라야 한다는 뜻이다.
• 동적 계획법은 환경의 동역학을 완벽히 안다고 가정할 때 최적 정책을 찾는 방법이다. 강력하지만 현실에서는 성립하기 어려운 가정이다.
• 정책 평가는 벨만 방정식을 대입식으로 바꿔 값이 안정될 때까지 반복하는 일이고, 정책 개선은 그 가치함수에 대해 탐욕적으로 행동하는 새 정책을 만드는 일이다.
• 두 과정이 서로 경쟁하며 협력하는 일반화 정책 반복(GPI)이라는 틀 하나로 거의 모든 강화학습 방법을 설명할 수 있다.

쉽게 이해하기

강의는 유한 마르코프 결정 과정(MDP) 복습에서 출발한다. 에이전트가 행동을 내보내면 환경이 보상과 다음 상태를 돌려주고, 이 과정이 종료 상태에 닿을 때까지 반복된다. 목표는 여러 궤적에 걸쳐 평균한 할인 누적 보상을 크게 만드는 정책을 찾는 것이고, 이를 위해 상태 가치함수와 행동 가치함수를 도입한다.

벨만 방정식은 이 가치들을 서로 잇는다. 강의는 다섯 개 상태로 된 작은 예시를 들어, 어떤 상태에서 좌우 행동의 확률과 다음 상태·보상 분포, 그리고 이웃 상태들의 값을 알면 현재 상태의 값을 계산할 수 있음을 보인다. 유도 과정은 전확률 법칙과 누적 보상의 재귀 관계를 쓰는 것이 전부이고, 강의자 스스로 대수 계산이라 조금 지루하지만 알아야 하는 부분이라고 말한다.

최적성 방정식은 여기에 한 가지만 더한다. 왼쪽으로 가면 평균 19.1, 오른쪽으로 가면 21.3을 얻는다고 할 때 최적 정책이라면 당연히 오른쪽을 고를 것이고, 따라서 그 상태의 최적 가치는 21.3이 된다. 최고 행동값을 항상 고른다는 이 조건이 벨만 최적성의 핵심이며, 최댓값을 내는 행동이 여럿이면 최적 정책도 여럿이라는 뜻이 된다.

정책 평가는 이 방정식을 계산 절차로 바꾼 것이다. 종료 상태만 0으로 두고 나머지 상태값을 아무렇게나 초기화한 뒤 각 상태값을 벨만 방정식이 시키는 대로 다시 대입하며, 전체 상태를 한 번 훑는 스윕을 값이 거의 변하지 않을 때까지 반복하면 참값으로 수렴한다. 반대편 절반인 정책 개선은 주어진 가치함수에 대해 각 상태에서 행동값이 가장 큰 행동만 고르는 새 정책을 만드는 일이고, 정책 개선 정리에 의해 이 정책은 원래 정책보다 나쁘지 않다. 더 흥미로운 것은 그 역으로, 정책이 자기 가치함수에 대해 이미 탐욕적이어서 고칠 것이 없다면 그 정책은 이미 최적이다.

두 절차를 번갈아 돌리는 것이 정책 반복이고, 이를 일반화한 것이 GPI다. 강의는 정책 평가를 끝까지 수렴시키지 않고 스윕 한 번만 하고 개선으로 넘어가도 최적에 도달한다는 점(가치 반복)을 들어 그 일반성을 보이며, 자본 1~99달러에서 앞면 확률 40%인 동전에 베팅해 100달러에 먼저 닿아야 하는 도박꾼 문제에서 사람이 직관으로 짜기 어려운 모양의 최적 정책이 그냥 나오는 과정을 보여 준다. 다만 여기까지 오려면 환경 동역학을 완전히 알아야 했고 상태 공간도 너무 크면 안 된다는 한계가 분명하다. 다음 주제로는 이 가정을 푸는 첫걸음인 몬테카를로 방법이 예고된다.

주요 인사이트

• 벨만 방정식의 값어치는 계산식 하나가 아니라 '연결'에 있다. 미지수마다 방정식이 하나씩 대응하므로, 가치함수를 구하는 일이 연립방정식을 푸는 일로 바뀐다.
• 강의가 제시한 격자 정리법(행에는 상태값·행동값, 열에는 대입 대상)은 벨만 방정식 두 개가 왜 그런 모양인지를 한눈에 보여 준다. 식을 외우는 대신 어디에 무엇을 대입했는지로 기억할 수 있다.
• 정책 평가를 끝까지 수렴시키지 않아도 된다는 사실은 실무적으로 크다. 각 과정이 제 몫을 조금씩만 해도 결국 최적에 도달하기 때문에, 알고리즘 설계자는 두 과정의 세밀함을 자유롭게 조절할 수 있다.
• 도박꾼 문제처럼 최적 전략이 직관에 반하는 문제에서 동적 계획법의 가치가 드러난다. 문제마다 영리한 분석을 새로 하는 대신, 일반 알고리즘 하나가 그 문제가 요구하는 전략을 내놓는다.
• 완전한 환경 지식이라는 가정은 비현실적이지만, 그렇다고 이 이론이 학술적 장식은 아니다. 이후의 모든 방법이 이 가정을 하나씩 걷어내는 방식으로 전개되므로, 무엇이 빠졌는지를 아는 것이 곧 이해의 지도가 된다.

자주 묻는 질문

관련 AI 소식