অনিশ্চয়তায় সিদ্ধান্ত — expected utility আর MDP-এর পরিচয়

মডিউল ৯-এর এটি শেষ পর্ব, আর এখানেই কোর্সের classical AI-এর অর্ধেক শেষ হচ্ছে। আগের চার পর্বে শিখেছি অনিশ্চয়তায় বিশ্বাস হালনাগাদ করা: Bayes-এর উপপাদ্য (পর্ব ৫০), Naive Bayes (পর্ব ৫১), Bayesian network (পর্ব ৫২) আর Markov model (পর্ব ৫৩)। কিন্তু বৃষ্টির সম্ভাবনা ৭০% জানার পরও ঠিক করতে হয় ছাতা নেবেন কি না। এই পর্ব সেই শেষ ধাপের: সম্ভাবনা থেকে সিদ্ধান্ত। উদাহরণ আবার বাজারঘর, এই কোর্সের কাল্পনিক অনলাইন দোকান; সব দাম, চাহিদা আর সম্ভাবনা বানানো সংখ্যা, কোনো আসল দোকানের নয়। চালানো যায় এমন ব্লকগুলো পাতাতেই চলে (ব্রাউজারের Python, NumPy 2.4.6, matplotlib 3.10.8); প্রথমবার package নামতে কয়েক সেকেন্ড লাগতে পারে।

১ · বিশ্বাস থেকে কাজ — rational agent কীভাবে বেছে নেয়

পর্ব ১-এ এই কোর্সের কাজের সংজ্ঞা ছিল: AI হলো এমন agent বানানো, যে পরিবেশ দেখে এমন কাজ বেছে নেয় যাতে একটি মাপকাঠিতে প্রত্যাশিত ফল সবচেয়ে ভালো হয়। সেখানে মেট্রো, CNG আর বাসের একটি ছোট উদাহরণে utility-based agent দেখেছিলেন। “প্রত্যাশিত” শব্দটির পুরো অর্থ এবার খুলে দেখা যাক।

যেকোনো সিদ্ধান্তে তিনটি উপাদান থাকে:

• কাজ (action): আপনি যা বেছে নিতে পারেন। যেমন ঈদের আগে ১০০ পিস পাঞ্জাবি আনবেন, না ২০০ পিস।
• অবস্থা (state of the world): যা আপনার হাতে নেই, কিন্তু ফল ঠিক করে। যেমন এবার চাহিদা বেশি হবে, না কম। এর ওপর আপনার বিশ্বাস একটি সম্ভাবনা, যা আগের পর্বগুলোর হাতিয়ার দিয়ে ডেটা থেকে আসে।
• ফল (outcome) আর তার utility: প্রতিটি কাজ আর অবস্থার জোড়ায় কী ঘটে, আর সেটি আপনার কাছে কতটা ভালো।

এই তিনটি জানা থাকলে নিয়মটি এক লাইনের:

EU(a) = ∑_s P(s) · U(a, s),   সিদ্ধান্ত = argmax_a EU(a)

এখানে a একটি কাজ, s জগতের একটি অবস্থা, P(s) সেই অবস্থার সম্ভাবনা, U(a, s) সেই জোড়ার utility, আর ∑ মানে সব অবস্থার ওপর যোগ। argmax মানে “যে a-তে মান সবচেয়ে বড়, সেই a”. একে বলে maximum expected utility নীতি (সংক্ষেপে MEU). Russell ও Norvig-এর বই rational agent-কে এভাবেই সংজ্ঞায়িত করে।

এ পর্যন্ত কোর্সের বেশিরভাগ AI ধরে নিয়েছিল কাজের ফল নিশ্চিত। Search-এ (মডিউল ৭) “বাঁয়ে যাওয়া” মানে নিশ্চিতভাবে বাঁয়ের ঘরে পৌঁছানো, আর পর্ব ৪৯-এর STRIPS planning-এও প্রতিটি action deterministic. ব্যতিক্রম ছিল পর্ব ৪২-এর লুডুর মতো খেলা, যেখানে chance node এসেছিল। বাস্তব জগৎ প্রায়ই stochastic: রাস্তা বন্ধ থাকতে পারে, গ্রাহক বাসায় না-ও থাকতে পারেন।

২ · Expected value — ঈদের আগে ১০০ না ২০০ পিস

বাজারঘর ঈদের আগে একটি পাঞ্জাবি বিক্রি করবে (সব সংখ্যা কাল্পনিক)। প্রতিটির কেনা দাম ৬০০ টাকা, বিক্রি ১০০০ টাকা। ঈদের পরে যা বাঁচবে, তা ২০০ টাকায় ছেড়ে দিতে হবে। চাহিদা নিয়ে দুটি সম্ভাবনা: বেশি চাহিদা (২০০ জন কিনতে চাইবেন) সম্ভাবনা ০.৬, কম চাহিদা (মাত্র ৮০ জন) সম্ভাবনা ০.৪. আনার সিদ্ধান্ত ঈদের আগেই নিতে হবে।

প্রথমে প্রতিটি জোড়ার লাভ হাতে হিসাব করি:

• ১০০ পিস, বেশি চাহিদা: সব বিক্রি, ১০০ × (১০০০ − ৬০০) = ৪০,০০০ টাকা।
• ১০০ পিস, কম চাহিদা: ৮০টি ১০০০ টাকায়, বাকি ২০টি ২০০ টাকায়: ৮০,০০০ + ৪,০০০ − ৬০,০০০ = ২৪,০০০ টাকা।
• ২০০ পিস, বেশি চাহিদা: ২০০ × ৪০০ = ৮০,০০০ টাকা।
• ২০০ পিস, কম চাহিদা: ৮০,০০০ + ১২০ × ২০০ − ১,২০,০০০ = −১৬,০০০ টাকা, মানে ক্ষতি।

Expected value (EV) পর্ব ৩৬-এ দেখেছেন: প্রতিটি মানকে তার সম্ভাবনা দিয়ে গুণ করে যোগফল, মানে দীর্ঘ মেয়াদের ওজনসহ গড়। লাভকেই utility ধরলে, মানে টাকার প্রতিটি অঙ্ক সমান মূল্যবান ধরলে, ২০০ পিস আনা ভালো: প্রত্যাশিত লাভ ৮,০০০ টাকা বেশি। এভাবে শুধু EV দেখে সিদ্ধান্ত নেওয়াকে বলে risk-neutral আচরণ।

৩ · Expected value যথেষ্ট নয় — ঝুঁকি, utility আর certainty equivalent

ধরুন বাজারঘর ছোট, ঈদের আগে হাতে নগদ মাত্র ২০,০০০ টাকা (ধার করে মাল তোলা হবে, ঈদের পরে শোধ)। ২০০ পিস এনে চাহিদা কম হলে হাতে থাকবে ৪,০০০ টাকা; অন্যদিকে নগদ ২,০০,০০০ টাকার একটি বড় দোকানের কাছে ১৬,০০০ টাকার ক্ষতি সহ্য করার মতো। একই EV, কিন্তু দুই দোকানের কাছে ঝুঁকির ওজন আলাদা। এই অনুভূতির নাম risk aversion: একই গড় হলে মানুষ অনিশ্চিত ফলের চেয়ে নিশ্চিত ফল পছন্দ করেন।

টাকার utility বাঁকা

প্রথম ১০,০০০ টাকা যতটা কাজে লাগে (ভাড়া, খাবার), দশম লাখের পরের ১০,০০০ টাকা ততটা নয়। তাই টাকা থেকে utility-র লেখচিত্র সোজা রেখা নয়, ধীরে ধীরে চ্যাপ্টা হয়ে আসা একটি বাঁক, যাকে বলে concave function. সবচেয়ে পরিচিত দুটি রূপ হলো log আর বর্গমূল: U(w) = ln(w) বা U(w) = √w, যেখানে w হলো সিদ্ধান্তের পরে হাতে থাকা মোট টাকা।

ছোট দোকানের জন্য হাতে হিসাব (নগদ ২০,০০০):

• ১০০ পিস: শেষে ৬০,০০০ বা ৪৪,০০০ টাকা। EU = ০.৬ × ln ৬০,০০০ + ০.৪ × ln ৪৪,০০০ ≈ ০.৬ × ১১.০০২ + ০.৪ × ১০.৬৯২ ≈ ১০.৮৭৮.
• ২০০ পিস: শেষে ১,০০,০০০ বা ৪,০০০ টাকা। EU = ০.৬ × ১১.৫১৩ + ০.৪ × ৮.২৯৪ ≈ ১০.২২৫.

EU-তে ১০০ পিস জেতে। log-এ ৪,০০০ টাকার মান খুব ছোট, কারণ শূন্যের কাছে log দ্রুত নিচে নামে; বড় ক্ষতির ভয় হিসাবে ঢুকে গেছে।

Certainty equivalent আর risk premium

EU-র একক (log-টাকা) কারও কাছে অর্থবহ নয়। তাই উল্টো প্রশ্ন করি: কত টাকা নিশ্চিত পেলে দোকানটি এই জুয়ার সমান খুশি হতো? এটিই certainty equivalent (CE): U(নগদ + CE) = EU. log-এর জন্য CE = e^EU − নগদ. আর EV − CE হলো risk premium: অনিশ্চয়তা এড়াতে আপনি গড়ে যতটা লাভ ছেড়ে দিতে রাজি। মানুষ যে গড়ের চেয়ে বেশি প্রিমিয়াম দিয়েও বীমা কেনেন, তার ব্যাখ্যা এখানেই।

import math

# বাজারঘর, ঈদের পাঞ্জাবি (কাল্পনিক): কেনা 600, বিক্রি 1000, ঈদের পরে বাকিটা 200 টাকা
# লাভ পয়সায় (integer), যাতে টাকার হিসাবে float-এর গোলমাল না ঢোকে
profit = {100: {"high": 40_000_00, "low": 24_000_00},
          200: {"high": 80_000_00, "low": -16_000_00}}
prob = {"high": 0.6, "low": 0.4}

def taka(paisa):
    return f"{paisa / 100:,.2f}"

def ev(q):
    return sum(prob[d] * profit[q][d] for d in prob)

for q in profit:
    print(f"stock {q}: EV = {taka(ev(q))} taka")

for cash in (20_000_00, 200_000_00):            # ঈদের আগে দোকানের নগদ টাকা
    print(f"\nstarting cash {taka(cash)} taka, utility = log(cash after Eid)")
    for q in profit:
        eu = sum(prob[d] * math.log((cash + profit[q][d]) / 100) for d in prob)
        ce = round(math.exp(eu) * 100) - cash   # certainty equivalent, paisa
        print(f"  stock {q}: EU = {eu:.4f}  CE = {taka(ce)}  "
              f"risk premium = {taka(ev(q) - ce)}")

best = max(ev(q) for q in profit)
perfect = sum(prob[d] * max(profit[q][d] for q in profit) for d in prob)
print("\nEV with a perfect forecast =", taka(perfect), "taka")
print("value of perfect information =", taka(perfect - best), "taka")

stock 100: EV = 33,600.00 taka
stock 200: EV = 41,600.00 taka

starting cash 20,000.00 taka, utility = log(cash after Eid)
  stock 100: EU = 10.8780  CE = 32,999.51  risk premium = 600.49
  stock 200: EU = 10.2254  CE = 7,594.59  risk premium = 34,005.41

starting cash 200,000.00 taka, utility = log(cash after Eid)
  stock 100: EU = 12.3608  CE = 33,467.24  risk premium = 132.76
  stock 200: EU = 12.3746  CE = 36,712.91  risk premium = 4,887.09

EV with a perfect forecast = 57,600.00 taka
value of perfect information = 16,000.00 taka

দুশো বছর পরে John von Neumann আর Oskar Morgenstern তাঁদের Theory of Games and Economic Behavior বইয়ের দ্বিতীয় সংস্করণে (১৯৪৭) দেখান: কারও পছন্দ কয়েকটি যুক্তিসঙ্গত শর্ত মানলে, তাঁর আচরণ কোনো একটি utility function-এর expected utility সর্বোচ্চ করার মতো করে বর্ণনা করা যায়। এই von Neumann–Morgenstern axiom-গুলো সাধারণত চার নামে বলা হয়: completeness, transitivity, continuity আর independence; বিভিন্ন বইয়ে এদের রূপ আর সংখ্যা কিছুটা আলাদা। মূল কথা: MEU খেয়ালি সূত্র নয়, সুসংগত পছন্দের পরিণতি। মানুষ সবসময় এই শর্ত মানেন কি না, তা ভাবনার প্রশ্ন ২-এ দেখবেন।

৪ · Decision tree — সিদ্ধান্ত আর সম্ভাবনার গাছ, পেছন থেকে হিসাব

বাস্তবে সিদ্ধান্ত প্রায়ই একটির পর একটি আসে। বাজারঘরের মার্কেটিং দল প্রস্তাব দিল: ঈদের আগে “ফ্রি ডেলিভারি” প্রচার চালানো হোক। এতে খরচ ১০,০০০ টাকা (ডেলিভারি চার্জ দোকান বহন করবে), কিন্তু বেশি চাহিদার সম্ভাবনা ০.৬ থেকে বেড়ে ০.৮ হবে বলে তাঁদের অনুমান (কাল্পনিক)। প্রচারের সিদ্ধান্ত আগে, তারপর stock-এর সিদ্ধান্ত, তারপর চাহিদা জানা যাবে।

এমন ক্রমের সিদ্ধান্ত আঁকা হয় decision tree দিয়ে। (Machine learning-এর decision tree আলাদা জিনিস।) গাছে দুই ধরনের node:

• Decision node (বর্গ ■): এখানে আপনি বেছে নেন। এর মান = শাখাগুলোর মানের মধ্যে সবচেয়ে বড় (শাখার খরচ বাদ দিয়ে)।
• Chance node (বৃত্ত ●): এখানে জগৎ “বেছে নেয়”. এর মান = শাখাগুলোর সম্ভাবনা-ওজনসহ গড়, ঠিক পর্ব ৪২-এর expectiminimax-এর chance node-এর মতো, শুধু এখানে কোনো প্রতিপক্ষ নেই।

হিসাব চলে পাতা থেকে গোড়ার দিকে, পেছন দিকে; একে বলে rollback বা backward induction. নিচের stepper-এ “পরে” চাপুন।

একই rollback কোডে একটি ছোট recursive function, কারণ গাছের প্রতিটি অংশও একটি গাছ (DSA কোর্সের recursion পর্ব)। Node তিন রকম: leaf (একটি integer, লাভ পয়সায়), chance node আর decision node.

# node: ("decision", name, {choice: (cost, child)}),
#       ("chance", name, [(prob, child), ...]), বা leaf = লাভ (পয়সা, int)
def stock(p_high):
    return ("decision", f"stock? (P(high)={p_high})", {
        "100": (0, ("chance", "demand | 100", [(p_high, 40_000_00), (1 - p_high, 24_000_00)])),
        "200": (0, ("chance", "demand | 200", [(p_high, 80_000_00), (1 - p_high, -16_000_00)])),
    })

tree = ("decision", "free delivery?", {
    "yes": (10_000_00, stock(0.8)),       # প্রচারের খরচ 10,000 টাকা
    "no":  (0, stock(0.6)),
})

def rollback(node, depth=0):
    if isinstance(node, int):                       # leaf
        return node
    kind, name, branches = node
    pad = "  " * depth
    if kind == "chance":                            # সম্ভাবনা-ওজনসহ গড়
        value = round(sum(p * rollback(child, depth + 1) for p, child in branches))
        print(f"{pad}chance   {name}: {value / 100:,.0f}")
        return value
    values = {c: rollback(child, depth + 1) - cost   # decision: সবচেয়ে বড়টি
              for c, (cost, child) in branches.items()}
    best = max(values, key=values.get)
    print(f"{pad}decision {name}: choose {best} -> {values[best] / 100:,.0f}")
    return values[best]

print("root value:", f"{rollback(tree) / 100:,.0f} taka")

    chance   demand | 100: 36,800
    chance   demand | 200: 60,800
  decision stock? (P(high)=0.8): choose 200 -> 60,800
    chance   demand | 100: 33,600
    chance   demand | 200: 41,600
  decision stock? (P(high)=0.6): choose 200 -> 41,600
decision free delivery?: choose yes -> 50,800
root value: 50,800 taka

৫ · তথ্যের দাম আর sensitivity analysis — পূর্বাভাসের মূল্য কত

একটি কোম্পানি প্রস্তাব দিল: তারা ঈদের আগেই নিশ্চিতভাবে বলে দেবে চাহিদা বেশি হবে না কম, ফি নেবে। কত টাকা পর্যন্ত দেওয়া যুক্তিসঙ্গত? (প্রচার ছাড়া, P(high) = ০.৬ ধরে।)

পূর্বাভাস হাতে থাকলে আপনি প্রতিটি অবস্থার জন্য আলাদা সেরা কাজ বাছতে পারতেন: বেশি চাহিদা শুনলে ২০০ (৮০,০০০), কম শুনলে ১০০ (২৪,০০০)। পূর্বাভাস আসার আগে আপনি জানেন না কোনটি শুনবেন, তাই এর প্রত্যাশিত মান ০.৬ × ৮০,০০০ + ০.৪ × ২৪,০০০ = ৫৭,৬০০. পূর্বাভাস ছাড়া সেরা EV ছিল ৪১,৬০০. পার্থক্যই value of perfect information (EVPI):

EVPI = E_s[ max_a U(a, s) ] − max_a E_s[ U(a, s) ] = 57,600 − 41,600 = 16,000 টাকা

প্রথম পদে “আগে জেনে তারপর বাছা”, দ্বিতীয় পদে “আগে বেছে তারপর জানা”. অংশ ৩-এর কোডের শেষ দুই লাইন ঠিক এটিই ছেপেছিল। কোনো পূর্বাভাসই নিখুঁত নয়, তাই EVPI হলো একটি ঊর্ধ্বসীমা: ১৬,০০০ টাকার বেশি দাম চাওয়া পূর্বাভাস কখনো লাভজনক নয় (risk-neutral হিসাবে)। ভুল করতে পারে এমন পূর্বাভাসের দাম আরও কম, আর তা Bayes দিয়ে হিসাব হয় (পর্ব ৫০)।

Sensitivity analysis — সম্ভাবনা ভুল হলে?

০.৬ সংখ্যাটি একটি অনুমান। এটি ০.৪৫ হলেও কি ২০০ পিসই ঠিক? Sensitivity analysis মানে একটি ইনপুট ধীরে ধীরে বদলে দেখা, সিদ্ধান্ত কোথায় উল্টে যায়। p = P(high) ধরলে দুই কাজের EV দুটি সরলরেখা:

EV₁₀₀(p) = 24,000 + 16,000p,   EV₂₀₀(p) = −16,000 + 96,000p

দুটি সমান হয় যখন ৪০,০০০ = ৮০,০০০p, মানে p = ০.৫. এই crossover point-এর ওপরে ২০০, নিচে ১০০. আমাদের অনুমান ০.৬ সীমা থেকে মাত্র ০.১ দূরে, তাই সিদ্ধান্তটি “ভঙ্গুর”: সম্ভাবনার অনুমান সামান্য ভুল হলেই সেরা কাজ বদলায়।

import numpy as np
import matplotlib.pyplot as plt

p = np.linspace(0, 1, 101)                      # P(high demand), 0 থেকে 1
ev100 = p * 40_000 + (1 - p) * 24_000           # টাকা
ev200 = p * 80_000 + (1 - p) * -16_000
best = np.maximum(ev100, ev200)
perfect = p * 80_000 + (1 - p) * 24_000         # আগে চাহিদা জানলে
evpi = perfect - best

# ev100 = ev200 সমীকরণ: 24000 + 16000p = -16000 + 96000p
cross = (24_000 + 16_000) / (96_000 - 16_000)
print("crossover P(high) =", cross)
for q in (0.3, 0.45, 0.6, 0.8):
    i = round(q * 100)
    pick = "200" if ev200[i] > ev100[i] else "100"
    print(f"P(high)={q}: EV100={ev100[i]:,.0f}  EV200={ev200[i]:,.0f}  "
          f"choose {pick}  EVPI={evpi[i]:,.0f}")
print("largest EVPI:", f"{evpi.max():,.0f}", "at P(high) =", p[evpi.argmax()])

fig, ax = plt.subplots(figsize=(6.4, 3.6), layout="constrained")
ax.plot(p, ev100 / 1000, label="stock 100")
ax.plot(p, ev200 / 1000, label="stock 200")
ax.plot(p, evpi / 1000, "--", label="value of perfect information")
ax.axvline(cross, color="gray", lw=1)
ax.axhline(0, color="black", lw=0.6)
ax.set_xlabel("P(high demand)")
ax.set_ylabel("thousand taka")
ax.set_title("Sensitivity: Eid stocking decision")
ax.legend(fontsize=8)
plt.show()

crossover P(high) = 0.5
P(high)=0.3: EV100=28,800  EV200=12,800  choose 100  EVPI=12,000
P(high)=0.45: EV100=31,200  EV200=27,200  choose 100  EVPI=18,000
P(high)=0.6: EV100=33,600  EV200=41,600  choose 200  EVPI=16,000
P(high)=0.8: EV100=36,800  EV200=60,800  choose 200  EVPI=8,000
largest EVPI: 20,000 at P(high) = 0.5

৬ · ধাপে ধাপে সিদ্ধান্ত — Markov decision process

এবার বাজারঘরের ডেলিভারি রাইডারের কথা ভাবুন। প্রতিটি মোড়ে তিনি ঠিক করেন কোন দিকে যাবেন, আর প্রতিটি সিদ্ধান্তের পরে নতুন জায়গায় নতুন সিদ্ধান্ত। একটি রাস্তা মাঝে মাঝে বন্ধ থাকে (মিছিল, পানি জমা বা খোঁড়াখুঁড়ি); তখন তিনি যেখানে ছিলেন সেখানেই আটকে থাকেন। Decision tree এখানে অসম্ভব বড় হয়, কারণ প্রতিটি ধাপে শাখা গুণ হয় আর রাইডার একই মোড়ে বারবার ফিরতে পারেন।

সেই মডেলের নাম Markov decision process (MDP). এর পাঁচটি অংশ:

• State S: agent কোথায় আছে। এখানে রাইডার কোন ঘরে।
• Action A: প্রতিটি state-এ কী করা যায়। এখানে ^ v > < (উত্তর, দক্ষিণ, পূর্ব, পশ্চিম)।
• Transition probability P(s′ | s, a): s-এ a করলে s′-এ পৌঁছানোর সম্ভাবনা। বন্ধ হতে পারা রাস্তায় ঢুকতে চাইলে ০.৫ সম্ভাবনায় ঢোকা যায়, ০.৫ সম্ভাবনায় একই ঘরে থাকতে হয়।
• Reward R: প্রতিটি ধাপে পাওয়া সংখ্যা। গ্রাহকের কাছে পৌঁছালে +১০, কাছের ছোট একটি অর্ডারে +২, আর প্রতিটি ধাপে সময় আর জ্বালানির খরচ, যাকে বলব step cost (যেমন −০.১)।
• Discount factor γ (গামা), ০ ≤ γ ≤ ১: ভবিষ্যতের reward আজকের তুলনায় কতটা কম মূল্যবান। t ধাপ পরের reward-কে γ^t দিয়ে গুণ করা হয়। γ = ০.৯ হলে ১০ ধাপ পরের reward-এর ওজন ০.৯^১০ ≈ ০.৩৪৯. ছোট γ মানে অধৈর্য agent.

“Markov” শব্দটি একটি অনুমান থেকে: Markov property, মানে ভবিষ্যৎ শুধু বর্তমান state আর action-এর ওপর নির্ভর করে, কীভাবে এখানে এলাম তার ওপর নয়। পর্ব ৫৩-এর Markov chain-এ এটিই ছিল; MDP সেই chain-এ action আর reward যোগ করে। বাস্তবে এটি সরলীকরণ (যানজট কিছুক্ষণ থাকে); দরকার হলে state-এ বাড়তি তথ্য রাখা হয়।

MDP-র উত্তর একটি পথ নয়, একটি policy π: প্রতিটি state-এ কোন action নিতে হবে তার নিয়ম, π(s) = a. কারণ রাস্তা বন্ধ থাকলে রাইডার কোথায় পড়বেন আগে জানা নেই; policy সব জায়গার উত্তর আগেই রাখে। একটি policy কতটা ভালো, তা মাপে value function V^π(s): s থেকে π মেনে চললে ভবিষ্যতের সব discount করা reward-এর প্রত্যাশিত যোগফল,

V^π(s) = E[ r₁ + γ r₂ + γ² r₃ + … | শুরু s, π মেনে ]

লক্ষ্য হলো optimal policy π*, যার মান প্রতিটি state-এ সবচেয়ে বেশি। নাম আর গণিত এসেছে Richard Bellman-এর কাছ থেকে: তাঁর ১৯৫৭ সালের বই Dynamic Programming আর একই বছরের প্রবন্ধ “A Markovian Decision Process”-কে সাধারণত এই কাঠামোর সূচনা ধরা হয়, যদিও sequential decision-এর কাছাকাছি ধারণা তার আগেও ছিল।

৭ · Bellman equation আর value iteration — হাতে দুই sweep

Bellman-এর মূল পর্যবেক্ষণটি সহজ ভাষায়: একটি জায়গার মান = এখনকার সেরা কাজের তাৎক্ষণিক reward + যেখানে গিয়ে পড়বেন সেই জায়গার মানের discount করা গড়। পুরো ভবিষ্যৎ একবারে হিসাব করার দরকার নেই; শুধু এক ধাপ সামনে দেখে বাকিটা পরের state-এর মানের হাতে ছেড়ে দিলেই চলে। সূত্রে, Bellman optimality equation:

V*(s) = max_a ∑_s′ P(s′ | s, a) · [ R(s, a, s′) + γ · V*(s′) ]

বন্ধনীর ভেতরের যোগফলটিকে বলে Q-value, Q(s, a): s-এ a করে তারপর সেরাভাবে চললে প্রত্যাশিত মান। তাহলে V*(s) = max_a Q(s, a), আর optimal policy হলো প্রতিটি state-এ সবচেয়ে বড় Q-র action, যাকে বলে greedy policy. এটি অংশ ৪-এর rollback-এরই রূপ (গড় আর max), শুধু গাছের বদলে state-এর জালে।

হাতে হিসাবের মতো একটি ছোট MDP

Grid-এ যাওয়ার আগে দুই state-এর একটি MDP নিই, যা পরীক্ষার খাতায় হাতে করা যায়। রাইডার দোকানে (S). দুটি পথ:

• short (মাঝে মাঝে বন্ধ রাস্তা): ০.৭ সম্ভাবনায় গ্রাহকের কাছে পৌঁছান, reward +১০, কাজ শেষ। ০.৩ সম্ভাবনায় রাস্তা বন্ধ: অপেক্ষার খরচ −১, আবার S-এ।
• long (ঘুরপথ): নিশ্চিতভাবে মোড় M-এ যান, খরচ −১. M থেকে একটিই কাজ, নিশ্চিতভাবে গ্রাহকের কাছে, +১০.

γ = ০.৯. গ্রাহকের ঘর G terminal, তাই V(G) = ০.

Value iteration চলে এভাবে: সব V = ০ দিয়ে শুরু, তারপর প্রতিটি state-এ Bellman equation-এর ডান দিক হিসাব করে নতুন V বানানো। সব state একবার হালনাগাদ করাকে বলে একটি sweep. প্রথম sweep-এ (সব V = ০) Q(S, short) = ০.৭ × ১০ + ০.৩ × (−১) = ৬.৭ আর Q(S, long) = −১, তাই V₁(S) = ৬.৭; আর V₁(M) = ১০. দ্বিতীয় sweep-এ S-এর হালনাগাদ নিচে ধাপে ধাপে।

Q(s,a) = ∑ P·[R + γ·V(s′)]
V(s) = max Q(s,a)

এভাবে sweep চলতে থাকলে মান স্থির হয়ে আসে, মানে convergence. নিচের stepper-এ প্রতিটি sweep-এর ফল; সংখ্যাগুলো scratch কোডে হিসাব করা, Δ মানে এক sweep-এ কোনো state-এর মানের সবচেয়ে বড় পরিবর্তন। প্রথম sweep-এর পরে V(M) সবসময় ১০.

Policy iteration — আগে policy, তারপর তার মান

Policy iteration উল্টো পথে যায়, আর একে সাধারণত Ronald Howard-এর ১৯৬০ সালের বই Dynamic Programming and Markov Processes-এর সঙ্গে যুক্ত করা হয়। দুটি ধাপ পালা করে চলে:

1. Policy evaluation: বর্তমান policy স্থির রেখে তার V^π বের করা। max নেই বলে এটি সরল সমীকরণের সেট।
2. Policy improvement: সেই V দিয়ে প্রতিটি state-এ greedy action বাছা। কিছু না বদলালে থামা।

ছোট MDP-তে হাতে: শুরুর policy “long”. Evaluation: V(S) = −১ + ০.৯ × ১০ = ৮. Improvement: Q(S, short) = ৭ + ০.৩ × (−১ + ০.৯ × ৮) = ৭ + ১.৮৬ = ৮.৮৬ > ৮, তাই policy বদলে “short”. আবার evaluation: V(S) = ৯.১৭৮. Improvement: long-এর Q = ৮ < ৯.১৭৮, কিছু বদলায় না, থামা। মাত্র দুই round, যেখানে value iteration-এ নয়টি sweep লেগেছিল; তবে প্রতিটি round-এ একটি পূর্ণ evaluation আছে।

৮ · কোডে value iteration আর policy iteration — γ আর step cost বদলালে

এবার ছবি ৫৪.১-এর grid. নিচের কোডে q_value হলো Bellman equation-এর বন্ধনীর অংশ: একটি দিকে চললে কোথায় পৌঁছান (ম্যাপের বাইরে গেলে যেখানে ছিলেন), R-এ ঢুকতে চাইলে block সম্ভাবনায় আগের ঘরে থাকা, আর প্রতিটি ধাপে step খরচ। Terminal ঘর (G, g) V-তে নেই, তাই তাদের মান ০ ধরা হয় (V.get(t, 0.0)). একই MDP-তে value iteration আর policy iteration চালিয়ে মেলানো হয়েছে, তারপর তিনটি সেটিংয়ে policy কীভাবে বদলায় দেখা হয়েছে। আউটপুটে প্রতিটি ঘরে মান আর greedy action-এর তীর।

GRID = ["....", "S.RG", "g..."]   # S দোকান, R মাঝে মাঝে বন্ধ রাস্তা, G গ্রাহক +10, g ছোট অর্ডার +2
END, MOVES = {"G": 10, "g": 2}, {"^": (-1, 0), "v": (1, 0), ">": (0, 1), "<": (0, -1)}
CELLS = [(r, c) for r in range(3) for c in range(4) if GRID[r][c] not in END]
def q_value(V, s, m, gamma, step, block):      # Q(s, m): এক ধাপ সামনে দেখে প্রত্যাশিত মান
    r, c = s[0] + MOVES[m][0], s[1] + MOVES[m][1]
    if not (0 <= r < 3 and 0 <= c < 4): r, c = s  # ম্যাপের বাইরে গেলে যেখানে ছিল
    outs = [(1 - block, (r, c)), (block, s)] if GRID[r][c] == "R" else [(1.0, (r, c))]
    return sum(p * (step + END.get(GRID[t[0]][t[1]], 0) + gamma * V.get(t, 0.0)) for p, t in outs)
def greedy(V, *mdp):
    return {s: max(MOVES, key=lambda m: q_value(V, s, m, *mdp)) for s in CELLS}
def value_iteration(*mdp, tol=1e-4):
    V = dict.fromkeys(CELLS, 0.0)
    for sweep in range(1, 1000):
        new = {s: max(q_value(V, s, m, *mdp) for m in MOVES) for s in CELLS}
        if max(abs(new[s] - V[s]) for s in CELLS) < tol: return new, sweep
        V = new
def policy_iteration(*mdp):
    pi = dict.fromkeys(CELLS, "<")                # শুরু: সবখানে "বাঁয়ে"
    for rounds in range(1, 100):
        V = dict.fromkeys(CELLS, 0.0)
        for _ in range(300): V = {s: q_value(V, s, pi[s], *mdp) for s in CELLS}  # evaluation
        new = greedy(V, *mdp)                     # improvement
        if new == pi: return pi, rounds
        pi = new
def show(V, pi):
    for r in range(3):
        print(" ".join(f"  {GRID[r][c]}   " if GRID[r][c] in END else f"{V[(r, c)]:5.2f}{pi[(r, c)]}" for c in range(4)))
V, sweeps = value_iteration(0.9, -0.1, 0.5)
pi, rounds = policy_iteration(0.9, -0.1, 0.5)
print("VI sweeps:", sweeps, "| PI rounds:", rounds, "| same policy:", pi == greedy(V, 0.9, -0.1, 0.5))
show(V, pi)
for mdp in [(0.5, -0.1, 0.5), (0.9, -3.0, 0.5), (0.9, -0.1, 0.8)]:
    V, sweeps = value_iteration(*mdp)
    print(f"\ngamma, step, block = {mdp}: {sweeps} sweeps")
    show(V, greedy(V, *mdp))

VI sweeps: 17 | PI rounds: 4 | same policy: True
 6.95>  7.83>  8.81>  9.90v
 7.03>  7.92>  9.90>   G
  g     7.83>  8.81>  9.90^

gamma, step, block = (0.5, -0.1, 0.5): 10 sweeps
 1.06>  2.33>  4.85>  9.90v
 1.90v  3.17>  9.90>   G
  g     2.33>  4.85>  9.90^

gamma, step, block = (0.9, -3.0, 0.5): 15 sweeps
-3.03> -0.03>  3.30>  7.00v
-1.00v  0.27>  7.00>   G
  g    -0.03>  3.30>  7.00^

gamma, step, block = (0.9, -0.1, 0.8): 6 sweeps
 6.95>  7.83>  8.81>  9.90v
 6.15^  6.95^  9.90>   G
  g     7.83>  8.81>  9.90^

৯ · MDP-এর পরে — POMDP, reinforcement learning আর সৎ সতর্কতা

যখন state-ও দেখা যায় না

আমাদের রাইডার সবসময় জানেন তিনি কোথায়। কিন্তু ধরুন তিনি জানেন না রাস্তাটি এখন বন্ধ কি না, শুধু ইঙ্গিত দেখেন (অন্য রাইডারের দেরি, ভিড়ের শব্দ)। পর্ব ৫৩-এর hidden Markov model-এর লুকানো অবস্থার মতো, তখন MDP হয়ে যায় POMDP (partially observable MDP), আর agent একটি state নয়, সম্ভাব্য state-গুলোর ওপর একটি সম্ভাবনা-বণ্টন, অর্থাৎ belief state, হালনাগাদ করে চলে; POMDP ঠিকভাবে সমাধান করা সাধারণত অনেক বেশি কঠিন।

Planning-এর সঙ্গে সম্পর্ক

পর্ব ৪৯-এর classical planning-এ action-এর ফল নিশ্চিত, তাই উত্তর একটি action-এর ক্রম। MDP হলো planning under uncertainty, যার উত্তর একটি policy. অনিশ্চয়তা কম হলে plan আর replanning-ও চলে; অনিশ্চয়তা বেশি আর মাপা গেলে policy বেশি নির্ভরযোগ্য।

Reinforcement learning-এর দিকে সেতু

Value iteration চালাতে P(s′ | s, a) আর R পুরোপুরি জানা লাগে। Reinforcement learning (RL) এই ফাঁক পূরণ করে: agent পরিবেশে বারবার কাজ করে, পাওয়া reward আর পরের state থেকে নিজেই মান বা policy শেখে, সবচেয়ে পরিচিত পদ্ধতিগুলোর একটি Q-learning (Chris Watkins, ১৯৮৯), যা অভিজ্ঞতা থেকে সরাসরি Q(s, a) শেখে। নতুন সমস্যা আসে নতুন পথ চেষ্টা বনাম জানা পথে থাকা (exploration–exploitation). পর্ব ৫৫ (যন্ত্র কীভাবে শেখে) RL-এর জায়গা দেখাবে, আর পরের একটি কোর্স RL গভীরভাবে পড়াবে।

লাইব্রেরিতে MDP কেমন দেখায়, তা দেখতে একটি ছোট সত্যিকারের run: Farama Foundation-এর Gymnasium-এর FrozenLake, যেখানে বরফ পিছলে action-এর ফল অনিশ্চিত, আর library-টি transition table P সরাসরি দেয়, তাই এতে আমাদের নিজের value iteration চালানো যায়।

$ cd ~/bazarghar-ai
$ python frozen_vi.py
gymnasium 1.4.0
state 14, action RIGHT: [(0.33333333333333337, 14, 0, False), (0.3333333333333333, 15, 1, True), (0.33333333333333337, 10, 0, False)]
reset -> 0 {'prob': 1}
step  -> (1, 0, False, False, {'prob': 0.3333333333333333})
sweeps: 438
[[0.542 0.499 0.471 0.457]
 [0.558 0.    0.358 0.   ]
 [0.592 0.643 0.615 0.   ]
 [0.    0.742 0.863 0.   ]]
[['S' 'F' 'F' 'F']
 ['F' 'H' 'F' 'H']
 ['F' 'F' 'F' 'H']
 ['H' 'F' 'F' 'G']]
[['<' '^' '^' '^']
 ['<' '<' '<' '<']
 ['^' 'v' '<' '<']
 ['<' '>' 'v' '<']]

সত্যিকারের run (desktop, Python 3.14.4, gymnasium 1.4.0, NumPy 2.5.4; লেখার সময়ের version). frozen_vi.py-তে অংশ ৮-এর মতোই Bellman update, P[s][a] থেকে, γ = ০.৯৯. State ১৪-এ RIGHT চাপলে তিনটি ফল, প্রতিটি ১/৩: পিছলে একই জায়গায়, লক্ষ্যে (reward 1), বা ওপরে। env.step পাঁচটি জিনিস ফেরত দেয় (obs, reward, terminated, truncated, info) আর reset দুটি; পুরোনো OpenAI Gym-এ (০.২৬-এর আগে) step চারটি দিত, তাই পুরোনো টিউটোরিয়াল বা AI-এর লেখা কোড এখানে প্রায়ই ভেঙে যায়। শুরুর ঘর S-এ optimal তীর <, দেয়ালের দিকে: বাঁয়ে চাপলে পিছলে কখনো গর্তে (H) পড়া যায় না, শুধু ধীরে নিচে সরা যায়। গর্ত আর লক্ষ্যের ঘরের তীর অর্থহীন (সব Q = ০)। γ = ০.৯৯ প্রায় ১ বলে ৪৩৮টি sweep লেগেছে।

সৎ সতর্কতা

• Utility বের করা কঠিন। কারও utility function জিজ্ঞেস করে সরাসরি পাওয়া যায় না; প্রশ্ন সাজানোর ধরন বদলালেই উত্তর বদলায় (ভাবনার প্রশ্ন ২)।
• Model ভুল হতে পারে। ০.৬ বা ০.৫-এর মতো সম্ভাবনা অনুমান; ভুল সম্ভাবনায় “optimal” policy আসলে খারাপ হতে পারে। তাই sensitivity analysis আর ফল দেখে model হালনাগাদ (পর্ব ৫০-এর Bayes). পরিস্থিতি বদলালে (distribution shift) পুরোনো policy অচল হয়।
• কার ঝুঁকি, কার লাভ। Expected value গড় দেখে, কিন্তু কে খারাপ দিকটি বহন করেন তা দেখে না। দোকানের লাভ বাড়ানো policy রাইডারের নিরাপত্তা বা নির্দিষ্ট এলাকার গ্রাহকের সেবা কমিয়ে দিতে পারে। এই fairness-এর প্রশ্ন পর্ব ৭২ (দায়িত্বশীল AI-এর অভ্যাস) আলোচনা করবে।

১০ · AI-এর যুগে — সিদ্ধান্তের কোড আর সংখ্যা যাচাই

AI সহকারী দিয়ে decision tree বা value iteration লেখানো সহজ, আর কোড প্রায়ই চলেও। সমস্যা হলো ভুলগুলো চুপচাপ থাকে: ভুল সংখ্যা দিয়েও একটি সুন্দর policy-র তীর ছাপা হয়। সাধারণ ভুলগুলো হলো: terminal state-এর পরেও মান যোগ করা, একই sweep-এ নতুন আর পুরোনো মান গুলিয়ে ফেলা, γ = ১-এ loop থামার শর্ত ভুলে যাওয়া, পুরোনো Gym API (step-এর চারটি মান) লেখা, আর বানানো সম্ভাবনাকে তথ্য বলে দেখানো। নিচের prompt আর চেকলিস্ট এগুলো ধরতে সাহায্য করে।

AI-এর লেখা সিদ্ধান্তের কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• দুই state-এর একটি MDP বা ছোট decision tree হাতে হিসাব করে কোডের ফলের সঙ্গে মিলিয়েছি
• প্রতিটি state-এর সব transition probability-র যোগফল ১ কি না, আর terminal-এর মান ০ কি না দেখেছি
• প্রতিটি sweep-এ Δ ছাপিয়ে দেখেছি তা কমছে; loop-এ সর্বোচ্চ সংখ্যার সীমা আছে
• Reward, step cost আর γ কে ঠিক করেছেন, আর কেন, তা লিখে রেখেছি; দু-একটি বদলে policy কতটা পাল্টায় দেখেছি
• Library-র API নিজের installed version-এর অফিসিয়াল docs-এ মিলিয়েছি আর কোড চালিয়ে পুরো আউটপুট ও warning পড়েছি
• শুধু EV নয়, খারাপ ফলের মাত্রা আর কে তা বহন করবেন, তা-ও সিদ্ধান্তের রিপোর্টে রেখেছি