Monte Carlo com exploração de inícios

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

Indice

Características da arquitetura

Hiperparâmetros e fórmulas

Exemplo clássico: dado de 6 faces

Deixe um comentário Cancelar resposta