Skip to main content
Here we document the technical details behind GrowthBook’s contextual bandit variation weight updates.

​
Thompson Sampling

Suppose we have KK variations, and we want to update the variation weights for a given context.
For the kk-th variation, define its mean as μk\mu_k, k = 1, …, K. Denote the probabiity that μk\mu_{k} is larger than the other means as as wkw_k.
Under Thompson Sampling, wkw_k is the variation weight for the kk-th variation. Define the posterior mean of μk\mu_k as mkm_k and its posterior variance as vk2v_k^2.
Define its posterior standard deviation as sk=vk2s_k = \sqrt{v_k^2}. Define the posterior distribution of μk\mu_k as fk(μk)f_k(\mu_k). This best-arm probability can be expressed as: wk=P([μk>μ1]∩[μk>μ2]∩⋯∩[μk>μk−1]∩[μk>μk+1]∩⋯∩[μk>μK])=∫−∞μk∫−∞μk⋯∫−∞μk∫−∞∞∫−∞μ1⋯∫−∞μ1∏i=1Kfi(μi)dμi=∫−∞∞fk(μk){∫−∞μk⋯∫−∞μk∏i≠kfi(μi)dμi}dμk=∫−∞∞fk(μk)∏i≠kΦ(μk−misi)dμk.\begin{align*} w_k &= P\left(\left[\mu_k > \mu_1 \right] \cap \left[\mu_k > \mu_2 \right] \cap \cdots \cap \left[\mu_k > \mu_{k-1} \right] \cap \left[\mu_k > \mu_{k+1} \right] \cap \cdots \cap \left[\mu_k > \mu_K \right]\right) \\ &= \int_{-\infty}^{\mu_{k}}\int_{-\infty}^{\mu_{k}} \cdots \int_{-\infty}^{\mu_{k}} \int_{-\infty}^{\infty} \int_{-\infty}^{\mu_{1}} \cdots \int_{-\infty}^{\mu_{1}} \prod_{i=1}^{K} f_{i}(\mu_i) d\mu_i \\ &= \int_{-\infty}^{\infty}f_{k}(\mu_k) \left\{\int_{-\infty}^{\mu_{k}} \cdots \int_{-\infty}^{\mu_{k}} \prod_{i\ne k} f_{i}(\mu_i) d\mu_i \right\} d\mu_k \\ &= \int_{-\infty}^{\infty}f_{k}(\mu_k) \prod_{i\ne k} \Phi\left(\frac{\mu_{k} - m_{i} }{s_{i}}\right) d\mu_k. \end{align*} We leverage the fact that the posterior distributions of the μi\mu_i are normal and independent. The result above can be expressed as the expected value of the function below over the distribution of μk\mu_k ∏i≠kΦ(μk−misi).\prod_{i\ne k} \Phi\left(\frac{\mu_{k} - m_{i} }{s_{i}}\right). We use Gauss-Hermite quadrature to approximate the integral. Our integral is well suited for Gauss-Hermite quadrature, as the function inside the integral is smooth and light-tailed.
Let t=μk−mksk,t = \frac{\mu_{k} - m_{k} }{s_{k}}, which implies that μk=mk+tsk.\mu_{k} = m_{k} + t s_{k}. Define the standard normal distribution as ϕ(.)\phi(.). The integral can be represented as: wk=∫−∞∞{∏i≠kΦ(mk+tsk−misi)}ϕ(t)dt.\begin{align*} w_k &= \int_{-\infty}^{\infty} \left\{ \prod_{i\ne k} \Phi\left(\frac{m_{k} + t s_{k} - m_{i} }{s_{i}}\right)\right\} \phi(t) dt. \end{align*} Letting u=t/(2)u = t / \sqrt(2) places the integral in the standard form for the Gauss-Hermite quadrature, which is ∫−∞∞exp⁡−u2g(u)du.\int_{-\infty}^{\infty} \exp^{-u^2} g(u) du.