2024/06/24 by Cesa-Bianchi, Nicolò, Eldowa, Khaled, Esposito, Emmanuel +1 · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2406.16802
In this research note, we revisit the bandits with expert advice problem. Under a restricted feedback model, we prove a lower bound of order √(K T ln(N/K)) for the worst-case regret, where K is the number of actions, N>K the number of experts, and T the time horizon. This matches a previously known upper bound of the same order and improves upon the best available lower bound of √(K T (ln N) / (ln K)). For the standard feedback model, we prove a new instance-based upper bound that depends on the agreement between the experts and provides a logarithmic improvement compared to prior results.