Bandits are the simplest reinforcement-learning problems with exploration. There is no state transition, only repeated action choice under uncertainty.
Stochastic bandit model
Each arm has an unknown reward distribution, and the learner observes only the reward of the chosen arm.
Definition. A \(K\)-armed stochastic bandit has reward distributions \(\nu_1,\ldots,\nu_K\) with means \(\mu_a\). At time \(t\), the learner chooses \(A_t\), observes \(R_t\sim\nu_{A_t}\), and seeks small regret \[ \operatorname{Reg}(T)=T\mu^*-\sum_{t=1}^TR_t. \]
Proposition. The expected regret is \(\sum_a\Delta_a\mathbb E N_a(T)\), where \(\Delta_a=\mu^*-\mu_a\).
Proof. Take expectation of \(T\mu^*-\sum_tR_t\). Conditional on \(A_t=a\), \(\mathbb E R_t=\mu_a\). Group the resulting \(\mu^*-\mu_a\) terms by arm.
Upper confidence bounds
UCB balances empirical mean and uncertainty radius.
Definition. For sub-Gaussian rewards, UCB chooses \[ A_t\in\operatorname*{argmax}_a\left\{\hat\mu_a(t)+\sqrt{\frac{2\log t}{N_a(t)}}\right\}. \]
Theorem. For each suboptimal arm \(a\), UCB pulls arm \(a\) \(O((\log T)/\Delta_a^2)\) times in expectation, yielding regret \(O(\sum_a(\log T)/\Delta_a)\).
Proof. On the high-probability event that all empirical means stay within their confidence radii, a suboptimal arm can be selected only if its confidence radius is large enough to bridge the gap \(\Delta_a\). This implies \(N_a(t)\lesssim(\log T)/\Delta_a^2\). The failure event contributes only a bounded additional amount by concentration and summability.
Thompson sampling
Posterior sampling randomizes according to uncertainty about which arm is best.
Definition. Thompson sampling maintains a posterior distribution over arm means, samples a plausible parameter vector from the posterior, and pulls the arm optimal for that sample.
Remark. For conjugate Bernoulli-beta bandits, the update is explicit. Regret analysis shows that posterior sampling often matches logarithmic gap-dependent rates under regularity.
Lower bounds
Logarithmic regret is unavoidable for uniformly good algorithms in parametric bandits.
Theorem. For many one-parameter reward families, any uniformly efficient algorithm must satisfy asymptotic lower bounds of Lai-Robbins type: \[ \liminf_{T\to\infty}\frac{\mathbb E N_a(T)}{\log T}\ge \frac{1}{\operatorname{KL}(\nu_a,\nu_{a^*})} \] with the appropriate alternative distribution in the denominator.
Proof. If a suboptimal arm is sampled too rarely, the data cannot statistically distinguish the true instance from an alternative in which that arm is optimal. A change-of-measure argument relates the probability of correct behavior under the two instances to the accumulated KL information, forcing at least logarithmically many samples.
Stochastic bandit model
Arm \(a\in\{1,\ldots,K\}\) produces iid rewards with law \(\nu_a\), mean \(\mu_a\), and sub-Gaussian scale \(\sigma\). Let \(\mu^*=\max_a\mu_a\), \(\Delta_a=\mu^*-\mu_a\), and let \(A_t\) be chosen from past observations. Pseudo-regret is \[ \bar R_T =T\mu^*-\sum_{t=1}^TE\mu_{A_t} =\sum_{a=1}^K\Delta_aE N_a(T). \] This decomposition turns regret analysis into control of suboptimal pull counts.
UCB and a gap-dependent proof
For \(\sigma\)-sub-Gaussian rewards, UCB selects \[ A_t\in\arg\max_a \left\{\widehat\mu_a(t-1) +\sqrt{\frac{2\sigma^2c\log t}{N_a(t-1)}}\right\}, \] after pulling every arm once.
Theorem. For \(c>1\), each suboptimal arm satisfies \[ E N_a(T) \le \frac{8c\sigma^2\log T}{\Delta_a^2}+C_c, \] and hence \[ \bar R_T \le\sum_{a:\Delta_a>0} \frac{8c\sigma^2\log T}{\Delta_a} +\sum_a C_c\Delta_a. \]
Proof. Once \(N_a\ge8c\sigma^2\log T/\Delta_a^2\), arm \(a\)'s confidence radius is at most \(\Delta_a/2\). If it is nevertheless selected, either its empirical mean exceeds \(\mu_a\) by its radius or the optimal arm's empirical mean falls below \(\mu^*\) by its radius. Sub-Gaussian concentration makes either event at time \(t\) have probability at most \(2t^{-c}\). Summing over \(t\) gives the constant \(C_c\).
Distribution-dependent lower bounds
Theorem (Lai--Robbins form). For a uniformly efficient policy in an identifiable parametric bandit, \[ \liminf_{T\to\infty} \frac{E N_a(T)}{\log T} \ge\frac1{\inf_{\nu:\,E_\nu X>\mu^*} D_{\mathrm{KL}}(\nu_a\|\nu)} \] for every suboptimal arm \(a\).
The proof changes arm \(a\)'s law to an alternative under which it is optimal. The trajectory KL divergence equals \(EN_a(T)D_{\mathrm{KL}}(\nu_a\|\nu)\). If this information were smaller than \(\log T\), no test could reliably distinguish the environments while maintaining low regret in both. KL-UCB is designed to match this information constraint.
Minimax regret and Thompson sampling
Gap-dependent bounds become large when gaps vanish. Minimax regret over \(\sigma\)-sub-Gaussian \(K\)-armed instances is of order \(\sigma\sqrt{KT}\). MOSS attains this rate without an extra \(\sqrt{\log T}\) factor. Thompson sampling draws a parameter from the posterior and acts optimally for that draw; its probability-matching interpretation is Bayesian, while frequentist regret bounds require prior support and concentration arguments.
Best-arm identification
Pure exploration changes the objective. With confidence \(1-\delta\), one seeks the best arm using as few samples as possible. Instance complexity is roughly \[ \sum_{a\ne a^*}\Delta_a^{-2}\log(1/\delta), \] but optimal allocations solve a KL information game. Low regret and rapid identification are related but not equivalent goals.