Abstract: We consider a version of the continuous-time multi-armed bandit problem where decision opportunities arrive at Poisson arrival times, and study its Gittins index policy. When driven by spectrally one-sided Lévy processes, the Gittins index can be written explicitly in terms of the scale function, and is shown to converge to that in the classical Lévy bandit of Kaspi and Mandelbaum (1995).
Introduction
The Multi-Armed Bandit (MAB) problem is a fundamental framework in reinforcement learning and stochastic optimization, centered on the tension between exploring new options and exploiting known rewards. Traditionally, this problem is analyzed in two distinct settings: discrete-time models, where decisions occur at fixed intervals, and continuous-time models, where a controller can monitor and switch arms at any instant.
While continuous-time models are mathematically elegant, they often rely on complex tools like local time analysis and assume a level of instantaneous monitoring that is rarely feasible in real-world economic or engineering scenarios. This research addresses this gap by introducing a "hybrid" model: Poissonian decision times. In this framework, the state of an arm evolves continuously as a Lévy process, but the controller can only observe the state and make decisions at random intervals dictated by a Poisson process.
The Poissonian Decision Model
The core innovation of this paper is the use of Poissonian arrival times to model decision opportunities. This "periodic observation" approach provides a more realistic representation of systems where constant monitoring is either prohibitively expensive or physically impossible.
By varying the Poisson rate ($\lambda$), the model acts as a mathematical bridge. As $\lambda$ decreases, the model reflects a sparse discrete-time environment; as $\lambda$ approaches infinity, it converges toward the fully continuous-time limit. This allows researchers to treat discrete and continuous bandits within a unified theoretical framework.
Methodology and Fluctuation Theory
The authors model the arms using spectrally one-sided Lévy processes—stochastic processes characterized by independent increments and jumps that occur in only one direction (either exclusively up or exclusively down). To solve the optimization problem, they focus on the Gittins index, a scalar value that simplifies a complex $J$-dimensional multi-arm problem into $J$ independent one-dimensional problems.
The methodology relies on several key pillars:
- Optimal Stopping: The Gittins index is defined through an auxiliary optimal stopping problem where stopping times are restricted to the arrival times of the Poisson process.
- Scale Functions: The authors utilize fluctuation theory, specifically scale functions ($W^{(q)}$ and $Z^{(q)}$), to derive explicit, closed-form expressions for the index. Such closed-form solutions are notoriously rare in MAB theory.
- Reward Variations: The study analyzes two distinct scenarios: one where rewards are collected only at the specific moments of decision (Problem 1), and another where rewards accumulate continuously throughout the intervals between decisions (Problem 2).
Key Results and Convergence
The paper provides a rigorous mathematical foundation for the Poissonian model through several key theorems:
- General Representation (Theorem 3.1): The authors establish a general representation of the Gittins index for the Poissonian model as a ratio of expected discounted rewards and expected discounted time.
- Explicit Formulas (Propositions 4.1 & 4.2): For both spectrally negative and spectrally positive Lévy processes, the authors provide the "meat" of the research—explicit formulas for the Gittins index expressed through the process's scale functions.
- The Continuous Limit (Propositions 5.1 & 5.2): The most significant theoretical contribution is the proof of convergence. Using Laplace and Fourier transforms, the authors demonstrate that as the decision rate $\lambda \to \infty$, the Poissonian Gittins index converges weakly to the classical Gittins index derived by Kaspi and Mandelbaum (1995). This validates the Poissonian model as a robust and consistent approximation of the continuous-time limit.
Conclusion and Future Directions
This research successfully bridges the gap between discrete and continuous stochastic control. By restricting the noise to spectrally one-sided Lévy processes, the authors overcome the typical hurdle of non-explicit Gittins indices.
While the paper establishes the Gittins index policy, the authors note that proving its exact optimality in the Poissonian setting remains an open challenge, though it is conjectured to be near-optimal. Future work may extend these results to two-sided jump processes using Wiener-Hopf factorization. Additionally, the authors suggest that this model could be used to approximate discrete-time models with deterministic steps via Carr’s randomization, potentially simplifying numerical computations for engineering applications.
Summary updated