Q-learning

Q-learning adalah algoritma pembelajaran tanpa model yang bersifat off-policy, yaitu mempelajari fungsi nilai aksi optimal $Q^*(s,a)$ tanpa peduli kebijakan perilaku yang dipakai untuk mengeksplorasi. Topik ini memaparkan aturan pembaruannya, menjalankannya pada FrozenLake-v1 versi tidak licin selama 2000 episode, lalu membaca return rata-rata dan beberapa nilai $Q$ yang dihasilkan. Setelah membaca, diharapkan pembaca memahami mengapa pembaruan Q-learning memakai $\max_{a'} Q(s',a')$ sebagai target dan bagaimana agen tabular belajar dari sampel pengalaman.

Aturan pembaruan off-policy#

Inti Q-learning adalah pembaruan yang mengarahkan $Q(s,a)$ menuju estimasi nilai optimal. Setelah agen melakukan transisi $(s,a,r,s')$, pembaruan dilakukan dengan aturan

Target pembaruan adalah $r + \gamma \max_{a'} Q(s',a')$, yaitu reward satu langkah ditambah estimasi terbaik yang dapat diperoleh dari state berikutnya. Penggunaan $\max_{a'}$ membuat target memperkirakan kebijakan optimal di state $s'$, terlepas dari kebijakan yang sebenarnya dipakai agen untuk memilih aksi perilaku. Inilah yang menjadikan Q-learning bersifat off-policy: kebijakan target (optimal) berbeda dari kebijakan perilaku (epsilon-greedy yang dipakai untuk eksplorasi).

Karena target selalu mengarah ke aksi terbaik berikutnya, $Q$ yang dipelajari konvergen menuju $Q^*$ selama setiap pasangan $(s,a)$ dikunjungi cukup sering. Syarat ini disebut eksplorasi yang memadai, dan biasanya dipenuhi dengan epsilon-greedy yang menjaga $\epsilon > 0$. Setelah $Q$ konvergen, kebijakan optimal diperoleh dengan memilih $a = \arg\max_a Q(s,a)$ di setiap state.

Implementasi tabular pada FrozenLake#

Blok berikut adalah berkas q_learning.py yang utuh dan dapat dijalankan. Berkas ini menjalankan Q-learning tabular pada FrozenLake-v1 dengan is_slippery=False dan peta 4x4 selama 2000 episode. Aksi perilaku dipilih dengan epsilon-greedy $\varepsilon=0{,}1$, sementara pembaruan memakai target $\max_{a'} Q(s',a')$. Setelah selesai, dicetak return rata-rata 100 episode terakhir dan nilai $Q$ pada tiga state kunci, yaitu state awal 0, state 14 yang berada tepat di sebelah kiri goal, dan state 15 yang merupakan goal terminal.

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

np.random.seed(0)

env = gym.make("FrozenLake-v1", is_slippery=False, map_name="4x4")
nS, nA = env.observation_space.n, env.action_space.n

alpha = 0.1
gamma = 0.99
epsilon = 0.1
n_episodes = 2000
max_steps = 100

Q = np.zeros((nS, nA))
rng = np.random.default_rng(0)
env.action_space.seed(0)

returns_window = []

for ep in range(n_episodes):
    obs, _ = env.reset(seed=0)
    G = 0.0
    for _ in range(max_steps):
        if rng.random() < epsilon:
            a = int(rng.integers(nA))
        else:
            maxq = np.max(Q[obs])
            cand = np.flatnonzero(Q[obs] == maxq)
            a = int(rng.choice(cand))
        ns, r, term, trunc, _ = env.step(a)
        best_next = 0.0 if (term or trunc) else np.max(Q[ns])
        Q[obs, a] += alpha * (r + gamma * best_next - Q[obs, a])
        G += r
        obs = ns
        if term or trunc:
            break
    returns_window.append(G)

avg_last100 = float(np.mean(returns_window[-100:]))
print(f"avg_return (100 episode terakhir) = {avg_last100:.4f}")
print(f"Q[0]  = {np.array2string(Q[0], precision=4)}")
print(f"Q[14] = {np.array2string(Q[14], precision=4)}")
print(f"Q[15] = {np.array2string(Q[15], precision=4)}")

avg_return (100 episode terakhir) = 0.9400
Q[0]  = [0.9409 0.951  0.9057 0.9372]
Q[14] = [0.9495 0.9887 1.     0.9706]
Q[15] = [0. 0. 0. 0.]

Return rata-rata 100 episode terakhir mencapai 0.9400, yang berarti agen menyelesaikan jalur menuju goal pada sebagian besar episode terbaru. Pada state 14, aksi 2 (kanan) memiliki nilai $Q \approx 1{,}0$, sesuai dengan fakta bahwa dari state 14 bergerak ke kanan langsung mencapai goal dengan reward 1. Nilai-nilai lain pada state 0 berada di sekitar 0.94 hingga 0.95, yaitu reward maksimum 1 yang terdiskon sesuai jumlah langkah menuju goal. State 15 adalah goal terminal sehingga seluruh $Q$ bernilai nol karena tidak ada transisi keluar.

Membaca pembaruan sebagai gerak menuju optimal#

Setiap pembaruan Q-learning menggeser $Q(s,a)$ ke arah target $r + \gamma \max_{a'} Q(s',a')$. Pada langkah awal, seluruh $Q$ bernilai nol sehingga target hanya berupa reward segera, yaitu 0 untuk seluruh transisi kecuali yang mencapai goal. Setelah satu transisi ke goal terjadi, nilai $Q$ pada state sebelumnya mulai naik, lalu naiknya nilai ini menarik state yang lebih jauh pada pembaruan berikutnya. Mekanisme ini disebut propagasi reward, dan menjelaskan mengapa Q-learning tabular memerlukan cukup banyak episode agar nilai benar-benar menyebar dari goal ke seluruh state.

Kesalahan umum#

Tidak mengenolkan target pada state terminal. Penyebabnya, pembaruan ditulis seragam sebagai $r + \gamma \max_{a'} Q(s',a')$ tanpa memeriksa apakah $s'$ terminal. Akibatnya, nilai $Q$ pada state sebelum goal terus didorong oleh estimasi $Q$ goal yang tidak pernah turun, sehingga agen salah menilai kebijakan optimal. Perbaikannya, tetapkan target menjadi $r$ saja bila transisi berakhir pada state terminal.

Memakai $\alpha$ konstan terlalu besar pada akhir pelatihan. Penyebabnya, $\alpha=0{,}5$ atau lebih terlihat mempercepat belajar pada awal. Akibatnya, $Q$ terus berosilasi di sekitar nilai optimal dan tidak pernah benar-benar stabil. Perbaikannya, gunakan $\alpha$ kecil seperti $0{,}1$, atau jadwalkan $\alpha$ yang menurun seiring jumlah kunjungan pasangan $(s,a)$ bertambah.

Ringkasan#

• Q-learning bersifat off-policy: target pembaruannya adalah $r + \gamma \max_{a'} Q(s',a')$, yaitu estimasi kebijakan optimal, terlepas dari kebijakan perilaku yang dipakai untuk eksplorasi.
• Aturan pembaruan adalah $Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$, dan konvergensi menuju $Q^*$ memerlukan eksplorasi yang memadai.
• Pada FrozenLake 4x4 tidak licin dengan 2000 episode, return rata-rata 100 episode terakhir mencapai 0.9400, dan $Q(14, \text{kanan}) \approx 1{,}0$ sesuai transisi langsung ke goal.
• Reward berpropagasi dari goal menuju state yang lebih jauh melalui pembaruan bertahap, sehingga jumlah episode yang cukup menjadi syarat nilai $Q$ benar-benar menyebar.

Referensi#

• Reinforcement Learning: An Introduction (2nd ed.), ch. 6 — Sutton & Barto — Bab “Q-learning: Off-policy TD Control” memperkenalkan aturan pembaruan dan sifat off-policy-nya.
• FrozenLake — Gymnasium documentation — Definisi lingkungan FrozenLake, peta 4x4, dan opsi is_slippery.