Continuous-time multi-armed bandits under random intervention times

Kei Noba, José Luis Pérez, Kazutoshi Yamazaki, Qingyuan ZhangarXiv 2026 · arXiv

Abstract

This paper investigates a class of multi-armed bandit (MAB) problems where decisions are restricted to random discrete time points. In this model, once an arm is activated, it must remain operational for a duration governed by a renewal process. For arms characterized by Lévy processes, we derive an explicit characterization of the Gittins index, the optimal allocation strategy. Furthermore, we provide closed-form expressions for the index in cases involving spectrally negative Lévy processes, reflected processes, and diffusion processes using scale functions and diffusion characteristics. Numerical simulations validate the theoretical findings and demonstrate the superiority of the Gittins index over myopic strategies.

Introduction

The Multi-Armed Bandit (MAB) problem represents the fundamental trade-off between exploration and exploitation. Traditionally, researchers have analyzed this problem in two distinct temporal frameworks: discrete-time, where decisions occur at fixed intervals, and continuous-time, where switching can occur instantaneously. However, many real-world applications—such as clinical trials or industrial project management—exhibit "sticky" decision-making, where an operator is committed to a choice for a random duration before a re-evaluation is possible.

This research bridges the gap between these two extremes by modeling continuous-time reward evolution under random discrete intervention times. The primary objective is to characterize the Gittins index, a scalar value assigned to each arm that simplifies the complex multi-dimensional optimization problem into a series of independent sub-problems. By always selecting the arm with the highest Gittins index, an operator can achieve an optimal long-term reward.

Methodology and Mathematical Framework

The study considers a system of $J$ independent arms. When an arm is operated, its state evolves according to a continuous-time stochastic process, but it can only be stopped or switched at times determined by an arm-dependent renewal process. To solve for the Gittins index in this setting, the authors utilize several advanced mathematical frameworks:

  • Lévy Processes: The authors characterize the index for processes with independent and stationary increments.
  • Fluctuation Theory: For spectrally negative Lévy processes (those with only downward jumps), the index is derived using scale functions, which describe the exit probabilities of the process from an interval.
  • Diffusion Characteristics: For diffusion processes like Brownian motion, the authors employ speed measures and Green functions to define the index.
  • Wiener-Hopf Factorization: This technique is applied to handle the Fourier transforms of reward measures, facilitating the proof of convergence as intervention frequency increases.

Numerical Experiments

In the absence of a specific real-world dataset, the authors conducted extensive numerical simulations across five stochastic models to test the robustness of their formulas:

  1. Standard Brownian Motion (BM)
  2. Reflected Brownian Motion (RBM): Incorporating a lower boundary to simulate non-negative assets.
  3. Ornstein-Uhlenbeck (OU) Process: Modeling mean-reverting behaviors.
  4. Spectrally Negative Lévy Process (SNLP): Capturing continuous growth with occasional sharp declines.
  5. Reflected SNLP (RSNLP): Combining jump dynamics with a lower boundary.

Key Insights

1. Optimality and Convergence

The paper rigorously proves that the Gittins index remains the optimal strategy even under random intervention constraints. A significant contribution is the "bridge" theorem: as the arrival rate of intervention times ($\lambda$) approaches infinity, the discrete-intervention Gittins index converges to the classical continuous-time Gittins index. This provides a unified theoretical framework for bandit problems across different time scales.

2. Explicit Characterizations

Calculating the Gittins index is traditionally computationally expensive. This paper provides explicit formulas based on the underlying process characteristics (e.g., scale functions). These closed-form solutions allow for significantly faster computation of optimal strategies in practical applications.

3. Performance Against Myopic Strategies

Numerical results consistently show that the Gittins Index (GI) strategy outperforms "Myopic" strategies. While a myopic approach only considers the immediate reward at the next intervention time, the GI strategy accounts for the future potential and the "option value" of exploration, leading to higher cumulative rewards.

Conclusion and Future Directions

This research provides a robust generalization of bandit theory, successfully unifying discrete and continuous frameworks. By solving the index for reflected processes, the authors increase the model's applicability to finance and operations, where variables like inventory or prices cannot drop below zero.

However, some limitations remain. The model assumes that arms are independent and that "frozen" arms do not evolve while inactive. Future research could extend these findings to restless bandits, where all arms evolve simultaneously, or explore scenarios with non-Markovian reward structures where the history of the process significantly influences future outcomes.

Summary updated

Abstract

This paper examines multi-armed bandits in which actions are taken at random discrete times. The model consists of $J$ independent arms. When an arm is operated, it must remain active for a random duration, modeled by the inter-arrival time of a (possibly arm-dependent) renewal process. For arms evolving as a Lévy process, we provide an explicit characterization of the Gittins index, which is known to yield an optimal strategy. Furthermore, when the inter-arrival times are exponential and the arms evolve as either a spectrally negative Lévy process, a reflected spectrally negative Lévy process, or a diffusion process, the Gittins index is explicitly characterized in terms of the scale function or diffusion characteristics, respectively. Numerical experiments are performed to support the theoretical results.
BibTeX
@misc{noba2026continuous,
  author = {Kei Noba and José Luis Pérez and Kazutoshi Yamazaki and Qingyuan Zhang},
  title = {{Continuous-time multi-armed bandits under random intervention times}},
  year = {2026},
  eprint = {2603.03661},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.03661},
}
Figure