English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The knowledge gradient (KG) algorithm is a popular and effective algorithmfor the best arm identification (BAI) problem. Due to the complex calculationof KG, theoretical analysis of this algorithm is difficult, and existingresults are mostly about the asymptotic performance of it, e.g., consistency,asymptotic sample allocation, etc. In this research, we present new theoreticalresults about the finite-time performance of the KG algorithm. Underindependent and normally distributed rewards, we derive bounds for the sampleallocation of the algorithm. With these bounds, existing asymptotic resultsbecome simple corollaries. Furthermore, we derive upper and lower bounds forthe probability of error and simple regret of the algorithm, and show theperformance of the algorithm for the multi-armed bandit (MAB) problem. Thesedevelopments not only extend the existing analysis of the KG algorithm, but canalso be used to analyze other improvement-based algorithms. Last, we usenumerical experiments to compare the bounds we derive and the performance ofthe KG algorithm.

On the Finite-Time Performance of the Knowledge Gradient Algorithm