CBT {CBT}

Confidence Bound Target (CBT) Algorithm

Description

CBT and EMp_CBT provide simution to infinite arms with Bernoulli Rewards. CBT assumes prior ditribution in known whereas EMp_CBT does not. Ana_CBT performs analysis to real data.

Usage

CBT(n, prior, bn = log(log(n)), cn = log(log(n)))
Emp_CBT(n, prior, bn = log(log(n)), cn = log(log(n)))
Ana_CBT(n, data,  bn = log(log(n)), cn = log(log(n)))

Arguments

n

total number of rewards.

prior

prior distribution on mean of the rewards. Currently avaiable priors: "Uniform", "Sine" and "Cosine".

bn

bn should increse slowly to infinity with n.

cn

cn should increse slowly to infinity with n.

data

A matrix or dataframe. Each column is a population.

Details

If bn or cn are not specified they assume the default value of log(log(n)).
The confidence bound for an arm with t observations is

L = max ( xbar/bn, xbar-cn*sigma/sqrt(t) ),

where xbar and sigma are the mean and standatd deviation of the rewards from that paticular arm.
CBT is a non-recalling algorithm. An arm is played until its confidence bound L drops below the target mean \mu_*, and it is not played after that.
If the prior distribution is unknown, we shall apply empirical CBT, in which the target mean \mu_* is replaced by S/n, with S the sum of rewards among all arms played at current stage. Unlike CBT howerver empirical CBT is a recalling algorithm which decides from among all arms which to play further, rather than to consider only the current arm.

Value

A list including elements

regret

cumulative regret generated by n rewards.

K

total number of experimented arms.

Author(s)

Hock Peng Chan and Shouri Hu

References

H.P. Chan and S. Hu (2018) Infinite Arms Bandit: Optimality via Confidence Bounds <arXiv:1805.11793>

Examples

R = 1000

cum_regret = numeric(R)
arms = numeric(R)

for(i in 1:R){
  result = CBT(n = 10000, prior = "Sine")
  cum_regret[i] = result$regret
  arms[i] = result$K
}

mean(cum_regret)
sd(cum_regret)/sqrt(R)
mean(arms)
sd(arms)/sqrt(R)