[RL] Do it 강화 학습 입문 1장 - 강화 학습이란?

1-1. 강화 학습 멀리서 훑어보기

머신러닝 내의 학습

지도학습이란

데이터와 각 데이터에 대한 레이블이 주어졌을 때 새로운 데이터에 대한 레이블을 매기는 방법을 학습하는 것

 

비지도학습이란

레이블 없이 주어진 데이터에 대해 데이터를 분류하거나 밀도를 추청하는 방법을 학습하는 것

 

강화학습이란

상태에 따른 행동에 대한 보상으로 상태에 대한 행동을 찾는 것

 

의사 결정을 위한 강화 학습

강화학습은 의사 결정을 위한 인공지능 방법론이다. 다르게 말하면 강화 학습을 제대로 구현하기 위해서 사람의 의사 결정이 어떻게 이루어지는지 이해해야 한다.

 

 

1-2. 마르코프 결정 과정(MDP, Markov Decision Process)

MDP 정의

상태(state, s1): 에이전트가 환경 내 특정 시점에 관찰할 수 있는 것을 수치화

행동(action, a1-1, a1-2): 에이전트가 환경에게 전달하는 입력

보상(reward): 에이전트가 환경으로부터 전달받은 목적을 달성하기 위해 행동을 잘 수행하고 있는지 피드백하는 신호

모델(model): 행동에 따른 상태 전이가 일어날 확률을 담은 규칙

 

초기 상태에서 출발해 다양한 상태와 각 상태에서 취할 수 있는 행동으로 원하는 목표까지의 과정을 탐색하는 것

 

행동에 의한 상태 전이에 확률 도입

에이전트가 특정 행동을 취하면 반드시 상태가 원하는대로 바뀌지 않는다

 

상태 전이 확률: 어떤 상태에서 어떤 행동을 할 때 결과를 정의

P(s1, a1-2)와 같이 표현

 

이러한 확률의 집합을 모델이라 한다

 

정리

MDP는 상태 집합 S로 이루어지며, 행동 집합 A가 있다

상태 s에서 행동 a를 통해 상태 s'로 전이할 확률을 P(s'|s, a), 그 보상은 R(s,a)이다

 

보상 총합

목표는 현재 상태에서 환경으로부터 얻을 수 있는 장기적 보상의 예측치를 극대화하는 행동 찾기

즉 MDP 상태 안에서 최적의 행동 찾기

 

보상 총합이 무한으로 발산하는 문제

에이전트의 상태 변경 횟수에 제약을 받지 않고 특정 상황을 무한히 왕복할 때

보상 총합이 무한으로 발산하는 문제

 

시간에 따른 할인 개념 도입

시간에 따른 할인은 에이전트가 최대한 가까운 시점에 보상을 얻게하는 장치

새로운 에피소드마다의 보상에 할인율을 제곱하여 더하여 보상의 총합을 계산

보상의 총합이 무한으로 발산되는 것을 방지

 

주어진 상태에서 미래에 얻을 수 있는 보상 총합

주어진 상태에서 최적의 행동을 찾기 위해

주어진 상태에서 미래에 얻을 수 있는 보상의 총합을 구해야 한다

 

이익(return)은 t번째 상태에 대한 보상과 할인율의 곱의 합으로 나타낼 수 있다

 

전체 경로에 대한 평균, 이익의 기대값을 구하면 미래에 얻을 수 있는 보상의 총합이다

가치 함수 V(s)는 상태 s 일때 이익의 평균 값이다

 

보상, 이익, 가치

보상(R): 특정 상태에서 얻을 수 있는 즉각적인 피드백

이익(G): 한 에피소드의 특정 상태에서 종단 상태까지 받을 수 있는 보상 총합

가치 함수(V): 특정 상태로부터 기대할 수 있는 보상

 

가치 계산

계산 방법

상태 s에서 행동 a를 선택할 때

상태 전이 확률 * 가치 * 할인율 의 합

 

현재 상태의 가치를 구해 주는 벨만 방정식

다음 상태의 가치로 현재 상태의 가치를 계산

V(s) = R(s) + (V(s'))

 

현재 상태의 가치를 구하려고 다음 상태를 계속 추적하므로

결국 종단 상태에 도달하여 종단 상태의 가치로 상태를 역추적하며 계산

종단 상태의 가치는 종단 상태의 보상과 같으므로 이미 알려진 값 -> 동적 계획법 알고리즘 사용

 

벨만 방정식 풀기

가치 반복법: 동적 계획법 기반으로 가치 함수를 산출하는 방식

 

모든 상태의 가치를 구한 결과를 바탕으로 행동을 선택할 수 있다

다시 초기 상태로 돌아가 각 상태에 대해 미래 보상을 최대화하는 최적 행동을 선택할 수 있다

 

즉 상태를 입력으로 받아 최적 행동을 출력하는 매핑 함수가 만들어진다

이러한 함수를 정책(policy)이라 하며, 정책을 구하는 것이 강화 학습의 목표이다

 

강화 학습의 목표, 정책

정책: 지금 상태에서 해야 할 최적의 행동을 계산

π(s) = a

 

최적의 가치 함수는 Vπ(s)로 구할 수 있다

 

정책 평가와 정책 개선

정책 반복법

정책 π(s)는 무작위로 초기화

π(s)가 주어진 것은 에이전트가 어떤 상항에서 어떤 행동을 해야하는지 지시받았음을 의미

 

가치 반복법과의 차이

: 모든 행동에 대해 이익의 기대값을 계산하고 최대치를 고르는 것이 아니라

주어진 행동 π(s)에 대한 이익의 기대값만 계산하면 된다

 

정책 평가(E): 주어진 정책에 따라 가치 함수를 구하는 일

정책 개선(I): 정책과 무관한 다른 행동의 가치가 클 경우 기존 정책을 가치가 더 큰 새로운 행동으로 업데이트

 

격자 세계로 알아보는 가치 반복법

실습 코드 참고

 

python gridworld_value_iteration.py

 

기존 코드의 경우(gamma = 0.9)

3번 반복 후에 가치 함수가 수렴

...

3  번째 반복
---------------------------
0.81 | 0.90 | 1.00 | 0.00 | 
---------------------------
0.73 | 0.00 | 0.90 | 0.00 | 
---------------------------
0.66 | 0.73 | 0.81 | 0.73 | 

가치 함수: 
---------------------------
0.81 | 0.90 | 1.00 | 0.00 | 
---------------------------
0.73 | 0.00 | 0.90 | 0.00 | 
---------------------------
0.66 | 0.73 | 0.81 | 0.73 | 

정책: 
---------------------------
  R  |  R  |  R  |     |
---------------------------
  U  |     |  U  |     |
---------------------------
  U  |  R  |  U  |  L  |

 

gamma = 0.8인 경우

4번 반복 후에 가치 함수가 수렴

...

4  번째 반복
---------------------------
0.64 | 0.80 | 1.00 | 0.00 | 
---------------------------
0.51 | 0.00 | 0.80 | 0.00 | 
---------------------------
0.41 | 0.51 | 0.64 | 0.51 | 

가치 함수: 
---------------------------
0.64 | 0.80 | 1.00 | 0.00 | 
---------------------------
0.51 | 0.00 | 0.80 | 0.00 | 
---------------------------
0.41 | 0.51 | 0.64 | 0.51 | 

정책: 
---------------------------
  R  |  R  |  R  |     |
---------------------------
  U  |     |  U  |     |
---------------------------
  U  |  R  |  U  |  L  |

 

gamma = 0.99인 경우

3번 반복 후에 가치 함수가 수렴

3  번째 반복
---------------------------
0.98 | 0.99 | 1.00 | 0.00 | 
---------------------------
0.97 | 0.00 | 0.99 | 0.00 | 
---------------------------
0.96 | 0.97 | 0.98 | 0.97 | 

가치 함수: 
---------------------------
0.98 | 0.99 | 1.00 | 0.00 | 
---------------------------
0.97 | 0.00 | 0.99 | 0.00 | 
---------------------------
0.96 | 0.97 | 0.98 | 0.97 | 

정책: 
---------------------------
  R  |  R  |  R  |     |
---------------------------
  U  |     |  U  |     |
---------------------------
  U  |  R  |  U  |  L  |

 

1-3. 모델 프리 강화 학습

가치 반복법은 브루트 포스 방식으로 모델을 구하는 데에 엄청난 자원이 필요하다

 

몬테카를로 학습(Monte Carlo, MC학습)

모델에 대한 완전한 지식이 필요하지 않은 모델 프리(model-free) 강화 학습 기법

에이전트가 모든 상태를 몰라도 환경 탐색 과정을 거치는 상태에 대해서만 가치 함수를 업데이트

탐색을 진행하면서 경험을 누적하여 계산량 감소

 

개념

정책을 초기에 무작위로 설정

무작위로 설정한 정책에 따라 가치 함수를 추정하고, 추정한 가치 함수로 정책을 개선

개선한 정책에 따라 가치 함수를 추정하고, 추정한 가치 함수로 다시 정책을 개선

두 과정을 반복

 

정책 반복법과의 다른 점은

MC 학습은 완전한 가치 함수가 아닌 가치 함수의 추정치만 얻을 수 있으며, 

MC 학습은 환경 내모든 상태의 가치 함수를 추정하는 것이 아니라, 에이전트가 에피소드 안에서 거쳐간 상태의 가치 함수만 추정한다

 

에이전트가 환경의 모든 상태를 거친다고 보장하지 못하기 때문에 에이전트가 실제로 모든 에피소드를 겪을 필요가 없다

 

특징

1. 에이전트는 주어진 상태에서 행동을 취했을 때 어떤 상태로 전이할지, 어떤 보상이 주어질지 알지 못한다

2. 에이전트는 경험의 표본으로부터 학습

3. 현재까지 겪은 모든 에피소드에 대해 상태의 이익 G를 평균하여 상태의 가치 함수를 계산

4. 에피소드 하나를 완전히 끝낸 다음 업데이트

5. 에피소드 단위 문데에 한해 적용

 

이러한 특징으로 MC 학습은 에피소드가 무한히 이어지는 환경에서는 적용할 수 없다

또한 복잡도가 매우 높아 에피소드가 끝나지 못한 채로 상태 전이를 오래할 수 있다

 

전이 확률이 주어지지 않는다고 가정하므로

에이전트가 어떤 행동을 한 다음 상태를 바탕으로 구한 s의 가치 함수가 의미 없다

그 상태에서 어떤 행동을 했는지에 따라 이후의 이익 G가 완전히 달라지는데

전이 확률을 모르므로 특정한 행동이 그 상태의 최선 행동이라는 것이 보장되지 않는다

 

행동-가치 함수 도입

Q함수: 행동-가치 함수

Q(s,a): 상태 s에서 행동 a를 취했을 때의 장기적인 보상에 대한 평균

기존의 V(s)에 행동 a를 추가

 

한계

MC 학습은 테트리스와 같이 에피소드가 무한히 되면 학습이 느려진다

 

시간차 학습(Temporal Difference, TD학습)

테트리스와 같이 무한히 할 수 있는 게임이나

한 에피소드 자체가 긴 경우 적용하는 학습 기법

 

TD 학습의 개념

MDP 정보가 없는 모델 프리 학습이며, 경험으로부터 직접 학습

 

상태 변화가 있을 때마다 Q함수를 업데이트하므로

하나의 에피소드가 완전히 끝나지 않아도 단계마다 학습

 

수식

기존의 MC 학습의 Q함수 업데이트 공식은

Q(S,A) = (1-1/N) Q(S,A) + (할인율)Gt+1

N회의 에피소드에 대한 G에 할인율을 곱한후 평균하여 계산

 

TD학습은 다음 단계 보상 Rt+1과 Q함수 Q(St+1,At+1)가 반환하는 값을 사용하여 현재의 Q 값을 업데이트

Q(St+1, At+1)로 Q(S,A)를 추정한다

Q(St, At) = Q(St,At) + a(Rt+1 + ..)

 

가치 반복법과 비교

Q함수의 초기값은 0

첫 번째 에피소드에서는 보상이 있는 상태로 전이하는 경우에만 이전 상태의 Q 함수를 갱신

 

TD학습은 에이전트가 거치는 상태와 행동에만 Q함수를 갱신

전체의 일부를 샘플링

At+1에 따라 달라지기 때문에 선택하는 기준이 중요

 

At+1을 선택하는 엡실론-탐욕 알고리즘

기본적으로 탐욕 알고리즘을 사용했지만

상태, 행동 공간이 넓은 환경에서는 가치 함수를 최대하는 이용하는 탐욕 알고리즘으로 수렴한 정책보다 더 좋은 정책이 나올 수 있다

 

엡실론-탐욕 알고리즘은

에이전트가  가치 함수를 이용하면서 새로운 영역을 탐험할 수 있도록

여지를 주는 알고리즘을 사용하여 최적의 행동과 정책을 찾을 수 있다

 

예시로

기존 상태 S에서 S1, S2, S3로 갈 수 있는 상황이다

그 중 S2의 가치가 가장 높다면, S2로 가기 위한 행동을 선택할 것이다

 

S2로 가지 않을 확률이 ε라면

S2로 갈 확률은 (1-ε), S1과 S3로 갈 확률을 ε/2이다

 

TD학습에서 At+1을 선택할 때 엡실론-탐욕 알고리즘을 사용하면

탐색에 덜 진행된 상태에서 학습 결과가 수렴하는 것을 막을 수 있다

 

TD학습은 단계마다 현재 취득한 보상과 다음 단계의 Q함수를 업데이트하고

갱신한 Q함수를 바탕으로 엡실론-탐욕 알고리즘을 적용해 행동을 판단하여 이것을 정책으로 사용한다

 

TD학습에서 At+1을 선택하기 위해 엡실론-탐욕 알고리즘을 사용하면

환경 탐색이 덜 된 상태에서 학습 결과가 수렴하는 것을 막을 수 있다

 

TD학습은 단계마다 현재 취득한 보상과 다음 단계의 Q 함수로 현재의 Q함수를 업데이트하고

갱신한 Q함수를 바탕으로 엡실론-탐색 알고리즘을 적용해 행동을 판단하며 정책으로 사용한다

 

이 알고리즘은 임의의 정책인 (s)를 사용하여 행동 A를 취하고

다음 단계에서 Q함수를 추정할 때 같은 (s)를 사용하여 행동At+1을 선택한다

이는 행동 정책과 학습 정책이 같다

 

이 경우 Q함수를 업데이트 하는 정책에 탐험 요소가 사용되면 수렴 속도가 느려진다

그렇다고 행동 정책과 학습 정책에 탐욕 알고리즘을 모두 사용하면

빠르게 수렴할 수 있지만 학습이 충분히 탐색하지 못해 최적의 정책으로 수렴하지 않을 수 있다

탐험과 이용 사이의 균형

이용은 안정된 보상을 받을 수 있다고 알려진 길을 택하는 것이고

탐험은 높은 보상을 받을 가능성이 있으나 실패할 위험이 있는 길을 택하는 것이다

 

탐욕 알고리즘은 탐험을 배제한 이용이며

엡실론-탐욕 알고리즘은 엡실론 확률을 통해 가장 높은 가치 함수를 추구하지 않는 행동 중에서 하나를 무작위로 선택한다

랜덤 노이즈 알고리즘은 가치 함수의 추정치에 무작위값을 더해 탐험을 진행한다

 

Q학습

행동 정책(A)과 학습 정책(a)을 서로 다르게 하는 학습

TD학습의 Q함수 업데이트 수식과 유사하지만

행동 정책은 엡실론-탐욕 알고리즘을 따르고, 학습 정책은 탐욕 알고리즘을 따른다

 

{(0, 0): {'U': 0, 'D': 0, 'L': 0, 'R': 0.506}, (0, 1): {'U': 0, 'D': 0, 'L': 0, 'R': 0.724}, (0, 2): {'U': 0, 'D': 0, 'L': 0, 'R': 0.852}, (0, 3): {'U': 1, 'D': 1, 'L': 1, 'R': 1}, (1, 0): {'U': 0, 'D': 0, 'L': 0, 'R': 0.062}, (1, 1): {'U': 0, 'D': 0, 'L': 0, 'R': 0}, (1, 2): {'U': 0, 'D': 0, 'L': 0.465, 'R': -0.18}, (1, 3): {'U': -1, 'D': -1, 'L': -1, 'R': -1}, (2, 0): {'U': 0, 'D': 0, 'L': 0.054, 'R': -0.001}, (2, 1): {'U': 0, 'D': 0, 'L': 0.097, 'R': -0.005}, (2, 2): {'U': 0, 'D': 0, 'L': 0.127, 'R': -0.028}, (2, 3): {'U': 0, 'D': 0, 'L': 0, 'R': -0.154}}