📚TheoryIntermediate

Exploration-Exploitation Tradeoff

Key Points

•
The exploration–exploitation tradeoff is the tension between trying new actions to learn (exploration) and using the best-known action to earn rewards now (exploitation).
•
In multi-armed bandits, you repeatedly choose among K options (arms) with unknown reward rates and aim to maximize total reward or equivalently minimize regret.
•
Simple strategies like $ε - g ree d y$ explore with small probability, while principled methods like UCB1 and Thompson Sampling use uncertainty estimates to guide choices.
•
Regret quantifies how much reward you lose compared to always pulling the optimal arm; good algorithms achieve regret that grows only logarithmically with time.
•
UCB1 uses confidence bounds derived from concentration inequalities to be “optimistic in the face of uncertainty.”
•
Thompson Sampling uses Bayesian reasoning: it samples plausible values of each arm’s quality and picks the best sample, naturally balancing exploration and exploitation.
•
All standard bandit algorithms run in O(KT) time for T steps and K arms if implemented straightforwardly, with O(K) memory.
•
Real-world issues like non-stationarity, delayed feedback, and context require adaptations (e.g., sliding windows, discounting, contextual bandits).

Prerequisites

→Basic probability — Understanding random variables, independence, and distributions is essential for modeling rewards and uncertainty.
→Expectation and variance — Regret and performance guarantees are expressed using expectations and concentration around means.
→Bernoulli and Binomial distributions — Common bandit benchmarks use binary rewards; Beta-Bernoulli conjugacy underlies Thompson Sampling.
→Concentration inequalities (Hoeffding) — They justify confidence bonuses in UCB algorithms and guide exploration rates.
→Bayesian inference basics — Thompson Sampling requires understanding priors, posteriors, and conjugate updates.
→C++ STL (vectors, RNG, algorithms) — Implementations rely on vectors, random number generators, and standard algorithms.
→Argmax and linear scans — Each round, algorithms select the best arm by scanning scores or samples across arms.

Detailed Explanation

Tap terms for definitions

01Overview

The exploration–exploitation tradeoff is a core challenge in sequential decision-making under uncertainty. Imagine repeatedly choosing among K alternatives, each giving a stochastic reward drawn from an unknown distribution. If you always pick the alternative that looks best from the data you already have (exploitation), you might miss out on better options you have not tried enough (insufficient exploration). If you keep trying less-tested options too often (over-exploration), you sacrifice short-term rewards. Multi-armed bandits formalize this setting: each arm is an option with an unknown average payoff, and your job is to select arms over time to maximize cumulative reward. The performance benchmark is regret—the loss relative to an omniscient strategy that always pulls the best arm from the start.

Classic algorithms engineer a balance. ε-greedy injects random exploration at a fixed or decaying rate. UCB1 constructs an upper confidence bound for each arm, effectively awarding a bonus to uncertain arms. Thompson Sampling uses Bayesian inference to sample from the posterior quality of each arm and play the arm with the highest sampled value. Under standard stochastic assumptions, these approaches achieve low (typically logarithmic) regret, meaning they learn efficiently while still earning rewards along the way.

02Intuition & Analogies

Hook: Think about picking a place for lunch every day. You have a favorite spot that’s consistently good, but a new café opened nearby. If you always go to your favorite (pure exploitation), you may miss discovering that the new café is even better. If you keep trying new places all the time (pure exploration), you might suffer many bad meals. The art is in balancing trying new places just enough to learn, while mostly going to the best place you know so far.

Concept: This is the essence of the exploration–exploitation tradeoff. Early on, you should explore more because you don’t know much. As you collect data, you should shift toward exploiting the best option. But even later, occasional exploration can pay off because initial impressions may have been noisy.

Example: Picture K slot machines (hence “multi-armed bandit”), each with an unknown payout rate. You start with no knowledge. An ε-greedy rule might say: with probability ε = 0.1, pick a random machine to try; with probability 0.9, pick the one that currently looks best based on your averages. UCB1 says: for each machine, compute a “score” = current average reward + an uncertainty bonus that shrinks as you play it more. Choose the machine with the highest score. Thompson Sampling imagines a distribution over each machine’s payout probability, randomly samples a guess from each, and plays the arm with the best sampled guess. All three methods ensure you try promising but uncertain options sometimes, yet gravitate to what seems best as evidence accumulates.

03Formal Definition

A stochastic K-armed bandit has arms i ∈ {1, …, K}. Each arm i yields i.i.d. rewards

r_{i, t}

with unknown mean

μ_{i}

. Let

μ

_* =

max_{i}

μ_{i}

be the optimal mean. Over a time horizon T, a policy

π

selects an arm

A_{t}

based on past actions and rewards. The (expected) cumulative regret up to time T is

R_{T} = T μ_{*}

\mathbb{E}\left

[

\sum_{t = 1}^{T}

r_{A_t,t}\right

]. A policy is good if

R_{T}

grows slowly with T, ideally

R_{T}

= O(

lo g

T) in the stochastic setting.

ε - g ree d y

with parameter

ε_{t}

explores uniformly at random with probability

ε_{t}

and exploits (chooses

ar g max_{i}

\overset{μ}{^}_{i}

(t)) otherwise, where

\overset{μ}{^}_{i}

(t) is the empirical mean of arm i after

N_{i}

(t) plays. UCB1 defines an index UC

B_{i}

(t) =

\overset{μ}{^}_{i}

(t) +

\frac{2 l o g t}{N _{i} ( t )}

, selecting the arm with the largest index; this follows from Hoeffding’s inequality, providing high-probability upper bounds on true means. Thompson Sampling assumes a prior over parameters (e.g., Beta(

α,

β)

for Bernoulli arms), updates the posterior with observations, samples a parameter for each arm from its posterior, and chooses the arm with the highest sample. Under standard assumptions, UCB1 and Thompson Sampling achieve regret

R_{T}

= O

\left

(

\sum_{i : Δ_{i} > 0}

\frac{\log T}{\Delta_i}\right

) where

Δ_{i}

μ

_* -

μ_{i}

04When to Use

Use bandit algorithms when you face repeated decisions with partial (bandit) feedback—i.e., you only observe the reward of the option you chose—and you care about maximizing cumulative reward while learning. Examples include online A/B/n testing (choose which webpage variant to show), recommendation systems (which item to suggest), clinical trials (which treatment to assign under ethical constraints), network routing (which path to send packets), and hyperparameter tuning with limited budget.

If rewards are stationary (do not change over time), classic stochastic bandit algorithms like UCB1 and Thompson Sampling are a great fit. If you have prior knowledge and want a probabilistic approach, Thompson Sampling is attractive. If you want a simple baseline, ε-greedy with a decaying ε is easy to implement.

When contexts or user features matter (the payoff depends on who you act on), move to contextual bandits. If the environment changes over time (non-stationary), use sliding windows, discounted updates, or change-point detection variants (e.g., discounted UCB, SW-UCB, or resettable Thompson Sampling). For adversarial settings (rewards may be chosen by an adversary), use adversarial bandit algorithms like EXP3.

⚠️Common Mistakes

Too little exploration: Picking the empirically best arm too aggressively (pure greedy) can lock in early to a suboptimal arm due to noise. Initialize by trying each arm and use an explicit exploration mechanism.
Too much exploration: Using a large constant ε forever wastes reward. Decay ε over time or use algorithms with principled uncertainty bonuses (UCB) or posteriors (Thompson Sampling).
Ignoring uncertainty: Comparing only sample means without accounting for variance or number of pulls biases toward noisy arms. Confidence bounds or Bayesian posteriors fix this.
Off-by-one and logging mistakes in UCB: Using \log(0) or wrong t can break indices. Ensure t ≥ 1 and initialize N_i(t) > 0 before computing bounds.
Deterministic tie-breaking: Always picking the first arm on ties can bias learning. Break ties randomly to avoid systematic preference.
Mismatch of model and rewards: Applying Bernoulli Thompson Sampling to non-binary rewards without adaptation leads to incorrect updates. Match priors/likelihoods (e.g., Gaussian rewards use Normal–Inverse-Gamma).
Stationarity assumption violations: If true rewards drift, standard UCB/TS may underperform. Use sliding windows or discounting to adapt.
Misinterpreting regret: Optimizing average reward in a short horizon can conflict with long-term regret minimization; tune exploration to the horizon and goals.

Key Formulas

Expected Regret

R_{T} = T μ_{*} - E [t = 1 \sum T r_{A_{t}, t}]

Explanation: Regret measures how much reward is lost compared to always playing the best arm. Smaller growth of $R_{T}$ with T indicates a better learning strategy.

Arm Gap

Δ_{i} = μ_{*} - μ_{i}

Explanation: The gap quantifies how suboptimal an arm is. Arms with small gaps are harder to distinguish from the best arm, often dominating learning difficulty.

Empirical Mean

\overset{μ}{^}_{i} (t) = \frac{1}{N _{i} ( t )} s \leq t : A_{s} = i \sum r_{i, s}

Explanation: The empirical mean is the observed average reward of arm i after it has been pulled $N_{i}$ (t) times. It is used by many algorithms as the current estimate of an arm’s value.

UCB1 Index

UCB1_{i} (t) = \overset{μ}{^}_{i} (t) + \frac{2 lo g t}{N _{i} ( t )}

Explanation: UCB1 selects the arm with the largest index, combining the current mean with an exploration bonus that shrinks as the arm is sampled more, guided by Hoeffding’s inequality.

Hoeffding’s Inequality

P (\overset{μ}{^}_{i} - μ_{i} \geq ε) \leq exp (- 2 N_{i} ε^{2})

Explanation: This bounds the probability that a sample mean deviates above the true mean by $ε .$ It justifies setting exploration bonuses that vanish as the number of samples increases.

Beta-Bernoulli Posterior Update

α_{i}^{(t)} = α_{i}^{(0)} + S_{i} (t), β_{i}^{(t)} = β_{i}^{(0)} + F_{i} (t)

Explanation: For Bernoulli rewards with a Beta prior, the posterior remains Beta with parameters incremented by observed successes $S_{i}$ and failures $F_{i}$ . This makes Thompson Sampling easy to implement.

Thompson Sampling Draw

θ_{i}^{(t)} \sim Beta (α_{i}^{(t)}, β_{i}^{(t)})

Explanation: At each step, sample a plausible mean reward for each arm from its posterior and pick the arm with the largest sample. This balances exploration proportional to uncertainty.

UCB1 Pull Bound (Auer et al.)

E [N_{i} (T)] \leq \frac{8 lo g T}{Δ _{i}^{2}} + 1 + \frac{π ^{2}}{3}

Explanation: For each suboptimal arm i, UCB1’s expected number of pulls grows logarithmically with T and inversely with the square of the gap. This yields low cumulative regret overall.

Logarithmic Regret (UCB/TS)

R_{T} = O (i : Δ_{i} > 0 \sum \frac{lo g T}{Δ _{i}})

Explanation: Both UCB1 and Thompson Sampling achieve regret that grows only like log T, up to problem-dependent constants. This is near-optimal for stochastic bandits.

Posterior Mean (Beta-Bernoulli)

\overset{μ}{^}_{i}^{Bayes} = E [θ_{i} ∣ data] = \frac{α _{i} + S _{i}}{α _{i} + β _{i} + N _{i}}

Explanation: The posterior mean of the Bernoulli success probability after observing S successes and N-S failures is a smoothed estimate. It can be used for exploitation or for reporting.

Complexity Analysis

Let K be the number of arms and T the horizon. A straightforward implementation of common bandit algorithms performs an O(K) scan each round to compute indices or samples and then picks the best arm, yielding total time O(KT). Specifically:

ε - g ree d y

computes an argmax over K empirical means per step (O(K)); UCB1 computes K bonuses (logarithm and division) plus an argmax (O(K)); Thompson Sampling draws K samples from the posterior (constant-time per arm for conjugate families like Beta-Bernoulli using gamma sampling) and then finds the maximum (O(K)). With priority queues or incremental maintenance you can reduce average constants, but asymptotically O(KT) remains for naive implementations. Space complexity is O(K) for all these methods: you store per-arm counts, cumulative rewards (or sufficient statistics), and possibly prior/posterior parameters. For UCB1 you keep

N_{i}

and

\overset{μ}{^}_{i}

; for Thompson Sampling you keep (

α_{i},

β_{i});

for

ε - g ree d y

you keep

N_{i}

and averages. The environment simulator (if used) adds O(K) to store true probabilities. From a statistical performance viewpoint, for stochastic stationary bandits the expected regret of UCB1 and Thompson Sampling scales as O(

\sum_{i > 1}

(

lo g

T)/

Δ_{i}

), meaning per-suboptimal-arm cost grows only logarithmically in time and inversely with the gap.

ε - g ree d y

with a well-chosen decaying

ε_{t}

can also achieve logarithmic regret, while a fixed ε incurs linear regret due to perpetual over-exploration. Constants matter in practice: Thompson Sampling often performs strongly because it naturally tailors exploration to uncertainty, while UCB1 offers parameter-free guarantees and simplicity.

Code Examples

Epsilon-Greedy on a Bernoulli Multi-Armed Bandit

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Simulate pulling a Bernoulli arm with success probability p
5 int pull_arm(double p, mt19937 &rng) {
6     uniform_real_distribution<double> U(0.0, 1.0);
7     return (U(rng) < p) ? 1 : 0; // reward is 1 (success) or 0 (failure)
8 }
9 
10 int main() {
11     ios::sync_with_stdio(false);
12     cin.tie(nullptr);
13 
14     // --- Problem setup ---
15     vector<double> true_p = {0.10, 0.30, 0.50, 0.40}; // unknown to the algorithm
16     int K = (int)true_p.size();
17     int T = 20000;                 // horizon (number of pulls)
18     double epsilon = 0.10;         // exploration probability (try decaying schedules too)
19 
20     // RNG (fixed seed for reproducibility)
21     mt19937 rng(42);
22     uniform_int_distribution<int> Arm(0, K - 1);
23     uniform_real_distribution<double> U(0.0, 1.0);
24 
25     // --- Statistics maintained by the learner ---
26     vector<int> pulls(K, 0);           // N_i(t)
27     vector<double> sum_reward(K, 0.0); // cumulative reward per arm
28 
29     // Helper to compute empirical mean safely
30     auto est = [&](int i) {
31         return pulls[i] > 0 ? (sum_reward[i] / pulls[i]) : 0.0;
32     };
33 
34     // Initialization: play each arm once to get nonzero counts
35     int t = 0;
36     int total_reward = 0;
37     for (int i = 0; i < K && t < T; ++i) {
38         int r = pull_arm(true_p[i], rng);
39         pulls[i]++;
40         sum_reward[i] += r;
41         total_reward += r;
42         ++t;
43     }
44 
45     // --- Main loop ---
46     while (t < T) {
47         int a;
48         if (U(rng) < epsilon) {
49             // Exploration: pick a random arm uniformly
50             a = Arm(rng);
51         } else {
52             // Exploitation: pick the arm with the highest empirical mean
53             a = 0;
54             double best = est(0);
55             for (int i = 1; i < K; ++i) {
56                 double ei = est(i);
57                 if (ei > best) { best = ei; a = i; }
58             }
59         }
60         int r = pull_arm(true_p[a], rng);
61         pulls[a]++;
62         sum_reward[a] += r;
63         total_reward += r;
64         ++t;
65     }
66 
67     // --- Reporting ---
68     int best_true = (int)(max_element(true_p.begin(), true_p.end()) - true_p.begin());
69     cout << fixed << setprecision(4);
70     cout << "Epsilon-Greedy with epsilon = " << epsilon << "\n";
71     cout << "Horizon T = " << T << ", Arms K = " << K << "\n";
72     cout << "True best arm: " << best_true << " (p = " << true_p[best_true] << ")\n";
73     cout << "Total reward: " << total_reward << ", Average reward: " << (double)total_reward / T << "\n\n";
74     for (int i = 0; i < K; ++i) {
75         cout << "Arm " << i
76              << ": pulls = " << pulls[i]
77              << ", est = " << est(i)
78              << ", true p = " << true_p[i]
79              << "\n";
80     }
81 
82     // Tip: try decaying epsilon, e.g., epsilon_t = min(1, c*K/(t)) for large t
83     return 0;
84 }
85

This program simulates an ε-greedy agent on a Bernoulli K-armed bandit. Each arm has an unknown success probability. The agent initializes by pulling each arm once, then at each step explores with probability ε by picking a random arm, or exploits by picking the arm with the highest empirical mean. It tracks per-arm counts and rewards to update estimates and reports total performance and per-arm statistics.

Time: O(KT) overall (O(K) argmax per step).Space: O(K) for per-arm counts and sums.

UCB1: Optimism in the Face of Uncertainty

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int pull_arm(double p, mt19937 &rng) {
5     uniform_real_distribution<double> U(0.0, 1.0);
6     return (U(rng) < p) ? 1 : 0;
7 }
8 
9 int main() {
10     ios::sync_with_stdio(false);
11     cin.tie(nullptr);
12 
13     // Bandit setup
14     vector<double> true_p = {0.10, 0.30, 0.50, 0.40};
15     int K = (int)true_p.size();
16     int T = 20000;
17 
18     mt19937 rng(123);
19 
20     vector<int> pulls(K, 0);
21     vector<double> sum_reward(K, 0.0);
22 
23     auto mean = [&](int i){ return pulls[i] ? sum_reward[i] / pulls[i] : 0.0; };
24 
25     // Play each arm once to avoid log(0) and division by zero
26     int t = 0;
27     int total_reward = 0;
28     for (int i = 0; i < K && t < T; ++i) {
29         int r = pull_arm(true_p[i], rng);
30         pulls[i]++;
31         sum_reward[i] += r;
32         total_reward += r;
33         ++t;
34     }
35 
36     // UCB1 main loop
37     while (t < T) {
38         int best_arm = 0;
39         double best_index = -1e100; // very small
40         double logt = log((double)t); // t >= K >= 1
41         for (int i = 0; i < K; ++i) {
42             // Exploration bonus shrinks as pulls[i] increases
43             double bonus = sqrt(2.0 * logt / pulls[i]);
44             double index = mean(i) + bonus;
45             if (index > best_index) { best_index = index; best_arm = i; }
46         }
47         int r = pull_arm(true_p[best_arm], rng);
48         pulls[best_arm]++;
49         sum_reward[best_arm] += r;
50         total_reward += r;
51         ++t;
52     }
53 
54     int best_true = (int)(max_element(true_p.begin(), true_p.end()) - true_p.begin());
55     cout << fixed << setprecision(4);
56     cout << "UCB1 Results\n";
57     cout << "Horizon T = " << T << ", Arms K = " << K << "\n";
58     cout << "True best arm: " << best_true << " (p = " << true_p[best_true] << ")\n";
59     cout << "Total reward: " << total_reward << ", Average reward: " << (double)total_reward / T << "\n\n";
60     for (int i = 0; i < K; ++i) {
61         cout << "Arm " << i
62              << ": pulls = " << pulls[i]
63              << ", est = " << mean(i)
64              << ", true p = " << true_p[i]
65              << "\n";
66     }
67     return 0;
68 }
69

This program implements UCB1. After an initial pull of each arm, it repeatedly computes the UCB1 index (empirical mean plus a confidence bonus) and chooses the arm with the largest index. The bonus is larger for under-sampled arms, encouraging exploration, and shrinks with more samples, favoring exploitation as certainty grows.

Time: O(KT): compute K indices and argmax per step.Space: O(K): per-arm counts and cumulative rewards.

Thompson Sampling with Beta-Bernoulli Posteriors

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int pull_arm(double p, mt19937 &rng) {
5     uniform_real_distribution<double> U(0.0, 1.0);
6     return (U(rng) < p) ? 1 : 0;
7 }
8 
9 // Sample from Beta(a,b) by sampling two Gammas and taking X/(X+Y)
10 double sample_beta(double a, double b, mt19937 &rng) {
11     gamma_distribution<double> Ga(a, 1.0); // shape a, scale 1
12     gamma_distribution<double> Gb(b, 1.0);
13     double x = Ga(rng);
14     double y = Gb(rng);
15     if (x + y == 0) return 0.0; // degenerate (extremely unlikely with positive shapes)
16     return x / (x + y);
17 }
18 
19 int main() {
20     ios::sync_with_stdio(false);
21     cin.tie(nullptr);
22 
23     vector<double> true_p = {0.10, 0.30, 0.50, 0.40};
24     int K = (int)true_p.size();
25     int T = 20000;
26 
27     mt19937 rng(2024);
28 
29     // Beta(1,1) (uniform) priors for Bernoulli means
30     vector<double> alpha(K, 1.0), beta(K, 1.0);
31     vector<int> pulls(K, 0);
32 
33     int total_reward = 0;
34     for (int t = 1; t <= T; ++t) {
35         // Sample a plausible mean for each arm and pick the argmax
36         int best_arm = 0;
37         double best_sample = -1.0;
38         for (int i = 0; i < K; ++i) {
39             double theta = sample_beta(alpha[i], beta[i], rng);
40             if (theta > best_sample) { best_sample = theta; best_arm = i; }
41         }
42         int r = pull_arm(true_p[best_arm], rng);
43         pulls[best_arm]++;
44         total_reward += r;
45         // Conjugate update
46         if (r == 1) alpha[best_arm] += 1.0; else beta[best_arm] += 1.0;
47     }
48 
49     int best_true = (int)(max_element(true_p.begin(), true_p.end()) - true_p.begin());
50     cout << fixed << setprecision(4);
51     cout << "Thompson Sampling (Beta-Bernoulli)\n";
52     cout << "Horizon T = " << T << ", Arms K = " << K << "\n";
53     cout << "True best arm: " << best_true << " (p = " << true_p[best_true] << ")\n";
54     cout << "Total reward: " << total_reward << ", Average reward: " << (double)total_reward / T << "\n\n";
55     for (int i = 0; i < K; ++i) {
56         double post_mean = (alpha[i]) / (alpha[i] + beta[i]);
57         cout << "Arm " << i
58              << ": pulls = " << pulls[i]
59              << ", posterior mean = " << post_mean
60              << ", true p = " << true_p[i]
61              << "\n";
62     }
63     return 0;
64 }
65

This program implements Thompson Sampling for Bernoulli bandits with Beta priors. At each round, it samples a mean reward from each arm’s Beta posterior and picks the arm with the highest sample, then updates the posterior with the observed binary reward. The conjugacy of Beta and Bernoulli makes updates simple and efficient.

Time: O(KT): sample K Beta variables and take an argmax each step.Space: O(K): store per-arm (alpha, beta) parameters and counts.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Simulate pulling a Bernoulli arm with success probability p
5	int pull_arm(double p, mt19937 &rng) {
6	uniform_real_distribution<double> U(0.0, 1.0);
7	return (U(rng) < p) ? 1 : 0; // reward is 1 (success) or 0 (failure)
8	}
9
10	int main() {
11	ios::sync_with_stdio(false);
12	cin.tie(nullptr);
13
14	// --- Problem setup ---
15	vector<double> true_p = {0.10, 0.30, 0.50, 0.40}; // unknown to the algorithm
16	int K = (int)true_p.size();
17	int T = 20000; // horizon (number of pulls)
18	double epsilon = 0.10; // exploration probability (try decaying schedules too)
19
20	// RNG (fixed seed for reproducibility)
21	mt19937 rng(42);
22	uniform_int_distribution<int> Arm(0, K - 1);
23	uniform_real_distribution<double> U(0.0, 1.0);
24
25	// --- Statistics maintained by the learner ---
26	vector<int> pulls(K, 0); // N_i(t)
27	vector<double> sum_reward(K, 0.0); // cumulative reward per arm
28
29	// Helper to compute empirical mean safely
30	auto est = [&](int i) {
31	return pulls[i] > 0 ? (sum_reward[i] / pulls[i]) : 0.0;
32	};
33
34	// Initialization: play each arm once to get nonzero counts
35	int t = 0;
36	int total_reward = 0;
37	for (int i = 0; i < K && t < T; ++i) {
38	int r = pull_arm(true_p[i], rng);
39	pulls[i]++;
40	sum_reward[i] += r;
41	total_reward += r;
42	++t;
43	}
44
45	// --- Main loop ---
46	while (t < T) {
47	int a;
48	if (U(rng) < epsilon) {
49	// Exploration: pick a random arm uniformly
50	a = Arm(rng);
51	} else {
52	// Exploitation: pick the arm with the highest empirical mean
53	a = 0;
54	double best = est(0);
55	for (int i = 1; i < K; ++i) {
56	double ei = est(i);
57	if (ei > best) { best = ei; a = i; }
58	}
59	}
60	int r = pull_arm(true_p[a], rng);
61	pulls[a]++;
62	sum_reward[a] += r;
63	total_reward += r;
64	++t;
65	}
66
67	// --- Reporting ---
68	int best_true = (int)(max_element(true_p.begin(), true_p.end()) - true_p.begin());
69	cout << fixed << setprecision(4);
70	cout << "Epsilon-Greedy with epsilon = " << epsilon << "\n";
71	cout << "Horizon T = " << T << ", Arms K = " << K << "\n";
72	cout << "True best arm: " << best_true << " (p = " << true_p[best_true] << ")\n";
73	cout << "Total reward: " << total_reward << ", Average reward: " << (double)total_reward / T << "\n\n";
74	for (int i = 0; i < K; ++i) {
75	cout << "Arm " << i
76	<< ": pulls = " << pulls[i]
77	<< ", est = " << est(i)
78	<< ", true p = " << true_p[i]
79	<< "\n";
80	}
81
82	// Tip: try decaying epsilon, e.g., epsilon_t = min(1, c*K/(t)) for large t
83	return 0;
84	}
85