Arquivo de Inteligência Artificial - Página 43 de 165

Monte Carlo sem exploração de inícios

26/04/202623/03/2026 Por antonino

4.2 – Metodos Baseados em Valor
4.2.2 – Metodos de Monte Carlo
4.2.2.2 – Monte Carlo sem exploracao de inicios

LEGENDA

Principal

Ramo

Metodo

Problemas

Modelo

Arquitetura

Nem todo ambiente permite exploração de inícios. Muitos problemas têm um estado inicial fixo. Por exemplo, um jogo sempre começa do mesmo ponto. Nesses casos, precisamos de outras estratégias de exploração. Primeiramente, usamos políticas estocásticas como ε-greedy. Em segundo lugar, garantimos que todas as ações sejam tentadas. Por conseguinte, o agente aprende mesmo com início fixo.

Características da arquitetura

A arquitetura mantém uma política suave (soft policy). Isso significa que toda ação tem probabilidade > 0. Frequentemente, usamos ε-greedy ou softmax. A função Q(s,a) é aprendida por Monte Carlo. Contudo, a política usada para gerar episódios é diferente da política alvo. Esse é o conceito de off-policy learning. A política de comportamento (behavior) explora mais. A política alvo (target) é a ótima que queremos aprender. A razão de importância (importance sampling) corrige a diferença.

A atualização off-policy usa pesos de importância. A fórmula é \( \rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(a_k|s_k)}{b(a_k|s_k)} \). Esse peso ajusta o retorno amostrado. O estimador é \( V(s) = \frac{\sum_{t} \rho_{t:T-1} G_t}{\sum_{t} \rho_{t:T-1}} \). A variância pode ser alta com muitos termos. Por isso, usamos weighted importance sampling. Ele tem viés mas variância menor. Outra abordagem é on-policy com ε-greedy. Nela, a política de comportamento é a mesma alvo.

Hiperparâmetros e fórmulas matemáticas

Os hiperparâmetros principais são ε e γ. A taxa de exploração ε típica é 0.1. O fator de desconto γ é 0.95 ou 0.99. Para off-policy, usamos α (taxa aprendizado). A atualização incremental é \( Q(s,a) \leftarrow Q(s,a) + \alpha \rho (G_t – Q(s,a)) \). A política ε-greedy é definida como \( \pi(a|s) = 1 – \epsilon + \frac{\epsilon}{|A|} \) para a ação ótima. Para outras ações, \( \pi(a|s) = \frac{\epsilon}{|A|} \). Isso garante exploração contínua.

O erro de Monte Carlo on-policy é \( \delta = G_t – Q(s,a) \). No off-policy, o erro é ponderado por ρ. A convergência é garantida se exploração continuar. Contudo, a variância pode ser alta. Por isso, métodos de TD são preferidos na prática. Ainda assim, Monte Carlo sem exploring starts é importante. Ele é usado em jogos como Blackjack e Poker.

Exemplo clássico: Blackjack com início fixo

Considere o Blackjack com estado inicial sempre o mesmo. O jogador recebe duas cartas e vê uma do dealer. Ele não pode reiniciar em posições aleatórias. Portanto, exploring starts é impossível. Usamos ε-greedy para garantir exploração. O objetivo é aprender a função valor. O código abaixo implementa Monte Carlo on-policy com ε-greedy. Ele resolve o Blackjack sem exploring starts.

import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
import random

print("=" * 70)
print("MONTE CARLO SEM EXPLORAÇÃO DE INÍCIOS - BLACKJACK")
print("=" * 70)

# ============================================
# AMBIENTE BLACKJACK SIMPLIFICADO
# ============================================

class Blackjack:
    """Ambiente Blackjack com início fixo"""
    
    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)"""
        return random.randint(2, 11)
    
    def reset(self):
        """Inicia novo episódio - início SEMPRE fixo"""
        # Sempre começa com duas cartas para o jogador
        self.jogador = [self._carta_aleatoria(), self._carta_aleatoria()]
        self.dealer = [self._carta_aleatoria(), self._carta_aleatoria()]
        self.soma_jogador = self._soma_mao(self.jogador)
        self.carta_dealer = self.dealer[0]
        self.usou_aso = 11 in self.jogador
        self.terminou = False
        return (self.soma_jogador, self.carta_dealer, self.usou_aso)
    
    def step(self, acao):
        """Executa ação e retorna (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:
                return None, -1.0, True
            
            self.usou_aso = 11 in self.jogador
            return (self.soma_jogador, self.carta_dealer, self.usou_aso), 0.0, False
        
        else:  # parar (stick)
            # Dealer joga (regra: pede até soma >= 17)
            soma_dealer = self._soma_mao(self.dealer)
            while soma_dealer < 17:
                self.dealer.append(self._carta_aleatoria())
                soma_dealer = self._soma_mao(self.dealer)
            
            # Determina resultado
            if soma_dealer > 21 or self.soma_jogador > soma_dealer:
                recompensa = 1.0
            elif self.soma_jogador == soma_dealer:
                recompensa = 0.0
            else:
                recompensa = -1.0
            
            return None, recompensa, True

# ============================================
# AGENTE MONTE CARLO ON-POLICY COM ε-GREEDY
# ============================================

class AgenteMonteCarlo:
    """Agente Monte Carlo com ε-greedy (sem exploring starts)"""
    
    def __init__(self, epsilon=0.1, gamma=0.95):
        self.Q = defaultdict(float)
        self.returns = defaultdict(list)
        self.epsilon = epsilon
        self.gamma = gamma
        
    def _politica_egreedy(self, estado):
        """Política ε-greedy para o estado"""
        # Escolhe ação aleatória com probabilidade ε
        if random.random() < self.epsilon:
            return random.randint(0, 1)
        
        # Escolhe ação gulosa
        q0 = self.Q[(estado, 0)]
        q1 = self.Q[(estado, 1)]
        return 0 if q0 >= q1 else 1
    
    def escolher_acao(self, estado):
        """Usada durante interação com ambiente"""
        return self._politica_egreedy(estado)
    
    def aprender_episodio(self, episodio):
        """Aprende com episódio completo (first-visit)"""
        G = 0
        first_visitados = set()
        
        for t in range(len(episodio)-1, -1, -1):
            estado, acao, recompensa = episodio[t]
            G = recompensa + self.gamma * G
            
            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 INÍCIO FIXO E ε-GREEDY")
print("=" * 70)

env = Blackjack()
agente = AgenteMonteCarlo(epsilon=0.1, gamma=0.95)
num_episodios = 500000
vitorias = []

print(f"\n📊 Configuração:")
print(f"   - Episódios: {num_episodios}")
print(f"   - Epsilon: 0.1 (exploração constante)")
print(f"   - Gamma: 0.95")
print(f"   - Exploring starts: NÃO (início sempre fixo)")
print(f"\n🚀 Treinando... (pode levar alguns segundos)\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) % 50000 == 0:
        taxa = np.mean(vitorias[-5000:]) * 100
        print(f"   Episódio {ep+1}: Taxa de vitória = {taxa:.1f}%")

print("\n✅ Treinamento concluído!")

# ============================================
# AVALIAÇÃO FINAL
# ============================================

print("\n" + "=" * 70)
print("AVALIAÇÃO DO AGENTE (SEM EXPLORAÇÃO)")
print("=" * 70)

# Salva epsilon original e desliga exploração
epsilon_original = agente.epsilon
agente.epsilon = 0

num_testes = 10000
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}%")

# Restaura epsilon
agente.epsilon = epsilon_original

# ============================================
# VISUALIZAÇÃO DA FUNÇÃO VALOR
# ============================================

print("\n" + "=" * 70)
print("VISUALIZAÇÃO DA FUNÇÃO VALOR")
print("=" * 70)

# Cria grade de estados (soma do jogador 12-21, carta do dealer 2-10)
somas = range(12, 22)
cartas_dealer = range(2, 11)

# Matriz para com Ás (usável) e sem Ás
V_com_aso = np.zeros((len(somas), len(cartas_dealer)))
V_sem_aso = np.zeros((len(somas), len(cartas_dealer)))

for i, soma in enumerate(somas):
    for j, carta in enumerate(cartas_dealer):
        estado_com = (soma, carta, True)
        estado_sem = (soma, carta, False)
        
        q0_com = agente.Q[(estado_com, 0)]
        q1_com = agente.Q[(estado_com, 1)]
        V_com_aso[i, j] = max(q0_com, q1_com) if (estado_com, 0) in agente.Q else 0
        
        q0_sem = agente.Q[(estado_sem, 0)]
        q1_sem = agente.Q[(estado_sem, 1)]
        V_sem_aso[i, j] = max(q0_sem, q1_sem) if (estado_sem, 0) in agente.Q else 0

# Gráficos
plt.figure(figsize=(14, 6))

# Gráfico 1: Evolução da taxa de vitória
plt.subplot(2, 2, 1)
media_movel = np.convolve(vitorias, np.ones(5000)/5000, mode='valid')
plt.plot(media_movel, 'b-', linewidth=1)
plt.xlabel('Episódio')
plt.ylabel('Taxa de vitória (média 5000)')
plt.title('Aprendizado com Início Fixo (ε=0.1)')
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 com Ás usável
plt.subplot(2, 2, 2)
im1 = plt.imshow(V_com_aso, cmap='RdYlGn', interpolation='nearest',
                 extent=[2, 10, 21, 12], aspect='auto')
plt.colorbar(im1, label='Valor V(s)')
plt.xlabel('Carta do Dealer')
plt.ylabel('Soma do Jogador')
plt.title('Com Ás usável (verde = melhor)')

# Gráfico 3: Função Valor sem Ás
plt.subplot(2, 2, 3)
im2 = plt.imshow(V_sem_aso, cmap='RdYlGn', interpolation='nearest',
                 extent=[2, 10, 21, 12], aspect='auto')
plt.colorbar(im2, label='Valor V(s)')
plt.xlabel('Carta do Dealer')
plt.ylabel('Soma do Jogador')
plt.title('Sem Ás usável')

# Gráfico 4: Política ótima (diferença entre ações)
plt.subplot(2, 2, 4)
politica = np.zeros((len(somas), len(cartas_dealer)))
for i, soma in enumerate(somas):
    for j, carta in enumerate(cartas_dealer):
        estado = (soma, carta, False)
        q0 = agente.Q[(estado, 0)]
        q1 = agente.Q[(estado, 1)]
        politica[i, j] = 0 if q0 >= q1 else 1

im3 = plt.imshow(politica, cmap='RdBu', interpolation='nearest',
                 extent=[2, 10, 21, 12], aspect='auto')
plt.colorbar(im3, label='0=Pedir, 1=Parar')
plt.xlabel('Carta do Dealer')
plt.ylabel('Soma do Jogador')
plt.title('Política Ótima (0=HIT, 1=STICK)')

plt.tight_layout()
plt.show()

# ============================================
# COMPARAÇÃO COM DIFERENTES EPSILONS
# ============================================

print("\n" + "=" * 70)
print("COMPARAÇÃO COM DIFERENTES VALORES DE ε")
print("=" * 70)

epsilons = [0.01, 0.05, 0.1, 0.2, 0.3]
taxas = []

for eps in epsilons:
    print(f"\n   Testando ε = {eps}...")
    agente_teste = AgenteMonteCarlo(epsilon=eps, gamma=0.95)
    
    # Treino rápido (10000 episódios)
    for ep in range(10000):
        estado = env.reset()
        episodio = []
        terminou = False
        while not terminou:
            acao = agente_teste.escolher_acao(estado)
            prox_estado, recompensa, terminou = env.step(acao)
            episodio.append((estado, acao, recompensa))
            estado = prox_estado
        agente_teste.aprender_episodio(episodio)
    
    # Avaliação
    agente_teste.epsilon = 0
    vitorias_eps = []
    for _ in range(2000):
        estado = env.reset()
        terminou = False
        while not terminou:
            acao = agente_teste.escolher_acao(estado)
            estado, recompensa, terminou = env.step(acao)
        if recompensa == 1.0:
            vitorias_eps.append(1)
        elif recompensa == -1.0:
            vitorias_eps.append(0)
        else:
            vitorias_eps.append(0.5)
    
    taxa = np.mean(vitorias_eps) * 100
    taxas.append(taxa)
    print(f"      Taxa de vitória: {taxa:.1f}%")

print("\n📊 Resumo da comparação:")
for eps, taxa in zip(epsilons, taxas):
    print(f"   ε = {eps}: {taxa:.1f}%")

print("\n🔍 Melhor ε: " + str(epsilons[np.argmax(taxas)]))

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

print("\n" + "=" * 70)
print("FUNDAMENTOS - MONTE CARLO SEM EXPLORING STARTS")
print("=" * 70)

print("""
✅ DESAFIO: Sem exploring starts, precisamos de exploração contínua.

✅ SOLUÇÃO: Política suave (soft policy) como ε-greedy.

✅ FÓRMULAS PRINCIPAIS:

1. POLÍTICA ε-GREEDY:
   [latex] \pi(a|s) = \begin{cases} 
   1 - \epsilon + \frac{\epsilon}{|A|}, & \text{se } a = \arg\max Q(s,a) \\
   \frac{\epsilon}{|A|}, & \text{caso contrário}
   \end{cases} [/latex]

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

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

✅ HIPERPARÂMETROS CRÍTICOS:

• ε (epsilon): Taxa de exploração (ex: 0.05 a 0.3)
• γ (gamma): Fator de desconto (ex: 0.95)
• N(s,a): Número de visitas ao par

✅ VANTAGENS E DESVANTAGENS:

VANTAGENS:
✓ Não precisa de reinicialização do ambiente
✓ Funciona para qualquer problema episódico
✓ Simples de implementar

DESVANTAGENS:
✗ Exploração constante (nunca converge completamente)
✗ Pode escolher ações subótimas para sempre
✗ Necessita ajuste do ε

✅ COMPARAÇÃO COM EXPLORING STARTS:

• COM EXPLORING STARTS: Exploração garantida, política gulosa
• SEM EXPLORING STARTS: Exploração via ε, política suave
• A escolha depende se ambiente pode ser reiniciado
""")

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

print("""
✅ Monte Carlo sem exploring starts é mais prático.
✅ Ele funciona quando o início do episódio é fixo.
✅ A exploração é garantida por políticas suaves (ε-greedy).
✅ O agente aprende a função valor mesmo sem reinicialização.
✅ Este método é amplamente usado em jogos reais.
""")

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

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

import numpy as np

import matplotlib.pyplot as plt

from collections import defaultdict

import random

print("=" * 70)

print("MONTE CARLO SEM EXPLORAÇÃO DE INÍCIOS - BLACKJACK")

print("=" * 70)

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

# AMBIENTE BLACKJACK SIMPLIFICADO

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

class Blackjack:

"""Ambiente Blackjack com início fixo"""

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

return random.randint(2, 11)

def reset(self):

"""Inicia novo episódio - início SEMPRE fixo"""

# Sempre começa com duas cartas para o jogador

self.jogador = [self._carta_aleatoria(), self._carta_aleatoria()]

self.dealer = [self._carta_aleatoria(), self._carta_aleatoria()]

self.soma_jogador = self._soma_mao(self.jogador)

self.carta_dealer = self.dealer[0]

self.usou_aso = 11 in self.jogador

self.terminou = False

return (self.soma_jogador, self.carta_dealer, self.usou_aso)

def step(self, acao):

"""Executa ação e retorna (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:

return None, -1.0, True

self.usou_aso = 11 in self.jogador

return (self.soma_jogador, self.carta_dealer, self.usou_aso), 0.0, False

else: # parar (stick)

# Dealer joga (regra: pede até soma >= 17)

soma_dealer = self._soma_mao(self.dealer)

while soma_dealer < 17:

self.dealer.append(self._carta_aleatoria())

soma_dealer = self._soma_mao(self.dealer)

# Determina resultado

if soma_dealer > 21 or self.soma_jogador > soma_dealer:

recompensa = 1.0

elif self.soma_jogador == soma_dealer:

recompensa = 0.0

else:

recompensa = -1.0

return None, recompensa, True

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

# AGENTE MONTE CARLO ON-POLICY COM ε-GREEDY

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

class AgenteMonteCarlo:

"""Agente Monte Carlo com ε-greedy (sem exploring starts)"""

def __init__(self, epsilon=0.1, gamma=0.95):

self.Q = defaultdict(float)

self.returns = defaultdict(list)

self.epsilon = epsilon

self.gamma = gamma

def _politica_egreedy(self, estado):

"""Política ε-greedy para o estado"""

# Escolhe ação aleatória com probabilidade ε

if random.random() < self.epsilon:

return random.randint(0, 1)

# Escolhe ação gulosa

q0 = self.Q[(estado, 0)]

q1 = self.Q[(estado, 1)]

return 0 if q0 >= q1 else 1

def escolher_acao(self, estado):

"""Usada durante interação com ambiente"""

return self._politica_egreedy(estado)

def aprender_episodio(self, episodio):

"""Aprende com episódio completo (first-visit)"""

G = 0

first_visitados = set()

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

estado, acao, recompensa = episodio[t]

G = recompensa + self.gamma * G

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 INÍCIO FIXO E ε-GREEDY")

print("=" * 70)

env = Blackjack()

agente = AgenteMonteCarlo(epsilon=0.1, gamma=0.95)

num_episodios = 500000

vitorias = []

print(f"\n📊 Configuração:")

print(f" - Episódios: {num_episodios}")

print(f" - Epsilon: 0.1 (exploração constante)")

print(f" - Gamma: 0.95")

print(f" - Exploring starts: NÃO (início sempre fixo)")

print(f"\n🚀 Treinando... (pode levar alguns segundos)\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) % 50000 == 0:

taxa = np.mean(vitorias[-5000:]) * 100

print(f" Episódio {ep+1}: Taxa de vitória = {taxa:.1f}%")

print("\n✅ Treinamento concluído!")

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

# AVALIAÇÃO FINAL

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

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

print("AVALIAÇÃO DO AGENTE (SEM EXPLORAÇÃO)")

print("=" * 70)

# Salva epsilon original e desliga exploração

epsilon_original = agente.epsilon

agente.epsilon = 0

num_testes = 10000

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}%")

# Restaura epsilon

agente.epsilon = epsilon_original

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

# VISUALIZAÇÃO DA FUNÇÃO VALOR

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

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

print("VISUALIZAÇÃO DA FUNÇÃO VALOR")

print("=" * 70)

# Cria grade de estados (soma do jogador 12-21, carta do dealer 2-10)

somas = range(12, 22)

cartas_dealer = range(2, 11)

# Matriz para com Ás (usável) e sem Ás

V_com_aso = np.zeros((len(somas), len(cartas_dealer)))

V_sem_aso = np.zeros((len(somas), len(cartas_dealer)))

for i, soma in enumerate(somas):

for j, carta in enumerate(cartas_dealer):

estado_com = (soma, carta, True)

estado_sem = (soma, carta, False)

q0_com = agente.Q[(estado_com, 0)]

q1_com = agente.Q[(estado_com, 1)]

V_com_aso[i, j] = max(q0_com, q1_com) if (estado_com, 0) in agente.Q else 0

q0_sem = agente.Q[(estado_sem, 0)]

q1_sem = agente.Q[(estado_sem, 1)]

V_sem_aso[i, j] = max(q0_sem, q1_sem) if (estado_sem, 0) in agente.Q else 0

# Gráficos

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

# Gráfico 1: Evolução da taxa de vitória

plt.subplot(2, 2, 1)

media_movel = np.convolve(vitorias, np.ones(5000)/5000, mode='valid')

plt.plot(media_movel, 'b-', linewidth=1)

plt.xlabel('Episódio')

plt.ylabel('Taxa de vitória (média 5000)')

plt.title('Aprendizado com Início Fixo (ε=0.1)')

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 com Ás usável

plt.subplot(2, 2, 2)

im1 = plt.imshow(V_com_aso, cmap='RdYlGn', interpolation='nearest',

extent=[2, 10, 21, 12], aspect='auto')

plt.colorbar(im1, label='Valor V(s)')

plt.xlabel('Carta do Dealer')

plt.ylabel('Soma do Jogador')

plt.title('Com Ás usável (verde = melhor)')

# Gráfico 3: Função Valor sem Ás

plt.subplot(2, 2, 3)

im2 = plt.imshow(V_sem_aso, cmap='RdYlGn', interpolation='nearest',

extent=[2, 10, 21, 12], aspect='auto')

plt.colorbar(im2, label='Valor V(s)')

plt.xlabel('Carta do Dealer')

plt.ylabel('Soma do Jogador')

plt.title('Sem Ás usável')

# Gráfico 4: Política ótima (diferença entre ações)

plt.subplot(2, 2, 4)

politica = np.zeros((len(somas), len(cartas_dealer)))

for i, soma in enumerate(somas):

for j, carta in enumerate(cartas_dealer):

estado = (soma, carta, False)

q0 = agente.Q[(estado, 0)]

q1 = agente.Q[(estado, 1)]

politica[i, j] = 0 if q0 >= q1 else 1

im3 = plt.imshow(politica, cmap='RdBu', interpolation='nearest',

extent=[2, 10, 21, 12], aspect='auto')

plt.colorbar(im3, label='0=Pedir, 1=Parar')

plt.xlabel('Carta do Dealer')

plt.ylabel('Soma do Jogador')

plt.title('Política Ótima (0=HIT, 1=STICK)')

plt.tight_layout()

plt.show()

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

# COMPARAÇÃO COM DIFERENTES EPSILONS

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

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

print("COMPARAÇÃO COM DIFERENTES VALORES DE ε")

print("=" * 70)

epsilons = [0.01, 0.05, 0.1, 0.2, 0.3]

taxas = []

for eps in epsilons:

print(f"\n Testando ε = {eps}...")

agente_teste = AgenteMonteCarlo(epsilon=eps, gamma=0.95)

# Treino rápido (10000 episódios)

for ep in range(10000):

estado = env.reset()

episodio = []

terminou = False

while not terminou:

acao = agente_teste.escolher_acao(estado)

prox_estado, recompensa, terminou = env.step(acao)

episodio.append((estado, acao, recompensa))

estado = prox_estado

agente_teste.aprender_episodio(episodio)

# Avaliação

agente_teste.epsilon = 0

vitorias_eps = []

for _ in range(2000):

estado = env.reset()

terminou = False

while not terminou:

acao = agente_teste.escolher_acao(estado)

estado, recompensa, terminou = env.step(acao)

if recompensa == 1.0:

vitorias_eps.append(1)

elif recompensa == -1.0:

vitorias_eps.append(0)

else:

vitorias_eps.append(0.5)

taxa = np.mean(vitorias_eps) * 100

taxas.append(taxa)

print(f" Taxa de vitória: {taxa:.1f}%")

print("\n📊 Resumo da comparação:")

for eps, taxa in zip(epsilons, taxas):

print(f" ε = {eps}: {taxa:.1f}%")

print("\n🔍 Melhor ε: " + str(epsilons[np.argmax(taxas)]))

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

# EXPLICAÇÃO MATEMÁTICA

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

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

print("FUNDAMENTOS - MONTE CARLO SEM EXPLORING STARTS")

print("=" * 70)

print("""

✅ DESAFIO: Sem exploring starts, precisamos de exploração contínua.

✅ SOLUÇÃO: Política suave (soft policy) como ε-greedy.

✅ FÓRMULAS PRINCIPAIS:

1. POLÍTICA ε-GREEDY:

[latex] \pi(a|s) = \begin{cases}

1 - \epsilon + \frac{\epsilon}{|A|}, & \text{se } a = \arg\max Q(s,a) \\

\frac{\epsilon}{|A|}, & \text{caso contrário}

\end{cases} [/latex]

2. ATUALIZAÇÃO ON-POLICY (first-visit):

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

3. RETORNO COM DESCONTO:

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

✅ HIPERPARÂMETROS CRÍTICOS:

• ε (epsilon): Taxa de exploração (ex: 0.05 a 0.3)

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

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

✅ VANTAGENS E DESVANTAGENS:

VANTAGENS:

✓ Não precisa de reinicialização do ambiente

✓ Funciona para qualquer problema episódico

✓ Simples de implementar

DESVANTAGENS:

✗ Exploração constante (nunca converge completamente)

✗ Pode escolher ações subótimas para sempre

✗ Necessita ajuste do ε

✅ COMPARAÇÃO COM EXPLORING STARTS:

• COM EXPLORING STARTS: Exploração garantida, política gulosa

• SEM EXPLORING STARTS: Exploração via ε, política suave

• A escolha depende se ambiente pode ser reiniciado

""")

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

print("CONCLUSÃO")

print("=" * 70)

print("""

✅ Monte Carlo sem exploring starts é mais prático.

✅ Ele funciona quando o início do episódio é fixo.

✅ A exploração é garantida por políticas suaves (ε-greedy).

✅ O agente aprende a função valor mesmo sem reinicialização.

✅ Este método é amplamente usado em jogos reais.

""")

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

Monte Carlo com exploração de inícios

25/04/202623/03/2026 Por antonino

4.2 – Metodos Baseados em Valor
4.2.2 – Metodos de Monte Carlo
4.2.2.1 – Monte Carlo com exploracao de inicios

LEGENDA

Principal

Ramo

Metodo

Problemas

Modelo

Arquitetura

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