1.4 – Por Reforco
1.4.2 – Metodos Baseados em Valor
1.4.2.2 – Metodos de Monte Carlo
LEGENDA
Principal
Ramo
Metodo
Problemas
Modelo
Arquitetura
Monte Carlo é uma família de métodos estatísticos. Eles usam amostragem aleatória para estimar quantidades. No aprendizado por reforço, Monte Carlo aprende com episódios completos. Primeiramente, o agente interage com o ambiente até o fim. Depois, ele calcula o retorno real de cada estado visitado. Por conseguinte, não é necessário conhecer o modelo do ambiente.
Características dos métodos de Monte Carlo
Monte Carlo só funciona para tarefas episódicas. Cada episódio deve ter um fim definido. A estimativa da função valor é feita pela média dos retornos observados. Frequentemente, usamos a média incremental: \( V(s) \leftarrow V(s) + \alpha (G_t – V(s)) \). Aqui G_t é o retorno real do episódio. Uma vantagem importante é a ausência de viés. Contudo, a variância pode ser alta. Muitos episódios são necessários para convergência.
A atualização pode ser first-visit ou every-visit. No first-visit, apenas a primeira ocorrência de cada estado conta. No every-visit, todas as ocorrências são usadas. A escolha entre eles é um hiperparâmetro. Outro hiperparâmetro é a taxa de aprendizado α. Valores típicos são 0.1 ou 0.01. A política pode ser fixa (avaliação) ou melhorada (controle). O método Monte Carlo sem modelo é muito poderoso. Ele é aplicado em jogos como Blackjack e Go.
Arquitetura e fórmulas matemáticas
A arquitetura armazena V(s) ou Q(s,a) em uma tabela. Para cada episódio, guardamos estados, ações e recompensas. O retorno é calculado somando recompensas futuras com desconto: \( G_t = \sum_{k=0}^{T-t-1} \gamma^k r_{t+k+1} \). A atualização first-visit é \( V(s) \leftarrow \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_t^{(i)} \). Isso é equivalente à média amostral. Para controle, usamos a estratégia ε-greedy. A política é melhorada após cada episódio.
A equação de atualização incremental é \( V(s) \leftarrow V(s) + \alpha (G_t – V(s)) \). O erro de Monte Carlo é \( \delta = G_t – V(s) \). Diferente do TD learning, não há bootstrap. Isso significa que o valor estimado não depende de outras estimativas. Portanto, Monte Carlo não sofre com viés de inicialização. Contudo, a variância é maior e a convergência mais lenta. O método é ideal quando o ambiente é estocástico mas episódico.
Exemplo clássico: Blackjack simplificado
Imagine uma versão simples do jogo Blackjack. O jogador vê sua soma (12-21) e a carta do dealer (2-11). Ele pode pedir (hit) ou parar (stick). Pedir mais de 21 resulta em derrota. O objetivo é vencer o dealer sem estourar. Recompensas: +1 por vitória, -1 por derrota, 0 por empate. O ambiente é estocástico e episódico. O código abaixo usa Monte Carlo para aprender a função valor.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 |
import numpy as np import matplotlib.pyplot as plt from collections import defaultdict import random print("=" * 70) print("MÉTODOS DE MONTE CARLO - BLACKJACK SIMPLIFICADO") print("=" * 70) # ============================================ # AMBIENTE BLACKJACK SIMPLIFICADO # ============================================ class BlackjackSimplificado: """Versão simplificada do Blackjack para demonstração""" def __init__(self): self.n_acoes = 2 # 0=pedir (hit), 1=parar (stick) def _soma_mao(self, cartas): """Calcula soma da mão tratando Ás como 1 ou 11""" soma = sum(cartas) ases = cartas.count(11) while soma > 21 and ases > 0: soma -= 10 ases -= 1 return soma def _carta_aleatoria(self): """Gera carta de baralho (2-11, 11 é Ás)""" carta = random.randint(2, 11) return carta def _mao_inicial(self): """Cria mão inicial do jogador e dealer""" jogador = [self._carta_aleatoria(), self._carta_aleatoria()] dealer = [self._carta_aleatoria(), self._carta_aleatoria()] return jogador, dealer def reset(self): """Inicia novo episódio""" self.jogador, self.dealer = self._mao_inicial() self.soma_jogador = self._soma_mao(self.jogador) self.carta_dealer = self.dealer[0] self.jogador_fez_hit = True self.terminou = False return (self.soma_jogador, self.carta_dealer, self.jogador_fez_hit) def step(self, acao): """Executa ação e retorna (prox_estado, recompensa, terminou)""" if acao == 0: # pedir (hit) nova_carta = self._carta_aleatoria() self.jogador.append(nova_carta) self.soma_jogador = self._soma_mao(self.jogador) if self.soma_jogador > 21: # Jogador estourou - perde return None, -1.0, True self.jogador_fez_hit = True return (self.soma_jogador, self.carta_dealer, self.jogador_fez_hit), 0.0, False else: # parar (stick) self.jogador_fez_hit = False # Dealer joga: regra simples, pede até soma >= 17 soma_dealer = self._soma_mao(self.dealer) while soma_dealer < 17: nova_carta = self._carta_aleatoria() self.dealer.append(nova_carta) soma_dealer = self._soma_mao(self.dealer) # Determina resultado if soma_dealer > 21 or self.soma_jogador > soma_dealer: recompensa = 1.0 # Jogador ganha elif self.soma_jogador == soma_dealer: recompensa = 0.0 # Empate else: recompensa = -1.0 # Jogador perde return None, recompensa, True # ============================================ # MÉTODO DE MONTE CARLO FIRST-VISIT # ============================================ class AgenteMonteCarlo: """Agente que aprende usando Monte Carlo first-visit""" def __init__(self, epsilon=0.1, alpha=0.1, gamma=0.95): self.Q = defaultdict(float) # Função ação-valor self.returns = defaultdict(list) # Retornos observados self.epsilon = epsilon # Exploração self.alpha = alpha # Taxa aprendizado (opcional) self.gamma = gamma # Fator desconto def escolher_acao(self, estado): """Política ε-greedy""" if random.random() < self.epsilon: return random.randint(0, 1) # Escolhe melhor ação q0 = self.Q[(estado, 0)] q1 = self.Q[(estado, 1)] return 0 if q0 >= q1 else 1 def aprender_episodio(self, episodio): """Aprende com um episódio completo usando first-visit""" # Armazena estados, ações e recompensas estados = [] acoes = [] recompensas = [] for (estado, acao, recompensa) in episodio: estados.append(estado) acoes.append(acao) recompensas.append(recompensa) # Calcula retornos G_t G = 0 first_visitados = set() # Itera do final para o início for t in range(len(episodio)-1, -1, -1): estado = estados[t] acao = acoes[t] recompensa = recompensas[t] G = recompensa + self.gamma * G # First-visit: atualiza apenas primeira ocorrência if (estado, acao) not in first_visitados: first_visitados.add((estado, acao)) self.returns[(estado, acao)].append(G) self.Q[(estado, acao)] = np.mean(self.returns[(estado, acao)]) # ============================================ # TREINAMENTO # ============================================ print("\n" + "=" * 70) print("TREINAMENTO COM MONTE CARLO") print("=" * 70) env = BlackjackSimplificado() agente = AgenteMonteCarlo(epsilon=0.2, alpha=0.1, gamma=0.95) num_episodios = 100000 vitorias = [] print(f"\n📊 Configuração:") print(f" - Episódios: {num_episodios}") print(f" - Epsilon: 0.2 (exploração)") print(f" - Gamma: 0.95") print(f"\n🚀 Treinando...\n") for ep in range(num_episodios): estado = env.reset() episodio = [] terminou = False while not terminou: acao = agente.escolher_acao(estado) prox_estado, recompensa, terminou = env.step(acao) episodio.append((estado, acao, recompensa)) estado = prox_estado agente.aprender_episodio(episodio) # Registra resultado if episodio[-1][2] == 1.0: vitorias.append(1) elif episodio[-1][2] == -1.0: vitorias.append(0) else: vitorias.append(0.5) # Progresso if (ep + 1) % 10000 == 0: taxa = np.mean(vitorias[-1000:]) * 100 print(f" Episódio {ep+1}: Taxa de vitória = {taxa:.1f}%") print("\n✅ Treinamento concluído!") # ============================================ # AVALIAÇÃO (SEM EXPLORAÇÃO) # ============================================ print("\n" + "=" * 70) print("AVALIAÇÃO DO AGENTE (SEM EXPLORAÇÃO)") print("=" * 70) agente.epsilon = 0 # Desliga exploração num_testes = 1000 vitorias_teste = [] for ep in range(num_testes): estado = env.reset() terminou = False while not terminou: acao = agente.escolher_acao(estado) estado, recompensa, terminou = env.step(acao) if recompensa == 1.0: vitorias_teste.append(1) elif recompensa == -1.0: vitorias_teste.append(0) else: vitorias_teste.append(0.5) taxa_final = np.mean(vitorias_teste) * 100 print(f"\n🏆 Taxa de vitória em {num_testes} partidas: {taxa_final:.1f}%") # ============================================ # VISUALIZAÇÃO DA FUNÇÃO VALOR # ============================================ print("\n" + "=" * 70) print("VISUALIZAÇÃO DA FUNÇÃO VALOR") print("=" * 70) # Cria grade de estados somas = range(12, 22) # Somas possíveis do jogador (12-21) cartas_dealer = range(2, 11) # Cartas visíveis do dealer (2-10) V = np.zeros((len(somas), len(cartas_dealer))) for i, soma in enumerate(somas): for j, carta in enumerate(cartas_dealer): estado = (soma, carta, True) # Jogador pode pedir q0 = agente.Q[(estado, 0)] q1 = agente.Q[(estado, 1)] V[i, j] = max(q0, q1) if (estado, 0) in agente.Q else 0 # Gráficos plt.figure(figsize=(14, 5)) # Gráfico 1: Evolução da taxa de vitória plt.subplot(1, 2, 1) media_movel = np.convolve(vitorias, np.ones(1000)/1000, mode='valid') plt.plot(media_movel, 'b-', linewidth=1) plt.xlabel('Episódio') plt.ylabel('Taxa de vitória (média 1000)') plt.title('Aprendizado por Monte Carlo\n(quanto maior, melhor)') plt.ylim(0, 1) plt.grid(True, alpha=0.3) plt.axhline(y=0.5, color='r', linestyle='--', alpha=0.5, label='Aleatório (50%)') plt.legend() # Gráfico 2: Função Valor V(s) plt.subplot(1, 2, 2) im = plt.imshow(V, cmap='RdYlGn', interpolation='nearest', extent=[2, 10, 21, 12], aspect='auto') plt.colorbar(im, label='Valor V(s)') plt.xlabel('Carta do Dealer') plt.ylabel('Soma do Jogador') plt.title('Função Valor V(s) - Monte Carlo\n(verde = melhor decisão)') # Anota os valores for i, soma in enumerate(somas): for j, carta in enumerate(cartas_dealer): if V[i, j] != 0: cor = 'white' if V[i, j] < 0 else 'black' plt.text(carta, soma, f'{V[i, j]:.2f}', ha='center', va='center', fontsize=8, color=cor) plt.tight_layout() plt.show() # ============================================ # POLÍTICA ÓTIMA (VISUALIZAÇÃO) # ============================================ print("\n" + "=" * 70) print("POLÍTICA ÓTIMA APRENDIDA") print("=" * 70) print("\n📋 Decisão: PEDIR (HIT) ou PARAR (STICK)?") print(" (Baseado na soma do jogador e carta do dealer)\n") print("Dealer →", end="") for carta in cartas_dealer: print(f" {carta:2d} ", end="") print("\n" + "-" * 50) for soma in somas: print(f"Soma {soma:2d} |", end="") for carta in cartas_dealer: estado = (soma, carta, True) q0 = agente.Q[(estado, 0)] q1 = agente.Q[(estado, 1)] if q0 > q1: print(" HIT ", end="") elif q1 > q0: print(" STCK", end="") else: print(" ? ", end="") print() print("\nLegenda: HIT = pedir carta | STCK = parar") # ============================================ # EXPLICAÇÃO DOS CONCEITOS # ============================================ print("\n" + "=" * 70) print("FUNDAMENTOS DOS MÉTODOS DE MONTE CARLO") print("=" * 70) print(""" ✅ CARACTERÍSTICAS PRINCIPAIS: • Aprendem com EPISÓDIOS COMPLETOS (não passo a passo) • Não precisam de modelo do ambiente (model-free) • Estimativas não enviesadas (bias = 0) • Variância alta (muitos episódios necessários) ✅ FÓRMULAS MATEMÁTICAS: 1. RETORNO (G_t): [latex] G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} [/latex] 2. ESTIMATIVA FIRST-VISIT: [latex] V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_t^{(i)} [/latex] 3. ATUALIZAÇÃO INCREMENTAL: [latex] V(s) \leftarrow V(s) + \alpha (G_t - V(s)) [/latex] ✅ HIPERPARÂMETROS: • ε (epsilon): Taxa de exploração (ex: 0.1 ou 0.2) • γ (gamma): Fator de desconto (ex: 0.95) • α (alpha): Taxa de aprendizado (opcional) • N(s): Número de visitas ao estado ✅ VANTAGENS E DESVANTAGENS: VANTAGENS: ✓ Não requer modelo do ambiente ✓ Simples de implementar ✓ Converge para solução ótima DESVANTAGENS: ✗ Só funciona para tarefas episódicas ✗ Variância alta (lento para convergir) ✗ Precisa de muitos episódios ✅ COMPARAÇÃO COM OUTROS MÉTODOS: • MONTE CARLO: Aprende com episódios completos • TD LEARNING: Aprende passo a passo (bootstrap) • PROGRAMAÇÃO DINÂMICA: Requer modelo do ambiente """) print("\n" + "=" * 70) print("CONCLUSÃO") print("=" * 70) print(""" ✅ Monte Carlo é ideal quando o ambiente é desconhecido. ✅ Ele aprende diretamente da experiência real. ✅ O agente melhora sua política após cada episódio. ✅ A função valor é estimada pela média dos retornos. ✅ Este método é amplamente usado em jogos e simulações. """) print("\n✅ PROGRAMA CONCLUÍDO COM SUCESSO!") |
