Regret, made precise
Over T steps, regret is the total reward an optimal policy would have earned minus what your algorithm actually earned. The benchmark is whether regret grows sublinearly in T: if it does, your average reward per step approaches optimal, so you are 'learning to act' in a meaningful sense. Linear regret means a constant per-step loss forever — you never truly learn. The art is making the regret as small as the laws of statistics allow.
Diagram of the reinforcement-learning loop: agent takes an action, environment returns a state and reward, repeated over time.
Optimism in the face of uncertainty
The most successful exploration principle is optimism under uncertainty: act as if the world is as good as it plausibly could be, given your data. If an action is genuinely good you exploit it; if it is merely uncertain, optimism inflates its value, you try it, and you learn — either way you win. The bandit version is the famous upper confidence bound (UCB): pick the arm with the highest mean-plus-confidence-width.
The confidence width comes straight from concentration bounds: the more times you have tried an arm, the tighter its average concentrates around the truth, so the optimism bonus shrinks. Optimism is therefore self-correcting — it explores exactly the actions it is still unsure about and stops wasting time on settled ones.
Optimism made concrete: pick the action with the largest upper confidence bound, where the bonus shrinks as an arm's pull count grows.
UCRL: optimism for whole MDPs
Lifting UCB from one state to a full MDP gives the UCRL algorithm (Upper Confidence RL). Instead of one optimistic number per arm, UCRL maintains a confidence set of plausible MDPs — all transition and reward models consistent with the data so far — and plans for the most rewarding one. It then runs that optimistic policy until some state-action count doubles, recomputes the confidence set, and repeats. This 'plan optimistically, act, shrink uncertainty' loop is the template for nearly all provably-efficient exploration in MDPs.
# UCRL, episode loop (sketch)
while t < T:
M_set = confidence_set(counts, reward_hat, P_hat) # plausible MDPs
pi = plan(optimistic_MDP(M_set)) # extended value iteration
# act under pi until any (s,a) visit count doubles
while not any_count_doubled():
s, a, r, s2 = step(pi); update_counts(s, a, r, s2); t += 1
# regret(T) = O~( D * S * sqrt(A * T) )UCRL's payoff: optimistic confidence sets over plausible MDPs yield regret that scales like √T, not T.
The √T barrier: what no algorithm can beat
Is √T regret merely the best we found, or the best possible? Here the minimax lower bounds answer: one can construct MDPs so statistically confusable that any learner must incur regret at least on the order of √(D·S·A·T). Because UCRL-style upper bounds match this √T scaling (up to the dimension factors), the rate in T is settled. The remaining battle is over the dependence on the diameter D and on S and A — exactly the exploration cost terms.
Interactive Bayesian belief update: a prior distribution is reshaped into a posterior as new evidence arrives.
From regret to sample complexity
Regret and sample complexity are two views of one efficiency. A sublinear-regret algorithm makes only a bounded number of 'large mistakes', and that count is essentially a PAC sample-complexity bound. So UCRL not only learns to act with low cumulative loss, it also certifies a near-optimal policy after a predictable number of samples. Next we ask the harder question: do any of these guarantees survive once the state space is too big for a table?