Learning the Switching Rate by Discretising Bernoulli Sources Online

Steven de Rooij, Tim van ErvenAISTATS 2009 · OpenReview

Abstract

The expert tracking algorithm Fixed-Share depends on a parameter $\alpha$, called the switching rate. If the final number of outcomes $T$ is known in advance, then the switching rate can be learned with regret $\frac{1}{2} \log T + O(1)$ bits. The current fastest method that achieves this, Learn-alpha, is based on optimal discretisation of the Bernoulli distributions into $O(\sqrt{T})$ bins and runs in $O(T\sqrt{T})$ time; however, the exact locations of these points have to be determined algorithmically. This paper introduces a new discretisation scheme with the same regret bound for known $T$, that specifies the number and positions of the discretisation points explicitly. The scheme is especially useful when $T$ is not known in advance: a new fully online algorithm, Refine-Online, is presented, which runs in $O(T \sqrt{T} \log T)$ time and achieves a regret of $\frac{1}{2} \log 3 \log T + O(\log \log T)$ bits.

Introduction

In the "prediction with expert advice" framework, a learner combines advice from $n$ experts to predict a sequence of outcomes. While stationary environments allow for identifying a single best expert, real-world scenarios often involve non-stationary dynamics where the best expert changes over time. The Fixed-Share algorithm is the standard approach for this tracking task, governed by a switching rate parameter $\alpha$— the probability that the best expert changes at any given time step.

Setting $\alpha$ optimally typically requires prior knowledge of the total time horizon $T$ and the number of switches $m$. Incorrect estimates lead to significantly increased regret. Previous solutions either required $T$ to be known or suffered from high computational complexity ($O(T^2)$). This paper addresses these challenges by framing expert tracking as a hierarchical Hidden Markov Model (HMM) and introducing an efficient online discretization strategy.

Methodology

HMM Framework and the Lifting Lemma

The authors decompose the tracking problem into two levels: an upper-level tracking HMM for managing experts and a lower-level "Bernoulli HMM" that models the switching process $\alpha$.

The HMM structure for expert tracking, where $S_i$ represents the state and $X_i$ the observation.

A critical theoretical contribution is the Lifting Lemma. It proves that a regret bound established for the simpler Bernoulli switching process can be automatically "lifted" to the more complex expert tracking problem. This allows the researchers to focus on optimizing the discretization of the Bernoulli source.

The $\phi$-parameterization

Directly discretizing the switching rate $\alpha$ is inefficient because the sensitivity of the loss function varies across the range $[0, 1]$, requiring higher density near the boundaries. To solve this, the authors transform $\alpha$ using $\phi = \arcsin \sqrt{\alpha}$. In this $\phi$-space, the Fisher information is constant, enabling a simple uniform discretization that remains mathematically "fair" across all probability values.

The Refine-Online Algorithm

Standard online algorithms often use a "doubling trick," restarting with higher precision whenever the time horizon doubles. This paper introduces Refine-Online, which employs a more sophisticated refinement scheme. As $T$ increases, the algorithm adds new discretization points and redistributes the probability mass from existing points to their new neighbors using a "patch-up" strategy.

The refinement scheme for discretization points in $\phi$-space, showing the redistribution of probability mass as the grid density increases.

This approach allows the algorithm to retain information learned about the switching rate while incrementally increasing precision, avoiding the wastefulness of full restarts.

Key Results

Regret Bounds

  • Offline Bound (Known $T$): The proposed discretization scheme achieves a regret of $\frac{1}{2} \ln T + 2.8$ bits, matching optimal theoretical benchmarks.
  • Online Bound (Unknown $T$): The Refine-Online algorithm achieves a regret of $\frac{1}{2} \log 3 \ln T + \log 3 \ln \ln(T+1) + 23.1$ bits. While the $\log 3$ factor introduces a slight overhead compared to the offline case, the bound remains highly competitive and theoretically sound.

Computational Efficiency

The algorithm is computationally efficient, with a running time of $O(n \cdot T\sqrt{T} \log T)$ for $n$ experts. This complexity makes it practical for long sequences where $O(T^2)$ methods would fail.

Conclusion and Future Work

This work provides a robust, fully online method for learning the switching rate in expert tracking. By utilizing a $\phi$-transformation and a novel refinement strategy, the authors bridge the gap between theoretical optimality and practical online implementation.

Future research may focus on eliminating the $\log 3$ factor in the online regret bound, which might be an artifact of the specific refinement function used. Additionally, the Lifting Lemma suggests that these discretization techniques could be generalized to other expert algorithms involving repeated binary choices.

Summary updated

Abstract

The expert tracking algorithm Fixed-Share depends on a parameter alpha, called the switching rate. If the final number of outcomes $T$ is known in advance, then the switching rate can be learned with regret $\frac{1}{2} \log T + O(1)$ bits. The current fastest method that achieves this, Learn-alpha, is based on optimal discretisation of the Bernoulli distributions into $O(\sqrt{T})$ bins and runs in $(T\sqrt{T})$ time; however the exact locations of these points have to be determined algorithmically. This paper introduces a new discretisation scheme with the same regret bound for known $T$, that specifies the number and positions of the discretisation points explicitly. The scheme is especially useful when $T$ is not known in advance: a new fully online algorithm, Refine-Online, is presented, which runs in $O(T \sqrt{T} \log T)$ time and achieves a regret of $\frac{1}{2} \log 3 \log T + O(\log \log T)$ bits.
BibTeX
@inproceedings{rooij2009learning,
  author = {Steven de Rooij and Tim van Erven},
  title = {{Learning the Switching Rate by Discretising Bernoulli Sources Online}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2009},
  url = {https://openreview.net/forum?id=SaSHjIae44c},
}
Figure