An online reinforcement learning algorithm is anytime if it does not need to know in advance the horizon T of the experiment. A well-known technique to obtain an anytime algorithm from any non-anytime algorithm is the "Doubling Trick". In the context of adversarial or stochastic multi-armed bandits, the performance of an algorithm is measured by its regret, and we study two families of sequences of growing horizons (geometric and exponential) to generalize previously known results that certain doubling tricks can be used to conserve certain regret bounds. In a broad setting, we prove that a geometric doubling trick can be used to conserve (minimax) bounds in $R\_T = O(\sqrt{T})$ but cannot conserve (distribution-dependent) bounds in $R\_T = O(\log T)$. We give insights as to why exponential doubling tricks may be better, as they conserve bounds in $R\_T = O(\log T)$, and are close to conserving bounds in $R\_T = O(\sqrt{T})$.

研究在线强化学习算法中的任何时间算法以及倍增技巧，为了在广泛的情境中证明几何变倍技巧可以用于保留某些遗憾边界，但无法保留分布依赖边界，而指数倍增技巧可能更好，因为它们保留了 R_T = O（log T）的边界，并且接近于保留 R_T = O（sqrt（T））的边界。

Doubling Tricks对多臂老虎机能做什么，不能做什么