https://www.youtube.com/watch?v=gA-6J-nl4c4&list=PL_iJu012NOxehE8fdF9me4TLfbdv3ZW8g&index=5
Bellman Equation
벨만 방정식은 특정 상태에서 최선의 선택을 하기 위해 현재 가치와 미래 가치를 연결하여 정의하는 방정식이다.
벨만 방정식을 증명하기 전 몇가지 알아야 할 식들은 다음과 같다.
상태 가치 함수:
$V(s_t)=\int_{a_t:a_\infty}G_t\cdot P(a_t,s_{t+1},a_{t+1},\cdots|s_t)d_{a_t:a_\infty}$
행동 가치 함수:
$Q(s_t,a_t)=\int_{s_{t+1}:a_\infty}G_t\cdot P(s_{t+1},a_{t+1},\cdots|s_t,a_t)d_{s_{t+1}:a_\infty}$
누적 가치 함수:
$G_t=R_t+\gamma G_{t+1}$
조건부 확률의 체인 룰:
$P(x,y|z)=P(x|y,z)\cdot P(y|z)$
이제 각 가치 함수들에 대해 증명(?)해보자
상태 가치 함수 $V(s_t)$
위 상태 가치 함수에 있는 확률 분포식 $P(a_t,s_{t+1},a_{t+1},\cdots|s_t)$을 변형하면 다음 두 식이 나온다.
- $P(s_{t+1},a_{t+1},\cdots|s_t,a_t)\cdot P(a_t|s_t)$
- $P(a_{t+1},\cdots|s_{t+1})\cdot P(a_t,s_{t+1}|s_t)$
위 확률 수식을 각각 대입하면 다음과 같다.
1번 수식
$V(s_t)=\int_{a_t}\int_{s_{t+1}:a_\infty}G_t\cdot P(s_{t+1},a_{t+1},\cdots|s_t,a_t)d_{s_{t+1}:a_\infty}P(a_t|s_t)d_{a_t}$
$\int_{s_{t+1}:a_\infty}G_t\cdot P(s_{t+1},a_{t+1},\cdots|s_t,a_t)d_{s_{t+1}:a_\infty}$를 행동 가치 함수 Q(s_t,a_t)로 표현하면 다음과 같이 상태 가치 함수를 나타낼 수 있다.
$V(s_t)=\int_{a_t}Q(s_t,a_t)\cdot P(a_t|s_t)d_{a_t}$
2번 수식
$V(s_t)=\int_{a_t}\int_{s_{t+1}:a_\infty}G_t\cdot P(a_{t+1},\cdots|s_t,a_t)d_{s_{t+1}:a_\infty}P(a_t,s_{t+1}|s_t)d_{a_t}$
위의 누적 가치 함수를 사용
$V(s_t)=\int_{a_t,s_{t+1}}\int_{a_{t+1}:a_\infty}(R_t+\gamma G_{t+1})\cdot P(a_{t+1},\cdots|s_t,a_t)d_{a_{t+1}:a_\infty}P(a_t,s_{t+1}|s_t)d_{a_t,s_{t+1}}$
$R_t$는 $a_t$에 대한 식이니 따로 빼면 다음과 같다.
$V(s_t)=\int_{a_t,s_{t+1}}P(a_t,s_{t+1}|s_t)\cdot(R_t+\gamma\int_{a_{t+1}:a_\infty}G_{t+1}\cdot P(a_{t+1},\cdots|s_{t+1})d_{a_{t+1}:a_\infty}d_{a_t,s_{t+1}}$
$\int_{a_{t+1},a_\infty}G_{t+1}\cdot P(a_{t+1},\cdots|s_{t+1})d_{a_{t+1}:a_\infty}$를 상태 가치 함수 $V(s_{t+1})$로 나타내면 다음과 같이 나타낼 수 있다.
$V(s_t)=\int_{a_t,s_{t+1}}(R_t+\gamma\cdot V(S_{t+1}))\cdot P(a_t, s_{t+1}|s_t)d_{a_t,s_{t+1}}$
행동 가치 함수 Q(s_t,a_t)
위 행동 가치 함수에 있는 확률 분포식 $P(s_{t+1},a_{t+1},\cdots|s_t,a_t)$을 변형하면 다음 두 식이 나온다.
- $P(a_{t+1},\cdots|s_{t+1})\cdot P(s_{t+1}|s_t,a_t)$
- $P(s_{t+2},a_{t+2},\cdots|s_{t+1},a_{t+1}\cdot P(s_{t+1},a_{t+1}|s_t,a_t)$
1번 수식
$Q(s_t,a_t)=\int_{s_{t+1}}P(s_{t+1}|s_t,a_t)\int_{a_{t+1}:a_\infty}(R_t+\gamma\cdot G_{t+1})\cdot P(a_{t+1},s_{t+2},\cdots|s_{t+1})d_{a_{t+1}:a_\infty}d_{s_{t+1}}$
$R_t$는 $a_t, s_t$에 의한 값이므로 다음과 같이 분리할 수 있다.
$Q(s_t,a_t)=\int_{s_{t+1}}P(s_{t+1}|s_t,a_t)(R_t+\gamma\int_{a_{t+1}:a_\infty}G_{t+1}\cdot P(a_{t+1},s_{t+2},\cdots|s_{t+1}d_{a_{t+1}:a_\infty}d_{s_{t+1}}$
$\int_{a_{t+1}:a_\infty}G_{t+1}\cdot P(a_{t+1},s_{t+2},\cdots|s_{t+1},s_{t+2},\cdots|s_{t+1}d_{a_{t+1}:a_\infty}$를 상태 가치 함수 $V(s_{t+1})$로 나타내면 다음과 같이 나타낼 수 있다.
$Q(s_t,a_t)=\int_{s_{t+1}}(R_t+\gamma\cdot V(s_{t+1}))\cdot P(s_{t+1}|s_t,a_t)d_{s_{t+1}}$
2번 수식
$Q(s_t,a_t)=\int_{s_{t+1},a_{t+1}} P(s_{t+1},a_{t+1}|s_t,a_t)\cdot\int_{s_{t+2}:a_\infty}(R_t+\gamma\cdot G_{t+1})\cdot P(s_{t+2},a_{t+2},\cdots|s_{t+1},a_{t+1})d_{s_{t+2}:a_\infty}d_{s_{t+1},a_{t+1}}$
1번 수식에서처럼 분리를 진행하면 최종적으로 다음과 같이 나타낼 수 있다.
$Q(s_t,a_t)=\int_{s_{t+1},a_{t+1}}(R_t+\gamma\cdot Q(s_{t+1},a_{t+1}))\cdot P(s_{t+1},a_{t+1}|s_t,a_t)d_{s_{t+1},a_{t+1}}$