Temporal Difference Learning

Metody TD są pomiędzy Monte Carlo Methods (RL) a Dynamic programming (RL). Charakterystyka:

• nie potrzebują modelu środowiska, są model-free, tak jak MC,
• w odróżnieniu od MC, nie czekamy tutaj na zakończenie całego epizodu, a aktualizację możemy robić po jakimś ustalonym kroku, nawet w trakcie trwania epizodu,
• robią bootstrapping, tzn. do podejmowania decyzji wykorzystuj swoje wcześniejsze predykcje, tak jak DP
• może być używany do problemów niestacjonarnych

Metody TD prediction (Policy evaluation)

Czyli znamy Policy, chcemy znaleźć Value function.

one-step TD (TD(0))

$V(S_t)\leftarrow V(S_t)+\alpha [\underset{{\delta }_t,\text{TD Error}}{\underbrace{R_{t+1}+\gamma V(S_{t+1})-V(S_t)}}]$ Zauważmy, że $(R_{t+1}+\gamma V(S_{t+1}))$ to jest wartość dla stanu $S_t$ jaką estymujemy po kroku $t$, a $V(S_t)$ to wartość jaką estymowaliśmy przed krokiem $t$, więc wyrażenie w nawiasie (TD Error) to jest błąd o który chcemy się poprawić. $\alpha$ to taki learning rate.

Batchowe TD(0)

Załóżmy, że mamy dostęp do ograniczonej liczby epizodów, np. 10. Takie epizody pokazujemy kilkukrotnie z myślą, że po jakimś czasie algorytm zbiegnie. Algorytm, w którym nie aktualizujemy wag po każdym odwiedzeniu, tylko robimy to w batchach, tzn. robimy kalkulacje zmian na bieżąco, ale aktualizujemy tylko raz na te 10 epizodów jako sumę zmian które mieliśmy wprowadzić, ale nie wprowadziliśmy.

Optymalność

Batchowe TD(0) deterministycznie zbiega do stałej dla małego $\alpha$. Uwaga: batchowe alpha-constant Monte Carlo też zbiega do stałej, ale do innej! TD(0) zbiega do wartości, które są optymalne w sensie modelu maximum-likelihood procesu Markova, tzn. że wybiera takie parametry modelu, że prawdopodobieństwo wygenerowania danych, które widzimy jest największe. Dla porównania, batchowe alpha-constant Monte Carlo jest optymalne w sensie minimalizacji mean squared error.

n-step TD (TD(n))

Analogia do one-step TD - ale tutaj ${\delta }_t$ wygląda tak: $(R_{t+1}+\gamma R_{t+2}+...+{\gamma }^{n-1}{R}_{t+n}+{\gamma }^n{V}_{t+n-1}(S_{t+n}))-V_{t+n-1}(S_t)$ czyli zbieramy dane z większej liczby akcji, żeby zaktualizować $V$.

n-step TD jest również optymalne i jest uogólnieniem metod one-step TD oraz Monte Carlo, które są po prostu ekstremalnymi przypadkami n-step TD. Ponadto najczęściej można znaleźć dla danego problemu takie $n$, z którym n-step TD jest lepsze i od on-step TD i od Monte Carlo.

Metody TD Control

Sarsa

Metoda on-policy i standardowo jest to forma Generalized policy iteration, czyli po każdym kroku aktualizujemy funkcję Q, i potem od razu używamy nowej funkcji Q w naszej polityce.

Sarsa zbiega z prawdopodobieństwem 1 do optymalnej polityki pod warunkiem, że :

1. $\alpha$ jest dobrana “odpowiednio”, zobacz Warunki na zbieżność RL
2. wszystkie pary stan-akcja są odwiedzone nieskończenie wiele razy
3. polityka zbiega do greedy polityki (to można osiągnąć poprzez na przykład epsilon-greedy politykę gdzie ustawiamy $ϵ=\frac{1}{t}$)

Wzór na aktualizację: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$ gdzie $A_{t+1}$ wybierany jest na podstawie aktualnej polityki, którą poprawiamy. Metoda jest on-policy.

Q-learning

Wzór na aktualizację: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma {\max }_{a}Q(S_{t+1},a)-Q(S_t,A_t)]$ Różnica względem Sarsa jest taka, że tutaj jest inne założenie co do akcji jaka zostanie wybrana w nowym stanie - założenie jest, że wybieramy najlepszą akcję (greedy), a nie taką, jaką powie nam polityka.

Q-learning jest znacznym ulepszeniem względem Sarsa.

Expected Sarsa

Wzór na aktualizację: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma {\sum }_a\pi (a|S_{t+1})Q(S_{t+1},a)-Q(S_t,A_t)]$ Ten algorytm zmniejsza wariancję względem zwykłego Sarsa, gdzie wybieramy kolejną akcję czasami losowo. Może być trochę bardziej kosztowny obliczeniowo niż Q-learning i Sarsa, ale będzie dominował w wynikach te dwie metody.

n-step Sarsa

Uogólnienie zwykłego algorytmu Sarsa, podobnie jak n-step TD.

Źródło: Reinforcement Learning An introduction