exp3

exp3, short for Exponential-weight algorithm for Exploration and Exploitation, is an online learning algorithm designed for adversarial multi-armed bandit problems. It selects among K arms with unknown reward distributions, aiming to perform nearly as well as the best fixed arm in hindsight despite potentially hostile feedback. The algorithm was introduced by Auer, Cesa-Bianchi, Freund, and Schapire in 2002 and is widely cited in machine learning and decision theory.

In each round t, exp3 maintains a weight w_i(t) for each arm i, initialized equally (for example w_i(1) = 1). It then forms a probability distribution over arms as p_i(t) = (1 - gamma) * w_i(t) / sum_j w_j(t) + gamma / K, where gamma ∈ (0, 1] is a parameter controlling exploration. An arm i_t is drawn according to p(t), and a reward r_t ∈ [0, 1] is observed for that arm. An unbiased reward estimate is computed for the selected arm: hat r_i_t(t) = r_t / p_i_t(t), with hat r_j(t) = 0 for j ≠ i_t. The weights are updated only for the chosen arm via w_i_t(t+1) = w_i_t(t) * exp( gamma * hat r_i_t(t) / K ), while the other weights remain unchanged.

The algorithm achieves a regret bound on the order of O(sqrt(K T log K)) against the best fixed arm in T rounds under the stated assumptions. gamma controls the balance between exploration and exploitation; a common choice is gamma ≈ sqrt(K log K / T). Variants like EXP3.P introduce high-probability guarantees and refined parameters.

EXP3 is applicable to online decision making under uncertainty and adversarial feedback, including online recommendations and resource allocation, particularly when rewards may be non-stationary or worst-case. It requires rewards in [0, 1] and per-round feedback after pulling an arm, and its performance depends on the chosen gamma and the number of arms.