2.2 동적계획법, 중첩되는 부분문제와 역진귀납법 : 강화학습의 수학적기초와 알고리즘의 이해

강화학습의 수학적기초와 알고리즘의 이해 강의를 보고 정리한 글임을 밝힙니다.

2.1 문제해결전략과 동적계획법 : 강화학습의 수학적 기초와 알고리즘의 이해

위의 링크와 이어지는 포스트 입니다.

(확정적) 동적 계획법

순차적 의사결정을 내리는 알고리즘

 

확정적(deterministic)의 의미

→ 내가 어떤 상태에서 어떤 액션을 취하면, 그 다음 단계의 상태가 ‘확정적’으로 결정이 되는 경우

• 단계(Stage), 의사결정시점(decision epoch) : 의사결정을 내리는 시점
• 상태(State) : 의사결정을 내릴 때 필요한 정보
• 행동(Action) : 상태(State)를 바탕으로 의사결정

 

< 일반적인 문제 해결 방법론 >

1. Optimal 구조 기반 Overlapping(중첩되는) 하위문제 정의

2. principle of optimality(최적화 원리)를 만족하는 벨만의 최적 방정식 활용

3. 역진 귀납법(Backward induction)을 통해 역순으로 문제 해결

 

이 방법론을 아래의 그림과 함께 자세히 살펴보자.

 

순차적 문제

 

다음 시점, 시스템의 상태가 다음과 같은 f() 함수를 통해서 함수적으로 결정이 되는 경우 아래처럼 식을 쓸 수 있다.

$$ s_{t+1} = f_t(s_t + a_t) $$

 

각 단계에 보상 개념을 도입하여 어떤 상태에서 어떤 행동을 하면 보상을 준다고 하자.

$$ r_t = r_t(s_t,a_t)$$

 

그렇다면 어떤 평가기준을 가지고 각 단계에서 a라는 의사결정을 내릴것인가?

 

 

< 해결하고자 하는 문제 >

→ 초기 상태 $s_0$가 주어진 상황에서 T 기간에 걸친 총 보상합을 최대화하기 위한 일련의 행동들을 결정하는 것

$$ r_0 + r_1 + \cdots + r_{T-1} $$

Decision Rule : 각 단계에서 가능한 모든 상태 중 최적의 행동을 찾는 것을 정의한 함수

$$ \delta_t (s_t) = a_t $$

Policy(정책) : 모든 단계에서의 Decision Rule의 집합

$$ \pi = \left\{ \delta_t \right\}_{t=0,1, \dots , T-1} $$

 

 

보상합 최대화를 위해 어떤 행동(action)을 취해야 하는가?

 

→ 최적의 규칙(정책) 탐색해야

 

중첩되는 부분 문제(overlapping subproblems)

특정 단계에서, 한 상태로 부터 이후 남은 단계 들에서 이루어진 모든 의사결정들은 현 단계 이전의 의사결정에 영향을 주지 않는다 → 독립성을 가진다.

 

시점 t에서, t시점 이후의 총 보상 합을 최대화 하는 부분 문제를 아래와 같이 정의하면

$$ v_t^*(s_t) = \underset{a_t, a_{t+1},\ \dots, \ a_{T-1}}{max} \left\{ r_t + r_{t+1} + \cdots +r_{T-1} \right\} $$

최종적으로 구해야 하는 식은 $v_0^*(s_0)$이 될 것이다.

아래 방식으로 중첩되는 것을 확인할 수 있다.

위와 같이 정의한 문제를 아래와 같은 재귀적인 식으로 도출해 낼 수 있다.

 

< principle of optimality 의미 >

$v_t$가 포함된 $v_{t+1}$문제의 최적해를 활용하여 $v_t$의 최적해를 구하는 성질이 만족하면
→ 벨만 방정식을 통해서 최적해 도출 가능

 

위의 최적화 원리를 만족하므로 아래 식을 벨만 최적 방정식 (Bellman Optimality Equation) 이라고 한다.

 

벨만 최적 방정식

 

이 식은  t 시점에 $s_t$가 주어진 상황에서 $a_t$라는 action을 취했을 때 t 시점부터 남은 기간 동안 얻을 수 잇는 총 효용의 최대값을 설명한다.

 

역진 귀납법(Backward induction)

가장 마지막 단계 문제부터 순차적으로 문제를 해결하는 방법

 

➢ 모든 가능한 $s_{T-1}$에 대해 $v_{T-1}^*(s_{T-1}) = \underset{a_{T-1}} {max} \ r_{t-1}$을 계산한다.

➢ 단계 t = T-2, T-3, $\dots$ , 1 순서로 모든 가능한 $s_t$에 대해 $v_t^*(s_t)$를 계산한다

$$ v_t^*(s_t) = \underset{a_t} {max} \left\{ r_t(s_t,a_t) + v_{t+1}^*(f_t(s_t,a_t)) \right\} $$

➢ 초기상태 $s_0$에 대해, $v_0^*(s_0) = \underset{a_0} {max} \left\{ t_0(s_0,a_0) + v_1^*(s_1) \right\}$

→ 이는 $v_0^*(s_0) = \underset{a_0,a_1, \dots, a_{T-1}}{max} \left\{ r_0 + r_1 + \cdots + r_{T-1} \right\}$와 동일