We consider the classical stochastic multi-armed bandit problem with a constraint that limits the total cost incurred by switching between actions to be no larger than a given switching budget. For this problem, we prove matching upper and lower bounds on the optimal (i.e., minimax) regret, and provide efficient rate-optimal algorithms. Surprisingly, the optimal regret of this problem exhibits a non-conventional growth rate in terms of the time horizon and the number of arms. Consequently, we discover surprising "phase transitions" regarding how the optimal regret rate changes with respect to the switching budget: when the number of arms is fixed, there are equal-length phases, where the optimal regret rate remains (almost) the same within each phase and exhibits abrupt changes between phases; when the number of arms grows with the time horizon, such abrupt changes become subtler and may disappear, but a generalized notion of phase transitions involving certain new measurements still exists. The results enable us to fully characterize the trade-off between the regret rate and the incurred switching cost in the stochastic multi-armed bandit problem, contributing new insights to this fundamental problem. Under the general switching cost structure, the results reveal interesting connections between bandit problems and graph traversal problems, such as the shortest Hamiltonian path problem.
翻译:我们认为古老的多武装匪盗问题具有制约性,限制了在行动之间转换的总成本,因此限制了在行动之间转换的总成本。 对于这一问题,我们证明在最佳(即迷你)遗憾上匹配上下界限,并提供了高效的速率最佳算法。令人惊讶的是,这一问题的最佳遗憾在时间范围和武器数量方面表现出非常规的增长率。因此,我们发现在转换预算方面的最佳遗憾率变化是如何发生的令人惊讶的“阶段过渡 ” : 当武器数量固定下来时,有同等长的阶段,每个阶段内的最佳遗憾率保持相同(几乎),并显示两个阶段之间的突变变化;当武器数量随着时间跨度的增长而变化时,这种突然的变化变得微妙,可能会消失,但涉及某些新计量的阶段过渡的普遍概念仍然存在。结果使我们能够充分说明在选择的遗憾率和多武装暴徒问题中发生的转折价,从而导致对这个基本阶段问题产生新的洞察力。在总体成本结构下,这种轮廓将揭示出这种根本性问题,作为最短的轮廓问题。