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

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

Multi-armed bandit সমস্যা

Multi-armed bandits — RL distilled to its essence

৭ মিনিট পড়া উচ্চ · Advanced Python কোডসহ

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

Multi-armed bandit problem — formal definition
Regret — performance metric
UCB1 ও Thompson sampling — দু'টি classical algorithm
Contextual bandit — recommendation system-এর core

১ · একটি বহু-হাত-ওয়ালা slot machine

নাম এসেছে Las Vegas-এর slot machine থেকে — "one-armed bandit"। বহু slot machine-এর সামনে দাঁড়িয়ে — কোনটিতে coin ফেললে বেশি payout?

Multi-armed bandit (MAB)

$K$ arms, প্রতিটি arm $i$-এর reward distribution $\mathcal{D}_i$ (mean $\mu_i$ unknown)। প্রতি timestep $t$:
১) Agent action $a_t \in \{1, \ldots, K\}$ বাছে।
২) Reward $r_t \sim \mathcal{D}_{a_t}$।
৩) লক্ষ্য — $T$ step-এ মোট reward maximize।

২ · MAB কেন "stateless RL"

MDP-এ — current state ভবিষ্যৎ-এ প্রভাব ফেলে। MAB-এ — state নেই (বা trivial)। প্রতিটি action স্বাধীন।

গাণিতিকভাবে — MAB হলো MDP যেখানে $|\mathcal{S}| = 1$। তাই সব RL idea (exploration, value estimation) এখানে purified form-এ দেখা যায় — credit assignment বা sequential dependency ছাড়া।

MAB = "এক step RL"। এটাই RL-এর সরলতম interesting subproblem। এই পরিচ্ছন্ন setting-এ algorithm design + theory pure form-এ দেখা যায়।

৩ · Regret — performance measure

Best arm-এর mean $\mu^* = \max_i \mu_i$। আমরা যদি best arm-ই সবসময় টানতাম — total reward $T \mu^*$।

Actual policy $\pi$-এর regret:

$$R_T(\pi) = T \mu^* - \mathbb{E}\left[ \sum_{t=1}^T r_t \right]$$

Regret-এর scaling:

Linear ($\Theta(T)$): খারাপ। ε-greedy with constant ε।
Sublinear ($O(\sqrt{T})$ বা $O(\log T)$): ভাল। UCB, Thompson।

Lai-Robbins lower bound (১৯৮৫): যেকোনো algorithm-এর জন্য $R_T = \Omega(\log T)$ — instance-dependent। তাই $O(\log T)$-ই optimal।

৪ · UCB1 algorithm

Auer, Cesa-Bianchi, Fischer (২০০২) প্রস্তাবিত — সরল ও near-optimal:

প্রথম $K$ step-এ — প্রতিটি arm একবার pull করো।
$t \ge K$ এর জন্য:

$$a_t = \arg\max_i \left[ \hat{\mu}_i + \sqrt{\frac{2 \ln t}{N_i}} \right]$$

Reward observe, $\hat{\mu}_i, N_i$ update।

Theorem: UCB1-এর regret $O(\sqrt{KT \log T})$ — order-optimal।

৫ · Thompson sampling

Bayesian — প্রতি arm-এ posterior distribution maintain। Bernoulli reward-এ — Beta posterior:

Prior: Beta($\alpha_0, \beta_0$) — সাধারণত $\alpha_0 = \beta_0 = 1$ (uniform)।
Reward $r_t \in \{0, 1\}$ observe → posterior update: $\alpha \leftarrow \alpha + r, \beta \leftarrow \beta + (1-r)$।

প্রতি step-এ:

প্রতি arm-এর posterior থেকে sample $\hat{\mu}_i \sim \text{Beta}(\alpha_i, \beta_i)$।
$a_t = \arg\max_i \hat{\mu}_i$।

Theorem (Agrawal-Goyal, 2012): Thompson sampling-এর regret $O(\sqrt{KT \log T})$ — UCB-এর সমান।

Cumulative regret vs time — algorithm choice কতটা matter। greedy linear, smart algorithm logarithmic।

৬ · Python — full bandit experiment

Python · Bandit comparison

import numpy as np

class Bandit:
    def __init__(self, mus):
        self.mus = mus
        self.K = len(mus)
        self.best = max(mus)

    def pull(self, a):
        return float(np.random.rand() < self.mus[a])

def regret_ucb(b, T, c=2.0):
    Q, N = np.zeros(b.K), np.zeros(b.K)
    cum_reward = 0
    for t in range(1, T+1):
        if t <= b.K:
            a = t - 1
        else:
            ucb = Q + np.sqrt(c * np.log(t) / N)
            a = np.argmax(ucb)
        r = b.pull(a)
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]
        cum_reward += r
    return T * b.best - cum_reward

def regret_thompson(b, T):
    alpha = np.ones(b.K)
    beta = np.ones(b.K)
    cum_reward = 0
    for t in range(T):
        samples = np.random.beta(alpha, beta)
        a = np.argmax(samples)
        r = b.pull(a)
        alpha[a] += r
        beta[a] += (1 - r)
        cum_reward += r
    return T * b.best - cum_reward

np.random.seed(0)
b = Bandit([0.2, 0.5, 0.7, 0.3, 0.4])
T = 1000

ucb_regrets = [regret_ucb(b, T) for _ in range(20)]
ts_regrets = [regret_thompson(b, T) for _ in range(20)]
print(f"UCB regret:      {np.mean(ucb_regrets):.1f} ± {np.std(ucb_regrets):.1f}")
print(f"Thompson regret: {np.mean(ts_regrets):.1f} ± {np.std(ts_regrets):.1f}")
# দু'টিই ১০০-এর কাছাকাছি — sub-linear in T=1000।

Random policy regret = ০.৫ · ৫ - ০.৭ · ৫ = ১০০ × T = ৫০০ (linear)। UCB ও Thompson ১০০-এর নিচে — অনেক ভাল।

৭ · Contextual bandits

MAB-এ context নেই — প্রতি arm-এর single mean। কিন্তু production-এ — user different। তাই contextual bandit:

$$r_t \sim \mathcal{D}(a_t \mid x_t)$$

$x_t$ = context (user features, time, location)। mean $\mu_a(x)$ — context-dependent।

Linear contextual: $\mu_a(x) = \theta_a^T x$।
LinUCB: linear regression + UCB confidence interval।
Neural contextual: $\mu_a(x) = f_\theta(x, a)$, neural net।

৮ · Production applications

Yahoo News: LinUCB to personalize news article placement (Li et al., 2010)। +১২% click।
Microsoft: Decision Service / Personalizer — Thompson-based platform।
Google AdWords: ad selection per query — contextual bandit।
Netflix: artwork selection (which thumbnail per user)।
Drug trials: adaptive trial design — patient allocation Bayesian।
Crop selection: কোন variety কোন season-এ — agriculture R&D।

৯ · MAB থেকে full RL-এ

Python · Bandit → MDP transition

# MAB:    state = ∅  →  action  →  reward  (one shot)
# Contextual MAB:  state x  →  action  →  reward  (one shot)
# Full MDP:  state s  →  action  →  reward + next state  (sequence)

# MAB-এ "value" = arm's mean. MDP-এ "value" = future cumulative.

# Pseudocode:
def mab_value(arm_data):
    return np.mean(arm_data)

def mdp_value(state, policy, env, gamma=0.9, n_episodes=100):
    """Monte Carlo এর সাহায্যে V(s)।"""
    G_list = []
    for _ in range(n_episodes):
        env.set_state(state)
        G, t = 0, 0
        done = False
        while not done:
            a = policy(state)
            state, r, done = env.step(a)
            G += (gamma ** t) * r
            t += 1
        G_list.append(G)
    return np.mean(G_list)

print("MAB → MDP-এ — credit assignment + bootstrapping যোগ হয়।")

MAB → contextual MAB → full MDP — RL-এ complexity-র gradient। মডিউল ২ থেকে আমরা full MDP-এ যাব।

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

প্র ০১ UCB-এর exploration bonus $\sqrt{2 \ln t / N}$ — কেন এই ফর্ম? কীভাবে derive করা হয়?

এই formula Hoeffding-এর inequality থেকে আসে।

Hoeffding bound: $X_1, \ldots, X_n$ i.i.d., $X_i \in [0, 1]$, mean $\mu$। তবে:

$$\Pr[\bar{X}_n + u < \mu] \le e^{-2 n u^2}$$

যদি $u = \sqrt{\frac{\ln(1/\delta)}{2n}}$ — তবে $\Pr[\bar{X} + u < \mu] \le \delta$। মানে — true $\mu$ confidence interval-এর বাইরে যাওয়ার probability $\delta$।

UCB-এ $\delta = 1/t^4$ চাই (কেন এত নির্দিষ্ট — proof-এর জন্য union bound)।

$$u = \sqrt{\frac{\ln(t^4)}{2n}} = \sqrt{\frac{2 \ln t}{n}}$$

এটাই UCB1-এর exploration bonus।

Intuitive:

$\ln t$ — sub-linear growth (long-term-এ exploration কমে)।
$1/N$ — কম-explored arm-এ বেশি bonus।
$\sqrt{}$ — variance-এর scale।

Variants:

UCB-V (variance-aware) — empirical variance কাজে লাগায়।
KL-UCB — Bernoulli-এ tighter bound।
BayesUCB — Bayesian version।

প্র ০২ Thompson sampling-এর "matching probability" interpretation কী?

Thompson-এর elegance — প্রতি step-এ একটি action নেওয়ার probability সেই action best হওয়ার posterior probability-র সমান:

$$\Pr[a_t = i] = \Pr[\mu_i \text{ is best} \mid \text{data}_{1:t-1}]$$

প্রমাণ: sample $\hat{\mu}_i \sim P(\mu_i | \text{data})$, $a = \arg\max_i \hat{\mu}_i$। তাই $i$ chosen ⟺ $\hat{\mu}_i = \max$ — যার probability $\Pr[\mu_i \text{ best}]$।

কেন এটা elegant:

Probability matching — "ratio of belief = ratio of action"।
Natural exploration — uncertain arm-এর posterior wide → sometimes selected।
Confident arm — narrow posterior → consistently selected।

Optimality: Russo & Van Roy (2014) প্রমাণ করেছেন যে — Bayesian regret-এ Thompson information-ratio-optimal।

Practical edge over UCB:

Stochastic action — ties break naturally।
Prior incorporate করা সহজ।
Contextual extension সরল (linear / Bayesian regression posterior)।

প্র ০৩ Non-stationary bandit — true mean time-এ shift হয়। কী algorithm-এ পরিবর্তন দরকার?

Stationary assumption ভেঙে গেলে — UCB/Thompson stale data-এ বিভ্রান্ত।

উদাহরণ: news click — সকালের article-এর popularity দুপুরে আলাদা।

সমাধান:

Sliding window UCB: শুধু last $W$ pulls-এর data থেকে। old data forget।
Discounted UCB: exponential discount old observations।
Change-point detection: CUSUM-style — abrupt change detect করে reset।
Adversarial bandit (EXP3): worst-case minimal assumption — আরও robust কিন্তু slower।

Trade-off:

Window ছোট = quick adapt কিন্তু high variance।
Window বড় = stable estimate কিন্তু slow adapt।

Production reality: non-stationarity সবসময় থাকে। তাই Microsoft Personalizer, Stitch Fix — discounted Thompson বা bandit-network ensemble use।

প্র ০৪ আপনি Pathao-এর জন্য ride-fare optimization design করছেন। কীভাবে contextual bandit-এ frame করবেন?

Context $x$:

Origin / destination zones।
Time of day, day of week।
Weather (rain → demand spike)।
Current driver supply।
Historical demand at this hour।
User-tier (regular vs occasional)।

Action $a$: price multiplier ∈ {1.0, 1.2, 1.5, 1.8, 2.0} (discrete) বা continuous।

Reward $r$: revenue if booking accepted, 0 if rejected। বা — long-term proxy: GMV with deterrent penalty।

Why not full RL:

Each ride mostly independent — bandit সরল।
One-shot decision — no sequential dependency।

চ্যালেঞ্জ:

Counterfactual: এক price-এ accept, অন্যতে কী হতো — observe করি না।
Off-policy evaluation: historic data থেকে new policy evaluate (IPS, DR estimator)।
Fairness: certain area-এ surge unfair perception।
Long-term effect: high price short-term revenue বাড়ায়, long-term churn।
Multi-stakeholder: driver + rider + platform — তিন optimizing party।

Solution architecture:

Contextual Thompson with neural posterior।
Counterfactual evaluation pipeline।
Simulator (digital twin) for offline test।
Gradual rollout (1% → 10% → 100%)।

অনুশীলন

Regret compute: 3-armed bandit, mu = [0.3, 0.5, 0.4]। T=100, কোনো algorithm টেনেছে [25, 50, 25] times respectively। expected regret কত?

Best mean = 0.5। Expected reward = 25·0.3 + 50·0.5 + 25·0.4 = 7.5 + 25 + 10 = 42.5।

Regret = 100·0.5 − 42.5 = 7.5।
UCB calc: arm A: pulled 50, mean 0.4। arm B: pulled 5, mean 0.6। t=100। কোন arm UCB1 বাছবে?

UCB(A) = 0.4 + √(2·ln 100 / 50) = 0.4 + √(0.184) = 0.4 + 0.43 = 0.83।

UCB(B) = 0.6 + √(2·ln 100 / 5) = 0.6 + √(1.84) = 0.6 + 1.36 = 1.96।

UCB → arm B।
Thompson update: Bernoulli arm, prior Beta(1,1)। 7 pulls — 4 success, 3 failure। posterior কী?

Beta(1+4, 1+3) = Beta(5, 4)।

Mean = 5/9 ≈ 0.556। Variance = (5·4)/((9)²·(10)) ≈ 0.0247।