[Monte Carlo methods - 3] On-Policy Monte Carlo

On-policy Monte Carlo

Exploration of the environment를 maintain하기 위한 method 중 하나

$\epsilon$-greedy policy

: Exploration of environment를 maintain하기 위해 낮은 확률로 random action을 수행하도록 만드는 Policy이다. 모든 Action의 확률은 0보다 크며, $\epsilon$ 의 확률로 random action이 선택되고 $1-\epsilon$ 의 확률로 가장 높은 $Q(s, a)$를 가진 Action이 선택된다. 이 Policy는 시간이 지날수록 모든 action을 선택해볼 것이고, 이는 예상보다 더 좋은 결과를 도출해낼 수도 있다.

• $\left | A \right |$는 가능한 action의 개수이다.

$$ \pi(a|s) = \begin{cases}1-\epsilon+\epsilon_r & a=a^* \ \epsilon_r & a\ne a^*\end{cases} $$

$$ \epsilon_r = {\epsilon\over|A|} $$

예시로 만약 $\epsilon = 0.2$이고 행동 가능한 Action이 4가지라면, 위 공식에 따라 가장 높은 Q-value를 가지는 Action이 선택될 확률은 0.85이고 나머지 Action들 3가지가 선택될 확률은 각각 0.05이다.

Algorithm

1. $\epsilon$ 과 $\gamma$를 적절한 값으로 설정하고, Q-value를 임의의 값으로 초기화한다. 종료조건의 Q-value는 0이다.
2. Policy는 모든 episode가 끝날 때 까지 높은 Q-value 선택하는 전략을 가진 e-greedy이다.
3. 현재의 episode가 끝날 때까지 Agent가 Environment와 상호작용시키면서 trajectory를 얻는다.
4. Return을 0으로 초기화한다.
5. 모든 State를 방문하면서 (시간 역순으로) return을 계산하고, (s, a) pair에 해당하는 Return table에 저장한다. 이때, 해당 (s, a) pair Return들의 평균을 해당 Q-value($Q(s, a)$)로 update한다.
   • 이때, 시간 역순으로 계산하는 이유는 모든 reward를 구해놓고 시간 정순으로 계산하는 것보다 역순으로 reward를 얻을 때마다 계산하는 것이 효율적이기 때문이다.
6. 모든 episode가 끝날 때까지 3 ~ 5번과정을 반복한다.

• e-greedy Policy를 사용하여 간헐적으로 random action을 행함으로써, 이 모든 과정이 끝나면 완벽한 Optimal인지는 알 수 없지만, Optimal에 근접한 Policy와 Q-value를얻을 수 있다.

Exercise

[실습 환경 (Maze)]

 

[알고리즘 구현 코드]

def policy(state, epsilon=0.2):
    # 0이상 1미만의 값을 샘플링해서 epsilon과 비교
    if np.random.random() < epsilon:
        # 0 ~ 4미만의 정수 값을 샘플링 
        return np.random.randint(4)
    else:
        av = action_values[state]
        # flatnonzero(조건) : 조건에 맞는 원소들의 인덱스 리스트를 반환
        # 즉, 아래 코드는 가장 높은 value를 가진 action들 중 하나를 랜덤하게 선택함
        return np.random.choice(np.flatnonzero(av == av.max())) 
        

def on_policy_mc_control(policy, action_values, episodes, gamma=0.99, epsilon=0.2):
    
    # (s, a)에 해당하는 returns들을 저장하는 딕셔너리
    sa_returns = {}
    
    
    for episode in range(1, episodes + 1):
        # 환경을 reset
        state = env.reset()
        done = False
        # episode 동안 agent의 State, Action, Reward를 기록하는 List (Trajectory)
        transitions = []
        
        while not done:
            action = policy(state, epsilon)
            next_state, reward, done, _ = env.step(action)
            transitions.append([state, action, reward])
            state = next_state
        
        G = 0
        
        # 시간 역순으로 returns를 계산
        for state_t, action_t, reward_t in reversed(transitions):
            G = reward_t + gamma * G
            
            if not (state_t, action_t) in sa_returns:
                sa_returns[(state_t, action_t)] = []
            
            sa_returns[(state_t, action_t)].append(G)
            
            action_values[state_t][action_t] = np.mean(sa_returns[(state_t, action_t)])

[실습 결과 Q-value]

[실습 결과 Policy]
: Policy는 (0, 0)에서 Goal에 대해서 최단거리로 이끌어준다. 최단거리 루트에 포함되지 않는 State들 중 (0, 0)과 비교적 가까운 State들은 어느정도 알맞은 Policy를 가지고 있지만, 최단거리 루트에 포함되지 않으면서 (0, 0)과 먼 State들은 잘못된 Policy를 가지고있다. 왜냐하면, on-policy이기 때문이 explore 또한 점점 Goal에대한 최단거리를 찾아가기 때문에 최단거리 루트에 포함되지 않으면서 (0, 0)과 먼 State들에대한 Explore가 충분히 이루어지지 않았기 때문이다.

[계산을 효율적으로 하기위한 Constant Alpha를 사용해서 구현]

$$ Q(s, a) \gets Q(s, a) + \alpha[G - Q(s, a)] $$

: 기존의 방법과 다른 점은 각 (s, a)에 대한 returns들을 episode마다 계속 저장하여 averaging하는 것이 아니라, return을 즉각적으로 $\alpha$ 만큼 Q-value에 반영한다. (constant alpha)

def on_policy_mc_control(policy, action_values, episodes, gamma=0.99, epsilon=0.2, alpha=0.2):
    
    for episode in range(1, episodes+1):
        state = env.reset()
        done = False
        transitions = []
        
        while not done:
            action = policy(state, epsilon)
            next_state, reward, done, _ = env.step(action)
            transitions.append([state, action, reward])
            state = next_state
        
        G = 0
        for state_t, action_t, reward_t in reversed(transitions):
            G = reward_t + gamma * G
            
            # constant alpha
            qsa = action_values[state_t][action_t]
            action_values[state_t][action_t] += alpha * (G - qsa)