Introduction to Multi-Armed Bandits (1)

오늘 포스팅을 시작으로 Multi-Armed Bandits (MAB)에 대하여 차근차근 정리하고자 합니다. 며칠전 예고(?)와 같이 제가 느끼기엔 MAB에 대하여 스토리가 있게 체계적으로 풀어가는 글들을 찾기가 어려웠고, 작게나마 MAB를 recommendation에 적용하길 고민하고 계시는 분들과 연구를 목적으로 기본적인 틀을 잡을 수 있는데 도움이 되길 바랍니다 :)

Multi-Armed Bandit?

먼저 MAB란 무엇일까요? 단어를 두덩이로 쪼개서 보면, "multi-armed" + "bandit"으로 살펴볼 수 있습니다. 직역하면 "팔이 많은 강도"라는 뜻입니다. 어떤 팔이 많은 강도가 슬롯머신 $K$개 위에 팔을 모두 올려놨습니다. 그런데 이 강도는 팔이 많지만, 한 번에 딱 하나의 팔을 선택하여, 슬롯을 당길 수 있습니다. 강도는 주어진 round, $T$번 반복할 때, 최대의 보상을 얻고자하는 문제를 일컫습니다.

Fig. 1: Multi-armed bandits 개요

일반화하면, 순차적 의사결정 상황에서 매 round, 선택지 (arm) 중 하나를 선택하고, 최종적인 보상을 최대화하는 문제를 MAB problems이라고 합니다. 그래서 MAB Problem을 푼다는 것은 각 시도별로 가장 좋은 arm을 선택하는 전략을 찾는 것과 같습니다.

그러면 여기서 한 가지 의문이 듭니다. "제일 처음 시작할 땐 아무런 정보가 없는데, 어떤 기준으로 팔을 선택해야 될까?", "만약 어떻게든 하나를 골랐는데, 그게 최적의 선택이 아니면 어떡하지?"

Exploration-Exploitation Trade-off

앞서 언급한 것 처럼 처음 시작할 땐 아무런 정보가 없습니다. 때문에 여러 arms 중 하나를 임의로 선택하고, 보상을 관측하면서 정보를 수집해야됩니다. 이 과정을 탐험 혹은 탐색 (Exploration)이라고 합니다. 어느 정도 정보가 수집되면 보상을 가장 크게 주는 arm만 선택하면 됩니다. 이 과정은 활용 (Exploitation)이라고 합니다. 요약하겠습니다.

• Exploration: 정보 수집을 위해 무작위로 arm을 선택하는 것
• Exploitation: 충분한 정보 수집 후, 최적의 arm을 선택하는 것

여기서 합리적인 의심을 할 수 있습니다. Exploration을 너무 오래 동안하면, 보상이 작은 arm을 선택하는 round가 많아져 총 보상이 작아지게 될 것이고, Exploitation만 하면, 최적의 arm 대신 우연히 보상이 좋았던 arm을 선택하여 총 보상에 대한 기회 손실이 발생할 것 입니다. 이를 조금 고상한 말로 Exploration-Exploiation Trade-off라고 부릅니다.

Fig. 2: Exploration-Exploitation Trade-off

Examples of MAB

MAB는 다음과 같은 상황을 해결할 때 적용할 수 있습니다.

• News: 인터넷 뉴스를 유저에게 노출할 때, 어떤 뉴스를 노출해야 click이 증가할까?
• Ad selection: 유저가 webpage에 들어 왔을때 어떤 광고를 노출해야 click이 증가할까?

MAB는 위 예시 말고도 다양한 문제를 해결하기 위해 간단하게 적용해 볼 수 있습니다.

그런데 MAB는 기본적으로 1 round에 1 arm을 선택할 수 있습니다. 물론 combinatorial bandit이 있지만, 역시 선택할 arm이 많아지면 경우의 수가 많아져 학습이 어렵습니다. 그래서 한 번에 여러 선택을 할 수 있는 algorithm을 여러개 개발하고, 각 algorithm을 arm으로 간주하여 MAB를 적용할 수 있습니다. 일반적으로 이런 algorithm을 비교하고 더 나은 algorithm을 취하기 위하여 AB Test를 합니다. 다시말하면 AB Test 대신 MAB를 적용하자는 것과 같습니다.

AB Test vs. MAB

AB Test는 어떤 모집단을 1:1혹은 1:1:$\cdots$:1로 쪼개여 임의로 새로운 방법을 적용하고 그에 대한 결과를 통계적 분석을 적용하여 우열을 가리는 방법입니다. 아직 MAB를 푸는 방법을 짧게 요약하면, Exp.-Exp. Trade-off에서 힌트를 얻으면, 적응적으로 좋은 arm을 찾아가는 것입니다. 이를 비교해보면 다음과 같습니다. (Fig. 3)

Fig. 3: AB Test vs. MAB

Summary

다음 포스팅에서는 MAB 개요 중 Formulation 및 MAB Branches를 다루겠습니다.

이번 포스팅을 요약하겠습니다. MAB는 무정보상태로 시작하는 순차적 의사결정 문제에서 가장 좋은 arm을 찾는 방법론이고, 최적의 arm을 찾는 과정에서 Exploration-Exploitation Trade-off가 발생합니다. 이를 해쳐나가는 관점이 MAB를 푸는 것과 같다고 할 수 있습니다. 또한 MAB는 다양한 분야에서 활용 가능한 방법이고, 조금더 구체적인 예제로 AB Test를 MAB로 대체하는 것까지 살펴봤습니다.

읽어 주셔서 감사합니다. 이번 포스팅은 여기서 마치겠습니다. :)

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.