Definitions and setup

Repeated sampling, best-of-N, majority vote, self-consistency

• Repeated sampling: drawing several answers to the same query.
• Best-of-N: choosing among them with a scorer or verifier.
• Majority vote: choosing the most common answer.
• Self-consistency: majority vote over several reasoning chains from a chain-of-thought prompt.

Verifier, false approval, attractor

• Verifier: something that judges a candidate answer (tests, a checker, a reward model, a person).
• False approval: the verifier accepts a wrong answer.
• Attractor: a wrong answer that many samples converge on, so a vote follows it.

Prioritisation, knapsack, value per cost

• Prioritisation: choosing the order in which to spend a limited budget on tasks.
• Knapsack problem: choose items with values and costs to maximise value within a budget; here the exact optimum is computed by dynamic programming.
• Value per cost: the greedy rule that ranks tasks by estimated value divided by cost.

Exploration, exploitation, bandit, regret

• Exploitation: using the strategy that looks best so far.
• Exploration: trying other strategies to learn whether they are better.
• Multi-armed bandit: the problem of choosing among options with unknown success rates, one trial at a time.
• Regret: the successes lost compared with always using the best option.
• Epsilon-greedy: explore at random with probability epsilon, otherwise use the best so far. UCB adds an optimism bonus for rarely tried options. Thompson sampling picks each option with the probability that it is the best, using a posterior over its success rate.