Tool Selection and Regret

An agent choosing among tools is running a bandit — and the logarithmic regret of UCB tells you exactly what exploration is worth.

AgentsGraduate⏱ 3 hours10 min readbanditsucbregretexplorationtool use

1 problem →

AssumesError Compounding in Agent Trajectories · Concentration Inequalities

Setup

DefinitionCumulative regret

There are $K$ arms (tools). Arm $i$ yields i.i.d. rewards in $[0,1]$ with unknown mean $\mu_i$ . Let $\mu^\star = \max_i \mu_i$ and $\Delta_i = \mu^\star - \mu_i$ be arm $i$ 's gap. An algorithm choosing arm $I_t$ at round $t$ has cumulative regret

R_T = T\mu^\star - \E\left[\sum_{t=1}^T \mu_{I_t}\right] = \sum_{i=1}^K \Delta_i\,\E\big[n_i(T)\big],

where $n_i(T)$ counts pulls of arm $i$ in $T$ rounds.

The second equality is just bookkeeping: each pull of arm $i$ costs exactly $\Delta_i$ against the benchmark, so total regret is the gap-weighted pull count. Bounding regret therefore means bounding how often a suboptimal arm is pulled.

Algorithm — UCB1

Pull each arm once.
For $t > K$ , pull the arm maximising $\mathrm{UCB}_i(t) = \hat\mu_i(t) + \sqrt{\frac{2\log t}{n_i(t)}},$ where $\hat\mu_i(t)$ is the empirical mean of arm $i$ 's rewards so far.
Update $\hat\mu$ and $n$ and repeat.

The second term is a confidence radius: wide for rarely-pulled arms, shrinking like $1/\sqrt{n_i}$ . Acting on the upper end of the interval is "optimism in the face of uncertainty" — an arm is played either because it looks good or because you do not yet know that it is not.

The pull bound

TheoremUCB1 pulls a suboptimal arm O(log T / Δ²) times

For rewards in $[0,1]$ and any arm $i$ with $\Delta_i > 0$ , UCB1 satisfies

\E\big[n_i(T)\big] \ \le\ \frac{8\log T}{\Delta_i^2} \;+\; 1 + \frac{\pi^2}{3}.

Assumptions

Rewards i.i.d. per arm, bounded in $[0,1]$ , independent across arms and rounds, and stationary. The last is the assumption most often violated in agent settings and is discussed at the end.

CorollaryLogarithmic regret for UCB1

R_T \ \le\ \sum_{i:\Delta_i&gt;0}\left(\frac{8\log T}{\Delta_i} + \left(1+\frac{\pi^2}{3}\right)\Delta_i\right) \qquad\text{and}\qquad R_T = O\big(\sqrt{KT\log T}\big).

Key idea

Two readings of the same result:

Per-instance: regret grows like $\log T$ , not $T$ . The fraction of rounds spent on the wrong tool tends to zero. Exploration is nearly free in the long run.
Small gaps are expensive. The $1/\Delta_i^2$ in the pull bound says arms that are nearly as good as the best get pulled a lot — which is fine, because each such pull costs only $\Delta_i$ . That is exactly why the regret bound carries $1/\Delta_i$ rather than $1/\Delta_i^2$ .

TheoremNo algorithm beats logarithmic regret

For any algorithm whose regret is $o(T^a)$ for every $a > 0$ on every instance, and for a broad class of reward families, there are instances on which

\liminf_{T\to\infty}\frac{R_T}{\log T} \ \ge\ \sum_{i:\Delta_i&gt;0}\frac{\Delta_i}{\mathrm{KL}(\nu_i\,\|\,\nu^\star)},

where $\mathrm{KL}(\nu_i\|\nu^\star)$ is the divergence between arm $i$ 's reward distribution and the optimal arm's.

What this does not say

The gap between this theory and an actual agent is wide, and each gap is a genuine modelling failure rather than a technicality:

Tool quality is context-dependent. The right tool depends on the query, which makes this a contextual bandit; the analysis above is for a single fixed distribution per arm. Contextual algorithms exist with their own guarantees and different assumptions.
Rewards are not stationary. Tools change, indexes go stale, APIs degrade. UCB's confidence radius shrinks monotonically, so it becomes progressively less willing to re-explore an arm that has gone bad — the wrong behaviour under drift. Discounted or sliding-window variants exist.
Calls are not free or equal. Arms have different latencies and costs; the reward-per-round model prices them identically.
Feedback is delayed and partial. Whether a tool call helped is often only apparent at the end of a trajectory, if at all — the credit-assignment problem the bandit formulation assumes away.

Use the bandit framing to reason about exploration budgets and to recognise that a small persistent exploration rate is cheap. Do not read the regret bound as a guarantee about a deployed agent.

References

PaperP. Auer, N. Cesa-Bianchi, P. Fischer (2002). Finite-time Analysis of the Multiarmed Bandit Problem
PaperT. L. Lai, H. Robbins (1985). Asymptotically Efficient Adaptive Allocation Rules
BookT. Lattimore, C. Szepesvári (2020). Bandit AlgorithmsThe standard modern reference; the analysis below is the classical one, stated independently.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionCumulative regretThe shortfall of an algorithm's total reward against always playing the best arm in hindsight.
TheoremUCB1 pulls a suboptimal arm O(log T / Δ²) timesproof includedWith confidence radius √(2 log t / n), the expected number of pulls of an arm with gap Δ is at most 8 log T/Δ² plus a constant.
CorollaryLogarithmic regret for UCB1proof includedCumulative regret is O(Σ log T/Δᵢ) for gap-dependent bounds, and O(√(KT log T)) uniformly over gaps.
TheoremNo algorithm beats logarithmic regretAny algorithm with sublinear regret on every instance suffers Ω(log T) regret on some instance, so UCB is optimal in order.

Problems (1)

All problems

The UCB pull boundProofGraduate⏱ 3 hours