멀티암드밴딧 - (1-4) 확률적 밴딧: 초기정보를 가진 밴딧

 

 

 

 

 

 

 

 

 

 

 

 

 

확률적 밴딧

 

1.4 초기 정보를 가진 밴딧

문제에 대한 정보가 알고리즘에게 먼저 알려질 수 있고, 이는 알고리즘의 성능을 개선하기 위해 사용될 수 있다. 이러한 "초기 정보"는 평균 보상 벡터 $\mu$에 큰 도움을 준다. 초기 정보를 부여하기 위한 두가지 일반적인 방법이 있다:

1. $\mu$에게 "얌전함"(well-behaved)을 강요하는 것, 그리고
2. 베이지안(Bayesian) 사전 확률을 부여하는 것이다. 중요한 후회 범위를 가지는 어떤 모델들은 슬롯의 숫자에 영향을 받지 않고, 따라서 무수히 많은 슬롯을 수용할 수 있다.

 

$\mu$에 얌전함을 강요하는 것

정석적인 모델은 다음과 같다. 슬롯은 $\mathbb{R}^d$ 내의 포인트들과 일치한다. 우리는 $\mu$를 각 슬롯을 알맞는 평균 보상에 연결하는 함수로 간주하고, $\mu$를 "얌전한" 함수의 모임 $F$에 속하는 것으로 간주한다. 일반적인 가정은 다음과 같다.

• 선형함수(linear functions): 값이 고정되어 있지만 알려지지 않은 벡터 $w \in \mathbb{R}^d$에 대해 $\mu(a) = w \cdot a$가 성립한다.
• 오목함수(concave functions): 슬롯의 집합은 볼록한 함수들의 집합 $\mathbb{R}^d$의 부분집합이고, $\mu''(\cdot)$이 존재하며 이는 음수이다.
• 립시츠 함수 (Lipschitz functions): 모든 슬롯 $a$와 $a'$ 그리고 정해진 상수 $L$에 대해 $|\mu(a) - \mu(a')| \le L \cdot ||a - a'||_2$가 성립한다.

 

위와 같은 가정은 슬롯들 간의 의존성을 소개하고, 이에 따라 하나의 슬롯의 평균 보상을 관찰함에 따라 다른 슬롯의 평균 보상에 대한 정보를 유추할 수 있게 한다. 특별히, 립시츠 함수의 속성은 "짧은-범위"(short-range)의 추론만을 가능하게 한다: 슬롯 $a$와 너무 멀리 떨어져 있지 않은 슬롯으로부터만 슬롯 $a$에 대한 정보를 얻을 수 있다. 선형성과 오목성은 "넓은-범위"(long-range)의 추론을 가능하게 한다: 슬롯 $a$와 아주 멀리 떨어져 있는 슬롯을 관찰함을 통해 슬롯 $a$에 대한 정보를 얻는다.

 

후회 범위는 주로 $\mu \in F$가 성립하는 것에 대해서 증명된다. 이러한 후회 범위는 주로 (오직) 차원 $d$에만 의존하고, 무수히 많은 슬롯들을 수용한다. 이들의 단점은 $F$의 최악의 상황에 대해서만 성립하고, 과하게 비관적이거나 (만약 좋지 않은 상황이 매우 드물게 발생한다면), 과하게 낙관적이게 (만약 실제로는 잘 동작하지 않는 만약 강한 가정을 한다면) 된다.

 

베이지안 밴딧

평균 보상 벡터 $\mu$는 베이지안 사전분포라고 불리는 임의의 분포 $\mathbb{P}$에서 독립적으로 추출된다. 여기서 관심이 있는 것은 "베이지안 후회값": 분포 $\mathbb{P}$에 대한 기대값의 후외값이다. 이는 베이지안 접근법의 특별한 상황인데, 이는 머신러닝과 통계에서 매우 보편적인 방법이다: 모델의 실제 값이 알고있는 분포로부터 샘플링 되고, 분포의 기대값으로 성능을 측정한다.

 

사전확률 $\mathbb{P}$는 실현 가능한 평균 보상 벡터들의 모임 $F$를 묵시적으로 정의하지만, 이는 또한 $F$에 속한 임의의 평균 보상 벡터가 다른 것들에 비해 어떻게 그리고 얼마나 더 확률이 높은지를 정의한다. 이 접근법의 주된 단점은 샘플링에 대한 가정이 현실에서는 매우 최적화 되어 있을 수 있지만, "실제"(true) 사전확률이 알고리즘에게 완벽하게 주어지지는 않을 수 있다.

 

---

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

arxiv.org/abs/1904.07272

Introduction to Multi-Armed Bandits