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

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

Bellman সমীকরণ — RL-এর হৃদয়

Bellman equations — the recursive heart of all RL algorithms

৮ মিনিট পড়া উচ্চ · Advanced Math-heavy

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

Bellman equation কীভাবে infinite sum-কে recursive form-এ রূপান্তর করে
Bellman expectation বনাম Bellman optimality
Bellman operator ও contraction mapping — কেন convergence নিশ্চিত
একটি tabular MDP-এ iterative Bellman update

১ · Bellman-এর সরল insight

১৯৫০-এর দশকে Richard Bellman একটি অত্যন্ত elegant observation করেন — যেকোনো sequential decision problem-এর "value" recursive। আজকে যা পাচ্ছি + কালকের value × discount = মোট value।

গাণিতিকভাবে — return $G_t$:

$$G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \ldots = r_{t+1} + \gamma G_{t+1}$$

এই pattern value function-এও:

$$V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s] = \mathbb{E}_\pi[r_{t+1} + \gamma V^\pi(s_{t+1}) \mid s_t = s]$$

২ · Bellman expectation equation — full form

Stochastic policy ও stochastic environment-এ — সব expectation expand করলে:

$$V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) \big[ R(s,a,s') + \gamma V^\pi(s') \big]$$

এবং Q-form:

$$Q^\pi(s, a) = \sum_{s'} P(s'|s,a) \big[ R(s,a,s') + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s', a') \big]$$

কেন এত গুরুত্বপূর্ণ

Infinite sum $\sum_{k=0}^\infty \gamma^k r_{t+k+1}$ — সরাসরি compute করা যায় না (অনেক sample লাগে)। কিন্তু Bellman recursion — একটি linear equation system। $|\mathcal{S}|$ unknown, $|\mathcal{S}|$ equation। সরাসরি solve করা যায়।

৩ · Bellman optimality equation

Optimal policy $\pi^*$ — প্রতিটি state-এ best action। তাই:

$$V^*(s) = \max_a \sum_{s'} P(s'|s,a) \big[ R(s,a,s') + \gamma V^*(s') \big]$$

$$Q^*(s, a) = \sum_{s'} P(s'|s,a) \big[ R(s,a,s') + \gamma \max_{a'} Q^*(s', a') \big]$$

লক্ষ্য করুন: max operator এই equation non-linear করে। linear সমাধান নয় — iterative solution লাগে।

৪ · Bellman operator $T$

Bellman expectation-কে operator হিসেবে লেখা যায়:

$$(T^\pi V)(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)[R + \gamma V(s')]$$

$V^\pi$ = এই operator-এর fixed point: $T^\pi V^\pi = V^\pi$।

Optimality operator:

$$(T^* V)(s) = \max_a \sum_{s'} P(s'|s,a)[R + \gamma V(s')]$$

৫ · Contraction — কেন iteration converge করে

Banach Fixed-Point Theorem: যদি $T$ একটি contraction হয় (i.e., $\|T x - T y\| \le \alpha \|x - y\|$ for $\alpha < 1$) — তবে $T$-এর unique fixed point আছে এবং যেকোনো initial guess থেকে iteration converge করে।

Bellman operator-এর জন্য — $\sup$-norm-এ contraction factor = $\gamma$:

$$\|T V_1 - T V_2\|_\infty \le \gamma \|V_1 - V_2\|_\infty$$

এর প্রমাণ মূলত expectation-এর monotonicity ও $\gamma$-discount থেকে আসে। এই property-ই value iteration ও Q-learning-এর convergence guarantee।

$\gamma = 1$ হলে contraction না — convergence guarantee নেই। তাই episodic task-এ terminal absorbing state বা $\gamma < 1$ আবশ্যক।

Bellman backup — state-এর value সম্ভাব্য action ও next state-এর weighted combination। RL-এর সব algorithm এই backup-এর variant।

৬ · Iterative policy evaluation

$V^\pi$ compute করার সরল algorithm:

$V_0(s) = 0$ — সব state-এ initialize।
প্রতিটি iteration $k$-এ — সব state-এ Bellman backup:

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

$\|V_{k+1} - V_k\|_\infty < \epsilon$ পর্যন্ত repeat।

Contraction-এর জন্য — convergence guaranteed। এই algorithm-ই Policy Iteration-এর "evaluation" step।

৭ · Python-এ iterative policy evaluation

Python · Iterative policy evaluation

import numpy as np

# একটি ৪-state chain MDP
# state 3 = terminal, reward
# action: 0=left, 1=right (deterministic)
n_states, n_actions = 4, 2
gamma = 0.9

# Transition: T[s][a] = next_state
T = {
    0: {0: 0, 1: 1},
    1: {0: 0, 1: 2},
    2: {0: 1, 1: 3},
    3: {0: 3, 1: 3},  # terminal absorbing
}
# Reward: R[s][a][s']
def R(s, a, s_next):
    if s_next == 3 and s != 3: return 10.0
    return 0.0

# Random policy: 50-50
policy = lambda s, a: 0.5

# Iterative evaluation
V = np.zeros(n_states)
for it in range(200):
    V_new = np.zeros_like(V)
    for s in range(n_states):
        if s == 3: continue
        for a in range(n_actions):
            s_next = T[s][a]
            r = R(s, a, s_next)
            V_new[s] += policy(s, a) * (r + gamma * V[s_next])
    if np.max(np.abs(V_new - V)) < 1e-6:
        print(f"Converged at iteration {it}")
        break
    V = V_new

print("V^π =", V)
# state 2 (terminal-এর কাছে) — উচ্চতম value

Random policy-এর under — terminal-এর কাছে value বেশি। iteration-এর সংখ্যা contraction factor $\gamma$-এর উপর নির্ভর — $\gamma$ যত বড়, তত বেশি iteration।

৮ · Bellman optimality দিয়ে value iteration

Python · Value iteration (preview)

# উপরের MDP-এ optimal V*
V_star = np.zeros(n_states)
for it in range(200):
    V_new = np.zeros_like(V_star)
    for s in range(n_states):
        if s == 3: continue
        # max over actions — Bellman optimality
        V_new[s] = max(
            R(s, a, T[s][a]) + gamma * V_star[T[s][a]]
            for a in range(n_actions)
        )
    if np.max(np.abs(V_new - V_star)) < 1e-6:
        break
    V_star = V_new

print("V* =", V_star)
# Optimal policy
for s in range(3):
    best_a = max(range(n_actions),
                 key=lambda a: R(s, a, T[s][a]) + gamma * V_star[T[s][a]])
    print(f"  π*({s}) = action {best_a}")

$V^*$ — random policy-এর $V$-এর চেয়ে বেশি (optimal বলেই)। optimal policy "always right" — সরাসরি terminal-এ। এটাই পরের পাঠের value iteration-এর preview।

৯ · কেন Bellman সবকিছুর মূল

Value iteration: Bellman optimality iteratively apply।
Policy iteration: Bellman expectation দিয়ে evaluate, greedy-improve।
Q-learning: Bellman optimality-এর sample-based version।
TD learning: Bellman backup, single sample।
DQN: Bellman optimality, neural net function approximator।
Actor-Critic: Critic Bellman expectation শেখে, actor policy gradient।

Bellman সমীকরণ ভালোভাবে না বুঝলে — RL-এর কোনো algorithm-ই বুঝতে পারবেন না। প্রয়োজনে এই পাঠে ফিরে আসুন।

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

প্র ০১ Bellman expectation linear, optimality non-linear। এই difference algorithm choice-এ কীভাবে প্রভাব ফেলে?

এই difference RL-এর সব algorithm design-এ central:

Linear (expectation) Bellman:

$V^\pi$ একটি linear equation system — closed-form solve সম্ভব ($V = (I - \gamma P^\pi)^{-1} R^\pi$)।
Iteration-ও দ্রুত converge।
কিন্তু — $\pi$-নির্ভর। different policy → different $V$।

Non-linear (optimality) Bellman:

$V^*$ — max operator-এর জন্য non-linear।
Closed-form নেই। iterative-ই উপায়।
কিন্তু — directly optimal policy দেয়।

Algorithm design:

Policy Iteration: two-step — evaluate (linear) তারপর improve (max)। প্রতিটি step efficient।
Value Iteration: one-step — Bellman optimality directly। সরল কিন্তু slower।
Q-learning: sample-based optimality।

Practical: ছোট MDP-এ policy iteration faster (matrix invert করে)। বড় MDP-এ value iteration বা Q-learning।

প্র ০২ Contraction factor $\gamma$ যত ১-এর কাছাকাছি — iteration তত slow। কেন?

Iteration error প্রতি step-এ $\gamma$ factor দিয়ে কমে:

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

$\epsilon$-accuracy পেতে — $k = O(\log(1/\epsilon) / \log(1/\gamma))$ iteration।

সংখ্যাত্মক:

$\gamma = 0.5$: ১০ iteration-এ error $\approx 10^{-3}$।
$\gamma = 0.9$: ৫০ iteration-এ একই accuracy।
$\gamma = 0.99$: ৫০০ iteration।
$\gamma = 0.999$: ৫০০০ iteration।

কেন এত sensitive:

$\gamma$ বড় হলে — far-future reward propagate করতে অনেক step লাগে।
Effective horizon $1/(1-\gamma)$ — $\gamma = 0.99$-এ ১০০ steps-এর information consider।

সমাধান:

Multi-step bootstrap (TD(λ), n-step return) — $\gamma$ effective কমায়।
Prioritized sweeping — important state-এ আগে update।
Linear programming formulation — exact solve, কিন্তু large MDP-এ slow।

প্র ০৩ Function approximation (neural net) ব্যবহার করলে contraction guarantee থাকে কি?

Tabular Bellman একটি contraction। কিন্তু neural net approximator যোগ করলে — প্রায়ই না। এটি "deadly triad"-এর কারণ:

Deadly triad (Sutton):

Function approximation
Bootstrapping (Bellman target)
Off-policy learning

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

কেন: neural net update এক state-এ shift করলে — অন্য state-এও shift করে (parameter sharing)। সেটা বার বার Bellman backup-কে drift করায়।

Practice-এর সমাধান:

Target networks (DQN): backup target আলাদা slow-update network থেকে। contraction approximate করে।
Replay buffer: data correlation কমায়, IID sampling।
Gradient clipping।
Smaller learning rate।
Soft updates ($\tau$): $\theta_{target} \leftarrow \tau \theta + (1-\tau) \theta_{target}$।

Theoretical guarantees: linear approximation-এ ($V = \theta^T \phi$) — Tsitsiklis-Van Roy (১৯৯৭) on-policy convergence proved। off-policy-তে diverge উদাহরণ আছে। Non-linear (NN)-এ open problem।

প্র ০৪ Bellman residual = $V(s) - T V(s)$। এই residual minimize করা কি Bellman fixed point খোঁজার সমান?

Bellman residual minimize:

$$\min_\theta \sum_s (V_\theta(s) - T V_\theta(s))^2$$

fixed-point-এ — residual = 0। কিন্তু gradient-based minimization সবসময় fixed point দেয় না — কারণ:

$T V_\theta$ নিজেই $\theta$-এ depend করে। sample-based gradient biased।
"Double sampling" সমস্যা: $\mathbb{E}[(r + \gamma V(s'))^2] \ne (\mathbb{E}[r + \gamma V(s')])^2$।

সমাধান — semi-gradient (Sutton):

$T V$-কে fixed target ধরে gradient নেওয়া। এটি correct gradient না, কিন্তু practice-এ stable।
DQN-এ target network-এর role এটা।
Convergence guarantee সীমিত — কিন্তু empirically works।

True residual gradient: দু'টি independent sample দরকার — costly। তাই practice-এ semi-gradient।

মূল উপলব্ধি: Bellman fixed point খোঁজা = residual = 0 খোঁজা। কিন্তু gradient method bias-প্রবণ — তাই trick (target net, replay) লাগে।

অনুশীলন

Manual Bellman: chain MDP $s_1 \to s_2$ (terminal +১০)। deterministic policy "go right"। $\gamma = 0.9$। $V(s_1)$ কত?

$V(s_2) = 0$ (terminal)। action right থেকে $r=10$ — $V(s_1) = 10 + 0.9 \cdot 0 = 10$।

(Reward terminal-এ enter করার সময় — তাই terminal value 0 ধরে নিই)
Iteration count: $\gamma = 0.95$ ও initial error 100। ১০⁻⁴ accuracy পেতে কত iteration?

$\gamma^k \cdot 100 \le 10^{-4} \Rightarrow k \ge \log(10^{-6}) / \log(0.95) \approx 269$ iteration।
Bellman ভাঙা: non-Markov environment (সর্বশেষ ৩ state remember দরকার) — Bellman সরাসরি apply করলে কী ভুল?

$V(s)$ ill-defined — কারণ একই state-এ ভিন্ন history থেকে এলে ভিন্ন expected return। Bellman update inconsistent value দেয়। সমাধান: state augment (last 3 observation), বা RNN-based value function।