1) 마르코프 결정과정 (Markov Decision Process : MDP)
: 마르코프 보상과정(MRP)에 행동을 추가한 과정
- MDP <$S$,$\cal{A}$,$P,R,\gamma$>인 튜플이다
- $S$ : 유한한 상태의 집합
- $\cal{A}$ : 유한한 행동의 집합
- $P$ : 상태천이행렬, $P_{ss'}^{a} = P[S_{t+1} = s' | S_t = s, A_t = a]$
-> $P_{ss'}^{a}$ : 행동 a가 추가됨으로써 3차원형태 (행동의수, $s_t$상태의 수, $s_{t+1}$상태의 수)
- $R$ : 보상함수, $R : S \times \cal{A} \rightarrow \mathbb {R}$ -> 2차원 matrix
- $\gamma$ : 감소율
"기존의 MRP에 비해 차원이 증가"
여기부터는 새로운 개념이 나온다. 헷갈릴 수 있으니 정책함수부터 잘 숙지해둬야 한다.
2) 정책함수 (Policy function)
: 정책함수는 $\pi$로 나타낸다. $\pi$ : 현재 상태에서 수행 할 행동의 확률분포
$$ \pi(a|s) = P(A_t = a | S_t = s)$$
- 수식 그대로 해석하면 현재 t시점의 상태가 s 일때, 현재의 행동 a가 나타날 확률이다.
- Markov Property를 가정하므로, 현재 상태만 가지고 의사결정을 해도 충분
정책함수가 강화학습에서는 아주 중요한 역할을 한다.
왜냐? 다음 행동을 결정하는 것이 정책함수이기 때문이다.
좋은 $\pi$를 가지고 있다는 것은 곧 최대한 많은 보상을 얻을 수 있다는 말이다.
3) MDP, MRP 와 MP의 관계
MDP<$S,\cal{A},P,R,\gamma$> 와 정책 $\pi$가 결정 됐을 때,
- $S_0, S_1, S_2, ...$는 마르코프 과정이다.
- $S_0, R_1, S_1, R_2, S_2, ...$는 MRP <$S$,$P^{\pi}$,$R^{\pi}$, $\gamma$>이다.
$$P_{ss'}^{\pi} = \sum _{a\in \cal{A}}\pi (a|s)P_{ss'}^{a}$$
$$R_{s}^{\pi} = \sum_{a \in \cal{A}} \pi(a|s)R_{s}^{a}$$
4) MDP의 가치함수
1. 상태 가치함수 :
$$ V_{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s] $$
- $t$시점에서 상태 $s$일 때, 정책 $\pi$를 따른다면 얻을 미래의 가치의 감가 총합
2. 행동 가치함수 :
$$ Q_{\pi}(s,a) = \mathbb {E}_{\pi}[G_t | S_t = s, A_t = a]$$
- $t$시점에서 상태 $s$일 때, $a$라는 행동을 취한 후 정책 $\pi$를 따른다면 얻을 미래의 가치의 감가 총합
※ TMI : Q - Learning의 Q가 바로 행동 가치함수이다.
※ 참고 : 미래의 가치의 감가 총합 $G_t$
5) Bellman 기대값 방정식
1. 상태 가치함수 :
2. 행동 가치함수 :
잘 보면 가치상태함수와 행동가치함수의 Bellman Expectation Equation은 구조가 동일하다.
여기서, V와 Q의 관계를 살펴보면 다음과 같다.
-> 현재 상태 s에서 각각의 행동 a를 확률이 $\pi(a|s)$ 이므로, 각 상태와 행동에 대한 가치 $Q_{\pi}(s,a)$ 를 $\pi(a|s)$ 로 평균을 내면 현재 상태의 가치 $V_{\pi}$ 가 된다.
-> 현재 상태 s에서 a를 행동 -> $R_{s}^{a}$ 만큼의 보상 획득 -> 확률적으로 어떤 $s'$ 들에 도달 -> $s'$ 에서 각각의 가치는 $V_{\pi}(s')$ -> 그 가치들의 기대값은 각각의 $s'$에 대한 확률 $P_{ss'}^{a}$과 가치$V_{\pi}(s')$을 활용한 평균값 -> 그 후 $\gamma$만큼 감가
말이 어렵게 느껴질 수 있지만 기댓값의 성질과 MDP의 성질을 잘 활용하면 쉽게 해석 할 수 있다.
그림5. 는 상태 가치함수와 행동 가치함수를 재귀식의 형태로 만든 식인데 참고하면 될 것 같다.
이를 또다시 행렬표현으로 변형하여 직접해를 구하면
$$ v = R^{\pi} + \gamma P^{\pi} v$$
$$ v = (I - \gamma P^{\pi})^{-1} R^{\pi}$$
의 형식이 된다.
좋은 $\pi$를 얻는다면 최대한 많은 보상을 얻을 수 있다는 것은 알았다.
그렇다면 무엇이 좋은 $\pi$의 기준인가?
무엇이 최적의 $\pi$를 결정지을까?
6) 최적 가치함수(Optimal Value Function)
1. 최적 상태 가치 함수 :
$$ V^{*}(s) = max_{\pi}V_{\pi}(s)$$
- 존재하는 모든 정책들 중 모든 상태 s에서 가장 높은 $V_{\pi}(s)$를 만드는 $\pi$를 적용했을 때 얻는 $V_{\pi}(s)$
2. 최적 행동 가치 함수 :
$$Q^{*}(s,a) = max_{\pi} Q_{\pi}(s,a)$$
- 존재하는 모든 정책들 중 모든 상태/행동조합 (s,a)에서 가장 높은 $Q_{\pi}(s,a)$를 만드는 $\pi$를 적용했을 때 얻는 $Q_{\pi}(s,a)$
7) 최적 정책 (Optimal Policy)
정책 함수 $\pi$간의 대소관계를 다음과 같이 정의한다.
$$ \pi' \geq \pi \leftrightarrow V_{\pi'}(s) \geq V_{\pi}(s) $$
<최적 정책 정리>
- 어떠한 MDP에 대해서도 다음이 성립한다.
- 최적 정책들은 $\pi^*$가 존재하며, 모든 존재하는 정책 $\pi$에 대하여 $\pi^* \geq \pi$를 만족한다.
- 최적 정책들은 최적 상태 가치함수를 성취한다. ($V_{\pi^{*}}(s) = V^{*}(s)$)
- 최적 정책들은 최적 행동 가치함수를 성취한다. ($Q_{\pi^{*}}(s,a) = Q^{*}(s)$)
8) 최적 행동함수$Q^{*}(s,a)$로 최적 정책($\pi^{*}$) 중 하나를 찾는법
$\underset{a \in \cal{A}}{argmax}Q^{*}(s,a)$는 $Q^{*}(s,a)$를 최대화하는 $a$를 반환한다.
이에 따라 위 식을 해석하면 상태 $s$가 주어진 정책함수에서 $Q^{*}(s,a)$를 최대화 하는 $a$에 대한 정책함수 값만 1로 두고 나머지 action $a$에 대해서는 모두 0으로 두는 것이다.
그러면 agent가 상태 s에 도달 했을 때, 다음행동은 무조건 이전에 정해진 $a$로만 행동하는 것이다.
9) Bellman 최적 방정식 (Bellman Optimality Equation : BOE)
* 주의 : 이전에 본 Bellman 기대 방정식(BEE)과 다른 방정식이다
기존 BEE의 $\pi$ 자리에 $\pi^{*}$를 대입한 형식
이 또한 마찬가지로 재귀형식으로 만드는 것이 가능하다.
10) 중요! 'BOE 직접해'는 존재하지 않는다.
우선 BOE는 선형방정식이 아니다. (Optimal 한 값을 구하기 위해 차원수를 하나씩 줄여줬으므로)
즉, MP / MRP의 글의 마지막 부분에 나오는 선형방정식 계산을 통한 직접해를 구하는 것이 불가능 한 것이다.
대신 이 문제를 반복적 알고리즘 ex) PE, PI, VI, Q-Learning, SARSA 등 을 이용하여 계산 할 수 있다.
정리하기)
1. 정책함수 $\pi(a | s)$ : 현재상태 s에서 행동 a를 수행할 확률
2. 상태 가치함수 $V_{\pi}(s)$ : 현재상태가 s이고 정책함수 $\pi$를 따를 때 미래에 얻을 가치의 감가 총합
3. 행동 가치함수 $Q_{\pi}(s,a)$ : 현재상태 s와 행동 a가 정책함수 $\pi$를 따를 때 미래에 얻을 가치의 감가 총합
4. Bellman 기대값 방정식 (Bellman Expectation Equation : BEE)
: 직접해를 가진다. $V_{\pi}$와 $Q_{\pi}$는 서로 관계가 존재하며 둘을 알고 있으면 각각에 대한 재귀식을 만들 수 있다.
5. 최적 가치함수 $V^{*}$ , $Q^{*}$
6. 최적 정책함수 $\pi^{*}$ : $Q^{*}$를 이용하여 구할 수 있다.
7. 최적 가치함수와 최적 정책함수는 서로 관계가 존재
8. Bellman 최적 방정식 (Bellman Optimality Equation : BOE)
: 직접해를 가지지 않는다. BEE의 $\pi$자리에 $\pi^{*}$를 대입한 방정식
내 생각 :
수식투성이에 글로만 설명을 해놓다 보니 이번 챕터는 상당히 이해하기가 어려울 것 같다.
하지만 뒤에 나오는 Learning기법을 이해하기 위해서는 반드시 알고 있어야 하는 개념이므로 이해가 될 때까지 읽어서 꼭 익히는 것이 좋다고 생각한다.
특히 가치함수, 행동함수, 정책함수의 관계도 눈여겨 봐야할 부분이다.
참고자료 :
강화학습 A-Z 강의노트
'강화학습 강의 복습노트' 카테고리의 다른 글
| Part2 - 4. 비동기적 동적계획법 (0) | 2020.12.23 |
|---|---|
| Part2 - 3. 동적계획법 (Dynamic Programming) (0) | 2020.12.23 |
| Part2 - 1. MP, MRP (0) | 2020.12.21 |
| Part1 - 1. 강화학습의 기본개념 (0) | 2020.12.21 |
| 0. 강화학습 복습노트를 시작하기 전에 (1) | 2020.12.20 |
