[Monte Carlo methods - 4] Off-Policy Monte Carlo

Off-policy Monte Carlo

Off-policy strategy

Off-policy 에서는, Exploratory policy와 Target policy를 분리하고 각각 다른 policies를 사용한다.

 

Exploratory policy ($b(a|s)$)

: Exploratory policy는 Task를 수행하면서 State, Action, Reward를 포함한 Experience(tarjectory)를 수집한다. Experience들은 Target policy를 학습시키는데 사용된다.

$$ S_0, A_0, R_1, S_1, A_1, ..., R_T $$

 

Target policy ($\pi(a|s)$)
: Optimal policy를 찾기 위해서 실질적으로 개선되는 Policy이다. Exploratory policy를 통해 수집된 Experience를 통해서 update된다. -> Off-policy로 불리는 이유

$$ \pi(s) \gets \arg\max_a Q(s,a) $$

 

당연한 말일수도 있지만, Off-policy가 제대로 작동하기 위해서는 Exploratory policy는 Target policy의 모든 action을 cover해야한다. 이 조건이 만족하지 않는다면, Exploatory Policy가 행하지 않는 Action의 Q-value는 Target Policy에서 update되지 않을 것이다.

 

$$ if $\pi(a|s) > 0, \quad then \quad b(a|s) > 0 $$

Problem

Exploratory policy의 returns를 수집하기 때문에 우리가 그것들일 average하게된다면, 우리는 target policy가 아닌 exploratory policy에 대한 q-value를 근사하는 것이된다.

 

$$ E_b[G_t|s_t=s, A_t = a] = q_b(s,a) $$

 

이를 해결하기 위해서는 Exploratory policy의 returns에 뭔가를 해서 그들의 average가 target policy를 represent하도록 해야한다.

Importance sampling

Exploratory policy의 returns가 target policy를 represnet하도록 하기위해 Importance sampling이라는 통계적인 기법을 사용한다. 어떤 시점 t에서 행할 수 있는 Action에 대해서 Target policy하에 해당 Action을 행할 확률에서 Exploratory policy하에 해당 Action을 행할 확률을 나눈 값을, 행할 수 있는 모든 Action에 대해 순차적으로 곱한 값을 $W_t$라고 한다. 이를 Exploratory policy하에서 구한 $G_t$에 곱하여 조정된 return을 사용함으로써, Target policy에 대한 근사를 할 수 있다.

 

$$ W_t = \prod_{k=t}^{T-1}{\pi(A_k|s_k)\over b(A_k|s_k)} \qquad E[W_tG_t|S_t = s] = v_\pi(s)$$

 

Update Rule

기존의 방법은 $(s,a)$마다, 우리는 observed returns들의 list를 보관하여 $Q(s,a)$를 update 해야할 때마다 average를 다시 계산했었다.

 

$$ [G_1, G_2, ..., G_N] \qquad Q(s,a) \gets {1\over N}\sum_{k=1}^N G_k$$

 

이 방법은 returns를 저장해야해야하고 매번 average를 계산하는 것을 반복해야하므로 비효율적이다. 따라서 위 방법 대신에 On-Policy mc 2번째 실습에서 사용했던 constant alpha Monte carlo를 사용할 것이다.

 

$$ Q(s,a) \gets Q(s,a) + {W_t \over C(s,a)}[G-Q(s,a)] \qquad \alpha = W_t/C(s,a)$$

 

Importance sampling 값이 너무 과장되거나 너무 축소되는 것을 막기위해 모든 Importance sampling ratio들의 합으로 normalize한다. 이는 Importance sampling ratio를 0 ~ 1의 값으로 만들어 learning process를 smooth하게 만들어준다는 뜻이다.

 

$$ C(s,a) = \sum_{k=1}^N W_k$$

Algorithm

1. On-policy에서는 $(s, a)$에 대한 returns를 keep a table 했지만, 여기서는 $(s, a)$에 대한 Importance sampling ratio들의 sum을 keep a table한다. 이는 각 $(s, a)$ 마다 Importance sampling ratio를 normalize 하는데 사용된다.
2. Exploratory policy를 사용하여 trajectory를 만든다.
3. 이후 Exploratory policy를 이용하여 계산된 return을 사용하여 시간 역순으로 Target policy 하에 Q-value를 update한다. 이 과정에서 Importance sampling ratio를 사용한다.
4. Exploratory Policy에 의해 수집된 $A_t$ 와 현재 Target Policy 하에 $A_t$가 다를 경우 loop를 멈추고 다음 episode로 넘어간다. 만약 $A_t$가 같을 경우 Importance sampling ratio를 update하고 loop를 계속한다.
   • 이렇게 하는 이유: (s, a) 공간이 매우 커질 경우 현실적으로 모든 공간을 explore 하는 것은 현실적이지 않다. 따라서 두 $A_t$가 다를 경우 Target Policy에 대한 update가 잘 이루어지지 않을수도 있으므로 현재 episode를 멈추고 다음 episode에 대해서 학습하는 것이다.
5. episode의 수만큼 2 ~ 4번을 반복한다.

Exercise

[실습 환경 (Maze)]

 

[알고리즘 구현 코드]

def target_policy(state):
    av = action_values[state]
    # action value(Q-value)가 가장 높은 Action들 중 random하게 선택
    return np.random.choice(np.flatnonzero(av == av.max()))
    

def exploratory_policy(state, epsilon=0.):
    if np.random.random() < epsilon:
        return np.random.choice(4)
    else:
        av = action_values[state]
        return np.random.choice(np.flatnonzero(av == av.max()))
        

def off_policy_mc_control(action_values, target_policy, exploratory_policy, episodes, gamma=0.99, epsilon=0.2):
    
    csa = np.zeros((5, 5, 4))
    
    for episode in range(1, episodes + 1):
        G = 0
        W = 1
        state = env.reset()
        done = False
        transitions = []
        
        while not done:
            action = exploratory_policy(state, epsilon)
            next_state, reward, done, _ = env.step(action)
            transitions.append((state, action, reward))
            state = next_state
            
        
        for state_t, action_t, reward_t in reversed(transitions):
            G = reward_t + gamma * G
            csa[state_t][action_t] += W
            qsa = action_values[state_t][action_t]
            action_values[state_t][action_t] += (W / csa[state_t][action_t]) * (G - qsa)
            
            if action_t != target_policy(state_t):
                break
            
            # exploratory policy의 action과 target policy의 action이 같다는 뜻은 exploratory policy에서
            # 1 - epsilon의 확률로 target policy와 같은 policy를 따랏다는 뜻이므로 아래와 같이 계산
            W = W * 1. / (1 - epsilon + epsilon / 4)

exploratory policy는 epsilon greedy 방법으로 explore 한다. epsilon의 확률로 random action을 행하고 1 - epsilon의 확률로 Target policy와 같은 알고리즘으로 Action을 택한다. 결국 이러면 e-greedy on-policy와 똑같은 것이 아니냐는 의문이 생길 수 있는데, off-policy에서는 target-policy에 e-greedy를 직접적으로 적용하지 않음으로써 때때로 불필요한 탐색이 policy 개선에 영향을 주는 것을 방지할 수 있다. on-policy는 이에비해 구현의 간단하고 직관적이라는 장점이 있다.

[실습 결과 Q-value]
: on-policy와는 다르게 target-policy가 e-greedy한 explore를 하지않고 exploratory-policy만 explore했으므로 최단거리와 관계없는 action value들은 초기를 제외하면 완벽하게 무시된 것을 아래 table에서 볼 수 있다. 이로써 알 수 있는 off-policy의 장점은 target-policy가 goal에 완벽하게 집중할 수 있게 해준다.

[실습 결과 Policy]