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

Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / Multi-agent RL

Multi-agent RL — সহযোগিতা ও প্রতিদ্বন্দ্বিতা

Multi-agent RL: cooperation, competition, mixed

১০ মিনিট পড়া মাঝারি · Intermediate MADDPG sketch

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

Multi-agent setting-এ non-stationarity ও credit assignment problem
Cooperative, competitive, mixed game-এর গাণিতিক formalism
MADDPG architecture — কেন centralized training + decentralized execution
OpenAI Five ও AlphaStar — production-scale multi-agent achievements

১ · Multi-agent — single-agent থেকে কেন কঠিন?

এতদিন আমরা ধরে এসেছি — একটি agent, একটি environment, fixed dynamics. কিন্তু বাস্তবে: রাস্তার গাড়ি একে অপরের প্রতিক্রিয়ায় চলে; বাজারে দু'জন trader একসাথে শিখছে; football-এর ১১ জন প্লেয়ার coordinate করে। এই সব multi-agent problem.

মূল challenge — একজন agent-এর দৃষ্টিতে environment non-stationary. কারণ অন্য agent-ও শিখছে, তাদের policy বদলাচ্ছে। যা গতকাল optimal ছিল, আজ নয়। এটা সরাসরি Q-learning-এর convergence guarantees ভাঙে।

Non-stationarity problem

Single-agent: $P(s'|s,a)$ ও $R(s,a)$ স্থির। Q-learning convergence proof valid.
Multi-agent: $P$ ও $R$ অন্য agents-এর policy-এর উপর নির্ভর। তাদের policy বদলালে environment-ও বদলে। Standard RL guarantees ভেঙে পড়ে।

ভাবুন আপনি বাচ্চাদের shoot-out খেলছেন। যদি opponent fixed strategy ব্যবহার করে — আপনি counter শিখলে জিতবেন। কিন্তু opponent-ও শিখছে — আপনার counter দেখে সে নিজে adjust. এটাই multi-agent. আপনাদের দু'জনের policy একসাথে evolve করে — সম্ভবত একটি equilibrium-এ থামে, সম্ভবত forever cycle.

২ · গাণিতিক formalism — Markov Game

MDP-র extension: Markov Game বা Stochastic Game. $N$ agents:

State $s \in \mathcal{S}$ — সবাই দেখে (full obs) বা নিজস্ব $o_i$ (partial).
Action: joint $\mathbf{a} = (a_1, \ldots, a_N)$।
Transition: $P(s' | s, \mathbf{a})$।
Reward: প্রতিটি agent-এর জন্য $r_i(s, \mathbf{a})$।

তিন category:

Fully cooperative: $r_1 = r_2 = \ldots = r_N$ — একই reward. গোল: team return maximize.
Fully competitive (zero-sum, ২ agent): $r_1 + r_2 = 0$। AlphaZero, পোকার।
Mixed (general-sum): partial cooperation. Traffic, market, social dilemma.

৩ · Solution concept — Nash equilibrium

Multi-agent-এ "optimal" definition tricky. সবচেয়ে ব্যবহৃত: Nash Equilibrium — কোনো agent-ই unilaterally policy পরিবর্তন করে gain করতে পারে না: $$V_i(\pi_i^*, \boldsymbol{\pi}_{-i}^*) \geq V_i(\pi_i, \boldsymbol{\pi}_{-i}^*) \quad \forall \pi_i, \forall i$$

Two-player zero-sum-এ Nash সবসময় আছে (Minimax theorem). General-sum-এ multiple Nash থাকতে পারে — কোনটি বাছবেন? এটি অন্যতম unsolved problem.

Cooperative games-এ আমরা সাধারণত Pareto-optimal equilibrium চাই — যেখানে কেউ improve করতে পারে না অন্যকে damage না করে। Nash-এ সবাই Pareto-suboptimal-এ stuck হতে পারে — Prisoner's Dilemma-র মতো।

৪ · Naive approach — Independent Learners

সবচেয়ে সহজ idea: প্রতিটি agent নিজে standalone Q-learning/PPO চালায়, অন্যদের environment-এর অংশ ভাবে। কাজ করে?

সরল cooperative game: অনেক সময় কাজ করে — ছোট state space, predictable opponent.
Competitive বা complex coop: ভেঙে পড়ে — non-stationarity আগের point থেকে।
Credit assignment: team-wide reward এলে — কে contribute করল কেউ জানে না।

সমাধানগুলো এই দুর্বলতাগুলো address করে।

৫ · CTDE — Centralized Training, Decentralized Execution

Multi-agent RL-এর ১০ বছরের সবচেয়ে useful idea. Train-এর সময় — সবাই একে অপরের state, action দেখে; এটা stationary environment তৈরি করে। Execution-এ — শুধু নিজস্ব observation. দু'টি নাম: MADDPG (Lowe et al., ২০১৭) ও QMIX (Rashid et al., ২০১৮)।

MADDPG-এর critic প্রতিটি agent-এর জন্য:

$$Q_i^\mu(s, a_1, a_2, \ldots, a_N) — \text{সবার action জানে}$$

Actor (deployment): $\mu_i(o_i)$ — শুধু নিজস্ব observation.

প্রতিটি critic-এর target — অন্য agents-এর target policy দিয়ে compute. Replay buffer-এ joint $(s, a_1, \ldots, a_N, r_1, \ldots, r_N, s')$ store.

৬ · MADDPG PyTorch sketch

Python · PyTorch · MADDPG core

import torch, torch.nn as nn
import torch.nn.functional as F

N = 3                           # number of agents
obs_dim, act_dim = 18, 5

class Actor(nn.Module):
    def __init__(self):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(obs_dim, 128), nn.ReLU(),
            nn.Linear(128, 128),     nn.ReLU(),
            nn.Linear(128, act_dim), nn.Tanh(),
        )
    def forward(self, o):
        return self.net(o)

class CentralCritic(nn.Module):
    """Sees ALL agents' obs and actions."""
    def __init__(self):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(N * (obs_dim + act_dim), 256), nn.ReLU(),
            nn.Linear(256, 256),                     nn.ReLU(),
            nn.Linear(256, 1),
        )
    def forward(self, all_obs, all_acts):
        x = torch.cat([all_obs.flatten(-2), all_acts.flatten(-2)], -1)
        return self.net(x).squeeze(-1)

actors  = [Actor() for _ in range(N)]
critics = [CentralCritic() for _ in range(N)]
opt_a   = [torch.optim.Adam(a.parameters(), lr=1e-3) for a in actors]
opt_c   = [torch.optim.Adam(c.parameters(), lr=1e-3) for c in critics]
gamma   = 0.95

def update(batch, i):
    """One MADDPG update for agent i."""
    o, a, r_i, o_next = batch    # joint obs/acts; r_i is agent i's reward
    # 1) Critic loss
    with torch.no_grad():
        a_next = torch.stack([actors[j](o_next[..., j, :]) for j in range(N)], dim=-2)
        y = r_i + gamma * critics[i](o_next, a_next)
    q = critics[i](o, a)
    loss_c = F.mse_loss(q, y)
    opt_c[i].zero_grad(); loss_c.backward(); opt_c[i].step()

    # 2) Actor loss — agent i's policy gradient
    a_i_pred = actors[i](o[..., i, :])
    a_pred = a.clone()
    a_pred[..., i, :] = a_i_pred
    loss_a = -critics[i](o, a_pred).mean()
    opt_a[i].zero_grad(); loss_a.backward(); opt_a[i].step()
    return float(loss_c), float(loss_a)

প্রতিটি agent-এর critic global view দেখে — তাই environment "stationary" থেকে যায় (অন্যদের policy explicitly modeled). Actor decentralized — deployment-এ realistic. Cooperative + competitive + mixed সব setting-এ একই code.

৭ · Self-play scaled — OpenAI Five ও AlphaStar

OpenAI Five (২০১৮): Dota-2 — ৫v৫ team game. প্রতিটি hero একটি LSTM-based PPO agent. ৬৪০ unique skill, ১১৭ heroes, partial observability. প্রায় ৪৫,০০০ বছরের simulated play (১২৮,০০০ CPU + ২৫৬ GPU). ২০১৯-এ World Champion OG-কে ২-০ হারায়।

Surgery: game patch হলে — full retrain না করে network "surgery". Old weights extend.
Team spirit τ: reward = $(1-\tau) r_i + \tau \bar{r}$। Initially τ low (selfish), ক্রমে বাড়ে (team). Curriculum বুদ্ধিমত্তা।

AlphaStar (২০১৯): StarCraft-II — ১v১ RTS, partial obs, real-time, action space বিশাল। DeepMind সমাধান:

Imitation learning থেকে শুরু — replay file থেকে human strategy seed.
League training: Main + Exploiter + League agents — pure self-play-র rock-paper-scissors এড়াতে।
Result: Grandmaster level — top ০.২%.

CTDE paradigm — training-এ centralized critic stationarity দেয়, deployment-এ decentralized actor practical.

৮ · Emergent behaviors

Multi-agent training-এর সবচেয়ে আকর্ষণীয় দিক — pre-programmed না হওয়া complex behavior emerge হয়:

Hide-and-seek (OpenAI, ২০১৯): agents emergence-এ tool use শিখে — ramp ব্যবহার করে wall block, opponent বাক্সে আটকানো। ৬টি distinct strategy auto-emerge.
Capture the flag (DeepMind): coordination — defenders + attackers দল ভাগ।
OpenAI Five: "5-man push", "split push", lane rotation — Dota community-র সব strategy.

Reward design = ethics: mixed-motive game-এ — selfish reward দিলে agents social dilemma-তে stuck (Tragedy of Commons). Sequential Social Dilemma research এ দেখায় — naive RL agents pollute, hoard, betray. Real-world deployment-এ কী reward function বাছছেন — এটাই agency এর choice.

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

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ OpenAI Five-এর "team spirit τ" কেন প্রথমে কম, পরে বেশি? উল্টো করলে কী হত?

চমৎকার curriculum design question.

Setup: $r_i^{\text{shaped}} = (1-\tau) r_i^{\text{individual}} + \tau \bar{r}^{\text{team}}$, $\tau \in [0, 1]$।

(১) Individual reward signal denser: Dota-তে kill, last-hit, gold — প্রতিটি hero নিজে measurable. Team win rare event (গেমের শেষে)। প্রথমে individual signal দিলে — gradient signal density বেশি, learning fast.

(২) Skill before strategy: agent প্রথমে নিজের hero চালানো শিখে — last-hit, dodge skill, item usage. সেটা না জানলে team coordination অর্থহীন। Same as football — passing শেখার আগে dribbling.

(৩) Selfish exploration: early training-এ — selfish behavior diverse. সব agent নিজস্ব niche develop করে। পরে team-অনুকূলে adjustment. Diversity → coordination.

(৪) Why increase τ later: skill শেখার পর — team-fight, objective control, lane rotation — সব team-game. সেখানে individual reward misleading হতে পারে (e.g., farm করতে গেলে team late-game suffer).

উল্টো করলে:

প্রথমে $\tau = 1$ (pure team): team win rare → gradient sparse → random behavior dominate. Agent কোনো skill শেখে না।
Late game τ=0 (selfish): high-skill agents team-fight ছেড়ে farm করবে। Lose by sabotage.

(৫) Curriculum learning theory: "Easy first, hard later" — Bengio (২০০৯)। Multi-agent-এ — individual goal easy, team coordination hard. OpenAI Five সেই theory-র concrete demo.

(৬) Generalization: এই trick অন্য domain-এ — team robotics-এ — apply করা হচ্ছে। StarCraft-এ AlphaStar similar curriculum.

মূল উপলব্ধি: Multi-agent reward shaping = curriculum. Single-agent-এ আমরা environment difficulty বাড়াই; multi-agent-এ — coordination intensity.

প্র ০২ Independent Q-learning (IQL) তো ভেঙে পড়ার কথা — তবু কেন কখনো কখনো কাজ করে? Centralized critic বাধ্যতামূলক না হলে কখন?

এটি একটি subtle empirical truth — IQL অনেক জায়গায় surprising-ভাবে কাজ করে।

কখন IQL কাজ করে:

Loosely-coupled agents: traffic-এ গাড়ি — পাশের গাড়ি ছাড়া অন্যদের influence কম। Local interaction → IQL fine.
Slowly-changing opponents: opponents যদি ধীরে শিখে — moving target slow enough to track.
Symmetric agents: সব agent একই (homogeneous) — একে অপরের best response naturally align.
Cooperative + dense reward: credit assignment problem কম severe.

কখন ভেঙে পড়ে:

Tightly-coupled coordination: Hanabi, StarCraft — exact joint action important. IQL miss.
Adversarial: opponent দ্রুত evolve — moving target fast.
Sparse reward: credit assignment-এ explicit signal need.
Heterogeneous roles: different abilities, asymmetric. Single agent ভাবা যায় না।

Empirical evidence:

Tampuu et al. (২০১৭) — ALE-এ Pong/Tag-এ IQL surprisingly competitive.
de Witt et al. (২০২০) — "Independent PPO" simple SMAC tasks-এ MAPPO-র কাছাকাছি।
Foerster (Hanabi) — IQL ব্যর্থ; QMIX, BAD প্রয়োজন।

Practical advice:

সবসময় IQL baseline চালান — সরল, fast.
যদি ভাল-ই — production deploy. Centralized critic complexity-overhead দরকার নেই।
IQL stuck হলে — MADDPG/MAPPO/QMIX try.
Final option — parameter sharing, attention-based communication.

(বোনাস insight) Modern MAPPO (Yu et al., ২০২২) দেখায় — independent PPO-র সাথে centralized critic যোগ করলেই অনেক benchmark-এ SOTA. ভারী QMIX-এর প্রয়োজন রহিত।

মূল কথা: Theory বলে IQL fail করার কথা — practice often disagrees. Empirical baselines first, theory-driven complexity only when needed.

প্র ০৩ OpenAI Five জিতে গেলেও — পরে disabled হয়েছে। AlphaStar মানুষ-পর্যায়ে দাঁড়িয়েই থেমেছে। Production multi-agent RL এত rare কেন?

চমৎকার critical question — research vs deployment-এর বিশাল gap.

(১) Compute budget অসহনীয়: OpenAI Five — ১২৮,০০০ CPU + ২৫৬ GPU, প্রতি ২ সেকেন্ডে full game-day সিমুলেট। AlphaStar — ১৬ TPU × ৪৪ দিন × ১২ agents. Cost millions-of-dollars. Recurring revenue-এর pathway অস্পষ্ট।

(২) Brittleness: Adversarial example — Adam Gleave-এর ২০২০ paper দেখায় AlphaStar-কে "weird" opening দিয়ে break. Trained agent narrow distribution-এ — out-of-distribution opponent fail. Production-এ unacceptable.

(৩) Debugging hard: single-agent debug-এ তো কষ্ট, multi-agent-এ ১০×। কোন agent-এর কারণে fail? Reward shaping change করলে কী হবে — কেউ জানে না।

(৪) Game-specific engineering: Dota-এর প্রতিটি hero-এর জন্য hand-crafted obs encoding. Patch এলে — extensive surgery. Generality কম।

(৫) Limited revenue model: "Beat humans" novelty wears off. Consumer entertainment-এ — humans চায় opponent fun, not impossibly strong. Twitch demonstrations দু'বছর viral, তারপর forgotten.

(৬) Where multi-agent IS in production:

Algorithmic trading: hedge funds — কিন্তু private, very hidden.
Ad auction bidding: Google, Meta — implicit market RL.
Recommendation systems: users + items + advertisers একটি multi-agent equilibrium.
Robot fleet (Amazon warehouse): hundreds of robots coordinate path.
Power grid balancing: distributed generators — early-stage MARL.

(৭) Scientific use: AI safety research — agent-agent dynamics study, mesa-optimization.

মূল উপলব্ধি: Game-AI demo headline-grabbing — কিন্তু true production multi-agent quietly সবখানে। Bidding, routing, market — প্রতিটিতে। শুধু "RL" label-এ আসে না।

প্র ০৪ আপনি Dhaka-র traffic light controller-এর জন্য multi-agent RL design করছেন — ১০০টি signal একসাথে। Architecture কী হবে?

চমৎকার applied scenario.

Setup:

Agent: প্রতিটি traffic light একটি agent. ১০০টি।
State (local): waiting queue length per direction, current phase, time-since-last-switch.
State (global): neighbor signal status, time-of-day, weather flag.
Action: discrete — phase 1/2/3/4 select, বা hold (stay current).
Reward: $-\sum(\text{queue length}) - \alpha \cdot \text{switch penalty}$।

Architecture choice:

Parameter sharing: ১০০টি signal homogeneous — একই network architecture, weights share. ১০০× sample efficiency.
Local observation only (deployment): communication latency reality. Each signal own decisions.
Centralized critic (training): simulator-এ — global queue-state available. Critic হ্যান্ডল করে non-stationarity.
Graph structure: signals graph nodes — adjacency = roads connect. Graph Neural Net (GNN) message passing — neighbor-aware.

Training pipeline:

Phase 1: SUMO/CityFlow simulator — calibrated to Dhaka traffic data (Bangladesh Road Transport Authority).
Phase 2: MAPPO with parameter sharing + GNN critic. ~১M episodes.
Phase 3: Sim-to-real — domain randomization (queue noise, sensor failure).
Phase 4: Shadow deploy — agent suggests, current signal-controller decides. ৩-৬ মাস log.
Phase 5: Gradual handover — confidence-weighted. Edge cases (VIP convoy, accident) → human override.

Dhaka-specific challenges:

Mixed traffic: rickshaw, CNG, bus, bike, pedestrian — heterogeneous speed/size. Sensor design হার্ড।
Manual override habit: traffic police হাত দিয়ে control করেন। RL agent মাঝে মাঝে disabled হবে। Robust to interruption.
Religious/cultural events: Eid jamaat, friday prayer, Pohela Boishakh — extreme spike. Pre-defined "festival mode".
Power outages: backup mode (fixed timing) embedded.
Vehicle non-compliance: red-light violation common — RL must not "trust" all vehicles will stop.

Evaluation metric: avg waiting time, total throughput, equity (poor-area road কি extra delay পাচ্ছে?), safety incidents.

Reality check: Hangzhou (China) deployed similar system — ১৫% avg delay reduction. Dhaka-র চ্যালেঞ্জ বেশি, কিন্তু improvement potential বিশাল।

মূল কথা: Multi-agent RL দাবি করে compute + simulator + domain expertise + slow rollout. One-shot research demo না — ৩-৫ বছরের infrastructure investment.

অনুশীলন

Game classification: নিচের গেম-গুলো cooperative/competitive/mixed কোনটি? (a) Football, (b) Tennis 1v1, (c) Two cars merging into highway, (d) Hanabi (cooperative card game), (e) Stock trading.
- (a) Football — mixed (team-cooperative, intra-team mostly cooperative; inter-team competitive zero-sum at scoreline level)
- (b) Tennis 1v1 — fully competitive zero-sum
- (c) Highway merge — mixed, primarily cooperative (avoid crash) with mild competition (lane priority)
- (d) Hanabi — fully cooperative
- (e) Stock trading — general-sum mixed (one wins, another loses, but new money entry-exit changes pie)
Non-stationarity: দু'টি agent IQL চালাচ্ছে rock-paper-scissors-এ। Equilibrium কী? কেন IQL converge না হতে পারে?

Nash equilibrium: uniform mixed strategy ($1/3, 1/3, 1/3$)। কিন্তু IQL deterministic Q-update — Agent 1 rock prefer করলে Agent 2 paper, তাহলে Agent 1 scissors, then Agent 2 rock... infinite cycle. Mixed strategy শেখা যায় না deterministic Q দিয়ে — soft policy (Boltzmann, entropy reg) লাগে।
CTDE intuition: এক-line-এ ব্যাখ্যা করুন — কেন training-এ centralized critic non-stationarity সমস্যা সমাধান করে?

Critic যদি সব agent-এর action জানে, তাহলে environment তার দৃষ্টিতে stationary — কারণ "অজানা agent policy" আর hidden variable নয়, observed variable.