antonino, Autor em Área de Trampo

Monte Carlo com exploração de inícios

23/05/202623/03/2026 Por antonino

A exploração de inícios é uma técnica simples mas poderosa. Ela garante que todas as ações sejam experimentadas. Primeiramente, cada episódio começa em um par estado-ação aleatório. Em segundo lugar, a política é determinística durante o resto do episódio. Por conseguinte, a exploração é assegurada sem usar ε-greedy. Este método funciona apenas em ambientes que podem ser reiniciados.

Características da arquitetura

A arquitetura armazena Q(s,a) em uma tabela. Cada par estado-ação é inicializado com um valor. A política é gulosa em relação a Q. Contudo, o primeiro passo de cada episódio é forçado. Ele é escolhido aleatoriamente entre todas as ações possíveis. Depois disso, o agente segue a política gulosa. Esse método é chamado de Monte Carlo exploring starts. Ele é garantido de convergir para a política ótima. Uma desvantagem é a necessidade de reiniciar o ambiente. Muitos problemas reais não permitem isso.

A atualização first-visit é usada frequentemente. O retorno G_t é calculado ao final do episódio. A equação de atualização é \( Q(s,a) \leftarrow Q(s,a) + \alpha (G_t – Q(s,a)) \). Alternativamente, usamos a média simples: \( Q(s,a) = \frac{1}{N(s,a)} \sum_{i=1}^{N(s,a)} G_t^{(i)} \). A exploração de inícios substitui o ε-greedy. Portanto, não há hiperparâmetro epsilon. Isso simplifica o ajuste do modelo. Contudo, nem todo ambiente pode ser reiniciado arbitrariamente.

Hiperparâmetros e fórmulas

Os hiperparâmetros são poucos neste método. O fator de desconto γ é o mais importante. Valores típicos são 0.9, 0.95 ou 0.99. A taxa de aprendizado α pode ser usada (opcional). O número de episódios deve ser grande. Cada par estado-ação precisa ser visitado muitas vezes. A equação de Bellman para Q* é \( Q^*(s,a) = \sum_{s’,r} p(s’,r|s,a) [r + \gamma \max_{a’} Q^*(s’,a’)] \). Monte Carlo aproxima isso por amostragem. O erro é dado por \( \delta = G_t – Q(s,a) \). A convergência é garantida se cada par for visitado infinitas vezes.

A política gulosa é definida como \( \pi(s) = \arg\max_a Q(s,a) \). No exploring starts, o primeiro passo quebra essa gulodice. Isso é feito amostrando a ação inicial uniformemente. A probabilidade é \( P(A_0 = a | S_0 = s) = \frac{1}{|A(s)|} \). Depois disso, a política é determinística. Este método é elegante e teórico. Porém, sua aplicação prática é limitada.

Exemplo clássico: dado de 6 faces

Imagine um dado de 6 faces que você pode jogar. Cada face tem uma recompensa diferente. O estado é sempre o mesmo (único estado). As ações são escolher qual face apostar. Após a aposta, o dado é rolado. Você ganha a recompensa da face sorteada. O objetivo é maximizar a recompensa esperada. O ambiente é um bandido (k-armed bandit). A exploração de inícios força cada ação a ser testada. O código abaixo resolve este problema.

import numpy as np
import matplotlib.pyplot as plt

print("=" * 70)
print("MONTE CARLO COM EXPLORAÇÃO DE INÍCIOS (EXPLORING STARTS)")
print("=" * 70)

# ============================================
# AMBIENTE: BANDIDO (K-ARMED BANDIT)
# ============================================

class AmbienteBandido:
    """Dado de 6 faces com recompensas diferentes"""
    
    def __init__(self, recompensas_reais=None):
        # Recompensas reais de cada ação (face do dado)
        if recompensas_reais is None:
            self.recompensas_reais = np.array([0.2, 0.5, -0.3, 0.8, 0.1, 0.6])
        else:
            self.recompensas_reais = recompensas_reais
        
        self.n_acoes = len(self.recompensas_reais)
        self.melhor_acao = np.argmax(self.recompensas_reais)
        
    def reset(self, acao_inicial=None):
        """Reseta o ambiente (estado único)"""
        self.passo = 0
        return 0  # estado único
    
    def step(self, acao):
        """Executa ação e retorna recompensa"""
        # Recompensa é a média real + ruído
        recompensa = np.random.normal(self.recompensas_reais[acao], 0.1)
        self.passo += 1
        return 0, recompensa, True  # episódio termina após uma ação

# ============================================
# AGENTE MONTE CARLO COM EXPLORING STARTS
# ============================================

class AgenteMonteCarloExploringStarts:
    """Agente que usa exploring starts para explorar"""
    
    def __init__(self, n_acoes, gamma=1.0):
        self.n_acoes = n_acoes
        self.Q = np.zeros(n_acoes)  # Valor de cada ação
        self.returns = [[] for _ in range(n_acoes)]  # Retornos observados
        self.gamma = gamma
        self.politica = None  # Política gulosa será calculada dinamicamente
        
    def _politica_gulosa(self):
        """Retorna ação gulosa (melhor valor Q)"""
        return np.argmax(self.Q)
    
    def escolher_acao_inicial(self):
        """Exploração de inícios: escolhe ação aleatória"""
        return np.random.randint(self.n_acoes)
    
    def escolher_acao(self, state, passo):
        """Segue política gulosa após o primeiro passo"""
        return self._politica_gulosa()
    
    def aprender_episodio(self, episodio):
        """Aprende com episódio completo usando first-visit"""
        # Episódio é uma lista de (estado, ação, recompensa)
        G = 0
        first_visitados = set()
        
        # Itera do final para o início
        for t in range(len(episodio)-1, -1, -1):
            _, acao, recompensa = episodio[t]
            G = recompensa + self.gamma * G
            
            # First-visit
            if (acao,) not in first_visitados:
                first_visitados.add((acao,))
                self.returns[acao].append(G)
                self.Q[acao] = np.mean(self.returns[acao])

# ============================================
# EXPERIMENTO COMPARATIVO
# ============================================

print("\n" + "=" * 70)
print("EXPERIMENTO: COMPARAÇÃO DE MÉTODOS")
print("=" * 70)

# Configuração
n_acoes = 6
n_episodios = 2000
recompensas_reais = np.array([0.2, 0.5, -0.3, 0.8, 0.1, 0.6])

print(f"\n📊 Recompensas reais das ações:")
for i, r in enumerate(recompensas_reais):
    print(f"   Ação {i}: {r:.2f}")
print(f"\n🏆 Melhor ação: {np.argmax(recompensas_reais)} (recompensa {max(recompensas_reais):.2f})")

# ============================================
# MÉTODO 1: EXPLORING STARTS
# ============================================

print("\n" + "=" * 70)
print("MÉTODO 1: MONTE CARLO COM EXPLORING STARTS")
print("=" * 70)

env = AmbienteBandido(recompensas_reais)
agente_es = AgenteMonteCarloExploringStarts(n_acoes, gamma=1.0)

recompensas_es = []
acoes_escolhidas_es = []
melhor_acao = np.argmax(recompensas_reais)

for ep in range(n_episodios):
    # Começa com ação aleatória (exploring starts)
    estado = env.reset()
    acao_inicial = agente_es.escolher_acao_inicial()
    
    # Executa o episódio (apenas um passo)
    _, recompensa, _ = env.step(acao_inicial)
    
    # Registra episódio
    episodio = [(estado, acao_inicial, recompensa)]
    agente_es.aprender_episodio(episodio)
    
    recompensas_es.append(recompensa)
    acoes_escolhidas_es.append(acao_inicial)
    
    if (ep + 1) % 500 == 0:
        taxa_melhor = np.mean([1 if a == melhor_acao else 0 for a in acoes_escolhidas_es[-500:]]) * 100
        print(f"   Episódio {ep+1}: {taxa_melhor:.1f}% escolheu a melhor ação")

# ============================================
# MÉTODO 2: ε-GREEDY PARA COMPARAÇÃO
# ============================================

print("\n" + "=" * 70)
print("MÉTODO 2: MONTE CARLO COM ε-GREEDY (ε=0.1)")
print("=" * 70)

class AgenteMonteCarloEpsilon:
    """Agente Monte Carlo com ε-greedy para comparação"""
    
    def __init__(self, n_acoes, epsilon=0.1, gamma=1.0):
        self.n_acoes = n_acoes
        self.Q = np.zeros(n_acoes)
        self.returns = [[] for _ in range(n_acoes)]
        self.epsilon = epsilon
        self.gamma = gamma
    
    def escolher_acao(self):
        """Política ε-greedy"""
        if np.random.random() < self.epsilon:
            return np.random.randint(self.n_acoes)
        return np.argmax(self.Q)
    
    def aprender_episodio(self, episodio):
        G = 0
        first_visitados = set()
        for t in range(len(episodio)-1, -1, -1):
            _, acao, recompensa = episodio[t]
            G = recompensa + self.gamma * G
            if (acao,) not in first_visitados:
                first_visitados.add((acao,))
                self.returns[acao].append(G)
                self.Q[acao] = np.mean(self.returns[acao])

env2 = AmbienteBandido(recompensas_reais)
agente_eg = AgenteMonteCarloEpsilon(n_acoes, epsilon=0.1, gamma=1.0)

recompensas_eg = []
acoes_escolhidas_eg = []

for ep in range(n_episodios):
    estado = env2.reset()
    acao = agente_eg.escolher_acao()
    _, recompensa, _ = env2.step(acao)
    
    episodio = [(estado, acao, recompensa)]
    agente_eg.aprender_episodio(episodio)
    
    recompensas_eg.append(recompensa)
    acoes_escolhidas_eg.append(acao)
    
    if (ep + 1) % 500 == 0:
        taxa_melhor = np.mean([1 if a == melhor_acao else 0 for a in acoes_escolhidas_eg[-500:]]) * 100
        print(f"   Episódio {ep+1}: {taxa_melhor:.1f}% escolheu a melhor ação")

# ============================================
# RESULTADOS FINAIS
# ============================================

print("\n" + "=" * 70)
print("RESULTADOS FINAIS")
print("=" * 70)

Q_es = agente_es.Q
Q_eg = agente_eg.Q

print("\n📊 Valores Q aprendidos:")
print("   Ação | Real | Exploring Starts | ε-Greedy")
print("   " + "-" * 45)
for i in range(n_acoes):
    print(f"     {i}   | {recompensas_reais[i]:.2f}  |     {Q_es[i]:.2f}       |    {Q_eg[i]:.2f}")

print(f"\n🏆 Melhor ação real: {melhor_acao}")
print(f"   Exploring Starts escolheu: {np.argmax(Q_es)}")
print(f"   ε-Greedy escolheu: {np.argmax(Q_eg)}")

# ============================================
# GRÁFICOS
# ============================================

print("\n" + "=" * 70)
print("GERANDO GRÁFICOS")
print("=" * 70)

plt.figure(figsize=(14, 5))

# Gráfico 1: Comparação da taxa de escolha da melhor ação
plt.subplot(1, 2, 1)

# Calcula médias móveis (janela 100)
media_es = np.convolve([1 if a == melhor_acao else 0 for a in acoes_escolhidas_es], 
                        np.ones(100)/100, mode='valid')
media_eg = np.convolve([1 if a == melhor_acao else 0 for a in acoes_escolhidas_eg], 
                        np.ones(100)/100, mode='valid')

plt.plot(media_es, 'g-', linewidth=2, label='Exploring Starts')
plt.plot(media_eg, 'b-', linewidth=2, label='ε-Greedy (ε=0.1)')
plt.xlabel('Episódio')
plt.ylabel('Taxa de escolha da melhor ação')
plt.title('Comparação: Exploring Starts vs ε-Greedy')
plt.ylim(0, 1)
plt.grid(True, alpha=0.3)
plt.legend()

# Gráfico 2: Valores Q estimados vs reais
plt.subplot(1, 2, 2)

x = np.arange(n_acoes)
width = 0.25

plt.bar(x - width, recompensas_reais, width, label='Valor Real', color='gray', alpha=0.7)
plt.bar(x, Q_es, width, label='Exploring Starts', color='green', alpha=0.7)
plt.bar(x + width, Q_eg, width, label='ε-Greedy', color='blue', alpha=0.7)

plt.xlabel('Ação')
plt.ylabel('Valor Q')
plt.title('Estimativas de Valor por Método')
plt.xticks(x)
plt.legend()
plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

# ============================================
# VISUALIZAÇÃO DA EXPLORAÇÃO
# ============================================

print("\n" + "=" * 70)
print("ANÁLISE DA EXPLORAÇÃO")
print("=" * 70)

# Conta frequência de cada ação nos primeiros episódios
primeiros_episodios = 500
freq_es = np.zeros(n_acoes)
freq_eg = np.zeros(n_acoes)

for a in acoes_escolhidas_es[:primeiros_episodios]:
    freq_es[a] += 1
for a in acoes_escolhidas_eg[:primeiros_episodios]:
    freq_eg[a] += 1

freq_es = freq_es / primeiros_episodios * 100
freq_eg = freq_eg / primeiros_episodios * 100

print(f"\n📊 Distribuição das ações nos primeiros {primeiros_episodios} episódios:")
print("\n   Ação | Exploring Starts | ε-Greedy")
print("   " + "-" * 35)
for i in range(n_acoes):
    print(f"     {i}   |     {freq_es[i]:.1f}%      |    {freq_eg[i]:.1f}%")

print("\n🔍 Interpretação:")
print("   - Exploring Starts: explora TODAS as ações igualmente no início")
print("   - ε-Greedy: explora uniformemente, mas pode favorecer ações boas")
print("   - Exploring Starts garante que ações ruins sejam testadas")

# ============================================
# EXPLICAÇÃO MATEMÁTICA
# ============================================

print("\n" + "=" * 70)
print("FUNDAMENTOS MATEMÁTICOS - EXPLORING STARTS")
print("=" * 70)

print("""
✅ EXPLORING STARTS (EXPLORAÇÃO DE INÍCIOS):

Definição: Todo episódio começa com um par (estado, ação) aleatório.
Isso garante que todos os pares sejam visitados infinitas vezes.

✅ FÓRMULAS PRINCIPAIS:

1. RETORNO (G_t):
   [latex] G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots [/latex]

2. ATUALIZAÇÃO FIRST-VISIT:
   [latex] Q(s,a) = \frac{1}{N(s,a)} \sum_{i=1}^{N(s,a)} G_t^{(i)} [/latex]

3. POLÍTICA GULOSA (após primeiro passo):
   [latex] \pi(s) = \arg\max_a Q(s,a) [/latex]

4. PROBABILIDADE DE AÇÃO INICIAL:
   [latex] P(A_0 = a | S_0 = s) = \frac{1}{|A(s)|} [/latex]

✅ HIPERPARÂMETROS:

• γ (gamma): Fator de desconto (ex: 0.95 ou 1.0)
• N(s,a): Número de visitas ao par (s,a)
• Nenhum epsilon necessário!

✅ VANTAGENS DO EXPLORING STARTS:

✓ Não requer hiperparâmetro de exploração (ε)
✓ Garante exploração de todas as ações
✓ Convergência teórica garantida
✓ Mais simples de implementar

✅ DESVANTAGENS:

✗ Só funciona quando ambiente pode ser reiniciado
✗ Não prático para problemas reais
✗ Requer que todos os estados sejam acessíveis como inícios
""")

print("\n" + "=" * 70)
print("CONCLUSÃO")
print("=" * 70)

print("""
✅ Exploring Starts é um método elegante para garantir exploração.
✅ Ele força cada par estado-ação a ser visitado.
✅ A política é gulosa durante o resto do episódio.
✅ Este método é mais teórico do que prático.
✅ Contudo, é fundamental para provas de convergência.

COMPARAÇÃO FINAL:
• Exploring Starts: 100% exploração no primeiro passo
• ε-Greedy: exploração constante (ε) em todos os passos
• A escolha depende da capacidade de reiniciar o ambiente
""")

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

import numpy as np

import matplotlib.pyplot as plt

print("=" * 70)

print("MONTE CARLO COM EXPLORAÇÃO DE INÍCIOS (EXPLORING STARTS)")

print("=" * 70)

# ============================================

# AMBIENTE: BANDIDO (K-ARMED BANDIT)

# ============================================

class AmbienteBandido:

"""Dado de 6 faces com recompensas diferentes"""

def __init__(self, recompensas_reais=None):

# Recompensas reais de cada ação (face do dado)

if recompensas_reais is None:

self.recompensas_reais = np.array([0.2, 0.5, -0.3, 0.8, 0.1, 0.6])

else:

self.recompensas_reais = recompensas_reais

self.n_acoes = len(self.recompensas_reais)

self.melhor_acao = np.argmax(self.recompensas_reais)

def reset(self, acao_inicial=None):

"""Reseta o ambiente (estado único)"""

self.passo = 0

return 0 # estado único

def step(self, acao):

"""Executa ação e retorna recompensa"""

# Recompensa é a média real + ruído

recompensa = np.random.normal(self.recompensas_reais[acao], 0.1)

self.passo += 1

return 0, recompensa, True # episódio termina após uma ação

# ============================================

# AGENTE MONTE CARLO COM EXPLORING STARTS

# ============================================

class AgenteMonteCarloExploringStarts:

"""Agente que usa exploring starts para explorar"""

def __init__(self, n_acoes, gamma=1.0):

self.n_acoes = n_acoes

self.Q = np.zeros(n_acoes) # Valor de cada ação

self.returns = [[] for _ in range(n_acoes)] # Retornos observados

self.gamma = gamma

self.politica = None # Política gulosa será calculada dinamicamente

def _politica_gulosa(self):

"""Retorna ação gulosa (melhor valor Q)"""

return np.argmax(self.Q)

def escolher_acao_inicial(self):

"""Exploração de inícios: escolhe ação aleatória"""

return np.random.randint(self.n_acoes)

def escolher_acao(self, state, passo):

"""Segue política gulosa após o primeiro passo"""

return self._politica_gulosa()

def aprender_episodio(self, episodio):

"""Aprende com episódio completo usando first-visit"""

# Episódio é uma lista de (estado, ação, recompensa)

G = 0

first_visitados = set()

# Itera do final para o início

for t in range(len(episodio)-1, -1, -1):

_, acao, recompensa = episodio[t]

G = recompensa + self.gamma * G

# First-visit

if (acao,) not in first_visitados:

first_visitados.add((acao,))

self.returns[acao].append(G)

self.Q[acao] = np.mean(self.returns[acao])

# ============================================

# EXPERIMENTO COMPARATIVO

# ============================================

print("\n" + "=" * 70)

print("EXPERIMENTO: COMPARAÇÃO DE MÉTODOS")

print("=" * 70)

# Configuração

n_acoes = 6

n_episodios = 2000

recompensas_reais = np.array([0.2, 0.5, -0.3, 0.8, 0.1, 0.6])

print(f"\n📊 Recompensas reais das ações:")

for i, r in enumerate(recompensas_reais):

print(f" Ação {i}: {r:.2f}")

print(f"\n🏆 Melhor ação: {np.argmax(recompensas_reais)} (recompensa {max(recompensas_reais):.2f})")

# ============================================

# MÉTODO 1: EXPLORING STARTS

# ============================================

print("\n" + "=" * 70)

print("MÉTODO 1: MONTE CARLO COM EXPLORING STARTS")

print("=" * 70)

env = AmbienteBandido(recompensas_reais)

agente_es = AgenteMonteCarloExploringStarts(n_acoes, gamma=1.0)

recompensas_es = []

acoes_escolhidas_es = []

melhor_acao = np.argmax(recompensas_reais)

for ep in range(n_episodios):

# Começa com ação aleatória (exploring starts)

estado = env.reset()

acao_inicial = agente_es.escolher_acao_inicial()

# Executa o episódio (apenas um passo)

_, recompensa, _ = env.step(acao_inicial)

# Registra episódio

episodio = [(estado, acao_inicial, recompensa)]

agente_es.aprender_episodio(episodio)

recompensas_es.append(recompensa)

acoes_escolhidas_es.append(acao_inicial)

if (ep + 1) % 500 == 0:

taxa_melhor = np.mean([1 if a == melhor_acao else 0 for a in acoes_escolhidas_es[-500:]]) * 100

print(f" Episódio {ep+1}: {taxa_melhor:.1f}% escolheu a melhor ação")

# ============================================

# MÉTODO 2: ε-GREEDY PARA COMPARAÇÃO

# ============================================

print("\n" + "=" * 70)

print("MÉTODO 2: MONTE CARLO COM ε-GREEDY (ε=0.1)")

print("=" * 70)

class AgenteMonteCarloEpsilon:

"""Agente Monte Carlo com ε-greedy para comparação"""

def __init__(self, n_acoes, epsilon=0.1, gamma=1.0):

self.n_acoes = n_acoes

self.Q = np.zeros(n_acoes)

self.returns = [[] for _ in range(n_acoes)]

self.epsilon = epsilon

self.gamma = gamma

def escolher_acao(self):

"""Política ε-greedy"""

if np.random.random() < self.epsilon:

return np.random.randint(self.n_acoes)

return np.argmax(self.Q)

def aprender_episodio(self, episodio):

G = 0

first_visitados = set()

for t in range(len(episodio)-1, -1, -1):

_, acao, recompensa = episodio[t]

G = recompensa + self.gamma * G

if (acao,) not in first_visitados:

first_visitados.add((acao,))

self.returns[acao].append(G)

self.Q[acao] = np.mean(self.returns[acao])

env2 = AmbienteBandido(recompensas_reais)

agente_eg = AgenteMonteCarloEpsilon(n_acoes, epsilon=0.1, gamma=1.0)

recompensas_eg = []

acoes_escolhidas_eg = []

for ep in range(n_episodios):

estado = env2.reset()

acao = agente_eg.escolher_acao()

_, recompensa, _ = env2.step(acao)

episodio = [(estado, acao, recompensa)]

agente_eg.aprender_episodio(episodio)

recompensas_eg.append(recompensa)

acoes_escolhidas_eg.append(acao)

if (ep + 1) % 500 == 0:

taxa_melhor = np.mean([1 if a == melhor_acao else 0 for a in acoes_escolhidas_eg[-500:]]) * 100

print(f" Episódio {ep+1}: {taxa_melhor:.1f}% escolheu a melhor ação")

# ============================================

# RESULTADOS FINAIS

# ============================================

print("\n" + "=" * 70)

print("RESULTADOS FINAIS")

print("=" * 70)

Q_es = agente_es.Q

Q_eg = agente_eg.Q

print("\n📊 Valores Q aprendidos:")

print(" Ação | Real | Exploring Starts | ε-Greedy")

print(" " + "-" * 45)

for i in range(n_acoes):

print(f" {i} | {recompensas_reais[i]:.2f} | {Q_es[i]:.2f} | {Q_eg[i]:.2f}")

print(f"\n🏆 Melhor ação real: {melhor_acao}")

print(f" Exploring Starts escolheu: {np.argmax(Q_es)}")

print(f" ε-Greedy escolheu: {np.argmax(Q_eg)}")

# ============================================

# GRÁFICOS

# ============================================

print("\n" + "=" * 70)

print("GERANDO GRÁFICOS")

print("=" * 70)

plt.figure(figsize=(14, 5))

# Gráfico 1: Comparação da taxa de escolha da melhor ação

plt.subplot(1, 2, 1)

# Calcula médias móveis (janela 100)

media_es = np.convolve([1 if a == melhor_acao else 0 for a in acoes_escolhidas_es],

np.ones(100)/100, mode='valid')

media_eg = np.convolve([1 if a == melhor_acao else 0 for a in acoes_escolhidas_eg],

np.ones(100)/100, mode='valid')

plt.plot(media_es, 'g-', linewidth=2, label='Exploring Starts')

plt.plot(media_eg, 'b-', linewidth=2, label='ε-Greedy (ε=0.1)')

plt.xlabel('Episódio')

plt.ylabel('Taxa de escolha da melhor ação')

plt.title('Comparação: Exploring Starts vs ε-Greedy')

plt.ylim(0, 1)

plt.grid(True, alpha=0.3)

plt.legend()

# Gráfico 2: Valores Q estimados vs reais

plt.subplot(1, 2, 2)

x = np.arange(n_acoes)

width = 0.25

plt.bar(x - width, recompensas_reais, width, label='Valor Real', color='gray', alpha=0.7)

plt.bar(x, Q_es, width, label='Exploring Starts', color='green', alpha=0.7)

plt.bar(x + width, Q_eg, width, label='ε-Greedy', color='blue', alpha=0.7)

plt.xlabel('Ação')

plt.ylabel('Valor Q')

plt.title('Estimativas de Valor por Método')

plt.xticks(x)

plt.legend()

plt.grid(True, alpha=0.3)

plt.tight_layout()

plt.show()

# ============================================

# VISUALIZAÇÃO DA EXPLORAÇÃO

# ============================================

print("\n" + "=" * 70)

print("ANÁLISE DA EXPLORAÇÃO")

print("=" * 70)

# Conta frequência de cada ação nos primeiros episódios

primeiros_episodios = 500

freq_es = np.zeros(n_acoes)

freq_eg = np.zeros(n_acoes)

for a in acoes_escolhidas_es[:primeiros_episodios]:

freq_es[a] += 1

for a in acoes_escolhidas_eg[:primeiros_episodios]:

freq_eg[a] += 1

freq_es = freq_es / primeiros_episodios * 100

freq_eg = freq_eg / primeiros_episodios * 100

print(f"\n📊 Distribuição das ações nos primeiros {primeiros_episodios} episódios:")

print("\n Ação | Exploring Starts | ε-Greedy")

print(" " + "-" * 35)

for i in range(n_acoes):

print(f" {i} | {freq_es[i]:.1f}% | {freq_eg[i]:.1f}%")

print("\n🔍 Interpretação:")

print(" - Exploring Starts: explora TODAS as ações igualmente no início")

print(" - ε-Greedy: explora uniformemente, mas pode favorecer ações boas")

print(" - Exploring Starts garante que ações ruins sejam testadas")

# ============================================

# EXPLICAÇÃO MATEMÁTICA

# ============================================

print("\n" + "=" * 70)

print("FUNDAMENTOS MATEMÁTICOS - EXPLORING STARTS")

print("=" * 70)

print("""

✅ EXPLORING STARTS (EXPLORAÇÃO DE INÍCIOS):

Definição: Todo episódio começa com um par (estado, ação) aleatório.

Isso garante que todos os pares sejam visitados infinitas vezes.

✅ FÓRMULAS PRINCIPAIS:

1. RETORNO (G_t):

[latex] G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots [/latex]

2. ATUALIZAÇÃO FIRST-VISIT:

[latex] Q(s,a) = \frac{1}{N(s,a)} \sum_{i=1}^{N(s,a)} G_t^{(i)} [/latex]

3. POLÍTICA GULOSA (após primeiro passo):

[latex] \pi(s) = \arg\max_a Q(s,a) [/latex]

4. PROBABILIDADE DE AÇÃO INICIAL:

[latex] P(A_0 = a | S_0 = s) = \frac{1}{|A(s)|} [/latex]

✅ HIPERPARÂMETROS:

• γ (gamma): Fator de desconto (ex: 0.95 ou 1.0)

• N(s,a): Número de visitas ao par (s,a)

• Nenhum epsilon necessário!

✅ VANTAGENS DO EXPLORING STARTS:

✓ Não requer hiperparâmetro de exploração (ε)

✓ Garante exploração de todas as ações

✓ Convergência teórica garantida

✓ Mais simples de implementar

✅ DESVANTAGENS:

✗ Só funciona quando ambiente pode ser reiniciado

✗ Não prático para problemas reais

✗ Requer que todos os estados sejam acessíveis como inícios

""")

print("\n" + "=" * 70)

print("CONCLUSÃO")

print("=" * 70)

print("""

✅ Exploring Starts é um método elegante para garantir exploração.

✅ Ele força cada par estado-ação a ser visitado.

✅ A política é gulosa durante o resto do episódio.

✅ Este método é mais teórico do que prático.

✅ Contudo, é fundamental para provas de convergência.

COMPARAÇÃO FINAL:

• Exploring Starts: 100% exploração no primeiro passo

• ε-Greedy: exploração constante (ε) em todos os passos

• A escolha depende da capacidade de reiniciar o ambiente

""")

print("\n✅ PROGRAMA CONCLUÍDO COM SUCESSO!")

Métodos de Monte Carlo para problemas baseados em valor

23/05/202623/03/2026 Por antonino

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