[KMOOC 강화학습] Week 02-3 Overlapping & Recursive
해당 강의는 K-MOOC의 “강화학습의 수학적 기초와 알고리즘 이해” 수업을 수강하며 기록한 내용입니다. 강의는 링크에서 확인하실 수 있습니다.
동적계획법의 특징
- Optimal substructure
- Overlapping subproblems
- Principle of optimality
- Bellman Optimality Equation
- Backward Induction(Recursive)
문제 상황
돈을 벌고 쓰는 상황에서 T기간에서 각 시각별 효용(Utility) $U$에 대해 총 효용을 최대화하려면 매달 돈을 얼마나 쓸 수 있을까?
문제 정의
Assumption
$U(a) = a$
Constraint
- 내가 쓸 수 있는 돈의 양은 내가 가진 돈의 양에 제한된다.
- 이전 달의 잔여금에 따라 이번 달에 영향을 받는다.
☝ 즉 이전 단계의 의사 결정이 이후 수준의 의사결정에 영향을 끼친다!
문제 구조
t 시점에 $x_{t}$만큼의 자본을 소유하고 있을 때
⚡ 이전 단계의 의사결정은 이후의 의사결정에 영향을 끼치지 않으며 ⚡ 단지 자본 규모에 대해서만 의존적이다! ⚡ 의사 결정은 독립적이라고 가정 가능하다
문제 구조화
$v_{t} (x)$ : t 시점에서 자본 수준이 $x$일 때 남은 기간의 총 효용의 최대값
결국 계산하고 싶은 대상은 $v_{0}(x_{0})$
남은 1기간의 경우
이 문제에서는 마지막 달에서 총 효용의 최대값!
$v_{T-1}(x) = \max_{a\in [0, x]} U(a_{T-1}) = \max_{a\in [0, x]} a$
이는 선형 증가 함수의 형태를 가지게 되어 그렇기 때문에 $a=x$일 때 마지막 달의 총 효용이 최대화된다.
의사결정 규칙
$\delta_{T-1}^{*}(x) $ : (T-1) 시점의 자본수준이 $x$인 경우 얼만큼 지출할지 알려주는 함수
$\delta_{T-1}^{*}(x) = x $ : 마지막 달의 자본 그 만큼(x)사용하면 된다고 알려주는 것!
남은 2 기간의 경우
$v_{T-2}(x) = \max { U(a_{T-1}) + U(a_{T-2})} = \max_{a\in [0, x]} { U(a)+ v_{T-1}(\alpha (x-a)) }$
⚡ (T-2) 시점에서 a만큼 돈을 쓴다고 할 때 ⚡ (T-1) 시점에서 남은 돈은 $\alpha (x-a)$
☝ 즉, 첫번째 항은 (T-1) 시점에서 a만큼 돈 썼을 때의 효용이며, 두번째 항은 (T-1) 시점에서 남은 비용으로 얻은 효용
그 결과 가정에 의해
$v_{T-2}(x) = \max_{a\in [0, x]} { a + \alpha(x-a) } = \max_{a\in [0, x]} {(1-\alpha) a + \alpha x } = \alpha x$
이며 즉 a=0일 때 최대가 된다.
☝ $\delta_{T-2}^{*}(x) = 0 $ : (T-2)일 때 돈을 안써야 한다는 것이 되고 그럴 때 최대 효용은 $\alpha x$ 가 된다.
일반화
총 효용 규칙
- $v_{t}(x)=\alpha^{T-t-1}x$
의사 결정 규칙
- $\delta_{t}^{*}(x) = 0 , t=0,1,…,T-2$
- $\delta_{T-1}^{*}(x) = x $
☝ (T-2) 시점 이전에는 자본수준이 x라면 돈을 쓰지 말고, 마지막 단계에서 다 써라!
확정적 동적 계획법
- 순차적인 의사결정 방식이기 때문에 의사결정 내리는 시점(stage, decision epoch)이 여러단계다
- 이 때 사용하는 정보는 상태(State) : 각 달의 자본 수준
- 이 상태를 바탕으로 의사결정(action)한다. : 지출 정도
⚡ 현재의 지출정도(행동)가 다음 달의 초기 자본의 수준(상태)을 결정한다.
☝ 확정적이라는 말은, 어떤 상태에서 행동이 그 다음 상태를 확정적으로 결정하기에 확정적 동적 계획법이라고 부른다.
평가지표와 보상
결국 상태는 이전 단계의 결과로 결정되는 일종의 함수의 형태로 정의되기에 의사결정에서는 일종의 평가지표가 필요하다.
동적 계획법에서는 보상이 바로 이 역할을 한다.
그렇기 때문에 각 단계별에서는 행동을 하고 보상을 받는 과정이 반복되어 어떤 의사결정을 할지 풀게 되기 때문에 순차적 의사 결정 문제라고 불리게 된다.
이 과정에서 보상의 총합이 바로 평가지표가 될 것이고 이를 최대화 하고자 한다.
관계식
$r_{t} = r_{t}(s_{t},a_{t})$ : 현재 보상은 현재 상태와 현재 행동의 함수
$s_{t+1} = f_{t}(s_{t},a_{t})$ : 다음 상태는 현재 상태와 현재 보상의 함수
$\delta_{t}(s_{t}) = a_{t}$ : 각 단계에서 모든 가능한 상태에 대해 어떤 의사결정을 내릴지 결정하는 함수(Decision Rule) 혹은 그 집합(Policy )
의의
“보상합의 최대화를 위해 어떤 행동을 취해야 하는가?”를 풀기 위해 최적의 규칙 혹은 정책을 구하고자 하는 것
일반화된 방법론
하위 문제 정의
- 특정 상태에서 한 상태를 가정
- 이후의 모든 의사 결정은 현 단계 이전의 의사 결정에 영향을 주지 않아 독립적
☝ 이후의 의사결정은 이전의 의사결정이 영향을 끼치긴 하지만, 현재 상태의 정보가 주어져 있다면 사실 현재 상태의 정보가 이전 상태의 의사 결정들을 다 대체하게 된다~!!
총 보상합 정의
$v_{t}^{*} (s_{t}) =\max { r_{t} + r_{t+1} + \cdots + r_{T-1} }$
이 때 계산하고자 하는 것은 $v_{0}^{*} (s_{0})$.
주요 논지
overlapping subproblems
결국 마지막 상태에서 총 보상합($v_{t}^{*} (s_{t})$)을 정의하고 역순으로 계산해 나간다.
Bellman Optimality Equation
$v_{t}^{} (s_{t}) =\max_{ a_{t} } { r_{t} (s_{t^{‘}}, a_{t}) + v_{t+1}^{} (f_{t} (s_{t^{‘}}, a_{t}) ) }$
현재의 상태 $s_{t}$가 주어진 상태에서 남은 기간에서 총 효용의 최대화를 구하고자 하며
어떤 행동 ($a_{t}$)을 취하게 되면 보상($r_{t}$)을 얻게 되고, 그 행동에 의해 남은 기간에서의 총 효용을 합친 최대값을 현재 상태에서의 최대 보상합으로 구하게 된다!
principle of optimality
☝ 현재의 총 보상합이 포함된 다음 시점의 총보상합의 최적해를 활용해서 현재 상태의 총 보상합을 찾게 되는 것이다.
즉 다음단계의 총 보상합의 최대값을 알아야 한다.
역진 귀납법(Backward Induction)
- 다음 단계의 총 보상합을 알아야 하기 때문에 역순으로 귀납법을 사용한다는 것
- 다만, 모든 가능한 상태에서 계산하여 총 보상합의 최대값을 구해야 하고,
- 그 시점을 기준으로 역순으로 찾아가는 방식을 사용해야 한다.
댓글남기기