들어가며...

앞 글에서 State value를 다음과 같이 정의했다.

$$v_\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t=s \right]$$

State $s$에서 Policy $\pi$를 따를 때 앞으로 받을 Return의 기대값이다.

정의만 보면 Value를 구하려면 미래의 Reward를 Episode 끝까지 전부 펼쳐야 할 것 같다.

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$$

Episode가 세 Step이면 직접 더할 수 있다. 하지만 수백 Step이거나 끝나지 않는 환경에서는 매 State마다 긴 미래를 반복해서 계산하는 방식이 답답해진다.

Bellman Equation은 이 긴 미래에서 반복되는 구조를 찾아낸다.

전체 미래는 바로 다음 Reward와, Next State부터 시작하는 나머지 미래로 나눌 수 있다.

말로 보면 당연해 보이지만 강화학습의 거의 모든 Value 업데이트가 이 아이디어에서 나온다.

Return의 꼬리를 접어보기

Return을 첫 Reward와 나머지 부분으로 묶어보자.

$$\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\ &= R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \cdots \right) \end{aligned}$$

괄호 안을 자세히 보면 시간 $t+1$부터 시작하는 Return $G_{t+1}$과 같다.

$$G_t = R_{t+1} + \gamma G_{t+1}$$

이제 Expectation을 취하면 $G_{t+1}$의 기대값은 Next State의 Value가 된다.

$$v_\pi(s) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t=s \right]$$

이것이 State value에 대한 Bellman expectation equation이다.

수식이 자기 자신을 포함해서 이상해 보일 수 있다. 왼쪽에 $v_\pi$가 있고 오른쪽에도 $v_\pi$가 있다. 하지만 현재 State의 Value를 Next State들의 Value로 표현한 것이므로 순환 구조가 생기는 것이 자연스럽다.

회사 조직도에서 “팀의 전체 업무량은 오늘 들어온 일과 내일로 넘어간 업무량”이라고 적는 것과 비슷하다. 내일의 업무량도 같은 규칙으로 그다음 날과 연결된다. Bellman Equation은 이 반복되는 구조를 이용한다.

작은 숫자로 Bellman Equation 읽기

State $s$에서 다음 Reward는 항상 $2$이고, Policy와 Environment에 따라 다음 두 State로 이동한다고 하자.

• 확률 $0.7$로 $s_1$에 도착하며 $v_\pi(s_1)=5$
• 확률 $0.3$으로 $s_2$에 도착하며 $v_\pi(s_2)=1$
• $\gamma=0.9$

먼저 Next State의 기대 Value를 계산한다.

$$0.7 \times 5 + 0.3 \times 1 = 3.8$$

그다음 Discount하고 즉시 Reward를 더한다.

$$\begin{aligned} v_\pi(s) &= 2 + 0.9 \times 3.8 \\ &= 5.42 \end{aligned}$$

현재 State $s$의 Value는 $5.42$다. $2$는 바로 다음에 받는 Reward이고 $3.42$는 Next State 이후 미래의 현재 가치다.

Transition probability와 Reward function을 모두 알고 있다면 Bellman Equation을 합 기호로 펼칠 수 있다.

$$v_\pi(s) = \sum_a \pi(a \mid s) \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a v_\pi(s') \right]$$

수식이 길어졌지만 순서는 다음 네 단계뿐이다.

1. Policy가 Action $a$를 고를 확률을 본다.
2. 그 Action의 즉시 Reward를 본다.
3. 가능한 Next State의 Value를 Transition probability로 평균낸다.
4. 모든 Action에 대해 Policy 확률로 다시 평균낸다.

Bellman backup은 오른쪽으로 왼쪽을 고치는 일이다

오른쪽의 Reward와 Next State Value를 이용해 현재 Value를 새로 계산하는 과정을 Backup이라고 부른다.

처음에는 모든 Value를 $0$으로 두어도 된다.

$$V_0(s)=0$$

한 번 Backup하면 바로 다음 Reward의 정보가 들어온다. 여러 번 반복하면 Reward 정보가 한 Step씩 더 먼 State로 퍼져나간다.

Gridworld 출구에 $+10$이 있다고 하자.

• 첫 번째 반복: 출구 바로 옆 State가 좋아진다.
• 두 번째 반복: 출구에서 두 칸 떨어진 State가 좋아진다.
• 반복을 계속하면 출구의 정보가 Grid 전체로 퍼진다.

Value Iteration을 “최종 Reward에서 시작해 뒤로 계산한다”라고 설명하는 이유다. 실제 환경이 Loop와 확률적 Transition을 가지고 있어도 반복 Backup을 통해 같은 직관을 사용할 수 있다.

Action value의 Bellman Equation

Action value도 같은 방식으로 한 Step과 나머지 미래로 나눌 수 있다.

$$q_\pi(s,a) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma q_\pi(S_{t+1},A_{t+1}) \mid S_t=s, A_t=a \right]$$

현재 $(s,a)$에서 Reward를 받고 Next State로 이동한 뒤, Policy가 다음 Action $A_{t+1}$을 고른다. 그다음부터의 기대 미래가 $q_\pi(S_{t+1},A_{t+1})$다.

뒤에서 SARSA의 Update target이 다음 모양으로 등장한다.

$$R_{t+1} + \gamma Q(S_{t+1},A_{t+1})$$

갑자기 만들어진 공식이 아니다. Action value의 Bellman expectation equation을 한 번의 실제 경험으로 근사한 것이다.

가장 좋은 Policy를 찾는 Bellman optimality equation

Bellman expectation equation은 정해진 Policy $\pi$가 얼마나 좋은지 계산한다. 최적 Policy를 찾으려면 다음 State에서 가능한 Action 중 가장 큰 값을 선택한다.

$$v_*(s) = \max_a \mathbb{E} \left[ R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t=s, A_t=a \right]$$

Action value는 다음과 같다.

$$q_*(s,a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1},a') \mid S_t=s, A_t=a \right]$$

두 번째 수식의 Target은 나중에 Q-Learning에서 그대로 다시 만난다.

$$R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a')$$

Expectation equation은 현재 Policy가 실제로 고를 다음 Action을 평균낸다. Optimality equation은 가능한 다음 Action 중 가장 큰 것을 고른다. 이 작은 차이가 On-policy인 SARSA와 Off-policy인 Q-Learning의 차이로 이어진다.

Dynamic Programming은 무엇을 알고 시작할까?

Dynamic Programming, 줄여서 DP는 복잡한 문제를 겹치는 작은 문제로 나누고 그 결과를 재사용하는 방법이다.

강화학습에서 DP를 사용하려면 MDP의 Model을 알고 있어야 한다.

• Transition probability $\mathcal{P}_{ss'}^a$
• Reward function $\mathcal{R}_s^a$

State $s$에서 Action $a$를 하면 어디로 갈 가능성이 있고 평균 Reward가 얼마인지 미리 알고 있다고 가정한다.

이 정보가 있으면 실제로 Environment를 여러 번 실행하지 않고도 모든 가능한 Next State를 합산해 Bellman backup을 수행할 수 있다.

Model을 안다는 조건이 강해 보이지만 DP는 이후 Algorithm의 기준점이 된다. MC와 TD가 경험 한 개로 무엇을 근사하는지 이해하려면 먼저 Model을 모두 알고 계산하는 DP의 모습을 보는 편이 좋다.

Policy Evaluation: 이 Policy는 얼마나 좋은가?

Policy Evaluation은 고정된 Policy $\pi$의 Value $v_\pi$를 구하는 과정이다.

처음 추정값 $V_0(s)$에서 시작해 모든 State를 반복해서 업데이트한다.

$$V_{k+1}(s) = \sum_a \pi(a \mid s) \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a V_k(s') \right]$$

$V_k$는 $k$번째 반복에서의 추정값이다. 오른쪽은 이전 반복의 값 $V_k$를 사용하고, 계산된 새 값은 $V_{k+1}$에 저장한다.

반복하면서 값의 변화가 충분히 작아지면 $V_k$가 $v_\pi$에 가까워졌다고 보고 멈춘다.

Policy Improvement: 더 좋은 Action으로 바꾸기

Policy의 Value를 알게 되면 각 State에서 한 Step 앞을 살펴보고 더 좋은 Action을 고를 수 있다.

$$\pi'(s) = \arg\max_a \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a v_\pi(s') \right]$$

현재 Policy의 Value를 기준으로 가장 좋아 보이는 Action을 고르는 Greedy improvement다.

Policy Evaluation과 Policy Improvement를 번갈아 반복하면 Policy Iteration이 된다.

흐름은 다음과 같다.

$$\pi_1 \xrightarrow{\text{evaluate}} v_{\pi_1} \xrightarrow{\text{improve}} \pi_2 \xrightarrow{\text{evaluate}} v_{\pi_2} \xrightarrow{\text{improve}} \cdots$$

더 이상 Policy가 바뀌지 않으면 모든 State에서 현재 Action이 이미 Greedy한 선택이라는 뜻이고, Optimal policy에 도달한다.

Value Iteration: 평가를 한 번만 하고 바로 개선하기

Policy Evaluation을 완전히 수렴시킨 뒤 Policy를 개선해야만 할까?

David Silver 강의에서는 평가를 한 번만 하고 바로 개선하는 극단적인 경우가 Value Iteration과 같다고 설명한다.

$$V_{k+1}(s) = \max_a \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a V_k(s') \right]$$

Policy를 명시적으로 저장해 평가하는 대신 Bellman optimality backup을 Value에 반복 적용한다.

둘 다 Model을 알고 있는 MDP에서 Optimal policy를 찾는 DP 방법이다. 차이는 Evaluation을 얼마나 오래 수행한 뒤 Improvement를 반영하는가에 있다.

모든 것을 계산하는 DP의 한계

DP는 개념이 명확하지만 조건이 있다.

1. Transition과 Reward Model을 알아야 한다.
2. 모든 State를 반복해서 훑을 수 있어야 한다.
3. State와 Action 수가 너무 크지 않아야 한다.

현실에서는 Robot이 미끄러질 확률을 정확히 모르거나, 가능한 이미지 State가 사실상 무한할 수 있다. 이때 모든 $s'$를 합산하는 Backup은 사용할 수 없다.

다음 단계는 가능한 결과를 전부 계산하지 않고, 실제로 경험한 Sample을 사용하는 것이다.

• Monte Carlo: Episode가 끝난 뒤 실제 Return을 Target으로 사용
• TD: 한 Step의 Reward와 Next State 추정값을 Target으로 사용

두 방법은 Model을 모르는 환경에서도 Value를 학습한다.

이번 글에서 기억할 것

이번 글의 핵심은 다음 한 줄이다.

Bellman Equation은 긴 미래를 즉시 Reward와 Discount된 Next State Value로 나눈다.

조금 더 나누면 다음과 같다.

1. $G_t=R_{t+1}+\gamma G_{t+1}$로 Return의 반복 구조를 볼 수 있다.
2. Bellman expectation equation은 정해진 Policy의 Value를 표현한다.
3. Bellman optimality equation은 다음 Action에서 $\max$를 사용한다.
4. Policy Iteration은 Evaluation과 Improvement를 번갈아 수행한다.
5. Value Iteration은 Bellman optimality backup을 반복한다.
6. DP는 Transition과 Reward Model을 알고 있어야 한다.

다음 글에서는 Environment의 Transition matrix를 모르는 상황으로 넘어간다. 가능한 미래를 모두 계산하는 대신 Episode를 직접 끝까지 경험하고, 실제 Return의 평균으로 Value를 배우는 Monte Carlo Prediction을 살펴볼 예정이다.

참고 자료

• David Silver, Lecture 2: Markov Decision Processes
• David Silver, Lecture 3: Planning by Dynamic Programming
• 서울대학교 DSBA 연구실, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition