SARSA

Pembelajaran on-policy dan kontrasnya pada kasus cliff-walking.

Daftar isi

SARSA adalah algoritma temporal-difference on-policy yang memperbarui $Q(s,a)$ dengan aksi berikutnya yang benar-benar dipilih oleh kebijakan saat ini, alih-alih aksi terbaik menurut estimasi. Topik ini menurunkan rumus pembaruan SARSA dari persamaan Bellman ekspektasi, membandingkannya dengan Q-learning, lalu menjalankan keduanya pada lingkungan cliff-walking 4x12. Pembaca akan melihat bagaimana perbedaan satu baris rumus menghasilkan dua kebijakan yang sangat berbeda: Q-learning berjalan di tepi jurang, sedangkan SARSA memilih jalur yang lebih aman.

Pembaruan on-policy#

Estimasi $Q^\pi(s,a)$ untuk sebuah kebijakan $\pi$ memenuhi persamaan Bellman ekspektasi, yaitu nilai sebuah pasangan state-aksi sama dengan expected reward satu langkah ditambah nilai ekspektasi pasangan berikutnya yang ditimbang kebijakan. Pada SARSA, ekspektasi itu diperkirakan dengan satu sampel: pasangan $(s', a')$ di mana $a'$ benar-benar dipilih oleh $\pi$ saat berinteraksi. Pembaruannya menjadi

Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma Q(s',a') - Q(s,a) \right],

dengan $a' \sim \pi(\cdot \mid s')$ . Karena $a'$ diambil dari kebijakan yang sama yang menghasilkan $a$ , SARSA bersifat on-policy, yaitu target pembaruan konsisten dengan perilaku yang sebenarnya dijalankan. Konsekuensinya, SARSA belajar menilai kebijakan yang dipakainya, termasuk kebijakan yang masih sering mengeksplorasi.

Kontras dengan Q-learning terletak pada bagian target. Q-learning mengganti $Q(s',a')$ dengan $\max_{a'} Q(s',a')$ , sehingga target selalu mengasumsikan agen akan memilih aksi terbaik di state berikutnya tanpa memandang kebijakan sesungguhnya. Bila kebijakan sesungguhnya masih sering mengeksplorasi dengan epsilon tinggi, aksi yang dipilih bisa jadi jauh dari aksi terbaik, dan jarak antara asumsi target dengan kenyataan inilah yang membedakan perilaku kedua algoritma.

Kontras pada cliff-walking#

Berkas sarsa.py berikut menjalankan SARSA dan Q-learning pada gridworld cliff-walking 4x12 selama 150 episode, dengan $\alpha=0{,}5$ , $\gamma=1{,}0$ , dan $\epsilon=0{,}1$ . Setelah pelatihan, kebijakan serakah (greedy) dari masing-masing dirender pada papan untuk memperlihatkan jalur yang dipilih.

python sarsa.py

import warnings; warnings.filterwarnings("ignore")
import numpy as np

np.random.seed(0)

# Gridworld cliff 4x12: row 0 = lorong atas (S start kiri, G goal kanan),
# row 1..3 = region cliff. Jatuh ke cliff = terminal, reward -100.
# Aksi: 0=atas, 1=kanan, 2=bawah, 3=kiri.
n_rows, n_cols = 4, 12
n_states = n_rows * n_cols
n_actions = 4
START = 0
GOAL = n_states - 1


def step(s, a):
    r, c = divmod(s, n_cols)
    if a == 0:
        r = max(0, r - 1)
    elif a == 1:
        c = min(n_cols - 1, c + 1)
    elif a == 2:
        r = min(n_rows - 1, r + 1)
    elif a == 3:
        c = max(0, c - 1)
    ns = r * n_cols + c
    if ns == GOAL:
        return ns, 0.0, True
    if r >= 1:
        return ns, -100.0, True
    return ns, -1.0, False


def egreedy(Q, s, epsilon, rng):
    if rng.random() < epsilon:
        return int(rng.integers(n_actions))
    maxq = np.max(Q[s])
    cand = np.flatnonzero(Q[s] == maxq)
    return int(rng.choice(cand))


def run(algo, n_episodes=150, alpha=0.5, gamma=1.0, epsilon=0.1):
    rng = np.random.default_rng(0)
    Q = np.zeros((n_states, n_actions))
    returns = []
    max_steps = 500
    for ep in range(n_episodes):
        s = START
        a = egreedy(Q, s, epsilon, rng)
        G = 0.0
        for _ in range(max_steps):
            ns, r, term = step(s, a)
            if algo == "q":
                target = r + (0.0 if term else gamma * np.max(Q[ns]))
                na = 0
            else:
                if term:
                    target = r
                    na = 0
                else:
                    na = egreedy(Q, ns, epsilon, rng)
                    target = r + gamma * Q[ns, na]
            Q[s, a] += alpha * (target - Q[s, a])
            G += r
            s, a = ns, na
            if term:
                break
        returns.append(G)
    return Q, returns


def greedy_path(Q):
    s = START
    path = [s]
    for _ in range(100):
        a = int(np.argmax(Q[s]))
        ns, r, term = step(s, a)
        path.append(ns)
        s = ns
        if term:
            break
    return path


Qq, Rq = run("q")
Qs, Rs = run("sarsa")

avg_q = float(np.mean(Rq[-50:]))
avg_s = float(np.mean(Rs[-50:]))
print(f"Q-learning: avg_return (50 ep terakhir) = {avg_q:.4f}")
print(f"SARSA     : avg_return (50 ep terakhir) = {avg_s:.4f}")
print(f"episode_total = {len(Rq)}")

pq = greedy_path(Qq)
ps = greedy_path(Qs)


def render_path(path):
    grid = [["." for _ in range(n_cols)] for _ in range(n_rows)]
    grid[0][0] = "S"
    grid[0][n_cols - 1] = "G"
    for rr in range(1, n_rows):
        for cc in range(1, n_cols - 1):
            grid[rr][cc] = "C"
    for s in path[1:]:
        rr, cc = divmod(s, n_cols)
        cur = grid[rr][cc]
        if cur == "G":
            grid[rr][cc] = "G"
        elif cur == "C":
            grid[rr][cc] = "X"
        else:
            grid[rr][cc] = "*"
    return grid


print()
print("Jalur Q-learning (greedy):")
for row in render_path(pq):
    print("  " + " ".join(row))

print()
print("Jalur SARSA (greedy):")
for row in render_path(ps):
    print("  " + " ".join(row))

text Keluaran

Q-learning: avg_return (50 ep terakhir) = -484.0000
SARSA     : avg_return (50 ep terakhir) = -122.9400
episode_total = 150

Jalur Q-learning (greedy):
  S * * . . . . . . . . G
  . C C C C C C C C C C .
  . C C C C C C C C C C .
  . C C C C C C C C C C .

Jalur SARSA (greedy):
  S . . . . . . . . . . G
  * C C C C C C C C C C .
  . C C C C C C C C C C .
  . C C C C C C C C C C .

Membaca dua jalur#

Perbedaan return rata-rata sangat mencolok: Q-learning mencapai -484 pada 50 episode terakhir, sedangkan SARSA mencapai -122,94. Penyebabnya terlihat pada render jalur serakah. Q-learning mempelajari jalur optimal yang menyentuh tepi atas baris cliff, sehingga kebijakan serakahnya berjalan lurus ke kanan sepanjang baris atas. Akan tetapi, kebijakan sesungguhnya selama pelatihan masih mengeksplorasi dengan $\epsilon=0{,}1$ , dan sepuluh persen langkah acak itu sering menjatuhkan agen ke jurang dengan hukuman -100, sehingga return pelatihan tetap rendah.

SARSA, sebaliknya, belajar bahwa berada di tepi atas berbahaya karena eksplorasinya sendiri dapat menjatuhkannya. Kebijakan serakah SARSA memilih naik dulu ke baris paling atas, lalu baru bergerak ke kanan, menjauhi tepi jurang. Jalur ini lebih panjang namun jauh lebih aman ketika kebijakan masih mengeksplorasi, sehingga return pelatihannya jauh lebih tinggi. Inilah inti perbedaan on-policy dan off-policy: SARSA mengoptimalkan kebijakan yang benar-benar dijalankan, sedangkan Q-learning mengoptimalkan kebijakan optimal ideal yang tidak sama dengan perilaku eksploratifnya.

Kesalahan umum#

Mengira SARSA selalu lebih aman daripada Q-learning. Penyebabnya, hasil cliff-walking digeneralisasi ke segala kasus. Akibatnya, SARSA dipakai pada lingkungan yang sebenarnya tidak sensitif terhadap eksplorasi, di mana kedua algoritma memberi hasil mirip. Perbaikannya, uji kedua algoritma pada lingkungan target dan bandingkan return pelatihan serta jalur serakah sebelum memilih.

Mengabaikan aksi berikutnya $a'$ saat menyimpan transisi. Penyebabnya, hanya pasangan $(s,a,r,s')$ yang disimpan sehingga $a'$ hilang saat pembaruan SARSA dilakukan. Akibatnya, $a'$ harus diambil ulang sebagai sampel dengan kebijakan baru, yang melanggar sifat on-policy karena aksi yang dipakai untuk target bukan aksi yang dipilih saat berinteraksi. Perbaikannya, simpan juga $a'$ dalam buffer transisi atau lakukan pembaruan sebelum melangkah ke state berikutnya.

Ringkasan#

SARSA memperbarui $Q(s,a)$ dengan target $r+\gamma Q(s',a')$ di mana $a'\sim\pi(\cdot\mid s')$ , sehingga bersifat on-policy dan menilai kebijakan yang benar-benar dijalankan.
Pada cliff-walking dengan $\epsilon=0{,}1$ , Q-learning belajar jalur tepi jurang yang berbahaya saat dieksplorasi (return -484), sedangkan SARSA belajar jalur yang menjauhi tepi (return -122,94).
Perbedaan satu baris target, $\max_{a'} Q(s',a')$ versus $Q(s',a')$ , mengubah kebijakan akhir secara dramatis ketika eksplorasi memengaruhi keselamatan.

Referensi#

Reinforcement Learning: An Introduction, ch. 6 — Sutton & Barto — Bab “Temporal-Difference Learning” yang memperkenalkan SARSA dan membandingkannya dengan Q-learning pada cliff-walking.
SARSA — Wikipedia — Ringkasan rumus pembaruan SARSA dan sifat on-policy-nya.