UCRL (upper confidence reinforcement learning)

UCRL is the canonical way to get a provable regret bound in unknown MDPs, built on a simple slogan: optimism in the face of uncertainty. The agent keeps statistics on rewards and transitions, builds confidence intervals around them, and then plans as if the environment were the best it could plausibly be within those intervals. Acting on that rosy model naturally drives the agent toward states it is still unsure about.

Concretely, UCRL2 proceeds in episodes. At the start of each it forms a set of plausible MDPs consistent with the data, picks the most optimistic one, computes its optimal policy by extended value iteration, and follows it until some state-action count doubles, then re-plans. This optimism-driven exploration earns a regret bound of order the diameter times the square root of S·A·T, close to the minimax floor. Posterior-sampling variants achieve similar guarantees more simply.

The guarantees are beautiful but the algorithm is rarely run as-is at scale: planning over a whole confidence set is expensive, and the bounds assume tabular or tightly structured MDPs. Its lasting contribution is the optimism principle that underlies most modern exploration methods.