벨만 최적 방정식은 강화학습에서 중요한 개념으로, 주어진 상태에서 최적의 행동을 선택할 때의 기대 보상을 나타내는 방정식입니다. 이 방정식은 강화학습 에이전트가 환경에서 학습하면서 최적의 결정을 내리도록 도와줍니다. 벨만 최적 방정식은 최적의 정책을 찾는 데 필수적이며, 최적 상태 가치 함수 V∗(s)와 최적 행동 가치 함수 Q∗(s,a)를 정의하는 데 사용됩니다. 앞서 알아본 벨만 방정식은 어떠한 정책 π에 대해 성립하는 방정식이었습니다. 여기 벨만 최적 방정식에서는 최적 정책을 찾는게 목적이고 최적 정책이란 모든 상태 s에서의 상태가치 함수가 최대(max)인 정책입니다.
전회에서 도출해낸 상태가치함수 식에서의 벨만 방정식을 다시 불러오겠습니다. Vπ(s) = Eπ[Rt + γGt+1 | St = s] = Eπ[Rt|St=s] + γEπ[Gt+1|St=s] = Σa Σs'π(a|s)p(s'|s,a)r(s,a,s') + γΣa Σs'π(a|s)p(s'|s,a)Vπ(s') = Σa Σs'π(a|s)p(s'|s,a) * {r(s,a,s') + γVπ(s')} 여기서 정책은 π(a|s) 이 부분입니다. 이 정책을 최적 정책으로 변경하면 그것이 바로 상태가치함수에서의 벨만 최적 방정식이 될 것입니다. 그렇다면 위 벨만 방정식을 아래와 같이 변경할 수 있습니다. 여기서 V*(s)는 상태 s에서의 최적정책 가치함수를 의미합니다. 여기서 π*(a|s) 파이스타는 최적 정책을 의미합니다. V*(s) = Σa Σs'π*(a|s)p(s'|s,a) * {r(s,a,s') + γV*(s')} 이 식에서 최적정책 π*(a|s)에 의해 선택되는 행동 a가 최대가 되는 정책을 선택하면 됩니다. 위 식을 아래와 같이 변형할 수 있습니다. V*(s) = Σa π*(a|s)Σs'p(s'|s,a) * {r(s,a,s') + γV*(s')} 여기서 뒷부분인 Σs'p(s'|s,a) * {r(s,a,s') + γV*(s')} 의 행동 후보 5개가 있고 그 값이 -1,-5, 1, 6, 11 이렇게 5가지라고 할때, 값이 최대인 11을 나타내는 행동 a5 를 선택해야 합니다. 따라서 최대값인 11을 선택하고 이것이 그대로 v*(s)가 될수 있습니다. 이를 수식으로 다시 표현하자면, V*(s) = max a Σs'p(s'|s,a) * {r(s,a,s') + γV*(s')} 이렇게 나타낼 수 있습니다. 이 식에 상태가치함수에서의 벨만 최적방정식입니다.
이번에는 행동가치함수에서의 벨만 최적방정식을 도출하는 식을 알아볼 것인데, 먼저 행동가치함수에서의 벨만 방정식부터 다시 보도록 하겠습니다. 최적정책에서의 행동가치함수를 최적행동 가치함수라고 하고 여기서는 q*(큐스타)라고 명명하도록 하겠습니다. qπ(s,a) = Σs' p(s' | s,a){r(s,a,s') + γΣa'π(a'|s')qπ(s',a')} 이 행동가치함수 벨만방정식은 모든정책 π에 성립하므로, 최적정책 π*에도 적용됩니다. 그러면 아래와 같이 변경할 수 있습니다. q*(s,a) = Σs' p(s' | s,a){r(s,a,s') + γΣa'π*(a'|s')q*(s',a')} 여기서의 π*는 최적 정책으로 max연산자로 또 단순화 시킬수 있습니다. q*(s,a) = Σs' p(s' | s,a){r(s,a,s') + γmax a' q*(s',a')} 이 것이 Q함수에 대한 벨만 최적방정식이 됩니다.
3칸짜리 그리드월드 예제를 사용해 벨만 최적 방정식을 쉽게 설명해 보겠습니다. 이 그리드월드에서는 각 칸이 하나의 상태를 나타내고, 각 상태에서는 동쪽이나 서쪽으로 이동할 수 있는 행동을 선택할 수 있습니다. 목표는 마지막 칸에 도달해 큰 보상을 받는 것입니다. 상태 s1은 맨 왼쪽 칸, s2는 중간 칸, s3은 맨 우측 칸 각 칸을 이동하면 보상은 -1 주어진 칸을 벗어나면 -3의 보상 s3에 도착하면 +10의 보상이 주어진다고 환경을 설정합니다. 그리고 할인률(할인계수 γ는 0.9)도 설정합니다. 백업 다이아그램을 풀어서 설명하자면, s1인 상태에서 왼쪽으로 가면 범위를 벗어나게되어 -3 오른쪽(s2)으로 가면 -1의 보상과 0.9의 할인률 s2인 상태에서 왼쪽(s1)으로 가면 -1의 보상 오른쪽(s3)으로 가면 +10의 보상과 0.9의 할인률 여기서 벨만 최적방정식을 계산해 보겠습니다. v*(s1) = max{-3 + 0.9v*(s1), -1 + 0.9v*(s2)} v*(s2) = max{-1 + 0.9v*(s1), 10 + 0.9v*(s3)} v*(s3) = max{-1 + 0.9v*(s2), -3 + 0.9v*(s3)} 여기서 max{a,b} 연산자는 a와 b중 큰 값을 반환합니다. 이처럼 두개의 값중 큰 값을 반환한다는 것은 비선형 연산입니다. 위 3개의 식을 연립방정식으로 풀이하면 v*(s1), v*(s2), v*(s3)을 각각 구할 수 있습니다. 그 다음에는 최적정책을 구합니다. 위 식에서 최적 행동 가치함수 qπ(s,a)를 알고 있다고 가정하면 상태 s에서의 최적 행동은 다음과 같이 구할 수 있습니다. μ*(s) = argmax a q*(s,a) 여기서 argmax는 최댓값이 아니라 최댓값을 만들어내는 인수(여기서는 행동 a를 반환함)를 지정하는 함수입니다. 이 식과 같이 최적 행동 가치함수를 알고있는 경우, 함수의 값이 최대가 되는 행동을 선택하면 되고 그 행동을 선택하는 것이 최적정책 입니다. 이어서 다음의 식이 성립함을 보여줍니다. qπ(s,a) = Σs' p(s' | s,a){r(s,a,s') + γVπ(s')} 이 식의 qπ와 Vπ에서 정책의 첨자 π를 최적 정책인 첨자 *로 대체할 수 있고 이것을 식으로 표현하면 다음과 같습니다. μ*(s,a) = Σs' p(s' | s,a){r(s,a,s') + γV*(s')} 이와같이 최적상태 가치함수 V*(s)를 사용해 최적정책 μ*(s)를 얻을 수 있습니다. 이는 탐욕정책 greedy 인데 한정적인 후보중에서 최선을 찾는 것으로, 벨만 최적방정식에서는 현재상태 s와 다음상태 s'만 관련 있으며, 단순히 다음 상태만을 보고 가치가 가장 큰 행동을 하는 것입니다. 다시 정리하자면 위 연립방정식에서 최적 정책을 구하는 방법은 다음과 같습니다. 연립방정식을 전개합니다. v*(s1) = max{-3 + 0.9v*(s1), -1 + 0.9v*(s2)} v*(s2) = max{-1 + 0.9v*(s1), 10 + 0.9v*(s3)} v*(s3) = max{-1 + 0.9v*(s2), -3 + 0.9v*(s3)} 비선형 연립방정식을 풀게되면 v*(s1), v*(s2), v*(s3)의 각 값을 구할 수 있습니다. 그런 다음 μ*(s,a) = Σs' p(s' | s,a){r(s,a,s') + γV*(s')} 이 식을 통해 각각을 구하면 s1, s2, s3의 각 행동에 대한 값이 나오고 이 중에 큰 수를 나타내는 행동 a를 선택하게 됩니다. 이처럼 최적상태 가치함수를 알면 궁극적으로 최적정책을 구할 수 있게 됩니다.