liveBook · Manning

Upper confidence bound

As explained in Applied Reinforcement Learning

An upper confidence bound method selects actions using an optimistic estimate that combines estimated reward with an uncertainty-based confidence bonus.

When choosing which ad to show, an advertiser wants clicks now but also needs to learn whether less-tested ads might perform better. Upper confidence bound (UCB) balances these goals by scoring each action using its estimated reward plus an uncertainty bonus, then choosing the highest score. section 5.3 section 5.2

In one UCB implementation, the score is estimated reward + c × √(ln(total pulls) / action pulls). The bonus is larger for an action tried fewer times, while c controls the emphasis on exploration. As the total number of pulls increases, the logarithm also increases pressure to revisit less-tried actions. Try each action once before applying this formula. section 5.3 section 7.3

Choosing an ad

Treat each ad as an action and a click as reward 1, with no click worth 0. Keep a count and an estimated click-through rate for each ad. After each choice, update its count and estimated reward; on the next choice, an ad with fewer trials can win because its uncertainty bonus offsets a lower current estimate. section 5.3

Unlike epsilon-greedy, which sometimes chooses an action at random, UCB directs exploration toward uncertain actions. Regret measures the reward missed relative to the best action and helps compare policies in simulation. In a real campaign, the true best reward is unknown, so actual numerical regret cannot be calculated directly. section 5.2 section 5.4

LinUCB extends the idea to contextual bandits: a linear model estimates each action’s reward from features, and an uncertainty bonus guides exploration. For personalized discounts, actions are discount levels and rewards are transaction revenues. The approach assumes a linear reward relationship, sufficiently informative features, and relatively stable customer behavior. section 5.5

UCB1 also guides selection in Monte Carlo tree search. At each node, it combines a child’s average observed reward with a bonus based on parent and child visit counts, directing search toward promising routes without ignoring less-visited branches. section 7.3 section 7.5

How Applied Reinforcement Learning covers it

How deep it goes
Works through scoring, initialization, parameter choice, and updates, then extends the idea to contextual prediction and tree selection.
Examples
Uses simulated ad clicks, revenue from personalized discounts, and vehicle-routing branches to illustrate decisions.
What you can do after
Builds UCB and LinUCB agents from scratch for simulated ads and contextual discount decisions.
How it connects
Connects exploration and exploitation with epsilon-greedy, Thompson sampling, regret, contextual bandits, and Monte Carlo tree search.

Also explained in

Compare how 4 books explain upper confidence bound →

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.