What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
read the original abstract
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})$.
This paper has not been read by Pith yet.
Forward citations
Cited by 8 Pith papers
-
Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits
First shuffle-DP and joint-DP algorithms for GLM contextual bandits achieve near non-private regret without strong spectral assumptions on contexts.
-
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
Prudent-Banker achieves pseudo-regret Õ(√T + √D) and Õ(1) regret vs. safe comparator in adversarial bandits both with and without delays, matching new lower bounds up to logs.
-
Online Market Making and the Value of Observing the Order Book
Introduces action-dependent order-book feedback for online market making, yielding O(sqrt(T)) high-probability regret in stochastic i.i.d. and mean-reverting settings without smoothness assumptions, and O(T^{2/3}) in ...
-
Constrained Contextual Bandits with Adversarial Contexts
A modular reduction from budget-constrained contextual bandits with adversarial contexts to unconstrained bandits via surrogate rewards, yielding improved guarantees and an efficient algorithm based on SquareCB.
-
Optimal Semiparametric Dynamic Pricing with Feature Diversity
A stagewise greedy algorithm for semiparametric contextual dynamic pricing achieves regret T to the max of 1/2 and 3 over (2 beta plus 1) for linear m, with a matching lower bound proving optimality.
-
A single algorithm for both restless and rested rotting bandits
RAW-UCB achieves near-optimal regret in both rested and restless rotting bandits without prior knowledge of the setting or non-stationarity type.
-
Learning Safely Without Knowing the World:COMPASS-Hedge
COMPASS-Hedge is presented as the first parameter-free full-information anytime algorithm that simultaneously delivers minimax-optimal adversarial regret, instance-optimal stochastic regret, and Õ(1) regret to a basel...
-
Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction
A projection-based algorithm for COCO achieves O(log T) regret and O(log T) CCV for strongly convex losses and O(sqrt(T)) for convex losses by leveraging self-contracted curves.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.