기타등등

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

이제부터 상태가 무수히 많은 규모가 큰 MDP를 푸는 법에 대해 논의한다.

7.1 함수를 활용한 근사

상태가 많아지면 테이블의 사이즈가 기하급수적으로 커지므로 테이블 기반 방법론을 사용할 수 없게 된다.

새로운 접근법이 필요하다.

예를 들면, 상태값을 입력시켜 결과값으로 가치값을 리턴하는 함수를 구할 수 있다면, 

상태값과 가치값을 저장하는 테이블 방식보다 함수 정보만 가지고 있으면 되므로 메모리 사용이나 시간상 많은 이점이 있을 것이다.

하지만, 정확하게 실제 가치값을 도출해 내는 함수를 구하기는 어려우므로  근사함수를 구해서 사용할 수 있다.

실제 값에 가장 가깝게 근사하도록 함수 파라미터를 구하는 법으로 주로 "최소 제곱법"을 사용합니다.

1. 함수 복잡도에 따른 차이

함수의 차수가 높을 수록 아래 그림과 같이 실제 결과값과 거의 일치하게 근사시킬 수 있다.

하지만 실제 데이터에는 노이즈가 섞여 있으므로 실제 데이터값에 정확하게 피팅하면 오히려 구하고자 하는 평균치 데이터(가치밸류)와는 멀어질 수도 있게 된다. 즉, 높은 차수의 다항함수를 사용하는 것이 무조건 정확하다고 볼 수는 없다.

2. 오버피팅과 언더피팅

오버피팅 :  근사함수를 정할 때 , 너무 유연한 함수를 사용하여 노이즈까지 피팅해 버리는 현상

언더피팅 : 실제 모델을 담기에 함수의 유연성이 부족하여 주어진 데이터와의 에러가 큰 상황

위 그림에서 빨간선은 근사함수이며 녹색선이 실제 모델 함수이다.

좌측그림은 언더피팅, 우측그림은 오버피팅을 나타낸다.

3. 함수의 장점 - 일반화

이미 경험한 데이터들을 바탕으로 실제 모델 함수에 근사한 함수를 잘 구성한다면 경험하지 않은 데이터를 근사함수에 입력하였을 때 실제 데이터와 오차가 적은 결과값을 리턴하게 될 것이다. 이런 함수의 특징을 일반화라고 한다.

이 특징때문에 잘 근사된 함수를 사용하게 되면 데이터를 저장하기 위한 공간을 대폭 줄일 수 있게 된다.

7.2 인공 신경망의 도입

1. 신경망

신경망의 본질은 매우 유연한 함수이다. 함수에 포함된 프리 파라미터의 개수를 통해 함수의 유연성을 제어한다.

(근래 커다란 신경망의 프리 파라미터가 1000억개를 넘어가기도 한다)

이러한  특징을 가지고 있는 신경망을 이용해서 상태별 가치값을 계산되도록 하려는 것이 Deep RL 학습의 중심 아이디어이다.

위 그림은 길이 3인 벡터를 인풋으로 받아 2층으로 쌓여있는 히든레이어를 통과시켜 결과값 하나를 도출해내는 신경망을 나타낸다.

함수로 표현하면 y = f(\(x_1, x_2, x_3\)) 형태이다.

히든레이어들은 노드로 구성되어 있으므로 신경망의 최소단위를 노드라고 할 수 있다. 따라서 노드를 이해하면 신경망 이해에 도움이 된다.

위그림은 하나의 노드만 떼어내어 표현한 것이다.

(1) 인풋 (\(x_1, x_2, x_3\))을 \(w_1x_1 + w_2x_2+w_3x_3 + b\)의 형태로 선형결합시킨다.

(2) g(x)라는 비선형 함수를 적용한다. (예를 들면, RELU함수 => g(x) = max(0, x))

여기서 선형결합의 의미는 인풋값들을 조합하여 새로운 피처(특징값)를 만드는 과정이다.

또한 비선형함수 적용은 인풋과 아웃풋의 관계가 비선형일 수 있기에 필요한 과정이다.

2. 신경망의 학습 - 그라디언트 디센트

제공된 데이터를 근거로 신경망 함수의 w 파라미터를 구하는 방법으로 그라디언트 디센트 방법을 사용한다.

실제 모델의 함수를 F(x)라 하고 근사함수를 f(x)라 하면 두 함수의 차이를  줄이는 것이 최종 신경망 학습의 목표이다.

이를 위해 아래와 같은 두 함수의 차의 제곱을 함수로 구성할 수 있다. 

$$ L(w) = \{ F - f \}^2 $$

여기서 L(w)을 손실함수(loss function)라고 한다.

이 손실함수값을 최소화하는 것이 결국 신경망의 목표가 되는 것이다.

해당 신경망 모델에 100개의 w 파라미터가 존재한다고 가정할 때, 

파라미터 별로 편미분을 통해 해당 파라미터 항이 함수 전체에 미치는 영향을 파악한다.

위 식은 함수의 각 파라미터에 대해 편미분하여 벡터를 만든 것이고, 이를 그라디언트 라고 한다.

계산된 그라디언트를 이용해 손실함수를 최소화 하는 방향으로 아래 수식처럼 파라미터를 조금씩 업데이트 해 나간다.

이런 과정을 그라디언트 디센트(경사하강법) 방법이라고 한다.

여기서 편미분결과를 반영하는 비율 \( \alpha \)를 러닝레이트 또는 스텝사이즈라고 한다.

보통 러닝레이트 값은 1보다 작은 값으로 셋팅합니다.

그라디언트 디센트 방법을 반복하면서 파라미터값을 업데이트 시켜가면 결국 손실함수가 최소가 되는 방향으로 파라미터들이 조정되는 것이고 결국 실제 데이터 모델에 근사한 함수를 구성할 수 있게 되는 것이다.

3. 간단한 확인

간단한 함수로 예를 들어 위의 과정을 살펴보겠다.

아래와 같은 근사 함수 \( f_w \)가 있다.

초기 w파라미터는 랜덤하게 셋팅한다.

\( w_1 = 0.5, w_2 = 1.2 \) 라고 하자.

그리고 학습을 위해 주어진 경험치 데이터는 \( (x_1, x_2, y) = (1, 2, 1) \) 이다.

즉, 

$$ f_w(1,2) = 1 $$

만족하도록 w를 조정하는 것이 목표이다.

현재 상황에서 손실함수 L(w)는 아래와 같이 정의된다.

각 파라미터별로 편미분하면 아래와 같다.

구해진 그라디언트 벡터를 이용해 w 파라미터를 업데이트 한다(이때, 런닝레이트 \( \alpha \) = 0.01)

업데이트 된 w 파라미터를 이용해 \( f_w^{'}(1,2) \) 값을 계산했을 때 아래 결과에서 보듯이 w 파라미터 업데이트 전보다 실제결과값 1에 가까워졌다.

위 과정을 계속 반복하여 w파라미터를 업데이트함으로 실제 결과값에 점차로 가까워게 되며 결국 실제모델에 가까운 신경망함수를 얻게 되는 것이다. (이때 주의할 사항은 오버피트 이다)

4. 파이토치를 이용한 신경망 구현

간단한 실제 모델을 주고, 신경망 학습을 통해 근사함수를 구하는 과정을 파이토치를 활용해 구현해본다.

실제모델은 아래와 같다.

위 식에서 노이즈 U(-0.2, 0.2)는 -0.2에서 0.2 사이값을 실제값에 균등분포 시킨다는 것을 의미한다.

또한, 신경망의 모델은 아래와 같다.

인풋과 아웃풋은 각각 스칼라값 하나이고, 총 3개의 히든 레이어를 갖고 있으며 각 레이어에는 128개의 노드가 포함되어 있다. 또한 각 레이어에는 활성홤수 ReLU가 포함되어 있다.

이제부터, 위의 모델을 파이토치로 구현한다.

forward 함수에서 레이어별로 활성함수 ReLU 를 적용하고 있다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

본 챕터를 진행하기 전에 2가지 전제조건을 다시한번 언급하면,

1. 작은 모델(상태집합과 액션집합이 작다)

2. MDP를 모른다 (보상함수와 전이확률분포를 모른다)

이런 조건 하에서 그리드 월드 환경에서 최고의 정책을 찾는 방법을 3가지 소개한다.

1) 몬테카를로 컨트롤,

2) SARSA

3) Q 러닝

1. 몬테카를로 컨트롤

CH04 에서 언급한  MDP를 알 때 최적 정책함수 구하는 방법 중 정책이터레이션 방법이 있다.

위 그림이 정책 이터레이션 방법을 구조화 시킨 것이다.

하지만, 모델 프리 상황에서는 정책이터레이션을 그대로 사용할 수 없다.

이유는 2가지이다.

첫번째, 보상과 전이확률을 모르기 때문에 정책평가단에서 반복적 정책평가를 사용할 수 없다.

벨만 기대 방정식 2단계 공식을 보면 아래와 같다.

위 식을 통해 상태별로 반복적 정책 평가가 이루어지는데 공식 중에

보상 \( r_s^a \)와 전이확률 \( P_{ss^{'}}^{a}\)을 모르기 때문에 계산을 할 수 없게 된다.

두번째, 만일 첫번째 문제를 해결해서 각 상태의 밸류를 알고 있는 상태라고 가정할 때,

전이확률 \( P_{ss^{'}}^{a}\)을 모르기 때문에 그리드 정책을 수행할 수 없다.

즉, 다음상태의 리턴 기댓값이 큰 상태로 이동하는 정책을 수립해야 하는데 각 액션이 정해진 상태에서 다음상태로 이동을 예측할 수 없기 때문에 밸류를 계산할 수 없어서 그리디 정책을 수립할 수 없다.
따라서 모델 프리 상황에서 정책 이터레이션을 적용하려면 몇 가지 변형을 주어야 한다.

변형 1 : 
반복적 정책평가 방법에 앞에서 언급했던 MC를 적용하는 것이다.
MC는 MDP를 모를 때 밸류를 계산하는 방법이므로 적용가능하다.

변형 2:
정책개선단계에서 \( \nu(s) \) 대신 액션가치함수 q(s, a)를 이용한다.

q(s,a)를 알게 되면 MDP정보를 몰라도 q(s,a)가 큰 액션을 선택해 나가는 그리디 액션을 선택할 수 있다.

위 2가지 내용을 종합하면,

몬테카를로 방법을 이용하여 q(s,a)를 계산하고 평가된 q(s,a)를 이용해 새로운 그리디정책을 만들고, 이 정책에 대해 다시 MC를 이용하여 q(s,a)를 계산하는 일련의 과정을 반복하는 방법으로 MDP를 몰라도 최적의 정책을 찾을 수 있다.

마지막으로 여기에 추가되어야 하는 것이 있다.

에이전트가 최적의 정책을 찾으려면 MDP 상에 많은 상태를 충분히 탐색해야 한다.

만일 학습과정에서 도달해보지 못한 상태가 있는데 그 상태가 가장 좋은 상태인 경우 최적의 정책을 못찾게 되는 것이다.

하지만, 모든 액션을 완전히 랜덤하게 선택하면 모든 상태를 방문할 확률은 높지만 최적의 정책을 찾지는 못 할 것이다.

따라서 랜덤의 정도를 정해주는 \( \epsilon \) - greedy 방법론을 적용한다.

변형 3: greedy  대신 decaying \( \epsilon \) - greedy 방법론 적용

위 수식에서 \( \epsilon \) = 0.1 이라면, 

90%  확률로 q(s,a)값이 가장 높은 액션 a를 선택하고, 나머지 10% 확률로 랜덤하게 액션을 선택한다.

이 내용을 활용하여 학습을 진행할 수록 랜덤확률을 줄이고 파악된 정보를 이용해 최적의 정책을 찾아갈 수 있도록 \( \epsilon \)값을 줄여나가는 방법을 추천한다.

decaying \( \epsilon \)-greedy 방법론:

초기 학습과정에는 수집된 정보가 많지 않기 때문에 \( \epsilon \)값을 높게 주어 많은 상태를 접할 수 있도록 하며, 점차로 \( \epsilon \)값을 낮추어 학습에서 얻은 정보를 활용하여 최적의 액션을 선택할 수 있도록 유도한다.

또한 학습과정에 성능이슈를 줄이기 위해 정책평가단계에서 가치테이블에 값들을 한번만 계산하고 정책개선 단계로 넘어가도록 한다. (간소화된 정책 이터레이션)

2. TD 컨트롤 1 (SARSR)

정책평가 단계에서 MC 대신 TD를 사용하는 정책 이터레이션 방법이다.

위 그림은 TD컨트롤을 SARSA 라고 부르는 이유를 설명하고 있다.

SARSA는 정책평가 단계에서 MC대신 TD를 사용하여 평가를 진행한다.

각 상테에서 다음 상태로 이동해가면서 액션가치함수 q를 업데이트 시키게 된다.

이때 업데이트 식은 아래와 같다.

여기서 빨간색 부분인 \( R + \gamma Q(S^{'}, A^{'}) \) 을 TD타깃으로 볼 수 있다.

결국 이 부분을 스텝별로 계산해가면서 업데이트 하게 되면  정책개선 단계에서 활용하여 더 좋은 정책을 선별할 수 있게 된다.

3. TD 컨트롤 2 (Q러닝)

Q러닝 설명 전에 타깃정책과 행동정책, Off-Policy 와 On-Policy 개념을 설명한다.

타깃정책 : 강화하고자 하는 목표가 되는 정책이다. 학습의 대상이 되는 정책이며 업데이트 됨에 따라 점점 강화되는 정책이다.

행동정책 : 실제로 환경과 상호 작용하며 경험을 쌓고 있는 정책을 의미한다.

On-Policy : 타깃정책과 행동정책이 일치하는 경우를 의미(현재까지 논의되었던 모든 상황)

Off-Policy : 타깃정책과 행동정책이 일치하지 않는 경우를 의미 (간접경험을 통해 실력을 향상시키는 방법- 예를 들면, 게임을 하고 있는 친구의 행동을 관찰하면서 실력을 향상시키는 상황)

3.1 Off-Policy 학습의 장점

(1) 과거의 경험을 재사용할 수 있다.

일반적인 On-Policy 방법론에서는 타킷정책과 행동정책이 일치해야 한다.

SARSA 를 사용한다고 가정할 때 에이전트의 초기 정책 \( \pi_0 \)를 이용하여 하나의 에피소드를 진행해나가며 행동가치함수 q를 업데이트하고 이를 활용해 정책을 \( \pi_1 \)로 수정한다. 새로 수립된 정책을 가지고 다시 처음부터 경험을 쌓아 가야 한다. 

여기서 새로 수립된 정책 \( \pi_1 \)정책이 타깃정책이며 실제 행동을 취했던 정책이 \( \pi_0 \)정책인데 On-Policy정책에서는 타깃정책과 행동정책이 일치해야 하므로 \( \pi_1 \)정책을 강화하기 위해서는 \( \pi_1 \)정책을 사용하여 액션을 통해 경험을 쌓아가야 한다.

하지만 Off-Policy 방법론은 타깃정책과 행동정책이 다르므로 \( \pi_1 \)정책을 강화하기 위해 \( \pi_0 \)정책을 근거로 액션을 선택하며 경험을 쌓은 정보를 재활용할 수 있다.

(2) 전문가들의 정책을 액션정책으로 활용할 수 있다.

보통은 랜덤정책으로 초기화하고 학습을 진행하면서 조금씩 유의미한 학습이 이루어지도록 하게된다. 따라서 초기에 유의미한 학습이 이루어지기까지 상당한 양의 학습이 필요하게 된다.

만일 초기에 전문가들의 정책을 적용하여 학습을 시작하게 되면 학습속도를 높일 수 있게 된다.

(3) 일대다, 다대일 학습이 가능하다

동시에 여러 개의 정책을 학습키는 경우, Off-Policy 학습을 이용하면 1개의 정책만 경험을 쌓게 하고, 그 결과 데이터를 이용해 동시에 여러 개의 정책을 학습시킬 수 있다.

반대로 동시에 여러 개의 정책이 각각의 경험을 통해 얻은 데이터를 모아서 1개의 정책을 업데이트 할 수도 있다.

3.2 Q러닝의 이론적 배경 - 벨만 최적 방정식

위 식은 \( q_{*}(s,a) \)의 정의를 식으로 표현한 것으로 상태집합 S와 행동집합A가 주어진 MDP 상황에서 존재하는 모든 정책 중에 가장 좋은 정책을 따를 때의 가치함수를 의미한다.

또한, \( q_{*} \)를 알게 되면 상태마다 \( q_{*} \)의 값이 가장 높은 액션을 선택하면 그것이 가장 좋은 정책, 최적 정책이 된다.

수식으로 표현하면 아래와 같다.

결국 최적정책을 찾기 위해서 최적의 액션가치함수 \( q_{*} \) 를 찾으면 된다.

이제 \( q_{*} \) 를 찾는 방법을 설명한다.

기본이 되는 수식은 아래의 벨만 최적 방정식 0단계이다.

이 식을 근거로 Q러닝의 업데이트 식은 아래와 같다.

앞에서 언급한 SARSA 의 업데이트식과 비교해보면 아래와 같다.

빨간색 글자 부분이 Q러닝과 SARSA  업데이트식의 차이부분이다.

위 식에서 알 수 있듯이 밸류 업데이트 수식은 비슷하지만 아래의 표에서 보는 것처럼 SARSA는 On-policy방식이고, Q러닝은 Off-Policy방식이다.

SARSA와 Q러닝이 다른 이유는 기초가 되는 수식이 다르기 때문이다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

보상과 전이확률을 모르는 상황을 모델프리( Model - free) 라고 부른다.

모델 프리 상황에서 정책 \( \pi \)가 주어졌을 때 밸류 평가 방법 즉, Prediction 문제를 푸는 2가지 방법

몬테카를로와 Temporal difference 를 소개한다.

작은 모델 MDP에 대해 다루기 때문에 이전 챕터에서 사용했던 테이블 룩업 방법론을 적용하여 문제를 풀어간다.

1. 몬테카를로 학습

몬테카를로 방법론 - 직접 측정하기 어려운 통계량을 구하고자 할 때 여러 번 샘플링하여 그 값을 가늠하는 기법

위 공식은 상태가치함수의 정의이다.

공식을 풀이해보면 정책 \( \pi \)가 주어진 상황에서 t 시점의 상태 \( s_t \)의 밸류는 t 시점의 리턴의 기댓값이다.

리턴을 얻어내기 위해 직접 에피소드를 종료시점까지 실행하여 리턴값을 얻어내고 이 과정을 반복하여 얻어낸 리턴의  평균을 냄으로 리턴 기댓값을 계산해 내는 것이 몬테카를로 학습의 중요 개념이다.

바둑게임을 예시로 들어보면,

임의의 시점에 바둑판의 상황을 캡쳐해놓고 이 상황이 얼마나 좋은 상황인지 밸류를 평가하려면 실제로 그 상황에서 부터 게임 종료까지 진행해보고 승패 여부에 맞게 보상을 주고 이 과정을 수만 번 반복함으로 리턴 기댓값을 계산해 냄으로 캡쳐한 상황의 밸류를 평가할 수 있다.

 1.1 몬테카를로 학습 알고리즘

보상과 전이확률을 모르는 그리드 월드를 이용하여 몬테카를로 학습 알고리즘을 살펴본다.

실제로 보상은 -1, 전이확률은 100% 라고 정해놓고 그 내용을 에이전트가 모르는 상태에서 몬테카를로 학습을 진행한다고 가정한다.

(1) 테이블 초기화

위 그림의 오른쪽 테이블에서 보이는 것처럼 각 상태별로 N(s)와 V(s) 2개의 값이 필요한데

N(s)는 학습하는 동안 해당 상태를 방문한 횟수 이며,

V(s)는 해당 상태 방문시 마다 얻게된 리턴 누적 합을 의미한다.

초기에는 각 상태별로 2값을 모두 0으로 셋팅한다.

(2) 경험쌓기

에이전트는 주어진 \( \pi \) 정책하에 \( s_0 \) 상태부터 시작하여 종료상태까지 액션과 그에 따른 보상을 받으면서 에피소드를 진행해 나간다. 이를 기호로 표기하면 아래와 같다.

이렇게 하나의 에피소드가 종료되면 각 상태에 대한 리턴은 아래와 같이 계산할 수 있다.

감마 \( \gamma \)와 보상은 실행해 나가면서 에이전트가 알게된 숫자값이다. 결국 각 상태별 리턴은 숫자값이 되는 것이다.

(3) 테이블 업데이트

위 그림의 경로로 하나의 에피소드가 끝난 후 (2)에서 제시한 수식으로 상태별 리턴값을 계산하여

상태별 N(s)와 V(s)값을 업데이트 한다. (위 그림 우측테이블)

(4) 상태 밸류 계산

  경험쌓기와 테이블 업데이트를 충분히 반복한 후 각 상태별로 리턴(V(s))의 평균값을 계산하면 그 값이 상태 밸류가 된다.

(5) 조금씩 업데이트하는 버전

   (4)번 까지의 방법은 에피소드를 충분히 반복한 이후 (예를 들면, 10만번 반복 실행) 밸류를 계산할 수 있었다.

이번 방법은 하나의 에피소드가 끝날때마다 밸류를 조금씩 업데이트 시켜주는 방법이다.

방법은 아래 공식과 같이 \( \alpha \) 라는 개념을 추가하여 기존 값에 새로 계산된 리턴값을 얼마의 비율로 섞어줄지를 지정할 수 있도록 한 것이다.

이렇게 되면 N(s)를 저장해 둘 필요가 없다.

위 공식을 조금 변형하면 아래 식이 된다. 이후에 몬테카를로 학습에서는 아래의 식을 사용한다.

2. Temporal Difference 학습

MC 학습(몬테카를로 학습)은 최소한 하나의 에피소드가 끝나야 밸류를 업데이트할 수 있는 구조이다.

하지만 실제 세계에서는 종료 조건이 명확하지 않은 MDP도 많다.

이처럼 종료하지 않는 MDP 에서 밸류를 구할 수 있는 방법이 Temporal Difference 학습방법이다.

Temporal Difference의 기본 개념은 아래와 같다.

"추측을 추측으로 업데이트 하자!!"

한 스텝이 지나고, 조금이라도 시간이 흐르면 좀 더 정확한 추측을 할 수 있게 되는 것이고 이를 이용하여 이전 스텝의 밸류를 업데이트 활용하는 방식이다.

2.1 이론적 배경

위 공식은 벨만 기대 방정식 0단계 수식이다.

위 공식을 풀이해보면,

\( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \)을 여러 번 뽑아서 평균을 내면 그 평균은 \( \nu_{\pi} (s_t) \)에 수렴한다는 의미이고, 

\( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \)을 풀이해보면, 

\( s_t \) 상태에서 받게 되는 보상 \( r_{t+1} \)과 다음 상태( \( s_{t+1} \)의 밸류를 합한 값을 의미한다.

여기서 \( \nu_{\pi}(s_{t+1}) \) 값이 다음 스텝으로 이동 시 상태밸류 값이고 이것은 사실 에피소드가 끝나기 전 까지는 예상치라고 볼 수 있을 것이다.

이전에도 언급했듯이 , 반복적으로 수행하다 보면 위 예상치에 보상을 더하기 때문에 점차 실제 상태밸류에 수렴해간다

여기서 \( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \) 값을 "TD 타깃" 이라고 부른다.

MC학습에서는 각 상태별 리턴을 여러 개 모아 평균을 내어 밸류를 측정했듯이,

TD에서는 TD타깃 \( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \)을 여러 개 모아 평균을 내어 밸류를 측정한다.

2.2 TD 학습 알고리즘

MC 학습과 동일한 조건에서 TD학습 알고리즘을 설명한다.

 (1) 초기화

에이전트를 \( s_0 \) 상태부터 경험을 쌓게 한다.

하나의 에피소드 경로는 아래와 같다

이런 상태에서 TD학습이 MC학습과 차이나는 부분은 2가지이다.

1) 다음 스텝으로 이동한 직후 이전 스텝의 밸류를 아래 수식으로 업데이트 해준다.

이전의 MC 학습 시 공식과 비교하면, 

2) MC학습에서 리턴값을 이용했던 위치에 TD타깃이 대입되었다고 보면 된다.

위 방법으로 하나의 에피소드에 수식을 적용해보면 

위 과정을 에피소드를 반복적으로 수행하면서 진행해나가면 테이블에 상태밸류값은 수렴하게 된다.

3. MC (몬테카를로) & TD 비교

3.1 학습시점 측면

MC는 Episodic MDP (종료가 있는 MDP) 에서만 적용할 수 있다.

TD는 Episodic MDP 와 Non-Episodic MDP (종료가 없는 MDP) 에서도 적용할 수 있다.

따라서  모든 종류의 MDP에서 적용이 가능하다는 측면에서 TD가 좀 더 낳은 방법이다.

3.2 편향성(Bias) 측면

위 공식은 MC의 근간이 되는 수식과 TD의 근간이 되는 수식이다.

MC의 밸류는 리턴들을 여러 개 모아 평균을 내는 방법론으로 샘플이 모일 수록 실제밸류에 반드시 수렴하게 된다.

즉, 편향되지 않는 안전한 방법이다.

TD는 현재의 밸류 추측치를 다음 스텝의 밸류 추측치로 업데이트 해주는 방법이다.

위 벨만 기대 방정식 공식에서 사용되는 것은 \( \nu_{\pi} (s_{t+1}) \) 이지만 실제 사용되는 값은 V(\(s_{t+1}\)) 이다

\( \nu_{\pi} \) : 정책 \( \pi \)의 실제 가치를 의미하며

V : 학습과정에서 업데이트하고 있는 테이블 안에 쓰여있는 값으로 \( \nu_{\pi} \)와 같아지기를 바라는 값

따라서 

이고, 현실에서 사용되는 TD타깃 \( r_{t+1} + \gamma V(s_{t+1}) \)는 편향되어 있다.

편향의 의미를 해석하자면, TD타깃은 샘플을 무한히 모아서 업데이트해도 실제 가치에 다가간다는 보장이 없다는 뜻이다. 하지만 몇 가지 조건을 붙이면 실제로 의미있게 동작한다. 그 부분은 뒤에서 다시 언급한다.

데이터의 편향성 측면에서 보았을 때는 편향되어 있지 않은 MC학습법이 우세하다.

3.3 분산 (변동성)(Variance) 측면

- MC 학습 과정에서 나오는 리턴값은 변동성이 크다

- TD학습과정에서 나오는 TD타깃은 변동성이 작다

1) MC 학습 과정에서 나오는 리턴값은 변동성이 크다

MC학습에서 하나의 리턴값을 얻으려면 하나의 에피소드가 종료되어야 하며 하나의 에피소드 과정에는 많은 확률적 과정이 들어가 있다. 쉽게 말해 수많은 동전 던지기가 실행되면서 에피소드가 진행된다는 의미이다.

따라서 그만큼 리턴 결과 값은 변화가 클 수 있다는 것이다.

2)TD학습과정에서 나오는 TD타깃은 변동성이 작다

TD학습과정에서 밸류값을 업데이트 하기 위해서는 한 스텝만 이동하면 되므로 확률적 과정이 상당히 적게 들어간다.

액션 선택과정과 액션선택 후 다음 상태로 전이하는 과정, 이렇게 2과정이 확률적 과정이라고 보면 된다.

따라서 그만큼 결과값의 변동성이 MC 보다는 작을 수 있다는 것이다.

3.4 종합

요즘 강화학습은 종료상태가 있건 없건 사용가능한 TD학습을 많이 적용하고 있다.

4. MC와 TD의 중간 성격을 지닌 학습방법

4.1 n스텝 TD

이 방법은 여러 스텝을 진행하여 각 스텝별 보상을 받은 후 그 다음스텝의 V(\(s_{t+n}\)) 값을 이용하여 밸류를 계산할 수 있다는 개념이다.

이 개념을 수식으로 표현하면 아래와 같다.

N을 무한대로 했을 경우 식은 아래와 같다.

이 경우 결국 리턴계산식과 동일하다.

TD 학습방법에서 n이 무한대인 특수한 경우가 MC라는 것을 알 수 있다.

이 내용을 하나의 스펙트럼으로 표현하면 아래와 같다.

위 그림에서 좌측 끝단은 TD-zero (N=1인 경우의 TD타깃을 이용하여 업데이트하는 방법론),

우측 끝단은 MC 학습을 의미한다.

N이 커질수록 MC 성격에 가까워지게 된다.

즉, 추측값인 TD타깃의 값이 작아지고 보상의 비중이 늘어가게 되어 결국 편향성은 줄어들고, 확률적 과정이 점차 많이 포함되므로 변동성은 점차 커지게 된다.

결국, TD 학습을 적용할 때 N을 얼마로 할 것인지가 주요한 결정이 될 것이다.

유명한 A3C 알고리즘 논문은 N = 5로 하여 적용하였다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

간단한 그리드 월드 MDP 상황을 예시로

정책 \( \pi \)가 주어졌을 때 각 상태의 밸류를 평가하는 prediction문제와

최적의 정책 함수를 찾는 control 문제를 푸는 방법에 대해 설명한다.

2가지 전제조건이 있다.

1. 작은문제 ( 상태집합(S)과 액션집합(A)의 크기가 작은 문제 )

2. MDP에 대해 알고 있다. (즉, 보상과 전이확률을 알고 있다)

이 전제조건이 만족하기에 테이블 기반 방법론을 활용하여 문제를 풀어나간다.

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

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

풀어야 할 문제와 상황은 다음과 같이 정리할 수 있다.

4방향 랜덤이라는 정책함수 \( \pi \)가 주어졌고 이때 각 상태 s에 대한 가치함수 \( \nu(s) \)를 구하는 전형적인 prediction 문제이다.

이 문제는 테이블 값들을 초기화한 후, 벨만 기대 방정식을 반복적으로 사용하여 테이블에 적어 놓은 값을 조금씩 업데이트해 나가는 반복적 정책 평가 방법론을 사용하여 풀게 된다.

보상은 모든 상태에서 -1 이다.

전이확률 \( P_{ss^{'}}^a \) 은 100%이다( 예를 들면, 좌측 이동 액션을 선택한 경우 다음 상태는 100% 좌측상태로 이동하기 때문)

\( \gamma \) 는 편의상 1 로 정한다

(1) 테이블 초기화 과정

테이블 빈칸은 상태별 밸류 \( \nu(s) \)를 기록해야 하기 때문에 상태 개수만큼 필요하다.

임의의 값 0으로 초기화한다. 추후 반복적 정책평가를 진행하면서 각 상태의 밸류들은 특정값으로 수렴해 갈 것이다.

(2) 상태의 값을 업데이트하는 과정

\( s_5 \) 상태의 밸류를 좀 더 정확하게 업데이트 하려면 , 정책이 주어져 있고 MDP를 알고 있으므로

아래의 벨만 기대 방정식 2단계 공식을 이용해서 상태밸류를 계산할 수 있다.

이 수식은 현재 상태 s의 가치를 다음에 도달하게 되는 상태 \( s^{'} \)의 가치로 표현한 식이다.

이 식을 토대로 위 그림의 파란색 셀( \( s_5 \) )의 밸류를 노란색 셀의 밸류를 이용해 업데이트 한다.

위의 벨만 기대 방정식을 그리드 월드에 맞게 풀어 적으면 아래와 같다.

$$ \nu_{\pi}(s_5) = \pi( 좌|s_5) ( r_{s_5}^좌 + \gamma ( P_{s_{5}s_{4}}^{좌} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{좌} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{좌} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{좌} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 우|s_5) ( r_{s_5}^우 + \gamma ( P_{s_{5}s_{4}}^{우} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{우} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{우} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{우} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 상|s_5) ( r_{s_5}^상 + \gamma ( P_{s_{5}s_{4}}^{상} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{상} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{상} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{상} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 하|s_5) ( r_{s_5}^하 + \gamma ( P_{s_{5}s_{4}}^{하} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{하} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{하} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{하} \nu_{\pi}(s_9) ) ) $$

이 식에 실제 값을 대입해보자

$$ \nu_{\pi}(s_5) = 0.25 \times ( -1 + 1 \times ( 1 \times 0 + 0 \times 0 + 0 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 1 \times 0 + 0 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 0 \times 0 + 1 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 0 \times 0 + 0 \times 0 + 1 \times 0 ) ) $$

정리하면,

$$ \nu_{\pi}(s_5) = 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

결과값은, 

$$ \nu_{\pi}(s_5) = -1 $$

따라서 테이블의 파란색 셀, 즉 상태 \( s_5 \)의 밸류를 -1로 업데이트한다.

여기서 노란색 셀의 밸류들이 초기에 임의의 값으로 지정했기 때문에 그 값을 이용해 계산된 파란색 셀의 값도 정확한 값이 아니다. 하지만 실제 값인 보상값이 포함되어 계산되었기 때문에 초기 임의의 값보다는 실제값에 조금 가까워졌다고 볼 수 있다.

이런 과정을 상태를 이동해가며 계속 반복적으로 진행하다 보면 점차 상태들의 밸류값들이 실제값에 가까워진다.

(3) 모든 상태에 대해 (2)의 과정 적용

(2)의 과정을 마지막 상태를 제외한 15개 상태에 대해서 진행하여 위 그림의 오른쪽과 같은 결과를 얻는다.

가장자리 상태의 업데이트 계산은 바깥을 향하는 액션은 제외시킨다

예를 들면, \( s_0 \) 상태에서 보면 좌, 상 이동은 선택액션에서 제외되어야 한다.

(2)과정의 수식을 \( s_0 \) 상태에 적용해서 나열하면 다음과 같다.

$$ \nu_{\pi}(s_0) = \pi( 우|s_0) ( r_{s_0}^우 + \gamma ( P_{s_{0}s_{1}}^{우} \nu_{\pi}(s_1) + P_{s_{0}s_{4}}^{우} \nu_{\pi}(s_4) ) ) $$

$$ \quad\qquad + \pi( 하|s_0) ( r_{s_0}^하 + \gamma ( P_{s_{0}s_{1}}^{하} \nu_{\pi}(s_1) + P_{s_{0}s_{4}}^{하} \nu_{\pi}(s_4) ) ) $$

정리하면,

$$ \nu_{\pi}(s_0) = 0.5 \times ( -1 + 1 \times (1 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.5 \times ( -1 + 1 \times (0 \times 0 + 1 \times 0 ) ) $$

$$ \nu_{\pi}(s_0) = 0.5 \times ( -1 + 1 \times 0 ) $$

$$ \quad\qquad + 0.5 \times ( -1 + 1 \times 0 ) $$

$$ \nu_{\pi}(s_0) = 0.5 \times -1 + 0.5 \times -1 $$

$$ \nu_{\pi}(s_0) = -1 $$

결과값은, 

$$ \nu_{\pi}(s_0) = -1 $$

정책이 정해져 있는 상태에서 (여기서는 4방향 랜덤한 액션 선택 정책) 마지막 상태를 제외한 모든 상태에 대해서 반복적인 정책평가를 진행하다보면 각 상태별로 특정값에 수렴해간다.

예를 들어, 상태 \( s_0 \)의 수렴값이 -59.4 가 나왔다.

즉, 이 값은 상태 \( s_0 \)의 가치밸류가 -59.4 라는 의미이고 현재 상황에서 의미는 4방향으로 무작위로 움직이다 보면 평균적으로 대략 60번은 움직여야 종료 상태에 도달하게 된다는 뜻이다.

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

최적의 정책을 찾는 방법은 정책 이터레이션과 밸류 이터레이션 방법이 있다.

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

정책 이터레이션은 2단계로 구성된다.

1단계 ) 정책평가단계: 임의의 정책으로 \( \pi \)를 고정해놓고 반복적 정책 평가 방법을 사용하여 각 상태의 밸류를 계산한다.

2단계 ) 정책개선단계: 1단계에서 계산해 놓은 상태별 밸류값 \( \nu(s) \)을 이용하여 그리디 정책을 생성한다. 

여기서 그리디 정책이란 현재상태에서 바로 앞의 이익을 최대화하는 선택을 하도록 하는 정책을 의미하며 현재 상황에 적용하면 현재 위치한 상태에서 4방향의 다음 상태를 선택할 때 상태밸류 \( \nu(s) \)값이 최대인 상태로 이동을 선택하도록 하는 정책을 의미한다.

1단계=>2단계=>1단계=>2단계... 반복적으로 진행하다보면 정책평가 결과인 가치밸류가 변하지 않고 그리디정책도 변화하지 않는 상태에 도달하게 된다.

이때가 최적의 정책과 최적 가치에 도달한 것으로 판단하면 된다.

그리디 정책 선택이 정책 개선을 의미하는 이유는,

\( \pi_{greedy} \) : 현재 상태에서 바로 다음 상태 이동만 그리디 정책으로 움직이고 그 후 상태 이동은 기존 정책으로 움직이는 정책

\( \pi \) : 기존 정책

위 2가지 정책 중 상태밸류가 높은 쪽은 당연히 \( \pi_{greedy} \) 정책이다. 이 논리를 t 시점뿐만이 아니라 t+1, t+2, .. 모든 시점에 대해 적용하면 결국 모든 상태에서 그리디 정책을 선택하는 것이 정책개선 효과가 있다고 판단할 수 있다.

- 정책평가 방법 간소화 하기

위에서 언급한 정책 이터레이션 방법은 1단계 정책평가 과정에서 정책을 평가하기 위해 반복적 정책평가방법을 사용하며 그 부분에서 상당한 시간을 소요하게 된다.

우리의 목적은 최적정책을 찾기 위해 정책을 평가하는 것이므로 정확한 값을 도출해내지 않더라도 큰 문제는 없다.

상태밸류값이 변하지 않을 때까지 반복평가하는 것이 아니라 예를 들면, 5번만 반복평가를 해도 그리드 정책을 선택에 문제가 없다는 것이다.

이런 논리를 적용하여 정책 이터레이션에서 1단계 정책평가는 1번만 계산하는 것으로 한다.

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

밸류 이터레이션도 테이블 기반 방법론을 사용한다.

각 셀은 최적 정책 \( \pi^{*} \)의 밸류인 \( \nu_{*} (s) \) 를 의미하게 된다.

초기에는 셀의 값들을 0으로 초기화한다.

MDP를 알고 있으므로 ( 보상과 전이확률값을 알고 있음을 의미 )

벨만 최적 방정식 2단계 공식을 사용해 각 셀의 최적밸류를 구한다.

예를 들어 \( s_5 \) 상태의 최적 밸류를 계산하면 아래와 같다.

같은 방식을 모든 셀에 적용한다.

각 셀의 밸류가 특정값에 수렴할 때까지 위의 방법을 반복적으로 수행한다.

최적 정책을 찾는 것이 목표인데 최적 밸류를 먼저 계산했다. 

이유는 MDP를 모두 알고 있는 상황에서는 최적 밸류를 계산하는 것이 최적 정책을 찾는 빠른 방법이다.

최적 밸류를 모두 계산해놓으면 임의의 상태에서 다음 상태 이동은 밸류가 가장 큰 셀로 이동하는 것이 최적 정책이다.

즉, 최적 밸류에 대한 그리디 정책이다.!!

의견 => 정책 이터레이션에서 계산 간소화를 위해 주어진 정책에서 상태밸류 계산시 반복적으로 계산하지 않고 1번만 계산하고 그리디 정책을 선택했다. 이 논리를 밸류 이터레이션에도 적용할 수 있을까?

즉, 최적 정책을 찾기 위해 최적밸류가 수렴할 때까지 반복적 계산이 필요할까 ? 하는 질문이다.

밸류 계산은 1번만 한 상태에서 그리디 정책을 적용하면 어떨까?

질문을 남겨두고 다음챕터로 넘어간다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

1. 벨만 방정식 소개

주어진 상태의 밸류를 구하는 실제 방법에 벨만 방정식이 사용된다.

벨만 방정식은 시점 t 에서의 밸류와 시점 t+1 에서의 밸류 사이의 관계를 다루고 있으며

또 가치함수와 정책함수 사이의 관계도 다루고 있다.

벨만 방정식은 현재 시점 (t)와 다음 시점(t+1) 사이의 재귀적 관계를 이용해 정의된다.

벨만 방정식은 벨만 기대 방정식과 벨만 최적 방정식이 있다.

2. 벨만 기대 방정식

벨만 기대 방정식을 아래와 같이 편의상 세 단계로 나눠 볼 수 있다.

(1) 0단계

\( \nu_{\pi}(S_t)  = \mathbb{E}_{\pi} \left [ r_{t+1} + \gamma \nu_{\pi}(S_{t+1}) \right ] \) 증명 및 의미

위 풀이식을 해석을 해보면,

상태 \( s_t \)의 가치밸류는 상태 \( s_t \)에서 부터 미래에 받을 보상을 더해준 리턴의 기댓값인데, 풀어서 생각해보면 한 스텝 더 진행하여 보상을 받고, 그 다음 상태인 \( s_{t+1} \) 부터 미래에 받을 보상(리턴)을 더해줘도 같은 결과를 가져온다는 것이다.

더 연장해서 생각해보면 \( s_{t+1} \) 상태로 진행한 후 한스탭 더 진행해서 보상을 받고 그 다음상태인 \( s_{t+2} \) 부터 미래에 받을 보상(리턴)을  더해줘도 같은 결과를 가져온다

이것을 수식으로 표현해보면 아래와 같다.

$$ \nu_{\pi} (s_t) = \mathbb{E}_{\pi} \left [ r_{t+1} + \gamma r_{t+2} + \gamma^2 \nu_{\pi} (s_{t+2})  \right ] $$

같은 원리로 액션가치함수에 대해서도 적용할 수 있다.

$$ \mathbf{q}_{\pi}(s_t, a_t) = \mathbb{E}_{\pi} \left [ r_{t+1} + \gamma \mathbf{q}_{\pi}(s_{t+1}, a_{t+1}) \right ] $$

$$ \mathbf{q}_{\pi}(s_t, a_t) = \mathbb{E}_{\pi} \left [ r_{t+1} + \gamma r_{t+2} + \gamma^2 \mathbf{q}_{\pi}(s_{t+2}, a_{t+2}) \right ] $$

풀이식에서 하나 더 주목해야 할 부분은 기댓값에 대한 부분이다.

\( s_t \)에서 시작하여 \( s_{t+1} \)이 정해지기까지 두 번의 확률적인 과정을 거쳐야 한다.

쉽게 이야기하면 두번의 동전던지기 과정이 필요하다.

첫번째는 상태 \( s_t \)에서 액션 \( a_t \)를 선택하는 과정에서 필요하다

이때는 정책확률분포 ( \( \pi \) 에 따라 액션이 정해진다.

예를 들어 수식으로 표현하면,

$$ \pi (a_1 \vert s_t) = 0.6, \pi (a_2 \vert s_t ) = 0.4 $$

이 수식을 해석하면 상태 \( s_t \)에서 액션을 정할 때 \( a_1 (앞면) \)을 선택하게 될 확률 0.6, \( a_2 (뒷면) \)를 선택하게 될 확률 0.4 를 가지는 정책이라는 의미이다. 그리고 이 정책 확률분포에 따라 동전던지기를 실행한다는 것이다.

이 부분을 위 그림에서는 \( \pi \)의 동전던지기 라고 표현했다.

이 과정을 거쳐 액션이 선택되면 그 다음 과정은 환경이 전이확률에 따라 (동전을 던져) 다음 상태 \( s_{t+1} \) 를 정하게 된다.

상태 전이하는 과정에서 이렇게 확률분포에 따라 선택되어 지는 과정(동전던지기)를 수행해야 하기 때문에 매번 결과가 같게 나올 수 없으므로 이 부분을 수식으로 표현하기 위해 기댓값이 사용된 것이다.

(2) 1단계

벨만 방정식 1단계에는 액션 밸류 \( \mathbf{q}_{\pi}(s, a) \) 를 이용해 상태 밸류 \( \nu_{\pi}(s) \) 를 표현하는 식과 \( \nu_{\pi} (s) \)를 이용하여 \( \mathbf{q}_{\pi}(s, a) \)를 표현하는 식으로 구성되어 있다.

왜 1단계에서 이 둘의 관계를 정리하는 방정식이 등장했을까?

0단계에서 언급한 것처럼 상태 전이 과정에는 액션의 선택과정과 그것을 토대로 다음상태를 선택하는 2가지 과정이 내포되어 있다.

즉, 다음상태로 전이과정이 둘과의 관계가 정리되어야 전이과정의 풀이를 한쪽만의 공식으로 나타낼 수 있게 될 것이다.

1) \( \mathbf{q}_{\pi} \)를 이용해 \( \nu_{\pi} \)를 계산하기

다음은 위 식을 예를 들어 설명한다.

정책은 그림의 확률분포를 따른다고 가정하며, \( a_1 \) 선택시 액션밸류(액션가치)는 1, \( a_2 \)를 선택시 액션밸류(액션가치)는 2를 가지고 있다고 가정할 때 상태s 의 밸류 계산식은 다음과 같다.

2) \( \nu_{\pi} \)를 이용해 \( \mathbf{q}_{\pi} \) 계산하기

다음은 위 식을 예를 들어 설명한다.

위 식을 이용해 상태s 에서 액션 \( a_1 \) 선택시 밸류를 구하는 위해서는 아래의 전제조건이 필요하다.

a) \(a_1 \)선택시 받는 보상을 알아야 한다 (그림에서는 0.5)

b) 상태 s에서 액션 \(a_1 \) 선택시 다음 상태로의 전이확률 \( P_{ss^{'}}^a \) 을 알아야 한다.

    (그림에서는 \(s_1 \)으로 이동확률은 70%, \(s_2 \)로 이동확률은 30%이다)

c) 다음상태로 전이된 후 각 상태의 밸류를 알아야 한다.

 (그림에서는 \(s_1 \)의 상태밸류\( \nu_{\pi}(s_1) \)는 1.5 , \(s_2 \)의 상태밸류\( \nu_{\pi}(s_2) \)는 -1 이다)

(3) 2단계

1단계의 \( \mathbf{q}_{\pi} \)에 대한 식을 \( \nu_{\pi} \)에 대한 식에 대입하면 아래와 같은 결과 식이 나온다.

반대로 \( \nu_{\pi} \)에 대한 식을 \( \mathbf{q}_{\pi} \)에 대한 식에 대입하면 다음과 같은 결과식을 얻는다.

2단계의 공식은 0단계 공식의 실제 계산에 사용되는 공식이라고 보며 된다.

0단계와 2단계 수식을 같이 적어보면 아래와 같다.

0단계에서 기댓값 실제 계산을 2단계 공식을 사용한다고 보면 된다.

단, 이때 전제조건은 아래 2가지를 알고 있어야 한다.

- 보상함수 \( r_{s}^{a} \) : 각 상태에서 액션을 선택하면 얻는 보상

- 전이확률 \( P_{ss^{'}}^{a} \) : 각 상태에서 액션을 선택하면 다음 상태가 어디가 될지에 관한 확률분포

이 2가지는 환경의 일부이며 이 2가지에 대한 정보를 알 때 "MDP를 안다"고 표현한다.

하지만 실제 환경에서는 이 2가지를 모르는 경우도 많다.

즉, MDP에 대한 정보를 모르는 상태에서 학습하는 접근법을 "모델-프리" 접근법이라 한다.

반대로 이 2가지에 대한 정보를 알고 있는 경우 학습하는 접근법을 "모델 기반" 혹은 "플래닝" 접근법 이라고 한다.

MDP 모든 정보를 알 때는 벨만 기대 방정식 중 2단계 식을 이용하며,

MDP 정보를 모를 때에는 0단계 식을 이용한다.

2. 벨만 최적 방정식

(1) 최적밸류와 최적 정책

어떤 MDP가 주어졌을 때 그 MDP안에 존재하는 모든 \( \pi \)들 중에서 가장 좋은 \( \pi \)를( 즉 \( \nu_{\pi}(s) \) 의 값을 가장 높게 하는 정책) 선택하여 계산한 밸류가 최적 밸류 \( \nu_{*}(s) \)라는 뜻이다.

\( \mathbf{q}_{*}(s,a) \)도 마찬가지 의미이다.

만일 상태별로 가장 높은 밸류를 주는 정책이 다르면, 예컨대 \( s_0 \)의 밸류는 \( \pi_{238} \)를 따를 때 최고이고 \( s_1 \)의 밸류는 \( \pi_{345} \) 를 따를 때 최고인 경우, 이런 경우는 각 상태별로 최고인 정책을 따르는 새로운 정책\( \pi_{*} \)를 생각할 수 있다. 

해당 정책을 따르면 모든 상태에 대해 그 어떤 정책보다 높은 밸류를 얻게 되는 이러한 정책을 최적 정책 이라고 한다.

(2) 벨만 최적 방정식

1) 0단계 수식 설명

이 식은 밸만 기대 방정식 0단계 수식의 취지와 같은 취지의 수식이다.

"상태s에서 최적 밸류는 한 스탭만큼 진행해서 보상을 받고, 다음 상태인 \( s^{'} \)의 최적 밸류를 더해줘도 같다" 는 의미이다.

여기서 기댓값이 들어가 있는 이유는 액션a에서 다음상태로 전이될 때 사용되는 전이확률는 계속 사용되기 때문에 매번 전이된 상태가 다르며 그로 인해 기댓값이 사용되었다.

2) 1단계 수식 설명

 a) \( \mathbf{q}_{*} \)를 이용해 \( \nu_{*} \) 계산하기

$$ \nu_{*}(s) = \underset{a}{\max} \mathbf{q}_{*} (s,a) $$

위 수식의 의미는 다음과 같다.

"상태 s의 최적밸류는 s 상태에서 선택할 수 있는 모든 액션들 중에 가장 높은 액션밸류와 같다."

아래 그림과 같은 상황으로 위 식을 좀 더 설명한다

벨만 기대 방정식 1단계에서

$$ \nu_{\pi}(s) = \sum_{a \in A} \pi(a \vert s) \mathbf{q}_{\pi}(s, a) $$

\( \pi(a \vert s) \) 부분이 빠진 이유는 상태 s에서 액션 a를 선택하는 방법은 정책확률에 따라 선택했었으나

벨만 최적 방정식에서는 액션밸류가 최대가 되는 a를 선택하는 방식이기 때문에 확률적 접근을 하지 않게 된다. 따라서 확률정보를 가지고 있는 정책확률 \( \pi \)가 필요없게 되어 빠진 것이다.

b) \( \nu_{*} \)를 이용해 \( \mathbf{q}_{*} \)계산하기

$$ \mathbf{q}_{*}(s, a) = r_{s}^{a} +\gamma \sum_{s^{'} \in S} P_{ss^{'}}^{a} \nu_{*}(s^{'}) $$

이 식은 벨만 기대방정식 1단계 \( \mathbf{q}_{\pi}(s, a) \)와 거의 같다. \( \pi \)가 * 로 변경되었다고 보면 된다.

이 식의 의미는 다음과 같다.

상태 s에서 액션a 의 액션밸류의 최대값은 그 상태에서 a액션 선택했을 때 받는 보상과 , 전이확률에 의해 다음 상태로 이동했을 때 이동한 상태에서의 최적의 상태밸류들의 합산 값을 감마 만큼 감쇠한 값을 합산한 것이다.

3) 2단계 수식 설명

1단계 수식 2개를 조합하여 2단계 수식을 구성할 수 있다.

2단계 수식을 사용하여 최적밸류를 계산하기 위해서는 기대방정식에서와 같이 보상과 전이확률을 알고 있어야 한다.

즉, MDP를 알고 있을 때 사용할 수 있는 수식이다.

정리차원에서 위에서 나온 벨만 기대 방정식과 최적 방정식을 같이 나열해본다.

1. 벨만 기대 방정식

2. 벨만 최적 방정식

벨만 방정식을 큰 틀에서 정리해보면,

MDP 상에서 정책 \( \pi \) 가 주어지고 해당 정책을 평가해야 하는 경우 벨만 기대방정식을 사용하여 계산한다.

최적의 밸류를 찾아야 할 경우는 벨만 최적방정식을 사용한다.

이후 과정에서 벨만 방정식에 대해 더 세부적으로 다룰 것이다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

앞으로 이야기는 어떤 문제의 상황이 주어졌을 때 MDP의 형태로 만들어서 MDP를 풀어 문제를 해결해 나가는 방법을 논의할 것이다.

여기서 MDP를 푼다는 것은 MDP 형태 (S, A, P, R, \( \gamma \) )가 주어졌을 때 아래 2가지 문제를 해결하는 것을 의미한다.

(1) Prediction : 에이전트가 액션을 선택하는 방법에 대한 정책함수 \( \pi \) 가 주어졌을 때 각 상태의 밸류를 평가하는 문제

(2) Control : 최적 정책 \( \pi^{*} \)를 찾는 문제

좀 더 자세히 살펴보기 위해 그리드 월드 예시를 살펴본다.

- 먼저 그리드 월드상에서 Prediction을 설명한다.

Prediction을 하려면 당연히 에이전트가 액션을 취하는 방법인 정책 \( \pi \)가 주어져야 한다.

처음에는 간단하게 모든 상태에서 4방향으로 랜덤하게 움직이는 정책으로 정한다.

수식으로 표현하면 아래와 같다

$$ A= \left [ 동쪽으로 이동, 서쪽으로 이동, 남쪽으로 이동, 북쪽으로 이동 \right ] $$

$$ \pi(동 \vert s) = 0.25, \pi(서 \vert s) = 0.25 , \pi(남 \vert s) = 0.25, \pi(북 \vert s) = 0.25 $$

이런 MDP 모델에서 \( s_{11} \)의 상태 가치 \( \nu_{\pi} (s_{11}) \)의 값은 얼마일까?

이것이 Prediction 문제이고 해당 상태의 밸류(상태가치함수)를 예측(계산)하는 것이 목적이다.

수식으로 표현하면 앞에서 언급된 상태가치함수이다.

$$ \nu_{\pi} (s_{11}) = \mathbb{E} \left [ G_t \vert S_t = s_{11} \right ] $$

\( s_{11} \)에서 취할 수 있는 액션이 4가지 이므로 그에 따라 이동경로도 여러 경우가 나온다.

예를 들면, 

각각의 이동경로는 에피소드 라고 하며 

상태가치함수를 계산하기 위해서는 위의 에피소드의 각각의 경우에 대해 발생확률과 리턴값을 얻어내어 확률과 리턴값을 곱하여 기댓값을 계산해야 한다.

하지만 복잡한 환경에서는 모든 에피소드를 찾아내는 것이 불가능하므로 실제로 계산시에는 언급한 것처럼 계산하지는 않는다.

실제 계산방식은 뒤에서 설명이 이어진다. 여기서는 개념만 이해하고 넘어가도록 한다.

정리하면, Prediction 문제는 주어진 상태에서의 상태가치함수 계산을 통해 상태의 가치를 계산해 내는 문제이다.

- Control 문제

Control의 목적은 최적의 정책 \( \pi^{*} \)를 찾는 것이다.

복잡한 MDP 모델 상에서 최적의 정책을 찾는 것은 매우 어려운 일이며 이를 위해서 강화학습을 진행하게 된다.

최적의 정책 \( \pi^{*} \)를 따를 때의 가치 함수를 최적가치함수 라고 하며 \( \nu^{*} \)라고 표기한다.

만일, 최적의 정책 \( \pi^{*} \) 와 최적가치함수 \( \nu^{*} \)를 찾았다면 주어진 MDP를 풀었다고 한다.

다시 언급하면, 이후에는 Prediction 과 Control에 대한 내용을 중심으로 다루게 될 것이다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

1. MDP의 정의

MRP에 에이전트 요소가 추가되어 각 상황마다 에이전트가 액션을 취하고 그것에 의해 다음 상태로 이동하며 환경으로부터 보상을 받게 되는 프로세스이다.

수식으로 정의하면 아래와 같다.

$$ MDP \equiv ( S, A, P, R, \gamma ) $$

- 상태의 집합 S

  해당 프로세스에서 가능한 모든 상태의 집합이다.

- 액션의 집합 A

해당 프로세스에서 취할 수 있는 모든 액션을 모아놓은 집합이다.

예를 들면, 포트폴리오를 운영하는 펀드매니저를 모델링한다면 펀드매니저가 취할 수 있는 모든 행동은 "매수하기", "매도하기", "관망하기" 이렇게 3가지로 정리할 수 있으며 따라서 액션 집합 A는 

                                              A={ 매수하기, 매도하기, 관망하기 }

에이전트는 스텝마다 위 액션의 집합 중 하나를 선택하여 액션을 취하며 그에 따라 다음 상태가 달라진다.

- 전이확률행렬P

$$ P_{ss^{'}}^a $$

위 식의 의미 : 현재상태가 s 에서 에이전트가 액션 a를 선택했을 때 다음상태가 \( s^{'} \) 이 될 확률

즉, 에이전트가 같은 행동을 하더라도 그 결과로 매번 같은 상태로 변하지 않으며 다음상태 변화는 정해놓은 확률 분포를 따른다는 의미이다.

전이확률의 엄밀한 정의는 다음과 같다

$$ P_{ss^{'}}^a = P[S_{t+1} = s^{'} \vert S_t = s, A_t = a ] $$

- 보상함수 R

MRP 에서는 상태 s 에서 바로 보상이 정해졌지만 MDP에서는 상태 s에서 에이전트가 액션 a를 선택해야 보상을 정할 수 있게 된다. 물론 여기서 보상도 확률적으로 접근되어 액션 a 를 선택해도 매번 보상은 달라지므로 보상의 기댓값을 사용해야 한다

MDP 에서 보상함수 R은 다음과 같다

$$ R_{s}^a = \mathbb{E}[R_{t+1} \vert S_t=s, A_t = a] $$

- 감쇠인자 \( \gamma \)

MRP에서의 \( \gamma \) 와 동일한 개념이다.

- MDP에서의 핵심은 보상의 합을 최대화하기 위해서 에이전트는 각 스텝에서 어떤 액션을 선택해야 할까를 정하는 것이다.

이 룰을 정책 (Policy) 이라고 한다. 좀 더 세부적으로 정책에 대해 알아보기로 한다.

2. 정책함수와 2가지 가치함수

- 정책함수

정책함수는 전체 보상의 합이 최대가 되기 위해서 각 상태에서 어떤 액션을 선택할 지 정해주는 함수이다.

정책함수 수식은 아래와 같다.

$$ \pi (a \vert s) = \mathbb{P} \left [  A_t = a \vert S_t = s \right ] => 상태 s에서 액션 a를 선택할 확률 $$

예를 들어, MDP 상의 상태 \( s_0 \) 에서 선택할 수 있는 액션이 \( a_0, a_1, a_2 \) 3가지 라고 할 때

정책함수는 \( s_0 \) 상태에서 에이전트가 \( a_0 \) 액션을 선택할 확률, \( a_1 \) 액션을 선택할 확률, \( a_2 \) 액션을 선택할 확률을 결정한다.

예를 들어, 수식으로 표현하면 아래와 같다

$$ \pi ( a_0 \vert s_0 ) = 0.2 $$

$$ \pi ( a_1 \vert s_0 ) = 0.5 $$

$$ \pi ( a_2 \vert s_0 ) = 0.3 $$

\( s_0 \)에서 취할 수 있는 모든 액션의 확률을 더하면 1.0 이 되어야 한다.

중요한 점은 정책 또는 정책함수는 에이전트가 가지고 있는 중요 기능이다. 

또한 강화학습을 통해 에이전트는 이 정책함수를 계속 고쳐나가야 한다.

- 상태가치함수

MRP 에서 가치함수는 상태가 주어지면 리턴의 기댓값으로 가치를 계산할 수 있었다.

하지만 MDP에서는 임의의 상태에서 에이전트의 액션이 결정이 되어야 그 액션에 따른 상태와 보상이 결정되며 그에 따른 리턴이 계산될 수 있게 된다.

다시 정리하면, 상태 S에서 정책함수 \( \pi \)가 결정되어야 리턴이 계산되어 가치함수의 결과를 도출할 수 있다.

수식으로 정리하면 다음과 같다

$$ \nu_{\pi}(S) = \mathbb{E}_{\pi}[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3} + ...\vert S_t=s] $$

리턴부분을 G 기호로 변환하면 아래와 같다

$$ \nu_{\pi}(S) = \mathbb{E}_{\pi}[G_{t} \vert S_t=s] $$

이 식의 의미는 상태 S부터 에피소드 끝까지 정책함수\( \pi \)를 따라서 움직일 때 얻는 리턴의 기댓값 이다.

중요한 것은 MDP 에서 상태가치함수는 정책함수에 의존적이다 라는 것이다.

- 액션가치함수

"각 상태에서 액션의 가치도 평가할 수 없을까?"

임의의 상태에서 취할 수 있는 액션의 가치를 모두 평가해본 후 그 중 가장 가치가 높은 액션을 선택하면 성능이 좋은 에이전트가 될 것이다.

이런 이유로 "상태-액션가치함수" 라는 개념이 나온다. 축약해서 "액션가치함수" 라고 한다.

"상태-액션 가치함수"의 정의를 수식으로 표현하면 아래와 같다

$$ \mathbf{q}_{\pi} (s,a) = \mathbb{E}_{\pi} \left [ G_t \vert S_t = s, A_t = a \right ] $$

(  s에서 a를 선택하고, 그 이후에는 \( \pi \)를 따라서 움직일 때 얻는 리턴의 기댓값 )

인풋 인자로 상태s 와 액션 a가 페어로 들어가는 것과 조건부식에 액션이 포함되는 것만 다르고 나머지는 상태가치함수와 같다.

상태-액션가치함수 인풋 인자로 상태 s 가 들어있는 이유는 무엇일까?

액션(a)의 가치를 평가할 때 항상 함께 고려해야 할 것이 상태(s)이다.

먼저 상태(s)가 정해지고 해당 상태에서 액션(a)을 취할 때 가치를 평가하는 것이 의미가 있다.

상태없이 액션만을 평가하는 것은 의미가 없고 틀린 결과를 도출해 낼 것이다.

예를 들면, \( S_0 \)  상태에서 액션 \( a_1 \)을 취해서 변경되는 다음상태와 보상은,  \( S_2 \)  상태에서 액션 \( a_1 \)을 취해서 변경되는 다음상태와 보상하고 서로 다르기 때문에 상태 s 에 대한 정보 없이 액션 a 만을 가지고는 정확하게 액션의 가치를 평가할 수 없다.

상태가치함수 \( \nu_{\pi}(s) \)와 상태-액션가치함수 \( \mathbf{q}_{\pi}(s,a) \) 는 주어진 상태 s 에서 어떤 액션을 취하는가 하는 부분에 차이가 있다.

상태가치함수 \( \nu_{\pi}(s) \)는 상태 s 에서 정책 \( \pi \)에 따르는 확률 분포에 의해 액션 a가 선택되어 지는 것을 고려한 함수이고, 

상태-액션가치함수 \( \mathbf{q}_{\pi}(s,a) \) 는 주어진 상태 s 에서 특정 액션 a로 선택된 것을 감안한 함수이다.

상태 s에서 액션 a가 선택된 이후에는 2가지 가치함수 모두 정책 \( \pi \) 에 따라 에피소드가 진행되는 점을 고려한다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

2. 마르코프 리워드 프로세스 (Markov Reward Process)

마르코프 프로세스에 보상의 개념이 추가된 프로세스이다.

위 그림은 아이가 잠이 드는 과정을 마르코프 프로세스로 모델링하여 표현한 것이다.

아이가 특정 상태에 들어오면 그에 따른 보상을 받게 되어 있다.

MRP를 정의하기 위해서는

보상함수 \( R \)과 감쇠인자 \( \gamma \) (감마) 가 추가로 필요하다

$$ MRP \equiv ( S, P, R, \gamma ) $$

- 보상함수 R

R은 어떤 상태 s에 도착할 때 받는 보상을 의미한다

$$ R = \mathbb{E} \left [ R_t \vert S_t = s \right ] $$

기댓값이 나온 이유는 특정 상태에 도달했을 때 받는 보상이 매번 조금씩 다를 수 있기 때문이다.

예를 들어, 어떤 상태에 도달하면 보상을 줄 때 동전을 던져 앞면이 나오면 500원, 뒷면이 나오면 받지 못한다고 하면 실제 보상은 매번 달라질 것이다. 이런 경우 기댓값을 적용하면 보상은 250원이 된다. 

기댓값의 이런 성격을 이용하여 어떤 상태에 도달했을 때 보상을 일반화해서 표현을 할 때 기댓값이 사용되는 것이다.

거꾸로 생각해보면 어떤 값을 표현할 때 기댓값을 사용했다는 의미는 그 값이 항상 나오는 고정된 값이 아니라는 의미를 내포하고 있는 것이다.

- 감쇠인자 \( \gamma \) 

\( gamma \) 는 강화학습에서 미래 얻을 보상에 비해 당장 얻을 보상을 얼마나 더 중요하게 여길 것인지 나타내는 파라미터이다. ( 0 에서 1 사이의 숫자 )

더 구체적인 설명을 위해 우선 리턴 이라는 개념을 이해해야 한다.

- 감쇠된 보상의 합, 리턴

MRP 모델에서는 상태가 바뀔때마다 보상을 받는다.

상태 \( S_0 \) 에서 시작하여 보상 \( R_0 \)를 받고 이어서 다음 상태로 전환되면서 보상을 받는 프로세스로 진행되다가 마지막 상태 \( S_T \) 에서 \( R_T \) 보상을 받고 종료된다.

이와 같이 시작상태에서 마지막 상태까지 이동하는 과정을 에피소드 라고 한다.

에피소드를 기호로 표시하면 아래와 같다.

$$ S_0, R_0, S_1, R_1, ... , S_T, R_T $$

리턴 ( \( G_t \) )이란 t 시점 이후 상태 \( S_{t+1} \)에서부터 에피소드가 종료할 때까지의 미래에 받을 감쇠된 보상의 합이다

$$ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} + ... $$

\( \gamma \)의 값이 0에서 1 사이 값이므로 먼 미래 시점 항은 \( \gamma \)를 여러 번 곱해지면서 계산값은 작아져 0에 가까워진다.

결국 t 시점의 리턴값은 먼 미래에 받을 보상의 영향은 줄이고 가까운 미래에 받을 보상의 영향을 크게 하는 방식으로 계산된다.

엄밀히 말하면 강화학습은 리턴값이 최대화되도록 학습하는 방식이라고 할 수 있다.

리턴은 과거의 보상값은 포함시키지 않는다. 과거는 중요치 않다는 것이다.

\( \gamma \)는 왜 필요한가?

\( \gamma \)를 1에 가까운 값을 사용하게 되면 미래 보상값이 리턴에 거의 그대로 영향을 주게되며 이것은 먼 미래도 중요시 생각하는 장기적인 시야를 갖도록 하는 모델이 되도록 할 것이다.

반대로 \( \gamma \)를 0에 가까운 값을 사용하게 되면 먼 미래 보상값은 0에 가깝게 작아지게 되어 근시안적인 모델이 되도록 할 것이다.

 1) 수학적 편리성 때문에

\( \gamma \)를 1보다 작게 해줌으로 리턴 \( G_t \) 가 무한의 값을 가지는 것을 방지할 수 있다.

따라서 다양한 수학연산에 리턴값을 활용할 수 있게 된다.

 2) 사람의 선호 반영

사람은 먼 미래에 보상보다 가까운 미래에 보상을 더 선호한다.

3) 미래에 대한 불확실성 반영

먼 미래 상태는 확률적으로 더 불확실 하므로 그에 대한 보상 역시 불확실성을 반영하여 감쇠시킨다

- MRP에서 각 상태의 밸류 평가하기

어떤 상태의 가치를 평가할 때 과거보다 미래를 고려하여 평가하게 된다.

MRP에서도 특정 시점의 상태에 대한 가치 밸류를 계산하려면 해당 시점 기준으로 미래에 받을 보상들의 합이 높으면 그 상태 밸류가 높다고 생각할 수 있다.

여기서 이야기한 미래에 받을 보상의 합이 바로 리턴값 ( \( G_t \) ) 이다.

문제는 리턴값이 매번 바뀐다는 점이다.

확률적 요소에 의해 다음 상태가 정해지므로  t 시점 기준으로 다음 도달 상태들이 매번 달라질 수 있다. 결국 그에 대한 보상이 달라지므로 보상의 합인 리턴값이 매번 바뀐다는 것이다.

이때 사용되는 개념이 기댓값 이다.

상태가치함수(State Value Function)

상태가치함수는 임의의 상태 S를 인풋으로 넣으면 그 상태의 밸류를 아웃풋으로 출력하는 함수이다.

$$ \mathcal{V}(S) =  \mathbb{E} \left [ G_t \vert S_t = s \right ] $$

조건부로 붙는 \( S_t = s \)의 의미는 시점 t에서 상태 s부터 시작하여 에피소드가 끝날 때까지의 리턴을 계산하라는 뜻

같은 상태에서 출발하여도 주어진 확률분포때문에 매번 실행할 때마다 에피소드가 달라지면서 리턴값이 달라지므로 

상태가치함수의 인풋으로 동일한 S를 입력하여도 결과 리턴값이 다르게 나오게 된다.

이런 경우 위에서 언급한 기댓값 성질을 이용한다.

여기서 \( S_t \) 상태의 가치를 계산하는 방법으로 리턴의 기댓값을 사용한다는 의미는 무엇일까?

\( S_t \) 상태부터 종료상태까지 해당 프로세스를 상당히 여러번 실행시켜 다양한 에피소드 샘플들을 얻어 각 샘플 에피소드의 리턴값을 합산 후 평균을 냄으로 기댓값으로 활용할 수 있다는 의미이다.

정리하면, MRP에서는 상태별 보상을 줌으로 현재 상태에 대한 리턴 이라는 개념을 추가하게 되었으며 이 리턴이 결국 상태가치함수 값이 된다.

다음은 MDP에 대한 설명으로 넘어간다