데이터사이언스/강화학습

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

_금융덕후_ 2021. 3. 18. 18:30
728x90
반응형

 

 

 

 

 

 

 

 

 

 

 

 

 

확률적 밴딧

 

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

Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory,

arxiv.org

 

728x90
반응형