liveBook · Manning

Upper confidence bound

As explained in Grokking Bayes

Upper confidence bound is a decision rule that selects actions using an optimistic estimate combining observed value with an uncertainty bonus.

Upper confidence bound (UCB) is a shortcut for choosing actions when calculating full long-term expected utility is too expensive. It favors actions that already look valuable and actions whose value remains uncertain, treating uncertainty as a reason to explore. section 12.10

μ + β σ,

UCB scores an action by adding its estimated mean utility to an uncertainty bonus: μ is the mean, σ is the standard deviation, and β controls how strongly uncertainty affects the choice. section 12.10

Read the score as a deliberately optimistic estimate:

  • A larger μ rewards exploitation: choose actions with higher observed utility. section 12.10
  • A larger σ rewards exploration: choose actions whose utility is more uncertain. section 12.10
  • A larger β increases the exploration preference; β = 2 can approximate the upper edge of a 95% credible interval for normally distributed utility. section 12.10

Comparing two policies

Suppose policy A produces utilities [4, 9], while policy B usually produces −2 but occasionally produces 28. Policy A has the higher mean, but policy B has much greater uncertainty. With β = 2, UCB selects policy B, matching the decision from Bayesian decision theory.

How Grokking Bayes covers it

How deep it goes
Defines the score, explains its components and optimism, and demonstrates a two-policy calculation without deriving full sequential search.
Examples
Uses two utility lists, mean and standard-deviation calculations, and a figure where β = 2 selects policy B.
What it assumes
Assumes expected utility and exploitation–exploration ideas while explaining the uncertainty bonus from basic means and standard deviations.
What you can do after
Apply UCB by computing each action’s mean and standard deviation, choosing β, and comparing μ + βσ scores.
How it connects
Connects UCB to expected utility, exploitation–exploration tradeoffs, Thompson sampling, 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 Grokking Bayes. The section links point to the parts of the book it draws on.