�ݺ�ߣ

1. 몬테카를로 예측
2. 시간차 예측
3. 살사
4. 큐러닝

강화학습은 환경의 모델을 몰라도
환경과의 상호작용을 통해 최적 정책을 학습한다.
에이전트는 환경과의 상호작용을 통해
주어진 정책에 대한 가치함수를 학습할 수 있는데,
이를 예측이라고 한다.
또한 가치함수를 토대로 정책을 끊임없이 발전시켜 나가서
최적 정책을 학습하는 것이 제어이다.

예측
몬테카를로 예측
시간차 예측
제어 살사 (시간차 제어)
살사의 한계를 극복
큐러닝
(오프폴리시 제어)

강화학습은 환경의 모델 없이 환경이라는
시스템의 입력과 출력 사이의 관계를 학습한다.
이때 입력은 에이전트의 상태와 행동이고 출력은 보상이다.
강화학습은
1. 일단 해보고
2. 자신을 평가하며
3. 평가한 대로 자신을 업데이트하며
4. 이 과정을 반복한다.
강화학습에서는 계산을 통해서 가치함수를 알아내는 것이 아니라
에이전트가 겪은 경험으로부터 가치함수를 업데이트 한다.

정책 이터레이션에서 정책 평가는 현재 정책을 따랐을 때
참 가치함수를 구하는 과정이다.
강화학습에서는 이 과정을 "예측"이라고 한다.
또한 다이내믹 프로그래밍에서는 정책 평가와 정책 발전을 합친 것을
정책 이터레이션이라고 불렀지만
강화학습에서는 예측과 함께 정책을 발전시키는 것을
"제어"라고 부른다.

몬테카를로 근사
몬테카를로라는 말은 "무작위로 무엇인가를 해본다"는 의미이다.
근사라는 것은 원래의 값은 모르지만 "샘플"을 통해
"원래의 값에 대해 이럴 것이다"라고 추정하는 것이다.
몬테카를로 근사의 특성 중 하나는 무한히 반복했을 때
원래의 값과 동일해진다는 것이다.
(종이의 면적을 안다고 했을때 그 종이에 그려진
원의 넓이를 추정하는 문제를 생각해보자.
종이에 점을 무작위로 무수히 많이 찍는다.
전체 찍은 점들 중에서 원 안에 들어가 있는 점의 비율을 구하면
이미 알고 있는 종이의 면적을 통해 원의 넓이 값을 추정할 수 있다.
즉 찍은 점의 비율로 원의 넓이를 근사하는 것이다.
원의 넓이를 구하는 방정식을 몰라도 이 방식을 통해
원의 넓이를 구할 수 있다는 점이 장점이다.)

샘플링과 몬테카를로 예측
정책 이터레이션의 정책 평가 과정에서
몬테카를로 근사를 이용해 가치함수를 추정해보자
원의 넓이를 추정할 때는 점이 하나의 샘플이며
점을 찍는 것이 "샘플링"이다.
가치함수를 추정할 때는 에이전트가 한 번 환경에서
에피소드를 진행하는 것이 샘플링이다.
이 샘플링을 통해 얻은 샘플의 평균으로 참 가치함수의 값을 추정한다.
이때 몬테카를로 근사를 사용하는 것을 몬테카를로 예측이라고 한다.

몬테카를로 예측을 통한 가치함수 추정의 과정은 다음과 같다
샘플링 가치함수 추정평균
+ =

벨만 기대 방정식을 계산하려면 조건이 필요했었다.
바로 환경의 모델인 보상과 상태 변환 확률을 알아야 하는 것이다.
이것은 마치 원의 넓이를 구할 때 원의 넓이의 방정식을
알아야 하는 것과 마찬가지이다.
몬테카를로 예측에서는 환경의 모델을 몰라도
여러 에피소드를 통해 구한 반환값의 평균을 통해 가치함수를 추정한다.
위 수식은 여러 번의 에피소드에서 s라는 상태를 방문해서 얻은
반환값들의 평균을 통해 참 가치함수를 추정하는 식이다.
N(s)는 싱태 s를 여러 번의 에피소드 동안 방문한 횟수이다.
G_i (s)는 그 상태를 방문한 i번째 에피소드에서 s의 반환값이다.
s를 방문했던 에피소드에 대해 마침 상태까지의
반환값을 평균내는 것이다.

현재 정책에 따라 무수히 많은 에피소드를 진행해 보면
현재 정책을 따랐을 때 지날 수 있는
모든 상태에 대해 충분한 반환값들을 모을 수 있다.
따라서 각 상태에 대해서 모인 반환값들의 평균을 내면
상당히 정확한 가치함수의 값을 얻을 수 있다.

n개의 반환값을 통해 평균을 취한 가치함수를 V_(n+1)이라고 해보자.
추정된 가치함수 V_(n+1)는 현재 받은 반환값 G_n과
이전에 받았던 반환값의 합 를 더한 값의 평균이다.

앞의 식에서 이전 반환값들의 합에 (n-1)을 곱하고 나눠보자
는 이전의 가치함수 이다.
따라서 수식을 정리해보면
)
위 식을 정리하면
)

어떤 상태의 가치함수는 샘플링을 통해
에이전트가 그 상태를 방문할 때마다 업데이트하게 된다.
원래 가지고 있던 가치함수 값 V(s)에 1/n(G(s)-V(s))를 더함으로써
업데이트 하는 것이다.
다음은 몬테카를로 예측에서 가치함수의 업데이트 식이다.
G(s)-V(s)를 오차라고 하며, 1/n은 스텝사이즈로서 업데이트할때
오차의 얼마를 가지고 업데이트할지 정하는 것이다.
이때 스텝사이즈가 1이라면 G(s)가 기존의 V(s)를 대체하게 된다.
일반적으로 스텝사이즈는 α로 표현한다.
이 값이 너무 크면 수렴하지 못하고 너무 작으면 수렴의 속도가 느리다.
모든 강화학습 방법에서 가치함수를 업데이트하는 것은
모두 위 식의 변형일 뿐이므로 이 식을 정확히 이해해야 한다.

가치함수 입장에서 업데이트를 통해 도달하려는 목표는 반환값이다.
가치함수는 이 목표로 감으로써 자신을 업데이트하는데
한 번에 목표점으로 가는 것이 아니고
스텝사이즈를 곱한 만큼만 가는 것이다.
몬테카를로 예측에서 에이전트는 이 업데이트 식을 통해
에피소드 동안 경험했던
모든 상태에 대해 가치함수를 업데이트한다.
어떠한 상태의 가치함수가 업데이트될수록
가치함수는 현재 정책에 대한 참 가치함수에 수렴해간다.
에이전트는 마침 상태에 갈 때까지 아무것도 하지 않는다.
마침 상태에 도착하면 에이전트는
지나온 모든 상태의 가치함수를 업데이트한다.
에피소드 동안 방문했던 모든 상태의 가치함수를 업데이트하면
에이전트는 다시 시작 상태에서부터 새로운 에피소드를 진행한다.
이러한 과정을 계속 반복하는 것이 몬테카를로 예측이다.

강화학습에서 가장 중요한 아이디어 중 하나가 바로 시간차이다.
몬테카를로 예측의 단점은 실시간이 아니라는 점이다.
가치함수를 업데이트하기 위해서는
에피소드가 끝날 때까지 기다려야 한다.
또한 에피소드의 끝이 없거나 에피소드의 길이가 긴 경우에는
몬테카를로 예측은 적합하지 않다.
몬테카를로 예측에서와 같이 에피소드마다가 아니라
타임스텝마다 가치함수를 업데이트하는 방법이 시간차 예측이다.

몬테카를로 예측에서는 다음과 같은 가치함수의 정의를 이용하는데
기댓값을 계산하지 않고 샘플링을 통해 예측했었다.
시간차 예측에서는 다음과 같은 가치함수의 정의를 이용한다
기댓값을 계산하지 않고 값을 샘플링해서
그 값으로 현재의 가치함수를 업데이트한다.
가치함수의 업데이트는 실시간으로 이뤄지며,
몬테카를로 예측과는 달리
한 번에 하나의 가치함수만 업데이트한다.

다음 식은 시간차 예측에서 가치함수를 업데이트하는 식이다.
) : 업데이트의 크기
: 업데이트의 목표
: 시간차 에러

시간차 예측에서 업데이트의 목표는 실제의 값은 아니다.
V(S_(t+1))은 현재 에이전트가 가지고 있는 값이다.
에이전트는 이 값을 S_(t+1)의 가치 함수일 것이라고 예측하고 있다.
다른 상태의 가치함수 예측값을 통해 지금 상태의 가치함수를 예측하는
이러한 방식을 부트스트랩(Bootstrap)이라고 한다.
즉, 업데이트 목표도 정확하지 않은 상황에서 가치함수를 업데이트 하는 것이다.
어떤 상태에서 행동을 하면 보상을 받고 다음 상태를 알게 되고
다음 상태의 가치함수와 받은 보상을 더해 그 값을 업데이트의
목표로 삼는다는 것이다.
다음 상태에서 또 다시 행동을 선택하고 이 과정이 반복된다.
시간차 예측은 에피소드가 끝날 때까지 기다릴 필요 없이
바로 가치함수를 업데이트 할 수 있다.
시간차 예측은 충분히 많은 샘플링을 통해
업데이트하면 참 가치함수에 수렴하며
많은 경우에 몬테카를로 예측보다 더 효율적으로
빠른 시간 안에 참 가치함수에 근접한다.

[파이썬과 케라스로 배우는 강화학습] p.128 그림 4.14
강화학습 알고리즘 흐름을 살펴보면
정책 이터레이션과 가치 이터레이션
은 살사로 발전한다.
살사부터 강화학습이라고 부른다.

정책 이터레이션은 "정책 평가"와 "정책 발전"을 번갈아 가며 실행하는 과정이다.
현재의 정책에 대해 정책 평가를 통해 가치함수를 구하고,
그 가치함수를 통해 정책을 발전하는 것의 반복이다.
벨만 기대 방정식을 이용해 현재의 정책에 대한
참 가치함수를 구하는 것이 정책 평가이며,
구한 가치함수에 따라 정책을 업데이트하는 것이 정책 발전이다.

정책 평가 과정에서 참 가치함수에 수렴할 때까지
계산하지 않아도 정책 평가와
정책 발전을 한 번씩 번갈아 가면서 실행하면
참 가치함수에 수렴할 때까지 계산했을 때와 마찬가지로
최적 가치함수에 가치함수가 수렴한다.
이러한 정책 이터레이션을 GPI(Generalized Policy Iteration)라고 한다.
GPI는 단 한 번만 정책을 평가해서 가치함수를 업데이트하고
바로 정책을 발전하는 과정을 반복한다.
GPI의 정책 평가 과정을 수행하는 것이 몬테카를로 예측, 시간차 예측이다.
시간차 예측에 대해서만 살펴보자
GPI의 탐욕 정책 발전은 주어진 가치함수에 대해
새로운 정책을 얻는 과정이다.
시간차 방법에서는 타임스텝마다 가치함수를 현재 상태에 대해서만
업데이트한다.
따라서 GPI에서처럼 모든 상태의 정책을 발전시킬 수 없다.
하지만 시간차 방법에서 이를 가능케 할 수 있는데,
바로 가치 이터레이션의 방법을 사용하는 것이다.
가치 이터레이션에서는 정책 이터레이션에서와 달리
별도의 정책 없이 가치함수에 대해 탐욕적으로 움직일 뿐이었다.
시간차 방법에서도 마찬가지인데 별도의 정책을 두지 않고
에이전트는 현재 상태에서 가장 큰 가치를 지니는 행동을 선택하는
탐욕 정책을 사용하면 된다.
시간차 예측과 탐욕 정책이 합쳐진 것을 시간차 제어라고 한다.

GPI에서 정책 발전의 식은 다음과 같다.
현재 상태의 정책을 발전시키려면 결국 의 최댓
값을 알아야 하는데
그러려면 환경의 모델인 를 알아야 한다.

탐욕 정책에서 다음 상태의 가치함수를 보고
판단하는 것이 아니고
현재 상태의 큐함수를 보고 판단한다면
환경의 모델을 몰라도 된다.
큐함수를 사용한 탐욕 정책의 식은 다음과 같다.

시간차 제어에서는 위 수식으로 표현되는
탐욕 정책을 통해 행동을 선택한다.
큐함수에 따라 행동을 선택하려면 에이전트는
가치함수가 아닌 큐함수의 정보를 알아야 한다.
따라서 시간차 제어에서 업데이트하는 대상이
가치함수가 아닌 큐함수가 돼야 한다.
시간차 제어의 식은 다음과 같다.
위 수식에서 다음 상태의 큐함수인 를
알기 위해서는
다음 상태 S_(t+1)에서 다음 행동 까지 A_(t+1)선택해야 한다.

시간차 제어에서 큐함수를 업데이트하려면 샘플이 있어야 한다.
시간차 제어에서는 [ ]을 샘플로 사용한다.
에이전트는 샘플인 상태 S_t에서 탐욕 정책에 따라 행동 A_t를 선택하고
그 행동을 환경에서 한 타임스텝을 진행한다.
그러면 환경은 에이전트에게 보상 R_(t+1)을 주고
다음 상태 S_(t+1)를 알려준다.
여기서 한 번 더 에이전트는 탐욕 정책에 따라 행동 A_(t+1)을 선택하고
하나의 샘플이 생성되면 그 샘플로 큐함수를 업데이트한다.
이것이 시간차 제어의 과정이다.
[ ]을 하나의 샘플로 사용하기 때문에
시간차 제어를 다른 말로 살사(SARSA)라고 부른다.
살사는 현재 가지고 있는 큐함수를 토대로 샘플을 탐욕 정책으로 모으고
그 샘플로 방문한 큐함수를 업데이트하는 과정을 반복하는 것이다.

하지만 이미 충분히 많은 경험을 한 에이전트의 경우에는
탐욕 정책이 좋은 선택이겠지만
초기의 에이전트에게 탐욕 정책은 잘못된 학습으로 가게 할 가능성이 크다.
즉, 충분한 경험을 통해 에이전트가 보유하고 있는
큐함수들이 최적에 가까워지게 하는 것이 필요하다.
이 문제는 강화학습의 중요한 문제로서 탐험(Exploration)의 문제이다.
따라서 탐욕 정책을 대체할 수 있는 새로운 정책이 필요하다.
에이전트로 하여금 더 탐험하게 할 방법이 필요한 것이다.
그 대안이 ε-탐욕 정책이다.
ε만큼의 확률로 탐욕적이지 않은 행동을 선택하게 하는 것이다.

[파이썬과 케라스로 배우는 강화학습] p.132 그림 4.21
1-ε인 확률로는 현재 상태에서 가장 큰 큐함수의 값을 가지는
행동을 선택한다.
즉, 탐욕 정책을 따르는 것이다.
하지만 현재 가지고 있는 큐함수는 수렴하기 전까지는 편향돼 있는,
정확하지 않은 값이다.
따라서 에이전트는 정확하지 않은 큐함수를 토대로
탐욕적으로 행동하기 보다는
일정한 ε인 확률로 엉뚱한 행동을 한다.

ε-탐욕 정책은 탐욕 정채의 대안으로서 에이전트가
지속적으로 탐험하게 한다.
물론 ε-탐욕 정책은 최적 큐함수를 찾았다 하더라도
ε의 확률로 계속 탐험한다는 한계가 있다.
따라서 학습을 진행함에 따라 ε의 값을 감소시키는 방법도 있다.
더 많은 학습 방법이 있는데 그건 나중에 다룰 것이다.

이처럼 살사는 GPI의 정책 평가를 큐함수를 이용한 시간차 예측으로,
탐욕 정책 발전을 ε-탐욕 정책으로 변화시킨 강화학습 알고리즘이다.
또한 정책 이터레이션과는 달리 별도의 정책 없이
ε-탐욕 정책을 사용하는 것은 가치 이터레이션에서 그 개념을 가져온 것이다.
살사는 간단히 두 단계로 생각하면 된다.
1. ε-탐욕 정책을 통해 샘플 [ ]을 획득
2. 획득한 샘플로 다음 식을 통해 큐함수 Q(S_t,A_t)를 업데이트
큐함수는 에이전트가 가진 정보로서
큐함수의 업데이트는 에이전트 자신을 업데이트하는 것과 같다.

살사는 온폴리시(On-Policy) 시간차 제어,
즉 자신이 행동하는 대로 학습하는 시간차 제어이다.
탐험을 위해 선택한 ε-탐욕 정책을 시행하는 과정에서
랜덤한 액션을 취한 것의 결과로
에이전트가 최적의 정책이 아니라
잘못된 정책을 학습하게 되는 경우가 발생할 수 있다.
하지만 강화학습에서 탐험은 절대적으로 필요한 요소이기도 하다.
충분한 탐험을 하지 않으면 최적 정책을 학습하지 못하기 때문이다.
이러한 딜레마를 해결하기 위해 사용하는 것이
바로 오프폴리시(Off-Policy) 시간차 제어이다.
다른 말로는 큐러닝이라고 한다.

오프폴리시의 말그대로
현재 행동하는 정책과는 독립적으로 학습한다는 것이 큐러닝의 아이디어이다.
즉 행동하는 정책과 학습하는 정책을 따로 분리한다.
에이전트는 행동하는 정책으로 지속적인 탐험을 하면서
따로 목표 정책을 둬서 학습은 목표 정책에 따라서 한다.
반면 살사에서는 따로 정책이 존재하지 않으며
단지 현재 큐함수에 따라 행동을 선택했을 뿐이었다.
살사에서 에이전트는 현재 상태 s에서 행동 a를 ε-탐욕 정책에 따라 선택한다.
그리고 에이전트는 환경으로부터 보상 r을 받고 다음 상태 s ́ 을 받는다.
그리고 다음 상태인 s ́ 에서 또다시 ε-탐욕 정책에 따라
다음 행동을 선택한 후에 그것을 학습에 샘플로 사용한다.
하지만 큐러닝에서는 에이전트가 다음 상태 s ́ 를 알게 되면
s ́ 에서 가장 큰 큐함수를
현재 상태 s에서의 큐함수의 업데이트에 사용한다.
에이전트는 실제로 s ́ 에서 어떤 행동을 했는지와 상관없이
현재 상태 s의 큐함수를 업데이트할 때는 s ́ 의 최대 큐함수를 이용한다.
따라서 현재 상태의 큐함수를 업데이트하기 위해 필요한 샘플은 <s,a,r,s ́>이다.

큐러닝의 업데이트 수식은 다음과 같다.
다음 식이 더 익숙한 사람이 있을 수도 있다.

살사와 큐러닝의 업데이트 식과 벨만 기대 방정식, 벨만 최적 방정식을 다시 살펴보자
벨만 기대 방정식
살사
벨만 최적 방정식
큐러닝
이를 통해 알 수 있는 점은 살사에서는 큐함수를 업데이트하기 위해
벨만 기대 방정식을 사용하고,
큐러닝에서는 큐함수를 업데이트하기 위해
벨만 최적 방정식을 사용한다는 것이다.

큐러닝을 통해 학습하면 다음 상태 s ́ 에서
실제 선택한 행동이 안 좋은 행동이라도
그 정보가 현재 상태 s의 큐함수를 업데이트할 때 포함되지 않는다.
왜냐하면 큐러닝에서 학습에 사용했던 다음 상태에서의 행동과
실제로 다음 상태로 가서 한 행동이 다르기 때문이다.
이처럼 실제 환경에서 행동을 하는 정책과
큐함수를 업데이트할 때 사용하는 정책이
다르기 때문에 큐러닝을 오프폴리시라고 한다.
큐러닝은 살사에서 딜레마였던 "탐험 vs 최적 정책 학습"의 문제를
정책은 분리시키고 행동 선택은 ε-탐욕 정책으로,
업데이트는 벨만 최적 방정식을
이용함으로써 해결했다.

딥살사
폴리시 그레디언트

�ݺ�ߣ

Rl from scratch part3

Recommended

More Related Content

Similar to Rl from scratch part3 (20)

Rl from scratch part3