벨만 방정식

벨만 기대 방정식

가치함수는 어떤 상태의 가치에 대한 기대를 나타냅니다.

어떤 상태의 가치함수는 에이전트가 그 상태로 갈 경우에 앞으로 받을 보상의 합에 대한 기댓값입니다.

가치함수는 현재 에이전트의 정책에 영향을 받는데, 이 정책을 반영한 식이 벨만 기대 방정식이라고 합니다.

vπ(s) = Eπ[R(t+1) + γvπ(S(t+1))|St=s]

벨만 기대 방정식이라고 하는 이유는 식에 기댓값의 개념이 들어가기 때문입니다.

이 벨만 방정식은 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 식으로 나타낸 것입니다.

벨만 방정식은 강화학습에서 상당히 중요한 부분을 차지합니다.

벨만 방정식이 강화 학습에서 왜 그렇게 중요한 위치를 차지하고 있는 것일까요?

앞에서 정의했던 가치함수의 정의를 다시 살펴 봅시다.

vπ(s) = Eπ[R(t+1) + γR(t+2) + γ^2R(t+3)+...|St=s]

기댓값을 알아내려면 앞으로 받을 모든 보상에 대해 고려해야 합니다.

정의상으로는 가능하지만 물리적으로는 불가능한 방법입니다.

다라서 컴퓨터가 이 기댓값을 계산하기 위해 다른 조치가 필요합니다.

많은 컴퓨터 계산에서 방정식을 풀 때 식 하나로 풀어내는 방법보다는 식 자체로는 풀리지 않지만 계속 계산을 하면서 푸는 방법을 사용합니다.

예를 들어, 1을 100번 더해야 하는 문제가 있다고 해봅시다.

1 + 1 + 1 + ... + 1 = 100

하지만 다른 방법으로 접근해볼 수도 있습니다. x라는 변수를 지정해 그 값에 1을 계속 더해나가는 방법입니다.

X = 0

for i in range(100):

X = X + 1

위와 같은 방식으로 계산한다면 위 식과 같은 결과를 얻을 수 있습니다.

벨만 방정식 또한 두번째 방식과 같습니다.

한 번에 모든 것을 계산하는 것이 아니라 값을 변수에 저장하고 루프를 도는 계산을 통해 참 값을 알아나가는 것입니다.

이러한 과정은 뒤에서 설명할 다이내믹 프로그래밍과도 관련이 있습니다.

벨만 기대 방정식을 다시 살펴 봅시다.

vπ(s) = Eπ[R(t+1) + γvπ(S(t+1))|St=s]

코드에서 = 연산자는 연산자를 기준으로 오른쪽 값을 왼쪽 변수에 대입하는 것입니다.

코드에서 처리할 때도 마찬가지 입니다.

원래 가지고 있던 vπ(s) 값을 Eπ[R(t+1) + γvπ(S(t+1))|St=s]로 대체하는 것입니다.

즉, 현재 가치함수 값을 업데이트하는 것입니다.

하지만 업데이트하려면 기댓값을 계산해야 하는데 기댓값을 어떻게 계산할 수 있을 까요?

기댓값에는 어떠한 행동을 할 확률(정책 π(a|s))과 그 행동을 했을 때 어떤 상태로 가게 되는 확률(상태 변환 확률 P(a,ss'))이 포함돼 있습니다.

따라서 정책과 상태 변환 확률을 포함해서 계산하면 됩니다.

기댓값의 계산이 가능한 형태로 벨만 기대 방정식을 나타내면

vπ(s) = Σ(a∈A)π(a|s)(R(t+1)+γΣ(s'∈S)P(a,ss')vπ(s'))

상태 변환 확률을 모든 s와 a에 대해 1이라고 가정해봅시다. 즉, 왼쪽으로 행동을 취하면 왼쪽에 있는 상태로 무조건 가게 되는 환경으로 설정 합니다.

	V=0
V=1	A	V=0
	V=0.5	-> 1

 

A라고 적혀 있는 곳이 현재 에이전트가 있는 상태입니다.

현재 상태의 가치함수를 0이라고 할 때 벨만 기대 방정식을 통해 가치함수는 얼마로 업데이트될까요?

행동은 그림에서 볼수 있듯이 "상, 하, 좌, 우"로 네 개가 있습니다. 

에이전트의 초기 정책은 무작위로 행동하는 것으로서 각 행동은 25%의 확률로 선택됩니다.

또한, 현재 에이전트의 상태에 저장된 가치함수는 0, 왼쪽 상태의 가치함수는 1, 밑의 상태의 가치함수는 0.5, 위의 상태의 가치함수는 0, 오른쪽 상태의 가치함수는 0입니다. 

그리고 오른쪽으로 행동을 취할 경우 1의 보상을 받습니다. 감가율은 0.9 입니다

상태 변환 확률이 항상 1이라고 가정했으므로 다음과 같이 수식이 변형됩니다.

vπ(s) = Σ(a∈A)π(a|s)(R(t+1)+γΣ(s'∈S)vπ(s'))

이 식을 말로 표현하면 다음과 같이 말할 수 있습니다.

(1) 각 행동에 대해 그 행동을 할 확률을 고려하고

(2) 각 행동을 했을 대 받을 보상과

(3) 다음 상태의 가치함수를 고려합니다.

1	행동 = 상     0.25 X (0+0.9X0) = 0
2	행동 = 하     0.25 X (0+0.9X0.5) = 0.1125
3	행동 = 좌     0.25 X (0+0.9X1) = 0.225
4	행동 = 우     0.25 X (1+0.9X0) = 0.25
총합	기댓값 = 0+0.1125+0.225+0.25 = 0.5875

벨만 기대 방정식을 이용해 현재의 가치함수를 계속 업데이트하다 보면 참값을 구할 수 있습니다.

참값이라는 것은 최대로 받을 보상을 이야하는 것이 아닙니다.

현재의 정책을 따라갔을 경우에 에이전트가 얻을 실제 보상의 값에 대한 참 기댓값입니다.

벨만 최적 방정식

벨만 기대 방정식을 통해 계속 계산을 진행하다 보면 언제가 식의 왼쪽 항과 오른쪽항이 동일해집니다.

vπ(s) = Eπ[R(t+1) + γvπ(S(t+1))|St=s]

처음에 가치함수의 값들은 의미가 없는 값으로 초기화됩니다.

초깃값으로부터 시작해서 벨만 기대 방정식으로 반복적으로 계산한다고 가정해봅시다.

이 계산을 반복하다 보면 방정식의 왼쪽 식과 오른쪽 식이 같아집니다.(무한히 반복한다는 가정하에)

즉, vπ(s) 값이 수렴하는 것입니다. 그렇다면 현재 정책 π에 대한 참 가치함수를 구한 것입니다.

참 가치함수와 최적 가치함수는 다릅니다.

참 가치함수는 "어떤 정책"을 따라서 움직였을 경우에 받게 되는 보상에 대한 참값입니다.

가치함수의 정의가 현재로부터 미래까지 받을 보상의 총합인데 이 값이 얼마가 될지에 대한 값입니다.

하지만 최적의 가치함수는 수많은 정책 중에서 가장 높은 보상을 주는 가치함수 입니다.

기댓값을 계산하기 위한 형태인 수식으로 변환 해봅시다.

v(k+1) = Σ(a∈A)π(a|s)(R(a,s)+γvk(s'))

위 식의 계산은 상태집합에 속한 모든 상태에 대해 가능한 행동들을 고려합니다.

주변 상태에 저장돼 있는 가치함수를 통해 현재의 가치함수를 업데이트 합니다.

현재 정책에 대한 참 가치함수를 구할 수 있습니다.

하지만 단순히 현재 에이전트의 정책에 대한 가치함수를 구하고 싶은게 아니라 최적 정책을 찾는 것이라면 어떻게 할 수 있을까요?

강화학습은 결국은 MDP로 정의되는 문제에서 최적 정책을 찾는 것이라고 할 수 있습니다.

단순히 현 정책에 대한 가치함수를 찾는 것이 아니라 더 좋은 정책으로 현재의 정책을 업데이트해 나가야 할 것입니다.

더 좋은 정책이라는 것의 정의는 무엇일 까요?

어떤 정책이 더 좋은 정책이라고 할 수 있을까요?

이는 정책을 따라갔을 때 받을 보상들의 합인 가치함수를 통해 판단할 수 있습니다.

가치함수가 결국 정책이 얼마나 좋은지를 말해주는 것입니다.

따라서 다음 식과 같이 모든 정책에 대해 가장 큰 가치함수를 주는 정책이 최적 정책입니다.

v*(s) = max(π)[vπ(s)]

max라는 함수는 모든 가능한 정책에 따른 vπ(s) 값 중에서 최대를 반환하는 함수입니다.

최적 정책을 따라갓을 때 받을 보상의 합이 최적 가치함수입니다.

최적 큐함수 또한 같은 방식으로 수식을 구할 수 있습니다.

q*(s,a)=max(π)[qπ(s,a)]

가장 높은 가치함수를 에이전트가 찾았다고 가정해 봅시다.

이 때 최적 정책은 각 상태 s에서의 최적의 큐함수 중에서 가장 큰 큐함수를 가진 행동을 하는 것입니다.

즉, 선택 상황에서 판단 기준은 큐함수이며, 최적 정책은 언제나 이 큐함수 중에서 가장 높은 행동 하나를 하는 것입니다.

다라서 최적 정책은 최적 큐함수 q*만 안다면 다음과 같이 수식을 구할 수 있습니다.

argmax는 q*를 최대로 해주는 행동 a를 반환하는 함수 입니다.

π*(s,a) = 1, if a = argmax(a∈A)q*(s,a)

            0, otherwise

그렇다면 최적 가치함수 혹은 큐함수는 어떻게 구할 수 있을까요?

그것을 구하는 것이 순차적 행동 결정 문제를 푸는 것입니다.

여기서는 최적의 가치함수끼리의 관계가 어떻게 되는지를 살펴보겠습니다.

벨만 방정식은 현재 상태의 가치함수와 다음 타임스텝 상태의 가치함수 사이의 관계식입니다.

현재 상태의 가치함수가 최적이라고 가정해봅시다. 현재 상태의 가치함수가 최적이라는 것은 에이전트가 가장 좋은 행동을 선택한다는 것입니다.

에이전트는 무엇을 기준으로 어떤 행동이 가장 좋은지를 알까요?

앞에서 말한 큐함수 입니다.

이때 선택의 기준이 되는 큐함수가 최적의 큐함수가 아니라면 아무리 에이전트가 큐함수 중에 최대를 선택해도 가치함수는 최적의 가치함수가 되지 않습니다.

따라서 최적의 큐함수 중에서 max를 취하는 것이 최적의 가치함수가 됩니다.

v*(s) = max(a)[q*(s,a)|St=s,At=a]

큐함수를 가치함수로 고쳐서 표현하면

v*(s) = max(a)E[R(t+1)+γv*(S(t+1))|St=s,At=a]

이를 벨만 최적 방정식이라 부르며, 이 식은 가치함수에 대한 것입니다.

큐함수에 대해서도 벨만 최적 방정식을 표현할 수 있는데, 다음과 같이 표현합니다.

q*(s,a) = E[R(t+1)+γmax(a')q*(S(t+1),a')|St=a, At=a]

최적 정책을 따라갈 때 현재 상태의 큐함수는 다음 상태에 선택 가능한 행동 중에서 가장 높은 값의 큐함수를 1번 감가하고 보상을 더한 것과 같습니다.

E가 있는 이유는 큐함수 자체가 행동까지 선택한 상황이라 그에 따라 받는 보상은 에이전트가 선택하는 것이 아니고 환경이 주는 값이기 때문입니다.

벨만 기대 방정식과 벨만 최적 방정식을 이용해 MDP로 정의되는 문제를 "계산"으로 푸는 방법이 다이내믹 프로그래밍 입니다.