Notation

General

Symbol	Description
$\mathbb{N}$	Natural numbers, not including zero
$\mathbb{Z}$	Integers
$\mathbb{R}$	Real numbers
$\mathbb{C}$	Complex numbers
$\mathbb{R}^d$	Euclidean space of dimension $d$
$\mathbb{R}^X$	Space of functions from $X$ to $\mathbb{R}$
$C(X;\mathbb{R})$	Space of continuous real-valued functions
$[N]$	Finite set of all integers from $1$ to $N$
$\oplus$	Disjoint union of sets, concatenation of sequences
$\text{𝟙}_{(\cdot )}$	Indicator function
$\mathcal{O}(\cdot )$	Asymptotic upper bound
$\Omega(\cdot )$	Asymptotic lower bound
$\Theta(\cdot )$	Asymptotic upper and lower bound

Probability

Symbol	Description	Link
$(\Omega,\mathcal{F},\operatorname{\mathbb{P}})$	Probability space	A.1
$\sim$	Distribution of a random variable	A.1
$\operatorname*{\mathbb{E}}(\cdot )$	Expectation of a random variable	A.1
$\operatorname{Var}(\cdot )$	Variance of a random variable	A.1
$\operatorname{Cov}(\cdot ,\cdot )$	Covariance between two random variables	A.1
$\operatorname*{\mathbb{E}}(\cdot \mid\cdot )$	Conditional expectation	A.1
$\mathcal{M}_1(X)$	Space of probability measures over $X$	A.1
$\mathcal{M}_1(Y\mid X)$	Space of probability kernels over $Y$ given $X$	A.1
$\delta_x$	Dirac measure centered at $x$	A.1
$\operatorname{N}(\mu,\sigma^2)$	Normal distribution	A.1
$\operatorname{U}(X)$	Uniform distribution over $X$	A.1
$\operatorname{Ber}(p)$	Bernoulli distribution	A.1
$\operatorname{Bin}(n,p)$	Binomial distribution	A.1
$D_{\operatorname{KL}}(\cdot \mid\mid\cdot )$	Kullback–Leibler divergence	A.2
$I(\cdot ;\cdot )$	Mutual information	A.2

Markov Decision Processes

Symbol	Description	Link
$\mathcal{S}$	State space	A.3
$\mathcal{A}$	Action space	A.3
$r$	Reward function	A.3
$p$	Transition kernel	A.3
$\gamma$	Discount factor	A.3
$s_0$	Initial state	A.3
$\pi$	Policy	A.3
$\Pi$	Space of policies	A.3
$V^{(\pi)}(\cdot )$	Value function under policy $\pi$	A.3
$V^*(\cdot )$	Optimal value function	A.3
$\pi^*$	Optimal policy	A.3

Episodic Decision Problems

Symbol	Description	Link
$A$	Action space	2.1
$\mathcal{R}$	Reward function class	2.1
$r$	True reward function	2.1
$q$	Reward distribution in the Bayesian variant	2.1
$r_t$	Sequence of true rewards in the adversarial variant	2.1
$\Sigma$	Observation space	2.1
$\sigma$	Feedback function	2.1
$a_t, \sigma_t$	Action played and feedback observed in episode $t$	2.1
$x_{1:t}$	Sequence from $x_1$ to $x_t$	2.1
$\operatorname{Seq}(X)$	Space of finite-length sequences over $X$	2.2
$p$	Algorithm for an episodic decision problem	2.2
$\mathcal{P}$	Space of algorithms	2.2
$R_T(p,r)$	Cumulative regret	2.3
$r_T(p,r)$	Simple regret	2.3
$r_c(p,r)$	Cost-adjusted simple regret	2.3
$R_T(p,q)$	Bayesian regret	2.3
$V^*_{\operatorname{MDP}}$	Optimal value of the underlying MDP of a Bayesian variant	2.3
$\preceq$	Blackwell order over feedback functions	2.3

Bayesian Models and Algorithms

Symbol	Description	Link
$p_\theta$	Prior distribution for $\theta$	2.2
$p_{y\mid\theta}$	Likelihood for $y$ given $\theta$	2.2
$p_{\theta\mid y}$	Posterior distribution for $\theta$ given $y$	2.2
$\delta$	Decision rule	2.2
$\alpha$	Acquisition function	2.2