Multi-Armed Bandit：如何平衡探索與利用？

arm 0：μ₀ = 0.20
arm 1：μ₁ = 0.50
arm 2：μ₂ = 0.65
每次 reward 為 0 或 1；總共 T = 200 次選擇。

目前平均 Q(a) = successes(a) / counts(a)

90% 的決策：選目前平均最高的一臂
10% 的決策：從全部三臂均勻抽一臂

index(a) = Q(a) + sqrt(2 × ln(t) / n(a))
選 index 最大者；同分選較小 ID。

t：目前已完成的總拉臂次數
n(a)：其中選過臂 a 的次數

posterior(a) = Beta(1 + successes(a), 1 + failures(a))

每次決策：
1. 每臂各抽一個可能成功率 θ̃(a)
2. 選抽到的 θ̃ 最大的一臂
3. 只用該臂這次的 0／1 回饋更新它

最佳真實均值 μ* = 0.65
pseudo-regret = Σ_t (μ* − μ[選中的臂])
             = 0.45 × count(arm0) + 0.15 × count(arm1)

realized gap = T × μ* − observed cumulative reward
             = 130 − observed cumulative reward

python3 bernoulli_bandit_policies.py > stdout.json

# Python 3.10.12; standard library only. No third-party packages required.

"""Original stationary, immediate-feedback Bernoulli bandit mechanics.

Only the environment/evaluator knows the true means and potential outcomes.
Every policy sees just its own chosen-action feedback. No contextual features.
"""
import hashlib
import json
import math
import platform
import random


MEANS = (0.2, 0.5, 0.65)
HORIZON = 200
SEEDS = tuple(range(20))
EPSILON = 0.1
POLICIES = ("random", "greedy", "epsilon_0_1", "ucb1", "thompson_beta")


def argmax_low_id(values):
    """Python max keeps the first ID when values are equal."""
    return max(range(len(values)), key=lambda arm: values[arm])


class Policy:
    """No true means, unchosen rewards or environment RNG are passed here."""
    def __init__(self, name, number_of_arms, seed):
        self.name = name
        self.rng = random.Random(seed)
        self.counts = [0] * number_of_arms
        self.successes = [0] * number_of_arms

    def choose(self):
        completed = sum(self.counts)
        number_of_arms = len(self.counts)
        # All policies share this explicit warm start, included in HORIZON.
        if completed < number_of_arms:
            return completed
        if self.name == "random":
            return self.rng.randrange(number_of_arms)
        averages = [s / n for s, n in zip(self.successes, self.counts)]
        if self.name == "greedy":
            return argmax_low_id(averages)
        if self.name == "epsilon_0_1":
            if self.rng.random() < EPSILON:
                # Exploration samples ALL arms, so it may select the greedy arm.
                return self.rng.randrange(number_of_arms)
            return argmax_low_id(averages)
        if self.name == "ucb1":
            # t is completed plays; first post-warm-start decision uses t=3.
            indexes = [q + math.sqrt(2 * math.log(completed) / n)
                       for q, n in zip(averages, self.counts)]
            return argmax_low_id(indexes)
        if self.name == "thompson_beta":
            # Beta(1,1) prior: successes -> alpha; failures -> beta.
            draws = [self.rng.betavariate(1 + s, 1 + n - s)
                     for s, n in zip(self.successes, self.counts)]
            return argmax_low_id(draws)
        raise ValueError("Unknown policy")

    def observe(self, arm, reward):
        if reward not in (0, 1):
            raise ValueError("This prototype accepts binary rewards only")
        self.counts[arm] += 1
        self.successes[arm] += reward


def potential_rewards(seed):
    """Independent time x arm Bernoulli cells; shared across policies per seed."""
    environment_rng = random.Random(seed)
    return [[int(environment_rng.random() < mean) for mean in MEANS]
            for _ in range(HORIZON)]


def run_policy(name, policy_seed, table):
    policy = Policy(name, len(table[0]), policy_seed)
    actions, rewards = [], []
    for time_index, row in enumerate(table):
        action = policy.choose()
        # The policy never receives row, including unchosen potential rewards.
        reward = row[action]
        policy.observe(action, reward)
        actions.append(action)
        rewards.append(reward)
    assert actions[:3] == [0, 1, 2]
    assert sum(policy.counts) == HORIZON
    assert sum(policy.successes) == sum(rewards)
    return policy, actions, rewards


def main():
    records = []
    trace_seed_zero = {}
    table_hashes = []
    best_mean = max(MEANS)
    for seed in SEEDS:
        table = potential_rewards(seed)
        payload = json.dumps(table, separators=(",", ":")).encode("ascii")
        table_hashes.append({"seed": seed, "sha256": hashlib.sha256(payload).hexdigest()})
        for policy_id, name in enumerate(POLICIES):
            policy_seed = 10000 + seed * 100 + policy_id
            policy, actions, rewards = run_policy(name, policy_seed, table)
            total_reward = sum(rewards)
            pseudo_regret = math.fsum((best_mean - mean) * count
                                     for mean, count in zip(MEANS, policy.counts))
            # This random realized gap is NOT the sum of nonnegative mean gaps.
            realized_gap = HORIZON * best_mean - total_reward
            assert math.isclose(pseudo_regret,
                                math.fsum(best_mean - MEANS[a] for a in actions), abs_tol=1e-12)
            records.append({"seed": seed, "policy": name, "policy_rng_seed": policy_seed,
                "cumulative_reward": total_reward,
                "pseudo_regret": round(pseudo_regret, 12),
                "realized_gap_to_best_expected_total": round(realized_gap, 12),
                "arm_counts": policy.counts, "arm_successes": policy.successes,
                "empirical_means": [round(s / n, 12) for s, n in zip(policy.successes, policy.counts)]})
            if seed == 0:
                trace_seed_zero[name] = {"actions": actions, "observed_rewards": rewards}
    metric_names = ("cumulative_reward", "pseudo_regret", "realized_gap_to_best_expected_total")
    summary = {}
    for name in POLICIES:
        rows = [row for row in records if row["policy"] == name]
        summary[name] = {"number_of_seeds": len(rows), **{
            "mean_" + metric: round(math.fsum(row[metric] for row in rows) / len(rows), 12)
            for metric in metric_names},
            "mean_arm_counts": [round(math.fsum(row["arm_counts"][a] for row in rows) / len(rows), 12)
                                for a in range(len(MEANS))]}
    print(json.dumps({
        "scope": "Fixed stationary Bernoulli means, no context, immediate chosen-action feedback; "
                 "original simulation, not an online recommendation experiment or universal policy ranking.",
        "versions": {"python": platform.python_version(), "dependencies": "Python standard library only"},
        "settings": {"true_means_for_environment_and_evaluation_only": MEANS,
            "horizon_including_three_warm_start_pulls": HORIZON, "seeds": SEEDS,
            "policies": POLICIES, "epsilon": EPSILON,
            "ucb1": "empirical_mean + sqrt(2*ln(completed_plays)/arm_count), completed_plays=3 at round4",
            "thompson": "independent Beta(1,1) priors; posterior Beta(1+successes,1+failures)",
            "warm_start": "Each policy chooses arms0,1,2 at global time indices0,1,2, included in T=200",
            "tie_break": "lowest arm ID for equal indexes or equal sampled values",
            "environment_seed": "random.Random(seed)",
            "policy_seed": "random.Random(10000 + seed*100 + fixed_policy_id)",
            "coupling": "Same full global-time-by-arm potential-reward table per seed for all policies; "
                        "not indexed by the number of times an arm has been pulled"},
        "metric_definitions": {
            "cumulative_reward": "sum of observed selected-cell rewards",
            "pseudo_regret": "sum_t (max(mu)-mu[action_t]); nonnegative for each chosen-action path",
            "realized_gap_to_best_expected_total": "T*max(mu)-observed_reward; may be negative; "
                                                   "not regret against a realized clairvoyant reward sequence",
            "summary": "arithmetic means over the same20fixed-environment seeds; not significance tests"},
        "per_seed_records": records, "summary": summary,
        "seed_zero_full_chosen_feedback_traces": trace_seed_zero,
        "potential_table_sha256": table_hashes,
        "limits": ["All policies use only their own past chosen-action counts and binary feedback.",
            "True means and unchosen cells are evaluator information, unavailable to choose().",
            "All policies receive an identical3pull warm start; this differs from TS with no forced initialization.",
            "Greedy uses empirical means, not the Beta posterior means of a Bayesian greedy policy.",
            "Exploration can reselect the greedy action; epsilon is not the probability of a nongreedy action.",
            "Fixed epsilon.1 and UCB1 coefficient were not tuned using these results.",
            "The twenty seeds vary outcomes/policy randomization, not the underlying mean vector.",
            "No nonstationarity, delayed/censored feedback, user heterogeneity, exposure correction or actual lift.",
            "A finite realized simulation need not order policies as a regret theorem or a longer run would.",
            "Reproduction of beta draws is scoped to the recorded Python implementation/version."]}, indent=2))


if __name__ == "__main__":
    main()

Image source attribution and changes (selected illustrations)

Fig. 1, 2 and 5 — “UCB-type run.gif” by Adrien PREVOST, https://commons.wikimedia.org/wiki/File:UCB-type_run.gif, dedicated to the public domain under CC0 1.0: https://creativecommons.org/publicdomain/zero/1.0/ . The figures show complete source frames 0, 50 and 196 (zero-based). The selected frames were decoded from the original 560×800 animation and alpha-composited on white as PNGs. No plot content was cropped, redrawn, or changed. The original file is labelled “UCB-type”; no exact algorithm variant, parameterization, code, or seed is provided, so these images should not be attributed to canonical UCB1 or a repeated-run benchmark. In frame 196 the displayed arm counts are 173, 15 and 13 (sum 201) while the source x-axis tick extent reaches 200; the source has not been altered and the frame index is not presented as a round number.

Fig. 3, 4 and cover — “Example of Thompson sampling.webp” by Nguiard, https://commons.wikimedia.org/wiki/File:Example_of_Thompson_sampling.webp, licensed under CC BY 4.0: https://creativecommons.org/licenses/by/4.0/ . The original 640×480 animation is a simplified simulated treatment-efficacy illustration, not clinical evidence. Figures 3 and 4 use complete zero-based frames 0/20 and 100/300, respectively, stacked in source order with a 24-pixel white separator. The cover uses complete frame 300 scaled proportionally to 1200×900 and centered on a white 1600×900 canvas. These are frame extractions/layout derivatives; no plotted labels, values, curves, or data were redrawn or changed. Frame 0 shows four overlapping uniform density-1 priors with zero pulls, rather than an empty plot. In frame 100, legend-order Placebo/T1/T2/T3 counts are 3/4/25/68; in frame 300 they are 6/5/84/205. Count order follows the source legend, not the left-to-right colored marks.

The UCB and Thompson sampling images come from two separate source simulations and should not be compared as a shared experiment. All published use remains subject to the linked source licenses and accurate attribution.