5.2.12
Intuition Ek-sentence ka ideaSingle-agent RL maan leta hai ki world ek stationary environment hai jise tum control karna seekhte ho. MARL us assumption ko tod deta hai: other agents bhi learn kar rahe hain , isliye "environment" tumhare neeche se khisak jaata hai. Core challenge hai non-stationarity — aaj ka best response kal galat ho sakta hai.
Definition Multi-Agent RLEk aisa setting jisme N joint action of everyone par depend karta hai. Ise Stochastic (Markov) Game ke roop mein formalize kiya gaya hai, jo MDP ka multi-agent generalization hai.
Definition Markov / Stochastic GameEk tuple ⟨ N , S , { A i } i = 1 N , P , { r i } i = 1 N , γ ⟩
N S A i i joint action hai a = ( a 1 , … , a N ) ∈ A = ∏ i A i P ( s ′ ∣ s , a ) joint action par depend karta hai,r i ( s , a ) i γ ∈ [ 0 , 1 )
Jab N = 1
YEH generalization KYUN? Kyunki real world mein (auctions, traffic, games, markets) outcomes sirf tumhari action par nahi balki sabki simultaneous action par depend karte hain. Ek single reward function conflicting ya shared incentives ko capture nahi kar sakti.
Intuition Reward structure ke hisaab se kyun split karein?Learning dynamics poori tarah is baat par depend karti hain ki agents ke interests align hote hain ya nahi.
Fully cooperative : sabhi agents ek reward share karte hain, r 1 = ⋯ = r N = r Fully competitive (zero-sum, N = 2 : r 1 = − r 2 Mixed / general-sum : kuch bhi beech mein (jaise traffic — zyaadatar cooperative lekin self-interested).
Definition Nash Equilibrium (NE)Ek joint policy π ∗ = ( π 1 ∗ , … , π N ∗ ) koi bhi agent apni policy unilaterally change karke improve nahi kar sakta :
V π i , π − i ∗ i ( s ) ≤ V π i ∗ , π − i ∗ i ( s ) ∀ i , ∀ π i , ∀ s . π − i i
Sirf "reward maximize karo" kyun nahi? Kyunki maximize karne ke liye koi single objective nahi hai — har agent ka apna V i fixed point jahan sab ek saath best-respond kar rahe hain.
Agent i best response fixed opponents π − i V i
Intuition MARL kyun mushkil hai, first principles seAgent i P ~ i ( s ′ ∣ s , a i ) = ∑ a − i ( ∏ j = i π j ( a j ∣ s ) ) P ( s ′ ∣ s , a i , a − i ) . opponents' policies π j π j P ~ i
Consequence: Markov property P ( s ′ ∣ s , a i ) stationary hona — wo assumption jo Q-learning ke convergence proof ko chahiye — violate ho jaati hai . Har agent ek moving target ko chase karta hai. Yeh sabse important cheez hai jo yaad rakhni chahiye.
Common mistake Steel-man: "Bas har agent ke liye independent DQN run karo."Kyun sahi lagta hai: har agent ke paas states, actions, rewards hain — normal MDP jaise dikhta hai, toh DQN plug in karo. Independent Q-Learning (IQL) toh ek common baseline bhi hai.
Kyun toot jaata hai: upar ki derivation dikhati hai ki P ~ i replay buffer un transitions ko store karta hai jo purani opponent policies se generate hue the — stale, misleading data.
Fix: ya toh (a) Centralized Training with Decentralized Execution (CTDE) ke zariye information share karo, ya (b) critic ko joint action par condition karo, ya (c) replay ko chota/prioritize karo taaki stale data discard ho.
Definition Centralized Training, Decentralized Execution (CTDE)Training ke dauran ek centralized critic global state aur joint action a Execution ke dauran har agent sirf apni decentralized policy π i ( a i ∣ o i ) o i
Kyun kaam karta hai: critic Q i ( s , a ) full joint action ka function hai, isliye uske perspective se koi hidden non-stationarity nahi hai — sabke actions explicit input hain. Yahi MADDPG , COMA , QMIX ki backbone hai.
Intuition Factorize kyun karein?Fully cooperative team mein hum ek team value Q t o t apne Q i
Worked example Example 1 — Matrix game Nash (competitive)Rock–Paper–Scissors, zero-sum. NE ke liye kyun solve karein? Koi pure best response exist nahi karta (koi bhi pure choice exploit ho jaati hai).
Yeh step kyun: maano opponent ( p R , p P , p S ) p S − p P p R = p P = p S = 1/3 Result: unique NE dono ke liye uniform random ( 1/3 , 1/3 , 1/3 ) 0
Worked example Example 2 — IQL kyun diverge karta haiEk coordination game mein do agents ko reward ke liye same action choose karni hoti hai. Agent 1 ke replay buffer mein purane episodes hain jahan Agent 2 ne action A choose kiya tha. Agent 1 seekhta hai "A accha hai."
Yeh step kyun: isi beech Agent 2 ne B switch kar liya. Agent 1 ka stored Q Fix: centralized critic Q ( s , a 1 , a 2 ) pair se explain hota hai, koi staleness nahi.
Worked example Example 3 — QMIX consistency checkMaano Q t o t = Q 1 + Q 2 = 1 ≥ 0
Yeh step kyun: arg max a 1 , a 2 ( Q 1 + Q 2 ) = ( arg max Q 1 , arg max Q 2 ) Contrast: Q t o t = Q 1 ⋅ Q 2 Q i < 0 nonnegative weights force karta hai .
Recall Feynman: 12-saal ke bacche ko explain karoSocho tum aur tumhare doston ek hi video game ek saath khel rahe ho, aur tum mein se har ek abhi bhi khelna seekh raha hai. Jab bhi tumhara dost better hota hai, game tumhe alag lagti hai — kyunki jo kaam karta hai wo depend karta hai ki wo kya karte hain. Toh tum akele practice nahi kar sakte yeh maante hue ki sab same rahenge; tum galat lessons seekhoge. Clever trick (CTDE) yeh hai: practice karte waqt, ek coach jo sabke moves dekh sakta hai har player ki madad karta hai; lekin real match mein, har player akele faisla karta hai sirf woh dekhkar jo wo dekh sakte hain.
"Nash Sees Non-stationary Crowds Centrally" →
N ash equilibrium (goal), S tochastic game (framework), N on-stationarity (the problem), C ooperative/competitive/mixed (regimes), C TDE (the fix).
#flashcards/ai-ml
Markov (stochastic) game ko kaunsa tuple define karta hai? ⟨ N , S , { A i } , P , { r i } , γ ⟩
MARL ki core difficulty kya hai? Non-stationarity — har agent ka effective environment badalta hai jab doosre agents learn karte hain.
Dikhao kyun agent i Uska effective transition P ~ i ( s ′ ∣ s , a i ) = ∑ a − i ∏ j = i π j ( a j ∣ s ) P ( s ′ ∣ s , a i , a − i )
Markov game mein Nash equilibrium define karo. Ek joint policy jahan koi bhi agent apni policy unilaterally change karke apna V i
CTDE ka matlab kya hai aur ise kyun use karte hain? Centralized Training, Decentralized Execution — ek centralized critic joint actions dekhta hai (stationary target) jabki agents local observations par execute karte hain.
MARL mein independent DQN (IQL) kyun toot jaata hai? Convergence proof stationary transitions assume karta hai; opponents ka learning us assumption ko violate karta hai, aur replay buffers stale transitions store karte hain.
IGM condition state karo. Q t o t Q i
QMIX IGM kaise guarantee karta hai? Mixing network ko monotonic banake: ∂ Q t o t / ∂ Q i ≥ 0 i
MADDPG ka centralized critic policy gradient do. ∇ θ i J i = E [ ∇ θ i μ i ( o i ) ∇ a i Q ϕ i ( s , a 1 , … , a N ) ∣ a i = μ i ]
Rock-Paper-Scissors ka NE kya hai? Uniform mixed strategy ( 1/3 , 1/3 , 1/3 ) 0
MARL mein teen reward regimes kaunse hain? Fully cooperative (shared r r 1 = − r 2
Markov Decision Process — MARL is mein reduce ho jaata hai jab N = 1 Q-Learning — iski stationarity assumption wahi hai jo MARL todata hai.Policy Gradient Methods — MADDPG DPG ko joint critics tak generalize karta hai.Game Theory & Nash Equilibrium — solution concept provide karta hai.Actor-Critic Methods — CTDE critic ek centralized actor-critic hai.Self-Play — competitive MARL ke liye training method (AlphaGo, OpenAI Five).
