Documentation

# Documentation

## Functions

function klBern(x, y)

Kullback-Leibler divergence for Bernoulli distributions. https://en.wikipedia.org/wiki/Bernoulli_distribution#Kullback.E2.80.93Leibler_divergence

$\mathrm{KL}(\mathcal{B}(x), \mathcal{B}(y)) = x \log(\frac{x}{y}) + (1-x) \log(\frac{1-x}{1-y}).$
    julia> klBern(0.5, 0.5)
0.0
julia> klBern(0.1, 0.9)
1.757779...
julia> klBern(0.9, 0.1)  # And this KL is symmetric
1.757779...
julia> klBern(0.4, 0.5)
0.020135...
julia> klBern(0.01, 0.99)
4.503217...
• Special values:

    julia> klBern(0, 1)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
34.539575...
source
function klBin(x, y, n)

Kullback-Leibler divergence for Binomial distributions. https://math.stackexchange.com/questions/320399/kullback-leibner-divergence-of-binomial-distributions

• It is simply the n times klBern on x and y.

$\mathrm{KL}(\mathrm{Bin}(x, n), \mathrm{Bin}(y, n)) = n \times \left(x \log(\frac{x}{y}) + (1-x) \log(\frac{1-x}{1-y}) \right).$
• Warning: The two distributions must have the same parameter n, and x, y are p, q in (0, 1).

    julia> klBin(0.5, 0.5, 10)
0.0
julia> klBin(0.1, 0.9, 10)
17.57779...
julia> klBin(0.9, 0.1, 10)  # And this KL is symmetric
17.57779...
julia> klBin(0.4, 0.5, 10)
0.20135...
julia> klBin(0.01, 0.99, 10)
45.03217...
• Special values:

    julia> klBin(0, 1, 10)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
345.39575...
source
function klPoisson(x, y)

Kullback-Leibler divergence for Poison distributions. https://en.wikipedia.org/wiki/Poisson_distribution#Kullback.E2.80.93Leibler_divergence

$\mathrm{KL}(\mathrm{Poisson}(x), \mathrm{Poisson}(y)) = y - x + x \times \log(\frac{x}{y}).$
    julia> klPoisson(3, 3)
0.0
julia> klPoisson(2, 1)
0.386294...
julia> klPoisson(1, 2)  # And this KL is non-symmetric
0.306852...
julia> klPoisson(3, 6)
0.920558...
julia> klPoisson(6, 8)
0.273907...
• Special values:

    julia> klPoisson(1, 0)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
33.538776...
julia> klPoisson(0, 0)
0.0
source
function klExp(x, y)

Kullback-Leibler divergence for exponential distributions. https://en.wikipedia.org/wiki/Exponential_distribution#Kullback.E2.80.93Leibler_divergence

.. math::

\mathrm{KL}(\mathrm{Exp}(x), \mathrm{Exp}(y)) = \begin{cases}
\frac{x}{y} - 1 - \log(\frac{x}{y}) & \text{if} x > 0, y > 0\\
+\infty & \text{otherwise}
\end{cases}
    julia> klExp(3, 3)
0.0
julia> klExp(3, 6)
0.193147...
julia> klExp(1, 2)  # Only the proportion between x and y is used
0.193147...
julia> klExp(2, 1)  # And this KL is non-symmetric
0.306852...
julia> klExp(4, 2)  # Only the proportion between x and y is used
0.306852...
julia> klExp(6, 8)
0.037682...
• x, y have to be positive:

    julia> klExp(-3, 2)
Inf
julia> klExp(3, -2)
Inf
julia> klExp(-3, -2)
Inf
source
function klGamma(x, y, a=1)

Kullback-Leibler divergence for gamma distributions. https://en.wikipedia.org/wiki/Gamma_distribution#Kullback.E2.80.93Leibler_divergence

• It is simply the a times klExp on x and y.

.. math::

\mathrm{KL}(\Gamma(x, a), \Gamma(y, a)) = \begin{cases}
a \times \left( \frac{x}{y} - 1 - \log(\frac{x}{y}) \right) & \text{if} x > 0, y > 0\\
+\infty & \text{otherwise}
\end{cases}
• Warning: The two distributions must have the same parameter a.

    julia> klGamma(3, 3)
0.0
julia> klGamma(3, 6)
0.193147...
julia> klGamma(1, 2)  # Only the proportion between x and y is used
0.193147...
julia> klGamma(2, 1)  # And this KL is non-symmetric
0.306852...
julia> klGamma(4, 2)  # Only the proportion between x and y is used
0.306852...
julia> klGamma(6, 8)
0.037682...
• x, y have to be positive:

    julia> klGamma(-3, 2)
Inf
julia> klGamma(3, -2)
Inf
julia> klGamma(-3, -2)
Inf
source
function klNegBin(x, y, r=1)

Kullback-Leibler divergence for negative binomial distributions. https://en.wikipedia.org/wiki/Negative_binomial_distribution

$\mathrm{KL}(\mathrm{NegBin}(x, r), \mathrm{NegBin}(y, r)) = r \times \log((r + x) / (r + y)) - x \times \log(y \times (r + x) / (x \times (r + y))).$
• Warning: The two distributions must have the same parameter r.

    julia> klNegBin(0.5, 0.5)
0.0
julia> klNegBin(0.1, 0.9)
-0.711611...
julia> klNegBin(0.9, 0.1)  # And this KL is non-symmetric
2.0321564...
julia> klNegBin(0.4, 0.5)
-0.130653...
julia> klNegBin(0.01, 0.99)
-0.717353...
• Special values:

    julia> klBern(0, 1)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
34.539575...
• With other values for r:

    julia> klNegBin(0.5, 0.5, r=2)
0.0
julia> klNegBin(0.1, 0.9, r=2)
-0.832991...
julia> klNegBin(0.1, 0.9, r=4)
-0.914890...
julia> klNegBin(0.9, 0.1, r=2)  # And this KL is non-symmetric
2.3325528...
julia> klNegBin(0.4, 0.5, r=2)
-0.154572...
julia> klNegBin(0.01, 0.99, r=2)
-0.836257...
source
function klGauss(x, y, sig2x=0.25, sig2y=0.25)

Kullback-Leibler divergence for Gaussian distributions of means $x$ and $y$ and variances $sig2x$ and $sig2y$, $\nu_1 = \mathcal{N}(x, \sigma_x^2)$ and $\nu_2 = \mathcal{N}(y, \sigma_x^2)$:

$\mathrm{KL}(\nu_1, \nu_2) = \frac{(x - y)^2}{2 \sigma_y^2} + \frac{1}{2}\left( \frac{\sigma_x^2}{\sigma_y^2} - 1 \log\left(\frac{\sigma_x^2}{\sigma_y^2}\right) \right).$

See https://en.wikipedia.org/wiki/Normal_distribution#Other_properties

• By default, sig2y is assumed to be sig2x (same variance).

    julia> klGauss(3, 3)
0.0
julia> klGauss(3, 6)
18.0
julia> klGauss(1, 2)
2.0
julia> klGauss(2, 1)  # And this KL is symmetric
2.0
julia> klGauss(4, 2)
8.0
julia> klGauss(6, 8)
8.0
• x, y can be negative:

    julia> klGauss(-3, 2)
50.0
julia> klGauss(3, -2)
50.0
julia> klGauss(-3, -2)
2.0
julia> klGauss(3, 2)
2.0
• With other values for sig2x:

    julia> klGauss(3, 3, sig2x=10)
0.0
julia> klGauss(3, 6, sig2x=10)
0.45
julia> klGauss(1, 2, sig2x=10)
0.05
julia> klGauss(2, 1, sig2x=10)  # And this KL is symmetric
0.05
julia> klGauss(4, 2, sig2x=10)
0.2
julia> klGauss(6, 8, sig2x=10)
0.2
• With different values for sig2x and sig2y:

    julia> klGauss(0, 0, sig2x=0.25, sig2y=0.5)
-0.0284...
julia> klGauss(0, 0, sig2x=0.25, sig2y=1.0)
0.2243...
julia> klGauss(0, 0, sig2x=0.5, sig2y=0.25)  # not symmetric here!
1.1534...

julia> klGauss(0, 1, sig2x=0.25, sig2y=0.5)
0.9715...
julia> klGauss(0, 1, sig2x=0.25, sig2y=1.0)
0.7243...
julia> klGauss(0, 1, sig2x=0.5, sig2y=0.25)  # not symmetric here!
3.1534...

julia> klGauss(1, 0, sig2x=0.25, sig2y=0.5)
0.9715...
julia> klGauss(1, 0, sig2x=0.25, sig2y=1.0)
0.7243...
julia> klGauss(1, 0, sig2x=0.5, sig2y=0.25)  # not symmetric here!
3.1534...
• Warning: Using :class:Policies.klUCB (and variants) with klGauss is equivalent to use :class:Policies.UCB, so prefer the simpler version.

source
function klucb(x, d, kl, upperbound, lowerbound=-Inf, precision=1e-6, max_iterations=50)

The generic KL-UCB index computation.

• x: value of the cum reward,

• d: upper bound on the divergence,

• kl: the KL divergence to be used (klBern, klGauss, etc),

• upperbound, lowerbound=-Inf: the known bound of the values x,

• precision=1e-6: the threshold from where to stop the research,

• max_iterations: max number of iterations of the loop (safer to bound it to reduce time complexity).

• Note: It uses a bisection search, and one call to $kl$ for each step of the bisection search.

For example, for klucbBern, the two steps are to first compute an upperbound (as precise as possible) and the compute the kl-UCB index:

    julia> x, d = 0.9, 0.2   # mean x, exploration term d
julia> upperbound = min(1.0, klucbGauss(x, d, sig2x=0.25))  # variance 1/4 for [0,1] bounded distributions
julia> upperbound
1.0
julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-3, max_iterations=10)
0.9941...
julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-6, max_iterations=10)
0.994482...
julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-3, max_iterations=50)
0.9941...
julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-6, max_iterations=100)  # more and more precise!
0.994489...
• Note: See below for more examples for different KL divergence functions.

source
function klucbBern(x, d, precision=1e-6)

KL-UCB index computation for Bernoulli distributions, using klucb.

• Influence of x:

    julia> klucbBern(0.1, 0.2)
0.378391...
julia> klucbBern(0.5, 0.2)
0.787088...
julia> klucbBern(0.9, 0.2)
0.994489...
• Influence of d:

    julia> klucbBern(0.1, 0.4)
0.519475...
julia> klucbBern(0.1, 0.9)
0.734714...

julia> klucbBern(0.5, 0.4)
0.871035...
julia> klucbBern(0.5, 0.9)
0.956809...

julia> klucbBern(0.9, 0.4)
0.999285...
julia> klucbBern(0.9, 0.9)
0.999995...
source
function klucbGauss(x, d, sig2x=0.25, precision=0.0)

KL-UCB index computation for Gaussian distributions.

• Note: it does not require any search.

• Warning: it works only if the good variance constant is given.

• Influence of x:

    julia> klucbGauss(0.1, 0.2)
0.416227...
julia> klucbGauss(0.5, 0.2)
0.816227...
julia> klucbGauss(0.9, 0.2)
1.216227...

- Influence of d:


julia julia> klucbGauss(0.1, 0.4) 0.547213... julia> klucbGauss(0.1, 0.9) 0.770820...

julia> klucbGauss(0.5, 0.4)
0.947213...
julia> klucbGauss(0.5, 0.9)
1.170820...

julia> klucbGauss(0.9, 0.4)
1.347213...
julia> klucbGauss(0.9, 0.9)
1.570820...



• Warning: Using :class:Policies.klUCB (and variants) with klucbGauss is equivalent to use :class:Policies.UCB, so prefer the simpler version.

source
function klucbPoisson(x, d, precision=1e-6)

KL-UCB index computation for Poisson distributions, using klucb.

• Influence of x:

    julia> klucbPoisson(0.1, 0.2)
0.450523...
julia> klucbPoisson(0.5, 0.2)
1.089376...
julia> klucbPoisson(0.9, 0.2)
1.640112...
• Influence of d:

    julia> klucbPoisson(0.1, 0.4)
0.693684...
julia> klucbPoisson(0.1, 0.9)
1.252796...

julia> klucbPoisson(0.5, 0.4)
1.422933...
julia> klucbPoisson(0.5, 0.9)
2.122985...

julia> klucbPoisson(0.9, 0.4)
2.033691...
julia> klucbPoisson(0.9, 0.9)
2.831573...
source
function klucbExp(x, d, precision=1e-6)

KL-UCB index computation for exponential distributions, using klucb.

• Influence of x:

    julia> klucbExp(0.1, 0.2)
0.202741...
julia> klucbExp(0.5, 0.2)
1.013706...
julia> klucbExp(0.9, 0.2)
1.824671...
• Influence of d:

    julia> klucbExp(0.1, 0.4)
0.285792...
julia> klucbExp(0.1, 0.9)
0.559088...

julia> klucbExp(0.5, 0.4)
1.428962...
julia> klucbExp(0.5, 0.9)
2.795442...

julia> klucbExp(0.9, 0.4)
2.572132...
julia> klucbExp(0.9, 0.9)
5.031795...
source
function klucbGamma(x, d, precision=1e-6)

KL-UCB index computation for Gamma distributions, using klucb.

• Influence of x:

    julia> klucbGamma(0.1, 0.2)
0.202...
julia> klucbGamma(0.5, 0.2)
1.013...
julia> klucbGamma(0.9, 0.2)
1.824...
• Influence of d:

    julia> klucbGamma(0.1, 0.4)
0.285...
julia> klucbGamma(0.1, 0.9)
0.559...

julia> klucbGamma(0.5, 0.4)
1.428...
julia> klucbGamma(0.5, 0.9)
2.795...

julia> klucbGamma(0.9, 0.4)
2.572...
julia> klucbGamma(0.9, 0.9)
5.031...`
source