# An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond

The general structure of the code (and some functions) is taken from [this library](https://bitbucket.org/wmkoolen/tidnabbil/src/master/). References to the papers of the authors of this library are already included in the paper.

## Setting up the environment

**Install Julia**
```
wget https://julialang-s3.julialang.org/bin/linux/x64/1.9/julia-1.9.0-linux-x86_64.tar.gz
tar zxvf julia-1.9.0-linux-x86_64.tar.gz
export PATH="$PATH:/path/to/<Julia directory>/bin"
```

**Install packages**
```
julia
using Pkg;
Pkg.add(["JLD2", "Printf", "JSON", "Dates", "IterTools", "Distributed", "JuMP", "Tulip",
         "Random", "LinearAlgebra", "Distributions", "Combinatorics", "CPUTime",
         "StatsPlots", "ArgParse", "Statistics", "StatsBase", "Plots",
         "Pickle", "ColorSchemes", "SpecialFunctions", "LambertW", "LaTeXStrings"]);
using JLD2, Printf, JSON, Dates, IterTools, Distributed, JuMP, Tulip, StatsBase;
using Random, LinearAlgebra, Distributions, Combinatorics, CPUTime, StatsPlots, Statistics;
using Pickle, ColorSchemes, SpecialFunctions, LambertW, Plots, ArgParse;
```

## Experiments

After installing Julia, to run the experiments presented in the paper, you can either use the custom commands (defined below) to only perform a given experiment or you can directly run the `script.sh`. Some experiments are computationally costly, hence we recommend to use more cores than solely four (`-p4`), or to reduce the number of runs (`--Nruns 100`).

```
cd path_to_folder/code
cd adatoptwo
mkdir experiments
mkdir simulations
mkdir data
```

### All experiments at once

To run our script with four cores:
```
chmod +x script.sh
bash script.sh 4
```
Note that the script doesn't include the plotting functions. Therefore, additional runs of the corresponding plotting functionalities have to be made afterwards (see below). As it is, you might need to be careful in the order in which you call the visualization functions since the plots are created for all the folders in the `experiments` folder, which don't have `.pdf` inside them. Also, better visualization can be obtained by commenting some lines of codes and replacing them with others.

### One at a time

#### Benchmark EB-TCϵ and other algorithms

Random Gaussian instances: K ∈ (5,10,20) for ϵ ∈ (0.05, 0.1)
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_randoms.jl --expe "epsFull" --inst "uniform" --K 5 --eps 0.05 --reps 0.25 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_randoms.jl --expe "epsFull" --inst "uniform" --K 10 --eps 0.05 --reps 0.25 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_randoms.jl --expe "epsFull" --inst "uniform" --K 20 --eps 0.05 --reps 0.25 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_randoms.jl --expe "epsFull" --inst "uniform" --K 5 --eps 0.1 --reps 0.25 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_randoms.jl --expe "epsFull" --inst "uniform" --K 10 --eps 0.1 --reps 0.25 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_randoms.jl --expe "epsFull" --inst "uniform" --K 20 --eps 0.1 --reps 0.25 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia epstt_viz_random.jl
```

`1-sparse` benchmark
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "sparse" --K 10 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "sparse" --K 50 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "sparse" --K 100 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "sparse" --K 250 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "sparse" --K 500 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "sparse" --K 750 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "sparse" --K 1000 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
```

`α=0.3` benchmark
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha3" --K 10 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha3" --K 50 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha3" --K 100 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha3" --K 250 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha3" --K 500 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha3" --K 750 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha3" --K 1000 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
```

`α=0.6` benchmark
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha6" --K 10 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha6" --K 50 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha6" --K 100 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha6" --K 250 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFast" --inst "alpha6" --K 500 --eps 0.1 --opt "add" --seed 42 --Nruns 100 --history "partial" --freqHist 50
```

For the plots on the benchmarks `1-sparse`, `α=0.3` and `α=0.6`, it is necessary to get manually the results from all the runs in the summary file. After filling the lists in the file `plots_TTeBAI_largeK.jl`, simply run `julia plots_TTeBAI_largeK.jl`.

Gaussian instance from GK21
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "epsFull" --inst "GK21_1" --K 5 --eps 0.1 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFull" --inst "GK21_2" --K 6 --eps 0.15 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsFull" --inst "GK21_3" --K 6 --eps 0.1 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia epstt_viz_experiments.jl
```

"two-groups" instances with varying number of best arms
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 1 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 2 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 3 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 4 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 5 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 6 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 7 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "eps2G" --inst "2G" --K 10 --eps 0.1 --Ie 8 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
```

For the plots on "two-groups" instances, it is necessary to get manually the results from all the runs in the summary file. After filling the lists in the file `plots_TTeBAI_2G.jl`, simply run `julia plots_TTeBAI_2G.jl`.


#### Detailed Simple Regret, benchmark DSR and DSH

Gaussian instances from GK21
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "GK21_1" --K 5 --eps 0.1 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 500
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "GK21_2" --K 6 --eps 0.15 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 1000
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "GK21_3" --K 6 --eps 0.1 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 2000
julia epstt_viz_experiments.jl
```

2G varying number good arm
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "2G" --K 10 --eps 0.1 --Ie 1 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 1000
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "2G" --K 10 --eps 0.1 --Ie 2 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 1000
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "2G" --K 10 --eps 0.1 --Ie 3 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 1000
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "2G" --K 10 --eps 0.1 --Ie 4 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 1000
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "2G" --K 10 --eps 0.1 --Ie 5 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 1000
julia -O3 -p4 epstt_experiments.jl --expe "epsPoE" --inst "2G" --K 10 --eps 0.1 --Ie 6 --opt "add" --seed 42 --Nruns 10000 --history "partial" --freqHist 4 --Tmax 1000
julia epstt_viz_experiments.jl
```


#### Benchmarking BAI problems with EB-TCϵ and EB-TCϵ with varying slack

Random Gaussian Instances: K ∈ (5, 10, 20)
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_randoms.jl --expe "epsVSBench" --inst "BAIuniform" --K 5 --eps 0.0 --reps 0.001 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_randoms.jl --expe "epsVSBench" --inst "BAIuniform" --K 10 --eps 0.0 --reps 0.001 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_randoms.jl --expe "epsVSBench" --inst "BAIuniform" --K 20 --eps 0.0 --reps 0.001 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia epstt_viz_random.jl
```

Gaussian instances from GK21
```
cd path_to_folder/code/adatoptwo
julia -O3 -p4 epstt_experiments.jl --expe "epsVSBench" --inst "GK21_1" --K 5 --eps 0.0 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia -O3 -p4 epstt_experiments.jl --expe "epsVSBench" --inst "GK21_2" --K 6 --eps 0.0 --opt "add" --seed 42 --Nruns 1000 --history "partial" --freqHist 50
julia epstt_viz_experiments.jl
```
