exp4

Exp4 is an online learning algorithm for adversarial multi-armed bandit problems that incorporates advice from a set of experts. It combines exponential weighting of expert opinions with controlled exploration to make decisions when only partial feedback is available.

In the standard setting, there are K arms (actions) and N experts. At each round t, every expert i provides a probability distribution x_i(t) over the arms. The algorithm maintains a weight w_i for each expert, initialized to 1. The aggregated distribution over arms is computed as p_t = (1 − γ) * (sum_i w_i x_i(t)) / (sum_i w_i) + γ/K * 1, where γ ∈ (0,1] is an exploration parameter. An arm a_t is then drawn from p_t and a reward r_t ∈ [0,1] is observed for that arm.

To update the experts, exp4 forms an unbiased estimate of each expert’s gain. For the observed round, define hat_y_i = x_i(t)(a_t) * r_t / p_t(a_t). The weights are updated multiplicatively: w_i ← w_i * exp(η * hat_y_i), with η > 0 as a learning rate. This keeps the weights responsive to how well each expert’s advice performed, given the observed outcome.

Exp4 provides worst-case regret guarantees in the adversarial setting. With appropriate choices of γ and η, the expected regret against the best expert scales as O(sqrt(T K log N)) over T rounds. Complexity per round is O(NK) to compute p_t and update weights, with memory O(NK) to store the experts’ distributions.

Variants and extensions include EXP4.P, which offers high-probability guarantees. Applications encompass online decision making with expert advice, such as online advertising, recommendation systems, and routing. Exp4 was introduced by Auer, Cesa-Bianchi, Freund, and Schapire in the early 2000s.