Exploration is the statistical cost of learning what actions do. Regret measures this cost by comparing the learner's accumulated reward with an oracle policy.
Regret
Regret converts online learning into a sequence of excess-risk comparisons.
Definition. For rewards and optimal value benchmark \(V^*\), cumulative regret over horizon \(T\) is \[ \operatorname{Reg}(T)=\sum_{t=1}^T\{V^*(S_t)-R_t\} \] in episodic or continuing forms adapted to the model. For bandits, \(\operatorname{Reg}(T)=T\mu^*-\sum_{t=1}^T\mu_{A_t}\).
Remark. Sublinear regret means the average cost of exploration vanishes.
Optimism
Optimism chooses actions that could plausibly be best given current uncertainty.
Proposition. In a bandit problem, if upper confidence bounds \(U_t(a)\) satisfy \(\mu_a\le U_t(a)\) for all arms on a high-probability event, choosing \(A_t\in\operatorname*{argmax}_aU_t(a)\) explores arms whose uncertainty can still affect optimality.
Proof. On the confidence event, the optimal mean \(\mu^*\le U_t(a^*)\le U_t(A_t)\). If \(A_t\) is suboptimal, its upper bound must still be high enough to cover the optimal mean. Thus either its empirical mean is unusually high or its uncertainty radius is still large; confidence rules out the former and limits the number of times the latter can occur.
Regret decomposition
For finite bandits, regret is a sum over suboptimal arm pulls.
Proposition. For arm gaps \(\Delta_a=\mu^*-\mu_a\), \[ \mathbb E\operatorname{Reg}(T)=\sum_{a:\Delta_a>0}\Delta_a\,\mathbb E N_a(T). \]
Proof. Each time arm \(a\) is pulled, the expected loss relative to the best arm is \(\Delta_a\). Sum over time and group by arm, then take expectations.
Exploration in MDPs
MDP exploration is harder because information is gathered through state visitation.
Remark. Optimism and posterior sampling extend to MDPs by adding uncertainty bonuses or sampling plausible models. The difficulty is that actions affect both immediate reward and future information through the transition kernel.
Regret in episodic MDPs
For episodes \(k=1,\ldots,K\) of horizon \(H\), initial states \(s_1^k\), and policies \(\pi_k\), regret is \[ \operatorname{Regret}(K) =\sum_{k=1}^K \{V_1^*(s_1^k)-V_1^{\pi_k}(s_1^k)\}. \] It compares learning online with a policy that knew the MDP. This differs from sample complexity of identifying an \(\varepsilon\)-optimal policy after a separate exploration phase.
Optimism and Bellman bonuses
Suppose empirical estimates \(\widehat r_k,\widehat P_k\) are based on \(N_k(s,a)\) visits. An optimistic recursion has the form \[ \widehat Q_{k,h}(s,a) =\min\left\{H-h+1,\, \widehat r_k(s,a)+ \widehat P_k\widehat V_{k,h+1}(s,a) +b_{k,h}(s,a)\right\}, \] \[ \widehat V_{k,h}(s)=\max_a\widehat Q_{k,h}(s,a). \] The bonus upper-bounds reward and transition estimation error uniformly. Backward induction then proves \(\widehat V_{k,h}\ge V_h^*\) on the confidence event.
Proposition (regret decomposition). On an optimism event, the regret of the greedy optimistic policy is bounded by \[ \sum_{k,h} b_{k,h}(S_h^k,A_h^k) +\sum_{k,h}M_{k,h}, \] where \(M_{k,h}\) is a martingale-difference transition fluctuation.
Proof. Compare optimistic and true Bellman recursions along the realized policy. At each step, add and subtract the true conditional expectation. The predictable discrepancy is controlled by the bonus; the empirical next-state deviation is a martingale difference. Telescope the value differences over the horizon and episodes.
With Hoeffding-style bonuses of order \(\sqrt{H^2\log(1/\delta)/N_k(s,a)}\), the counting identity \[ \sum_{j=1}^{n}\frac1{\sqrt j}\le2\sqrt n \] and Cauchy--Schwarz produce sublinear regret. Bernstein bonuses exploit conditional variance and can achieve the sharp finite-MDP scale \(\widetilde O(\sqrt{H^2SAK})\) under standard formulations.
Why undirected exploration can fail
Random action noise does not target epistemic uncertainty and can take exponential time to reach a rewarding state in a long chain. Optimism, posterior sampling, count bonuses, and information-gain objectives propagate uncertainty through the transition graph. Efficient exploration is therefore a planning problem, not merely a local action-randomization rule.
Lower-bound mechanism
Regret lower bounds embed many nearly indistinguishable bandit problems into states or stages. A change-of-measure argument shows that identifying which transition or reward is better requires a number of visits inverse to the squared gap. Balancing information acquisition against loss yields \(\Omega(\sqrt{H^2SAK})\)-type minimax scales, with exact powers of \(H\) depending on the model and regret convention.