1.4 – Por Reforco
1.4.2 – Metodos Baseados em Valor
1.4.2.1 – Programacao Dinamica
LEGENDA
Principal
Ramo
Metodo
Problemas
Modelo
Arquitetura
Problemas baseados em valor e programação dinâmica
A programação dinâmica resolve problemas de decisão sequencial. Ela é usada quando o modelo do ambiente é conhecido. Primeiramente, ela calcula funções valor de forma iterativa. Em segundo lugar, ela extrai políticas ótimas dessas funções. Por conseguinte, é uma ferramenta poderosa para planejamento. Este método é considerado a base teórica do aprendizado por reforço moderno.
Iteração de valor e iteração de política
A iteração de valor atualiza todos os estados simultaneamente. A fórmula é \( V_{k+1}(s) = \max_a \sum_{s’,r} p(s’,r|s,a) [r + \gamma V_k(s’)] \). Esse processo converge para V* após várias iterações. A iteração de política, por outro lado, alterna entre avaliação e melhoria. Primeiro, avaliamos a política atual. Depois, melhoramos ela guloso. Ambos os métodos são garantidos de convergir.
A avaliação de política é feita resolvendo \( V^\pi(s) = \sum_a \pi(a|s) \sum_{s’,r} p(s’,r|s,a) [r + \gamma V^\pi(s’)] \). Isso é um sistema de equações lineares. Na prática, usamos iteração para resolvê-lo. A melhoria de política atualiza com \( \pi'(s) = \arg\max_a \sum_{s’,r} p(s’,r|s,a) [r + \gamma V^\pi(s’)] \). O processo repete até que a política não mude mais.
Hiperparâmetros e arquitetura
O fator de desconto γ é o hiperparâmetro mais importante. Valores típicos são 0.9, 0.95 ou 0.99. O critério de convergência θ (theta) controla a precisão. Valores menores como 1e-6 dão resultados mais exatos. O número máximo de iterações evita loops infinitos. A arquitetura armazena valores em uma tabela (espaço discreto). Para espaços contínuos, usamos aproximadores como redes neurais. Contudo, programação dinâmica clássica assume tabela finita.
A complexidade computacional é O(|S|² × |A|). Isso pode ser pesado para muitos estados. Por isso, usamos técnicas de varredura assíncrona. A programação dinâmica é um método de planejamento. Ela não aprende por interação, mas sim por cálculo direto. Portanto, é diferente do Q-learning que é livre de modelo.
Exemplo clássico: grade com recompensas
Imagine uma grade 4×4 onde cada célula é um estado. O agente começa no canto superior esquerdo. O objetivo está no canto inferior direito. Recompensas: -0.1 por passo, +10 no objetivo. Paredes bloqueiam certas células. O ambiente é determinístico e conhecido. O objetivo é encontrar a política ótima. O código abaixo resolve com iteração de valor.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 |
import numpy as np import matplotlib.pyplot as plt print("=" * 70) print("PROGRAMAÇÃO DINÂMICA - ITERAÇÃO DE VALOR") print("=" * 70) # ============================================ # DEFINIÇÃO DO AMBIENTE # ============================================ class AmbienteGrade: """Grade 4x4 com paredes e objetivo""" def __init__(self): # Mapa: 0=caminho, 1=parede, 2=objetivo self.grid = np.array([ [0, 0, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 2, 0] ]) self.n_estados = 16 self.n_acoes = 4 # 0=cima, 1=baixo, 2=esq, 3=dir self.inicio = 0 self.objetivo = 14 # posição (3,2) # Pré-computa transições self.transicoes = {} self.recompensas = {} self._precomputar() def _precomputar(self): """Calcula todas as transições e recompensas""" for estado in range(self.n_estados): linha = estado // 4 coluna = estado % 4 for acao in range(self.n_acoes): # Calcula movimento if acao == 0: # cima nl = max(0, linha - 1) nc = coluna elif acao == 1: # baixo nl = min(3, linha + 1) nc = coluna elif acao == 2: # esquerda nl = linha nc = max(0, coluna - 1) else: # direita nl = linha nc = min(3, coluna + 1) # Verifica parede if self.grid[nl, nc] == 1: prox_estado = estado recompensa = -0.5 terminou = False else: prox_estado = nl * 4 + nc if self.grid[nl, nc] == 2: recompensa = 10.0 terminou = True else: recompensa = -0.1 terminou = False self.transicoes[(estado, acao)] = prox_estado self.recompensas[(estado, acao)] = recompensa # ============================================ # ITERAÇÃO DE VALOR (PROGRAMAÇÃO DINÂMICA) # ============================================ def iteracao_valor(ambiente, gamma=0.95, theta=1e-6, max_iter=1000): """Implementa iteração de valor para encontrar política ótima""" V = np.zeros(ambiente.n_estados) historico_valores = [] # para visualização print(f"\n📊 Parâmetros:") print(f" - γ (gamma) = {gamma}") print(f" - θ (theta) = {theta}") print(f" - Max iterações = {max_iter}") for i in range(max_iter): delta = 0 V_antigo = V.copy() historico_valores.append(V.copy()) for s in range(ambiente.n_estados): if s == ambiente.objetivo: continue # Calcula valor máximo sobre ações valores_acoes = [] for a in range(ambiente.n_acoes): s_prox = ambiente.transicoes[(s, a)] r = ambiente.recompensas[(s, a)] valor = r + gamma * V_antigo[s_prox] valores_acoes.append(valor) V[s] = max(valores_acoes) delta = max(delta, abs(V[s] - V_antigo[s])) if i % 50 == 0: print(f" Iteração {i}: delta = {delta:.6f}") if delta < theta: print(f"\n✅ Convergiu após {i+1} iterações!") break # Extrai política ótima politica = np.zeros(ambiente.n_estados, dtype=int) for s in range(ambiente.n_estados): if s == ambiente.objetivo: politica[s] = -1 continue valores_acoes = [] for a in range(ambiente.n_acoes): s_prox = ambiente.transicoes[(s, a)] r = ambiente.recompensas[(s, a)] valores_acoes.append(r + gamma * V[s_prox]) politica[s] = np.argmax(valores_acoes) return V, politica, historico_valores # ============================================ # AVALIAÇÃO DA POLÍTICA # ============================================ def avaliar_politica(ambiente, politica, gamma=0.95, max_passos=50): """Simula a política ótima para verificar seu desempenho""" estado = ambiente.inicio trajetoria = [estado] recompensa_total = 0 passos = 0 while estado != ambiente.objetivo and passos < max_passos: acao = politica[estado] if acao == -1: break s_prox = ambiente.transicoes[(estado, acao)] r = ambiente.recompensas[(estado, acao)] trajetoria.append(s_prox) recompensa_total += r estado = s_prox passos += 1 return trajetoria, recompensa_total, passos # ============================================ # EXECUÇÃO PRINCIPAL # ============================================ # Cria ambiente ambiente = AmbienteGrade() print("\n" + "=" * 70) print("AMBIENTE: GRADE 4x4") print("=" * 70) print("\n🗺️ Mapa do ambiente:") print(" Col0 Col1 Col2 Col3") for i in range(4): linha = f"Lin{i}: " for j in range(4): if ambiente.grid[i, j] == 1: linha += " ██ " elif ambiente.grid[i, j] == 2: linha += " 🎯 " else: linha += " ·· " print(linha) print("\nLegenda: ·· = caminho | ██ = parede | 🎯 = objetivo (+10)") print("Recompensas: -0.1 por passo | -0.5 por bater na parede") # Executa iteração de valor print("\n" + "=" * 70) print("ITERAÇÃO DE VALOR (PROGRAMAÇÃO DINÂMICA)") print("=" * 70) V_otimo, politica_otima, historico = iteracao_valor(ambiente, gamma=0.95) # Mostra função valor print("\n" + "=" * 70) print("FUNÇÃO VALOR ÓTIMA V*(s)") print("=" * 70) print("\n📈 Valores por estado:") for i in range(4): linha = "" for j in range(4): s = i * 4 + j if ambiente.grid[i, j] == 1: linha += " ██ " elif s == ambiente.objetivo: linha += " 🎯🎯 " else: linha += f" {V_otimo[s]:6.2f} " print(linha) # Mostra política ótima print("\n" + "=" * 70) print("POLÍTICA ÓTIMA π*(s)") print("=" * 70) setas = ['↑', '↓', '←', '→'] print("\n🎯 Melhor ação em cada estado:") for i in range(4): linha = "" for j in range(4): s = i * 4 + j if ambiente.grid[i, j] == 1: linha += " ██ " elif s == ambiente.objetivo: linha += " 🎯 " else: linha += f" {setas[politica_otima[s]]} " print(linha) # Simula uma trajetória print("\n" + "=" * 70) print("SIMULAÇÃO DA POLÍTICA ÓTIMA") print("=" * 70) trajetoria, recomp_total, passos = avaliar_politica(ambiente, politica_otima) print(f"\n🚶 Trajetória do início ao objetivo:") for i, s in enumerate(trajetoria): linha = s // 4 col = s % 4 if s == ambiente.objetivo: print(f" Passo {i}: → 🎯 OBJETIVO! (posição {linha},{col})") else: print(f" Passo {i}: posição ({linha},{col})") print(f"\n💰 Recompensa total: {recomp_total:.2f}") print(f"📏 Passos: {passos}") # ============================================ # GRÁFICOS # ============================================ print("\n" + "=" * 70) print("GERANDO GRÁFICOS") print("=" * 70) plt.figure(figsize=(14, 5)) # Gráfico 1: Convergência da iteração de valor plt.subplot(1, 2, 1) # Calcula a mudança máxima por iteração deltas = [] for i in range(1, len(historico)): delta = np.max(np.abs(historico[i] - historico[i-1])) deltas.append(delta) plt.semilogy(deltas, 'b-', linewidth=2) plt.xlabel('Iteração') plt.ylabel('Mudança máxima (escala log)') plt.title('Convergência da Iteração de Valor\n(quanto menor, mais próximo da solução)') plt.grid(True, alpha=0.3) plt.axhline(y=1e-6, color='r', linestyle='--', label='Critério θ = 1e-6') plt.legend() # Gráfico 2: Função Valor visual plt.subplot(1, 2, 2) V_mapa = V_otimo.reshape(4, 4) mask = ambiente.grid == 1 V_mapa_masked = np.ma.masked_where(mask, V_mapa) im = plt.imshow(V_mapa_masked, cmap='RdYlGn', interpolation='nearest', vmin=0, vmax=10) plt.colorbar(im, label='Valor V*(s)') for i in range(4): for j in range(4): s = i * 4 + j if ambiente.grid[i, j] == 1: plt.text(j, i, '██', ha='center', va='center', fontsize=16, color='gray') elif s == ambiente.objetivo: plt.text(j, i, '🎯', ha='center', va='center', fontsize=16) else: cor = 'white' if V_mapa[i, j] < 5 else 'black' plt.text(j, i, f'{V_mapa[i, j]:.1f}', ha='center', va='center', fontsize=10, color=cor, fontweight='bold') plt.title('Função Valor Ótima V*(s)\n(verde = mais valioso)') plt.xlabel('Coluna') plt.ylabel('Linha') plt.tight_layout() plt.show() # ============================================ # COMPARAÇÃO COM DIFERENTES GAMMAS # ============================================ print("\n" + "=" * 70) print("COMPARAÇÃO DE HIPERPARÂMETROS: DIFERENTES γ") print("=" * 70) gammas = [0.5, 0.9, 0.95, 0.99] valores_iniciais = [] for gamma in gammas: V, _, _ = iteracao_valor(ambiente, gamma=gamma, theta=1e-4, max_iter=200) valores_iniciais.append(V[ambiente.inicio]) print(f"γ = {gamma}: V(início) = {V[ambiente.inicio]:.2f}") print("\n📊 Interpretação:") print(" - γ baixo (0.5): agente é 'míope' (valoriza recompensas imediatas)") print(" - γ alto (0.99): agente planeja longo prazo (valoriza futuro)") # ============================================ # EXPLICAÇÃO MATEMÁTICA # ============================================ print("\n" + "=" * 70) print("FUNDAMENTOS MATEMÁTICOS") print("=" * 70) print(""" ✅ EQUAÇÕES FUNDAMENTAIS: 1. EQUAÇÃO DE BELLMAN PARA V*: [latex] V^*(s) = \max_a \sum_{s',r} p(s',r|s,a) [r + \gamma V^*(s')] [/latex] 2. ITERAÇÃO DE VALOR (atualização): [latex] V_{k+1}(s) = \max_a \sum_{s',r} p(s',r|s,a) [r + \gamma V_k(s')] [/latex] 3. POLÍTICA ÓTIMA EXTRAÍDA: [latex] \pi^*(s) = \arg\max_a \sum_{s',r} p(s',r|s,a) [r + \gamma V^*(s')] [/latex] ✅ PROPRIEDADES DA PROGRAMAÇÃO DINÂMICA: • Convergência garantida para V* • Complexidade O(|S|² × |A|) por iteração • Método de PLANEJAMENTO (modelo do ambiente é conhecido) • Base teórica para algoritmos modernos ✅ HIPERPARÂMETROS CRÍTICOS: • γ (gamma): Fator de desconto (0 a 1) • θ (theta): Critério de convergência (ex: 1e-6) • max_iter: Número máximo de iterações """) print("\n" + "=" * 70) print("CONCLUSÃO") print("=" * 70) print(""" ✅ A programação dinâmica resolve problemas baseados em valor de forma exata. ✅ Ela requer conhecimento completo do modelo do ambiente. ✅ Iteração de valor é simples e converge monotonicamente. ✅ A política ótima é extraída diretamente da função valor. ✅ Este método é a base teórica do aprendizado por reforço moderno. """) print("\n✅ PROGRAMA CONCLUÍDO COM SUCESSO!") |