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

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

Value function ও Q-function

Value functions — measuring "how good" a state is

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

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

State value function $V^\pi$ — definition ও interpretation
Action-value function $Q^\pi$ — কেন এটি RL-এ এত central
$V$ ও $Q$-এর সম্পর্ক, optimal version
একটি tabular environment-এ value computation

১ · Value function-এর intuition

একটি state কতটা "ভালো"? — এই প্রশ্নের গাণিতিক উত্তর-ই value function। state থেকে শুরু করে যদি একটি নির্দিষ্ট policy অনুসরণ করি — গড়ে কত reward পাব?

দু'টি value function

১) State value $V^\pi(s)$: state $s$ থেকে শুরু, policy $\pi$ অনুসরণ। expected return।
২) Action value $Q^\pi(s, a)$: state $s$-এ action $a$ নাও (one-step), তারপর $\pi$।

গাণিতিক রূপ:

$$V^\pi(s) = \mathbb{E}_\pi \left[ G_t \mid s_t = s \right] = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k r_{t+k+1} \mid s_t = s \right]$$

$$Q^\pi(s, a) = \mathbb{E}_\pi \left[ G_t \mid s_t = s, a_t = a \right]$$

২ · কেন $V$ ও $Q$ — দুটোই

$V(s)$ থেকে action বাছা যায় না সরাসরি — কারণ $V$ শুধু state-এর "মান" বলে, কোন action নিতে হবে বলে না। action বাছতে হলে — environment-এর dynamics ($P, R$) জানতে হবে।

$Q(s, a)$ — সরাসরি বলে দেয় action $a$ নেওয়ার "মান"। তাই dynamics না জানলেও — $\arg\max_a Q(s, a)$ থেকে action বাছা যায়। এই কারণেই Q-learning, DQN — model-free RL-এ Q এত central।

$V(s)$ = "এই অবস্থানে বসে আমি কত ভালো"। $Q(s, a)$ = "এই অবস্থান থেকে এই দরজা দিয়ে বের হলে আমি কত ভালো হব"। দরজা বাছতে — দ্বিতীয়টি দরকার।

৩ · $V$ ও $Q$-এর গাণিতিক সম্পর্ক

Stochastic policy $\pi(a|s)$-এর জন্য:

$$V^\pi(s) = \sum_a \pi(a \mid s) \cdot Q^\pi(s, a)$$

মানে — $V$ হলো $Q$-এর policy-weighted average।

আবার $Q$ থেকে $V$:

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

৪ · Optimal value functions

প্রতিটি policy-র জন্য আলাদা $V^\pi, Q^\pi$। কিন্তু একটি optimal policy $\pi^*$ আছে যা সব state-এ best — তার value function-গুলো:

$$V^*(s) = \max_\pi V^\pi(s) \quad,\quad Q^*(s, a) = \max_\pi Q^\pi(s, a)$$

এবং সরাসরি:

$$V^*(s) = \max_a Q^*(s, a) \quad,\quad \pi^*(s) = \arg\max_a Q^*(s, a)$$

$Q^*$ জানলেই $\pi^*$ পেয়ে যাই — environment-এর dynamics না জেনেও। এই insight-ই Q-learning-এর ভিত্তি।

৫ · একটি সরল GridWorld-এ $V$

প্রতিটি cell-এ value function — সেখান থেকে শুরু করে optimal policy অনুসরণে expected return। Goal-এর কাছে value বেশি, দূরে কম।

৬ · Python-এ $V$ হিসাব — Monte Carlo

Python · MC value estimation

import numpy as np

# Toy MDP: 5 state chain
# 0 -- 1 -- 2 -- 3 -- 4 (terminal, reward +1)
n_states = 5
gamma = 0.9

def episode():
    """একটি random walk থেকে শুরু করে state 4 পৌঁছানো পর্যন্ত।"""
    s = 0
    trajectory = []
    while s != 4:
        a = np.random.choice([-1, 1])  # বাম বা ডান
        next_s = max(0, min(4, s + a))
        r = 1.0 if next_s == 4 else 0.0
        trajectory.append((s, r))
        s = next_s
    return trajectory

# Monte Carlo: প্রতিটি state-এ গড় return
np.random.seed(0)
returns = {s: [] for s in range(n_states)}
for _ in range(2000):
    traj = episode()
    G = 0
    for (s, r) in reversed(traj):
        G = r + gamma * G
        returns[s].append(G)

V = {s: np.mean(returns[s]) for s in range(n_states) if returns[s]}
for s in V:
    print(f"V({s}) ≈ {V[s]:.3f}")
# state 4-এর কাছাকাছি — V বেশি; দূরে — V কম

Monte Carlo estimate — অনেক episode-এর গড় return। sample বাড়ালে — V আরও সঠিক। পরের পাঠে Bellman দিয়ে এর exact equation দেখব।

৭ · Q-function — action-এর মান

$Q(s, a)$ একটি 2-D table (discrete environment-এ)। শুরু action-নির্ভর first reward, তারপর policy অনুসরণ করে দেখা যায়।

Python · Q-table init

import numpy as np

# 4 state, 2 action
Q = np.zeros((4, 2))

# কিছু episode থেকে Q estimate (toy)
# state 0 - action 0 → return 5
# state 0 - action 1 → return 2
samples = [
    (0, 0, 5), (0, 0, 4.8), (0, 0, 5.2),
    (0, 1, 2), (0, 1, 1.9),
    (1, 0, 3), (1, 1, 6),
    (2, 0, 8), (2, 1, 4),
]
counts = np.zeros((4, 2))
for s, a, G in samples:
    counts[s, a] += 1
    # incremental average
    Q[s, a] += (G - Q[s, a]) / counts[s, a]

print("Q-table:")
print(Q)
print("\nGreedy policy (argmax):")
print(Q.argmax(axis=1))
# state 0 → action 0; state 1 → action 1; state 2 → action 0
# এটাই greedy policy from Q।

Q-table থেকে policy = argmax। এটাই Q-learning-এর core idea। আগামী পাঠগুলোতে আমরা এই Q-table কীভাবে শেখায় সেটা দেখব।

৮ · Action-value advantage

একটি concept যা বহুল ব্যবহৃত — advantageAdvantage A(s, a)"এই state-এ এই action নিলে — গড় action-এর তুলনায় কতটা ভাল"। A=0 মানে গড়ের সমান, A>0 মানে ভালো। policy gradient ও actor-critic-এ central। $A^\pi(s, a)$:

$$A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s)$$

মানে — এই action $a$ নেওয়া policy-র গড় থেকে কতটা ভাল। $A > 0$ — গড়ের চেয়ে ভাল, $A < 0$ — গড়ের চেয়ে খারাপ। variance reduction-এ অপরিহার্য।

৯ · কী আসছে — Bellman

এই পাঠে $V$ ও $Q$ define করেছি। কিন্তু infinite sum গণনা করা impractical। পরের পাঠে Bellman সমীকরণ দেখব — যা এই infinite sum-কে recursive equation-এ রূপান্তর করে এবং RL-এর সব algorithm-এর ভিত্তি।

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

প্র ০১ $V$ থাকতে $Q$-এর কী দরকার? দু'টোই train করা wasteful?

$V$ থেকে action বাছতে dynamics দরকার:

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

কিন্তু model-free RL-এ $P, R$ unknown — তাই $V$ থেকে action বাছা যায় না। $Q$ এই dependency-কে action-এ এনকোড করে।

কখন $V$ যথেষ্ট:

Model-based RL — dynamics জানা।
Policy gradient — policy parameterized, value শুধু baseline।
Actor-Critic — actor policy, critic V (বা Q)।

কখন $Q$ দরকার:

Model-free value-based — Q-learning, DQN।
Optimal action সরাসরি বের করতে।

Dueling DQN-এর insight: $Q(s,a) = V(s) + A(s,a)$। দু'টোই separately learn করা stability ও sample efficiency বাড়ায়। তাই দু'টোই কাজ করে — wasteful নয়।

প্র ০২ Optimal value $V^*$ unique, কিন্তু optimal policy $\pi^*$ অনেক হতে পারে। কীভাবে?

$V^*$ unique কারণ এটি Bellman optimality equation-এর fixed point — contraction mapping-এর কারণে unique।

$\pi^*$ unique না — কারণ যদি দু'টি action-এর $Q^*$ মান সমান হয়:

$$Q^*(s, a_1) = Q^*(s, a_2) > Q^*(s, a_3)$$

তবে $a_1$ বা $a_2$ — দু'টিই optimal action। তাই deterministic policy দু'টি — দু'টোই $V^*$ produce করে।

উদাহরণ:

সমান-দুই-পথ গোলকধাঁধা — দু'টি optimal route।
Symmetric game — multiple equivalent best moves।

Practice-এ:

Q-learning ties break করে arbitrarily (numerical noise)।
Boltzmann/soft policy — সব optimal action proportional।
Maximum entropy RL — unique stochastic optimal policy (SAC)।

প্র ০৩ Advantage $A(s,a)$ কেন variance reduce করে? mathematically কেন?

Policy gradient-এ raw return ব্যবহার করলে:

$$\nabla J \approx \mathbb{E}[\nabla \log \pi(a|s) \cdot G]$$

$G$-এর variance সাধারণত বিশাল। তাই baseline $b(s)$ বিয়োগ — $G - b(s)$:

$$\nabla J \approx \mathbb{E}[\nabla \log \pi(a|s) \cdot (G - b(s))]$$

গাণিতিকভাবে এটা unbiased — কারণ $\mathbb{E}[\nabla \log \pi \cdot b(s)] = b(s) \cdot \mathbb{E}[\nabla \log \pi] = 0$ ($\nabla \log \pi$-এর expectation শূন্য)।

Optimal baseline = $V(s)$:

$G - V(s) \approx Q(s,a) - V(s) = A(s,a)$।
Variance বহু কম — কারণ $V$ "average" বের করে।

Intuitive: "এই action সবার চেয়ে ভাল কিনা" — সেটা শুধু "ভাল কিনা"-র চেয়ে cleaner signal।

প্র ০৪ Atari game-এ state space ১৬M-D pixel। Q-table অসম্ভব। কীভাবে $Q$ represent করব?

Tabular Q impossible এত বড় state space-এ। সমাধান — function approximation।

(১) Linear: $Q(s, a) = \theta_a^T \phi(s)$ — feature engineering-নির্ভর।

(২) Neural network (DQN):

Input: state (image)।
Output: $Q(s, a)$ for each action।
Parameters $\theta$ — gradient descent দিয়ে train।

চ্যালেঞ্জ:

Convergence guarantee হারায় (deadly triad)।
Catastrophic forgetting — নতুন data পুরাতন pattern ভোলায়।
সমাধান: replay buffer, target networks (পরে দেখব)।

মূল উপলব্ধি: table → neural network = curse of dimensionality থেকে বাঁচানোর উপায়। কিন্তু stability চ্যালেঞ্জ আনে।

অনুশীলন

Manual computation: deterministic chain $s_1 \to s_2 \to s_3$ (terminal), reward $r_1=2, r_2=4$, $\gamma=0.5$। $V(s_1), V(s_2)$ কত?

$V(s_2) = r_2 = 4$ (next is terminal)। $V(s_1) = r_1 + \gamma V(s_2) = 2 + 0.5 \cdot 4 = 4$।
$V$ vs $Q$: দু'টি action — $a_1$ reward +5 then terminal, $a_2$ reward +1 then state-এ যেখানে $V=20, \gamma=0.9$। কোন action ভাল?

$Q(s, a_1) = 5$। $Q(s, a_2) = 1 + 0.9 \cdot 20 = 19$। তাই $a_2$ ভাল। $V(s) = \max(5, 19) = 19$।
Conceptual: $\gamma = 0$ হলে $Q^*$ কী হবে? যদি reward bounded $|r| \le 1$ ও $\gamma \to 1$ হয় — $V^*$-এর upper bound কত?

$\gamma = 0$ হলে — $Q^*(s, a) = R(s, a)$ — শুধু immediate reward।

$\gamma \to 1$ হলে $V^* \le \frac{1}{1-\gamma}$ → ∞। তাই episodic বা bounded horizon দরকার।