ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← Học tăng cường

AI Researcher

Bài toán máy đánh bạc nhiều tay

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

Bài toán cân bằng giữa khai thác kiến thức đã có và khám phá lựa chọn mới

lesson120 minHọc tăng cườngAI Researcher

Dự đoán

Bạn bước vào casino có 5 máy slot. Mỗi máy có xác suất thắng KHÁC NHAU nhưng ẨN. Bạn có 100 lượt kéo. Làm sao tối đa tiền thắng?

Nếu chỉ exploit (1 máy) → có thể kẹt ở máy tệ. Nếu explore đều → lãng phí lượt cho máy tệ. Chiến lược tối ưu: lúc đầu explore nhiều, dần exploit khi đã có đủ thông tin. Đây là bài toán cơ bản của RL.

Khoảnh khắc Aha

Bạn vừa giải quyết bài toán cơ bản nhất của RL: explore vs exploit. Epsilon-greedy: 90% chọn tốt nhất, 10% random. UCB: explore arms có uncertainty cao (chưa thử nhiều). Thompson Sampling: model uncertainty bằng phân phối xác suất — thông minh nhất! Shopee, Netflix, Grab đều dùng Bandit hàng ngày.

Thử thách

Shopee test 3 thiết kế nút 'Mua ngay'. A/B/C test: chia đều 33/33/33, đợi 2 tuần. Bandit approach: bắt đầu 33/33/33, nhanh chóng chuyển traffic sang variant tốt nhất. Ưu điểm Bandit?

A/B test: 100K users × 2 tuần × variant C (tệ nhất) = 33K users có trải nghiệm tệ. Bandit: sau 1000 users nhận ra C tệ → giảm traffic C xuống 5% → chỉ ~5K users nhận C. Bandit giảm 6x số users bị ảnh hưởng.

Chạy UCB với c rất lớn (ví dụ c=100). Dự đoán regret curve?

c điều chỉnh trade-off explore/exploit. c quá lớn → bonus lấn át mean → thuật toán như random explore, regret cao. c quá nhỏ → hành xử như greedy, kẹt ở arm tồi. c=√2 (theoretical) hoặc c≈2 (practical) thường tốt.

Ba chiến lược chính

Multi-Armed Bandit là bài toán cân bằng explore (thử mới) và exploit (dùng tốt nhất) — cơ bản nhất của RL. Khi thêm state và transition, bandit mở rộng thành full RL như Q-Learning hoặc Policy Gradient.

3 chiến lược chính (action-value):

Epsilon-greedy: at={arg⁡max⁡aQ^(a)với xaˊc suaˆˊt 1−ϵrandomvới xaˊc suaˆˊt ϵ\text{Epsilon-greedy: } a_t = \begin{cases} \arg\max_a \hat{Q}(a) & \text{với xác suất } 1-\epsilon \\ \text{random} & \text{với xác suất } \epsilon \end{cases}
UCB: at=arg⁡max⁡a[Q^(a)+cln⁡tN(a)]\text{UCB: } a_t = \arg\max_a \left[\hat{Q}(a) + c\sqrt{\frac{\ln t}{N(a)}}\right]
Thompson Sampling: θa∼Beta(αa,βa),at=arg⁡max⁡aθa\text{Thompson Sampling: } \theta_a \sim \text{Beta}(\alpha_a, \beta_a), \quad a_t = \arg\max_a \theta_a

Regret

Regret — thước đo chất lượng:

R(T)=T⋅μ∗−E[∑t=1Tμat]R(T) = T \cdot \mu^{*} - \mathbb{E}\left[\sum_{t=1}^{T} \mu_{a_t}\right]

Với μ∗\mu^{*} là mean reward của arm tối ưu. UCB và Thompson Sampling có regret O(log⁡T)O(\log T) — coi như tối ưu theo định lý Lai–Robbins. ε-Greedy với ε cố định có regret Θ(T)\Theta(T) — tệ hơn nhiều về dài hạn.

Biến thể và các lưu ý

Code mẫu

NumPy — UCB cho 5-armed bandit

import numpy as np

class UCB:
    def __init__(self, n_arms: int, c: float = 2.0):
        self.n_arms = n_arms
        self.c = c
        self.counts = np.zeros(n_arms, dtype=np.int64)
        self.sums   = np.zeros(n_arms, dtype=np.float64)
        self.t = 0

    def select_arm(self) -> int:
        # Ưu tiên arm chưa thử — tránh chia 0
        for a in range(self.n_arms):
            if self.counts[a] == 0:
                return a
        ln_t = np.log(self.t)
        means = self.sums / self.counts
        bonus = self.c * np.sqrt(ln_t / self.counts)
        return int(np.argmax(means + bonus))

    def update(self, arm: int, reward: float) -> None:
        self.t += 1
        self.counts[arm] += 1
        self.sums[arm]   += reward


# ---- simulation ----
true_probs = np.array([0.35, 0.55, 0.78, 0.42, 0.60])
best_mu    = true_probs.max()

ucb = UCB(n_arms=5, c=2.0)
regret = []
cum = 0.0
for t in range(1, 2001):
    a = ucb.select_arm()
    r = float(np.random.rand() < true_probs[a])
    ucb.update(a, r)
    cum += best_mu - true_probs[a]
    regret.append(cum)

print(f"final regret  = {regret[-1]:.2f}")
print(f"pull dist     = {ucb.counts}")
print(f"best arm est  = {np.argmax(ucb.sums / np.maximum(1, ucb.counts))}")
# Regret tăng theo log(t) — đặc trưng của UCB

Thompson Sampling cho A/B/C test

import numpy as np

class ThompsonSampling:
    def __init__(self, n_arms: int):
        self.alpha = np.ones(n_arms)  # successes + 1
        self.beta  = np.ones(n_arms)  # failures  + 1

    def select_arm(self) -> int:
        samples = np.random.beta(self.alpha, self.beta)
        return int(np.argmax(samples))

    def update(self, arm: int, reward: float) -> None:
        if reward > 0:
            self.alpha[arm] += 1
        else:
            self.beta[arm]  += 1


# Shopee A/B/C test cho nút 'Mua ngay'
true_ctr = [0.10, 0.12, 0.09]
ts = ThompsonSampling(n_arms=3)
for user in range(10_000):
    arm = ts.select_arm()
    reward = 1 if np.random.rand() < true_ctr[arm] else 0
    ts.update(arm, reward)

    # Sau ~500 users: variant tốt nhất (B) nhận 80%+ traffic
    # Sau ~2000 users: converge gần như hoàn toàn về B
print(f"alpha = {ts.alpha}")
print(f"beta  = {ts.beta}")
print(f"est CTR = {ts.alpha / (ts.alpha + ts.beta)}")

Vì sao UCB có regret O(log T)

Ý tưởng: arm tối ưu a∗a^{*} có mean μ∗\mu^{*}, arm khác có mean μa<μ∗\mu_a < \mu^{*}. Khi UCB chọn sai arm aa, hoặc (1) upper bound của a đã vượt μ∗\mu^{*} (trường hợp hiếm theo bất đẳng thức Hoeffding), hoặc (2) số lượt kéo a còn quá ít khiến bonus lớn. Phân tích của Auer–Cesa-Bianchi–Fischer (2002) cho thấy mỗi suboptimal arm chỉ bị kéo nhiều nhất O(log⁡T/Δa2)O(\log T / \Delta_a^{2}) lần, với Δa=μ∗−μa\Delta_a = \mu^{*} - \mu_a. Tổng regret là O(∑alog⁡T/Δa)O\left(\sum_a \log T / \Delta_a\right) — sub-linear.

Lai–Robbins (1985) chứng minh cận dưới lý thuyết cũng là Ω(log⁡T)\Omega(\log T) nên UCB đạt order optimal. Thompson Sampling đạt cùng order nhưng constant factor tốt hơn trên phần lớn benchmark (Chapelle & Li 2011).

Bayesian view

Bayesian view: tại sao Beta là conjugate prior

Nếu reward là r∈{0,1}r \in \{0, 1\} với xác suất thành công θ\theta, đó là phân phối Bernoulli. Prior Beta cho θ\theta có dạng p(θ)∝θα−1(1−θ)β−1p(\theta) \propto \theta^{\alpha-1}(1-\theta)^{\beta-1} . Sau khi quan sát 1 thành công, likelihood là θ\theta, posterior ∝θα(1−θ)β−1\propto \theta^{\alpha}(1-\theta)^{\beta-1} — đúng là Beta(α+1,β)\text{Beta}(\alpha+1, \beta) . Đó là lý do update Thompson Sampling chỉ là α += 1 hoặc β += 1 — không cần tính tích phân.

Tính chất conjugate mở rộng cho Gaussian (prior Gaussian → posterior Gaussian), Poisson (Gamma prior), multinomial (Dirichlet prior). Đó là nền tảng toán học khiến Thompson Sampling dễ triển khai trên nhiều loại reward khác nhau.

Ứng dụng thực tế

News/feed ranking: Yahoo Front Page dùng LinUCB (2010) chọn bài viết hiển thị → tăng CTR 12.5% (theo nguồn bài, chưa kiểm chứng) so với editorial baseline.

Ad selection: Google Ads dùng Thompson Sampling (theo nguồn bài, chưa kiểm chứng) để quyết định ad nào hiển thị — đặc biệt cho keyword mới không đủ data cho ML lớn.

Clinical trials: "Adaptive clinical trials" dùng Thompson Sampling: bệnh nhân được chia ngẫu nhiên lúc đầu, sau đó nhánh điều trị hiệu quả hơn dần nhận nhiều bệnh nhân hơn → ít bệnh nhân nhận điều trị tệ.

Recommendation: Spotify, TikTok, YouTube dùng contextual bandit (theo nguồn bài, chưa kiểm chứng) để mix giữa "content bạn chắc chắn thích" và "content mới cần explore". Quá exploit → feed nhàm chán; quá explore → user churn.

Khi nào dùng và checklist

Reinforcement learning cơ bản: Bandit là state-less RL. Thêm state + dynamics thì trở thành MDP; các bài toán recommendation đa số được mô hình hoá như contextual bandit vì trạng thái thay đổi quá nhanh để dùng full RL.

Khi nào KHÔNG dùng Bandit? Khi hành động của bạn ảnh hưởng state theo cách lâu dài (ví dụ mua hàng làm thay đổi preference user trong tương lai). Lúc đó cần full MDP và Q-learning hoặc Policy Gradient.

Checklist chọn thuật toán: (1) Stationary, Bernoulli reward, context đơn giản → Thompson Sampling. (2) Theoretical guarantee cần thiết → UCB. (3) Cần cực kỳ đơn giản và prototype nhanh → ε-Greedy với ε giảm dần. (4) Có feature user → LinUCB hoặc Neural Contextual Bandit.

Khác biệt mô phỏng phía trên với thực tế: trong demo, reward là Bernoulli stationary, bạn có thể reset tuỳ ý. Ở production Shopee/Netflix: (a) reward non-stationary, (b) phải tuân thủ constraint (fairness, diversity), (c) có delay giữa action và reward (user click rồi vài phút sau mới đọc), (d) phải log propensity để debias khi off-policy evaluation.

Off-policy evaluation (OPE): khi muốn thử thuật toán mới mà không risk cho user, ta dùng dữ liệu đã log từ thuật toán cũ. Inverse Propensity Scoring (IPS) và Doubly Robust là hai kỹ thuật chuẩn — cho phép ước lượng "Thuật toán mới sẽ tốt thế nào?" chỉ từ log, không cần deploy. Đây là cầu nối giữa bandit và supervised learning .

Công thức cần thuộc: (1) ε-Greedy chọn tốt nhất với xác suất 1−ε, random với xác suất ε. (2) UCB score = μ^a+cln⁡t/Na\hat{\mu}_a + c\sqrt{\ln t / N_a} . (3) Thompson sample từ Beta(αa,βa)\text{Beta}(\alpha_a, \beta_a). (4) Regret R(T)=Tμ∗−∑tμatR(T) = T\mu^{*} - \sum_t \mu_{a_t}. Bốn công thức này đủ cho 90% use-case thực tế.

Gợi ý đọc thêm: "Bandit Algorithms" của Lattimore & Szepesvári (miễn phí online) là bible cho lý thuyết. Về production, đọc paper LinUCB (Yahoo), BatchedBandits (Google), và Netflix tech blog về contextual bandit cho thumbnail personalization.

Tóm tắt

  • Multi-Armed Bandit: bài toán cân bằng EXPLORE (thử arm mới) và EXPLOIT (dùng arm đã biết tốt nhất).
  • 3 chiến lược kinh điển: ε-Greedy (đơn giản), UCB (khai thác uncertainty), Thompson Sampling (Bayesian, thường mạnh nhất).
  • Regret R(T) = T·μ* − Σ μ_{a_t} là thước đo chất lượng; UCB/TS đạt O(log T), ε-Greedy cố định chỉ O(T).
  • Contextual bandit thêm feature vector — nền tảng recommendation hiện đại (Netflix, TikTok, YouTube).
  • Bandit ≠ A/B test: Bandit adaptive, ít user bị ảnh hưởng bởi variant tệ → ethical + efficient hơn.
  • Khi action làm thay đổi state dài hạn → không đủ, cần full RL (Q-learning, Policy Gradient).

Continue the module

Lesson 1 of 5