강화학습 벨만 방정식

최적의 정책을 찾기 위해서는, 정책을 평가해야한다.

에피소드마다 미래에 얻을 보상이 다르고, 그 에피소드가 발생할 확률도 다르기 때문에 정책의 value를 구하는 것은 어렵다. 벨만 방정식은 정책의 value를 구하는데 사용된다.

벨만 방정식은 시점 t에서의 value와 시점 t+1에서의 value 사이의 관계를 다루고 있고 가치 함수와 정책 함수 사이의 관계도 다루고 있다.

벨만 방정식에는 두 가지의 방정식이 존재한다.

• 벨만 기대 방정식: 특정 정책 $\pi$를 평가
• 벨만 최적 방정식: 최적의 value를 갖는 $\pi$를 찾음

 

벨만 기대 방정식

특정 정책 $\pi$를 평가하기 위해 상태 가치 값을 반복적인 방법을 통해 구한다.

상태 가치 함수는 다음의 식으로 나타낼 수 있고

$$ v_{\pi}(s_t)=\mathbb E_\pi[G_t] \\= \mathbb E_\pi[r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\cdots]\\=\mathbb E_\pi[r_{t+1}+\gamma(r_{t+2}+\gamma r_{t+3}+\cdots)] \\ =\mathbb E_\pi[r_{t+1}+\gamma G_{t+1}]\ \ \ \ \ \ \ \ \cdots \ \cdots \ \ (1)\\ =\mathbb E_\pi[r_{t+1}+\gamma v_\pi(s_{t+1})]\ \ \cdots \ \cdots \ \ (2) $$

(1)→(2): $\mathrm{G}_{t+1}$은 확률변수로 정해져있는 특정값이 아니기 때문에 그 자체의 값을 기댓값으로 사용할 수 있다.

식(2)를 통해 t+1시점의 상태에서의 가치함수를 알면 t시점의 상태에서의 가치를 계산할 수 있게 되었다.

액션 가치 함수 또한 상태 가치 함수와 마찬가지로 식(3)으로 나타낼 수 있다.

$$ q_\pi(s_t,a_t)=\mathbb E_\pi[r_{t+1}+\gamma q_\pi(s_{t+1}, a_{t+1})]\ \cdots \ \cdots \ (3) $$

액션 가치또한 식(3)을 통해 t+1시점의 상태와 액션의 가치를 알면 t시점의 상태와 액션의 가치를 알수 있게 되었다. 그러나 문제는 둘의 관계가 기댓값을 통해 연결되어있다는 것이다. 모든 에피소드에 대해 알 수 없기 때문에 기댓값을 계산하기 어렵다.

이 문제를 해결하기 위해 상태 가치 함수와 액션 가치 함수 사이의 관계를 이용할 것이다.

먼저 액션 가치 함수를 통해 상태 가치 함수를 정의할 수 있다. 조금더 쉽게 설명하자면 상태 $s$에서 취할수 있는 모든 행동 $A$에 대해 각 행동의 발생 확률과 그 가치를 곱한 것의 합으로 상태 $s$에서의 가치를 정의하는 것이다. 직관적인 설명은 이렇게 할 수 있고, 수학적인 설명은 베이즈 정리를 통해 할 수 있다(혁펜하임 강의).

*수학적 설명

조건부 확률 곱셈 법칙

$$ P(A \cup B) = P(A)P(B|A) $$

$$ P(A,B) = P(A|B)P(B)=P(B|A)P(A) \\ P(A,B|C)=P(A|B,C)P(B|C) $$

상태 가치 함수의 변수: s

액션 가치 함수의 변수: s, a

상태 가치 함수에 액션을 나타내는 변수 a를 도입한 것이 상태 가치 함수이기 때문에 베이즈 정리(조건부 확률)를 통해 상태 가치 함수를 액션 가치 함수로 나타낼 수 있다.

$$ v_\pi(s)=\sum_{a \in A} \pi(a|s)q_\pi(s,a) \ \cdots \ \cdots \ (4) $$

• $v_\pi(s)$: s상태의 가치
• $\pi(a|s)$: s상태에서 a를 실행할 확률
• $q_\pi(s,a)$: s상태에서 a를 실행하는 것의 가치

$$ q_\pi(s,a)=r^a_s + \gamma \sum_{s' \in S}p^a_{ss'}v_\pi(s') \ \ \cdots \ \cdots \ (5) $$

• $q_\pi(s,a)$: s상태에서 a를 행할때의 가치
• $r^a_s$: 즉시 얻는 보상
• $p^a_{ss’}$: s상태에서 a를 행하면 s’상태에 도달할 확률
• $v_\pi(s’)$: s’상태의 가치

혁펜하임 강의 설명 정리

식(5)의 상태 가치 함수 부분에 식(4)를 대입하고, 식(4)의 액션 가치 함수 부분에 식(5)를 대입하면 다음과 같이 나타낼 수 있게 된다.

 

$$ v_\pi(s)=\sum_{a \in A}\pi(a|s)(r^a_s+\gamma\sum_{s' \in S}p^a_{ss'}v_\pi(s')) \ \ \cdots\ \ \cdots \ (6) \\ q_\pi(s,a)=r^a_s+\gamma \sum_{s' \in S}p^a_{ss'}\sum_{a' \in A}\pi(a'|s')q_\pi(s',a') \ \ \cdots \ \cdots \ (7) $$

이로써 기댓값을 사용하지 않고도 상태 s’에서의 가치로부터 상태 s에서의 가치 함수를 계산할 수 있게 된다.

강화학습은 리턴을 최대로 하는 것이 가장 중요하고, 리턴은 상태 가치 함수로 구성되기 때문에 이로부터 도출해낸 식(6)이 중요한 역할을 하게 된다.

식(6),(7)을 계산하기 위해서는 다음 두가지를 반드시 알아야 한다.

• 보상 함수 $r^a_s$: 각 상태에서 액션을 선택하면 얻는 보상
• 전이 확률 $p^a_{ss’}$: 각 상태에서 액션을 선택하면 다음 상태가 어떻게 될지에 관한 확률분포

이 두가지 값은 환경의 일부다. 이 두가지에 대한 정보를 알때 MDP를 안다고 표현한다.

그러나 MDP에 대한 모든 정보를 모르는 상황에서도 강화학습을 해야한다. → model-free 접근법

• r^a_s 를 모른다. → 어떨때 어떤 보상을 받는지 경험을 통해 학습한다.

반대로 MDP에 대한 모든 정보를 안다. → 실제로 경험해보지 않고 머릿속에서 시뮬레이션 해보는 것만으로도 강화학습을 할 수 있다. → model-based planning

model-free 접근법, model-based planning 모두 벨만방정식을 이용한다.

• MDP의 모든 정보를 알때 → 식(2) 이용
• MDP의 정보를 모를 때 → 식(6) 이용

벨만 최적 방정식

정책을 최적 정책으로 사용하기 때문에 \pi notation은 하지 않게 된다.

$$ v_(s_t)=\max_a \mathbb E[r_{t+1}+\gamma v_(s_{t+1})] \ \ \cdots \ \cdots \ (8) \\ q_(s_t, a_t) = \mathbb E[r_{t+1}+\gamma \max_{a'}q_(s_{t+1}, a')] \ \ \cdots \ \cdots \ (9) $$

$$ v_(s)=\max_a q_(s,a) \ \ \cdots \ \cdots \ (10) \\ q_(s,a) = r^a_s + \gamma \sum_{s' \in S}p^a_{ss'}v_(s') \ \ \cdots \ \cdots \ (11) $$

 

100%의 확률로 action을 선택하는 것이 최적의 밸류를 얻게 해주기 때문에 벨만 기대 방정식의 식 (4)에 사용된 정책 함숫값이 1로 사용되어 식 (10)에 표시하지 않는다.

$$ v_(s)=\max_a[r^a_s+\gamma\sum_{s'\in S}p^a_{ss'}v_(s')]\ \ \cdots \ \cdots \ (12)\\q_(s,a)=r^a_s+\gamma \sum_{s' \in S}p^a_{ss'}\max_{a'}q_(s',a')] \ \ \cdots \ \cdots \ (13) $$

최고의 정책 찾기 - 정책 이터레이션

정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할때까지 반복

최고의 정책 찾기 - 밸류 이터레이션

최적 정책의 밸류 계산 - 벨만 최적 방정식 사용.