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

Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / Exploration vs Exploitation

Exploration বনাম Exploitation

The fundamental tension of RL — known good vs unknown better

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

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

Exploration-exploitation dilemma — কেন এত মৌলিক
ε-greedy ও তার variant (decaying ε, Boltzmann/softmax)
UCB — "optimism in the face of uncertainty"
Thompson sampling — Bayesian framework

১ · Dilemma — দৈনন্দিন উদাহরণ

আপনি ঢাকার বাসিন্দা। প্রতিদিন lunch-এ ১০টি restaurant-এর মধ্যে বাছেন। একটি (X) — পরিচিত, সবসময় ৭/১০। বাকি ৯টি — কখনো যাননি। হয়তো একটি ১০/১০ হতে পারে — কিন্তু কোনটি?

সবসময় X-এ যাওয়া (exploitation): guaranteed ৭, কিন্তু ১০ মিস।
প্রতিদিন নতুন (exploration): ১০ পেতে পারেন, কিন্তু গড়ে অনেক ৩-৪ও।
সঠিক balance: মাঝে মাঝে নতুন চেষ্টা, ভাল পেলে settle।

RL-এ এটাই কেন্দ্রীয় সমস্যা — কারণ agent কখনোই পুরোপুরি জানে না কোন action best। জানতে হলে চেষ্টা করতে হয়, চেষ্টা করতে গেলে কিছু sub-optimal action নিতে হয়।

২ · কেন pure greedy ব্যর্থ

যদি agent শুরু থেকেই greedy ($\arg\max_a Q(s, a)$) — সমস্যা:

$Q$-এর initial estimate noisy/zero। প্রথমে যা try করে — সেটাই "ভাল" দেখায়।
Agent sub-optimal action-এ stuck — অন্য action-এর true value শেখা হয় না।
"Optimism" বা explicit exploration ছাড়া — local optimum-এ আটকে।

৩ · ε-greedy — সরল ও কার্যকর

প্রতিটি step-এ:

$1 - \epsilon$ probability-তে: $a = \arg\max_a Q(s, a)$ (exploit)।
$\epsilon$ probability-তে: random action (explore)।

Decaying ε: শুরুতে $\epsilon = 1$ (pure random), ধীরে ধীরে $\epsilon \to 0.01$। শুরুতে অনেক explore, পরে exploit।

গাণিতিক schedule:

$$\epsilon_t = \max(\epsilon_{\min}, \epsilon_0 \cdot \alpha^t)$$

বা — linear decay over $N$ steps।

৪ · Boltzmann/softmax exploration

ε-greedy uniform random — best action বনাম worst action সমান। Softmax — Q-value দিয়ে weighted:

$$\pi(a|s) = \frac{e^{Q(s, a) / \tau}}{\sum_{a'} e^{Q(s, a') / \tau}}$$

$\tau$ = temperature। $\tau \to 0$ — greedy। $\tau \to \infty$ — uniform random।

সুবিধা: সম্ভাবনা smooth — Q diff কম হলে exploration বেশি, বেশি হলে exploit।
সমস্যা: $\tau$ tuning কঠিন। Q scale-এ sensitive।

৫ · UCB — Optimism in the Face of Uncertainty

Idea: যে action কম try হয়েছে — তার সম্পর্কে uncertainty বেশি। সেই uncertainty-কে bonus হিসেবে যোগ:

$$a_t = \arg\max_a \left[ \hat{Q}(a) + c \sqrt{\frac{\ln t}{N(a)}} \right]$$

$\hat{Q}(a)$ — empirical mean। $N(a)$ — কতবার action $a$ নেওয়া হয়েছে। $c$ — exploration constant (সাধারণত $\sqrt{2}$)।

Intuition: rarely-tried action-এর bonus বড় — তাই naturally explored। যত বেশি try, bonus কম। শেষে exploit-এ settle।

UCB-এর regret bound — $O(\sqrt{T \log T})$ — sublinear। অর্থ অসীম time-এ গড় regret → 0। ε-greedy-তে guarantee নেই (asymptotically constant exploration)।

তিন exploration কৌশল — uniform random (ε-greedy), uncertainty-aware (UCB), posterior sampling (Thompson)। প্রতিটির trade-off।

৬ · Thompson sampling

Bayesian approach। প্রতিটি action-এর reward distribution-এর posterior maintain। প্রতিটি step-এ:

প্রতিটি action-এর posterior থেকে sample $\hat{Q}_a \sim P(Q_a | \text{data})$।
$a_t = \arg\max_a \hat{Q}_a$ (sampled values-এর greedy)।
Reward observe করে posterior update।

Bernoulli reward-এ — Beta posterior ($\alpha, \beta$ count of success/failure)। sample = Beta($\alpha+1, \beta+1$)।

৭ · Python — চারটি strategy compare

Python · Multi-strategy bandit

import numpy as np

# 5-armed bandit, true means
np.random.seed(42)
mu = [0.2, 0.5, 0.7, 0.4, 0.1]
n_arms = 5
T = 1000

def run(strategy):
    Q = np.zeros(n_arms)
    N = np.zeros(n_arms)
    rewards = []
    for t in range(1, T+1):
        if strategy == 'eps':
            a = np.random.randint(n_arms) if np.random.rand() < 0.1 \
                else np.argmax(Q)
        elif strategy == 'ucb':
            ucb = Q + np.sqrt(2 * np.log(t) / np.maximum(N, 1))
            a = np.argmax(ucb)
        elif strategy == 'thompson':
            samples = np.random.beta(N*Q + 1, N*(1-Q) + 1)
            a = np.argmax(samples)
        else:  # greedy
            a = np.argmax(Q)
        r = np.random.rand() < mu[a]
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]
        rewards.append(r)
    return np.cumsum(rewards)

for s in ['greedy', 'eps', 'ucb', 'thompson']:
    cum = run(s)
    print(f"{s:10s}: total reward = {cum[-1]:.0f}")
# UCB ও Thompson সাধারণত সবচেয়ে ভাল

Greedy কখনোই best arm খুঁজে পায় না (লোভী হয়ে stuck)। ε-greedy কাজ করে কিন্তু uniform exploration। UCB ও Thompson smarter — কম regret।

৮ · MDP-এ exploration আরও কঠিন

Multi-armed bandit-এ — context নেই, এক step। কিন্তু MDP-এ:

State-action visit count maintain করা কঠিন (high-D state space)।
"Deep exploration" — শুধু one-step exploration যথেষ্ট না, পুরো subtree explore করতে হয়।
Sparse reward problem-এ — random exploration কখনো reward পায় না।

আধুনিক উপায়:

Curiosity-driven: intrinsic reward — novel state দেখলে bonus।
Count-based: pseudo-count from density model।
Bootstrapped DQN: ensemble Q-network — disagreement = uncertainty।
NoisyNet: network weights-এ noise — implicit exploration।
Random Network Distillation (RND): prediction error হিসেবে exploration bonus।

৯ · Practical advice

Python · Decaying ε pattern

import numpy as np

# DQN-এর standard ε schedule
def epsilon(t, eps_start=1.0, eps_end=0.05, decay_steps=100000):
    return max(eps_end, eps_start - (eps_start - eps_end) * t / decay_steps)

# কয়েকটি timestep-এ ε
for t in [0, 10000, 50000, 100000, 200000]:
    print(f"t={t:>6}  ε={epsilon(t):.3f}")
# t=0: 1.000 (pure random)
# t=50k: 0.525
# t=100k+: 0.050 (mostly greedy)

DQN-এর জন্য টিপিকাল schedule — ১০০K step-এ ε ১ → ০.০৫। Atari Breakout-এ এই schedule-ই অধিকাংশ paper-এ ব্যবহৃত।

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

প্র ০১ ε-greedy কেন uniform exploration করে — best বনাম worst সম্ভাবনা সমান কেন?

ε-greedy-এর সরলতা এর শক্তি ও দুর্বলতা দু'টোই।

কেন uniform: সরল implementation। কোনো prior বা confidence-এর হিসাব নেই — শুধু "মাঝে মাঝে random" rule।

সমস্যা: যদি আপনি ৯টি bad action-এর কথা ৯০% sure থাকেন এবং ১টি promising action — uniform exploration ৯০% সময় bad action-এ যাবে। অপচয়।

উন্নতি:

Boltzmann/softmax — Q-weighted, better action বেশি probability।
UCB — uncertainty-weighted।
Thompson — posterior-aware।

তবু কেন ε-greedy popular:

সরল debug।
Hyperparameter কম (শুধু ε)।
Atari/MuJoCo-এ "good enough"।
Function approximation-এর সাথে অন্যগুলো ব্যবহার অস্থির।

উপলব্ধি: "best কাজ করে যা যথেষ্ট কাজ করে"। সরল baseline সবসময় production-এ আগে।

প্র ০২ UCB-এর regret bound $\sqrt{T \log T}$ কি bound? কেন এটা optimal-এর কাছাকাছি?

Regret define: $R_T = T \mu^* - \sum_t \mathbb{E}[r_t]$ — best arm-এর তুলনায় কত miss।

UCB1 (Auer et al., 2002): $R_T = O(\sqrt{KT \log T})$, K = arm count।

Lower bound (Lai-Robbins, 1985): যেকোনো algorithm-এর জন্য $R_T = \Omega(\log T)$ — instance-dependent।

UCB optimal কেন:

Worst-case-এ $\sqrt{T \log T}$ — Lai-Robbins-এর কাছাকাছি।
Confidence bound — concentration inequality (Hoeffding) থেকে natural।
"Optimism" principle — over-estimate করা ভাল কারণ worst case-এ correct estimate পাওয়া যায়।

ε-greedy regret: constant ε হলে regret $\Theta(\epsilon T)$ — linear, খারাপ।

Decaying ε ($\epsilon_t \propto 1/t$): regret $O(\log T)$ — কিন্তু constant tuning কঠিন।

মূল উপলব্ধি: UCB একই time complexity, কিন্তু empirically + theoretically better। তাই recommendation system, A/B testing, ad optimization-এ widely used।

প্র ০৩ Sparse-reward MDP-এ random exploration কেন ব্যর্থ? Montezuma's Revenge উদাহরণ।

Atari Montezuma's Revenge — DQN ১৪ বছর ধরে শিখতে পারেনি। কারণ:

Reward মাত্র key/door-এ পেলে — random exploration-এ ১ in millions probability।
গভীর সাবটাস্ক চাইন — climb ladder, jump skull, take key, open door।
Random agent-এর প্রথম reward পেতেই hours।

সমাধান যা কাজ করেছে:

Curiosity (RND, 2018): intrinsic reward novel state-এ। Montezuma break করল।
Go-Explore (Ecoffet, 2019): archive of "promising" states, randomize from there।
Imitation: human demonstrations দিয়ে warm-start।
Hierarchical: options/skills (high-level subgoals)।

কেন random exploration deep MDP-এ ব্যর্থ:

Random walk variance √t-এ scale — ১০০ step গভীর state-এ পৌঁছাতে চাইলে অনেক sample।
Bottleneck states (e.g., narrow passages) — random হিট করার probability nano।
Action space combinatorial।

মূল উপলব্ধি: exploration = "structured search"। Random শুধু simple problem-এ যথেষ্ট। Real-world hard MDP-এ — explicit novelty signal বা prior knowledge দরকার।

প্র ০৪ Production A/B test (Daraz-এ recommendation) — UCB না Thompson sampling? কী trade-off?

A/B test = bandit problem। variant-এ traffic allocate বুদ্ধিমানভাবে।

Classical A/B test: 50-50 split, fixed period, t-test। কিন্তু:

Loser variant-এ অনেক traffic অপচয়।
Sequential decision-এ stop early সম্ভব না।

UCB:

Pros: theoretical guarantee, clearly interpretable।
Cons: stationary assumption — preference time-এ shift হলে problem।
Best for: short-term, balanced scenarios।

Thompson:

Pros: smooth probability split (75-25 → 90-10 → 100-0), prior incorporate করা যায়, contextual extension সহজ।
Cons: posterior model design dependent, computational cost।
Best for: conversion rate, personalization, contextual bandits।

Industry preference: Microsoft Personalizer, Stitch Fix — Thompson dominant। reason — Bayesian framework natural for business priors।

Practical considerations:

Non-stationarity — sliding window, change-point detection দরকার।
Off-policy evaluation — past data থেকে new policy evaluate (IPS, DR estimators)।
Fairness — never zero-out a variant entirely।

অনুশীলন

UCB compute: arm A — N=10, mean=0.5। arm B — N=2, mean=0.4। t=20, c=√2। UCB কোন arm বাছবে?

UCB(A) = 0.5 + √2·√(ln 20 / 10) = 0.5 + √2·√(0.30) = 0.5 + 0.77 = 1.27।

UCB(B) = 0.4 + √2·√(ln 20 / 2) = 0.4 + √2·√(1.50) = 0.4 + 1.73 = 2.13।

UCB → arm B (high uncertainty bonus)।
Decaying ε: $\epsilon_0 = 1, \epsilon_{\min} = 0.01$, decay over 50,000 steps। step 25,000-এ ε কত?

Linear: $\epsilon = 1 - (1 - 0.01) \cdot 25000/50000 = 1 - 0.495 = 0.505$।
Design exploration: medical drug trial — কোন strategy? কী constraints unique?

Constraints: safety critical, patient-এ exploration ethical issue, sample expensive, lag in observing outcome।

Strategy: Bayesian Adaptive trial — posterior-based allocation, ineffective arm-এ traffic কমানো (Thompson-style), early stopping (futility/efficacy bound), informative prior (preclinical data থেকে)। FDA এই kind-এর adaptive design accept করছে।