Salt la conținut

Algoritmul PPO și GAE

AvansatLectură: 4 min

Am văzut la limitările algoritmului REINFORCE că metodele bazate pe gradientul strategiei au o problemă serioasă: sunt instabile. Dacă un pas de optimizare este prea mare, noua strategie poate deveni dintr-odată catastrofală. La HalfCheetah, o astfel de actualizare îl face pe robot să se răstoarne pe spate. Odată ce robotul a căzut, toate traiectoriile următoare conțin doar eșecuri, iar algoritmul nu își mai poate reveni.

Algoritmul PPO (Proximal Policy Optimization), propus în 2017 de John Schulman și colegii săi de la OpenAI, rezolvă problema cu o idee intuitivă: limitează automat cât se poate schimba strategia la fiecare iterație.

Fie πθvechi\pi_{\theta_{\text{vechi}}} strategia cu care am colectat cele mai recente traiectorii din mediu și πθ\pi_\theta noua strategie, pe care vrem să o optimizăm. Raportul de probabilități (probability ratio) rt(θ)r_t(\theta) este probabilitatea pe care noua strategie o dă acțiunii ata_t în starea sts_t, împărțită la probabilitatea pe care i-o dădea strategia veche.

Pentru curioșiFormula raportului de probabilități

Definim raportul de probabilități rt(θ)r_t(\theta) astfel.

rt(θ)=πθ(at∣st)πθvechi(at∣st)=exp⁡(log⁡πθ(at∣st)−log⁡πθvechi(at∣st))r_t(\theta) = \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{vechi}}}(a_t \mid s_t)} = \exp\left( \log \pi_\theta(a_t \mid s_t) - \log \pi_{\theta_{\text{vechi}}}(a_t \mid s_t) \right)

La începutul fiecărui ciclu de optimizare, θ=θvechi\theta = \theta_{\text{vechi}}, deci raportul este exact rt(θ)=1r_t(\theta) = 1. Dacă noua strategie face acțiunea ata_t mai probabilă decât înainte, rt(θ)>1r_t(\theta) > 1. Dacă o face mai puțin probabilă, rt(θ)<1r_t(\theta) < 1.

Funcția obiectiv tăiată (clipped surrogate objective)

Secțiune intitulată „Funcția obiectiv tăiată (clipped surrogate objective)”

Dacă am maximiza direct produsul rt(θ)A^tr_t(\theta) \hat{A}_t, schimbările mari ale lui rt(θ)r_t(\theta) ar putea destabiliza strategia. De aceea, PPO folosește o funcție obiectiv tăiată (clipped surrogate objective), în care raportul este trunchiat la un interval în jurul lui 1, de obicei între 0,8 și 1,2. Cât timp raportul rămâne în acest interval, obiectivul este chiar produsul rt(θ)A^tr_t(\theta) \hat{A}_t. Dacă o acțiune bună devine mai probabilă sau una slabă mai puțin probabilă decât permite intervalul, obiectivul nu mai crește, așa că strategia nu câștigă nimic dacă face un pas prea mare într-o singură iterație.

Pentru curioșiFuncția obiectiv tăiată
LCLIP(θ)=E^t[min⁡(rt(θ)A^t, clip⁡(rt(θ),1−ϵ,1+ϵ)A^t)]\mathcal{L}^{CLIP}(\theta) = \hat{\mathbb{E}}_t \left[ \min\left( r_t(\theta)\hat{A}_t, \, \operatorname{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon)\hat{A}_t \right) \right]

unde ϵ\epsilon are de regulă valoarea 0,20{,}2. Operatorul clip ține raportul în intervalul [1−ϵ,1+ϵ][1-\epsilon, 1+\epsilon], adică [0,8, 1,2][0{,}8, \, 1{,}2].

Funcția min alege varianta mai pesimistă dintre obiectivul netrunchiat și cel trunchiat. Să luăm pe rând cele două cazuri, după semnul avantajului A^t\hat{A}_t:

  1. Avantaj pozitiv (A^t>0\hat{A}_t > 0): acțiunea a fost mai bună decât media. Vrem să-i creștem probabilitatea (rt>1r_t > 1). Însă dacă rt>1+ϵr_t > 1+\epsilon (adică rt>1,2r_t > 1{,}2), termenul trunchiat devine (1+ϵ)A^t(1+\epsilon)\hat{A}_t, care este mai mic decât rtA^tr_t \hat{A}_t. Funcția min alege valoarea plafonată, iar gradientul devine zero. Astfel, strategia nu mai are niciun câștig dacă face un pas prea mare într-o singură iterație.
  2. Avantaj negativ (A^t<0\hat{A}_t < 0): acțiunea a fost mai slabă decât media. Vrem să-i scădem probabilitatea (rt<1r_t < 1). Dacă rt<1−ϵr_t < 1-\epsilon (adică rt<0,8r_t < 0{,}8), termenul trunchiat devine (1−ϵ)A^t(1-\epsilon)\hat{A}_t. Cum avantajul este negativ, acest termen este mai mic decât rtA^tr_t \hat{A}_t, așa că funcția min alege acest termen, iar gradientul devine din nou zero. Strategia nu câștigă nimic dacă scade prea mult probabilitatea acțiunii într-o singură iterație.

Celula de mai jos rulează direct în browser și calculează valoarea funcției obiectiv pentru rapoarte de probabilitate între 0,50{,}5 și 1,51{,}5.

import numpy as np
epsilon = 0.2
ratios = np.array([0.5, 0.7, 0.9, 1.0, 1.1, 1.3, 1.5])
def ppo_loss(ratio, adv):
obj1 = ratio * adv
obj2 = np.clip(ratio, 1.0 - epsilon, 1.0 + epsilon) * adv
return np.minimum(obj1, obj2)
print("r_t: ", ratios)
print("-----------------------------------------------------------------")
print("Avantaj pozitiv (+1):", np.round(ppo_loss(ratios, adv=1.0), 3))
print("Obiectiv netrunchiat:", np.round(ratios * 1.0, 3))
print("-----------------------------------------------------------------")
print("Avantaj negativ (-1):", np.round(ppo_loss(ratios, adv=-1.0), 3))
print("Obiectiv netrunchiat:", np.round(ratios * -1.0, 3))

Codul poate fi modificat și rulat direct în browser (Ctrl + Enter).

Observăm că, pentru A^t=+1\hat{A}_t = +1, odată ce rtr_t depășește 1,21{,}2, obiectivul se plafonează la 1,21{,}2. Pentru A^t=−1\hat{A}_t = -1, când rtr_t scade sub 0,80{,}8, obiectivul se plafonează la −0,8-0{,}8.

Ca să știm cât de bună a fost o acțiune față de ce ne așteptam în medie în starea respectivă, avem nevoie de o estimare bună a avantajului A(st,at)A(s_t, a_t).

Cea mai simplă estimare este eroarea de diferență temporală (temporal difference, TD) la un singur pas. Această eroare compară recompensa primită la acest pas, plus valoarea estimată a stării următoare, cu valoarea estimată a stării curente.

Pentru curioșiEroarea TD la un singur pas
δtV=rt+1+γV(st+1)−V(st)\delta_t^V = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)

Are o varianță mică, dar depinde mult de cât de precis este criticul V(s)V(s). La polul opus, recompensa cumulată Monte Carlo, calculată pe toată traiectoria, este nedeplasată (unbiased), dar are o varianță foarte mare.

Estimarea generalizată a avantajului (Generalized Advantage Estimation, GAE) face o interpolare între cele două extreme, cu ajutorul unui parametru de netezire suplimentar, λ∈[0,1]\lambda \in [0, 1].

Pentru curioșiEstimarea avantajului (GAE)
A^tGAE(γ,λ)=∑l=0∞(γλ)lδt+lV=δtV+γλA^t+1GAE(γ,λ)\hat{A}_t^{GAE(\gamma, \lambda)} = \sum_{l=0}^{\infty} (\gamma \lambda)^l \delta_{t+l}^V = \delta_t^V + \gamma \lambda \hat{A}_{t+1}^{GAE(\gamma, \lambda)}
  • Când λ=0\lambda = 0, obținem eroarea TD la un singur pas, adică A^t=δtV\hat{A}_t = \delta_t^V (varianță minimă).
  • Când λ=1\lambda = 1, obținem suma Monte Carlo a recompenselor minus valoarea stării (fără deplasare).

Pentru că fiecare avantaj se obține din avantajul pasului următor, GAE se calculează foarte eficient, cu o singură trecere prin traiectorie, în ordine inversă (de la ultimul pas, T−1T-1, până la pasul 0).

Stocarea traiectoriilor și calculul avantajelor GAE se fac în clasa RolloutBuffer din fișierul buffer.py:

buffer.py
def compute_gae(
self,
next_value: torch.Tensor,
next_done: torch.Tensor,
gamma: float = 0.99,
gae_lambda: float = 0.95,
def get_generator(
self, minibatch_size: int

După calculul avantajelor, datele colectate din toate mediile paralele sunt amestecate și împărțite în mini-loturi pentru optimizarea parametrilor. Pagina despre antrenare și evaluare explică acest pas în detaliu.