Bellman Optimality Equation

state-value function $v_{\pi }(s)$ 에 대한 Bellman Equation 은 다음과 같다.

$$v_{\pi }(s)\triangleq \sum _a\pi (a\mid s)\sum _{s^{\prime },r}p\left(s^{\prime },r\mid s,a\right)\left[r+\gamma v_{\pi }\left(s^{\prime }\right)\right]$$

하지만 optimal state-value function $v_{\ast }$ 는 $\pi (a|s)$ 가 필요없다. 왜냐하면 항상 최적의 policy 는 누적 보상을 최대화하는 action 을 이미 알고있기 때문이다.

결과적으로 optimal policy 에 대한 state-value function 에 대한 bellman 수식, 즉, bellman optimality equation 은 다음과 같이 바꿔쓸 수 있다.

$$\begin{array}{rl}{v}_{\ast }(s)=& \underset{a}{\max }{q}_{\ast }(s,a)\\ =& \underset{a}{\max }E\left[R_{t+1}+\gamma v_{\ast }\left(s^{\prime }\right)\mid S_t=s,A_t=a\right]\\ =& \underset{a}{\max }\sum _{s^{\prime },r}p\left(s^{\prime },r\mid s,a\right)\left[r+\gamma v_{\ast }\left(s^{\prime }\right)\right]\end{array}$$

A.1) 식 풀어 쓰기

$$\begin{array}{rl}{v}_{\ast }(s)& =\underset{a\in \mathcal{A}(s)}{\max }{q}_{{\pi }_{\ast }}(s,a)\\ & =\underset{a}{\max }{\mathbb{E}}_{{\pi }_{\ast }}\left[G_t\mid S_t=s,A_t=a\right]\\ & =\underset{a}{\max }{\mathbb{E}}_{{\pi }_{\ast }}\left[R_{t+1}+\gamma G_{t+1}\mid S_t=s,A_t=a\right]\\ & =\underset{a}{\max }\mathbb{E}\left[R_{t+1}+\gamma v_{\ast }\left(S_{t+1}\right)\mid S_t=s,A_t=a\right]\\ & =\underset{a}{\max }\sum _{s^{\prime },r}p\left(s^{\prime },r\mid s,a\right)\left[r+\gamma v_{\ast }\left(s^{\prime }\right)\right]\end{array}$$

여기서 $G_t\to R_{t+1}+\gamma G_{t+1}$ 는 이전에 수식을 활용하여 유도된다.

$$\begin{array}{rl}{G}_t& \doteq R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+{\gamma }^3{R}_{t+4}+\cdots \\ & =R_{t+1}+\gamma \left(R_{t+2}+\gamma R_{t+3}+{\gamma }^2{R}_{t+4}+\cdots \right)\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$

A.2) For Action-value Function

optimal action-value function $q_{\ast }$ 에 대한 Bellman Optimality Equation 은 다음과 같다.

$$\begin{array}{rl}{q}_{\ast }(s,a)& =E\left[R_{t+1}+\gamma v_{\ast }\left(s^{\prime }\right)\mid S_t=s,A_t=a\right]\\ & =E\left[R_{t+1}+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }\left(S_{t+1},a^{\prime }\right)\mid S_t=s,A_t=a\right]\\ & =\sum _{s^{\prime },r}p\left(s^{\prime },r\mid s,a\right)\left[r+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }\left(s^{\prime },a^{\prime }\right)\right]\end{array}$$

Bellman Optimality Equation 을 푸는 것은 optimal policy 를 찾는데 사용할 수 있다. 하지만 실제로는 그렇게 유용하지 못한데, 왜냐하면 다음과 같은 세가지 조건이 만족되어야 하기 때문이다.

1. 환경에 대한 dynamics 를 정확히 알아야 한다.
2. 계산을 위한 충분한 자원이 있어야 할 것
3. state 가 Markov property 를 따를 것

예를 들어 벡가몬 게임의 경우 (1), (3) 은 만족하지만 (2) 의 경우 $10^{20}$ 에 대한 경우의 수를 처리해야 한다.

B) References