Feynman's restaurant problem

Left-Leighton, Right-Feynman

Multi armed bandit 위키피디아 글을 보던 중 external link에서 'feynman'을 발견했다.

굉장히 좋아하는 사람이라 반가웠지만 추천시스템글에 왜 물리학자가 링크되지? 라고 생각했다.

어쨌거나 링크를 클릭해 들어가봤다. 

Feynman's restaurant problem이라는 제목의 글이었다.

내용은 다음과 같다.

 1970년 어느날 리처드 파인만과 랠프 레이턴이 자주 가던 식당에서 메뉴를 고르고 있었다. 메뉴를 고르던 중 둘은 가장 맛있었던 메뉴를 시키는 것과 새로운 메뉴를 시도해 보는 것 중 어떤 것이 더 나은지에 대한 이야기가 나누었고 이 문제를 수학적으로 분석했다.

 파인만이 타계한 이후 2002년 마이클 고트립(Michael Gottlieb)이라는 물리학자는 랠프 레이턴에게 이 일화를 전해듣게 된다. 하지만 오랜 시간이 지난 탓인지 랠프 레이턴은 상세한 솔루션들을 기억해내지 못했다. 

 하지만 이 문제에 관심을 가졌던 마이클 고트립은 그로부터 2년이 지난 2004년, 이 문제를 다음과 같이 수학적으로 정의해 "Feynman's Restaurant Problem" 이라는 이름을 붙이고 솔루션을 제시한다.

Problem.

 당신이 식사를 하러 레스토랑에 갔다. 레스토랑에는 N개의 메뉴가 있다. 각 메뉴는 당신의 취향에 따라서 별점이 매겨져 있다. 하지만 지금 당신은 그 점수를 모르는 상태이다. 

당신은 먹어보지 않은 메뉴를 먹어볼 때마다 그 메뉴가 지금까지 먹었던 것들 중 가장 맛있는 메뉴인지(가장 별점이 높은지) 아닌지에 대해서만 알 수 있다. 그리고 당신은 가장 맛있었던 메뉴와 먹어보지 않은 메뉴에 중에서만 주문을 할 수 있다.

앞으로 당신은 그 식당에 M번 방문할 것이다.(M≤N) 당신의 목표는 M번 식사의 평균별점을 최대한 높이는 것이다.

M번의 식사에서 새로운 메뉴를 n번, 가장 맛있었던 메뉴를 b번 먹는다고 한다면 n개의 새로운 메뉴를 처음에 차례대로 먹어본 후 베스트 메뉴를  b번 먹는 것의 평균별점이 그렇게 하지 않는 경우보다 항상 높을 것이다.

위와 같은 방법을 따를 때 M과 N에 대한 평균별점을 최대로 높이기 위해서는 새로운 메뉴를 몇번 먹어봐야 할까?