Fundamentos y Algoritmos de Aprendizaje por Refuerzo: Desde Q-Learning hasta PPO

Aprendizaje x refuerzo:

Agente aprende x prueba y error. Cd instante observa estado dl entorno, ejecuta acción, recibe recompnsa y actualiza xa mjor polític contrl xa maximizar la recmpensa acumulada.
Observación lo q miden los sensores estado: 
representación que usa algoritmo para decidir. Ej: LiDAR mide muchs dstncias; el estdo puede ser el cluster de K-medias asignado a esa lectura.

Markov

Estado debe contener suficiente info para que el futuro dependa slo dl estdo y acción actual, no d td el historial. P(st+1∣st,at)2 situacions distints caen en mismo estdo pro requieren acciones distintas, la represent no cumple bn Markov.

Política pi:

regla que usa el agnte xa actuar.

D

Π(s)=aEπ(s,a)=P(a∣s)

Ó

Π^*||V(s)
valora lo bueno q es estar S Q(s,a)
valora lo buena q es un par S-A.

Bellman:

valor act=recomp inmediata+ valor fut- Q-learn: Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)

On-policy

Aprende ev = política q usa xa actuar (SARSA)

Off policy:

≠(Q-learn)

Explotr:

usar lo q ya sé, elegir acción q parece mejor.

Explorr:

probr accions nuevs xa descubrir si algna va mejr.

Greedy:

elige siempre la mejor acción conocida. a=arg ⁡max⁡aQ(s,a)

Ε-greedy:

elige la mejor acción con probabilidad ϵ explora aleatorio.

Boltzmann:

Da + probab a acciones con ↑ valor, pero no descarta completamnte las otras. Usa Tª T. Tª ↑ → + exploración. Tª ↓ → ≈ greedy.

K-medias:

algorit d clustering q agrupa observcions parecidas en K clusters. Cd cluster (grupo de observaciones parecidas) queda represntdo x un centroide, y en nuestro caso cd cluster puede usarse cm un S discreto xa aplicar aprendizaje x refuerzo tabular. (lectura LiDAR)↔ Pasos: 1.
Elegir K 
2. Inicializar K centroids(lectura media representativa de un cluster)

3

Asignar cada observación al centroide + cercano.

4

Recalcular centroides cm media de sus puntos.

5

Repetir hasta que casi no cambien.

Voronoi:

Cada centroide define una regíón de Voronoi: los puntos + cercanos a ese centroide Regíón convexa:
2 ptos están dentro de la regíón, el segmento entre ellos tb queda dentro.

Densidad p(x)

Dnd aparecen + observaciones. K-medias tiende a poner más centroides donde hay + datos.

Error cuantificación:

Distancia/error entre una observación real y el centroide que la representa. Relación:+ K → regiones + peq → ↓ error d cuant → + s → aprendizaje + complejo.

K peq:

Pocos S, aprendizaje + simple, pero mzcla situacions distints.

K grande:

S + precisos, - error, pero tabla Q + grande y + lenta.

K-M y Markov:

El problema no es slo q el cluster sea geométricamente cohrente. Tiene q ser útil xa decidir.X eso si un mismo cluster mezcla situaciones que requieren acciones distintas, Q-learning ve el mismo S xa cass distintos y la propiedad de Markov falla. Cmprobación: Recojo transicions reales. Xa un mismo S y A, miro si las recompensas y siguientes S consistentes. Adecuado: =S +=A → consecuencias ≈. Alarma: =cluster + =A → recompensas muy≠.

Q-learning es un algorit d aprendizaje x refuerzo basado en valors q aprende una tabla/funcn Q(s,a) dnd cd valr indica lo buena q es una acción en un S. Es off-policy pq aprnde usndo el máx valr dl sig S, aunq durnte el entrno pueda actuar cn 1a polític exploratoria ϵ-greedy, pero al actualiz aprende cm si en el fut fuera a escger siempr la mejr acció, ese máx represnt polític greedy. Q(s,a)←Q(s,a)+α[r+γ maxa'Q(s',a')-Q(s,a)] α:
Learning rate. Dice cuánto cambio el valor con la nueva experiencia|| r:recompensa inmediata recibida ||γ:
Factor de descuento. Dice cuánto peso doy al futuro|| maxa'Q(s',a'):
Mejor valor posible en el sig S.

Q-L s puede usar en entornos estocásticos:

No necesita conocer explícitamente P(s'|s,a) Aprende a partir de muestras reales: (s,a,r,s') Si prueba muchas veces una A en un S, va aproximando el valor esperado de esa A.
Exploración excesiva en Q-L Explorar es necesario, pero una exploración demasiado agresiva puede retrasar la convergencia y hacer que los valores Q sean menos fiables. (aprende +lento, ejecuta ↑ accions aleatorias, recomp ↓, tarda + en estabilizar politic,↑ sobreest d valores Q x el uso del máximo Q-L Taxi es adecuado pq tiene S(posición taxi, posic pasajero, destino)y A(N,S,E,O, recoger, dejar) discretas. Recomp: dejar bien. Penalizaciónx paso, x recoger/dejar mal. Evaluación: recompensa media,% éxito, nº medio de pasos,distints posic inici.

Q-L seguir paredes 1

Leo LiDAR, 2
K-medias para convertir lectura en S discreto 3
Defino A discretas 4
Defino recompensa 5
Entreno tabla Q(s,a)|| ¿S?: Cd K de K-M, ¿A?: Izq, Der, Avanzar, Stop, Retroc|| Recomp+: No choca, distanc cn pared/ -:choca, muy cerca o lejos de pared Aprend superv + Q-L
Si tengo ej de un aprend sup (S, A) puedo usarlos xa ayudr al aprend. Formas de usarlo:inicializar cn + valor Q(s,a) las accions dl superv, añadir recomp auxiliar si el agnte imita al superv, etiquetr S cm seguros, peligross/ambiguos. Cuidado:El superv puede equivocarse o no ser óptimo x eso no dbe sustituir completamnt a la recomp real SARSA (S, A, Recomp, sig S, sig A): algoritmo de aprendiz x refuerzo basado en valores que aprende Q(s,a) = que Q-learning, pero es on-policy. Actualiz cn acción real sig, aprende el valr d actuar cn la polític real, incluyndo explorac. : Q(s,a)← Q(s,a)+α[r+ γ Q(s',a')-Q(s,a)]cambiar Q-L x SARSA
No basta con slo la fórm, hace falta ajustar: ϵ, decay de ϵ, α, nº d episodios, polític explorac. TbSARSA depnde d la política real q sigue. Si explora demasiado, aprende teniendo en cuenta esa exploración.
Trazas de elegibilidad son una memoria temporal d ls S o pares S-A visitados recientmnt, q permite repartir el error de aprendizaje hacia pasos ant.Sirven cnd la recomp (mérito/culpa) import llega tarde (ej Taxi)
λ controla cuánto duran ls trazas, hasta q pto el error actual afecta a pasos pasados. :
λ=0 apens se propaga hacia atrás, se parece a aprendiz d un paso.
λ=1se propaga + hacia S oA ant.
λ ↑ puede acelerar el aprend, pero tb hacerlo + inestable Accumulating traces
Cada vez q se visita un S-A, su traza aumenta (Ventaja: refuerza mucho S visitads repetidamnt|Problema:cpuede crecr mucho y ser inestabl)

Replacing traces

Cnd s visita un S-A, su traza se pone a 1/ s reemplaza. (Ventaja:evita q crezca sin control, suele ser + estable)
Trazas off-policy se puede cortar la traza al explorar xa no propgar el error x una trayect q no represent la polític greedy obj

DQN

Deep Q-Network, es 1a versión d Q-L en la q la tabla Q se sustituye x 1a red neuronal. La red recibe el S como entrda y devuelve un valor Q xa cd acción posible ¿Pq aparece DQN?
Q-L funciona bn si hay pocos S discretos, pero si el S es cont/muy grnde, la tabla Q deja de sr viable.Ej: CartPole el S es: pos, v, áng y v angulr. Cm sn valors reals, no puedo tenr 1a fila d la tabla xa cd posible S Entrada y salida DQN
La red recibe el S y devuelve un Q-valor x A, NO directamnt la A DQN y A discretas
DQN sirve bien para estados continuos, pero normalmente necesita acciones discretas x maxa'Q(s',a') Xa calcular ese máx necesito poder comparar ls A posibles. Si son cont, habría ∞ A y DQN no encaja directamnt Actualización en DQN
Se guarda una experiencia y en el S actual entreno la A ejecutada, en el sig S miro la mejor A futura.

Replay buffer (experience replay)

memoria q guarda experiencias pasadas (s,a,r,s',done) Luego entrena cn minibatches aleatorios d esa memoria. sirve para estabilizr el entreno, rompiendo la estabilización temp q se forma mezclando experiencias antg y nuev i.I.D.
indpndints e idénticamnt distribuidas. En Red neur las muestras seguidas no son i.I.D. El replay permite reutilizar experiencis y entrenar cn muestras + variadas y - correlacionadas.
Red target estabiliza DQN pq calcula el obj Bellman(target = r+γ maxa' Q_target(s',a') cn 1a red q cambia + lentamnt. 

Cuándo aprende DQN

Durante entreno, normalmnt empieza a actualizar pesos cnd el replay buffer ya tiene sufic experiencias ϵ-greedy en DQN
Durante entreno, al principio interesa explorar + (ϵ ↑ al principio favorece exploración). Dps interesa explotar más (ϵ ↓ al final favorece usar la política aprendida)

Hiperparámetros import en DQN

Principales:
lr (v de aprendiz), γ (peso futur) ,ϵ start (explor inic), ϵ end (explor final), ϵ decay (ritmo d bajda)

Grid search

Probar varis comb d hiperpará y escoger la mejor Early stopping:
Parar 1a config si deja d mejorar Successive halving
Probar muchas config con pco entreno, eliminar ls peores y seguir entrenando slo ls mejores Checkpoint
Guardar el mejor modelo encontrado. El mejor checkpoint puede ser mejor q el modelo final, pq al seguir entrenando puede empeorar Gradient clipping ayuda a estabilizr el entreno evitando saltos bruscos en la red.
DDQN, Double Deep Q-Network, es una variante d DQN q reduce la sobreestimción d ls valors Q separndo la selección d la A y la evaluación d esa A Problema DQN usa un máx y si los valors tienen ruido, el máx puede escogr valors demasiado optimistas(sobreestimar). DDQN la red policy elige la A y la red target la evalúa.
Prioritized Experience Replay es 1a variante dl replay buffer en la q no tds ls experiencias se muestrean con = probabilidad. Se da + prioridad a las experiencias con ↑ error TD. Ventaja:Puede acelerar el aprendizaje Problema: Introduce sesgo, porque ya no se muestrea d forma uniforme y cm correción se usan pess d importance sampling.

MLP red neuronal formada x capas lineals.

Cálculo d parámetros

Linear(in,out) →pesos: in x out → bias: out→ total in x out +outCNN se usa cnd el S tiene estruct espacial, ej: img/mapa Cálculo d parámetros
Xa convolución: Conv2d(in_channels,out_channels,kernel, stride, padding)↔

Fórmula del tamaño de salida→Para calcular el alto/ancho de salida: out=((input-kernel+2* padding)/(stride))+1

→Ejemplo 1 — Sin padding →Entrada: 3 x 8 x 8

nn.Conv2d(3, 2, kernel_size=3, stride=1, padding=0

salida: out=(8-3+2*0}/{1}  +1   → out=6

Como out_channels = 2, la salida es:2 x 6 x 6

Parámetros de la convolución→2 * 3 * 3 * 3 + 2→54+2=56 parámetros

REINFORCE es 1 algorit d gradiente d política. Aprende directamente 1a política ↑ la prob d ls A q han dado buenos retornos y reduciendo la d ls A q han dado malos retornos. Si actualizo en dirección + xa una A (a_j): pi(s_1,a_j) aumenta. Ls demás probab aumenta.Las demás probabilidades: pi(s_1,a_k), k≠ j tienden a bajar, pq las probab deben sumar 1. Si actualizo en sentido -, pasa al revés: baja la probab d (a_j)

Problema

Si tds ls retornos son + o tds son -, el algoritm no distingue bn q A fueron realmente mejores o peores. Por eso aparece el baseline/advantage
Advantage mide si una A fue mejor o peor de lo esperado en ese S A(s,a)=Q(s,a)-V(s). Si la A fue mejor d lo esperado → subo su probab. Si A fue peor → bajo probab Actor-Critic es una familia de algoritm dnd el actor aprende la política y el critic evalúa cm d buenos sn ls S o A, ayudando a calcular el advantage.
Actor decide la A Critic evalúa el S o la A. 
Actor-Critic discreto / A2C se usa cuando las acciones posibles son pocas y separadas.Ej:
CartPole( el agente solo puede hacer A 0: empujar a la izq; A 1: empujar der) . El actor debería devolver probabilidades: pi(a|s)el actor devuelve logits
Nº sin normalizar.→q se convierten en una distribuc Categorical representa una distribución de probabilidad para acciones discretas. Con ella puedo hacer tres cosas importantes: elegir una A durante el entreno. Calcular la pérdida del actor. Medir exploración. criticEl critic recibe el estado y devuelve V(s), es decir, Qué retorno espera obtener desde ese estado.

Qué es el advantage en A2C

El advantage compara lo que pasó realmente con lo que esperaba el critic. Si: A_t>0 mejor de lo esperado, entonces el actor debe aumentar la probabilidad de esa A. Si: A_t<0 A fue peor de lo esperado entonces el actor debe reducir la probabilidad de esa A. Buffer de trayectoria En A2C no se usa un replay buffer grande como DQN. Se usa un buffer de trayectoria, que guarda lo que acaba de pasar con la política actual. (state (estado observado), action (A ejecutada), reward (recompensa recib),log_prob(porbab d A ejec), valúe (valor Vs), done si terminó)Loss del actor cambia la probabilidad de la A ejecutada según el advantage: si fue mejor de lo esperado, la sube; si fue peor, la baja Loss del critic aprende comparando el valor que predijo con el retorno real o estimadoEntropía La entropía mide si la política está muy segura o todavía explora. Si es alta, la política reparte probabilidad entre varias acciones.Si es baja, la política casi siempre elige la misma A. Se usa para evitar que el actor se vuelva determinista demasiado pronto. DDPG tb es Actor-Critic para acciones continuas, pero con una diferencia importante: El actor no es estocástico, es determinista, devuelve directamente una A continua y un critic que valora pares S-A. DDPG y relación con DQN DDPG es como llevar ideas de DQN al control continuo mediante un actor determinista. Loss del critic en DDPG El critic de DDPG aprende a estimar (Q(s,a)) comparando su predicción con un target de Bellman.Loss del actor en DDPG se entrena para producir acciones que maximicen el valor (Q) dado por el critic Autograd en DDPG Autograd permite que el critic guíe al actor, indicando cómo modificar la A para aumentar (Q)

PO Proximal Policy Optimization algorit tipo Actor-Critic q mejora la estabilidad limitando cuánto puede cambiar la política en cd actualiz.Política vieja y política nuevaEn PPO hay dos políticas: pi_old (la q generó los datos), pi_theta(la q estoy enetrenndo)Ratio de probabi: comxa la política nueva cn la vieja: r_t(theta)=pi_theta(a_t|s_t)/pi_old(a_t|s_t) ↔Interpretación: (r_t=1): la A tiene la misma probab;(r_t>1): la A ahora es más probable; (r_t<1): la A ahora es menos probable. Pq se usan log-probabilidades?
En código normalmente se calcula así: r_t=exp(log pi_new - log pi_old) Se hace cn log pq las probab pueden ser muy peq y dividirlas directamnt puede ser inestable. Qué se guarda en PPO?
En cada paso se guarda: (s_t): estado observado; (a_t): A ejecutada; (r_t): recompensa; done si terminó el episodio;(log\ pi_old): xa calcular el ratio;(V(s_t)): xa calcular retornos y ventajas. Importance samplingPPO quiere usar datos generados por pi_old xa entrenar pi_theta. Función surrogate cn clipping PPO deja mejorar la política, pero corta cambios demasiado grandes mediante clipping Por qué se usa el mínimo?
Pq actúa como un freno pesimista: aunq una actualización parezca muy buena, PPO no deja q la política cambie demasiado Intuición cn advantage positivo o negativo Si: A_t>0 →la A fue mejor de lo esperado, qremos aumentar su probabilidad. Pero si el ratio sube demasiado, PPO lo recorta. Si: A_t<0 la A fue peor de lo esperado. Qremos reducir su probabilidad. Pero si el ratio baja demasiado, PPO también lo recorta. Pérdida total de PPO PPO combina pérdida de política cn clipping, pérdida del critic y entropía. GAE Generalized Advantage Estimation, es un método xa estimar el advantage combinando errores TD de varios pasos, buscando equilibrio entre sesgo y varianza. Primero se define el TD residual: δ_t=r_t+γ  V(s_t+1)-V(s_t) Luego GAE calcula: A_t^{GAE}=\sum_{k=0}^{\infty}(γ λ)^k * δ_{t+k}.
λ=0 ↓ varianza, +sesgo λ=1 + varianza, -sesgo Episodio de 4 ciclos El enunciado plantea(s_0 →{r0} s_1, s_1 →{r1} s_2 , s_2 →{r2} s_3, s_3 →{r3} FIN)Resultado:
 Estimación a 1 paso: Q^(1)=r_0+γ  V(s_1)| a 2 pasos Q^(2)=r_0+γ  r_1+γ^2 V(s_2)| a 3 pasos Q^(3)=r_0+γ r_1+γ^2 r_2+γ^3V(s_3) a 4 pasos / Monte Carló Q^(4)=r_0+γ  r_1+γ ^2r_2+γ ^3r_3 Advantage a partir del retorno advantage compara lo q acabó pasando cn lo q el critic esperaba xa ese estado.Qué mejora PPO respecto a Actor-CriticPPO mejora Actor-Critic porq permite actualizar la política de forma más estable, evitando q la política nueva se aleje demasiado de la anterior. PPO paso a paso 1.Inicializo actor/política y critic. 2Recojo trayectorias cn la política actual. 3 Guardo: s_t,a_t,r_t,done,log pi_old,V(s_t) 4Calculo returns. 5Calculo ventajas cn GAE.6 Durante varias épocas, recalculo (log pi_new}.7 Cálculo: r_t=exp(log pi_new - log pi_old) 8Calculo (L^{CLIP}), pérdida del critic y entropía. 9Actualizo actor y critic por gradiente.