Exp3 exponential-weight adversarial bandit

The Exp3 algorithm of Auer, Cesa-Bianchi, Freund and Schapire (2002), figure 1: weights start at 1; at each trial \(p_i(t) = (1-\gamma) w_i(t) / \sum_j w_j(t) + \gamma/K,\) an action is drawn from p(t), and only the chosen action updates its weight with the importance-weighted reward: \(w_i(t+1) = w_i(t) \exp(\gamma (x_i(t)/p_i(t)) / K).\) Theorem 3.1 of the source bounds the expected weak regret. The draw consumes exactly one uniform per trial, by inverse CDF on the probabilities in index order, mirroring the Python arm bit-exactly.

Usage

Exp3(x, gamma_, T = NULL, seed = 0)

Arguments

x

Matrix (T, K): reward each action pays at each trial, in 0 to 1.

gamma_

Mixing/learning parameter in (0, 1].

T

Number of trials (default all rows).

seed

SplitMix64 seed.

Value

List with estimate (0-based action with the largest final weight), actions, rewards, probs ((T, K) matrix), weights, total_reward, method.

References

Auer, P., Cesa-Bianchi, N., Freund, Y. and Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32(1), 48-77. Algorithm: figure 1, Section 3; bound: Theorem 3.1.

Examples

x <- matrix(rep(c(1, 0), 5), ncol = 2, byrow = TRUE)
Exp3(x, 0.2)$weights
#> [1] 2.060665 1.000000