이기면 그대로, 지면 바꾸기

Algorithms to live by the CS

  컴퓨터과학에서 탐색과 이용 사이의 긴장은 '다중 슬롯머신 문제'라는 시나리오에서 가장 명확하게 나타난다. 

  슬롯머신들이 꽉 들어찬 카지노로 들어간다고 상상하자. 슬롯머신마다 승률이 다르게 설정되어 있다. 물론 문제는 승률을 미리 알지 못한다는 데 있다. 게임을 시작하기 전에는 어느 기계가 가장 수지가 맞는지, 어느 기계가 돈을 계속 꼬라박게 만드는지를 전혀 알 수 없다.

  당연히 당신은 총 상금을 최대화하는 데 관심이 있다. 그러려면 각 슬롯머신의 팔을 잡아당겨서 승률이 얼마나 되는지 시험하는 일(탐색)과 가장 유망해 보이는 기계를 골라서 게임하는 일(이용)을 조합하는 과정이 필요할 것이 분명하다. 

(중략)

  사람들은 매번 최대 기댓값을 지닌 결과를 얻는 데에만 초점을 맞추면서, 각 결정을 독립적으로 다루는 경향이 있다. 하지만 결정들은 고립되어 내려지는 적이 거의 없으며, 기댓값은 이야기의 결말이 아니다. 다음 결정만이 아니라, 앞으로 동일한 대안들을 놓고 하게 될 모든 결정들을 생각한다면, 탐색/이용 트레이드오프가 그 과정의 핵심에 놓이게 된다.

  수학자 Peter Whittle은 바로 이런 점에서 "슬롯머신 문제가 모든 인간 행동에서 명백하게 드러나는 갈등의 본질적인 형태를 구현한다"고 썼다. 그렇다면 두 팔 중 어느 쪽을 잡아당겨야 할까?

(중략)

  수학자 Herbert Robbins가 완벽하지는 않지만 얼마간은 보장할 수 있는 단순한 전략을 내놓았다. 로빈스는 '이기면 그대로, 지면 바꾸기(Win-Stay, Lose-Shift)' 알고리즘이라는 해결책을 내놓았다. 직관적으로 생각할 때, '이기면 그대로'는 다양한 조건에서 탐색과 이용 사이의 균형을 잡는 최적 전략의 한 요소임이 드러난다. 하지만 '지면 바꾸기'는 다른 이야기다. 매번 질 때마다 팔을 바꾸는 것은 꽤 성급한 행동이다.

- Brian Christian, Tom Griffiths, '알고리즘, 인생을 계산하다' 중에서