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



