পাঠ ১২ · ৩২-এর মধ্যে · মডিউল ২

Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / Q-learning & SARSA

Q-learning ও SARSA

Q-learning & SARSA — off-policy and on-policy TD control

৮ মিনিট পড়া উচ্চ · Advanced Python কোডসহ

এই পাঠে যা শিখবেন

Q-learning algorithm — off-policy, Bellman optimality target
SARSA algorithm — on-policy, expected next action
Cliff-walking experiment — পার্থক্য visualize
NumPy দিয়ে scratch থেকে implement

১ · TD control — V থেকে Q-এ

TD prediction (পাঠ ১১) — $V$ estimate। Control-এর জন্য $V$ যথেষ্ট না (model-free-এ action বাছা যায় না)। তাই $Q(s, a)$ estimate।

Generic TD-control update:

$$Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \cdot \text{TARGET} - Q(s, a)]$$

"TARGET"-এর choice — Q-learning vs SARSA-এর মূল পার্থক্য।

২ · Q-learning (Watkins, ১৯৮৯)

Off-policy: target = next state-এর best action-এর Q।

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \big[ r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \big]$$

Off-policy কেন

Behavior policy (ε-greedy দিয়ে data collect) ≠ target policy (greedy দিয়ে evaluate)। তাই — agent explore করে কিন্তু $Q$ optimal greedy policy-র estimate-ই শেখে।

৩ · SARSA (Rummery & Niranjan, ১৯৯৪)

On-policy: target = next state-এ actual next action $a_{t+1} \sim \pi$।

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \big[ r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \big]$$

নাম "SARSA" = (s, a, r, s', a') tuple — পাঁচটি জিনিস update-এ লাগে।

৪ · Cliff-walking — পার্থক্য visualize

Sutton-Barto-র classic experiment। 4×12 grid। নিচের সারির ১১টি cell — cliff (-100 reward, episode reset)। start বাম-নিচ, goal ডান-নিচ। প্রতি step -1।

Q-learning: "optimal" পথ — cliff-এর গা ঘেঁষে। কিন্তু ε-greedy-এর কারণে — মাঝে মাঝে cliff-এ পড়ে। average return খারাপ।
SARSA: safer পথ — cliff থেকে দূরে। average return ভাল।

Cliff walking-এ Q-learning ও SARSA-এর behavior পার্থক্য — exploration-এর সময় safety-এর প্রভাব।

৫ · Q-learning Python — full GridWorld

Python · Q-learning

import numpy as np

N = 4
goal = (0, 3)
gamma = 0.9
alpha = 0.1
epsilon = 0.1
n_episodes = 500

def step(s, a):
    r, c = s
    if a == 0: r = max(0, r-1)
    if a == 1: r = min(N-1, r+1)
    if a == 2: c = max(0, c-1)
    if a == 3: c = min(N-1, c+1)
    s_next = (r, c)
    reward = 10.0 if s_next == goal else -1.0
    done = (s_next == goal)
    return s_next, reward, done

# Q-table
Q = np.zeros((N, N, 4))
np.random.seed(0)

for ep in range(n_episodes):
    s = (3, 0)  # start
    while True:
        # ε-greedy
        if np.random.rand() < epsilon:
            a = np.random.randint(4)
        else:
            a = np.argmax(Q[s[0], s[1]])
        s_next, r, done = step(s, a)
        # Q-learning update — max over next actions
        max_next = 0 if done else np.max(Q[s_next[0], s_next[1]])
        Q[s[0], s[1], a] += alpha * (r + gamma * max_next - Q[s[0], s[1], a])
        if done: break
        s = s_next

# Greedy policy
arrows = ['↑', '↓', '←', '→']
for r in range(N):
    print(' '.join(' G ' if (r,c)==goal else f' {arrows[np.argmax(Q[r,c])]} ' for c in range(N)))

৫০০ episode-এ — Q-learning shortest path খুঁজে বের করেছে। এটাই pure model-free RL — পরিবেশের কোনো model নেই, শুধু interaction।

৬ · SARSA Python

Python · SARSA

Q = np.zeros((N, N, 4))
np.random.seed(0)

def eps_greedy(s, eps):
    if np.random.rand() < eps:
        return np.random.randint(4)
    return np.argmax(Q[s[0], s[1]])

for ep in range(n_episodes):
    s = (3, 0)
    a = eps_greedy(s, epsilon)
    while True:
        s_next, r, done = step(s, a)
        if done:
            target = r
        else:
            a_next = eps_greedy(s_next, epsilon)  # SARSA's actual a'
            target = r + gamma * Q[s_next[0], s_next[1], a_next]
        Q[s[0], s[1], a] += alpha * (target - Q[s[0], s[1], a])
        if done: break
        s, a = s_next, a_next

print("SARSA learned Q-table")

SARSA Q-learning-এর চেয়ে slightly different policy শিখে — exploration-aware। GridWorld-এ পার্থক্য সামান্য, কিন্তু cliff-walking-এ স্পষ্ট।

৭ · Convergence conditions

Q-learning convergence (Watkins, 1992):

সব $(s, a)$ infinitely often visited।
$\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$ (Robbins-Monro)।
Tabular finite MDP।

$\Rightarrow Q \to Q^*$ with probability 1।

SARSA convergence: additional — policy GLIE (Greedy in the Limit with Infinite Exploration) — যেমন decaying ε। তবে $Q \to Q^*$।

৮ · Expected SARSA

Variance reduction — actual $a'$-এর জায়গায় expectation:

$$\text{target} = r + \gamma \sum_{a'} \pi(a' | s') Q(s', a')$$

Variance কম, performance ভাল। তবে computation $|A|$ গুণ। Atari-এ লেগে এসেছে।

৯ · Q-learning কোথায় ব্যবহার

Tabular control problems (educational, small games)।
Deep extension — DQN (Atari, gaming)।
Recommendation system — limited action space।
Self-driving (planning component)।

Function approximation-এ Q-learning unstable হতে পারে — "deadly triad"। DQN-এর target net + replay-এর জন্ম এই কারণেই।

ভাবনার প্রশ্ন

প্র ০১Off-policy ও on-policy — গভীরে কী মানে?

On-policy: data collect করে যে policy — সেই policy-র Q (বা V) শিখা।

Off-policy: data collect করে behavior policy $b$, কিন্তু target policy $\pi$ ($\ne b$)-এর Q শিখা।

Q-learning: behavior = ε-greedy, target = greedy। তাই off-policy।

SARSA: behavior = target = same ε-greedy। on-policy।

পরিণাম:

Off-policy advantage: replay buffer ব্যবহার করা যায় (DQN-এ central)। Old data reuse।
On-policy advantage: more stable. policy-data match।
Off-policy challenge: importance sampling, distribution shift।

Modern: PPO on-policy কিন্তু sample reuse trick দিয়ে। SAC off-policy + maximum entropy।

প্র ০২Maximization bias — কোথায় ও কেন?

Q-learning-এর update target $r + \gamma \max_{a'} Q(s', a')$ — max operator bias আনে।

Why: $\mathbb{E}[\max(X_1, X_2)] \ge \max(\mathbb{E}[X_1], \mathbb{E}[X_2])$ (Jensen's inequality)। Q noisy estimate হলে — max consistently overestimate।

Example: ১০টি action সবার true Q=0। কিন্তু noisy estimate ±1। max ≈ +2 — non-zero।

Effect:

Slow convergence — overestimate biased target chase।
Function approximation-এ amplified।

সমাধান — Double Q-learning (Hasselt, 2010):

দু'টি Q-table — A ও B।
Update A using max of B (or vice versa)।
Bias significantly reduced।

Double DQN (পাঠ ১৫) — এই idea-এর deep version।

প্র ০৩SARSA-কে "expected" করলে — Expected SARSA, on-policy থাকে কি?

Expected SARSA target:

$r + \gamma \mathbb{E}_{a' \sim \pi}[Q(s', a')] = r + \gamma \sum_{a'} \pi(a'|s') Q(s', a')$

On-policy যদি: $\pi$ = behavior। এই case-এ Expected SARSA ≈ SARSA but lower variance।

Off-policy ব্যবহার: $\pi$ = greedy, behavior = ε-greedy। তবে — Expected SARSA off-policy! এটা Q-learning-এর সাথে সংলগ্ন কারণ:

$\pi$ greedy হলে — $\sum \pi Q = \max Q$ — Q-learning।
$\pi$ uniform হলে — average Q।

সুতরাং: Expected SARSA on/off-policy-এর spectrum cover করে। flexible।

Empirical: Expected SARSA-এর variance lowest, performance Q-learning-এর সমান বা ভাল।

প্র ০৪Tabular Q-learning ১০M state-এ scale করে না। Function approximation-এ কী problem?

$Q_\theta(s, a)$ — neural net। Q-learning update:

$\theta \leftarrow \theta + \alpha [r + \gamma \max_{a'} Q_\theta(s', a') - Q_\theta(s, a)] \nabla_\theta Q_\theta(s, a)$

সমস্যা:

Moving target: $Q_\theta(s', a')$ also $\theta$-নির্ভর। target shift।
Correlated samples: consecutive transition similar — i.i.d. break।
Catastrophic forgetting: new region update পুরাতন region-এর Q নষ্ট।
Maximization bias amplified: generalization across (s,a) — overestimate spread।

"Deadly triad":

Function approximation
Bootstrapping (Bellman target)
Off-policy

এই তিনটি একসাথে — divergence সম্ভব।

DQN-এর fixes (পাঠ ১৩, ১৪):

Target network (slow copy of $Q_\theta$ for target)।
Replay buffer (decorrelate samples)।
Double Q-learning (max bias)।

অনুশীলন

Update manual: $Q(s,a)=2$, $r=1$, $Q(s', \cdot) = [3, 5, 4]$, $\gamma=0.9, \alpha=0.1$। Q-learning update?

$\max Q(s', \cdot) = 5$। Target = $1 + 0.9 \cdot 5 = 5.5$। $Q \leftarrow 2 + 0.1 \cdot (5.5 - 2) = 2.35$।
SARSA vs Q-learning: উপরের same state, কিন্তু actual $a' = 0$ (Q=3, not max)। SARSA update?

Target = $1 + 0.9 \cdot 3 = 3.7$। $Q \leftarrow 2 + 0.1 \cdot (3.7 - 2) = 2.17$।

SARSA conservative — Q-learning overestimate বেশি।
Code modify: উপরের Q-learning-এ ε-greedy-এর জায়গায় Boltzmann softmax exploration ব্যবহার করুন।
```
def boltzmann(s, tau=0.5):
    q = Q[s[0], s[1]]
    p = np.exp(q / tau) / np.sum(np.exp(q / tau))
    return np.random.choice(4, p=p)
```
τ tuning critical — too small mostly greedy, too large mostly random।