[RL] MDP를 알 때 플래닝

MDP를 알 때 플래닝

[RL] MDP를 알 때의 플래닝

바닥부터 배우는 강화 학습 | 04. MDP를 알 때의 플래닝

그리드 월드 MDP 상황을 예로
정책 𝜋가 주어졌을 때, 각 상태의 밸류를 평가하는 Prediction과
최적의 정책 함수를 찾는 Control 문제 푸는 방법을 배운다.
플래닝 = MDP에 대한 모든 정보를 알 때, 정책 개선 과정

본 목차의 내용을 적용하려면

- 작은 문제 (상태 집합 S, 액션 집합 A의 크기가 작은 경우)
- MDP를 알 때

두 가지의 조건을 만족하는 상황일 때만 가능
작은 문제이므로 *(테이블 기반 방법론)에 기반함

*테이블 기반 방법론
: 모든 상태 s 혹은 상태와 액션의 페어 (s,a)에 대한
테이블을 만들어 값을 기록해놓고, 그 값을 조금씩 업데이트하는 방식

밸류 평가하기 - 반복적 정책 평가

4방향 랜덤이라는 정책 함수 𝜋
각 상태 s에 대한 가치함수 v(s)를 구하는 전형적인 Prediction

반복적 정책 평가로 해결할 수 있음
이는 테이블의 값들을 초기화한 후,
밸만 기대 방정식을 반복적으로 사용하여
테이블에 적어 놓은 값을 조금씩 업데이트 해나가는 방식

또한, MDP에 대한 모든 정보를 알 때 사용 가능하다.

보상은 어느 액션을 하든 -1
r(s, a) = -1로 모든 액션에 대해 고정적
또한, 환경에 확률적인 요소가 없기 때문에 P(s, a, s')은 모두 1
(감마를 1로 두어 처리하겠음)

1. 테이블 초기화

먼저 테이블을 초기화 함 (어떤 값이든 상관 X)

현재는 아무 의미가 없는 값이나,
반복적 과정을 거치며 실제 각 상태의 가치에 해당하는 값으로 수렴

2. 테이블 업데이트

16개의 값 중, 한 개의 값이 어떻게 업데이트하는지 설명
파란색으로 칠해진 s5의 상태를 보자

MDP를 알고 있으므로,
이 상태의 다음 후보가 노란색(s1, s4, s6, s9)인 것을 알고 있다.

현재 상태와 다음 상태의 밸류 사이 관계식인
밸만 방정식 2단계 수식을 적용해보자

밸만 방정식 2단계 수식

여기서 정책 함수는 4방향으로 균등하게 랜덤하므로
𝜋(a|s)는 모든 액션에 대해 각각 0.25이다.

이를 토대로 실제 값을 대입해 다음을 구할 수 있다.
s 상태에서 a 행동, 즉 보상 = -1

즉, s5 자리를 -1.0으로 업데이트

왜 임의로 정한 0의 값을 이용했는데,
현재 상태 값을 업데이트하는게 더 정확할까 ?

우리는 다음 상태의 값만 갖고 업데이트 하는 것이 아닌,
보상이라는 실제 환경이 주는 정확한 시그널을 섞어 업데이트 함

즉, 처음에는 무의미 -> 점차 실제 값에 가까워짐

또한, 처음의 값이 항상 엉터리는 아님
오른쪽 맨 아래의 '종료 상태'의 경우 가치가 0으로 되어 있는데,
종료 상태 입장에서는 그 뒤의 미래라는 것이 존재 X
-> 정확한 값 ...?

마지막 종료 상태에 인접한 상태들의 경우,
더 유의미한 시그널로 업데이트

3. 모든 상태에 대해 2의 과정을 적용

마지막 상태를 제외한 15개 상태를 업데이트

모든 값을 업데이트하고 나면 비로소 한 바퀴를 돈 것,
종료 상태를 제외한 모든 상태의 값이 -1로 업데이트 됨

4. 앞의 2~3 과정을 계속해서 반복

한 번 테이블의 모든 값을 업데이트하는 과정을 여러 번 반복
k = 몇 번 반복했는가

위처럼 반복하면 각 상태의 값이 어떤 값에 수렴하게 됨
-> 해당 상태의 실제 밸류가 됨

정리

지금까지 우리는 정책 𝜋가 주어졌을 때
각 상태의 밸류를 계산하는 법을 익힘

MDP에 대한 정보를 알고, 그 크기가 충분히 작다면
그 어떤 정책함수에 대해서도 해당 정책함수를 따랐을 때
각 상태의 밸류를 구할 수 있게 됨

최고의 정책 찾기 - 정책 이터레이션

정책 이터레이션
: 정책 평가와 정책 개선을 번갈아 수행하여
정책이 수렴할 때까지 반복하는 방법론

우리가 파란색 상태인 s5에 있다고 생각하자
s5에서는 동쪽 혹은 남쪽의 a 행동이 최적이다.

즉 다음과 같은 정책 𝜋'이 나오게 된다.

해당 𝜋'은 원래의 정책 𝜋보다 나은 정책이다.
그럼 원래 정책은 ?

이러한 정책을 그리디 정책 이라 부른다.

*그리디: 탐욕스럽다는 뜻으로, 먼 미래를 보지 않고
눈 앞의 이익을 최대화하는 선택

s5 상태에서의 그리디 정책이 s5에서의 최적 정책이 됨

그리디 정책을 통해 위와 같은 그림이 그려진다.

랜덤 상태에서 랜덤 정책의 가치를 평가했을 뿐인데
s5에서의 더 나은 정책을 알게 되었다.
이를 모든 상태에서 보아도 더 나은 정책이 됨

그러나, 𝜋'이 최적 정책과 일치하는 경우는 많지 않음
대개는 이전 정책에 비해 소폭 향상되는 정도

𝜋'이 𝜋에 비해 개선 == 정책 이터레이션의 핵심

평가와 개선의 반복

정책 이터레이션은 정책 평가와 정책 개선 두 단계로 구성

정책 평가: 고정된 정책 𝜋에 대해 각 상태의 가치를 구함
= 반복적 정책 평가 = 밸류 평가

정책 개선: 정책 평가의 결과에 따라 새로운 정책 𝜋'를 생성
= 그리디 정책 생성

반복적 정책 평가와 정책 개선을 진행하면
정책과 가치가 변하지 않는 단계에 도달하게 됨
-> 최적 정책과 최적 가치

그리고 새로 생성된 𝜋'에 대해 다시 정책 평가를 진행
즉, 정책의 평가와 개선을 반복

그리디 정책 𝜋'는 기존 정책 𝜋에 비해 더 나은 정책임이 보장

정책 평가 부분 간소화하기

위 루프에서 연산을 가장 많이 필요로 하는 단계 = '정책 평가'

정책 평가 = 고정된 정책 𝜋에 대해 각 상태의 가치를 구함
= 반복적 정책 평가 = 밸류 평가
평가 단계에서는 반복적 정책, 즉 여러 스텝이 필요함

과연 끝까지 평가를 해야할까 ?

-> 우리의 목적은 최고의 정책을 찾는 것이지,
정확한 가치를 평가하는 것은 아니다.

실제로 정책 이터레이션에서는 가치 함수가
오로지 그리디 정책을 찾는 데만 쓰일 뿐
테이블에 적힌 구체적 값이 사용되지는 않음

6번만 업데이트해도 그리디 정책이 이미 최적 정책에 도달함
심지어 극단적으로는 한 번만 업데이트 해도 됨

그리디 정책이 현재의 정책과 조금이라도 다르기만 하면
일단 '개선'할 수 있고,
'개선'하여 새로운 정책을 얻으면 이전의 가치 테이블은 버림

극단적으로 정책 평가 단계에서 k=1인 경우

위 그림은 정책 평가를 1단계만 수행하고,
정책 개선을 수행하는 경우의 정책 이터레이션이다.

빠르게 정책 평가와 정책 개선이 가능하고,
빠르게 최적 정책을 찾을 수 있게 된다.

정책평가 단계에서 가치가 수렴할 때까지
과정을 반복하지 않아도 됨
-> 간결해진 정책 이터레이션으로 최적 정책 확보

최고의 정책 찾기 - 밸류 이터레이션

밸류 이터레이션
: 오로지 최적 정책이 만들어내는 최적 밸류 하나만 본다.
이는 벨만 방정식을 이용해, 단 번에 최적의 정책을 찾는다.

1. 테이블 초기화
-> 정책 이터레이션에서는 해당 평가 단계에서 사용하는
정책 𝜋의 밸류였으나,
위 테이블에서는 최적 정책 𝜋*의 밸류를 뜻함

s5 값을 업데이트

밸만 최적 방정식 2단계를 사용하여
s5의 최적 가치 v*(s)를 계산

v∗(s) = max(−1+1.0∗0,
                        −1+1.0∗0,
                        −1+1.0∗0,
                        −1+1.0∗0)
                        = -1.0

모든 상태 s에 대해 밸만 최적 방정식으로 업데이트한 결과

테이블의 값들이 수렴하였고,
이 값은 각 상태의 최적 밸류이다.

위 상황에서 최적 밸류를 알면 최적 정책을 곧바로 얻을 수 있음

최적 밸류를 높이는 방향으로 그리디 정책을 시행하면
그것이 최적 정책이기 때문