MAB算法之UCB1算法的复杂度分析

UCB1算法的时间复杂度为O(KlogT)，其中K是臂的数量，T是时间步数。这是因为UCB1算法需要在每个时间步中计算每个臂的置信上界，并选择置信上界最大的臂进行探索。在计算置信上界时，需要对每个臂的历史奖励和探索次数进行计算，因此时间复杂度为O(K)。在选择臂时，需要对所有臂的置信上界进行排序，因此时间复杂度为O(KlogK)。由于UCB1算法需要进行T次选择，因此总时间复杂度为O(KlogT)。