6. 몬테카를로 Control

몬테카를로 방법의 Control

어떤 상태에서 행동을 선택하는 정책에는 여러 종류가 있지만, 대표적으로 다음 세 가지가 있다:

1. 무작위로 행동을 선택하는 정책
2. 행동가치에 따라 확률적으로 행동을 선택하는 정책
3. 행동가치 중 가장 높은 행동을 선택하는 정책

이 중 3번은 탐욕정책(greedy policy) 으로, 행동가치가 가장 높은 행동만을 선택한다. 탐욕정책은 행동가치 함수가 충분히 학습된 후에는 효과적이지만, 학습 중에는 국소 최적해(local minimum) 에 빠질 위험이 있다.

그림 2.54 탐욕정책의 단점 예시

어떤 정책을 따르던 우연히 실선 경로로 먼저 도착지점에 도착했다고 하자. 실선 경로에 있는 상태들은 +1의 보상을 받게 되고, 이로 인해 C 상태에서는 오른쪽으로 가는 행동의 가치가 강화된다. 하지만 실제 최단 경로는 아래 방향이다. 경험 부족으로 인해 오른쪽으로만 계속 가게 되면, 학습은 국소해에 머물 수 있다.

이처럼 탐욕정책만을 사용할 경우 발생하는 문제를 해결하기 위해 ε-탐욕 정책(ε-greedy policy) 이 고안되었다. ε 값을 사용해 탐험(explore)과 이용(exploit)을 균형 있게 조절할 수 있다.

π(s,a) = {
  1 - ε + ε/|A(s)|  if a = A^*
  ε/|A(s)|          if a ≠ A^*
}

식 2.25

• |A(s)|: 상태 s에서 가능한 행동의 개수
• A^*: Q(s,a)를 최대로 하는 행동
• ε은 0 ≤ ε ≤ 1의 값을 가진다

예시로 상태 s에서의 행동가치가 다음과 같다면:

Q_π(s,a1) = 0.1  
Q_π(s,a2) = 0.2  
Q_π(s,a3) = 0.3  
Q_π(s,a4) = 0.4  

→ 최적 행동 A^*는 a4

이때 ε-탐욕 정책을 적용하면, ε 값에 따라 행동 선택 확률이 달라진다. ε = 1이면 네 행동 모두 0.25의 확률로 선택된다(완전 무작위), ε = 0이면 오직 a4만 선택된다(탐욕 정책). ε 값이 감소할수록 최적 행동의 선택 확률이 증가한다. 이를 시각화한 것이 그림 2.55다.

좀 더 단순화한 표현은 다음과 같다:

π(s,a) = {
  a = A^*     if random > ε
  random      otherwise
}

식 2.26

→ 확률적으로 ε보다 크면 최적 행동을 선택하고, 작으면 무작위로 선택한다. 본 문서에서는 교과서의 정식 정의인 식 2.25를 사용한다.

ε-탐욕 정책을 사용함으로써 몬테카를로 Control은 그림 2.54에서처럼 국소 최적 행동만 반복 선택하는 문제를 피할 수 있다.

---

몬테카를로 방법의 Control 알고리즘

알고리즘: 몬테카를로 방법의 Control

모든 s ∈ S, a ∈ A(S)에 대해 초기화:

    Q(s,a) <- 임의의 값
    Return(s,a) <- 빈 리스트
    π(s,a) <- 임의의 ε-탐욕정책

    무한 반복:
        (a) π를 사용해 에피소드 1개 생성
        (b) 에피소드에 출현한 각 s,a에 대해:

            R <- s,a의 처음 발생한 수익
            R을 Return(s,a)에 추가
            Q(s,a) <- average(Return(s,a))

        (c) 에피소드 안의 각 s에 대해:
            a^* <- argmax_a Q(s,a)
            모든 a ∈ A(S)에 대해

                π(s,a) = {
                1-ε+ε/|A(s)|  (a = a^*)
                ε/|A(s)|  (a ≠ a^*)
                }

→ 전체 흐름은 다음과 같다 (그림 2.56 참조):

1. 에피소드 생성
   • 초기 정책 π로 에피소드 생성
2. 행동가치 Q(s,a) 업데이트
   • 에피소드 결과로부터 return 값을 계산하고 평균으로 Q(s,a) 갱신
3. 정책 개선
   • Q(s,a)를 바탕으로 각 상태의 최적 행동 A^*를 찾고
   • ε-탐욕 정책을 이용해 새 π(s,a) 생성
4. 반복
   • 이 과정을 반복하며 최적 정책에 수렴

---

ε-탐욕 정책을 이용한 First-visit MC Control 구현

# 정책을 받아서 에피소드를 생성하는 함수
def generate_episode_with_policy(env, agent, first_visit, policy):
    gamma = 0.09
    # 에피소드를 저장할 리스트
    episode = []
    # 이전에 방문여부 체크
    visit = np.zeros((env.reward.shape[0], env.reward.shape[1],len(agent.action)))
    
    # 에이전트는 항상 (0,0)에서 출발
    i = 0
    j = 0
    agent.set_pos([i,j])    
    #에피소드의 수익을 초기화
    G = 0
    #감쇄율의 지수
    step = 0
    max_step = 100
    # 에피소드 생성
    for k in range(max_step):
        pos = agent.get_pos()        
        # 현재 상태의 정책을 이용해 행동을 선택한 후 이동
        action = np.random.choice(range(0,len(agent.action)), p=policy[pos[0],pos[1],:]) 
        observaetion, reward, done = env.move(agent, action)    
        
        if first_visit:
            # 에피소드에 첫 방문한 상태인지 검사 :
            # visit[pos[0],pos[1]] == 0 : 첫 방문
            # visit[pos[0],pos[1]] == 1 : 중복 방문
            if visit[pos[0],pos[1],action] == 0:   
                # 에피소드가 끝날때까지 G를 계산
                G += gamma**(step) * reward        
                # 방문 이력 표시
                visit[pos[0],pos[1],action] = 1
                step += 1               
                # 방문 이력 저장(상태, 행동, 보상)
                episode.append((pos,action, reward))
        else:
            G += gamma**(step) * reward
            step += 1                   
            episode.append((pos,action,reward))            

        # 에피소드가 종료했다면 루프에서 탈출
        if done == True:                
            break        
            
    return i, j, G, episode





# ϵ-정책을 이용하는 몬테카를로 control 알고리즘
np.random.seed(0)
# 환경, 에이전트를 초기화
env = Environment()
agent = Agent()

# 모든 𝑠∈𝑆,𝑎∈𝐴(𝑆)에 대해 초기화:
# # 𝑄(𝑠,𝑎)←임의의 값 (행동 개수, 미로 세로, 미로 가로)
Q_table = np.random.rand(env.reward.shape[0], env.reward.shape[1],len(agent.action))
print("Initial Q(s,a)")
show_q_table(Q_table,env)

# 상태를 방문한 횟수를 저장하는 테이블
Q_visit = np.zeros((env.reward.shape[0], env.reward.shape[1],len(agent.action)))

# 미로 모든 상태에서 최적 행동을 저장하는 테이블
# 각 상태에서 Q 값이 가장 큰 행동을 선택 후 optimal_a 에 저장
optimal_a = np.zeros((env.reward.shape[0],env.reward.shape[1]))
for i in range(env.reward.shape[0]):
    for j in range(env.reward.shape[1]):
        optimal_a[i,j] = np.argmax(Q_table[i,j,:])
print("initial optimal_a")
show_policy(optimal_a,env)

# π(𝑠,𝑎)←임의의 𝜖−탐욕 정책
# 무작위로 행동을 선택하도록 지정
policy = np.zeros((env.reward.shape[0], env.reward.shape[1],len(agent.action)))

# 한 상태에서 가능한 확률의 합이 1이 되도록 계산
epsilon = 0.8
for i in range(env.reward.shape[0]):
    for j in range(env.reward.shape[1]):
        for k in range(len(agent.action)):
            if optimal_a[i,j] == k:
                policy[i,j,k] = 1 - epsilon + epsilon/len(agent.action)
            else:
                policy[i,j,k] = epsilon/len(agent.action)
print("Initial Policy")
show_q_table(policy,env)


# 최대 에피소드 수 길이를 지정
max_episode = 10000

# first visit 를 사용할지 every visit를 사용할 지 결정
# first_visit = True : first visit
# first_visit = False : every visit
first_visit = True
if first_visit:
    print("start first visit MC")
else : 
    print("start every visit MC")
print()

gamma = 0.09
for epi in tqdm(range(max_episode)):
# for epi in range(max_episode):

    # π를 이용해서 에피소드 1개를 생성
    x,y,G,episode = generate_episode_with_policy(env, agent, first_visit, policy)
    
    for step_num in range(len(episode)):
        G = 0
        # episode[step_num][0][0] : step_num번째 방문한 상태의 x 좌표
        # episode[step_num][0][1] : step_num번째 방문한 상태의 y 좌표
        # episode[step_num][1] : step_num번째 상태에서 선택한 행동
        i = episode[step_num][0][0]
        j = episode[step_num][0][1]
        action = episode[step_num][1]
        
        # 에피소드 시작점을 카운트
        Q_visit[i,j,action] += 1

        # 서브 에피소드 (episode[step_num:])의 출발부터 끝까지 수익 G를 계산
        # k[2] : episode[step_num][2] 과 같으며 step_num 번째 받은 보상
        # step : 감쇄율
        for step, k in enumerate(episode[step_num:]):
            G += gamma**(step)*k[2]

        # Incremental mean : 𝑄(𝑠,𝑎)←𝑎𝑣𝑒𝑟𝑎𝑔𝑒(𝑅𝑒𝑡𝑢𝑟𝑛(𝑠,𝑎)) 
        Q_table[i,j,action] += 1 / Q_visit[i,j,action]*(G-Q_table[i,j,action])
    
    # (c) 에피소드 안의 각 s에 대해서 :
    # 미로 모든 상태에서 최적 행동을 저장할 공간 마련
    # 𝑎∗ ←argmax_a 𝑄(𝑠,𝑎)
    for i in range(env.reward.shape[0]):
        for j in range(env.reward.shape[1]):
            optimal_a[i,j] = np.argmax(Q_table[i,j,:])            
   
    # 모든 𝑎∈𝐴(𝑆) 에 대해서 :
    # 새로 계산된 optimal_a 를 이용해서 행동 선택 확률 policy (π) 갱신
    epsilon = 1 - epi/max_episode

    for i in range(env.reward.shape[0]):
        for j in range(env.reward.shape[1]):
            for k in range(len(agent.action)):
                if optimal_a[i,j] == k:
                    policy[i,j,k] = 1 - epsilon + epsilon/len(agent.action)
                else:
                    policy[i,j,k] = epsilon/len(agent.action)

print("Final Q(s,a)")
show_q_table(Q_table,env)
print("Final policy")
show_q_table(policy,env)
print("Final optimal_a")
show_policy(optimal_a,env)

---

결과 분석

그림 2.57: 학습 전후의 Q-table과 정책 테이블을 비교할 수 있다. 초기에는 무작위로 설정된 Q(s,a)와 정책이었지만, 학습을 거쳐 행동가치가 수렴하고 최적 정책이 형성되었다.

그림 2.58: 학습 전(A)과 학습 후(B)의 상태별 최적 행동을 비교한 그림이다. 학습 전에는 대부분의 상태에서 도착지점에 도달하지 못했지만, 학습 후에는 어떤 상태에서 시작하든 도착지점에 도달하는 경로를 형성하게 된다.