The multi-Armed Bandit Problem이란? #2
Multi-armed를 이해하기 위해 one-armed를 알아봅시다. 가장 흔하게 예로 들어지는 one-armed는 슬롯머신입니다. 카지노에서 볼 수 있는 슬롯머신에는우측에 당길 수 있는 긴 레버가 하나 달려 있습니다. (기계식 슬롯머신은 영화나 박물관에서 볼 수 있고 요즈음은 전자식으로 버튼을 누르는 슬롯머신을 쓰고있기는 합니다.) 그 레버를 잡아 당겼다 놓으면 게임이 시작됩니다.
실제로 카지노에서 빠른 시간 안에 많은 돈을 슬롯머신에서 잃을 수 있습니다. 만약에 그 슬롯머신에서 돈을 딸 수 있는 기회가 50:50라고 한다면 실제로 돈을 잃을 기회도 50: 50일 것입니다. 하지만 카지노에서 슬롯머신에 bug를 넣고 사람들은 실제로 50%보다 더 빠른 속도로 돈을 잃게 되며 이 기계가 돈을 강탈해 가기 때문에 이 긴 레버를 bandit(도둑, 강도)라고 부르는 이유가 됩니다.
그러면 multi-armed bandit은 무엇일까요? Multi – armed bandit problem이라는 것은 예를 들면 한 사람이 5대의 슬롯머신 세트를 play해야 하는 상황을들 수 있습니다. 이 5대의 슬롯머신에서 최소한으로 돈을 잃고 최대한으로 돈을따야 합니다. 5대의 슬롯머신을 100번, 1000번 반복되는 게임을 하다 보면 어떤 기계에서 돈을 더 따게 되고 어떤 기계에서 돈을 더 잃을 지 경험적으로 알 수 있습니다. 하지만 가지고 있는 돈은 한정이 되어 있으니 한없이 게임을 반복할 수 는 없습니다.
5대의 슬롯머신을 M1, M2, M3, M4, M5라고 하고 각 각의 기계는 default 값이 달라 돈을 잃고 따는 확률이 다르다고 가정해 봅시다. 하지만 게임을 하는 사람은 사전에 어떤 기계에서 돈을 더 많이 딸 수 있는지는 알 수 없습니다. 따라서 게임을 하는 사람은 빠른 시간 안에 가장 돈을 많이 딸 수 있는 기계를 알아내야 합니다. M1부터 M5까지 슬롯머신마다 각각의 distribution 값을 보게 되면 어떤 기계가 가장 돈을 많이 딸 수 있는 기계인지 알 수 있습니다. 이 사실만 알게 된다면 게임을 하는 사람은 그 기계에만 계속 배팅을 하고 가장 이득이되는 결과를 갖게 될 것입니다.
하지만 어떤 기계가 좋은 결과를 보여주는지 찾는 동안에도 계속해서 돈을 써야 하고 잃어야 합니다. 어떤 기계에서 돈을 딸 수 있는 지 아는 데까지 시간이 많이 걸린다면 확률이 낮은 기계에 돈을 계속 쓰게 되고 그 사이에 가진 돈을 모두 잃게 될 지 모릅니다.
따라서 이렇게 슬롯머신 게임을 하면서 두 가지의 개념이 필요하게 됩니다.
Exploration(탐험하기)과 exploitation(뽑아먹기)
1) 어떤 기계에서 가장 돈을 많이 딸 수 있는지 빠른 시간 안에 알아야 한다(exploration)
2) 동시에 현재 알고 있는 가장 돈을 많이 딸 수 있는 기계에서 최대한 빨리 돈을 계속 따야 한다(exploitation)
또한 여기서 regret이라는 수학적 개념이 나오게 됩니다.
한쪽은 optimal machine에 돈을 계속 넣어서 돈을 따게 되었지만 다른 한쪽은non-optimal machine에 돈을 계속 넣어서 많은 돈을 잃게 되었다면 best outcome과 non-best outcome 사이의 차이가 regret개념이 됩니다.
Optimal machine을 찾기 위해 다른 기계들을 exploration하는데 쓰이는 비용을 opportunity cost라고 하며 다른 non-optimal machine들을 explore하는 시간이 길면 길수록 높은 reget값을 가질 수 있습니다. 빠른 시간 안에 explore하면서 sub-optimal machine을 찾고(exploration) 그 그 기계에서 계속 돈을 따면서( exploitation) 최소한의 시간 안에 optimal machine을 찾아 내야 합니다.
(짧은 시간 안에 찾은 sub-optimal distribution이 정말 optimal distribution인지 검증이 필요합니다. 섣부른 판단으로 sub-optimal을 optimal이라고 판단할 수도 있습니다)
정리를 한다면, The multi-Armed Bandit model의 목적은 best one을 찾고(exploration) 이 best one에서 돈을 따고(exploitation) best one을 찾는 시간을 최소화 하는 것입니다.