Métodos de Monte Carlo para problemas baseados em valor

4 – Por Reforco
4.2 – Metodos Baseados em Valor
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.

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!")

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!")

Indice

Características dos métodos de Monte Carlo

Arquitetura e fórmulas matemáticas

Exemplo clássico: Blackjack simplificado

Deixe um comentário Cancelar resposta