questionet
MDP를 모를 때 Prediction 본문
바닥부터 배우는 강화 학습 Chapter 5
이번 챕터에서는 모델 프리상황에서의 prediction을 하는 2가지 방법에 대해 배운다.
= MDP를 모르는 상황에서 임의의 정책이 주어졌을 때 각 상태의 가치를 평가하는 2가지 방법에 대해 배운다.
1. 몬테카를로 학습
2. TD (Temporal Difference) 학습
용어 정리
MDP (Markov Decision Process) 를 모른다는 것의 의미
1. 보상함수(R)를 모른다 = 어떤 상태 s에 도착하게 됐을 때 받게 되는 보상이 뭔지 모른다
2. 전이확률행렬(P)을 모른다 = 현재 상태 s에서 어떤 액션a를 했을 때 가게 될 다음 상태들의 확률분포를 모른다
>>> 둘 다 액션을 해봐야 안다 = MDP를 모르는 상태 = 모델 프리 (모델을 모르는 상태)
정책 π : 정책함수 π(a|s) = P(At=a|St=s) 상태 s에서 액션a를 선책할 확률
각 상태의 가치를 평가 : 상태가치함수 Vπ(S) = 리턴의 기댓값 Eπ[Gt|St=s]
리턴 = t시점부터, 미래에 받을, 감쇠된 보상의 합
전이확률행렬 = 상태전이함수
5.1 몬테카를로 학습
몬테카를로 방법론 Monte Carlo
주의사항 : 보상함수와 전이확률을 인식하고 있는 지의 여부와, 그것이 존재하는 지의 여부를 혼동해선 안 된다.
MDP를 알고 모르고는 에이전트의 문제고,
(정확히 말하면 MDP를 안다는 건, 에이전트가 실제로 액션을 해보지 않아도 머릿속으로 시뮬레이션해서 학습할 수 있다는 뜻
i.e.플래닝)
MDP의 존재여부는 환경의 문제다.
테이블 룩업 방식으로 알고리즘을 구현한다고 했을 때
주요 과정은 다음과 같다.
1. 환경 GridWorld : 에이전트의 액션을 받아 상태변이를 일으키고, 보상을 줌 >> 아래 그리드 월드 클래스
2. 에이전트 : 4방향 랜덤 정책을 이용해 움직임 >> 아래 에이전트 클래스
3. 경험을 쌓는 부분 : 에이전트가 환경과 상호작용하며 만들어내는 데이터를 기록, 축적 >> 아래 메인함수
4. 밸류 계산 : 쌓인 경험을 통해 테이블을 업데이트 >> 아래 메인함수
코드를 바로 직접 살펴보며 몬테카를로 학습 알고리즘을 설명하겠다.
import random
import numpy as np
def main():
env = GridWorld() # 환경, 그리드월드 클래스 (아래 참고)
agent = Agent() # 강화학습의 주체, 에이전트 클래스 (아래 참고)
data = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] # 에이전트가 갈 수 있는 모든 상태의 '가치를 기록하는 테이블'
# 환경과 구조가 비슷하지만 의미하는 건 다르므로 혼동하지 말 것
gamma = 1.0 # 감쇠인자 값
reward = -1 # 보상 값
alpha = 0.001 # 각 상태의 가치를 얼마나 업데이트할 지 결정하는 파라미터
for k in range(50000): # left-top에서 출발해 right-bottom까지 도착하는 게 하나의 에피소드
# 이 에피소드를 총 50000만 시행하는 반복문
done = False # 매 애피소드의 종료조건
history = [] # 매 에피소드마다 에이전트가 지나간 상태의 위치와 보상값을 기록하는 히스토리 리스트
while not done: # 에피소드 하나가 끝날 때까지 에이전트가 움직이게 하는 반복문
action = agent.select_action() # 1. 에이전트가 4방향 중 한곳으로 액션을 취한다. (아래 에이전트 클래스참고)
(x,y), reward, done = env.step(action) # 2. 에이전트가 동서남북 중 한 방향으로 한칸 움직이면
# 도착한 상태가 어딘지 (x,y)
# 그 상태에서 받은 보상이 얼만지 (reword)
# 도착한 곳이 종료지점이면 done = True, 아니면 False를 반환한다
history.append((x,y,reward)) # 3. 히스토리 리스트에 x,y,reward를 튜플로 묶어 기록한다.
# 4. 종료지점에 도착했다면 while문 종료, 아니면 위 과정 1.~3.반복
env.reset() # 5. 에피소드 하나가 끝나면 에이전트의 위치를 다시 시작점으로 초기화
# 아래 그리드월드 클래스 참고
cum_reward = 0 # 6.리턴 값
for transition in history[::-1]: # 7.히스토리를 뒤에서부터 보며 상태 업데이트, 리턴을 계산한다
x, y, reward = transition # 8.히스토리에 담긴 값 언팩
data[x][y] = data[x][y] + alpha*(cum_reward-data[x][y]) # 9.각 상태(위치)의 밸류 계산, 업데이트
# 실제 수식은 책 111쪽 참고
cum_reward = reward + gamma * cum_reward # 10.리턴 계산, 업데이트 (책에 있는 코드는 오타로
# 깃헙의 수정된 코드로 바꿨습니다)
# 실제 수식은 책 116쪽 참고
# 11.에피소드 끝에서부터 맨 앞까지 위 과정 반복
# 계산이 다 끝나면
for row in data: # 12. 한 에피소드에서 얻은 테이블의 전체 상태를 출력
print(row)
# 위 1.~12. 과정을 50000번 반복class Agent():
def __init__(self):
pass
def select_action(self): # 위 메인함수의 16번 코드라인에서 반복문이 실행되면 제일 먼저 이 함수가 호출된다.
coin = random.random()
if coin < 0.25:
action = 0 # action = 0 , 1 , 2, 3 은 각각 서, 북, 동, 남을 의미
elif coin < 0.5: # 위의 난수 생성 함수에 따른 coin값에 의해 랜덤으로 에이전트의 액션결과가 정해진다.
action = 1
elif coin < 0.75:
action = 2
else:
action = 3
return action # 4방향 랜덤정책에 따른 에이전트의 액션을 반환
class GridWorld():
def __init__(self):
self.x=0 # 테이블은 4 x 4 크기. 에이전트의 초기 위치는 테이블의 left-top이므로
self.y=0 # x,y 좌표값은 0,0으로 초기화
# 따라서 x,y 값의 범위는 0~3까지라는 것을 알 수 있다.
# x, y는 에이전트가 테이블의 각 상태에 총 몇번 방문했는지 기록하는 역할을 한다.
def step(self, a): # 위 메인함수의 16번 라인에서 에이전트가 동서남북 중 한쪽방향으로 액션을 하면
# 에이전트의 액션을 받은 환경 그리드월드는 상태변이를 일으키고 보상을 에이전트에게 줘야하는데
# 이 역할을 하는게 step 함수다.
# 에이전트가 랜덤정책에 따라 액션을 하면 위 에이전트 클래스의 select_action 메서드에 따라
# 서쪽은 0, 북쪽은 1, 동쪽은 2, 남쪽은 3을 반환하고
# 각 숫자가 환경 Gridworld 클래스의 step메서드의 인자 a에 입력된다.
if a==0:
self.move_left() # 만약 랜덤정책에 따라 에이전트가 서쪽으로 움직였다면 아래에 있는 move_left() 메서드가 호출된다
elif a==1: # 이하 1, 2, 3 일때 각각 해당되는 메서드 호출
self.move_up()
elif a==2:
self.move_right()
elif a==3:
self.move_down()
reward = -1 # 에이전트가 어느쪽으로 움직이든 보상은 -1로 고정 << 보상은 환경이 주는 것
done = self.is_done() # 에이전트가 일으킨 한번의 액션에 따른 상태변이와 그에 대한 보상을 주고난 후
# 에이전트가 계속 움직여야 하는지 활동을 종료해도 되는 지를 알려주는 함수다.
# 아래 is_done()메서드 참고
return (self.x, self.y), reward, done
def move_right(self): # 이하 4개의 메서드는 에이전트가 매 에피소드마다 시작점에서 도착점까지 지나간 모든 좌표를
# 기록할 수 있게 하는 함수들이다.
# 다시 말해 각 상태를 몇번 방문했는지 기록
self.y += 1 # 동쪽으로 움직이면 y를 +1
if self.y > 3: # 테이블이 4 x 4 크기이므로 테이블 동쪽 끝에서 에이전트가 오른쪽으로 액션을 취하면 제자리에 위치
self.y = 3
def move_left(self):
self.y -= 1 # 서쪽으로 움직이면 y를 -1
if self.y < 0:
self.y = 0
def move_up(self):
self.x -= 1 # 북쪽으로 움직이면 x를 +1
if self.x < 0:
self.x = 0
def move_down(self):
self.x += 1 # 남쪽으로 움직이면 x를 -1
if self.x > 3:
self.x = 3
def is_done(self): # 에이전트의 액션에 따른 보상을 주고 에이전트의 위치를 기록한 후
# 에이전트가 계속 움직여야 하는지 결정하는 메서드다.
if self.x == 3 and self.y == 3: # 만약 에이전트가 도착점에 위치해 있다면
return True # True를 반환하고 위 24번 코드라인에 따라 done = True가 되어
else : # 메인함수에서 하나의 에피소드를 실시하는 while 반복문이 종료된다.
return False
def reset(self): # 매 에피소드가 끝날때마다 에이전트의 위치를 시작점으로 초기화하는 메서드
self.x = 0
self.y = 0
return (self.x, self.y)몬테카를로 그리드월드 학습결과
main()
[-59.11477141203388, -60.01662611648927, -60.55254782275037, -56.29858544036781]
[-56.52865616991303, -55.89339394009934, -52.00063593629217, -47.06750759283873]
[-51.89057750044844, -48.363582678400626, -38.92271045985149, -28.259751248994863]
[-48.79888729691329, -42.105247538099135, -28.333489910171316, 0.0]중요한 부분
위 코드에서 특별히 어려운 부분은 없다.
다만 위 메인함수에서 각 상태의 밸류를 업데이트하는 29번 코드라인이
data[x][y] = data[x][y] + alpha*(cum_reward-data[x][y])
왜 이런 수식형태를 갖게 되었는지 이해하는 게 중요할 것 같다.
data[x][y] 가 의미하는 것은 한 상태의 밸류다.
그 상태의 밸류를 업데이트하기 위해
그 상태의 원래 밸류 data[x][y] 에
리턴값cum_reward에서 원래 밸류값 data[x][y]를 빼고 알파를 곱한 값을 더해준 값을
그 상태의 새로운 밸류 data[x][y] 로 설정한다.
여기서 알파는 얼만큼 업데이트할지 크기를 결정해주는 파라미터로
알파가 크면 한번에 더 크게 업데이트 하게 된다.
이 수식이 수학적으로 어떻게 해서 왜 이러한 형태를 갖게 된 건지 공부할 것
5.2 Temporal Difference 학습
TD의 필요성
위에서 살펴본 바와 같이
몬테카를로 방식은 에피소드 하나가 다 끝날때까지 기다려야한다 (메인함수의 15번 코드라인이하)
리턴은 에피소드가 끝나기 전까진 알 수 없기 때문이다
바꿔 말하면 몬테카를로 방법은 MDP가 반드시 종료해야만 쓸 수 있다.
그러나 현실에선 종료조건이 따로 없는 MDP도 많다.
(인생은 죽기전까진 진행형이고(에피소드가 무지 길거나) 최종목표는 계속 바뀌므로(명확한 종료조건이 없거나))
따라서 에피소드가 끝나기 전에 prediction을 할 수 있는 방법이 있다면
에피소드가 끝나기 전에 밸류를 업데이트하여 필요에 따라 임의의 단계에서 prerdiction을 할수 있게 될 것이다.
다시 말해 종료하지 않는 MDP에서 에이전트가 학습을 하게 하려면 어떻게 해야 할까?
에피소드를 끝까지 가보지 않고, 최종 스텝 전의 임의의 스텝에서 가치를 평가하는 방법이 바로 TD이다.
예를 들어 t1, t2, t3,...t10 까지의 타임스텝이 있는 문제라 했을 때
t6까지만 가보고 t1,..t5까지의 밸류를 업데이트 하는 것이다
cf)몬테카를로 방법에선 t10까지 간 후 t1,...t9의 밸류를 업데이트 했었다.
몬테카를로 방법의 이론적 배경
가치함수의 정의는 리턴의 기댓값이므로
리턴Gt을 많이 모을수록 그 평균은 그 상태의 실제가치Vπ(St)에 수렴하게 된다. >> Vπ(St) = Eπ[Gt]
이를 바꿔 말하면
Gt는 Vπ(St)의 불편추정량이라고 한다.
TD의 이론적 배경
Vπ(St) = Eπ[Gt]
현재 상태 St의 밸류는 리턴의 기댓값이라는 위 식을 벨만 기대방정식으로 바꿔 쓰면 아래와 같이 된다.
Vπ(St) = Eπ[Rt+1 + γVπ(St+1)]
이 식은 리턴을 먼저 한 스텝 진행해 보상을 받고, 그 다음 상태인 St+1부터 미래에 받을 보상을 더한 걸 의미한다.
따라서 Rt+1 + γVπ(St+1)을 아주 많이 뽑아서 평균일 내도 그 평균은 Vπ(St)에 수렴하게 된다
TD에서는
Rt+1 + γVπ(St+1)를 TD 타깃이라고 부른다
그런데 우리는 MDP를 모르는 상황에서 prediction을 하는 문제를 풀고 있는 중이다.
prediction은 π가 주어졌을 때 각 상태의 밸류를 평가하는 문제고
Vπ(St)는 각 상태의 밸류를 평가하는 데 쓰이는 함수다.
몬테카를로에서는 에피소드를 끝까지 진행하므로 Vπ(St) = Eπ[Gt] 이 식을 사용할 수 있다.
(이 식을 사용해 밸류를 업데이트하는 코드는 data[x][y] = data[x][y] + alpha*(cum_reward-data[x][y]) 였다)
하지만 TD는 에피소드를 끝까지 진행하지 않고 밸류를 평가하는 방법이므로
Vπ(St)값을 알 수 없다.
Vπ의 의미는 정책 π의 실제 가치이기 때문이다. (이건 상술했듯 에피소드를 끝까지 진행해 봐야 알 수 있다)
우리가 찾고자 하는게 Vπ(St)이므로 그걸 알아내기 위해
Rt+1 + γVπ(St+1)를 그대로 쓸 수 없다.
그래서 TD에서는 Rt+1 + γV(St+1)를 사용해 샘플링한다.
TD에서 각 상태의 밸류를 업데이트하는 이 식을 코드로 구현하면 다음과 같다.
data[x][y] = data[x][y] + alpha*(reward+gamma*data[x_prime][y_prime]-data[x][y])
위 몬테카를로 학습 알고리즘에서 쓰인 메인함수와 달라진 부분을 전체적으로 비교해보면서
위 식의 의미를 이해해보자.
TD 학습 알고리즘
# TD의 메인함수
def main():
env = GridWorld()
agent = Agent()
data = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
gamma = 1.0
reward = -1
alpha = 0.01 # 알파값이 몬테카를로 방법보다 상대적으로 훨씬 커졌다.
# 몬테카를로에 있었던 히스토리 리스트가 사라졌다.
# 아래를 보면 알겠지만 리턴값을 저장하는 cum_reward 변수와 리턴 값 계산 공식 코드도
# 사라졌다.
for k in range(50000):
done = False
while not done:
x, y = env.get_state() # get_state()는 그리드월드 클래스에 추가된 메서드다 (아래 참고)
# 에이전트의 현재 상태 위치를 나타낸다.
action = agent.select_action()
(x_prime, y_prime), reward, done = env.step(action) # 에이젼트가 액션을 하면 그에 따른 상태변이와 보상이 반환되는데
# 액션에 의한 상태변이는 그리드월드 클래스의 step메서드에 따라
# self.x, self.y 에 입력되고, 이 값은 바뀐 상태의 위치를 나타내게 된다
# 그리고 이 값은 다시 x_prime, y_prime 에 바인딩된다.
x_prime, y_prime = env.get_state()
data[x][y] = data[x][y] + alpha*(reward+gamma*data[x_prime][y_prime]-data[x][y])
# 바뀐 상태에서 '바로 직전 상태'의 밸류가 업데이트 된다.
# 다시 말해 여기서 '바로 직전 상태'란
# 코드라인 13번에 저장된 에이전트의 현재 상태의 밸류,
# 바뀐 상태란 액션에 의해 바뀐 새로운 현재 에이전트의 상태 밸류를 의미하게 된다.
# 이렇게 에피소드가 완전히 끝나기 전에
# 에피소드가 진행중인 과정에서 상태변이가 일어나자마자 그 직후에
# 각 상태의 밸류를 업데이트 시키고
# 에피소드의 도착점에 이르면 위 과정을 50000번 반복한다.
env.reset() # 한 에피소드가 끝나면 에이전트를 시작점으로 되돌린다.그리드월드 클래스에 추가된 메서드
def get_state(self):
return (self.x, self.y)TD 알고리즘의 특징
이제 위 코드에서 TD의 알파값이 몬테카를로방법보다 훨씬 큰 이유를 알 수 있다.
위의 TD코드는 한번만 상태변이가 일어나면 그 즉시 밸류의 업데이트가 일어나는 구조이므로
리턴의 변동성이 매우 작다고 볼 수 있다.
(이를 분산이 낮다고 할 수도 있다)
따라서 그만큼 리턴의 기댓값을 계산할 때 틀릴 확률이 낮아지게 되므로
한번에 얼마나 업데이트 되는지 그 정도를 의미하는 알파값이 몬테카를로 방법때보다 더 커질 수 있는 것이다.
중요한 부분
위의 코드에서 보듯이 TD는 현재의 추측치를 다음 스텝의 추측치로 업데이트 해준다.
data[x][y] = data[x][y] + alpha*(reward+gamma*data[x_prime][y_prime]-data[x][y])
data[x][y] 현재의 추측치 data[x_prime][y_prime] 다음 스텝의 추측치 = 즉 액션을 하고 난 다음의 바뀐 밸류
그러니까 위에서 언급했던 TD타깃 Rt+1 + γVπ(St+1) 은
reward+gamma*data[x_prime][y_prime] 코드의 이 부분이 가리킨다고 볼 수 있다.
그런데 사실 reward+gamma*data[x_prime][y_prime] 이 부분이 의미하는 건
Rt+1 + γVπ(St+1) 게 아니라 Rt+1 + γV(St+1) 을 구현한 것이다.
그 이유는 앞서 한 번 말했듯이 TD 방법을 쓸 땐 Vπ(St) 를 알 수 없기 때문이다.
그렇다면 Rt+1 + γV(St+1) 이 값을 사용해서 업데이트 했을 때 그 값이 Rt+1 + γVπ(St+1)와 같아진다는 보장이 어디 있을까?
위 코드는 한 스텝만 진행하고 난 다음에 가치를 평가했지만
두 스텝, 세 스텝, n스텝을 진행하고 나서도 상태를 업데이트 할 수 있다고 생각해 볼 수도 있다.
Rt+1 + γRt+2 + γ^2Rt+3 + .....γ^nV(St+n)
이를 n스텝 리턴이라고 불러보자.
여기서 n이 무한이라고 하고, 이 MDP가 종료하는 문제라고 한다면
위 식은 결국 (에피소드를 끝까지 진행하고 나서 얻게 되는) 리턴이 된다.
바꿔 말하면 몬테카를로 방법론은 TD의 한 사례라 일반화해 볼 수 있다.
즉 위에서 구현한 코드 처럼 n=1일 때의 TD는 TD(0), TD-zero라 하고
n이 무한일 때는 몬테카를로 방법론이 되는 것이다.
n이 커질수록 (변동성, 분산)은 점점 커질 것이다.
대신 Rt+1 + γV(St+1) 과 Rt+1 + γVπ(St+1) 값의 차이 즉 편향성은 줄어들 것이다.
이러한 해석이
Rt+1 + γV(St+1) 이 값을 사용해서 업데이트 했을 때 그 값이 Rt+1 + γVπ(St+1)와 같아진다는 보장이 어디 있을까?
라는 질문에 대한 간접적인 답변이 된다.
적절한 n값을 찾는게 중요한 문제가 되는 것이다.
MC 와 TD 비교
1. 몬테카를로 방법은 MDP의 종료조건이 명확한 경우 유리
TD는 종료상태 없이 하나의 에피소드가 무한히 이어지는 MDP에서 사용가능
>>TD는 에피소드가 분명히 나뉘고 종료되는 MDP에도 쓸 수 있으므로 TD 승
2. 편향성, prediction의 결과 차이량에선
>>몬테카를로 방법 승
3. 분산(변동성)
TD는 스텝 길이를 조절해 사용할 수 있으므로
>> TD 승
'Deep learning > 강화학습' 카테고리의 다른 글
| 강화학습이란? (0) | 2021.03.02 |
|---|
