New Experiment: Empirical Comparison to Baseline
We highly appreciate the reviewers and area chairs for spending time evaluating this paper.
In this post, we present a new numerical simulation that compares our two exploration policies, $\texttt{Explore-A}$ and $\texttt{Explore-B}$, with a $\texttt{Baseline}$ that is always selecting the highest fidelity to explore arms. All three policies are employed under the LUCB framework (Algorithm 1). We note that, for the MF-MAB model, there is no prior algorithm (other baselines) on the best arm identification with fixed confidence setting (see Section 1.2's second paragraph for related work discussion).
This simulation aims to illustrate when our exploration policies $\texttt{Explore-A}$ and $\texttt{Explore-B}$ (utilize low-fidelity) are better than $\texttt{Baseline}$ (not utilize low-fidelity).
**Experiment Setup.** We consider a MF-MAB model consisting of $K=5$ arms and $M=5$ fidelities. The reward means are set as $\mu_{k}^{(m)} = 0.1 (k+4) + 0.01(m-5)$, where, for example, $\mu_5^{(5)} = 0.9$ is the true reward mean of optimal arm and its low-fidelity reward means are $\{0.89, 0.88, 0.87, 0.86\}$ accordingly, etc. The error upper bound in $\zeta^{(m)}$ are $\\{0.04, 0.03, 0.02, 0.01, 0\\}$ for $m\in\\{1,2,3,4,5\\}$ respectively. We set the cost of fidelity $m\in\\{1,2,3,4\\}$ as $\lambda^{(m)} = m$, and consider four different cases $I\in \\{1,2,3,4\\}$ of the cost of highest fidelity $\lambda^{(5)}=5I$. That is, from Case 1 to Case 4, the cost of the highest fidelity $\lambda^{(5)}$ increases from $5$ to $20$.
We set the confidence parameter $\delta=0.1$ and run each experiment for 100 trials. Averaged over these $100$ trials of each experiment, we present the empirical cost complexity in the table as follows,
| Cost Complexity ($\times 10^4$) | Case 1 ($\lambda^{(5)}=5$) | Case 2 ($\lambda^{(5)}=10$) | Case 3 ($\lambda^{(5)}=15$) | Case 4 ($\lambda^{(5)}=20$) |
| -------------------- | ------ | ------ | ------ | ------ |
| $\texttt{Explore-A}$ | $20.5$ | $20.0$ | $17.4$ | $17.4$ |
| $\texttt{Explore-B}$ | $36.1$ | $47.9$ | $59.5$ | $69.4$ |
| $\texttt{Baseline}$ | $21.4$ | $42.0$ |$64.6$ |$86.2$ |
**Discussion of Simulation Results.**
In all four cases, the cost complexities of $\texttt{Explore-A}$ are similar. Especially, when the cost of the highest fidelity $\lambda^{(5)}$ becomes larger, it is easier for $\texttt{Explore-A}$ to find out the optimal fidelity (e.g., the highest fidelity is obviously not the optimal one due to its high cost) and, hence, $\texttt{Explore-A}$ enjoys a slightly lower cost complexity. The cost complexities of both $\texttt{Explore-B}$ and $\texttt{Baseline}$ increase along these four cases.
When the cost of the highest fidelity is expensive, e.g., in Cases 3 and 4, both $\texttt{Explore-A}$ and $\texttt{Explore-B}$ outperform $\texttt{Baseline}$. This highlights the advantage of utilizing low fidelity to explore arms while avoiding using the expensive high fidelity.
When the cost of the highest fidelity is cheap, e.g., in Case 1, the cost complexity of $\texttt{Explore-A}$ is similar to $\texttt{Baseline}$, while $\texttt{Explore-B}$ is worse than $\texttt{Baseline}$. This suggests that when the cost of the highest fidelity is similar to that of lower fidelity, utilizing the high-fidelity to explore arms (i.e., $\texttt{Baseline}$) may be preferable.
In this comparison, $\texttt{Explore-A}$ always outperforms $\texttt{Explore-B}$. For another scenario where $\texttt{Explore-B}$ is better than $\texttt{Explore-B}$, please refer to Figure 1(b) in our paper.
Last but not least, we emphasize that this paper is a theoretical work and our focus is on devising algorithms and proving their theoretical guarantees. Our numerical experiments so far (including Figures 1(a) and 1(b) in the paper and the additional one reported here) achieve the purpose of providing the basic support and verification of the results in the theorems.
We will include the new comparison in the above table to the final version of this paper as well.
We also plan to further validate our algorithms with more experiments on larger datasets.