In sequential decision-making, a learner faces a fundamental tension: should they exploit the best-performing option found so far, or explore uncertain options to uncover potentially higher rewards? Balancing this trade-off optimally requires knowing how much time remains. If you only have a few rounds left, exploring is wasteful; if you have thousands, investing early rounds in gathering information pays massive dividends.
Because of this, classic multi-armed bandit and online learning algorithms traditionally require prior knowledge of the total time horizon $T$ (or a fixed sample budget) to calibrate their exploration parameters, confidence intervals, or regularization rates (Bubeck et al., Kumar et al.). However, real-world interactions are rarely fixed; they are open-ended, dynamic, or subject to sudden termination. Horizon-independent exploration focuses on eliminating this dependency, designing "anytime" algorithms that perform optimally no matter when the process is stopped.
The Failure of the Doubling Trick
When an algorithm requires a fixed horizon $T$, a common historical workaround is the doubling trick. This technique divides time into discrete epochs of exponentially increasing lengths ($1, 2, 4, 8, \dots$). The algorithm is reset at the start of each epoch, using the epoch's length as a proxy for a fixed horizon (Nie et al., Fourati et al.).
While the doubling trick can preserve theoretical sublinear regret bounds, it introduces severe practical limitations:
- Performance Lags and Resource Waste: Periodically wiping out the gathered history means the algorithm repeatedly drops its learned certainties and reverts to aggressive, redundant exploration at the start of every epoch (Carpentier et al., Jamieson et al.).
- Structural Incompatibility: In many real-world settings, resetting is physically or logically impossible. For instance, Chen demonstrates that when an application requires a monotone sequence of actions (where you cannot revert to a previous, lower-indexed state), the doubling trick fails entirely because it fundamentally relies on restarting the exploration process from scratch.
To build true anytime algorithms, researchers must replace these artificial epoch resets with continuous, time-dependent mechanisms.
Dynamic Confidence Intervals and Learning Rates
The most direct way to achieve horizon independence is to replace fixed-horizon parameters with functions that scale dynamically with the current time step $t$.
In upper confidence bound (UCB) frameworks, the width of an arm's confidence interval determines how aggressively the algorithm explores. If the confidence bound is tuned using a fixed $T$, it remains static. To make it anytime, the confidence interval must grow or shrink fluidly as a function of elapsed time $t$. For example, Garivier et al. introduce an anytime exploration function within the KL-UCB framework. By dynamically adjusting confidence intervals at each step, their approach maintains optimal distribution-dependent and distribution-free regret guarantees continuously across the entire sequence of actions.
A parallel challenge exists in online optimization and linear bandits, where regularization parameters and step sizes typically depend on knowing the total sample size in advance (Mao et al.). To resolve this, Schwartz et al. utilize a time-dependent learning rate within information-directed sampling. This allows the algorithm to automatically adapt its exploration aggressiveness based on the data accumulated up to step $t$, matching the performance of Bayesian methods without requiring a fixed end time.
Data-Driven Adaptive Switching
Many high-performance algorithms rely on a hybrid structure, such as Explore-then-Commit (ETC), which explicitly separates the learning phase from the exploitation phase (Nie et al., Krishna et al.). In a fixed-horizon setting, the optimal switching point is a clean mathematical fraction of $T$. Without $T$, a native anytime algorithm must determine when to stop exploring based entirely on internal data metrics.
This mechanism is highly effective in complex action spaces, such as submodular bandit maximization. The authors of Tajdini et al. design a hybrid algorithm that adaptively decides when to stop building a solution set greedily and when to treat the remaining choices as a standard multi-armed bandit problem. Rather than relying on a time limit, the algorithm monitors its own uncertainty levels to trigger the transition, achieving near-optimal regret across all horizons.
For pure exploration tasks—where the goal is to identify the best arm or threshold options rather than maximize cumulative reward—fixed budgets usually dictate sampling schedules (Lattimore, Komiyama et al.). To remove this constraint, Locatelli et al. introduce a parameter-free thresholding algorithm. Instead of allocating a fixed budget, it continuously balances exploration across arms based on their proximity to a target threshold, ensuring that if the algorithm is stopped prematurely, it can instantly output a highly accurate recommendation.
Shifting to Local Step-by-Step Competitiveness
An alternative intuition for bypassing global horizon constraints is to optimize for local competitiveness. Instead of trying to minimize total regret over an entire lifetime $T$, the algorithm ensures that its choice at any single step $t$ is competitive with respect to local environmental feedback.
This approach is particularly valuable in non-stationary or evolving environments. For instance, Patil et al. study improving bandits, where arm rewards increase the more they are pulled. Instead of planning an exploration phase around a distant horizon, their algorithm uses local improvement rates to guide choices step-by-step. By ensuring the strategy remains competitive at every individual interval, it naturally provides tight anytime guarantees without ever needing to estimate the total duration of the task.
Key Foundational Work
X-Armed Bandits (2010) — contributed 1 concept elements to this direction.
Minimax Policies for Adversarial and Stochastic Bandits (2009) — contributed 1 concept elements to this direction.