Sublinear regret grows more slowly than the number of decisions, so average regret approaches zero. It indicates that a policy’s cumulative performance is moving closer to the best possible decisions over time. section 5.4
In a controlled ad simulation, known click-through rates let you calculate regret and compare policies. In a real campaign, the true optimal reward is unknown, so actual regret cannot be calculated; use business KPIs as proxies and treat low-regret guarantees as a tool for comparing algorithms before deployment. section 5.4 section 5.7
Comparing policies
A UCB policy is described as having logarithmically growing regret, while Epsilon-Greedy has linearly growing regret. A 500-iteration simulation compares cumulative regret across policies. section 5.4
Figure 5.8 Cumulative Regret comparisons of different policies for 500 iterations (for better comparison).
Compare how cumulative regret changes across policies over 500 iterations. section 5.4
