Online Stochastic Optimization under Correlated Bandit Feedback

Abstract

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 $\mathcal{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.

References in corpus (4)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Reinforcement Learning in POMDP's via Direct Gradient Ascent
• Stochastic simultaneous optimistic optimization
• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning

Cited by in corpus (11)

• Black-box optimization of noisy functions with unknown smoothness
• Simple regret for infinitely many armed bandits
• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
• Hidden Incentives for Auto-Induced Distributional Shift
• A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
• Online Learning Demands in Max-min Fairness
• Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization
• Derivative-Free & Order-Robust Optimisation
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
• Adaptive KL-UCB based Bandit Algorithms for Markovian and i.i.d. Settings
• Bayesian optimization for modular black-box systems with switching costs