Continuous Time Associative Bandit Problems.

András György, Levente Kocsis, Ivett Szabó, Csaba SzepesváriIJCAI 2007 · OpenReview

Abstract

In traditional multi-armed bandit (MAB) problems, actions are typically assumed to occur in discrete, uniform time steps. However, real-world applications often involve actions with variable durations and contextual "side information." This paper, originally presented at IJCAI 2007, introduces a framework for continuous-time associative bandits. By modeling the problem as a Semi-Markov Decision Process (SMDP), the authors propose a UCB-style algorithm designed to maximize the long-term rate of return. The authors provide a theoretical guarantee that the algorithm achieves an optimal logarithmic regret bound, $O(\log n)$, effectively balancing exploration, duration estimation, and reward maximization.

Introduction

The classic multi-armed bandit problem is a cornerstone of reinforcement learning, representing the fundamental trade-off between exploration and exploitation. In its standard form, every "pull" of a lever is treated as an identical unit of time. This abstraction fails in many practical domains—such as task scheduling in supercomputing or clinical trial management—where different actions require different amounts of time to complete.

If Action A yields a reward of 10 but takes 10 hours, and Action B yields a reward of 2 but takes only 10 minutes, Action B is significantly more valuable for a decision-maker aiming to maximize long-term income. This paper addresses this "Rate Maximization" problem while incorporating "side information" (associative bandits), where the learner observes context before selecting an action.

Problem Formulation

The authors frame the challenge as a Semi-Markov Decision Process (SMDP). In this setting, the learner must account for two primary complexities:

  1. Learning the Value: The learner must predict both the expected reward and the expected duration for each action based on the provided side information.
  2. Opportunity Cost: The learner must recognize that selecting a lengthy, mediocre task prevents the initiation of potentially higher-reward tasks that may arrive shortly thereafter.

Unlike previous research that often relied on specific probability distributions (such as Poisson processes), this work adopts an "agnostic" approach. It makes no parametric assumptions about the distributions of rewards or delays, ensuring the model's robustness across diverse applications.

The Proposed Algorithm

The proposed solution is a novel algorithm rooted in the "Upper Confidence Bound" (UCB) philosophy, adapted for the continuous-time domain. The strategy centers on three key components:

Relative Value Estimation

Instead of evaluating actions solely on expected reward, the algorithm utilizes a "relative value" formula: $$q_i^*(x) = r_i(x) - \delta_i(x)\lambda^*$$ Where:

  • $r_i(x)$ is the expected reward for action $i$ given context $x$.
  • $\delta_i(x)$ is the expected duration.
  • $\lambda^*$ is the optimal long-term reward rate.

This formula effectively subtracts the "cost of time" from the reward, allowing the learner to compare actions of different durations on a level playing field.

Maximin Gain Estimation

Because the optimal rate $\lambda^*$ is initially unknown, the algorithm maintains a "pessimistic" estimate of the best possible gain it can guarantee. It evaluates all possible policies and selects the one that performs best under worst-case scenarios given the current data.

Modified UCB Rule

The decision rule selects the action that maximizes the estimated relative value plus an exploration bonus (confidence interval). This ensures that the learner continues to explore less-familiar actions while gradually converging on the strategy with the optimal reward-to-time ratio.

Theoretical Results

The paper's primary contribution is a rigorous mathematical proof of the algorithm's efficiency:

  • Logarithmic Regret: The authors demonstrate that the "regret"—the performance gap between the algorithm and a perfect theoretical strategy—grows at a rate of $O(\log n)$.
  • Optimality: This $O(\log n)$ rate is the theoretical gold standard for bandit problems, indicating that the algorithm learns the optimal strategy as efficiently as mathematically possible.
  • Polynomial Scaling: The regret scales polynomially with the number of actions and side-info states, confirming the algorithm's theoretical viability as problem complexity increases.

Discussion and Limitations

While the paper establishes a strong theoretical foundation for continuous-time bandits, several challenges remain for practical implementation. The current algorithm requires enumerating all possible stationary policies to estimate optimal gain; as the variety of side information grows, the number of policies increases exponentially, leading to high computational costs.

Furthermore, the proof assumes a finite set of side information and a stationary, memoryless environment. Future work may involve extending these methods to continuous side-information spaces using function approximation or addressing non-stationary environments where rewards and durations fluctuate over time.

Summary updated

BibTeX
@inproceedings{gyorgy2007continuous,
  author = {András György and Levente Kocsis and Ivett Szabó and Csaba Szepesvári},
  title = {{Continuous Time Associative Bandit Problems.}},
  booktitle = {IJCAI},
  year = {2007},
  url = {https://openreview.net/forum?id=4eyJSvx3kr-Z},
}
Figure