벨만 방정식

벨만 방정식

벨만 방정식은 결국 가치 함수를 재귀적으로 나타낸 것이다. 이 벨만 방정식에는 벨만 기대 방정식과 벨만 최적 방정식이 있는데, 이 둘을 살펴보고 이터레이션이 어떻게 일어나는지 알아보도록 하자.

 

벨만 기대 방정식

가치함수는 어떤 상태의 가치, 즉 에이전트가 그 상태로 갈 경우에 얻게 될 보상의 합에 대한 기댓값을 나타낸다. 이는 정책 π에 영향을 받으며 식으로는 vπ(s)=Eπ[Rt+1+γvπ(St+1)|St=s]로 나타낸다. 이와 같은 방정식을 벨만 기대 방정식(Bellman Expectation Equation)이라고 하며, 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 식으로 나타낸 것이다. 이는 가치함수 값의 지속적인 업데이트를 통해서 최종 보상의 기댓값을 계산한다.

 

기댓값에는 어떠한 행동을 수행할 확률인 정책 π(a|s)와 그 행동을 했을 때 도달할 상태의 확률을 나타내는 상태 변환 확률 Pass′이 포함되어 있다. 따라서 정책과 상태 변환 확률을 포함해서 계산을 수행하면 벨만 기대 방정식은 다음 식이 된다.

 

vπ(s)=Σa∈Aπ(a|s)(r(s,a)+γΣs′∈SPass′vπ(s′))

 

상태 변환 확률 Pass′은 환경의 일부를 이루는데, 환경을 만드는 사람이 직접 설정할 수 있다. 일반적으로 그리드월드에서는 왼쪽으로 가는 행동에 대한 상태 변환 확률을 1로 하여 다음 타임 스텝에 무조건 왼쪽 상태에 도달할 수 있도록 한다.

 

벨만 기대 방정식을 통해 업데이트되는 가치함수는 다음과 같은 과정을 거쳐 업데이트된다.

 

 

1. 각 행동에 대해 그 행동을 하게 될 확률을 고려 (π(a|s))
2. 각 행동을 했을 때 받을 보상과 그로 인해 도달하게 될 다음 상태의 가치함수를 고려 (vπ(s′))
3. 행동 확률 x (받게 될 보상 + 할인율 x 다음 상태의 가치함수) 계산
4. 모든 행동에 대해 위 식을 계산 후 합산하여 기댓값 계산 (Σa∈Aπ(a|s)(r(s,a)+γΣs′∈SPass′vπ(s′)))

 

 

벨만 최적 방정식

이처럼 벨만 기대 방정식을 이용해 현재의 가치함수를 계속 업데이트하여 현재의 정책을 따라갔을 경우 에이전트가 얻게 될 실제 보상의 대한 기댓값, 즉 참값을 얻게 된다.

 

의미 없는 무작위 값으로 초기화된 처음 시점의 가치함수의 값들은 벨만 기대 방정식을 통한 반복 업데이트가 이뤄지면서 좌항 vπ(s)와 우항 Eπ[Rt+1+γvπ(St+1|St=s)]이 동일해진다. 즉, vπ(s)가 수렴한다. 이 경우를 '현재 정책 π에 대한 참 가치함수를 구했다'라고 한다.

 

여기서 주의할 점은 참 가치함수와 최적 가치함수(Optimal Value Function)는 다르다는 점이다. 참 가치함수는 특정 정책을 따라 진행했을 경우 에이전트가 얻게 될 보상의 실제값이고, 이 중 가장 높은 보상을 얻는 정책에 대한 참 가치함수를 최적 가치함수라고 한다.

 

앞서 언급한 벨만 기대 방정식을 기댓값을 계산하기 위한 형태로 변환하면 다음과 같다.

 

vk+1(s)←Σa∈Aπ(a|s)(r(s,a)+γvk(s′))

 

위 수식에서 vk+1(s)는 상태 s에 대하여 현재 정책 π에 따라 k+1번째 계산한 가치함수를 의미한다. 이 가치함수는 k번째 가치함수 중 주변 상태 s'을 이용해서 수한다. 이 계산은 모든 상태에 대해 동시에 진행된다. 5*5 그리드월드에서는 25개의 상태에 대해 동시에 계산하게 되는 것이다.

 

위 수식의 계산은 상태집합에 속한 모든 상태에 대해 가능한 행동들을 고려하며 주변 상태에 저장되어 있는 가치함수를 통해 현재의 가치함수를 업데이트한다. 이를 통해 현재 정책에 대한 참 가치함수를 구할 수 있는데 이 과정을 거치면서 더 나은 정책을 찾아나가는 것이 강화학습의 핵심이다. 여기서 '더 나은 정책'이란 해당 정책을 따라갔을 때 얻게 될 보상의 합인 가치함수를 통해 판별할 수 있으므로 최적 정책을 따르는 최적 가치함수는 v∗(s)=maxπ[vπ(s)]로 나타낸다. 마찬가지로 최적 큐함수는 q∗(s,a)=maxπ[qπ(s,a)]로 나타낸다.

 

에이전트가 수행 행동을 선택하는 기준은 큐함수이며 최적 정책은 언제나 이 큐함수 중 가장 높은 행동을 수행하는 것이다. 따라서 최적 정책은 최적 큐함수 q∗만 안다면 다음과 같이 구할 수 있다.

 

π∗(s,a)=1 if a=argmaxa∈Aq∗(s,a), 0 otherwise

 

벨만 방정식은 현재 상태의 가치함수와 다음 타임스텝 상태의 가치함수 사이의 관계식이다. 현재 상태의 가치함수가 최적이라는 말은 에이전트가 가장 좋은 행동을 택한다는 의미이며, 이것의 기준은 큐함수가 된다. 이때 이 기준이 되는 큐함수가 최적이 아니라면 아무리 에이전트가 선택 가능한 큐함수 중 최대를 선택해도 그 가치함수는 최적 가치함수가 되지 못한다. 따라서 v∗(s)=maxa[q∗(s,a)|St=s,At=a]와 같이 최적의 큐함수 중 max를 취하는 것이 최적 가치함수가 된다.

 

위 수식에서 큐함수를 가치함수로 고쳐서 표현하면 다음과 같다.

 

v∗(s)=maxaE[Rt+1+γv∗(St+1)|St=s,At=a]

 

이를 벨만 최적 방정식(Bellman Optimality Equation)이라고 부른다. 여기서 기댓값을 나타내는 E가 있는 이유는, 다음 상태가 상태 변환 확률에 따라 달라지기 때문이다.

 

이처럼, 벨만 기대 방정식과 벨만 최적 방정식을 이용해 MDP로 정의되는 문제를 계산하는 것을 동적 프로그래밍(Dynamic programming)이라고 한다.

 

정리

MDP

순차적 행동 결정 문제를 수학적으로 정의한 것을 MDP라고 한다. MDP는 상태, 행동, 보상함수, 상태 변환 확률, 할인율로 구성되어 있으며 순차적 행동 결정 문제를 푸는 과정은 더 좋은 정책을 찾는 과정을 의미한다.

 

가치함수

에이전트가 어떤 정책이 더 좋은 정책인지를 판단하는 기준이 되는 함수로, 현재 상태로부터 정책을 따라갔을 때 받을 것이라 예상되는 보상의 합을 의미한다.

 

vπ(s)=Eπ[Rt+1+γvπ(St+1|St=s)]

 

에이전트는 정책을 업데이트할 때 가치함수 또는 큐함수를 사용하는데, 보통 가치함수보다는 에이전트가 선택할 각 행동의 가치를 직접적으로 나타내는 큐함수를 주로 사용한다. 큐함수의 정의는 다음과 같다.

 

qπ(s,a)=Eπ[Rt+1+γqπ(St+1,At+1)|St=s,At=a]

 

벨만 방정식

현재 상태의 가치함수와 다음 상태의 가치함수 사이 관계식을 의미한다. 벨만 기대 방정식은 특정 정책을 따라갔을 때 가치함수 사이의 관계식이며, 정의는 다음과 같다.

 

vπ(s)=Eπ[Rt+1+vπ(St+1|St=s)]

 

이를 계산 가능한 형태로 만들어 지속적인 업데이트를 통해 계산하다 보면 최적의 정책을 찾을 수 있다. 이때의 가치함수 사이의 관계식을 벨만 최적 방정식이라고 한다. 정의는 다음과 같다.

 

v∗(s)=maxaE[Rt+1+γv∗(St+1)|St=s,At=a]