UCB1 index policy on a fixed reward table

The deterministic policy UCB1 of Auer, Cesa-Bianchi and Fischer (2002), figure 1: play each machine once, then always play the machine maximizing \(\bar{x}_j + \sqrt{2 \ln n / n_j}\) where \(\bar{x}_j\) is the average reward obtained from machine j, \(n_j\) its play count so far and n the overall number of plays done so far. The policy is deterministic given the observed rewards, so it is run against a caller-supplied (T, K) table whose row t holds the reward each machine would pay at play t. Rewards have support 0 to 1 in the source; Theorem 1 gives the logarithmic regret bound. Initialization plays machines in index order; ties in the index break to the lowest machine.

Usage

Ucbb(x, T = NULL)

Arguments

x

Matrix (T, K) of realized rewards.

T

Number of plays (default all rows; at least K).

Value

List with estimate (0-based machine with the highest final average reward), actions (0-based machine per play), rewards, means, counts, index (final UCB index with n = T), total_reward, method.

References

Auer, P., Cesa-Bianchi, N. and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235-256. Policy: figure 1, p. 237; bound: Theorem 1.

Examples

x <- matrix(rep(c(1, 0), 6), ncol = 2, byrow = TRUE)
Ucbb(x)$actions
#> [1] 0 1 0 0 0 0