Reinforcement Learning 문제 (사실은 MDP) 를 풀기 위한 유명한 방법 중 하나인 Value Iteration 은 사실 수렴할 때까지 돌리는 동적 계획법과 별로 다를 게 없다. Sutton 책의 4장에 보면 연습 문제로 Gambler's Problem 이 나온다. 이거이 뭐냐면
동전을 던져서 앞면이 나온다에 돈을 걸려고 한다. 우리의 최종 목표는 100원이고, 정수 단위로만 돈을 걸 수 있다. 0원 이 되면 패배한다. 중간에 그만두는 것은 없다고 하고, 현재 x원 있다고 할 때, 얼마를 걸어야 할까?
이건데... 맨 밑에 있는 그림을 보면 몹시 특이한 전략이 그림으로 나온다. 연습 문제에도 이것을 강조하고 있는데:
Exercise 4.8 Why does the optimal policy for the gambler's problem have such a curious form? In particular, for capital of 50 it bets it all on one flip, but for capital of 51 it does not. Why is this a good policy? 너무 신기해서 구현해 봤다.
lang:py
from pylab import *
MAX_AMOUNT = 100
WIN_PROB = 0.45
LOSE_PROB = 1.0 - WIN_PROB
DECAY = 0.9
hold(True)
clf()
V = [0] * MAX_AMOUNT + [1 / DECAY]
subplot(1, 2, 1)
while True:
old = list(V)
for amt in xrange(1,MAX_AMOUNT):
V[amt] = DECAY * max(V[amt + bet] * WIN_PROB + V[amt - bet] * LOSE_PROB for bet in xrange(0, min(amt, MAX_AMOUNT - amt) + 1))
plot(V[1:MAX_AMOUNT])
if max(abs(old[i] - V[i]) for i in xrange(MAX_AMOUNT)) < 0.00001: break
x = xrange(1, MAX_AMOUNT)
subplot(1, 2, 2)
bar(x, [max((V[amt + bet] * WIN_PROB + V[amt - bet] * LOSE_PROB, bet) for bet in xrange(0, min(amt, MAX_AMOUNT - amt) + 1))[1] for amt in x])
show()
그런데 결과는
이렇게 나오는 것이었다.. 아니 왼쪽 그림은 교재랑 똑같은데 오른쪽은 뭐냐고요.. 내가 이것도 잘못 짠단 말인가. 하면서 절망해서 30분 넘게 디버그하다가 (그러다 수열이는 잠들고) 하도 이상해서 구글해 보니 이런 얘기 가 있었다. 으윽.... 낚였다......
근데 저자는 어떻게 해서 이런 특이한 결과를 얻었을꼬...;;;
