liveBook · Manning

Sublinear regret

As explained in Applied Reinforcement Learning

Sublinear regret is regret whose growth is slower than linearly with the number of decisions, causing average regret to approach zero.

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

How Applied Reinforcement Learning covers it

How deep it goes
Defines regret through simulations and theoretical growth rates, but cannot calculate actual regret when real-world optimal rewards are unknown.
Examples
Compares UCB and Epsilon-Greedy bounds and plots policy regret over 500 simulated iterations.
What you can do after
Evaluate bandit algorithms using theoretical low-regret guarantees and use business KPIs as real-campaign proxies.
How it connects
Connects regret to reinforcement learning, contextual bandits, UCB, Epsilon-Greedy, and business KPIs.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.