Fast Pure Exploration via Frank-Wolfe (NeurIPS 2021)

This is the repository for the NeurIPS 2021 paper "Fast Pure Exploration via Frank-Wolfe" by Po-An Wang, Ruo-Chun Tzeng and Alexandre Proutiere.

• utilities/envelope.jl contains the key functions for our sampling rules and introduces a generic way for the objective function and its sub-gradient (i.e., f, ∇f in our code) and the generalized log-likelihood ratio (i.e., alt_min and glrt in our utilities/peps.jl) for the active learning problems under various structures.

Package Requirement

Julia with version 1.5.4. * LinearAlgebra, Distributions, Statistics, Random * JuMP, Tulip * Distributed, JLD2 * Plots, StatsPlots, CPUTime, Printf, LaTeXStrings, IterTools

Experiments

• Classical Best-Arm Identification
• Linear Best-Arm Identification, Linear Threshold
• Lipschitz Best-Arm Identification

Execution Instructions

Please go to the corresponding folder, e.g., standard, linear, or lipschitz and then execute the following commands: * For Best Arm Identification problem, execute, e.g., julia -O3 -p8 experiment_bai1.jl for parallel computing with 8 processes to speeding-up the computation. * For Threshold Bandit problem, the command is similar as above, just replace the filename with, e.g., experiment_threshold.jl. * After completing the experiments, the performance statistics are saved in the .dat file. You can visualize the result by e.g., julia -O3 viz.jl BAI1.

Please note that except for linear/experiment_bai.jl, all other experiments support multiple confidence δs as input. The reason why linear/experiment_bai.jl cannot support multiple confidence δs is because of the stopping rule of XYAdaptive.

Baseline Tables

|Name | Abbrev. | Description | |:-------------------:|:--------:|:-------------------------------------------------------------------------------------------:| |FW-based Sampling | FWS | Our Frank-Wolfe based Sampling | |Track-and-Stop-D | T-D | Track and Stop (Garivier and Kaufmann, 2016) with D-Tracking | |Optimistic TaS-C | O-C | Optimistic Track and Stop (Degenne, Koolen and Ménard, 2019) with C-Tracking | |Menard-C | M-C | Gradient Ascent algorithm (Ménard, 2019) with C-Tracking | |DaBomb-C | D-C | AdaHedge vs Best-Response (Section 3.1 in Degenne, Koolen and Ménard, 2019) with C-Tracking | |ConvexGame-C | CG-C | LineGame-C with C-Tracking (Degenne et al. 2020) | |LinGame-C | Lk-C | LineGame with C-Tracking (Degenne et al. 2020) | |LazyTaS | LT | Lazy TaS with modified threshold in A.1 (Jedra and Proutiere, 2020) | |XY-Adaptive | XY-A | XY-Adaptive (Soare et al. 2014) |