벨만 방정식.


벨만 방정식은 강화학습과 동적 프로그래밍에서 핵심적인 역할을 하는 수식으로, 상태 가치 함수 V(s)를 재귀적으로 정의함.




이 공식을 볼때, 많은 사람들이 2번째 공식이 어떻게 유도되는가에 의문을 품음


우선

첫번째 수식은 상태 S에서 가치함수 V(s)가 해당 상태에서의 기대 반환값 G_t의 기댓값이라는 것을 의미함

이제 2번째 수식에서 G_t에 다음을 대입함 G_t=Rt+1 +γG_t+1 을 대입하여, 반환값을 시간에 따른 보상과 감쇠된 미래 보상으로 분리

3번째 수식에서 R은 다음 상태의 반환값을 의미함. 즉 기댓값을 보상과 감쇠된 미래 기댓값으로 분리함.

네번째 수식에서 Gt는 확률 변수로 정해져있는 특정값이 아니기때문에 기대값 개념을 추가함. 미래의 변화값에 대해서 다시 변화값을 취해서 V(s')로 표현됨




이 수식은 상태 S_t=s일때 다음 상태 기대값을 설명

G_t+1의 기대값을 상태 전이확률 P를 고려해 합산함


따라서 기대값은 V(S_t+1)로 표현되며 이는 미래상태에서의 가치함수로 변환


그리고 이를 도입해서


이 수식은 상태 S_t=s일때 반환값 G_t+1을 가질확률을 계산하는 것



이 식은 G_t+1 의 확률을 상태 s에 따른 조건부 확률과 상태 전이 확률을 가진


P(S_t+1=s'|S_t=s)로 분해하는 것. 즉 상태 s'로 전이될 확률의 합이고,


따라서 결과적으로 상태 전이 확률과 조건 부 확률을 계산하는 것이라고 봐야함.


그리고 이 2부분을 결합하면


이것이 흔히 말하는 벨만 방정식(Bellman Equation)임.


예를 들면 State S_1이 즉각 받는 보상은 Rs_1이고,


P12상태를 촉발할 확률은 S_2, S_2일때 얻는 보상은 R_s2임


자꾸 이렇게 말하면 솔직히 이해가 안갈거임


가장 일반적으로 예를 들어보자


야동검색->자위or프갤을 예로 들어보자


예를들어 야동을 검색한 후, 5의 보상을 받고,

야동을 검색한 후, 자위를 할지 프갤을 할지 선택한다고 하자.

0.6의 확률로 자위(+7의 보상이라고 가정)를 하고,

0.4의 확률로 프갤(+3의 보상) 한다고 하자.


여기서 후속상태에 기여하는 감쇠 인자를 약 0.5라고 하면


야동검색

R_s1=5


자위

R_s2=7( 자위 이후에는 현타밖에 없음) 자위를 하고나면 현타가 와서 아무것도 없기때문에 G_s2는 7임.


프로그래밍 갤러리


프로그래밍 갤러리는 3의 보상 R_s=3, 프로그래밍 갤러리는 벽보고 이야기하는 곳이니까 G_s3는 3임


따라서




라는 값이 나온다!


상태 S_2에는 S3의 후속 상태가 없고 각 상태의 후속 상태가 없으므로


v_s2=R_s2=7

v_s3=R_s3=3


이다.


자 이제 벨만 방정식을 가져와서 이값을 대입해보자



따라서 벨만 기대값은 7.7이다!


이건 단순한 계산이기때문에 계산량이 크지 않지만 상태가 많아지면 벨만 방정식의 계산량은 상대적으로 많아 진다

이때 계산에는 동적 프로그래밍(DP), 몬테 카를로 방법, TD 방법이 있는데


이것은 추후에 적도록 하겠다.