We model reinforcement learning as a Markov decision process (MDP). We define an MDP as $(\mathcal{S}, \mathcal{A}, T, R, p_0, \gamma)$, in which both the state space $\mathcal{S}$ and action space $\mathcal{A}$ are discrete, $T: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \mapsto \mathbb{R}_+$ is the transition distribution, $R: \mathcal{S} \times \mathcal{A} \mapsto \mathbb{R}$ is the reward function, and $\gamma \in (0, 1]$ is a discount factor, and $p_0$ is the initial state distribution. We denote a transition experience as $\tau=(s, a, r, s')$ where $s' \sim T(s'|s, a)$ and $r = R(s, a)$. A policy $\pi: \mathcal{S} \mapsto \mathcal{A}$ specifies the action taken after observing a state. We denote the $Q$-function for policy $\pi$ as $Q^{\pi}(s, a):= {\operatorname{\mathbb{E}}}_{\pi}\big[\sum\nolimits_{t=0}^{\infty} \gamma^t r_t | s_0=s, a_0=a \big]$. The optimal $Q^*$-function corresponds to taking the optimal policy $$Q^*(s, a) := \sup_{\pi} Q^{\pi}(s, a)$$ and satisfies the Bellman equation $$Q^*(s, a) = \mathbb{E}_{s'\sim T(\cdot|s, a)}\big[  r + \gamma \cdot \max_{a'}Q^*(s', a')\big].$$

Exploration in reinforcement learning {#section:exploration}
-------------------------------------

A notable early optimality result in reinforcement learning was the proof by Watkins and Dayan [@watkins1989learning; @watkins1992q] that an online $Q$-learning algorithm is guaranteed to converge to the optimal policy, provided that every state is visited an infinite number 