[CS234] Assignment 1 풀이

코딩 과제를 풀면서 느낀 점은, 전반적으로 강의 내용과 다르다는 점이다.

과제 풀이가 있었으면 좋겠다고 생각했지만,

코딩에 주석이 상세하게 달려있거나 

도식화해서 설명해 놓은 글을 찾을 수가 없어서 직접 작성해보았다.

 

Assignment 1의 코딩 과제 (4번) 풀이는 다음과 같다.

먼저 알아야 할 것은 환경 설정이 어떻게 되어 있는가 하는 것이다.

뭘 풀어야 하는 것인지에 대한 내용이 없다 보니,

코드가 잘 이해가 가지 않을 수 있다. 

 

이 문제는 OpenAI에서 만든 Frozen Lake라는 배경을

강화학습을 통해 빠져나가도록 하는 게 목표이다.

S로 표시된 Start 지점에서 G로 표시된 Goal까지 이동해야 하는데

중간에 H로 표시된 구멍에 빠지면 게임이 리셋된다.

F라고 표시된 완벽하게 얼어있는 부분만 잘 딛고 지나가야 하는 셈이다.

 

우리야 이렇게 지도를 보고 있으니까 최단기간을 잘 찾아내지만

한 치 앞 밖에 모르는 게임 속 세계에서는 

조금씩 이동하면서 지도를 만들어가는 수 밖에 없다.

 

또 주의해야 하는 점은, 강의에서는 모델을 줄 때

각 상태별로 받는 보상을 담은 Reward 행렬과,

한 상태에서 다른 상태로 이동하는 확률을 담은 P행렬을 준 바 있다.

 

하지만 이 문제에서는 P행렬은 조금 복잡하게 생겼으며 Reward행렬은 따로 주어지지 않는다.

P 행렬은 이렇게 생겼다. 

결국 상태가 바뀌는 확률과 그에 따른 보상 등은 

P[state][action]을 통해 조회가 가능한데

처음 접한다면 상당히 난해해서 어떤 변수를 어떻게 조회하고 있는가 감이 오지 않는다.

 

또한 코드를 짜는 가장 좋은 방법은

Pseudocode(프로그래밍 언어가 아닌, 일반 언어로 구현한 알고리즘)를 참조하는 것인데

파이썬 코드에 가장 가까운 수도코드는

강의에서도 가끔씩 참조되는 Sutton & Barto의 교과서에 실려있다.

 

위 수도코드에서 $\Sigma$부분만 유의해서 코드로 구현하자면 아래와 같다.

먼저 Policy Evaluation 코드.

def policy_evaluation(P, nS, nA, policy, gamma=0.9, tol=1e-3):
	"""Evaluate the value function from a given policy.

	Parameters
	----------
	P, nS, nA, gamma:
		defined at beginning of file
	policy: np.array[nS]
		The policy to evaluate. Maps states to actions.
	tol: float
		Terminate policy evaluation when
			max |value_function(s) - prev_value_function(s)| < tol
	Returns
	-------
	value_function: np.ndarray[nS]
		The value function of the given policy, where value_function[s] is
		the value of state s
	"""

	value_function = np.zeros(nS)

	############################
	# YOUR IMPLEMENTATION HERE #
	while True:
		delta = 0
		for s in range(nS):
			v = 0
			for prob, next_state, reward, terminal in P[s][policy[s]]:
				v += prob*(reward + gamma*value_function[next_state])
			delta = max(delta, np.abs(value_function[s] - v))
			value_function[s] = v
		if delta < tol:
			break
	############################
	return value_function

$\Sigma$로 곱해줘야 하는 확률, 보상 등의 값이 P행렬 안에 묶여있어서

for 구문으로 빼내주는 과정을 거쳤다. (28~29번째 줄)

그 이외에는 수도코드와 거의 차이가 없다.

 

Policy Improvement 코드는 아래와 같다.

def policy_improvement(P, nS, nA, value_from_policy, policy, gamma=0.9):
	"""Given the value function from policy improve the policy.

	Parameters
	----------
	P, nS, nA, gamma:
		defined at beginning of file
	value_from_policy: np.ndarray
		The value calculated from the policy
	policy: np.array
		The previous policy.

	Returns
	-------
	new_policy: np.ndarray[nS]
		An array of integers. Each integer is the optimal action to take
		in that state according to the environment dynamics and the
		given value function.
	"""

	new_policy = np.zeros(nS, dtype='int')

	############################
	# YOUR IMPLEMENTATION HERE #
	for s in range(nS):
		option = np.zeros(nA)

		for a in range(nA):
			
			option[a] = P[s][a][0][0]*P[s][a][0][2] + gamma*(P[s][a][0][0]*value_from_policy[P[s][a][0][1]])
			
		new_policy[s] = np.argmax(option)
	
	############################
	return new_policy

이건 따로 확률, 보상 등의 값을 P행렬에서 빼주는 과정을 거치지 않고

P행렬 안의 좌표를 일일이 불러내는 방법을 사용했다.

 

각 상태별 행동 경우의 수를 전수 조사해서 option 리스트에 저장해두고는

np.argmax 함수를 통해 가장 성공률이 높은 행동을 뽑아내는 방식이다.

 

이 두 함수(Policy Evaluation, Policy Improvement)를 모으면 Policy Iteration을 할 수 있다.

강의에서는 아래와 같은 알고리즘을 사용했다.

이를 그대로 파이썬으로 옮길 수 있다.

심지어 코드 줄 수도 거의 비슷하다. 앞의 함수들도 그랬지만...

def policy_iteration(P, nS, nA, gamma=0.9, tol=10e-3):
	"""Runs policy iteration.

	You should call the policy_evaluation() and policy_improvement() methods to
	implement this method.

	Parameters
	----------
	P, nS, nA, gamma:
		defined at beginning of file
	tol: float
		tol parameter used in policy_evaluation()
	Returns:
	----------
	value_function: np.ndarray[nS]
	policy: np.ndarray[nS]
	"""

	value_function = np.zeros(nS)
	policy = np.zeros(nS, dtype=int)
	
	############################
	# YOUR IMPLEMENTATION HERE #
	i = 0
	prev_policy = np.ones(nS, dtype=int)
	while i == 0 or abs(sum(policy - prev_policy)) > tol:
		prev_policy = np.copy(policy)
		value_function = policy_evaluation(P, nS, nA, policy, gamma=0.9, tol=10e-3)
		policy = policy_improvement(P, nS, nA, value_function, policy, gamma=0.9)
		i = i+1   
		print(policy)     
	   
	############################
	return value_function, policy

 

(b) 번문제는 Value Iteration에 관한 문제이다.

강의를 들으면서 찾아본 바로는

Policy Iteration 방식이 더 우수하다고 검색이 되었는데,

막상 코드를 적어보니

두 함수를 조합해야 하는 Policy Iteration 보다는

자체 함수로 끝낼 수 있는 Value Iteration 방식이 더 간편했다.

def value_iteration(P, nS, nA, gamma=0.9, tol=1e-3):
	"""
	Learn value function and policy by using value iteration method for a given
	gamma and environment.

	Parameters:
	----------
	P, nS, nA, gamma:
		defined at beginning of file
	tol: float
		Terminate value iteration when
			max |value_function(s) - prev_value_function(s)| < tol
	Returns:
	----------
	value_function: np.ndarray[nS]
	policy: np.ndarray[nS]
	"""

	value_function = np.zeros(nS)
	policy = np.zeros(nS, dtype=int)
	############################
	# YOUR IMPLEMENTATION HERE #
	while True:
		delta = 0
		for s in range(nS):
			temp = value_function[s]
			option = np.zeros(nA)
			for a in range(nA):
				option[a] = P[s][a][0][0]*(P[s][a][0][2]+gamma*value_function[P[s][a][0][1]])
			value_function[s] = np.max(option)
			delta = max(delta, abs(temp - value_function[s]))
			policy[s] = np.argmax(option)
			print(policy)
		if delta < tol:
			break
	############################
	
	return value_function, policy

코드 내용은 Policy Iteration과 큰 차이가 없다.

다만 policy iteration 방식이 최적의 행동만 무아서 

그 행동의 효율을 검토하는 방식을 사용했다면

value iteration은 모든 행동에 대해 효율성을 검토하는 방식인지라

데이터가 많아질수록 policy iteration이 더 빠르게 실행될 것이라는 생각이 들었다.

---

코드로 실제 알고리즘을 구현해보니

강의에서 놓쳤던 부분을 새로 알게 되기도 하고,

학습 방식을 다시 한 번 복습하는 시간이 될 수 있었다.

 

다만 아직까지는 기초적인 알고리즘을 구현했지만

당장 다음 과제부터는 실제 아타리 게임을 강화학습으로 풀어내는 방식인지라

훨씬 어려워질 것으로 생각된다.

사실 이번 과제도 풀어내는데 3일 정도 걸린 것 같다. 

그것도 온전히 풀어낸 것도 아니고, 결과적으로는 수도코드를 베낀 셈이지만...

또 다음 과제에서는 실력이 더 늘어나있기를 기대해본다.