Bellman Equation(벨만 방정식)이란?

http://www.yes24.com/Product/Goods/92337949

바닥부터 배우는 강화 학습 - YES24

https://dana-study-log.tistory.com/18

※본 내용은 위의 자료들을 참고하여 작성하였습니다.

 

 

 

벨만 방정식은 시점 t에서의 밸류와 시점 t+1에서의 밸류 사이의 관계를 다루며, 가치 함수와 정책 함수 사이의 관계도 다루고 있습니다. 여러 강화학습 알고리즘의 근간이 되는 만큼 중요한 개념입니다. 먼저 벨만 기대 방정식과 벨만 최적 방정식을 0단계부터 2단계까지 한눈에 볼 수 있게 표기해보겠습니다.

벨만 기대 방정식(좌), 벨만 최적 방정식(우)

 

실제로 벨만 방정식이 0단계, 1단계, 2단계 이렇게 명시적으로 나뉘지는 않습니다. 다만, 0단계에만 기댓값이 있으며, 이와 다르게 1, 2단계는 𝜋(𝑎|𝑠)와 전이 확률이라는 확률 변수가 포함되어 있다는 점입니다. MDP를 안다고 가정할 때 2단계 수식을 사용하는 것이 정확하겠지만 실제로 대부분 환경에서는 MDP를 알 수 있는 경우가 없기 때문에 0단계 수식이 주로 사용됩니다.

벨만 기대 방정식 (Bellman Expectation Equation)

벨만 기대 방정식은 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 식으로 나타낸 것입니다. 벨만 기대 방정식은 가치함수식에서 유도된 것인데 과정은 다음과 같습니다.

상태 가치 함수의 정의는 리턴의 기댓값입니다. Gt를 전개 한 다음, 먼저 한 스텝만큼 진행하여 보상을 받고, 그 다음 상태인 st+1부터 미래에 받을 보상을 더해줘도 똑같지 않겠냐는 것입니다.

 

우선, 가치함수의 정의에서 반환값 Gt를 풀어서 표기한 것이 두 번째 줄의 수식입니다.

두 번째 수식에서 반환값 부분의 두 번째 항부터 감가율(γ)로 묶어준 것이 세 번째 수식입니다.

세 번째 수식에서 묶어준 부분이 다음 상태의 반환값을 의미하므로 Gt+1라고 표기할 수 있습니다.

네 번째 수식에서 Gt+1 또한 확률 변수로 정해져 있는 특정값이 아니기 때문에 기댓값 개념을 추가할 수 있습니다. 

 

행동 가치 함수도 위와 같이 유도됩니다.

다음은 1단계입니다.

상태 가치 함수 수식은 다음과 같습니다.

위와 같이 정의할 수 있는 이유는 행동 가치 함수 역시 리턴의 기댓값이기 때문에 a를 실행할 확률을 안다면, 상태 가치 함수로 나타낼 수 있습니다. 위 식을 이해하기 위해서 다음과 같이 가정해보겠습니다.

s의 상태 가치 함수는 a1을 취한 이후에 받는 반환값들과 a2를 취한 이후에 받는 반환값들을 모두 고려해서 기댓값을 구한 것입니다. 행동 가치 함수에 대해 생각해보면, 상태 s에서의 행동 가치함수는 2가지가 나올 것입니다. 하나의 액션 밸류는 행동 a1을 취한 이후에 받는 반환값들에 대해서만 기댓값을 구한 것이고, 다른 액션 밸류는 행동 a2를 취한 이후에 받는 반환값들에 대해서만 기댓값을 구한 것입니다. 각 행동을 했을 때의 액션 밸류에 그 행동이 일어날 확률을 곱해서 모든 행동에 대해 그 값을 더해주면 상태 가치 함수가 되는 것입니다.

 

정책 𝜋가 두 액션을 선택할 확률은 각각 60%, 40%입니다. 또한 a1과 a2의 액션 밸류는 각각 1, 2입니다. 정책과 각각의 액션 밸류를 알고있기 때문에 위의 수식을 계산할 수 있습니다.

또한, 상태의 밸류를 안다면 액션 밸류 함수를 정의할 수 있습니다.

이번에는 다음과 같이 가정해보겠습니다.

먼저, 0단계와 비교해 살펴보면 전이 확률을 알고 있고, a를 선택한다고 가정하고 시작하기 때문에 확률 변수가 제거되어 기댓값을 없앨 수 있습니다. 전이 확률이 1이 아니라면 행동에서 다음 상태로 뻗어나가는 가지가 여러 개가 될 수 있습니다. 왜냐하면 무조건 정해진 다음 상태가 나타나는 deterministic한 환경이 아니라면 외부적인 요인에 의해 다른 상태로 갈 수 있기 때문입니다. 이와 같은 이유로 원래의 보상 함수는 상태에 대한 보상 함수지만, 행동을 정했기때문에 그 행동에 대해 즉시 얻는 보상으로 대체할 수 있습니다. 따라서 행동 가치 함수는 특정 행동을 한 뒤 즉시 받는 보상에 행동을 통해 각 다음 상태로 갈 확률 곱하기 다음 상태 밸류를 더한 것(한 스텝 지나서 감가율 적용)으로 표현할 수 있습니다.

따라서 위의 경우 다음과 같이 계산할 수 있습니다.

다음은 2단계입니다.

앞의 내용을 잘 이해했다면 2단계는 대입만 하면 끝입니다.

 

0단계와 2단계를 비교해보겠습니다.

0단계 식은 현재 상태의 밸류와 다음 상태의 밸류를 기댓값 연산자를 통해 연결해 놓은 식입니다.

2단계 수식도 결국 현재 상태의 밸류와 다음 상태의 밸류 사이 연결 고리를 나타내며, 0단계에 있는 기댓값 연산자를 모두 확률과 밸류의 곱 형태로 풀어서 쓴 형태입니다. 하지만 2단계 수식을 계산하기 위해서는 다음 2가지를 반드시 알아야 합니다.

2가지 강화학습 접근법

• 보상함수와 전이확률을 알 때 (“MDP를 안다”고 표현)
  • Model-Based(모델 기반) or Planning(플래닝) 접근법: 실제로 경험해 보지 않고 머릿속에서 시뮬레이션 해보는 것만으로도 강화학습을 할 수 있습니다.
  • 2단계 벨만 기대 방정식 이용.
• 보상함수와 전이확률을 모를 때 (즉, MDP를 모를 때)
  • Model-Free 접근법: 그 상태에서 실제로 액션을 해보고 경험(Experience)을 통해 학습하게 됩니다.
  • 0단계 벨만 기대 방정식 이용.

보상 함수와 전이 확률은 환경의 일부입니다. 이 2가지를 알 때 MDP를 안다고 표현합니다.

실제 문제의 상황에서는 이에 대한 정보를 알 때도 있지만 모르는 상황이 더 많습니다. 그래서 우리는 MDP에 대한 모든 정보를 아는 상황 뿐만 아니라 모르는 상황에서도 강화 학습을 해야 합니다. 모든 MDP를 다 안다면 실제로 경험해보지 않고 머릿 속에서 시뮬레이션 해보는 것만으로도 강화 학습을 할 수 있습니다. 이런 종류의 접근법을 Model-based(모델 기반) 혹은 Planning(플래닝)라고 합니다. 반대로 MDP에 대한 정보를 모를 때 학습하는 접근법을 Model-Free(모델 프리) 접근법이라고합니다.

벨만 최적 방정식 (Bellman Optimization Equation)

벨만 기대 방정식은 모두 정책이 𝜋로 고정되어 있을 때의 밸류에 관한 함수였습니다. 반면 벨만 최적 방정식은 최적 밸류에 대한 함수입니다. 최적 밸류의 정의는 다음과 같습니다.

어떤 MDP가 주어졌을 때 그 MDP안에 존재하는 모든 𝜋들 중에서 가장 좋은 𝜋를 선택하여 계산한 값이 곧 최적 밸류입니다. 가장 좋은 𝜋로 계산했기 때문에 가장 높은 밸류 값을 갖게 됩니다. 여기서 궁금증 하나가 생깁니다. s1~s5에서는 𝜋1 이 더 높고, s6~s10에서는 𝜋2가 더 높다고 가정할 때, 두 정책 중 어느 정책이 더 좋다고 말하기 어렵습니다. 하지만 뛰어난 학자들이 다음과 같은 정리를 증명해 놓았습니다.

이 정리를 이해하는 것은 또 다른 얘기로 이어지기 때문에 중요한 것은 어느 MDP라도 최적의 정책이 존재한다는 것입니다.

최적의 정책만 정의되면 다음과 같은 등식이 성립합니다.

다음은 벨만 최적 방정식입니다.

벨만 기대 방정식에서는 정책 𝜋가 액션을 선택할 때의 확률적 요소, 다른 하나는 전이 확률에 의해 다음 상태를 선택할 때의 확률적 요소 두가지의 확률 변수가 있습니다. 하지만 벨만 최적 방정식에서는 𝜋에 의한 확률적 요소가 사라집니다. 액션을 선택할 때 확률적으로 선택하는 것이 아니라 최댓값 연산자를 통해 제일 좋은 액션을 선택하기 때문입니다.

 

벨만 기대 방정식과 같은 취지의 식입니다. 벨만 최적 방정식은 최적의 정책을 선택할 것이기 때문에 최댓값 연산자를 이용해 액션을 선택합니다. 하지만 전이 확률이라는 확률 변수가 남아 있기 때문에 여전히 기댓값 연산자가 필요합니다.

 

이 식은 정말 간단합니다. 상태 s의 최적 밸류는 s에서 선택할 수 있는 액션들 중 가장 높은 액션 밸류와 같다는 뜻입니다.

벨만 기대 방정식에서는 𝜋(a|s)라는 액션을 선택할 확률이 곱해졌었는데 벨만 최적 방정식에서는 100% 확률로 최적의 액션을 선택할 것이기 때문에 위와 같은 수식으로 정의됩니다.

위의 수식은 벨만 기대 방정식의 1단계를 잘 이해했다면 그와 완전히 같은 구조이기 때문에 익숙할 것입니다.

원래의 𝜋자리에 최적을 의미하는 별표(*)가 들어갔다는 점만 다릅니다.

 

2단계 또한 마찬가지로 1단계의 수식 2개를 조합하여 만들 수 있습니다.