MDP를 모를 때 밸류 평가하기 1 - 몬테카를로 학습

강화 학습 스터디) 바닥부터 배우는 강화학습을 읽고 정리하였습니다.

 

MDP를 안다 → 보상함수 $r^a_{s}$와 전이 확률 $P^a_{ss’}$를 안다

MDP를 모른다 → 보상함수 $r^a_{s}$와 전이 확률 $P^a_{ss’}$를 모른다 !

이런 상황을 모델 프리(model free)라고 부름. 여기서 모델은 강화 학습에서 환경의 모델(model of environment)의 줄임말로, 에이전트의 액션에 대해 환경이 어떻게 답할지 예측하기 위해 사용하는 모든 것을 의미

몬테카를로 학습

chat gpt가 그린 그림. 스펠링은 여전히 틀리는구만

어떤 동전의 무게 중심이 한쪽에 치우쳐 있어서 앞면이 나올 확률이 50%가 아닐 때 앞면이 나올 확률을 아는 방법 → 여러번 시도하여 기댓값을 구하는 것 → MDP에 대한 정보를 모를 때 각 상태의 가치를 평가하는 문제와 매우 유사

즉, 동전을 100번 던졌을 때 앞면이 35번 나왔다면, 앞면의 확률이 35%라고 가늠해 볼 수 있음 → 몬테카를로 방법론(Monte Carlo Method)

따라서 전이 확률을 모르더라도, MDP에서도 똑같은 방법으로 각 상태의 가치를 평가할 수 있음

가치 함수의 정의 : $v_{\pi}(s_{t}) = \mathbb{E}{\pi}[G{t}]$ Chapter 3. 벨만 방정식

즉, 리턴을 여러번 계산하여 그 평균을 내면 그 값은 해당 상태의 실제 가치에 수렴할 것임

일단 에이전트를 환경에 갖다놓고 경험을 하도록 시킨 다음, 에피소드가 끝날 때 까지 얻었던 리턴들을 기록해 놓았다가 평균을 구함 → 대수의 법칙으로 각 상태의 밸류 예측치는 점점 정확해짐

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

1. 테이블 초기화
   1. 각 상태별로 N(s)와 V(s) 2개의 값이 필요
   2. N(s) → s를 총 몇번 방문했는지 세기 위해서 필요한 값
   3. V(s) → 해당 상태에서 경험했던 리턴의 총 합 

      

2. 경험 쌓기

1. 정책은 우리가 평가하고 싶은 아무 정책으로 설정(ex, random choice)
2. 그러면 에이전트는 $s_{0}$부터 시작하여 액션 $a_{0}$를 정하고, 그에 따른 보상 $r_{0}$를 받고 $s_{1}$에 도착
3. 그러면 각 상태에 대해 리턴을 계산할 수 있음($G_{0}, G_{1},..$)

3. 테이블 업데이트

• 앞의 경험 쌓기 단계에서 지나온 경로가 구체적으로 $s_{0}$→$s_{4}$→$s_{5}$→$s_{6}$→$s_{10}$→$s_{14}$→종료였다고 했을 때, 이미 각 상태에 따른 리턴도 계산이 되어 있음

• 

• 그러면 N과 V가 위와 같이 업데이트 됨, 모든 상태의 보상은 -1이고, 감마는 1로 계산하였음

4. 밸류 계산

1. 이를 계속 반복하여 얻은 N과 V를 통해 이 정책을 통한 $s_{t}$에서의 가치를 아래와 같이 계산할 수 있음
2. $v_{\pi}(s_{t}) \cong \frac{V(s_{t})}{N(s_{t})}$

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

1. $V(s_{t}) ← (1-\alpha)V(s_{t}) + \alphaG_{t}$
2. 이렇게 하면 N을 따로 저장할 필요는 없음

구현

• Grid world class

• import random
  
  class GridWorld():
  	def __init__(self):
  		self.x = 0
  		self.y = 0
  
  	def step(self, a):
  		if a==0:
  			self.move_right()
  		elif a==1:
  			self.move_left()
  		elif a==2:
  			self.move_up()
  		elif a==3:
  			self.move_down()
  
  		reward = -1
  		done = self.is_done()
  		return (self.x, self.y), reward, done
  
  	def move_right(self):
  		self.y += 1 #지금 여기서도 transition prob을 찾아볼 수 없음
  		if self.y > 3:
  				self.y = 3
  
  	def move_left(self):
  		self.y -= 1
  		if self.y < 0:
  				self.y = 0
  
  	def move_up(self):
  		self.x -= 1
  		if self.x < 3:
  				self.x = 3
  
  	def move_down(self):
  		self.x += 1
  		if self.x > 3:
  				self.x = 3
  
  	def is_done(self):
  		if self.x==3 and self.y==3:
  			return True
  		else :
  			return False
  
  	def get_state(self):
  		return (self.x, self.y)
  
  	def reset(self):
  		self.x = 0
  		self.y = 0
  		return (self.x, self.y)​

 

• Agent class

class Agent():
	def __init__(self):
		pass

	def select_action(self):
		coin = random.random()
		if coin < 0.25:
			action = 0
		elif coin < 0.5:
			action = 1
		elif coin < 0.75:
			action = 2
		else:
			action = 3

		return action

 

• main

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
	alpha = 0.0001

	for k in range(50000):
		done = False
		history = []
		while not done:
			action = agent.select_action()
			(x,y), reward, done = env.step(action)
			history.append((x,y,reward))
		env.reset()

		cum_reward = 0
		for transition in history[::-1]:
			x,y,reward = transition
			data[x][y] = data[x][y] + alpha*(cum_reward - data[x][y])
			cum_reward = reward + gamma*cum_reward


	for row in data:
		print(row)

 

참고 문헌

바닥부터 배우는 강화학습 - 노승은