후회를 최소화하는 알고리즘

Algorithms to live by the CS

"나는 이 일을 시도하면 80세가 되었을 때 후회하지 않으리라는 것을 알았죠. 내가 진정으로 엄청난 무언가가 될 거라고 생각했기 때문입니다. '인터넷'이라는 이 아이템에 참여하려 했던 시도를 후회하지 않을 것이라고요. 심지어 실패해도 후회하지 않으리라는 것을 알았어요. 시도하지 않으면 후회할지도 모른다는 것도 알았고요. 그랬다가는 매일 후회하며 살아가리라는 것을요. 그런 식으로 생각하니, 결정을 내리기가 놀라울만치 쉬웠어요." - 제프 베조스

컴퓨터과학이 후회가 전혀 없는 삶을 제공할 수는 없지만, 제프 베조스가 추구했던 것만큼은 제공할 수 있다. 후회를 최소화하는 삶이다.

  후회는 우리가 실제로 한 일을 돌이켜볼 때, 가장 좋았을 법한 행동과 비교한 결과다. 다중 슬롯머신 문제에서, 버나드의 '헤아릴 수 없는 상실감'은 정확히 측정할 수 있으며, 후회에 어떤 값을 할당할 수도 있다.

  1985년 허버트 로빈스는 다중 슬롯머신 문제를 이렇게 공략하여, 후회에 관한 몇 가지 요점을 증명할 수 있었다.

  첫째. 당신이 전지전능하지 않다고 가정하면, 당신의 후회 총량은 아마 결코 증가를 멈추지 않을 것이다. 설령 가능한 최고의 전략을 고른다고 해도 마찬가지다. 최고의 전략도 매번 완벽하지는 않기 때문이다.

  둘째, 최고의 전략을 고른다면 다른 전략을 고를 때보다 후회가 더 느린 속도로 증가할 것이다. 게다가 좋은 전략을 쓰면, 후회의 증가율이 시간이 흐를수록 낮아질 것이다. 그 문제를 더 잘 알게 됨으로써 더 나은 선택을 할 수 있기 때문이다.

  셋째, 가장 구체적인 사항이기도 한데, 가능한 최소 후회는 로그적으로 증가하는 후회다. 로그적으로 증가하는 후회란, 처음 10번 당길 때의 실수 횟수가 다음 90번 당길 때의 실수 횟수와 같고, 첫 1년 때의 실수 횟수가 나머지 9년에 걸친 실수 횟수를 합친 것과 같으리라는 의미다.

  후회 최소화 알고리즘을 따른다면, 해마다 이전 해보다 새로운 후회를 더 적게 할 것이라 예상할 수 있다.