Upper confidence bound

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

Upper confidence bound is an action-selection strategy that combines estimated reward with an uncertainty bonus to balance exploitation and exploration.

Upper confidence bound (UCB) selects actions by adding an uncertainty bonus to each action’s estimated reward. It therefore favors promising actions while still giving less-tested actions a chance to improve their estimates. section 12.1.6

A practical UCB loop follows these steps:

• Play every arm once to initialize its play count and accumulated reward. section 12.1.6
• For each later trial, calculate estimated mean reward plus c × sqrt(log(t) / number of plays). section 12.1.6
• Select the arm with the greatest score, sample its reward, and update its count and reward total. section 12.1.6
• Tune c to control exploration, then compare average regret with explore-only, greedy, and epsilon-greedy strategies. section 12.1.6

Three slot machines

Consider 90 trials with machines whose payoff distributions have means and standard deviations of (8, 0.5), (10, 0.7), and (5, 0.45). A NumPy implementation samples each machine initially, computes UCB scores thereafter, and records regret against the best mean reward. With c = 2, the reported average regret is 0.0378, compared with 0.3466 for epsilon-greedy and 2.246 for explore-only. section 12.1.6

Figure 12.7 Three slot machines as a noncontextual multi-armed bandit (MAB) problem. The payoff distribution’s mean and standard deviations of these three machines are (8,0.5), (10, 0.7), and (5, 0.45), respectively.

Use the slot-machine figure to compare the arms’ payoff means and variability before tracing how UCB balances estimated reward with uncertainty. section 12.1.6

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes

Implements initialization, a confidence-score formula, iterative updates, parameter tuning, and regret comparison through Python code.

Examples

Uses three slot machines, 90 trials, payoff distributions, NumPy listings, and average-regret comparisons.

What it assumes

Assumes multi-armed bandits, estimated rewards, exploration, exploitation, and regret while treating the problem as single-state decision-making.

What you can do after

Apply it via NumPy by selecting arms, updating rewards, tuning c, and measuring average regret.

How it connects

Connects multi-armed bandits with exploration, exploitation, regret, epsilon-greedy strategies, and contextual bandits.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Bayesian Optimization in ActionAn upper confidence bound is a Bayesian optimization acquisition policy that combines a predictive mean with an uncertainty-based confidence term to select candidate evaluations.

Compare how 2 books explain upper confidence bound →

Related concepts

• acquisition functionuses · An acquisition function is a scoring rule that ranks candidate evaluations by their expected usefulness for selecting the next sample or experiment.
• UCB parameterconfigured by · A UCB parameter is a positive scalar that weights predictive uncertainty in an upper confidence bound score and controls its exploration tendency.
• policykind of · A policy is a rule, strategy, or mapping that governs or determines decisions, actions, permissions, or behavior under specified conditions.

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.