[RL 이론] 2-3. Exploration과 Exploitation: UCB Algorithm

 

개요 

앞의 포스팅에서는 Multi-armed bandit problem 을 구현하고 모델의 학습을 위한 방법으로 Exploration, Exploitation, Epsilon decay, Incremental Implementation 등에 대해 알아봤습니다.

 

이번 포스팅에서는 초기 Reward 값을 높게 줘서 Exploration을 간접적으로 수행하는 Optimistic initial values 방법과, Action 들을 Random 하게 추출하는 대신 각 Action에 대해 Uncertainty 값을 주어 효율적으로 추출하는 방법인 UCB algorithm 을 살펴봅니다. 

 

본 포스팅에서 다루는 설명은 Sutton의 강화학습 책을 많이 참고하였습니다. 

관련 코드는 Github 에서 확인할 수 있습니다. 

 

Optimistic Initial Values 

앞에서 살펴본 Greedy method의 문제점은 Exploitation만 수행합니다. Exploitation만 수행했을 때의 문제는, 특정 Action-value 값이 초기에 설정한 Value 값보다 낮아지면 선택되는 Action이 변하지만 초기에 설정한 Value 값보다 높으면 그 Action만 선택하게 된다는 것입니다. 이로 인해 특정 Action의 Value 값이 Default 값보다 크게 되면 다른 Action을 시도해보지 못하게 됩니다.

 

그렇다면 Default로 주는 Value의 값을 예상되는 Reward 값보다 매우 높게 주면 어떨까요? 10-armed Bandit Problem에서 설정한 실제 Value 값은 $N(0, 1)$ 의 분포를 가지므로, Value의 초기값을 5로 주면 새로 받는 Reward 값들은 항상 기존의 Value 값보다 낮을 것이고, 모든 Action을 시도해볼 가능성이 높습니다. 이러한 방법을 Optimistic initial values 라고 합니다.

 

Optimistic initial values를 구현하기 위해 Agent의 __init__ 메소드에 initial_q_value를 입력할 수 있게 만들었습니다.

 

class Agent():
    def __init__(self, n_action, initial_q_value = 0):
        self.n_action = n_action 
        self.initial_q_value = initial_q_value
        self.step_size = 0.1
        self.init_values()

    def init_values(self):
        # 실제 optimal q value 생성 
        self.pred_q_value_list = [self.initial_q_value for _ in range(self.n_action)]

 

Optimistic Initial values 방법의 학습 진행에 따른 평균 Reward 값

Optimistic Initial values 방법의 학습 진행에 따른 최적의 Action을 수행할 확률

 

위 그래프는 Optimistic initial values 를 $\epsilon$-greedy method와 비교한 결과입니다. 초기에는 Exploration을 더 많이 하기 때문에 Optimistic initial values가 성능이 떨어지지만 어느 정도 지나면 Exploration이 급격히 줄고 Exploitation만 하기 때문에 $\epsilon$-greedy method보다 성능이 좋아집니다.

 

Upper-Confidence-Bound Action Selection (UCB)

앞의 Optimistic initial values를 통해 Exploration이 필요한 Action은 Value의 값을 증가시키면 된다는 것을 알았습니다. 하지만 Optimistic initial values 는 간접적으로 Exploration을 수행한 것이기 때문에 어느정도 시점이 지나면 특정 Action만을 반복하게 됩니다. $\epsilon$-greedy method 또한 Action들에 대해 랜덤하게 뽑기 때문에 불필요한 Exploration 으로 수렴 속도가 느리다는 단점이 있습니다.

 

Exploration을 보다 효율적으로 할 수 있는 방법은 없을까요? $\epsilon$-greedy method에서 Random한 Action을 선택하는 것이 아니라, 각 Action의 Uncertainty 가 높은 행동을 하여 Uncertainty를 낮추는건 어떨까요?

 

$$A_t \doteq \text{argmax}_a \Bigg[ Q_t(a) + c \sqrt{{\ln t \over N_t(a)}} \Bigg]$$

 

이러한 아이디어로 나온 것이 UCB 입니다. UCB는 각 Action의 수행 횟수와 Step 수를 이용하여 Action별로 Uncertainty를 계산합니다. Optimistic initial values 는 초기 Value 값을 임의의 큰 값으로 초기화 했다면, UCB는 기존의 Value 값에 Uncertainty를 더해서 Uncertainty가 큰 Action이 더 많이 실행될 수 있도록 합니다.

 

위 식에서 argmax 안의 두번째 식이 Uncertainty 가 됩니다. 여기서 $c$ 는 Exploration에 대한 계수입니다. $c$ 가 커질수록 Exploration을 많이 하게 됩니다. $N_t(a)$ 는 특정 Action이 실행된 횟수를 의미합니다. $t$ 는 현재까지 진행된 Step의 수입니다. 특정 Action이 과거에 많이 실행되었다면 그 Action에 대한 Variance는 낮아지고, 진행된 Step 수에 비해 실행된 수가 적다면 그 행동은 업데이트를 해주게 됩니다.

 

class Agent():
    '''
        중략    
    '''

    def init_values(self):
        # 실제 optimal q value 생성 
        self.pred_q_value_list = [self.initial_q_value for _ in range(self.n_action)]
        self.n_list = [0 for _ in range(self.n_action)]
        self.t = np.finfo(np.float32).eps
        self.c = 2

    def step(self, env, epsilon):
        
        # 1. UCB 알고리즘으로 Action 선택 및 reward를 받음
        action = self._get_UCB_action(self.t)
        reward = env.get_reward(action)

        # 2. n 값 증가 
        self.n_list[action] = self.n_list[action] + 1

        # 3. 선택된 Action의 Expected Reward 값 (q_value_list)을 업데이트. 
        self.pred_q_value_list[action] = self.pred_q_value_list[action] + (reward - self.pred_q_value_list[action]) / self.n_list[action]

        self.t = self.t + 1 
        return action, reward

    def _get_UCB_action(self, t):
        values = [q + self.c * np.sqrt(np.log(t) / n) for q, n in zip(self.pred_q_value_list, self.n_list)]
        action = np.argmax(values)
        return action
	
    '''
        중략    
    '''

 

위 코드는 UCB를 적용한 Agent 입니다. UCB 알고리즘은 Time step의 수와 Action이 실행된 횟수, Exploration 계수가 필요하므로 Init_values 메소드에서 정의해주고 _get_UCB_action 메소드에서 수행할 Action을 계산합니다. 

 

UCB 알고리즘의 학습 진행에 따른 평균 Reward 값

 

UCB 알고리즘의 학습 진행에 따른 최적의 Action을 수행할 확률

UCB 알고리즘과 $\epsilon$-greedy 를 비교한 결과를 위 그림에 나타냈습니다. UCB 알고리즘은 초반에 모든 Action에 대해 Exploration을 수행해서 Reward가 튀는 현상을 보이지만, 후반으로 갈수록 Exploitation에 비중을 두기 때문에 $\epsilon$-greedy method 보다 좋은 성능을 보여줍니다.

 

---

Reference

• Reinforcement Learning An Introduction 2nd Edition