Este problema foi retirado do livro Reinforcement Learning de Sutton
and Barto. É o exemplo 4.3 da seção sobre iterações da função valor.
Um jogador tem a oportunidade de fazer apostas nos resultados de uma seqüência de lançamentos de moeda. Se a moeda surgir, então ele ganha tantos dólares como ele apostou naquele flip, mas se for coroa, ele perde sua aposta. O jogo termina quando o o jogador ganha ao atingir sua meta de 100 dólares, ou perde ficando sem dinheiro. Em cada Por outro lado, o apostador deve decidir que parte de seu capital apostará, em números inteiros de dólares. Este problema pode ser formulado como um MDP finito.
O estado é o capital do jogador, que ele usará para as suas apostas e pode ser descrito como: \(s\epsilon\{1,2,3,...,99\}\) e as ações são as apostas (stakes), \(a\epsilon\{0,1,...,min(s,100-s\}\).
A recompensa é zero em todas as transições, exceto aquelas em
que o jogador atinge seu objetivo, quando é \(+1\). A função de valor de estado fornece então a probabilidade de ganhar de cada estado. Uma política é um mapeamento de níveis de capital para estacas. A política ótima maximiza a probabilidade de atingir o objetivo. Deixe \(p\) denotar a probabilidade da moeda dar CARA. Se \(p\) é conhecido, então todo o problema é conhecido e pode ser resolvido, por exemplo, por iteração de valor. A figura 4., abaixo, retirada do livro, mostra a mudança na função de valor conforme vamos iterando. E acabamos descobrindo a final polciy para quando \(p=0.4\).
