EXP3 Bandit Importance Weight Feedback
Seeing only the reward you chose creates biased feedback unless rare choices receive the right importance correction.
By Riano · Published · Updated · Report a correction
EXP3 Bandit Importance Weight Feedback
The EXP3 algorithm adapts full-information strategies to a bandit setting by observing only the reward for the selected action. Because it cannot see the reward of unchosen arms, it scales the observed reward using the selection probability—known as the importance weight—to maintain an unbiased estimate.
Worked Example: Single Round Update
Consider an EXP3 model starting with two arms initialized at weights w = [1, 1]. We apply an exploration mix ofgamma = 0.5.
- The sum of weights is
1 + 1 = 2. - The relative weight for Arm 1 is
w[0] / 2 = 0.5. The decision probability for Arm 1 is(1 - 0.5) * 0.5 + 0.5 / 2 = 0.25 + 0.25 = 0.5. - A uniform variate
u = 0.627is sampled. Becauseu ≥ 0.5, Arm 2 is chosen. - Arm 2 receives a true reward of
r_2 = 0from the "Switch" table (since[1, 0]is available at round 1). - The importance-weighted feedback for Arm 2 is computed as
hat_r_2 = r_2 / p_2 = 0 / 0.5 = 0. - The weight for Arm 2 is updated to
w_2 * exp(gamma * hat_r_2 / 2) = 1 * exp(0) = 1. - Arm 1 was not chosen, so its weight remains unchanged at
1.
Experiment
To see this behavior in practice:
- Set the "Reward table" to "Switch" or "Ties" to observe different adversarial environments.
- Adjust the "Exploration mix" to control the minimum probability of choosing any arm.
- Change the "Seed" to observe different random decision sequences.
- Select the number of "Rounds" to see how the relative weight and probabilities update step-by-step.
- Verify the "Last observed importance estimate" and how it affects the "Arm one relative weight".
Limitations
EXP3 relies on an unbiased reward estimate, which inherently possesses high variance because an action sampled with very low probability scales its reward by a huge factor. While the exploration mix ensures a minimum selection chance to bound this variance, empirical performance over short sequences can be noisy compared to full-information models.
References
Primary literature framing the nonstochastic bandit problem and establishing the foundational importance-weighted exponential weight algorithm.
- Auer, P., Cesa-Bianchi, N., Freund, Y., & Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1), 48-77.https://doi.org/10.1137/S0097539701398375
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive EXP3 Bandit Importance Weight Feedback module.
Try EXP3 Bandit Importance Weight Feedback on Riano →