Bandit Algorithms

Notation 5

V variance
Supp support of distribution or random variable
∇f(x) gradient offatx
∇^2 f(x) Hessian offatx
∨,∧ maximum and minimum,a∨b=max(a,b) anda∧b=min(a,b)
erf(x) √^2 π

∫x

0 exp(−y

(^2) )dy
erfc(x) 1 −erf(x)
Γ(z) Gamma function, Γ(z) =

∫∞

0 x

z− (^1) exp(−x)dx
φA(x) support functionφA(x) = supy∈A〈x,y〉
f(∗(y) convex conjugate,f∗(y) = supx∈A〈x,y〉−f(x)
n
k

)

binomial coefficient
argmaxxf(x) maximizer or maximizers off
argminxf(x) minimizer or minimizers off
Iφ indicator function: converts Booleanφinto binary
IB indicator of setB

Linear algebra
e 1 ,...,ed standard basis vectors of thed-dimensional Euclidean space
0 , 1 vectors whose elements are all zeros and all ones, respectively
det(A) determinant of matrixA
trace(A) trace of matrixA
im(A) image of matrixA
ker(A) kernel of matrixA
span(v 1 ,...,vd) span of vectorsv 1 ,...,vd
λmin(G) minimum eigenvalue of matrixG
〈x,y〉 inner product,〈x,y〉=

∑

ixiyi
‖x‖p p-norm of vectorx
‖x‖^2 G x>Gxfor positive definiteG∈Rd×dandx∈Rd

Distributions
N(μ,σ^2 ) Normal distribution with meanμand varianceσ^2
B(p) Bernoulli distribution with meanp
U(a,b) uniform distribution supported on [a,b]
Beta(α,β) Beta distribution with parametersα,β > 0
δx Dirac distribution with point mass atx

Topological
cl(A) closure of setA
int(A) interior of setA
∂A boundary of a setA,∂A= cl(A)\int(A)
co(A) convex hull ofA
aff(A) affine hull ofA
ri(A) relative interior ofA