[바닥부터 배우는 강화학습] Chapter 3 벨만 방정식

🚨해당 게시글에 포함된 이미지 중 출처가 쓰여있지 않은 이미지는 모두 직접 그렸습니다.

3.0. 재귀 함수

벨만 방정식은 기본적으로 재귀적 관계에 대한 식이다.

재귀라는 개념을 먼저 이해하기 위해 다음과 같은 수열을 생각해보자. $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …$

이 수열은 앞의 두 항을 더해서 그 다음 항이 만들어진다. $0+1=1, 1+1=2, 2+3=5, …$

일반적인 함수를 이용하여 수열을 표현하면 (1)과 같지만 주어진 수열만 보고 (1)을 떠올리기는 쉽지않다.

이런 상황에서는 (2)와 같은 재귀함수를 이용하면 위의 수열을 쉽게 표현할 수 있다.

이처럼 재귀 함수는 자기 자신과의 관계를 이용해 자기 자신을 표현한다. n에서의 함수 값이 n-1과 n-2에서의 함수 값으로 표현된 것처럼 벨만 방정식은 현재 시점$(t)$과 다음 시점$(t+1)$ 사이의 재귀적 관계를 이용해 정의된다.

---

3.1. 벨만 기대 방정식

벨만 기대 방정식은 편의상 세 단계로 나눌 수 있다. 이 단계는 편의상 나눈 개념이고 명시적으로는 나뉘지 않는다.

3.1.1. 0단계

위의 첫 번째 식은 현재 상태의 밸류와 다음 상태의 밸류 사이 관계를 나타내고 있다. 위와 같은 관계가 성립하는 이유는 아래의 $v_π(s_t)$의 정의를 통해 알 수 있다.

3.1.2. 1단계

(1) $q_π$를 이용해 $v_π$ 계산하기

위와 같이 상태 $s$에서 선택할 수 있는 액션이 $a_1, a_2$ 2개가 있는 상황을 생각해보자. 정책 $π$가 두 액션을 선택할 확률은 각 60%와 40%, 액션 밸류 $q_π(s,a_1)$와 $q_π(s,a_2)$의 값이 각각 1과 2이다. 정책이 $a_1$을 선택할 확률이 60%, $a_2$를 선택할 확률이 40%이므로 $s$에서 $a_1$을 선택했을 때의 밸류인 $q(s,a_1)$의 값에 0.6을, $a_2$를 선택했을 때의 밸류인 $q(s,a_2)$의 값에 0.4를 곱해서 더해주면 $s$의 밸류를 계산할 수 있다. 이를 식으로 풀어쓰면 아래와 같다.

즉, 어떤 상태에서 선택할 수 있는 모든 액션의 밸류를 모두 알고 있다면, 이를 이용해 해당 상태의 밸류를 계산할 수 있다. 액션의 밸류에 액션을 선택할 확률을 곱해서 시그마를 이용해 모두 더해주는 방식이다.

(2) $v_π$를 이용해 $q_π$ 계산하기

위와 같이 $a_1$을 선택하자마자 받는 보상은 0.5이고, 액션 $a_1$을 선택하면 다음 상태가 어디가 될지 그 각각에 대한 전이 확률 또한 알고 있다고 하자. 그리고 각 상태의 밸류 $v_π(s_1)$과 $v_π(s_2)$도 안다고 생각해보자. 받는 보상을 더해주고, 그 다음에 도달하게 되는 상태의 밸류와 그 확률을 곱해서 더해주면 된다.

3.1.3. 2단계

$v_π$에 대한 식을 $q_π$에 대한 식에 대입하면 아래와 같은 결과를 얻는다.

아래와 같이 0단계와 2단계의 $v_π(s)$를 나란히 두고 보자.

0단계의 기댓값을 계산하는 방법은? 2단계의 수식을 생각하면 된다.

2단계의 수식은 0단계에 있는 기댓값 연산자를 모두 확률과 밸류의 곱으로 풀어서 쓴 형태이다.

2단계 식을 계산하기 위해서는 다음 2가지를 반드시 알아야 한다.

위 2가지는 환경의 일부이며, 이 정보를 알 때 “MDP를 안다”고 표현한다.

하지만, 우리는 위의 정보를 모를 때에도 강화학습을 한다.

• MDP 정보를 모를 때 학습하는 접근법 : 모델-프리(model-free)
• MDP 정보를 알 때 학습하는 접근법 : 모델 기반(Model-based) 혹은 플래닝(planning)

---

3.2. 벨만 최적 방정식

3.2.1. 최적 밸류와 최적 정책

벨만 기대 방정식이 $v_π(s), q_π(s,a)$에 대한 수식이라면 벨만 최적 방정식은 $v^(s), q^(s,a)$에 대한 수식이다. $v^(s)$와 $q^(s,a)$는 최적 밸류에 대한 함수이다. 어떤 MDP가 주어졌을 때 그 MDP 안에 존재하는 모든 $π$들 중에서 가장 좋은 $π$로 계산한 밸류가 최적 밸류이다.

$$ v_(s)=\max_πv_(s)\\q_(s,a)=\max_πq_π(s,a) $$

챕터 2의 아이재우기 예시를 생각해보자. 아이 재우기 MDP에서 무수히 많은 정책 $π$를 생각해 볼 수 있다. (항상 $a_0$ 선택, 항상 $a_1$ 선택, 반반 선택…) 정책의 집합을 {$π_1, π_2, π_3,…,π_∞$}로 표현한다면 각각의 정책 $π_n$을 따랐을 때 $s_0$의 밸류를 정의할 수 있다. {$v_{π_1}(s_0), v_{π_2}(s_0), v_{π_3}(s_0),…, v_{π_∞}(s_0)$} 이 중에 23번째 정책 $π_{23}$의 밸류 $v_{π_{23}}(s_0)$의 값이 가장 크다면 우리는 $v^*(s_0)$를 찾은 것이다. 위의 과정을 한 줄로 표현하면 아래와 같다.

여기서 상태마다 가장 높은 밸류를 주는 정책이 다르다면? 즉, $s_0$의 밸류는 $π_{23}$를 따를 때 가장 크지만, $s_1$의 밸류는 $π_{35}$를 따를 때 가장 크다면? $s_0$에서는 $π_{23}$를 따르고, $s_1$에서는 $π_{35}$를 따르는 새로운 정책 $π^*$를 생각할 수 있고 이러한 정책을 최적 정책(optimal policy)라고 부른다.

“가장 좋다”의 엄밀한 정의
- 다른 정책을 따를 때보다 최적의 정책 $π^*$를 따를 때 얻는 보상의 총 합이 가장 크다는 뜻이다.
- 모든 상태 $s$에 대해, $v_{π_1}(s)>v_{π_2}$$(s)$이면 $π_1>π_2$이다.
- MDP 내의 모든 $π$에 대해 $π^*>π$를 만족하는 $π^*$가 반드시 존재한다.

최적의 정책만 정의되고 나면 최적의 밸류, 최적의 액션 밸류는 다음과 같은 등식을 만족한다.

3.2.2. 0단계

벨만 기대 방정식은 확률적 요소를 2개나 가지고 있기 때문에 기댓값 연산자가 많았다.

• 정책 π가 액션을 선택할 때의 확률적 요소
• 환경의 전이 확률에 의해 다음 상태를 선택할 때의 확률적 요소 하지만 벨만 최적 방정식에서는 이 둘 중 π에 의한 확률적 요소가 사라진다. 액션을 선택할 때 확률적으로 선택하는 것이 아니라 최댓값 연산자를 통해 제일 좋은 액션을 선택하기 때문이다.

벨만 기대 방정식의 0단계와 같은 방법으로 구할 수 있다.

$E_π$에서 E로 바뀐 이유? 원래는 주어진 π가 액션을 선택하였지만, 이제는 모든 액션들 중 값을 가장 크게 하는 액션 a를 선택해야하기 때문에 π의 역할은 없다. 하지만 환경에 의한 확률적 요소가 남아있어서 다양한 s’에 도달할 수 있기 때문에 기댓값 연산자가 필요하다.

3.2.2. 1단계

(1) $q_*$를 이용해 $π_*$를 계산하기

위 그림과 같이 상태 $s$에서 선택할 수 있는 액션이 $a_1, a_2$ 2가지가 있다고 하자. 이미 각 액션을 선택했을 때 얻을 수 있는 최적 밸류는 알고 있다. 그렇다면 둘 중에 가치가 더 높은 액션인 $a_2$를 선택하는 것이 상태 $s$에서 할 수 있는 최적의 액션일 것이다. 수식으로 나타내면 아래와 같다.

(2) π를 이용해 q를 계산하기

벨만 방정식의 1단계 과정과 동일하다. π를 *로 바꾼 것 뿐이다.

3.2.2. 2단계

$v*(s)$의 식에 $q*(s,a)$의 식을 대입하면 된다.

$v*(s)$의 식을 $q*(s,a)$의 식에 대입하면 된다.

• 벨만 기대 방정식 : 정책 π가 주어져있고, π를 평가하고 싶을 때 사용
• 벨만 최적 방정식 : 최적의 밸류를 찾고 싶을 때 사용

벨만 기대 방정식과 벨만 최적 방정식을 한번에 살펴보면 아래와 같다.