Sequential Decision-Makings in Non-Stationary Environments

Motivated by non-stationary environments in online advertising, dynamic pricing, and inventory control, we introduce data-driven decision-making algorithms that achieve state-of-the-art regret bounds for bandit optimization and reinforcement learning settings.

For bandit optimization, we show how the challenge posed by non-stationarity can be overcome by an unconventional marriage between stochastic and adversarial bandit algorithms. It is well known that the optimal regret bound can be achieved when the variation budget, which quantifies the total amount of temporal changes of the latent environment, is known in advance. Unfortunately, recovering this bound without knowing the variation budget has been an open problem until recently. We propose a novel Bandit-over-Bandit framework that utilizes an independent adversarial bandit algorithm to adaptively tune the parameter of a base stochastic bandit algorithm. We show that the Bandit-over-Bandit framework enjoys a nearly optimal regret bound. Numerical experiments with a dataset of an online auto-loan company demonstrate that our proposed algorithms achieve superior performance when compared to existing algorithms.

For reinforcement learning, we show that simply adopting techniques from bandit optimization might lead to linear regret despite the similarity between bandit optimization and reinforcement learning. We overcome this challenge by a novel confidence widening technique that incorporates extra optimism into the learning algorithm to ensure low regret bounds. We demonstrate the power of our technique by applying it to the stochastic inventory model with lost-sales, fixed cost, and zero lead time.