Stochastic Bandits (1) - Introduction

Introduction to Multi-armed Bandit (1), (2)에서 MAB가 무엇이고, 목적은 어떤 것인지에 대해 살펴보았습니다. 본격적으로 MAB를 푸는 Algorithm을 소개하려고합니다. Algorithm의 첫 주제로는 Stochastic Bandits이란 이름으로 Multi-Armed Bandits의 중간 session을 열었습니다. 시작하겠습니다.

이번 포스팅에서는 Stochastic Bandits이란 무엇이고, Stochastic Bandits이라는 큰 틀 안에서 최적의 arm을 찾기 위해 approach에 대한 scketch를 한 후, 이어질 포스팅에서 UCB, Thompson Sampling, linUCB 등 저명한 알고리즘을 다루겠습니다.

Formulation

MAB는 arms, contexts, round, reward의 sequential한 흐름으로 나타낼 수 있습니다.

• $a_{t}\in{1,\cdots,K}$: $t$-round에서 선택가능한 arm
• $x_{t}$: $t$-round에서 관측가능한 context
• $t\in{1,\cdots,T}$: round
• $r_{t}\in\mathbb{R}$: $t$-round의 reward

위 notation기반 MAB의 sequential한 흐름을 나타내면 $$x_{1}\rightarrow a_{1}\rightarrow r_{1} \rightarrow x_{2}\rightarrow a_{2}\rightarrow r_{2} \rightarrow \cdots \rightarrow x_{T} \rightarrow a_{T} \rightarrow r_{T}$$로 요약할 수 있습니다. 말로 풀어쓰면 $t$-round에 관측가능한 정보인 context $x_{t}$기반 $a_{t}$라는 arm을 선택해서 $r_{t}$의 reward를 얻는 과정입니다.

Stochastic Bandits (SB)?

직전 포스팅의 후반부에서 말했듯 MAB의 알고리즘을 전개할 때 가장 중요한 것은 매라운드의 reward를 어떻게 해석하느냐 입니다. Stochastic Bandits은 reward가 stochastic함을 의미합니다. 다시말해 reward가 어떤 확률 분포에서 튀어나온 random variable이란 가정 기반 algorithm을 일컫습니다. 게다가 모든 $t\in{1,\cdots,T}$에 대하여 independent and identically distributed (i.i.d) random variable을 가정합니다. 정리하면 $\forall t, r_{t}\overset{iid}{\sim}\mathbb{P}(\cdot)$을 의미합니다. 여기에서 $\mathbb{P}$는 어떤 확률분포를 가정할 수 있고, stochastic bandit에서 주로 bernoulli distribution 혹은 normal distribution을 가정합니다.

Context-free SB vs. Contextual SB

Stochatic Bandits인데, 매라운드 관측가능한 정보인 context의 유무에 따라서 context-free, contextual로 구분 할 수 있습니다. Context-free는 사실 앞에 stochastic bandits을 정의하면서 다루었습니다. Contextual하다는 것은 결국 reward가 i.i.d인데 conditional i.i.d라는 것과 같습니다. 즉 $\forall t, r_{t}\overset{iid}{\sim}\mathbb{P}(\cdot|x_{t})$인 경우와 같습니다.

Reward Distribution Estimation

+ on the view of "frequentist" or "Bayesian"

Stochastic Bandits(SB)은 reward가 어떤 확률분포에서 iid하게 주어진 값으로 해석하기 때문에 SB의 알고리즘은 어떻게 그 확률분포를 참값에 가깝게 추정해나가냐의 문제입니다. 확률분포는 전통 두가지 관점인 빈도론자(Frequentist) 관점 또는 베이지안(Bayesian) 관점에서 추정가능합니다. 일반적으로 Stochatic Bandit이라고하면 Frequentist 관점의 알고리즘을 의미하고, Bayesian 관점이 알고리즘은 Bayesian Bandit으로 부르는 경향이 있습니다.

Summary

이번 포스팅에서는 Stochastic Bandits의 framework을 잡는게 주목적이었습니다. 요약하면 stochatic bandits은 reward가 어떤 확률분포에서 얻어진 random variable이라는 가정에서 출발하고, 매라운드에 관측가능한 context의 유무에 따라 context-free, contextual stochastic bandits으로 구분했습니다.

앞으로 이어진 포스팅에서는 context-free에 대하여 stochastic bandits을 frequentist의 관점, Bayesian의 관점에서 해결하는 방법을 논의하고, 그 다음 contextual bandit에서도 같은 순서로 살펴보며 stochastic bandits을 정리할 예정입니다.

긴 글 읽어 주셔서 감사합니다:)

yjjo.tistory@gmail.com

References

Slivkins, Aleksandrs. "Introduction to multi-armed bandits."arXiv preprint arXiv:1904.07272(2019).

Wikipedia contributors. "Multi-armed bandit." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 22 Oct. 2020. Web. 30 Nov. 2020.

Li, Lihong, et al. "A contextual-bandit approach to personalized news article recommendation." Proceedings of the 19th international conference on World wide web. 2010.

Agrawal, Shipra, and Navin Goyal. "Thompson sampling for contextual bandits with linear payoffs." International Conference on Machine Learning. 2013.