We propose a new algorithm for the piece-wise i.i.d. non-stationary bandit problem with bounded rewards. Our proposal, GLR-klUCB, combines an efficient bandit algorithm, klUCB, with an efficient, parameter-free, change-point detector, the Bernoulli Generalized Likelihood Ratio Test, for which we provide new theoretical guarantees of independent interest. We analyze two variants of our strategy, based on local restarts and global restarts, and show that their regret is upper-bounded by @math if the number of change-points @math is unknown, and by @math if @math is known. This improves the current state-of-the-art bounds, as our algorithm needs no tuning based on knowledge of the problem complexity other than @math . We present numerical experiments showing that GLR-klUCB outperforms passively and actively adaptive algorithms from the literature, and highlight the benefit of using local restarts.
More recently, @cite_0 proposed the Discounted Thompson Sampling (DTS) algorithm, which performs well in practice with @math . However, no theoretical guarantees are given for this strategy, and our experiments did not really confirm the robustness to @math . The RExp3 algorithm can also be qualified as passively adaptive: it is based on (non-adaptive) restarts of the EXP3 algorithm. Note that this algorithm is introduced for a different setting, where the quantity of interest is not @math but a quantity @math called the total variational budget (satisfying @math with @math the minimum magnitude of a change-point). A @math regret bound is proved, which is weaker than existing results in our setting. Hence we do no include this algorithm in our experiments.
@cite_0
2141645258 2116082319 2040155008 2964000194
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have comparable or better empirical performance compared to the state of the art methods. In this paper, we provide a novel regret analysis for Thompson Sampling that proves the first near-optimal problem-independent bound of O( √ NT lnT ) on the expected regret of this algorithm. Our novel martingale-based analysis techniques are conceptually simple, and easily extend to distributions other than the Beta distribution. For the version of Thompson Sampling that uses Gaussian priors, we prove a problem-independent bound of O( √ NT lnN) on the expected regret, and demonstrate the optimality of this bound by providing a matching lower bound. This lower bound of Ω( √ NT lnN) is the first lower bound on the performance of a natural version of Thompson Sampling that is away from the general lower bound of O( √ NT ) for the multi-armed bandit problem. Our near-optimal problem-independent bounds for Thompson Sampling solve a COLT 2012 open problem of Chapelle and Li. Additionally, our techniques simultaneously provide the optimal problem-dependent bound of (1+ ǫ) ∑ i lnT d(μi,μ1) +O(Nǫ2 ) on the expected regret. The optimal problem-dependent regret bound for this problem was first proven recently by [2012b]. Appearing in Proceedings of the 16 International Conference on Artificial Intelligence and Statistics (AISTATS) 2013, Scottsdale, AZ, USA. Volume 31 of JMLR: W&CP 31. Copyright 2013 by the authors. Thompson Sampling has recently been shown to achieve the lower bound on regret in the Bernoulli Multi-Armed Bandit setting. This bandit problem assumes stationary distributions for the rewards. It is often unrealistic to model the real world as a stationary distribution. In this paper we derive and evaluate algorithms using Thompson Sampling for a Switching Multi-Armed Bandit Problem. We propose a Thompson Sampling strategy equipped with a Bayesian change point mechanism to tackle this problem. We develop algorithms for a variety of cases with constant switching rate: when switching occurs all arms change (Global Switching), switching occurs independently for each arm (PerArm Switching), when the switching rate is known and when it must be inferred from data. This leads to a family of algorithms we collectively term Change-Point Thompson Sampling (CTS). We show empirical results in 4 articial environments, and 2 derived from real world data: news click-through[Yahoo!, 2011] and foreign exchange data[Dukascopy, 2012], comparing them to some other bandit algorithms. In real world data CTS is the most eective. Motivated by multi-budgeted optimization and other applications, we consider the problem of randomly rounding a fractional solution x in the (non-bipartite graph) matching and matroid intersection polytopes. We show that for any fixed Δ > 0, a given point x can be rounded to a random solution R such that E[1R] = (1 − Δ)x and any linear function of x satisfies dimension-free Chernoff-Hoeffding concentration bounds (the bounds depend on Δ and the expectation μ). We build on and adapt the swap rounding scheme in our recent work [9] to achieve this result. Our main contribution is a non-trivial martingale based analysis framework to prove the desired concentration bounds. In this paper we describe two applications. We give a randomized PTAS for matroid intersection and matchings with any fixed number of budget constraints. We also give a deterministic PTAS for the case of matchings. The concentration bounds also yield related results when the number of budget constraints is not fixed. As a second application we obtain an algorithm to compute in polynomial time an ∈-approximate Pareto-optimal set for the multi-objective variants of these problems, when the number of objectives is a fixed constant. We rely on a result of Papadimitriou and Yannakakis [26]. We consider the problem of learning an unknown Markov Decision Process (MDP) that is weakly communicating in the infinite horizon setting. We propose a Thompson Sampling-based reinforcement learning algorithm with dynamic episodes (TSDE). At the beginning of each episode, the algorithm generates a sample from the posterior distribution over the unknown model parameters. It then follows the optimal stationary policy for the sampled model for the rest of the episode. The duration of each episode is dynamically determined by two stopping criteria. The first stopping criterion controls the growth rate of episode length. The second stopping criterion happens when the number of visits to any state-action pair is doubled. We establish @math bounds on expected regret under a Bayesian setting, where @math and @math are the sizes of the state and action spaces, @math is time, and @math is the bound of the span. This regret bound matches the best available bound for weakly communicating MDPs. Numerical results show it to perform better than existing algorithms for infinite horizon MDPs.