🎮 Reinforcement Learning: Q-Learning

Belajar dari coba-coba dan reward — tanpa dataset label. Cara AI bermain game & mengontrol robot.

🎬 Animasi: Q-Learning: Eksplorasi → Eksploitasi

Awalnya agen coba-coba acak (eksplorasi, Q-table terisi). Setelah belajar, ia mengikuti jalur terbaik (eksploitasi).

📌 1. Konsep: Agen, Lingkungan, Reward

          ┌──────────────┐
  aksi →  │              │ → observasi (state)
          │  LINGKUNGAN  │
  reward ←│  (game/dunia)│ ←
          └──────────────┘
                ↑        ↓
              └── AGEN ──┘

Loop:
1. Agen melihat STATE (posisi di grid)
2. Agen memilih AKSI (atas/bawah/kiri/kanan)
3. Lingkungan pindah ke state baru + beri REWARD
4. Agen memperbarui pengetahuannya, ulangi

Tidak ada dataset! Tidak ada label!
Agen belajar dari CONSEQUENCE (akibat) dari tindakannya.

Q-LEARNING: agen menyimpan tabel Q[state][aksi] =
"seberapa baik aksi ini di state ini (reward total jangka panjang)".

Update (Bellman equation):
    Q(s,a) ← Q(s,a) + lr · [ r + γ·max Q(s') − Q(s,a) ]
                    └──────────────────────────────┘
              "keheranan" (TD error): selisih antara yang
              diharapkan vs yang benar-benar terjadi

ε-greedy: dengan probabilitas ε pilih aksi ACAK (explorasi),
          selain itu pilih aksi terbaik di tabel (eksploitasi).
          ε diturunkan seiring waktu (awal banyak coba, akhir fokus).

📌 2. Contoh: Grid World 5×5 — Belajar Jalan ke Goal

print("=== Q-LEARNING: GRID WORLD 5x5 ===\n")
random_seed(42)
SIZE = 5
START = (0, 0)
GOAL = (4, 4)
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # atas, bawah, kiri, kanan

# Tabel Q: tiap state punya 4 nilai (satu per aksi)
Q = {}
for i in range(SIZE):
    for j in range(SIZE):
        Q[(i, j)] = [0.0] * 4

def step(s, a):
    ti, tj = s[0] + ACTIONS[a][0], s[1] + ACTIONS[a][1]
    ni, nj = clip(ti, 0, SIZE - 1), clip(tj, 0, SIZE - 1)
    ns = (ni, nj)
    hit_wall = (ni, nj) != (ti, tj)
    if ns == GOAL:
        r = 1.0          # sampai goal: reward besar
    elif hit_wall:
        r = -0.5         # nabrak dinding
    else:
        r = -0.1         # biaya per langkah (supaya cepat)
    return ns, r

lr = 0.2
gamma = 0.9
episodes = 300
for ep in range(episodes):
    s = START
    eps = max(0.05, 1.0 - ep / 200)      # ε decay: 1.0 → 0.05
    for _ in range(100):                 # maks 100 langkah/episode
        if rand() < eps:                 # EXPLORASI
            a = randint(0, 3)
        else:                            # EKSPLOITASI
            a = argmax(Q[s])
        ns, r = step(s, a)
        Q[s][a] += lr * (r + gamma * max(Q[ns]) - Q[s][a])
        s = ns
        if s == GOAL:
            break

# ── Ekstrak jalur terbaik (selalu greedy) ──
s = START
path = [s]
for _ in range(50):
    if s == GOAL:
        break
    a = argmax(Q[s])
    s, _ = step(s, a)
    path.append(s)

print("Jalur yang dipelajari (%d langkah, minimum = 8):" % (len(path) - 1))
for i in range(SIZE - 1, -1, -1):
    row = ""
    for j in range(SIZE):
        if (i, j) == START:
            row += "S "
        elif (i, j) == GOAL:
            row += "G "
        elif (i, j) in path:
            row += "* "
        else:
            row += ". "
    print("  " + row)

print("\nContoh isi tabel Q di start %s:" % (START,))
for a, name in enumerate(["atas", "bawah", "kiri", "kanan"]):
    print("  Q(start, %-6s) = %+.2f" % (name, Q[START][a]))
print("→ Aksi dengan Q tertinggi = arah yang akan dipilih agen.")

Output:

Coba ubah episodes = 300 menjadi 50 — jalurnya jadi tidak optimal (belum cukup belajar).

📌 3. Contoh: Efek Hyperparameter RL

Ukur "efisiensi": rata-rata panjang episode (semakin pendek = semakin cepat belajar).

print("=== EFEK HYPERPARAMETER Q-LEARNING ===\n")
random_seed(42)
SIZE = 5
START = (0, 0)
GOAL = (4, 4)
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def train_and_measure(lr, episodes, seed=42):
    random_seed(seed)
    Q = {(i, j): [0.0] * 4 for i in range(SIZE) for j in range(SIZE)}
    def step(s, a):
        ti, tj = s[0] + ACTIONS[a][0], s[1] + ACTIONS[a][1]
        ns = (clip(ti, 0, SIZE - 1), clip(tj, 0, SIZE - 1))
        hit = ns != (ti, tj)
        r = 1.0 if ns == GOAL else (-0.5 if hit else -0.1)
        return ns, r
    lengths = []
    for ep in range(episodes):
        s = START
        eps = max(0.05, 1.0 - ep / (episodes * 0.7))
        length = 0
        for _ in range(100):
            a = randint(0, 3) if rand() < eps else argmax(Q[s])
            ns, r = step(s, a)
            Q[s][a] += lr * (r + 0.9 * max(Q[ns]) - Q[s][a])
            s = ns
            length += 1
            if s == GOAL:
                break
        lengths.append(length)
    # rata-rata 20 episode terakhir (setelah "belajar")
    tail = sum(lengths[-20:]) / 20.0
    return tail

print("lr    │ rata-rata panjang episode (20 terakhir)")
print("-" * 48)
for lr in [0.05, 0.2, 0.5, 0.9]:
    tail = train_and_measure(lr, 300)
    print("%.2f  │   %5.1f langkah   (optimal = 8)" % (lr, tail))

print("""
Interpretasi:
• lr terlalu kecil → tabel Q lambat terisi, masih banyak jalan memutar
• lr terlalu besar → Q bergejolak (over-react ke reward terakhir)
• lr sedang (0.2-0.5) → konvergen ke jalur optimal paling stabil""")

Output:

💡 Q-learning dengan tabel hanya untuk state diskret kecil. Untuk state besar (gambar, posisi kontinu) tabel diganti neural network → Deep Q-Network (DQN), yang mengalahkan manusia di Atari dan (bersama varian policy-based-nya) menjadi dasar AlphaGo.

🧠 Latihan

Tambahkan "lubang" di (2,2) dengan reward -1. Apakah jalur yang dipelajari menghindari lubang?
Ubah reward per langkah dari -0.1 menjadi 0. Apakah agen masih belajar jalur cepat? Kenapa? (Petunjuk: tanpa biaya, semua jalur sama enak.)
Set eps selalu 1.0 (selalu acak). Apakah Q-table masih terisi dengan benar? (Petunjuk: exploration murni.)
Jelaskan trade-off eksplorasi-eksploitasi dengan analogi: restoran baru vs restoran langganan.