벨만 방정식

강화 학습 스터디) 바닥부터 배우는 강화학습을 읽고 정리하였습니다.

 

벨만 방정식: 어떤 주어진 상태의 밸류를 계산하는 방법

chatGPT가 생성한 벨만 방정식. 예쁘다...

밸만 기대 방정식

Remind

• state-value function
  • $v_{\pi}(s_{t}) = \mathbb{E}[r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + …] = \mathbb{E}[r_{t+1} + \gamma (r_{t+2} + \gamma r_{t+3} + …)] = \mathbb{E}[r_{t+1} + \gamma G_{t+1}] = \mathbb{E}[r_{t+1} + \gamma v_{\pi}(s_{t+1})]$
  • $s_{t}$의 밸류는 리턴의 기댓값인데 이를 위처럼 다시 $s_{t+1}$ 의 state-value function으로 나타낼 수 있음
  • 기댓값인 이유는 s_{t}에서 시작하여 s_{t+1}이 정해지기 까지는 두 번의 확률적인 과정을 거쳐야 하기 떄문!
    • 정책이 액션을 선택할 때 한번(에이전트가 실행)
    • 액선이 선택되고 나서 전이 확률에 의해 다음 상태가 정해질 때 한번(환경이 실행)

[1] $q_{\pi}$ 를 이용해 $v_{\pi}$ 계산하기

• 정책은 $\pi$로 고정되어 있음
• 여기서 각 action이 선택될 때 q 값은 알고 있다했을 때 위 밸류를 구할 수 있음 </aside>
• 💡 $v_{\pi}(s) = \sum_{a\in A} \pi(a|s)q_{\pi}(s,a)$

[2] $v_{\pi}$를 이용해 $q_{\pi}$ 계산하기

💡 $q_{\pi}(s,a) = r^a_{s} + \gamma \sum_{s’ \in S} P^a_{ss’}v_{\pi}(s’)$

• 상태의 밸류를 이용하여 액션 밸류를 평가하기
• 당연히 상태의 밸류를 모두 알고 있어야 함

[1]과 [2]를 바탕으로 서로 대입을 하면 최종 수식은 각각 다음과 같음

([1]에 있는 q 값을 [2]로 대체, vice versa)

💡 $v_{\pi}(s) = \sum_{a \in A} \pi(a|s)(r^a_{s} + \gamma \sum_{s’ \in S} P^a_{ss’}v_{\pi}(s’))$

💡 $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’)$

여기서 주목할 점은 위 remind 부분에서 언급했던 state value function인

$v_{\pi}(s_{t}) = \mathbb{E}[r_{t+1} + \gamma v_{\pi}(s_{t+1})]$ 과, 방금 정리한

$v_{\pi}(s) = \sum_{a \in A} \pi(a|s)(r^a_{s} + \gamma \sum_{s’ \in S} P^a_{ss’}v_{\pi}(s’))$의 관계인데,

후자의 기댓값을 어떻게 구할 수 있는지에 대해 깔끔히 정리가 됨

따라서 state value function의 값을 구하기 위해서는

각 상태에서 액션을 취하면 받는 보상 $r^a_{s}$와 각 상태에서 액션을 선택하면 다음 상태가 어디가 될지에 관한 확률 분포 $P^a_{ss’}$(dynamics)을 반드시 알아야 함

→ 그 두가지를 알 때 “MDP를 안다” 라고 표현

MDP 를 모를 때 → model free 접근법으로 풀어야 함(책의 후반부에 등장)

MDP를 알 때 → model based(planning) 접근법으로 푼다고 함(챕터 4, 5)

---

벨만 최적 방정식

• 최적의 정책: $\pi_{*}$
• 최적의 밸류: $v_{*} = v_{\pi_{ * }}(s)$ ($\pi_{*}$를 따랐을 때의 밸류)
• 최적의 액션 밸류: $q_{ * }(s,a) = q_{\pi_{ * }}(s,a)$($\pi_{*}$를 따랐을 때의 액션 밸류)

state value function, action value function 표현

• 여기서 expectation term이 있는 이유는 최적의 정책에 따라 action을 취했을 때 전이 확률에 따라 다음 상태가 결정되기 때문임(아직 확률적 과정이 남아있어서)

[1] $q_{ * }$를 이용해 $v_{ * }$ 계산하기

• 최적의 정책을 따랐을 때, 상태 s 에서의 최적 밸류는 액션 밸류 함수의 최댓값
• 만약, 최적의 정책을 따랐을 때 상태 s에서 a를 선택하는 액션 밸류 값을 모두 알고 있다면, 값을 구할 수 있음
• 확률적 요소가 사라진 이유는 최적의 정책은 가장 큰 값을 내뱉어야해서(무조건 값이 큰 q 값을 고름 → 액션이 정해짐) 

[2] $v_{*}$를 이용해 $q_{*}$ 계산하기

• 밸만 기대 방정식과 큰 차이 없음

[1]과 [2]를 바탕으로 서로 대입을 하면 최종 수식은 각각 다음과 같음

💡 $v_{ * }(s) = max_{a}q_{ * }(s,a)=max_{a}[r^a_{s}+\gamma \sum_{s' \in S} P^a_{ss'}v_{*}(s')]$<aside>

💡 $q_{}(s,a) = r^a_{s} + \gamma \sum_{s’ \in S} P^a_{ss’}v_{*}(s’)=r^a_{s} + \gamma \sum_{s' \in S}P^a_{ss'}max_{a'}q_{*}(s',a')$

→ MDP를 알 때에 최적의 밸류를 구할 수 있게 됨

• ([1]에 있는 q 값을 [2]로 대체, vice versa)
• 💡 $q_{ * }(s,a) = r^a_{s} + \gamma \sum_{s’ \in S} P^a_{ss’}v_{ * }(s’)$
• 💡 $v_{ * }(s) = max_{a}q_{ * }(s,a)$
• 💡 $v_{ * }(s) = max_{a} \mathbb{E} [r + \gamma v_{ * }(s’) | s_{t} = s, a_{t} = a]$ $q_{ * }(s,a) = \mathbb{E}[r+\gamma max_{a’}q_{ * }(s’,a’) | s_{t} = s, a_{t} = a]$
• 어떤 MDP가 주어졌을 때 그 MDP 안에 존재하는 모든 $\pi$ 들 중에서 가장 좋은 $\pi$를 선택하여 계산한 밸류가 최적 밸류 $v_{*}(s)$ 임

 

참고 문헌

바닥부터 배우는 강화학습 - 노승은