/NeurIPS2023-PerturbedFWS

Repo for "Closing the Computational-Statistical Gap in Best Arm Identification for Combinatorial Semi-bandits", NeurIPS 2023

Primary LanguageJuliaMIT LicenseMIT

Perturbed Frank-Wolfe Sampling

This is the official repository for "Closing the Computational-Statistical Gap in Best Arm Identification for Combinatorial Semi-bandits", NeurIPS 2023.

Required packages

Julia 1.7.3 with required packages: DataStructures.jl, Combinatorics.jl, Graph.jl, Polyhedra.jl, SNAPDatasets.jl, GLPK.jl, StatsPlots.jl, JLD2.jl

Combinatorial structures and algorithms

Algorithms for computing the most confusing parameter (MCP) are implemented in mcp_oracle.jl, where

  • NoRegMCP is an implementation of Algorithm 1 (ε,θ)-MCP(ω,μ) with an additional parameter MAX_ITER introduced to controll the maximum number n of iterations
  • NaiveMCP computes $f_x(ω,μ)$ for each $x$ in the action set $\mathcal{X}$ by a closed-form expression and returns the minimum value

Sampling rules are implemented in samplingrules.jl, which includes:

Name Abbrev. Description
PerturbedFWS PFWS Our Perturbed Frank-Wolfe Sampling
CombGame-OFW CG-OFW CombGame (Jourdan, et al., ALT'21) with D-Tracking
Uniform RR Uniform Sampling

Combinatorial structures are implemented in cstruct.jl, where functions to compute any $i^{\star}(\mu)\in\arg\max_{x\in X}\langle\mu,x\rangle$ and any $i^{\star}(\mu,x)\in\arg\max_{x'\in X\backslash{x}}\langle\mu,x'\rangle$ for a given $x\in X$ are provided. Our implementation is listed as follows:

Combinatorial Structure Time complexity of computing $i^{\star}(\mu)$ Time complexity of computing $i^{\star}(\mu,x)$
Spanning Trees Prim's algorithm with priority queue: $O(|E|\ln|V|)$ Lemma 2: $O(|E|\times\text{tree-depth})$
  • Note that: for random $r$-regular graphs on $n$ nodes, the $\text{tree-depth}\leq \lceil 3+\frac{\ln n+\ln\ln n}{\ln r}\rceil=O(\ln n)$ as $n\to\infty$. See Theorem 10.14 in (Béla Bollobás, "Random Graphs", 2nd edition, 2001).
  • NaiveMCP requires to list all possible spanning trees. enumerate_all for SpanningTree is implemented based on Kirchhoff's Matrix-Tree theorem (see, e.g., Sec 6 in (Knauer and Knauer 2019)).

Preliminary Experiments on Spanning Trees

As a preliminary check, we run experiments on SpanningTree with small number $n\in{8,10}$ of vertices.

  • Note that: we have slightly improved the input parameters used for calling NoRegMCP, and the averaged number of samples used by PFWS and by CG-OFW are better than what we have provided during the NeurIPS'23 rebuttal period.

  • dataset/ contains the 5-regular graphs generated by the script dataset/generate_sptree.jl:

    $|V|$ $K=|E|$ #spanning-trees $\Delta_{\min}(\mu)$
    sptree_E20.dat 8 20 21,025 0.0989
    sptree_E25.dat 10 25 343,385 0.0999

  • Execute experiment_sptree.jl with the following parameters:

    $K$ $δ$ MAX_ITER Command
    20 0.1 5000 $ julia -O3 -p12 experiment_sptree.jl 20 5000
    25 0.1 100000 $ julia -O3 -p12 experiment_sptree.jl 25 100000

  • After a successful execution, the results will be saved in .dat format, e.g., BAI_sptree_E20.dat for K=20. To visually compare the number of samples used by different sampling rules, use viz.jl by executing, e.g., $ julia -O3 viz.jl BAI_sptree_E20.dat.