পাঠ ০৩ · ৩২-এর মধ্যে · মডিউল ১
Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / MDP

Markov Decision Process — RL-এর গাণিতিক ভিত্তি

Markov Decision Process — the formal framework of RL
৮ মিনিট পড়া উচ্চ · Advanced Math-heavy

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

  • MDP-এর পাঁচ component — formal definition
  • Markov property — কেন এত গুরুত্বপূর্ণ
  • Policy — deterministic বনাম stochastic
  • Discount factor γ-এর গাণিতিক ও philosophical তাৎপর্য

১ · MDP — পাঁচটি অংশ

RL-এর সব problem-কে একই গাণিতিক frame-এ ফেলা যায় — সেটা হলো MDP। ১৯৫০-এর দশকে Richard Bellman এই formalism develop করেন।

MDP = $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$

১) $\mathcal{S}$ — state space (সম্ভাব্য সব state)
২) $\mathcal{A}$ — action space (সম্ভাব্য সব action)
৩) $P(s' \mid s, a)$ — transition probability
৪) $R(s, a, s')$ — reward function
৫) $\gamma \in [0, 1]$ — discount factor

২ · Markov property — "smriti-শূন্য" ভবিষ্যৎ

MDP-এর "M" — Markov। Andrey Markov (১৯০৬) প্রস্তাব করেছিলেন:

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots, s_0) = P(s_{t+1} \mid s_t, a_t)$$

মানে — current state $s_t$ ও current action $a_t$ — ভবিষ্যৎ predict করতে যথেষ্ট। এর আগের কোনো history-র দরকার নেই।

দাবা — Markov। শুধু বর্তমান board position দেখলেই যথেষ্ট, কিন্তু কোন order-এ এই অবস্থানে এলো — গুরুত্বহীন।

Stock trading — সাধারণ-ভাবে Markov নয়। gradient, volatility, sentiment — সব past-নির্ভর। তাই এই tasks-এ state augmentation দরকার (last 30 days price)।

৩ · State space ও action space

State space $\mathcal{S}$:

  • Finite discrete: Tic-tac-toe (~৫,০০০ states), GridWorld (১৬ states)।
  • Infinite discrete: অসীম queue length।
  • Continuous: robot joint position (real numbers)।
  • High-dimensional: Atari frame (১৬৭৭৭২১৬-D pixel space)।

Action space $\mathcal{A}$:

  • Discrete: {up, down, left, right}।
  • Continuous: robot torque ∈ [-1, 1]।
  • State-dependent: দাবা-এ legal moves position-নির্ভর।

৪ · Transition function $P$

$$P(s' \mid s, a) = \Pr[s_{t+1} = s' \mid s_t = s, a_t = a]$$

গুরুত্বপূর্ণ constraint: $\sum_{s'} P(s' | s, a) = 1$ — probability distribution।

Deterministic: $P$ degenerate — একটি specific $s'$-এ probability ১। Stochastic: ছড়ানো।

৫ · Reward function ও return

Reward function-এর তিনটি common form:

  • $R(s)$ — শুধু state-এর উপর।
  • $R(s, a)$ — state-action pair-এর উপর।
  • $R(s, a, s')$ — transition-এর উপর। সবচেয়ে general।

Return ($G_t$): timestep $t$ থেকে শেষ পর্যন্ত discounted future reward —

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$$

৬ · Discount factor γ — কেন দরকার

γ-এর তিনটি ব্যাখ্যা — সব valid:

  • গাণিতিক: $\gamma < 1$ ছাড়া infinite-horizon-এ return ∞ হতে পারে।
  • অর্থনৈতিক: "আজকের ১০০ টাকা > কালকের ১০০ টাকা" — interest rate analogy।
  • Behavioral: agent কতটা far-sighted হবে তার নিয়ন্ত্রণ। γ=0 → শুধু এই মুহূর্ত। γ→1 → far future-ও সমান গুরুত্ব।
γ একটি hyperparameter — task-নির্ভর। Atari-এ ০.৯৯, Go-এ ১.০ (terminal বাদে), continuous control-এ ০.৯৫-০.৯৯।
একটি ক্ষুদ্র MDP — তিন state, দুই action $s_1$ $s_2$ $s_3$ $s_4$ a₁, P=0.7 R=+1 a₁, P=0.3 R=-1 a₂ R=+10 a₂ R=0 terminal এক action অনেক outcome দিতে পারে (stochastic)। reward প্রতিটি transition-এ। $s_4$ terminal — episode শেষ। policy বলে: প্রতি state-এ কোন action।
একটি ক্ষুদ্র MDP — চার state, দুই action। প্রতিটি transition-এ probability ও reward। policy বলে কোন state-এ কী action নেব।

৭ · Policy — agent-এর behavior

Policy $\pi$ — state থেকে action-এ একটি mapping। দু'ভাবে:

Deterministic: $\pi(s) = a$ (একটি specific action)।
Stochastic: $\pi(a \mid s) = \Pr[a_t = a \mid s_t = s]$ (distribution)।

RL-এর লক্ষ্য — optimal policy $\pi^*$ খোঁজা যা প্রতিটি state থেকে expected return maximize করে:

$$\pi^* = \arg\max_\pi \mathbb{E}_\pi \left[ \sum_{t=0}^\infty \gamma^t R_{t+1} \right]$$

৮ · Python-এ একটি ক্ষুদ্র MDP

Python · Tabular MDP 
import numpy as np

# Sutton-Barto-র classic Student MDP-এর সরল রূপ
# States: 0=Class, 1=Pub, 2=Pass, 3=Sleep(terminal)
# Actions: 0=Study, 1=Skip
n_states, n_actions = 4, 2

# P[s][a] = list of (prob, next_state, reward)
P = {
    0: {  # Class
        0: [(1.0, 2, +5)],         # Study → Pass +5
        1: [(0.8, 1, -1), (0.2, 3, -2)],  # Skip → Pub -1 বা Sleep -2
    },
    1: {  # Pub
        0: [(0.5, 0, +0), (0.5, 2, +1)],  # Study (drunk) → Class বা Pass
        1: [(1.0, 3, -5)],         # Skip → Sleep -5
    },
    2: {  # Pass
        0: [(1.0, 3, +10)],        # → Sleep (terminal) +10
        1: [(1.0, 3, +10)],
    },
    3: {0: [(1.0, 3, 0)], 1: [(1.0, 3, 0)]},  # Sleep terminal
}

# Random policy চালাই
gamma = 0.9
np.random.seed(0)
state = 0
G = 0
for t in range(20):
    a = np.random.randint(2)
    transitions = P[state][a]
    probs = [tr[0] for tr in transitions]
    idx = np.random.choice(len(transitions), p=probs)
    _, next_s, r = transitions[idx]
    G += (gamma ** t) * r
    print(f"t={t} s={state} a={a} → s'={next_s} r={r}")
    state = next_s
    if state == 3:
        print(f"Episode done. Discounted return G = {G:.2f}")
        break

    


    

      এটাই tabular MDP-এর simulator। বাস্তব MDP তে state space বিশাল — table-এ ফিট হয় না, তাই function approximation (পরের পাঠে DQN)।
    


    
৯ · γ-এর প্রভাব দেখা


    

      

        
        Python · Discount sensitivity
      

      
import numpy as np

rewards = [1, 1, 1, 100]  # ৪র্থ step-এ jackpot
for gamma in [0.0, 0.5, 0.9, 0.99, 1.0]:
    G = sum((gamma**t) * r for t, r in enumerate(rewards))
    print(f"γ={gamma}: G = {G:.2f}")
# γ=0 → শুধু এই মুহূর্তের ১
# γ=0.9 → far reward অর্ধেক discount
# γ=0.99 → near-far সমান গুরুত্ব

      

        
        
      

      

    


    

      Output দেখলে বুঝবেন — γ ছোট হলে agent "myopic" (ক্ষুদ্রদৃষ্টি), γ বড় হলে agent "patient"। RL agent-এর "personality" এই hyperparameter দিয়ে।
    


  


  

    
    
  


  

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


    

      
        প্র ০১
        Markov property কেন এত গুরুত্বপূর্ণ — এটা ছাড়া কী algorithm কাজ করে না?
      
      

        

          Markov property — RL-এর সব theory-র backbone। ছাড়া কাজ করে না কারণ:
        

        
    
          
  • Bellman equation: $V(s) = \mathbb{E}[r + \gamma V(s')]$ — এটি ধরে নেয় current state ভবিষ্যৎ predict-এ যথেষ্ট। history দরকার হলে এই recursive form ভেঙে যায়।
    • 
          
  • Q-learning convergence: finite-state Markov assumption-এ optimal Q* convergence প্রমাণিত। non-Markov-এ প্রমাণ নেই।
    • 
          
  • Tabular methods: Q-table = $|S| \times |A|$ entries। non-Markov হলে $|S|$-এ history থাকতে হয় — exponential explosion।
    • 
        

        

          কীভাবে non-Markov fix:
        

        
    
          
  • State-এ history append (frame stacking)।
    • 
          
  • Belief state — POMDP-এ probabilistic state estimate।
    • 
          
  • RNN/Transformer policy — implicit memory।
    • 
          
  • R2D2 — DeepMind-এর recurrent DQN, hidden state replay।
    • 
        

        

          মূল উপলব্ধি: "Markov" একটি modeling choice — সঠিক state representation চেষ্টা। যথাযথ representation থাকলে Markov হয়, না থাকলে algorithm fail।
        

      

    


    

      
        প্র ০২
        Discount factor γ-এর জায়গায় average reward formulation আছে — কোনটি ভাল কখন?
      
      

        

          দু'টি RL formulation:
        

        
    
          
  • Discounted (γ < 1): $J = \mathbb{E}[\sum_t \gamma^t r_t]$।
    • 
          
  • Average reward: $\rho = \lim_{T \to \infty} \frac{1}{T} \mathbb{E}[\sum_t r_t]$।
    • 
        

        

          Discounted-এর সুবিধা:
        

        
    
          
  • সবসময় convergent।
    • 
          
  • Episodic ও continuing — দু'টোতেই কাজ করে।
    • 
          
  • Bellman-এর fixed point unique (contraction)।
    • 
          
  • সব mainstream algorithm এতে।
    • 
        

        

          Discounted-এর সমস্যা:
        

        
    
          
  • γ একটি artificial parameter — task-এ "discount" থাকার দরকার নাও থাকতে পারে।
    • 
          
  • Long-horizon task-এ γ → 1 হলে variance বিস্ফোরণ।
    • 
          
  • Optimal policy γ-নির্ভর — γ পাল্টালে policy পাল্টায়।
    • 
        

        

          Average reward-এর সুবিধা:
        

        
    
          
  • Continuing task-এ "rate" বেশি natural — server throughput, factory output।
    • 
          
  • γ নেই — কম hyperparameter।
    • 
          
  • Long-term asymptotic performance optimal।
    • 
        

        

          Average reward-এর সমস্যা:
        

        
    
          
  • Bellman equation আলাদা ($V(s) - V(s') = r - \rho$)।
    • 
          
  • Non-ergodic MDP-এ undefined।
    • 
          
  • Standard library সাপোর্ট কম।
    • 
        

        

          কখন কোনটি:
        

        
    
          
  • Game / robot manipulation — episodic, discounted।
    • 
          
  • Server allocation, queueing, finance — average reward natural।
    • 
          
  • Practice-এ — discounted γ ≈ 1 দিয়ে average-এর approximation কাজ করে।
    • 
        

      

    


    

      
        প্র ০৩
        Continuous state space — কোটি কোটি state। কীভাবে handle করা যায়?
      
      

        

          Tabular methods (Q-table) finite, small state space-এ চলে। Continuous-এ ভেঙে পড়ে। সমাধান:
        

        

          (১) Discretization: continuous state-কে bin-এ ভাগ। সরল কিন্তু curse of dimensionality।
        

        

          (২) Linear function approximation: $V(s) \approx \theta^T \phi(s)$ — feature engineering।
        

        

          (৩) Neural network (DQN, etc.): $V_\theta(s)$, $Q_\theta(s, a)$ — universal approximator।
        

        

          (৪) Policy parameterization: $\pi_\theta(a|s)$ — Gaussian, beta, deterministic mapping।
        

        

          চ্যালেঞ্জ deep RL-এ:
        

        
    
          
  • Convergence guarantee হারায় — "deadly triad" (off-policy + bootstrap + function approx)।
    • 
          
  • Stability tricks — replay buffer, target networks।
    • 
          
  • Hyperparameter sensitivity বাড়ে।
    • 
        

        

          মূল উপলব্ধি: Deep RL = MDP framework + neural network। সব algorithmic complexity neural net-কে stably train করার জন্য।
        

      

    


    

      
        প্র ০৪
        একটি food delivery startup — riders allocate করতে হয়। MDP হিসেবে frame করুন।
      
      

        

          State $\mathcal{S}$:
        

        
    
          
  • প্রতিটি rider-এর position, current load।
    • 
          
  • Pending orders (location, food type, deadline)।
    • 
          
  • Time of day, weather, traffic।
    • 
          
  • Restaurant queue length।
    • 
        

        

          Action $\mathcal{A}$: কোন order কোন rider-কে।
        

        
    
          
  • Discrete (rider count × order count)।
    • 
          
  • Combinatorial — multiple assignment per step।
    • 
          
  • Hierarchical decomposition দরকার (cluster → individual)।
    • 
        

        

          Reward $R$:
        

        
    
          
  • + delivery fee earned।
    • 
          
  • - delivery time-এ delay penalty।
    • 
          
  • - food temp loss।
    • 
          
  • - rider fatigue (hours worked)।
    • 
        

        

          Transition $P$:
        

        
    
          
  • Stochastic — traffic, weather, restaurant prep time।
    • 
          
  • Order arrival rate Poisson-like।
    • 
          
  • Cancellation probability।
    • 
        

        

          γ: ০.৯৯ — far-future order-এর প্রভাব রাখা।
        

        

          চ্যালেঞ্জ:
        

        
    
          
  • Markov property: rider history (যেমন recent breaks) state-এ থাকা চাই।
    • 
          
  • Multi-agent — riders coordinate, কিন্তু centralized agent বানানো সম্ভব।
    • 
          
  • Real-time constraint — sub-second decision।
    • 
          
  • Exploration cost — random assignment customer experience নষ্ট করে।
    • 
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        Markov কি? দেখুন কোনটি Markov: (ক) দাবা position। (খ) Stock-এর current price। (গ) চিকিৎসায় রোগীর current symptoms।
        
    
          
          
    
            
      
              
    • (ক) হ্যাঁ — board অবস্থা সব তথ্য ধারণ করে।
      • 
              
    • (খ) না — trend, momentum past থেকে আসে।
      • 
              
    • (গ) আংশিক — current symptoms-এ অনেক info, কিন্তু history (past treatments, allergies) দরকার। POMDP।
      • 
            
    
          
    
        
    
      
    2. 

      
  2. 
        Return হিসাব: $\gamma=0.9$, $r_1=2, r_2=4, r_3=8$ (terminal)। $G_0$ কত?
        
    
          
          
    
            
    $G_0 = 2 + 0.9 \cdot 4 + 0.81 \cdot 8 = 2 + 3.6 + 6.48 = 12.08$
    
          
    
        
    
      
    3. 

      
  3. 
        Policy বানান: উপরের Student MDP-এ — কোন policy "always Study" বনাম "always Skip" — কোনটি ভালো? simulation চালিয়ে দেখুন।
        
    
          
          
    
            
    "Always Study" → Class → Pass → Sleep, return ≈ 5 + 0.9·10 = 14। "Always Skip" → Class → Pub/Sleep, কম return।
    
            
    তবে stochastic — variance check করতে ১০০ episode-এ গড় নিন।
    
          
    
        
    
      
    4. 
    

  


  

    
 আরও পড়ুন

    
  







  
   এই পাঠে ভুল পেয়েছেন? জানান





  
    
 পূর্ববর্তী পাঠ

    
পাঠ ০২ · Agent & Environment