EXP3
Imagine choosing among several buttons when an opponent, a changing website, or an unknown process decides which button pays. EXP3 is designed for this harsher setting: it learns which actions are rewarding without assuming that rewards come from a fixed, friendly probability distribution.
How EXP3 learns from one observed rewardEXP3 stands for Exponential-weight algorithm for Exploration and Exploitation. It keeps a positive weight for each action and converts those weights into a probability distribution. Actions with stronger evidence receive more probability, but every action retains a deliberate chance of being selected. After choosing action i and seeing reward r, EXP3 cannot directly judge the unchosen actions. Instead, it gives the chosen action an importance-weighted reward estimate, roughly r / p(i), where p(i) was the probability of choosing it. Its weight is then multiplied by an exponential factor based on that estimate.
- Exploitation: high-weight actions are selected more frequently.
- Exploration: a mixing parameter assigns probability to every action, including poorly rated or untried ones.
- Correction for partial feedback: dividing by selection probability prevents a rarely sampled action’s evidence from being systematically undervalued.
In a standard stochastic bandit, an arm might have a stable average reward. EXP3 makes no such promise: rewards can shift strategically from round to round, even in response to the learner’s behavior. Its goal is low regret against the best single action in hindsight, rather than identifying a permanently best arm. With suitable tuning, its regret grows on the order of √(KT log K) over T rounds and K actions. This protection costs efficiency when rewards really are stable, because importance weighting can be noisy—especially when an action is sampled with tiny probability.
Where it is useful—and fragileEXP3 fits online ad selection, routing, or recommendation choices where rewards drift and only the selected option reveals feedback. It also guards against a policy repeatedly exploiting yesterday’s winner after conditions change. But exploration must not be set too low: probabilities near zero create huge importance-weighted updates, making learning unstable; set too high, and the agent wastes reward on random choices. EXP3 handles a single decision per round, not delayed multi-step credit assignment as in DQN or PPO.
EXP3 (Exponential-weight algorithm for Exploration and Exploitation) is a randomized multi-armed bandit algorithm for adversarial reward sequences. It assigns action probabilities from exponentially weighted estimates of their rewards, while mixing in explicit exploration; because it observes only the chosen action’s reward, it uses importance-weighted estimates. EXP3 matters because it provides provable low regret even when rewards are chosen adaptively or nonstationarily, rather than generated by fixed distributions.
Imagine choosing one of several cafés each day, but their quality can change unpredictably—perhaps even because someone is trying to make your choices harder. You only learn whether the café you picked was good; you do not get to see how the others would have been.
EXP3 is a strategy for this kind of uncertain choice. It helps a system balance trying different options with returning to options that have paid off before. It is designed for especially tough situations where rewards may shift or be deliberately manipulated, rather than following a stable pattern. That makes it useful whenever decisions must be made with limited feedback and an unreliable world.