UCB — Upper Confidence Bound for exploration.

medium

Answer

$[Q(a)\; + \;c\; \sqrt (\operatorname{ln}\;t\; / \;n_{a})]$
$Confidence bound term inflates rarely-tried actions.$
$Provides O(\sqrtT log T) regret bound.$
${\pi}_{\mathrm{prior}}$
$Uses: bandit algorithms, MCTS, contextual bandits.$
$Modern application: exploration bonus in some RL papers (BOOTSTRAPPED DQN, RND).$

Check yourself — multiple choice

Same as ε-greedy
a = argmax $[Q(a)\; + \;c\; \sqrt (\operatorname{ln}\;t\; / \;n_{a})]$ ; confidence bound inflates rare actions; O(√T log T) regret; PUCT extends to trees; used in MCTS + AlphaZero
Random
Not real

UCB: Q̂ + c √ $(\operatorname{ln}\;t\; / \;n_{a})$ ; optimism under uncertainty; PUCT for trees.

#exploration#theory

214 interview questions in this topic.