멀티암드밴딧 - (1-1) 확률적 밴딧: 모델과 예제

 

 

 

 

확률적 밴딧

이 챕터는 가장 기본적인 형태의 멀티암드밴딧인 IID(identically independently distributed, 독립적이고 동일하게 분포된)의 보상을 가진 밴딧에 대해 다룬다. 우리는 몇가지의 알고리즘을 소개하고, 해당 알고리즘들의 성능을 후회값(regret)으로 분석한다. 이 챕터에서 소개된 개념들은 기본적인 모델에 이어 이 책의 모든 부분에 적용된다.

 

1.1 모델과 예제

우리는 확률적 밴딧(stochastic bandits)이라 불리는, IID의 보상을 가진 기본적인 모델을 살펴본다. 이 알고리즘은 알고있는 숫자 $K$와 $T$에 대해 $T$개의 라운드 동안 $K$개의 가능한 행동(arm, 슬롯)이 선택 가능하도록 주어진다. 각 라운드에서 이 알고리즘은 어떤 슬롯에서 보상을 수집할 것인지를 선택한다. 따라서 이 프로토콜은 다음과 같이 정의될 수 있다:

 

문제 프로토콜: 멀티암드밴딧

주어진 값: $K$ 개의 슬롯, $T$ 개의 라운드
각 라운드 $t \in [T]$에 대해:
	1. 알고리즘은 슬롯 $a_t$를 선택한다.
	2. 알고리즘은 선택한 슬롯에 대한 보상 $r_t \in [0,1]$을 관측한다.

 

이 알고리즘의 목표는 $T$라운드 동안 관측할 수 있는 리워드의 합을 최대화 하는 것이다. 우리는 세가지의 필수적인 가정을 한다:

• 알고리즘은 오직 선택한 행동에 대한 보상만을 관측한다. 특별히, 알고리즘은 선택 했을 수 있는 다른 행동에 대한 보상은 관측할 수 없다. 이를 "밴딧 피드백" 이라고 한다.
• 각 행동에 대한 보상은 IID를 가정한다. 각 행동 $a$에 대해서는 "보상 분포"라고 하는 실제 보상의 분포 $D_a$가 존재한다. 알고리즘이 이 행동을 선택하는 각 시점에, 보상은 독립적으로 이 분포에서 샘플링 된다. 최초에 알고리즘은 이 보상 분포에 대해 알지 못한다.
• 각 라운드에서의 보상의 값은 제한되어 있다. 단순함을 위해 이 값은 $[0,1]$로 제한된다.

우리가 주로 관심 있는 것은 평균 보상 벡터 $\mu \in [0,1]^k$ 이다. 여기서 $\mu(a) = \mathbb{E}[D_a]$는 슬롯 $a$의 평균 보상이다. 가장 간단한 보상 분포는 각 슬롯 $a$의 보상이 1이나 0인 (성공 혹은 실패, 앞면 혹은 뒷면) 베르누이 분포일 것이다. 이 보상의 분포는 평균 보상으로 지정되고, 이 상황에서는 단순하게 성공적인 결과(1)이다. 문제는 시간수평선(time horizon) $T$와 평균 보상 벡트로 완벽하게 설명될 수 있다.

 

우리의 모델은 현실의 중요한 특성들을 담고있는 간단한 추상화이고, 이는 많은 애플리케이션 시나리오에 적용되어 있다. 다음 세가지의 인상적인 예제를 확인해보자:

1. 뉴스: 매우 형식화된 뉴스 애플리케이션에서, 한 사용자가 뉴스 사이트를 방문하고, 사이트는 뉴스 헤드라인을 제공하고, 사용자는 제공된 헤드라인을 클릭하거나 클릭하지 않는다. 웹사이트의 목적은 클릭의 횟수를 최대화 하는 것이다. 따라서 각 헤드라인은 밴딧 문제의 슬롯이 되고, 클릭은 보상이 된다. 각 사용자는 각 라운드에서 선정된 헤드라인에 의한 확률과 함께 클릭이 독립적으로 일어날 수 있도록, 정해진 사용자의 분포에서 독립적으로 추출된다.
2. 광고 선택: 웹사이트의 광고 시스템에서, 사용자가 웹페이지를 방문하고, 학습된 알고리즘은 많은 광고들 중에 게시할 하나의 광고를 선정한다. 만약 광고 $a$가 게시되었고, 웹사이트는 사용자가 이 광고를 클릭하는지 관찰하고, 광고주는 클릭에 따라 일정 금액 $v_a \in [0,1]$을 지불한다. 따라서 각 광고는 슬롯이고, 지불된 금액은 보상이다. $v_a$는 게시된 광고에만 의존하고, 시간에 따라 변동되지 않는다. 또한 주어진 광고를 클릭할 확률또한 시간에 따라 변하지 않는다.
3. 의학적 실험: 환자가 의사를 방문하고 의사는 몇가지 가능한 치료제를 처방하고, 치료제의 효과를 관찰한다. 다음 환자가 방문하고, 동일한 계속해서 이뤄진다. 이 문제를 단순화하기 위해, 치료제의 효과는 $[0,1]$ 사이의 숫자로 정량화 될 수 있다. 각 치료제는 하나의 슬롯으로 간주될 수 있고, 보상은 치료제의 효과로 정의된다. 이상적인 가정으로는, 각 환자는 환자의 분포로부터 독립적으로 추출되고, 이에 따라 주어진 치료제의 효과 또한 IID를 따른다.

첫 두가지의 예제에서, 주어진 슬롯의 보상은 두가지의 값(0 혹은 1)만을 취할 수 있지만, 세번째 예제에서는 이론적으로 어떠한 값이든 취할 수 있다.

 

표기법

우리는 이 챕터와 책 전체에서 다음과 같은 표기법을 따른다. 우리는 "슬롯"과 "행동"을 같은 의미로 사용한다. 각 슬롯은 $a$로, 각 라운드는 $t$로 표기한다. 총 $K$개의 슬롯과 $T$개의 라운드가 존재한다. 가능한 모든 슬롯의 집합은 $A$로 표기한다. 슬롯 $a$로부터 얻을 수 있는 평균 보상은 $\mu(a) := \mathbb{E}[D_a]$로 정의한다. 최적의 평균 보상은 $\mu^* := max_a \in A \mu (a)$로 정의한다. 차이값 $\nabla (a) := \mu^* - \mu(a)$은 슬롯 $a$가 $\mu^*$와 비교해 얼마나 나쁜지를 표현하고, 이를 갭(gap)이라고 정의한다. 최적의 슬롯 $a$는 $\mu(a) = \mu^*$를 만족하는 슬롯이고, 이는 유일하지 않을 수 있다. 우리는 최적의 슬롯을 $a^*$로 표기한다. $[n]$은 집합 ${1, 2, ..., n}$을 의미한다.

 

후회값

한 알고리즘이 여러 다른 문제에 대해 잘 하고 있다는 것을 어떻게 평가할까? 여기서 문제점은, 특정 문제들은 다른 문제들보다 높은 보상을 허락한다는 것이다. 정석적인 접근법은 알고리즘의 누적 보상을 "가장 완벽한 슬롯 벤치마크" $\mu^* \cdot T$와 비교하는 것이다. "가장 완벽한 슬롯 벤치마크"는 항상 최적의 슬롯을 선택한다 (또한 어떠한 문제에 대해 예정된 보상을 최대로 얻어낼 수 있다). 이를 우리는 다음과 같이 정의한다:

 

$R(T) = \mu^* \cdot T - \sum_{t=1}^{T} \mu(a_t)$,     (1.1)

 

이 수치는 라운드 $T$에서의 "후횟값"이다. 라운드 $t$에서 선정된 슬롯 $a_t$는 랜덤한 값이고, 이는 보상이나 알고리즘의 랜덤성에 의존한다. 따라서 $R(T)$는 확률변수이기도 하다. 우리는 통상적으로 기대되는 후회값(혹은 후횟값의 기댓값) $\mathbb{E}[R(T)]$에 대해서 이야기 한다.

 

우리의 주된 관심사는 시간수평선 $T$ 위에서 후회값 $\mathbb{E}[R(T)]$의 의존성이다. 또한 우리는 슬롯 의 숫자 $K$와 평균 보상 $\mu(\cdot)$에 대해서도 고려해야 한다. 우리는 자세한 (평균 보상을 넘어서는) 보상 분포에 대해서는 관심이 적다. 우리는 상수들을 일일이 추적하기 보다, 빅O 표기법을 통한 점근 표기법에 집중할 것이다.

 

Remark 1.1

후회값에 대한 우리의 정의는 모든 라운드에 대해서 더해진 값이기 때문에, 우리는 이를 종종 누적된 후회값이라고 부른다. 우리가 $R(T)$와 $\mathbb{E}[R(T)]$를 분리해서 강조할 때는 이를 각각 "실현된 후회값"과 "기대되는 후회값"이라 정의한다. 하지만 이 의미는 대부분의 경우 맥락상 명확하기 때문에 단순히 "후회값"으로 정의한다. 학문적으로 $R(T)$의 양는 종종 슈도-후회값(pseudo-regret)으로 불리운다.

---

이 글은 아래 링크의 책을 번역한 글 입니다.

arxiv.org/abs/1904.07272

Introduction to Multi-Armed Bandits