exploration–regret tradeoff

To learn what is good, an agent must sometimes try actions it currently believes are bad — that is exploration, and it costs reward right now. But never exploring means never discovering that something better existed, which costs reward forever. The exploration–regret tradeoff is the tension between these: every exploratory step is a small, deliberate down-payment of regret, made in hope of larger future gains.

Theory shows the down-payment is unavoidable and quantifies it. In a multi-armed bandit, distinguishing the best arm from a near-tie requires a number of pulls inversely proportional to the squared gap between them, so the regret any good algorithm pays scales like the sum over arms of (log T)/gap. Optimism-based methods (UCB, UCRL) and posterior sampling (Thompson) are designed to spend exactly enough exploration to keep total regret sublinear while never over-exploring.

The balance is delicate and problem-dependent: too little exploration risks linear regret by locking onto a wrong choice; too much wastes reward on settled questions. Good algorithms make the exploration rate shrink automatically as evidence accumulates.