Beta-Bernoulli Thompson sampling

Algorithm 3.2 (BernTS) of Russo et al. (2018): at each period sample \(\hat\theta_k \sim Beta(\alpha_k, \beta_k)\) for every action, apply \(x_t = \arg\max_k \hat\theta_k\), observe the Bernoulli reward and update the chosen action conjugately, \((\alpha_x, \beta_x) \leftarrow (\alpha_x + r_t, \beta_x + 1 - r_t).\) The probability-matching idea is Thompson (1933). Each period consumes one Beta draw per action in index order and then one uniform for the reward, bit-exactly as the Python arm; argmax ties break to the lowest action.

Usage

Thomp(p, T, alpha0 = NULL, beta0 = NULL, seed = 0)

Arguments

p

True Bernoulli success probabilities (the simulated environment), length K.

T

Number of periods.

alpha0

Beta prior alpha, length K (default all 1).

beta0

Beta prior beta, length K (default all 1).

seed

SplitMix64 seed.

Value

List with estimate (0-based arm with the largest posterior mean), actions, rewards, alpha, beta, post_mean, counts, total_reward, method.

References

Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I. and Wen, Z. (2018). A tutorial on Thompson sampling. Foundations and Trends in Machine Learning 11(1), 1-96 (arXiv:1707.02038). Algorithm 3.2 (BernTS), Section 3 conjugate update. Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3-4), 285-294.

Examples

Thomp(c(0.8, 0.2), 20, seed = 1)$counts
#> [1] 15  5