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

Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / Value Iteration

Value Iteration — Bellman optimality-এ সরাসরি

Value iteration — direct application of Bellman optimality

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

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

Value iteration algorithm — pseudocode থেকে full Python
GridWorld-এ value কীভাবে propagate করে — visual intuition
Convergence — when to stop
$V^*$ থেকে $\pi^*$ extract

১ · Algorithm-এর হৃদয়

Value iteration — Bellman optimality equation-কে iterative update হিসেবে use:

$$V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s, a) \big[ R(s, a, s') + \gamma V_k(s') \big]$$

Pseudocode:

$V_0(s) = 0$ ∀$s$।
প্রতিটি iteration $k$:
- প্রতি state $s$-এ — Bellman optimality apply।
- $\Delta = \max_s |V_{k+1}(s) - V_k(s)|$।
- $\Delta < \theta$ হলে stop।
Optimal policy: $\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V(s')]$।

২ · Convergence guarantee

Bellman optimality operator $T^*$ একটি $\gamma$-contraction। Banach fixed-point theorem অনুসারে — $V_k \to V^*$।

Rate: $\|V_k - V^*\|_\infty \le \gamma^k \|V_0 - V^*\|_\infty$।

Stopping criterion:

$$\|V_{k+1} - V_k\|_\infty < \frac{\theta(1-\gamma)}{2\gamma} \implies \|V_{k+1} - V^*\|_\infty < \theta$$

৩ · GridWorld-এ value কীভাবে propagate

Value iteration sweep-এ value goal থেকে wave-এর মতো ছড়ায়। প্রতিটি sweep-এ এক step গভীরে।

৪ · Python — full GridWorld value iteration

Python · Value iteration

import numpy as np

# 4x4 GridWorld
N = 4
goal = (0, 3)
gamma = 0.9
theta = 1e-6

# Action: 0=up 1=down 2=left 3=right
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

V = np.zeros((N, N))
for it in range(500):
    delta = 0
    V_new = np.copy(V)
    for r in range(N):
        for c in range(N):
            s = (r, c)
            if s == goal: continue
            best = -np.inf
            for a in range(4):
                s_next, reward, done = step(s, a)
                v = reward + (0 if done else gamma * V[s_next])
                if v > best: best = v
            V_new[r, c] = best
            delta = max(delta, abs(V_new[r, c] - V[r, c]))
    V = V_new
    if delta < theta:
        print(f"Converged at iteration {it+1}")
        break

print("\nOptimal V*:")
print(np.round(V, 2))

Goal-এ V=0 (terminal), neighbor-এ V=10 (immediate reward), এবং দূরত্বে গেলে discount-এর জন্য কম। প্রায় ২০-৩০ iteration-এ converge।

৫ · $V^$ থেকে $\pi^$ extract

Python · Greedy policy extraction

# V converged after value iteration above
arrows = ['↑', '↓', '←', '→']
policy = np.zeros((N, N), dtype=int)
for r in range(N):
    for c in range(N):
        s = (r, c)
        if s == goal:
            policy[r, c] = -1
            continue
        best_a, best_v = 0, -np.inf
        for a in range(4):
            s_next, reward, done = step(s, a)
            v = reward + (0 if done else gamma * V[s_next])
            if v > best_v:
                best_v, best_a = v, a
        policy[r, c] = best_a

print("\nOptimal policy:")
for r in range(N):
    row = ""
    for c in range(N):
        row += " G " if (r,c)==goal else f" {arrows[policy[r,c]]} "
    print(row)

প্রতিটি cell থেকে — goal-এর দিকে directly point করে। deterministic environment-এ — shortest path আবিষ্কৃত।

৬ · Stochastic environment

যদি action নয়েজ-যুক্ত — যেমন ৮০% intended direction, ১০% করে orthogonal-এ slip — algorithm কাজ করে কারণ Bellman expectation transition probability সব consider করে।

$$V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s, a) [R + \gamma V_k(s')]$$

Stochastic-এ optimal policy "noise-aware" হতে পারে — যেমন cliff থেকে দূরে থাকা যাতে slip সাবধানতা।

৭ · Synchronous vs asynchronous

Synchronous: পুরো $V_k$ থেকে $V_{k+1}$ — সব state simultaneously update। দু'টি buffer।
Asynchronous (Gauss-Seidel): in-place update — একই array-এ। প্রায়ই দ্রুত converge।
Prioritized sweeping: Bellman error বেশি যেখানে — সেখানে আগে update।

৮ · Computation cost

প্রতিটি sweep — $O(|\mathcal{S}|^2 \cdot |\mathcal{A}|)$। convergence-এর জন্য $O(\log(1/\epsilon)/\log(1/\gamma))$ sweep।

Total: $O\left(\frac{|\mathcal{S}|^2 \cdot |\mathcal{A}|}{\log(1/\gamma)} \log(1/\epsilon)\right)$।

ছোট MDP-এ instant। লক্ষ-state-এ infeasible — function approximation দরকার।

৯ · কখন value iteration ব্যবহার

$P, R$ জানা (model-based)।
State space ছোট (~10K states)।
Discrete state।
Educational baseline।

বাস্তব production-এ — DP-based methods সরাসরি কম, কিন্তু এদের ideas (Q-learning, planning, MCTS) সর্বত্র।

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

প্র ০১ Value iteration vs Policy iteration — কোনটি কখন দ্রুত?

দু'টি classical DP algorithm — আলাদা trade-off।

Value iteration:

Iteration-এ Bellman optimality (max) — non-linear।
প্রতি sweep cheap ($O(|S|^2 |A|)$)।
কিন্তু অনেক sweep লাগে ($\gamma$-নির্ভর)।

Policy iteration:

প্রতি iteration: full policy evaluation (linear system) + greedy improvement।
প্রতি step expensive কিন্তু অনেক কম iteration (~$|S|$)।
Iteration-এর সংখ্যা polynomial in $|S|, |A|$।

কখন কোনটি:

$\gamma$ small (0.5) — VI দ্রুত converge।
$\gamma$ near 1 — PI দ্রুত (fewer iter, প্রতিটি একটু বেশি কাজ)।
$|S|$ small — PI (matrix invert efficient)।
$|S|$ large — VI (avoid matrix inverse)।

Hybrid: Modified PI: partial policy evaluation (k Bellman backups) + greedy improvement। সাধারণত best of both।

প্র ০২ Function approximation-এ value iteration কি কাজ করে? কী ভাঙে?

Tabular VI guaranteed converge। কিন্তু $V_\theta(s) = $ neural net হলে — convergence guarantee নেই।

Fitted Value Iteration:

Sample state-action pairs।
Bellman target compute: $y = r + \gamma \max_{a'} V_\theta(s')$।
$\theta$ regress to $y$।
Repeat।

সমস্যা:

Target নিজেই $\theta$-এ depend — moving target।
Function approximator-এর representation error বার বার amplify।
Off-policy distribution mismatch।

সমাধান (পরের পাঠে):

Target network — slow-update copy।
Replay buffer — break correlation।
Smaller learning rate।
Regularization।

DQN আসলে fitted Q iteration + এই tricks।

প্র ০৩ $\gamma = 1$ episodic task-এ — Value iteration কাজ করে?

$\gamma = 1$-এ Bellman operator strict contraction না — কিন্তু episodic task-এ workable।

কেন কাজ করে:

Terminal state reachable everywhere — episodes finite।
$V$ bounded ($\le$ max episodic reward)।
Average-reward formulation-এর সাথে সংলগ্ন।

কী সমস্যা হতে পারে:

Cycle without reward — V infinite হতে পারে। practical-এ "absorbing terminal" বা reward সব state-এ।
Convergence rate বদলে যায় — এখন episode length-এর উপর নির্ভর।

Practical: Atari-এ $\gamma = 0.99$ used (very close to 1, কিন্তু strict contraction)। Go/Chess-এ effectively 1 with terminal +1/-1।

প্র ০৪ একটি warehouse robot — ১০,০০,০০০ unique state। Value iteration কেন infeasible?

১০M state × ৫ action — ৫০M Bellman backups প্রতি sweep। ১০০ sweep = ৫B ops। doable কিন্তু:

Memory: V-array ১০M × 8 bytes = 80MB। OK কিন্তু transition matrix?
Transition: প্রতি (s, a) থেকে possible (s')। sparse-ও — billions of entries।
Reward function — explicit specify করা impossible এত state-এ।

Practical solutions:

State abstraction: nearby state group, ১০M → ১০K।
Function approximation: $V_\theta(s)$ neural net। ১০M state → ১০K parameter।
Hierarchical RL: high-level (which warehouse zone) + low-level (movement)।
Sample-based: Q-learning, DQN — full sweep এড়ানো।
Approximate DP: Bertsekas-Tsitsiklis-এর work।

Industry reality: Amazon warehouse robot — RL + classical planning hybrid। pure DP rarely।

অনুশীলন

1-D chain: 5 state, action L/R, terminal s_4 (+10), step reward 0, $\gamma=0.9$, deterministic। $V^*(s_0)$ কত?

$V^*(s_3) = 10$ (next is terminal)। $V^*(s_2) = 0.9 \cdot 10 = 9$। $V^*(s_1) = 0.9 \cdot 9 = 8.1$। $V^*(s_0) = 0.9 \cdot 8.1 = 7.29$।
Sweep count: $\gamma=0.99$, initial error 100, target 1e-3। কত sweep?

$0.99^k \cdot 100 \le 0.001 \Rightarrow k \ge \log(10^{-5})/\log(0.99) \approx 1145$ sweeps।
Modify code: উপরের GridWorld-এ একটি obstacle (২,২) যোগ করুন (transition blocked)। policy কীভাবে adapt হয়?

step()-এ check: if next_s == (2,2) return current state (block)। policy obstacle এড়িয়ে route খুঁজবে। V map-এ obstacle-এর দিকে কম value (must detour)।