[베이지안 with Python] 베이지안 Multi-Armed Bandit(MAB)

Multi-Armed Bandits (MAB)

$\ $MAB 문제를 정의하고, 이 문제를 베이지안 관점에서 해결해보자.

우리가 $N$ 개의 슬롯머신을 마주하고있다고 가정하자. 각각의 슬롯머신이 보상을 줄 확률은 각기 다르며, 우리는 이 값을 현재 알지 못한다. 한 번에 한개의 슬롯머신을 택하면서, 우리는 어떻게 해야 우리의 보상을 최대화할 지에 대해 고민해야한다.

예를 들어, 4개의 슬롯머신이 있고, 각각의 머신이 보상을 줄 확률은 (0.1, 0.3, 0.65, 0.8) 이라고 해보자. 네번째에 해당하는 슬롯머신이 가장 높은 확률로 보상을 준다는 것을 알게되면 우리는 당연히! 네번째 머신만 계속해서 작동시킬 것이다. 결국 이 문제는 최대 확률을 갖는 슬롯머신을 최대한 빠르게 찾는 것이다.

어떻게 접근할까?

$\ $해당 문제는 online algorithm 의 관점에서 바라보아야 하며, 조금 더 구체적으로는 강화학습 알고리즘의 일종이다. 일종이라고 하기 좀 애매한 것이, 사실 MAB가 강화학습의 시조 격이다. offline algorithm 과는 다르게, 온라인 알고리즘은 계속해서 입력을 차례로 입력받으며, 학습을 계속 진행한다.

online algorithm : 시작할 때 모든 입력 정보를 갖고 처리하는 것이 아니라, 입력이 차례대로 들어오는 상황에서 처리하는 알고리즘을 말한다. 반대로, offline 알고리즘은 우리가 알고리즘을 처리할 때 모든 데이터를 다 갖고 있어야만 한다.

베이지안 접근에서는 각각의 Bandits(슬롯머신)에서 보상을 줄 확률들에 대한 사전확률분포를 제안한다. 하지만, 처음에 우리는 각 슬롯머신의 보상 확률에 대한 어떤 것도 알지 못하므로, uniform 사전확률분포로 시작하는 것이 일반적이다. 알고리즘 과정은 다음과 같다. :

모든 Bandits $b$의 사전확률분포로부터, 랜덤 변수 $X_b$를 추출한다.
추출된 값들 중 가장 큰 변수 값을 나타내는 Bandit을 선택한다, i.e. $B = argmax X_b$
Bandit $B$를 당겼을 때, 보상을 주는지 안주는 지에 대한 결과를 관측하고 이를 이용해, Bandit B에 대한 사전확률분포를 업데이트한다.
1번으로 돌아간다.

$\ $ 아주 간단한 알고리즘이다. 처음 사전분포는 $Beta(\alpha = 1, \beta = 1)$ (uniform distribution)이고, 관측한 $X$라는 결과는 Binomial 형태이기 때문에, 사후분포는 다음과 같다. $Beta(\alpha = 1 + X, \beta = 1 + 1 - X)$.
유의해야 할 점은, 우리가 3번 단계에서 밴딧을 당기고 보상을 받지 못했을 때, 해당 시행에 대하여 discard(무시)해선 안된다는 것이다. 밴딧을 당겼는데, 해당 머신에서 보상이 나오지 않았다는 정보 또한 업데이트를 해주면, 다른 밴딧이 더 나을 것이라는 의미를 반영시킬 수 있다.
$\ $아래는 Bandit 이라는 슬롯머신을 정의하는 클래스와, BayesianStrategy 라는 이 베이지안 학습 전략을 구현하는 클래스에 대한 코드이다.

rand = np.random.rand

class Bandits(object):
    """
    This class represents N bandits machines.

    parameters:
        p_array: a (n,) Numpy array of probabilities >0, <1.

    methods:
        pull( i ): return the results, 0 or 1, of pulling
                   the ith bandit.
    """
    def __init__(self, p_array):
        self.p = p_array
        self.optimal = np.argmax(p_array)

    def pull(self, i):
        #i is which arm to pull
        return np.random.rand() < self.p[i]

    def __len__(self):
        return len(self.p)


class BayesianStrategy(object):
    """
    Implements a online, learning strategy to solve
    the Multi-Armed Bandit problem.

    parameters:
        bandits: a Bandit class with .pull method

    methods:
        sample_bandits(n): sample and train on n pulls.

    attributes:
        N: the cumulative number of samples
        choices: the historical choices as a (N,) array
        bb_score: the historical score as a (N,) array
    """

    def __init__(self, bandits):

        self.bandits = bandits
        n_bandits = len(self.bandits)
        self.wins = np.zeros(n_bandits)
        self.trials = np.zeros(n_bandits)
        self.N = 0
        self.choices = []
        self.bb_score = []


    def sample_bandits(self, n=1):

        bb_score = np.zeros(n)
        choices = np.zeros(n)

        for k in range(n):
            #sample from the bandits's priors, and select the largest sample
            choice = np.argmax(np.random.beta(1 + self.wins, 1 + self.trials - self.wins))

            #sample the chosen bandit
            result = self.bandits.pull(choice)

            #update priors and score
            self.wins[choice] += result
            self.trials[choice] += 1
            bb_score[k] = result
            self.N += 1
            choices[k] = choice

        self.bb_score = np.r_[self.bb_score, bb_score]
        self.choices = np.r_[self.choices, choices]
        return

위의 밴딧 클래스들을 활용한 학습과정의 시각화는 다음과 같다.

위의 gif파일에서도 보이듯이, Pull을 진행함에 따라, 세번째 밴딧이 0.8 초과로 높은 보상을 주는 확률에 대해 점점 확실성이 높아지게 된다.

해당 결과는 얼마나 좋은 것일까? (A measure of Good)

$\ $가장 보상을 잘 주는 밴딧을 택해서 항상 해당 밴딧만 택하는 것이 절대적으로 좋은 방법일 것이다. 이 best 밴딧의 확률을 $w_{opt}$로 표현하자. total regret of a strategy 를 다음과 같이 정의하자.

$$ R_T = \sum_{i=1}^{T} (w_{opt} - w_{B(i)})$$ $$ = Tw^* - \sum_{i=1}^{T} w_{B(i)}$$

위의 식에서, $w_{B(i)}$는 $i$번째 라운드에서, 선택된 밴딧의 보상이다.

BayesianStrategy 외에 MAB 문제 접근에 대한 다른 접근들은 아래와 같다.

Random choose bandits
Largest Bayesian credible bound
Bayes-UCB algorithm
Mean of posterior
Largest proportion $\ $다양한 접근들에 따른 총 손실들을 아래 그래프에서 확인해보자. 아래 그래프에서 확인할 수 있듯이, 베이지안 밴디트 전략과 다른 전략들은 손실률이 줄어들고 있다.

pull이 늘어나고 있음에도, 손실이 크게 늘고있지 않다. 즉, 손실률(손실/Pull)은 줄어들고 있다.

기대 손실(expected total regret)은 가능한 모든 경우에 대한 총 손실의 기댓값이며 다음과 같다.

$$\bar{R}_T = E[R_T]$$

또한, 해당 기대손실은 T에 대한 로그함수 형태로 복잡도가 늘어난다.

$$E[R^T] = \Omega (log(T))$$

$\Omega (f(n))$ : running time is at least $k\dot f(n)$ for some constant $k$

PREVIOUS [베이지안 with Python] Prior Selection

NEXT [선형대수학] positive definite, semi-positive definite