Policy Iteration — Evaluate-Improve চক্র
এই পাঠে যা শিখবেন
- Policy evaluation — দেওয়া policy-র $V$ compute
- Policy improvement — greedy step
- Policy iteration vs value iteration — কখন কোনটি
- GPI — RL-এর mother pattern
১ · Policy Iteration-এর মূল ধারণা
Value iteration $V^*$ directly compute করে। Policy iteration আলাদা strategy — দু'টি phase:
- Evaluation: বর্তমান policy $\pi$-এর $V^\pi$ compute।
- Improvement: $\pi'(s) = \arg\max_a \sum_{s'} P(s'|s,a) [R + \gamma V^\pi(s')]$।
Repeat until $\pi$ পরিবর্তন হয় না।
যদি $\pi'$ greedy w.r.t. $V^\pi$ — তবে $V^{\pi'}(s) \ge V^\pi(s)$ ∀$s$। সমান হলে — $\pi$ optimal।
২ · Policy Evaluation — closed-form
$V^\pi$ Bellman expectation থেকে — linear equation:
$$V^\pi = R^\pi + \gamma P^\pi V^\pi \implies V^\pi = (I - \gamma P^\pi)^{-1} R^\pi$$
Matrix invert — $O(|S|^3)$। বা iterative — Bellman backup until convergence।
৩ · Iterative policy evaluation
Direct invert এড়ানোর জন্য:
$$V_{k+1}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R + \gamma V_k(s')]$$
Convergence guarantee — Bellman expectation operator $T^\pi$ also $\gamma$-contraction।
৪ · Greedy improvement step
$V^\pi$ পেলে — improved policy:
$$\pi'(s) = \arg\max_a Q^\pi(s, a) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V^\pi(s')]$$
সূক্ষ্ম point: $\pi'$ ≠ $\pi$ হলে — $V^{\pi'} > V^\pi$ অন্তত এক state-এ। তাই improvement strict (যদি optimal নয়)।
৫ · Algorithm-এর full pseudocode
Initialize: $\pi_0$ arbitrary (e.g., always action 0)।
For $k = 0, 1, \ldots$:
- $V \gets V^{\pi_k}$ (iterative evaluation)।
- $\pi_{k+1}(s) \gets \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V(s')]$।
- If $\pi_{k+1} = \pi_k$: stop, $\pi^* = \pi_k$।
Convergence: finite MDP-এ at most $|A|^{|S|}$ iteration (since each iter strict improve)। Practice-এ একটি অসুস্পষ্ট দ্রুত convergence — সাধারণত ~$|S|$ iteration।
৬ · Python implementation
import numpy as np
# 4x4 GridWorld (same as L08)
N, gamma = 4, 0.9
goal = (0, 3)
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)
return s_next, 10.0 if s_next == goal else -1.0
def evaluate(policy, V, theta=1e-5):
while True:
delta = 0
for r in range(N):
for c in range(N):
s = (r, c)
if s == goal: continue
v = V[s]
a = policy[s]
s_next, reward = step(s, a)
V[s] = reward + (0 if s_next == goal else gamma * V[s_next])
delta = max(delta, abs(v - V[s]))
if delta < theta: break
return V
def improve(V):
policy = {}
for r in range(N):
for c in range(N):
s = (r, c)
if s == goal:
policy[s] = -1; continue
best, best_a = -np.inf, 0
for a in range(4):
s_next, reward = step(s, a)
v = reward + (0 if s_next == goal else gamma * V[s_next])
if v > best: best, best_a = v, a
policy[s] = best_a
return policy
# Initialize: random policy
policy = {(r, c): 0 for r in range(N) for c in range(N)}
policy[goal] = -1
V = {(r, c): 0.0 for r in range(N) for c in range(N)}
for it in range(20):
V = evaluate(policy, V)
new_policy = improve(V)
if new_policy == policy:
print(f"Converged at iteration {it+1}")
break
policy = new_policy
# Display
arrows = ['↑', '↓', '←', '→']
for r in range(N):
print(' '.join(' G ' if policy[(r,c)]==-1 else f' {arrows[policy[(r,c)]]} ' for c in range(N)))৭ · Modified policy iteration
Full evaluation expensive। Modified PI — partial evaluation (k Bellman backup) — তারপর improvement:
# k = 1 হলে — Value Iteration!
# k = ∞ হলে — full Policy Iteration
# k = 5-10 — sweet spot, প্রায়ই দ্রুত
def modified_pi(k_eval=5):
policy = {(r, c): 0 for r in range(N) for c in range(N)}
policy[goal] = -1
V = {(r, c): 0.0 for r in range(N) for c in range(N)}
for _ in range(50):
# Partial evaluation — k Bellman backup
for _ in range(k_eval):
for r in range(N):
for c in range(N):
s = (r, c)
if s == goal: continue
a = policy[s]
s_next, reward = step(s, a)
V[s] = reward + (0 if s_next == goal else gamma * V[s_next])
new_policy = improve(V)
if new_policy == policy: return policy, V
policy = new_policy
return policy, V
p, v = modified_pi(k_eval=3)
print("Modified PI converged.")৮ · Generalized Policy Iteration (GPI)
Sutton-Barto-র মূল insight — almost সব RL algorithm-ই GPI-এর variant:
- Q-learning: single TD update + greedy improvement।
- SARSA: single TD update + ε-greedy improvement।
- DQN: stochastic gradient TD + greedy improvement।
- Actor-Critic: critic = evaluation, actor = improvement (gradient-based)।
- PPO: approximate evaluation (advantage estimate) + clipped improvement।
পার্থক্য — কত sample দিয়ে কতটা evaluation, কী form-এ improvement।
৯ · Practical considerations
- Stochastic environment: $V^\pi$ true mean, expectations exact।
- Function approximation: "policy" = parameters। improvement = gradient step।
- Continuous action: argmax computational — Gaussian policy বা actor net।
- Sample-based: P, R unknown — Q-learning replaces।
ভাবনার প্রশ্ন
প্র ০১ Policy improvement theorem-এর intuitive proof কী?
Theorem: $\pi'$ greedy w.r.t. $V^\pi$ → $V^{\pi'} \ge V^\pi$।
Intuition: $\pi'$ এক step better choose করে — তারপর $\pi$ চালিয়ে যায়। এক step better choose কখনোই খারাপ result দেবে না।
Formal: এক step swap করে দেখাই:
$V^\pi(s) \le Q^\pi(s, \pi'(s))$ — greedy বেশি বা সমান।
$= \mathbb{E}_{\pi'}[r + \gamma V^\pi(s')]$
$\le \mathbb{E}_{\pi'}[r + \gamma Q^\pi(s', \pi'(s'))]$ — recursive।
সরিয়ে চললে — $V^\pi(s) \le V^{\pi'}(s)$।
সমান হলে: $V^\pi(s) = \max_a Q^\pi(s, a)$ — Bellman optimality satisfied — $\pi$ already optimal।
প্র ০২ VI ও PI-এর actual time-complexity comparison?
Per-iteration:
- VI: $O(|S|^2 |A|)$ — Bellman optimality backup।
- PI: $O(|S|^3)$ (matrix invert) বা $O(|S|^2 / (1-\gamma))$ (iterative eval) + $O(|S|^2 |A|)$ improvement।
Iterations to converge:
- VI: $O(\log(1/\epsilon)/(1-\gamma))$।
- PI: $O(|S|/(1-\gamma) \cdot \log(1/\epsilon))$ worst-case, but usually much fewer ($O(\log |S|)$ empirically)।
Total:
- VI: $O(|S|^2 |A| \log(1/\epsilon)/(1-\gamma))$।
- PI: $O(|S|^3 \cdot |S|)$ worst-case — $O(|S|^4)$।
Practical: small/medium MDP-এ PI দ্রুত (fewer total operations)। Large MDP-এ VI memory-friendly।
প্র ০৩ Policy improvement ties-এ কী হয়? deterministic vs stochastic improvement?
$\arg\max_a Q^\pi(s, a)$-এ ties সম্ভব। সমাধান:
- Arbitrary tie-breaking: first action। deterministic policy retain।
- Random tie-break: uniform among ties। stochastic policy।
- Maintain previous: যদি previous $\pi(s)$ ties-এ থাকে — keep। convergence detection-এ helpful।
Theory: ties-এ সব choice optimal — তাই whichever। কিন্তু:
- Symmetric problem-এ — random tie-break preferable (no bias)।
- Numerical noise — float comparison সমান নয়, $|Q_1 - Q_2| < \epsilon$ check।
Stochastic gradient version: softmax-based — ties → near-equal probability। smooth।
প্র ০৪ Self-play (AlphaGo) — কীভাবে এটি GPI-এর version?
AlphaGo Zero training একটি deep GPI:
Setup:
- Neural net policy $\pi_\theta$ ও value $V_\theta$।
- MCTS (Monte Carlo Tree Search) — improvement operator।
Cycle:
- Self-play: current $\pi_\theta$ দিয়ে games। MCTS each move enhance policy।
- Evaluation (implicit): game outcomes — V_θ-এর target।
- Improvement: neural net train: $\pi_\theta$ → MCTS visit count distribution। $V_\theta$ → game outcome।
মূল insight: MCTS-এর output (visit-count policy) — current $\pi_\theta$-এর চেয়ে strictly better। নিজেকে train করিয়ে — gradient step in policy space।
Why it works:
- MCTS = "amplification" of current policy। বার বার এই amplify-distill cycle — exponential improvement।
- আস্তে আস্তে — random play থেকে superhuman।
মূল উপলব্ধি: AlphaGo ২৫০০ ELO performance — unsophisticated GPI + heavy compute। RL-এর elegance।
অনুশীলন
-
VI vs PI: ১,০০০ states, $\gamma=0.95$। VI vs PI — কোনটি দ্রুত? estimate।
VI: ~$\log(0.001)/\log(0.95) \approx 134$ sweep × 10K backup ≈ ১.৩M ops।
PI: ~$|S|/(1-\gamma) = 20$ iter × ($10^9$ matrix invert বা $10^6$ iterative eval) ≈ ২০M-২০B।
VI দ্রুত মাঝারি size-এ। PI memory-নির্ভর।
-
Modify code: উপরের PI-এ "step penalty" -1 → -0.1 করলে policy কীভাবে বদলাবে?
কম penalty — agent কম তাড়াহুড়ো করবে। safer route possible (e.g., obstacle থেকে দূরে route)। সরাসরি shortest path থেকে slightly diversion সম্ভব stochastic env-এ।
-
GPI উদাহরণ: Q-learning কীভাবে evaluation ও improvement দু'টোই এক step-এ করে?
$Q(s,a) \leftarrow Q + \alpha [r + \gamma \max_{a'} Q(s', a') - Q]$।
$r + \gamma \max Q(s', \cdot)$ — Bellman optimality target (improvement embedded)। update — evaluation step।
তাই Q-learning evaluate ও improve simultaneously — single backup-এ। বহু classical algorithm-এর elegance।
আরও পড়ুন
- পাঠ ১০ · Monte Carlo methods পরবর্তী পাঠModel-free sample-based evaluation।
- পাঠ ০৮ · Value Iteration আগের পাঠDP-এর প্রথম algorithm।
- পাঠ ১৮ · Actor-Critic এই পাঠের সাথে সম্পর্কিতGPI deep RL-এ।
- সব AI Courses ABCL TECHPython, ML, DL, NLP, CV, GenAI, RL — সব একসাথে।