# Online Stochastic Optimization under Correlated Bandit Feedback

arXiv: https://arxiv.org/abs/1402.0562 · HTML: https://mlsanity.com/paper/1402.0562/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2014.

## Built on by (most cited first, 11 of 11)

- [Reinforcement Learning and Bandits for Speech and Language Processing: Tutorial, Review and Outlook](https://mlsanity.com/paper/2210.13623/) (2022)
- [Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization](https://mlsanity.com/paper/2106.09215/) (2021)
- [Federated X-Armed Bandit](https://mlsanity.com/paper/2205.15268/) (2022)
- [PyXAB -- A Python Library for X-Armed Bandit and Online Blackbox Optimization Algorithms](https://mlsanity.com/paper/2303.04030/) (2023)
- [Black-box optimization of noisy functions with unknown smoothness](https://mlsanity.com/paper/2605.02462/) (2026)
- [Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-Fidelity Feedback](https://mlsanity.com/paper/2110.07232/) (2021)
- [Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions](https://mlsanity.com/paper/2402.15188/) (2024)
- [Personalized Federated X -armed Bandit](https://mlsanity.com/paper/2310.16323/) (2023)
- [Federated X-armed Bandit with Flexible Personalisation](https://mlsanity.com/paper/2409.07251/) (2024)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)
- [Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits](https://mlsanity.com/paper/2609.30017/) (2026)

## Abstract (arXiv)

In this paper we consider the problem of online stochastic optimization of a locally smooth function under bandit feedback. We introduce the high-confidence tree (HCT) algorithm, a novel any-time X-armed bandit algorithm, and derive regret bounds matching the performance of existing state-of-the-art in terms of dependency on number of steps and smoothness factor. The main advantage of HCT is that it handles the challenging case of correlated rewards, whereas existing methods require that the reward-generating process of each arm is an identically and independent distributed (iid) random process. HCT also improves on the state-of-the-art in terms of its memory requirement as well as requiring a weaker smoothness assumption on the mean-reward function in compare to the previous anytime algorithms. Finally, we discuss how HCT can be applied to the problem of policy search in reinforcement learning and we report preliminary empirical results.