A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
---
paper_title: Decision-Making Under Uncertainty: Capturing Dynamic Brand Choice Processes in Turbulent Consumer Goods Markets

paper_content:

We construct two models of the behavior of consumers in an environment where there is uncertainty about brand attributes. In our models, both usage experience and advertising exposure give consumers noisy signals about brand attributes. Consumers use these signals to update their expectations of brand attributes in a Bayesian manner. The two models are 1 a dynamic model with immediate utility maximization, and 2 a dynamic “forward-looking” model in which consumers maximize the expected present value of utility over a planning horizon. Given this theoretical framework, we derive from the Bayesian learning framework how brand choice probabilities depend on past usage experience and advertising exposures. We then form likelihood functions for the models and estimate them on Nielsen scanner data for detergent. ::: ::: We find that the functional forms for experience and advertising effects that we derive from the Bayesian learning framework fit the data very well relative to flexible ad hoc functional forms such as exponential smoothing, and also perform better at out-of-sample prediction. Another finding is that in the context of consumer learning of product attributes, although the forward-looking model fits the data statistically better at conventional significance levels, both models produce similar parameter estimates and policy implications. Our estimates indicate that consumers are risk-averse with respect to variation in brand attributes, which discourages them from buying unfamiliar brands. ::: ::: Using the estimated behavioral models, we perform various scenario evaluations to find how changes in marketing strategy affect brand choice both in the short and long run. A key finding obtained from the policy experiments is that advertising intensity has only weak short run effects, but a strong cumulative effect in the long run. ::: ::: The substantive content of the paper is potentially of interest to academics in marketing, economics and decision sciences, as well as product managers, marketing research managers and analysts interested in studying the effectiveness of marketing mix strategies. Our paper will be of particular interest to those interested in the long run effects of advertising. ::: ::: Note that our estimation strategy requires us to specify explicit behavioral models of consumer choice behavior, derive the implied relationships among choice probabilities, past purchases and marketing mix variables, and then estimate the behavioral parameters of each model. Such an estimation strategy is referred to as “structural” estimation, and econometric models that are based explicitly on the consumer's maximization problem and whose parameters are parameters of the consumers' utility functions or of their constraints are referred to as “structural” models. ::: ::: A key benefit of the structural approach is its potential usefulness for policy evaluation. The parameters of structural models are invariant to policy, that is, they do not change due to a change in the policy. In contrast, the parameters of reduced form brand choice models are, in general, functions of marketing strategy variables e.g., consumer response to price may depend on pricing policy. As a result, the predictions of reduced form models for the outcomes of policy experiments may be unreliable, because in making the prediction one must assume that the model parameters are unaffected by the policy change. ::: ::: Since the agents in our models choose among many alternative brands, their choice probabilities take the form of higher-order integrals. We employ Monte-Carlo methods to approximate these integrals and estimate our models using simulated maximum likelihood. Estimation of the dynamic forward-looking model also requires that a dynamic programming problem be solved in order to form the likelihood function. For this we use a new approximation method based on simulation and interpolation techniques. These estimation techniques may be of interest to researchers and policy makers in many fields where dynamic choice among discrete alternatives is important, such as marketing, decision sciences, labor and health economics, and industrial organization.
---
paper_title: Disappointment in Decision Making Under Uncertainty

paper_content:

Decision analysis requires that two equally desirable consequences should have the same utility and vice versa. Most analyses of financial decision making presume that two consequences with the same dollar outcome will be equally preferred However, winning the top prize of $10,000 in a lottery may leave one much happier than receiving $10,000 as the lowest prize in a lottery. This paper explores the implications of disappointment, a psychological reaction caused by comparing the actual outcome of a lottery to one's prior expectations, for decision making under uncertainty. Explicit recognition that decision makers may be paying a premium to avoid potential disappointment provides an interpretation for some known behavioral paradoxes, and suggests that decision makers may be sensitive to the manner in which a lottery is resolved. The concept of disappointment is integrated into utility theory in a prescriptive model.
---
paper_title: Conditions for intuitive expertise: a failure to disagree

paper_content:

This article reports on an effort to explore the differences between two approaches to intuition and expertise that are often viewed as conflicting: heuristics and biases (HB) and naturalistic decision making (NDM). Starting from the obvious fact that professional intuition is sometimes marvelous and sometimes flawed, the authors attempt to map the boundary conditions that separate trite intuitive skill from overconfident and biased impressions. They conclude that evaluating the likely quality of art intuitive judgment requires an assessment of the predictability of the environment in which the judgment is made and of the individual's opportunity to learn the regularities of that environment. Subjective experience is not a reliable indicator of judgment accuracy. Language: en
---
paper_title: Rational choice in an uncertain world: The psychology of judgment and decision making.

paper_content:

Chapter 1 - Thinking and Deciding 1.1 Decision Making Is a Skill 1.2 Thinking: automatic and Controlled 1.3 The Computational Model of the Mind 1.4 Through the Darkest Psychoanalytical Theory and Behaviorism to Cognition 1.5 Quality of Choice: Rationality 1.6 The Invention of Modern Decision Theory Chapter 2 - What Is Decision Making? 2.1 Definition of a Decision 2.2 Picturing Decisions 2.3 Decision Quality, Revisited 2.4 Incomplete Thinking: A Legal Example 2.5 Over-Inclusive Thinking: Sunk Costs 2.6 The Rationality of Considering Only the Future 2.7 The Rest of This Book Chapter 3 - A General Framework for Judgment 3.1 A Conceptual Framework for Judgment and Prediction 3.2 Research With the Lens Model Framework 3.3 Capturing Judgment in Statistical Models 3.4 How Do Statistical Models Beat Human Judgment? 3.5 Practical Implications of the Surprising Success of the Linear Model 3.6 Objections and Rebuttals 3.7 The Role of Judgment in Choices and Decisions Chapter 4 - The Fundamental Judgment Strategy: Anchoring and Adjustment 4.1 Salient Values 4.2 Anchoring and (Insufficient) Adjustment 4.3 Anchoring on Ourselves 4.4 Anchoring the Past in the Present Chapter 5 - Judging Heuristically 5.1 Going Beyond the Information Given 5.2 Estimating Frequencies and probabilities 5.3 Availability of Memories 5.4 Biased Samples in Memory 5.5 Biased Sampling From Memory 5.6 Availability to the Imagination 5.7 From Availability to Probablility and Causality 5.8 Judgment by Similarity: Same Old Things 5.9 Representative Thinking 5.10 The Ratio Rule Chapter 6 - Explanation-Based Judgments 6.1 Everyone Likes a Good Story 6.2 The Conjunction Probabliity Error (Again) 6.3 Judging From Explanations 6.4 Legal Scenarios: The Best Story Wins in the Courtroom 6.5 Scenarios About Ourselves 6.6 Scenarios About the Unthinkable 6.7 Hindsight: Reconstructing the Past 6.8 Sometimes It's Better to Forget Chapter 7 - Chance and Cause 7.1 Misconceptions About Chance 7.2 Illusions of Control 7.3 Seeing Causal Structure Where It Isn't 7.4 Regression Toward the Mean 7.5 Reflections on Our Inability to Accept Randomness Chapter 8 - Thinking Rationally About Uncertainty 8.1 What to Do About the Biases 8.2 Getting Started Thinking in Terms of Probabilities 8.3 Comprehending the Situation Being Judged 8.4 Testing for Rationality 8.5 How to Think About Inverse Probabilities 8.6 Avoiding Subadditivity and Conjunction Errors 8.7 The Other Side of the Coin: The Probability of a Disjunction of Events 8.8 Changing Our Minds: Bayes's Theorem 8.9 Statistical Decision Theory 8.10 Concluding Comment on Rationality Chapter 9 - Evaluating Consequences: Fundamental Preferences 9.1 What Good is Happiness? 9.2 The Role of Emotions in Evaluations 9.3 The Value of Money 9.4 Decision Utility -- Predicting What We will Value 9.5 Constructing Values Chapter 10 - From Preferences to Choices 10.1 Deliberate Choices Among Complex Alternatives 10.2 Ordering Alternatives 10.3 Grouping Alternatives 10.4 Choosing Alternatives 10.5 How to Make Good Choices Chapter 11 - A Rational Decision Theory 11.1 Formally Defining Rationality 11.2 Making Theories Understandable -- The Axiomatic Method 11.3 Defining Rationality: Expected Utility Theory 11.4 Traditional Objections to the Axioms 11.5 The Shoulds and Dos of the System 11.6 Some Bum Raps for Decision Analysis Chapter 12 - A Descriptive Decision Theory 12.1 Non-expected Utility Theories 12.2 Gain-Loss Framing Effects 12.3 Loss Aversion 12.4 Look to the Future Chapter 13 - What's Next? New Directions in Research on Judgment and Decision Making 13.1 The Neuroscience of Decisions 13.2 Emotions in Decision Making 13.3 The Rise of Experimental Methods to Study Dynamic Decisions 13.4 Do We Really Know Where We're Headed? Chapter 14 - In Praise of Uncertianty 14.1 Uncertainty as Negative 14.2 The Illusion of Hedonic Certainty 14.3 The Price of Denying Uncertainty 14.4 Two Cheers for Uncertainty 14.5 Living With Uncertainty
---
paper_title: A perspective on judgment and choice: Mapping bounded rationality

paper_content:

Early studies of intuitive judgment and decision making conducted with the late Amos Tversky are reviewed in the context of two related concepts: an analysis of accessibility, the ease with which thoughts come to mind; a distinction between effortless intuition and deliberate reasoning. Intuitive thoughts, like percepts, are highly accessible. Determinants and consequences of accessibility help explain the central results of prospect theory, framing effects, the heuristic process of attribute substitution, and the characteristic biases that result from the substitution of nonextensional for extensional attributes. Variations in the accessibility of rules explain the occasional corrections of intuitive judgments. The study of biases is compatible with a view Of intuitive thinking and decision making as generally skilled and successful. Language: en
---
paper_title: Sequential Medical Trials

paper_content:

Abstract In an extended review of Sequential Medical Trials by P. Armitage, the statistical principles which should govern the analysis of experimental observations, and the planning of experiments, are discussed. It is suggested that the operating-characteristic concepts of the Neyman-Pearson theory of tests are inappropriate to the analysis and interpretation of experimental data; the likelihood principle should be followed instead. The planning of medical trials under an ethical injunction against unnecessary continuance of inferior treatments is studied in some detail. The propriety of such trials is considered.
---
paper_title: Algorithms for multi-armed bandit problems

paper_content:

Although many algorithms for the multi-armed bandit problem are well-understood theoretically, empirical confirmation of their effectiveness is generally scarce. This paper presents a thorough empirical study of the most popular multi-armed bandit algorithms. Three important observations can be made from our results. Firstly, simple heuristics such as epsilon-greedy and Boltzmann exploration outperform theoretically sound algorithms on most settings by a significant margin. Secondly, the performance of most algorithms varies dramatically with the parameters of the bandit problem. Our study identifies for each algorithm the settings where it performs well, and the settings where it performs poorly. Thirdly, the algorithms' performance relative each to other is affected only by the number of bandit arms and the variance of the rewards. This finding may guide the design of subsequent empirical evaluations. In the second part of the paper, we turn our attention to an important area of application of bandit algorithms: clinical trials. Although the design of clinical trials has been one of the principal practical problems motivating research on multi-armed bandits, bandit algorithms have never been evaluated as potential treatment allocation strategies. Using data from a real study, we simulate the outcome that a 2001-2002 clinical trial would have had if bandit algorithms had been used to allocate patients to treatments. We find that an adaptive trial would have successfully treated at least 50% more patients, while significantly reducing the number of adverse effects and increasing patient retention. At the end of the trial, the best treatment could have still been identified with a high level of statistical confidence. Our findings demonstrate that bandit algorithms are attractive alternatives to current adaptive treatment allocation strategies.
---
paper_title: The Randomized Play-the-Winner Rule in Medical Trials

paper_content:

Abstract In a sequential medical trial, a simple randomized treatment assignment rule is proposed and analyzed. On the average this rule assigns more patients to the better treatment, and it is applicable to the case where patients have delayed responses to treatments. This new assignment rule is studied for both a fixed sample size and an inverse stopping rule.
---
paper_title: Adaptive design methods in clinical trials – a review

paper_content:

In recent years, the use of adaptive design methods in clinical research and development based on accrued data has become very popular due to its flexibility and efficiency. Based on adaptations applied, adaptive designs can be classified into three categories: prospective, concurrent (ad hoc), and retrospective adaptive designs. An adaptive design allows modifications made to trial and/or statistical procedures of ongoing clinical trials. However, it is a concern that the actual patient population after the adaptations could deviate from the originally target patient population and consequently the overall type I error (to erroneously claim efficacy for an infective drug) rate may not be controlled. In addition, major adaptations of trial and/or statistical procedures of on-going trials may result in a totally different trial that is unable to address the scientific/medical questions the trial intends to answer. In this article, several commonly considered adaptive designs in clinical trials are reviewed. Impacts of ad hoc adaptations (protocol amendments), challenges in by design (prospective) adaptations, and obstacles of retrospective adaptations are described. Strategies for the use of adaptive design in clinical development of rare diseases are discussed. Some examples concerning the development of Velcade intended for multiple myeloma and non-Hodgkin's lymphoma are given. Practical issues that are commonly encountered when implementing adaptive design methods in clinical trials are also discussed.
---
paper_title: A Model for Selecting One of Two Medical Treatments

paper_content:

Abstract A simple cost function approach is proposed for designing an optimal clinical trial when a total of N patients with a disease are to be treated with one of two medical treatments. The cost function is constructed with but one cost, the consequences of treating a patient with the superior or inferior of the two treatments. Fixed sample size and sequential trials are considered. Minimax, maximin, and Bayesian approaches are used for determining the optimal size of a fixed sample trial and the optimal position of the boundaries of a sequential trial. Comparisons of the different approaches are made as well as comparisons of the results for the fixed and sequential plans.
---
paper_title: The use of Thompson sampling to increase estimation precision.

paper_content:

In this article, we consider a sequential sampling scheme for efficient estimation of the difference between the means of two independent treatments when the population variances are unequal across groups. The sampling scheme proposed is based on a solution to bandit problems called Thompson sampling. While this approach is most often used to maximize the cumulative payoff over competing treatments, we show that the same method can also be used to balance exploration and exploitation when the aim of the experimenter is to efficiently increase estimation precision. We introduce this novel design optimization method and, by simulation, show its effectiveness.
---
paper_title: Adaptive clinical trial designs for phase I cancer studies

paper_content:

Adaptive clinical trials are becoming increasingly popular research designs for clinical investigation. Adaptive designs are particularly useful in phase I cancer studies where clinical data are scant and the goals are to assess the drug dose-toxicity profile and to determine the maximum tolerated dose while minimizing the number of study patients treated at suboptimal dose levels. In the current work we give an overview of adaptive design methods for phase I cancer trials. We find that modern statistical literature is replete with novel adaptive designs that have clearly defined objectives and established statistical properties, and are shown to outperform conventional dose finding methods such as the 3+3 design, both in terms of statistical efficiency and in terms of minimizing the number of patients treated at highly toxic or nonefficacious doses. We discuss statistical, logistical, and regulatory aspects of these designs and present some links to non-commercial statistical software for implementing these methods in practice. MSC 2010 subject classifications: Primary 62L05, 62L10, 62L12; secondary 62L20.
---
paper_title: Randomized play-the-winner clinical trials: review and recommendations.

paper_content:

The randomized play-the-winner rule is an adaptive randomized design, based on an urn model, that is used occasionally in clinical trials. This paper discusses practical and theoretical issues arising from its use, including stratification, delayed response, operating characteristics, selection of urn parameters, and inference. The paper also discusses recent experience with adaptive clinical trials within the pharmaceutical industry. The author concludes that the randomized play-the-winner rule is appropriate for some clinical trials, but intense and thoughtful planning must take place in the design phase. Such planning should incorporate considerations of variability, power, and appropriate techniques.
---
paper_title: Multi-armed bandit algorithms and empirical evaluation

paper_content:

The multi-armed bandit problem for a gambler is to decide which arm of a K-slot machine to pull to maximize his total reward in a series of trials. Many real-world learning and optimization problems can be modeled in this way. Several strategies or algorithms have been proposed as a solution to this problem in the last two decades, but, to our knowledge, there has been no common evaluation of these algorithms. ::: ::: This paper provides a preliminary empirical evaluation of several multi-armed bandit algorithms. It also describes and analyzes a new algorithm, Poker (Price Of Knowledge and Estimated Reward) whose performance compares favorably to that of other existing algorithms in several experiments. One remarkable outcome of our experiments is that the most naive approach, the e-greedy strategy, proves to be often hard to beat.
---
paper_title: The nonstochastic multiarmed bandit problem

paper_content:

In the multi-armed bandit problem, a gambler must decide which arm of non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to nd the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate . We show by a matching lower bound that this is best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of strategies then our algorithm approaches the per-round payoff of the strategy at the rate . Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate
---
paper_title: Analysis of Thompson Sampling for the multi-armed bandit problem

paper_content:

The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the stochastic multi-armed bandit problem. More precisely, for the stochastic two-armed bandit problem, the expected regret in timeT isO( lnT + 1 3 ). And, for the stochasticN -armed bandit problem, the expected regret in time T is O( h ( P N 1 2 ) 2 i lnT ). Our bounds are optimal but for the dependence on i and the
---
paper_title: The use of Thompson sampling to increase estimation precision.

paper_content:

In this article, we consider a sequential sampling scheme for efficient estimation of the difference between the means of two independent treatments when the population variances are unequal across groups. The sampling scheme proposed is based on a solution to bandit problems called Thompson sampling. While this approach is most often used to maximize the cumulative payoff over competing treatments, we show that the same method can also be used to balance exploration and exploitation when the aim of the experimenter is to efficiently increase estimation precision. We introduce this novel design optimization method and, by simulation, show its effectiveness.
---
paper_title: Contextual Bandit Algorithms with Supervised Learning Guarantees

paper_content:

We address the problem of competing with any large set of N policies in the nonstochastic bandit setting, where the learner must repeatedly select among K actions but observes only the reward of the chosen action.
---
paper_title: Hybrid Stochastic-Adversarial On-line Learning

paper_content:

Most of the research in online learning focused either on the problem of adversarial classification (i.e., both inputs and labels are arbitrarily chosen by an adversary) or on the traditional supervised learning problem in which samples are independently generated from a fixed probability distribution. Nonetheless, in a number of domains the relationship between inputs and labels may be adversarial, whereas input instances are generated according to a constant distribution. This scenario can be formalized as an hybrid classification problem in which inputs are stochastic, while labels are adversarial. In this paper, we introduce this hybrid stochastic-adversarial classification problem, we propose an online learning algorithm for its solution, and we analyze its performance. In particular, we show that, given a hypothesis space H with finite VC dimension, it is possible to incrementally build a suitable finite set of hypotheses that can be used as input for an exponentially weighted forecaster achieving a cumulative regret of order O( p nV C(H) log n) with overwhelming probability. Finally, we discuss extensions to multi-label classification, learning from experts and bandit settings with stochastic side information, and application to games.
---
paper_title: A theory of the learnable

paper_content:

Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. We find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. The methodology and results suggest concrete principles for designing realistic learning systems.
---
paper_title: Notes on Randomized Algorithms

paper_content:

Lecture notes for the Yale Computer Science course CPSC 469/569 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergraduate course on randomized algorithms. Discusses tools from probability theory, including random variables and expectations, union bound arguments, concentration bounds, applications of martingales and Markov chains, and the Lov\'asz Local Lemma. Algorithmic topics include analysis of classic randomized algorithms such as Quicksort and Hoare's FIND, randomized tree data structures, hashing, Markov chain Monte Carlo sampling, randomized approximate counting, derandomization, quantum computing, and some examples of randomized distributed algorithms.
---
paper_title: Algorithms for multi-armed bandit problems

paper_content:

Although many algorithms for the multi-armed bandit problem are well-understood theoretically, empirical confirmation of their effectiveness is generally scarce. This paper presents a thorough empirical study of the most popular multi-armed bandit algorithms. Three important observations can be made from our results. Firstly, simple heuristics such as epsilon-greedy and Boltzmann exploration outperform theoretically sound algorithms on most settings by a significant margin. Secondly, the performance of most algorithms varies dramatically with the parameters of the bandit problem. Our study identifies for each algorithm the settings where it performs well, and the settings where it performs poorly. Thirdly, the algorithms' performance relative each to other is affected only by the number of bandit arms and the variance of the rewards. This finding may guide the design of subsequent empirical evaluations. In the second part of the paper, we turn our attention to an important area of application of bandit algorithms: clinical trials. Although the design of clinical trials has been one of the principal practical problems motivating research on multi-armed bandits, bandit algorithms have never been evaluated as potential treatment allocation strategies. Using data from a real study, we simulate the outcome that a 2001-2002 clinical trial would have had if bandit algorithms had been used to allocate patients to treatments. We find that an adaptive trial would have successfully treated at least 50% more patients, while significantly reducing the number of adverse effects and increasing patient retention. At the end of the trial, the best treatment could have still been identified with a high level of statistical confidence. Our findings demonstrate that bandit algorithms are attractive alternatives to current adaptive treatment allocation strategies.
---
paper_title: SAMPLE MEAN BASED INDEX POLICIES WITH O(logn) REGRET FOR THE MULTI-ARMED BANDIT PROBLEM

paper_content:

We consider a non-Bayesian infinite horizon version of the multi-armed bandit problem with the objective of designing simple policies whose regret increases sldwly with time. In their seminal work on this problem, Lai and Robbins had obtained a O(logn) lower bound on the regret with a constant that depends on the KullbackLeibler number. They also constructed policies for some specific families of probability distributions (including exponential families) that achieved the lower bound. In this paper we construct index policies that depend on the rewards from each arm only through their sample mean. These policies are computationally much simpler and are also applicable much more generally. They achieve a O(logn) regret with a constant that is also based on the Kullback-Leibler number. This constant turns out to be optimal for one-parameter exponential families; however, in general it is derived from the optimal one via a 'contraction' principle. Our results rely entirely on a few key lemmas from the theory of large deviations.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: FOUR PROOFS OF GITTINS’ MULTIARMED BANDIT THEOREM

paper_content:

We study four proofs that the Gittins index priority rule is optimal for alternative bandit processes. These include Gittins’ original exchange argument, Weber’s prevailing charge argument, Whittle’s Lagrangian dual approach, and Bertsimas and Nino-Mora’s proof based on the achievable region approach and generalized conservation laws. We extend the achievable region proof to infinite countable state spaces, by using infinite dimensional linear programming theory.
---
paper_title: A short proof of the Gittins index theorem

paper_content:

Provides a short and elementary proof of the Gittins index theorem for the multi-armed bandit problem, for the case where each bandit is modeled as a finite-state semi-Markov process. The author also indicates how this proof can be extended to the branching bandits and Klimov problems. >
---
paper_title: A dynamic allocation index for the discounted multiarmed bandit problem

paper_content:

SUMMARY Earlier work by the present authors has established the existence of and a characterization of a priority index giving the Bayes rule for the discounted multiarmed bandit problem. The calculation of this index is described and illustrated, and the results obtained briefly discussed. The two-armed bandit problem is so-called because it models the situation faced by a gambler using a fruit machine with two arms, instead of just one. When an arm is pulled the result is that the gambler either wins a prize or not. All the prizes are of the same value, and for each arm there is a certain constant, and in general unknown, probability of success every time it is pulled, which is different for the two arms. The gambler's problem is to choose a sequence of pulls on the two arms, which depends in a sequential manner on the record of successes and failures, in such a fashion as to maximize his expected total gains. In one version of the problem the gambler is allowed a fixed number of pulls in total. Alternatively we may consider a discounted version of the problem for which the value of a prize received at the tth pull, irrespective of the arms pulled on the previous (t - 1) pulls, is multiplied by at-1, for some a < 1. Multiarmed bandit problems are similar, but with more than two arms. Their chief practical motivation comes from clinical trials, though they are also of interest as probably the simplest worthwhile set of problems in the sequential design of experiments. Recent numerical investigation of Bayesian rules for the two-armed bandit problem with independent arms by P. W. Jones (1975) and Wahrenberger, Antle & Klimko (1977) have shown significant improvements when compared with other rules which have been proposed. However, the calculation of these rules is costly in terms of computer storage and time, and the reported results are all for a total number of trials which does not exceed 50. The present authors (1974) showed that for the discounted case with an infinite number of trials, first considered by Bellman (1956), the Bayes rule is given by a function which, for each arm, depends on the posterior distribution for the unknown success probability. The Bayes rule is always to pull the arm for which the current value of the function is larger, for which reason the function was termed a dynamic allocation index. Moreover, this result holds for the multiarmed bandit problem. Gittins (1979) obtained a characterization of the dynamic allocation index which actually holds for a range of problems of which the multiarmed bandit is just one example. The present paper reports on a numerical investigation of the dynamic allocation index using this characterization, which shows that some further
---
paper_title: Optimal learning and experimentation in bandit problems

paper_content:

Abstract This paper studies how and how much active experimentation is used in discounted or finite-horizon optimization problems with an agent who chooses actions sequentially from a finite set of actions, with rewards depending on unknown parameters associated with the actions. Closed-form approximations are developed for the optimal rules in these ‘multi-armed bandit’ problems. Some refinements and modifications of the basic structure of these approximations also provide a nearly optimal solution to the long-standing problem of incorporating switching costs into multi-armed bandits.
---
paper_title: The Multi-Armed Bandit Problem: Decomposition and Computation

paper_content:

This paper is dedicated to our friend and mentor, Cyrus Derman, on the occasion of his 60th birthday. ::: ::: The multi-armed bandit problem arises in sequentially allocating effort to one of N projects and sequentially assigning patients to one of N treatments in clinical trials. Gittins and Jones Gittins, J. C., Jones, D. M. 1974. A dynamic allocation index for the sequential design of experiments. J. Gani, K. Sarkadi, L. Vince, eds. Progress in Statistics. European Meeting of Statisticians, 1972, 1, North Holland, Amsterdam, 241--266. have shown that one optimal policy for the N-project problem, an N-dimensional discounted Markov decision chain, is determined by the following largest-index rule. There is an index for each state of each given project that depends only on the data of that project. In each period one allocates effort to a project with largest current index. The purpose of this paper is to give a short proof of this result and a new characterization of the index of a project in state i, viz., as the maximum expected present value in state i for the restart-in-i problem in which, in each state and period, one either continues allocating effort to the project or immediately restarts the project in state i. Moreover, it is shown that an approximate largest-index rule yields an approximately optimal policy. These results lead to more efficient methods of computing the indices on-line and/or for sparse transition matrices in large state spaces than have been suggested heretofore. By using a suitable implementation of successive approximations, a policy whose expected present value is within 100e% of the maximum possible range of values of the indices can be found on-line with at most N + T-1TM operations where M is the number of operations required to calculate one approximation, T is the least integer majorizing the ratio ln e/ln a and 0
---
paper_title: Multi-armed bandit algorithms and empirical evaluation

paper_content:

The multi-armed bandit problem for a gambler is to decide which arm of a K-slot machine to pull to maximize his total reward in a series of trials. Many real-world learning and optimization problems can be modeled in this way. Several strategies or algorithms have been proposed as a solution to this problem in the last two decades, but, to our knowledge, there has been no common evaluation of these algorithms. ::: ::: This paper provides a preliminary empirical evaluation of several multi-armed bandit algorithms. It also describes and analyzes a new algorithm, Poker (Price Of Knowledge and Estimated Reward) whose performance compares favorably to that of other existing algorithms in several experiments. One remarkable outcome of our experiments is that the most naive approach, the e-greedy strategy, proves to be often hard to beat.
---
paper_title: SAMPLE MEAN BASED INDEX POLICIES WITH O(logn) REGRET FOR THE MULTI-ARMED BANDIT PROBLEM

paper_content:

We consider a non-Bayesian infinite horizon version of the multi-armed bandit problem with the objective of designing simple policies whose regret increases sldwly with time. In their seminal work on this problem, Lai and Robbins had obtained a O(logn) lower bound on the regret with a constant that depends on the KullbackLeibler number. They also constructed policies for some specific families of probability distributions (including exponential families) that achieved the lower bound. In this paper we construct index policies that depend on the rewards from each arm only through their sample mean. These policies are computationally much simpler and are also applicable much more generally. They achieve a O(logn) regret with a constant that is also based on the Kullback-Leibler number. This constant turns out to be optimal for one-parameter exponential families; however, in general it is derived from the optimal one via a 'contraction' principle. Our results rely entirely on a few key lemmas from the theory of large deviations.
---
paper_title: Multi-armed bandit algorithms and empirical evaluation

paper_content:

The multi-armed bandit problem for a gambler is to decide which arm of a K-slot machine to pull to maximize his total reward in a series of trials. Many real-world learning and optimization problems can be modeled in this way. Several strategies or algorithms have been proposed as a solution to this problem in the last two decades, but, to our knowledge, there has been no common evaluation of these algorithms. ::: ::: This paper provides a preliminary empirical evaluation of several multi-armed bandit algorithms. It also describes and analyzes a new algorithm, Poker (Price Of Knowledge and Estimated Reward) whose performance compares favorably to that of other existing algorithms in several experiments. One remarkable outcome of our experiments is that the most naive approach, the e-greedy strategy, proves to be often hard to beat.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

paper_content:

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K actions in response to the observed context, and observes the reward only for that action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only O(√KT) oracle calls across all T rounds. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We conduct a proof-of-concept experiment which demonstrates the excellent computational and statistical performance of (an online variant of) our algorithm relative to several strong baselines.
---
paper_title: The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information

paper_content:

We present Epoch-Greedy, an algorithm for multi-armed bandits with observable side information. Epoch-Greedy has the following properties: No knowledge of a time horizon $T$ is necessary. The regret incurred by Epoch-Greedy is controlled by a sample complexity bound for a hypothesis class. The regret scales as $O(T^{2/3} S^{1/3})$ or better (sometimes, much better). Here $S$ is the complexity term in a sample complexity bound for standard supervised learning.
---
paper_title: Probability inequalities for sums of bounded random variables

paper_content:

Abstract Upper bounds are derived for the probability that the sum S of n independent random variables exceeds its mean ES by a positive number nt. It is assumed that the range of each summand of S is bounded or bounded above. The bounds for Pr {S – ES ≥ nt} depend only on the endpoints of the ranges of the summands and the mean, or the mean and the variance of S. These results are then used to obtain analogous inequalities for certain sums of dependent random variables such as U statistics and the sum of a random sample without replacement from a finite population.
---
paper_title: SAMPLE MEAN BASED INDEX POLICIES WITH O(logn) REGRET FOR THE MULTI-ARMED BANDIT PROBLEM

paper_content:

We consider a non-Bayesian infinite horizon version of the multi-armed bandit problem with the objective of designing simple policies whose regret increases sldwly with time. In their seminal work on this problem, Lai and Robbins had obtained a O(logn) lower bound on the regret with a constant that depends on the KullbackLeibler number. They also constructed policies for some specific families of probability distributions (including exponential families) that achieved the lower bound. In this paper we construct index policies that depend on the rewards from each arm only through their sample mean. These policies are computationally much simpler and are also applicable much more generally. They achieve a O(logn) regret with a constant that is also based on the Kullback-Leibler number. This constant turns out to be optimal for one-parameter exponential families; however, in general it is derived from the optimal one via a 'contraction' principle. Our results rely entirely on a few key lemmas from the theory of large deviations.
---
paper_title: On Hoeffding’s inequalities

paper_content:

In a celebrated work by Hoeffding [J. Amer. Statist. Assoc. 58 (1963) 13-30], several inequalities for tail probabilities of sums M n = X 1 + ... + X n of bounded independent random variables X j were proved. These inequalities had a considerable impact on the development of probability and statistics, and remained unimproved until 1995 when Talagrand [Inst. Hautes Etudes Sci. Publ. Math. 81 (1995a) 73-205] inserted certain missing factors in the bounds of two theorems. By similar factors, a third theorem was refined by Pinelis [Progress in Probability 43 (1998) 257-314] and refined (and extended) by me. In this article, I introduce a new type of inequality. Namely, I show that P{M n ≥ x} ≤ cP{S n ≥ x}, where c is an absolute constant and S n = e 1 + ... + e n is a sum of independent identically distributed Bernoulli random variables (a random variable is called Bernoulli if it assumes at most two values). The inequality holds for those x ∈ Ρ where the survival function x → P{S n ≥ x} has a jump down. For the remaining x the inequality still holds provided that the function between the adjacent jump points is interpolated linearly or log-linearly. If it is necessary, to estimate P{S n ≥ x} special bounds can be used for binomial probabilities. The results extend to martingales with bounded differences. It is apparent that Theorem 1.1 of this article is the most important. The inequalities have applications to measure concentration, leading to results of the type where, up to an absolute constant, the measure concentration is dominated by the concentration in a simplest appropriate model, such results will be considered elsewhere.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: Minimax Policies for Adversarial and Stochastic Bandits

paper_content:

We fill in a long open gap in the characterization of the minimax rate for the multi-armed bandit prob- lem. Concretely, we remove an extraneous loga- rithmic factor in the previously known upper bound and propose a new family of randomized algorithms based on an implicit normalization, as well as a new analysis. We also consider the stochastic case, and prove that an appropriate modification of the upper confidence bound policy UCB1 (Auer et al., 2002) achieves the distribution-free optimal rate while still having a distribution-dependent rate log- arithmic in the number of plays.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: Minimax Policies for Adversarial and Stochastic Bandits

paper_content:

We fill in a long open gap in the characterization of the minimax rate for the multi-armed bandit prob- lem. Concretely, we remove an extraneous loga- rithmic factor in the previously known upper bound and propose a new family of randomized algorithms based on an implicit normalization, as well as a new analysis. We also consider the stochastic case, and prove that an appropriate modification of the upper confidence bound policy UCB1 (Auer et al., 2002) achieves the distribution-free optimal rate while still having a distribution-dependent rate log- arithmic in the number of plays.
---
paper_title: EXP3 with drift detection for the switching bandit problem

paper_content:

The multi-armed bandit is a model of exploration and exploitation, where one must select, within a finite set of arms, the one which maximizes the cumulative reward up to the time horizon T. For the adversarial multi-armed bandit problem, where the sequence of rewards is chosen by an oblivious adversary, the notion of best arm during the time horizon is too restrictive for applications such as ad-serving, where the best ad could change during time range. In this paper, we consider a variant of the adversarial multi-armed bandit problem, where the time horizon is divided into unknown time periods within which rewards are drawn from stochastic distributions. During each time period, there is an optimal arm which may be different from the optimal arm at the previous time period. We present an algorithm taking advantage of the constant exploration of EXP3 to detect when the best arm changes. Its analysis shows that on a run divided into N periods where the best arm changes, the proposed algorithms achieves a regret in O(N √T log T).
---
paper_title: The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

paper_content:

This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satisfies a uniformly better regret bound than UCB or UCB2; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specific classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, UCB2, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm.
---
paper_title: A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

paper_content:

We consider a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit problem in the case of distributions with finite supports (not necessarily known beforehand), whose asymptotic regret matches the lower bound of \cite{Burnetas96}. Our contribution is to provide a finite-time analysis of this algorithm; we get bounds whose main terms are smaller than the ones of previously known algorithms with finite-time analyses (like UCB-type algorithms).
---
paper_title: A Neural Networks Committee for the Contextual Bandit Problem

paper_content:

This paper presents a new contextual bandit algorithm, NeuralBandit, which does not need hypothesis on stationarity of contexts and rewards. Several neural networks are trained to modelize the value of rewards knowing the context. Two variants, based on multi-experts approach, are proposed to choose online the parameters of multi-layer perceptrons. The proposed algorithms are successfully tested on a large dataset with and without stationarity of rewards.
---
paper_title: On bayesian upper confidence bounds for bandit problems

paper_content:

Stochastic bandit problems have been analyzed from two dierent perspectives: a frequentist view, where the parameter is a deterministic unknown quantity, and a Bayesian approach, where the parameter is drawn from a prior distribution. We show in this paper that methods derived from this second perspective prove optimal when evaluated using the frequentist cumulated regret as a measure of performance. We give a general formulation for a class of Bayesian index policies that rely on quantiles of the posterior distribution. For binary bandits, we prove that the corresponding algorithm, termed BayesUCB, satisfies finite-time regret bounds that imply its asymptotic optimality. More generally, Bayes-UCB appears as an unifying framework for several variants of the UCB algorithm addressing dierent
---
paper_title: A Neural Networks Committee for the Contextual Bandit Problem

paper_content:

This paper presents a new contextual bandit algorithm, NeuralBandit, which does not need hypothesis on stationarity of contexts and rewards. Several neural networks are trained to modelize the value of rewards knowing the context. Two variants, based on multi-experts approach, are proposed to choose online the parameters of multi-layer perceptrons. The proposed algorithms are successfully tested on a large dataset with and without stationarity of rewards.
---
paper_title: Sequential Medical Trials

paper_content:

Abstract In an extended review of Sequential Medical Trials by P. Armitage, the statistical principles which should govern the analysis of experimental observations, and the planning of experiments, are discussed. It is suggested that the operating-characteristic concepts of the Neyman-Pearson theory of tests are inappropriate to the analysis and interpretation of experimental data; the likelihood principle should be followed instead. The planning of medical trials under an ethical injunction against unnecessary continuance of inferior treatments is studied in some detail. The propriety of such trials is considered.
---
paper_title: Multi-armed bandit algorithms and empirical evaluation

paper_content:

The multi-armed bandit problem for a gambler is to decide which arm of a K-slot machine to pull to maximize his total reward in a series of trials. Many real-world learning and optimization problems can be modeled in this way. Several strategies or algorithms have been proposed as a solution to this problem in the last two decades, but, to our knowledge, there has been no common evaluation of these algorithms. ::: ::: This paper provides a preliminary empirical evaluation of several multi-armed bandit algorithms. It also describes and analyzes a new algorithm, Poker (Price Of Knowledge and Estimated Reward) whose performance compares favorably to that of other existing algorithms in several experiments. One remarkable outcome of our experiments is that the most naive approach, the e-greedy strategy, proves to be often hard to beat.
---
paper_title: Adaptive Monte Carlo via Bandit Allocation

paper_content:

We consider the problem of sequentially choosing between a set of unbiased Monte Carlo estimators to minimize the mean-squared-error (MSE) of a final combined estimate. By reducing this task to a stochastic multi-armed bandit problem, we show that well developed allocation strategies can be used to achieve an MSE that approaches that of the best estimator chosen in retrospect. We then extend these developments to a scenario where alternative estimators have different, possibly stochastic costs. The outcome is a new set of adaptive Monte Carlo strategies that provide stronger guarantees than previous approaches while offering practical advantages.
---
paper_title: Cold-start Problems in Recommendation Systems via Contextual-bandit Algorithms

paper_content:

In this paper, we study a cold-start problem in recommendation systems where we have completely new users entered the systems. There is not any interaction or feedback of the new users with the systems previoustly, thus no ratings are available. Trivial approaches are to select ramdom items or the most popular ones to recommend to the new users. However, these methods perform poorly in many case. In this research, we provide a new look of this cold-start problem in recommendation systems. In fact, we cast this cold-start problem as a contextual-bandit problem. No additional information on new users and new items is needed. We consider all the past ratings of previous users as contextual information to be integrated into the recommendation framework. To solve this type of the cold-start problems, we propose a new efficient method which is based on the LinUCB algorithm for contextual-bandit problems. The experiments were conducted on three different publicly-available data sets, namely Movielens, Netflix and Yahoo!Music. The new proposed methods were also compared with other state-of-the-art techniques. Experiments showed that our new method significantly improves upon all these methods.
---
paper_title: Stochastic Regret Minimization via Thompson Sampling

paper_content:

The Thompson Sampling (TS) policy is a widely implemented algorithm for the stochastic multiarmed bandit (MAB) problem. Given a prior distribution over possible parameter settings of the underlying reward distributions of the arms, at each time instant, the policy plays an arm with probability equal to the probability that this arm has largest mean reward conditioned on the current posterior distributions of the arms. This policy generalizes the celebrated “probability matching” heuristic which has been experimentally and widely observed in human decision making. However, despite its ubiquity, the Thompson Sampling policy is poorly understood. Our goal in this paper is to make progress towards understanding the empirical success of this policy. We proceed using the lens of approximation algorithms and problem definitions from stochastic optimization. We focus on an objective function termed stochastic regret that captures the expected number of times the policy plays an arm that is not the eventual best arm, where the expectation is over the prior distribution. Given such a definition, we show that TS is a 2‐ approximation to the optimal decision policy in two extreme but canonical scenarios. One such scenario is the two-armed bandit problem which is used as a calibration point in all bandit literature. The second scenario is stochastic optimization where the outcome of a random variable is revealed in a single play to a high or low deterministic value. We show that the 2 approximation is tight in both these scenarios. We provide an uniform analysis framework that in theory is capable of proving our conjecture that the TS policy is a 2‐approximation to the optimal decision policy for minimizing stochastic regret, for any prior distribution and any time horizon.
---
paper_title: Thompson sampling with the online bootstrap

paper_content:

Thompson sampling provides a solution to bandit problems in which new observations are allocated to arms with the posterior probability that an arm is optimal. While sometimes easy to implement and asymptotically optimal, Thompson sampling can be computationally demanding in large scale bandit problems, and its performance is dependent on the model fit to the observed data. We introduce bootstrap Thompson sampling (BTS), a heuristic method for solving bandit problems which modifies Thompson sampling by replacing the posterior distribution used in Thompson sampling by a bootstrap distribution. We first explain BTS and show that the performance of BTS is competitive to Thompson sampling in the well-studied Bernoulli bandit case. Subsequently, we detail why BTS using the online bootstrap is more scalable than regular Thompson sampling, and we show through simulation that BTS is more robust to a misspecified error distribution. BTS is an appealing modification of Thompson sampling, especially when samples from the posterior are otherwise not available or are costly.
---
paper_title: Learning to Optimize Via Posterior Sampling

paper_content:

This paper considers the use of a simple posterior sampling algorithm to balance between exploration and exploitation when learning to optimize actions such as in multi-armed bandit problems. The algorithm, also known as Thompson Sampling, offers significant advantages over the popular upper confidence bound (UCB) approach, and can be applied to problems with finite or infinite action spaces and complicated relationships among action rewards. We make two theoretical contributions. The first establishes a connection between posterior sampling and UCB algorithms. This result lets us convert regret bounds developed for UCB algorithms into Bayesian regret bounds for posterior sampling. Our second theoretical contribution is a Bayesian regret bound for posterior sampling that applies broadly and can be specialized to many model classes. This bound depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm Bayesian regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models. Further, our analysis provides insight into performance advantages of posterior sampling, which are highlighted through simulation results that demonstrate performance surpassing recently proposed UCB algorithms.
---
paper_title: Notes on Randomized Algorithms

paper_content:

Lecture notes for the Yale Computer Science course CPSC 469/569 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergraduate course on randomized algorithms. Discusses tools from probability theory, including random variables and expectations, union bound arguments, concentration bounds, applications of martingales and Markov chains, and the Lov\'asz Local Lemma. Algorithmic topics include analysis of classic randomized algorithms such as Quicksort and Hoare's FIND, randomized tree data structures, hashing, Markov chain Monte Carlo sampling, randomized approximate counting, derandomization, quantum computing, and some examples of randomized distributed algorithms.
---
paper_title: Contextual Bandit for Active Learning: Active Thompson Sampling

paper_content:

The labelling of training examples is a costly task in a supervised classification. Active learning strategies answer this problem by selecting the most useful unlabelled examples to train a predictive model. The choice of examples to label can be seen as a dilemma between the exploration and the exploitation over the data space representation. In this paper, a novel active learning strategy manages this compromise by modelling the active learning problem as a contextual bandit problem. We propose a sequential algorithm named Active Thompson Sampling (ATS), which, in each round, assigns a sampling distribution on the pool, samples one point from this distribution, and queries the oracle for this sample point label. Experimental comparison to previously proposed active learning algorithms show superior performance on a real application dataset.
---
paper_title: Analysis of Thompson Sampling for the multi-armed bandit problem

paper_content:

The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the stochastic multi-armed bandit problem. More precisely, for the stochastic two-armed bandit problem, the expected regret in timeT isO( lnT + 1 3 ). And, for the stochasticN -armed bandit problem, the expected regret in time T is O( h ( P N 1 2 ) 2 i lnT ). Our bounds are optimal but for the dependence on i and the
---
paper_title: From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning

paper_content:

This work covers several aspects of the optimism in the face of uncertainty principle applied to large scale optimization problems under finite numerical budget. The initial motivation for the research reported here originated from the empirical success of the so-called Monte-Carlo Tree Search method popularized in computer-go and further extended to many other games as well as optimization and planning problems. Our objective is to contribute to the development of theoretical foundations of the field by characterizing the complexity of the underlying optimization problems and designing efficient algorithms with performance guarantees. The main idea presented here is that it is possible to decompose a complex decision making problem (such as an optimization problem in a large search space) into a sequence of elementary decisions, where each decision of the sequence is solved using a (stochastic) multi-armed bandit (simple mathematical model for decision making in stochastic environments). This so-called hierarchical bandit approach (where the reward observed by a bandit in the hierarchy is itself the return of another bandit at a deeper level) possesses the nice feature of starting the exploration by a quasi-uniform sampling of the space and then focusing progressively on the most promising area, at different scales, according to the evaluations observed so far, and eventually performing a local search around the global optima of the function. The performance of the method is assessed in terms of the optimality of the returned solution as a function of the number of function evaluations. Our main contribution to the field of function optimization is a class of hierarchical optimistic algorithms designed for general search spaces (such as metric spaces, trees, graphs, Euclidean spaces, ...) with different algorithmic instantiations depending on whether the evaluations are noisy or noiseless and whether some measure of the ''smoothness'' of the function is known or unknown. The performance of the algorithms depend on the local behavior of the function around its global optima expressed in terms of the quantity of near-optimal states measured with some metric. If this local smoothness of the function is known then one can design very efficient optimization algorithms (with convergence rate independent of the space dimension), and when it is not known, we can build adaptive techniques that can, in some cases, perform almost as well as when it is known.
---
paper_title: The many faces of optimism: a unifying approach

paper_content:

The exploration-exploitation dilemma has been an intriguing and unsolved problem within the framework of reinforcement learning. "Optimism in the face of uncertainty" and model building play central roles in advanced exploration methods. Here, we integrate several concepts and obtain a fast and simple algorithm. We show that the proposed algorithm finds a near-optimal policy in polynomial time, and give experimental evidence that it is robust and efficient compared to its ascendants.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: On bayesian upper confidence bounds for bandit problems

paper_content:

Stochastic bandit problems have been analyzed from two dierent perspectives: a frequentist view, where the parameter is a deterministic unknown quantity, and a Bayesian approach, where the parameter is drawn from a prior distribution. We show in this paper that methods derived from this second perspective prove optimal when evaluated using the frequentist cumulated regret as a measure of performance. We give a general formulation for a class of Bayesian index policies that rely on quantiles of the posterior distribution. For binary bandits, we prove that the corresponding algorithm, termed BayesUCB, satisfies finite-time regret bounds that imply its asymptotic optimality. More generally, Bayes-UCB appears as an unifying framework for several variants of the UCB algorithm addressing dierent
---
paper_title: An Empirical Evaluation of Thompson Sampling

paper_content:

Thompson sampling is one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly unpopular in the literature. We present here some empirical results using Thompson sampling on simulated and real data, and show that it is highly competitive. And since this heuristic is very easy to implement, we argue that it should be part of the standard baselines to compare against.
---
paper_title: Notes on Randomized Algorithms

paper_content:

Lecture notes for the Yale Computer Science course CPSC 469/569 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergraduate course on randomized algorithms. Discusses tools from probability theory, including random variables and expectations, union bound arguments, concentration bounds, applications of martingales and Markov chains, and the Lov\'asz Local Lemma. Algorithmic topics include analysis of classic randomized algorithms such as Quicksort and Hoare's FIND, randomized tree data structures, hashing, Markov chain Monte Carlo sampling, randomized approximate counting, derandomization, quantum computing, and some examples of randomized distributed algorithms.
---
paper_title: The use of Thompson sampling to increase estimation precision.

paper_content:

In this article, we consider a sequential sampling scheme for efficient estimation of the difference between the means of two independent treatments when the population variances are unequal across groups. The sampling scheme proposed is based on a solution to bandit problems called Thompson sampling. While this approach is most often used to maximize the cumulative payoff over competing treatments, we show that the same method can also be used to balance exploration and exploitation when the aim of the experimenter is to efficiently increase estimation precision. We introduce this novel design optimization method and, by simulation, show its effectiveness.
---
paper_title: On the uniform asymptotic validity of subsampling and the bootstrap

paper_content:

This paper provides conditions under which subsampling and the bootstrap can be used to construct estimators of the quantiles of the distribution of a root that behave well uniformly over a large class of distributions $\mathbf{P}$. These results are then applied (i) to construct confidence regions that behave well uniformly over $\mathbf{P}$ in the sense that the coverage probability tends to at least the nominal level uniformly over $\mathbf{P}$ and (ii) to construct tests that behave well uniformly over $\mathbf{P}$ in the sense that the size tends to no greater than the nominal level uniformly over $\mathbf{P}$. Without these stronger notions of convergence, the asymptotic approximations to the coverage probability or size may be poor, even in very large samples. Specific applications include the multivariate mean, testing moment inequalities, multiple testing, the empirical process and U-statistics.
---
paper_title: Sub-sampling for Multi-armed Bandits

paper_content:

The stochastic multi-armed bandit problem is a popular model of the exploration/exploitation trade-off in sequential decision problems. We introduce a novel algorithm that is based on sub-sampling. Despite its simplicity, we show that the algorithm demonstrates excellent empirical performances against state-of-the-art algorithms, including Thompson sampling and KL-UCB. The algorithm is very flexible, it does need to know a set of reward distributions in advance nor the range of the rewards. It is not restricted to Bernoulli distributions and is also invariant under rescaling of the rewards. We provide a detailed experimental study comparing the algorithm to the state of the art, the main intuition that explains the striking results, and conclude with a finite-time regret analysis for this algorithm in the simplified two-arm bandit setting.
---
paper_title: Contextual Bandit Algorithms with Supervised Learning Guarantees

paper_content:

We address the problem of competing with any large set of N policies in the nonstochastic bandit setting, where the learner must repeatedly select among K actions but observes only the reward of the chosen action.
---
paper_title: Tighter Bounds for Multi-Armed Bandits with Expert Advice

paper_content:

Bandit problems are a classic way of formulating exploration versus exploitation tradeoffs. Auer et al. [ACBFS02] introduced the EXP4 algorithm, which explicitly decouples the set of A actions which can be taken in the world from the set of M experts (general strategies for selecting actions) with which we wish to be competitive. Auer et al. show that EXP4 has expected cumulative regret bounded by O( √ TA logM), where T is the total number of rounds. This bound is attractive when the number of actions is small compared to the number of experts, but poor when the situation is reversed. In this paper we introduce a new algorithm, similar in spirit to EXP4, which has a bound ofO( √ TS logM). The S parameter measures the extent to which expert recommendations agree; we always have S ≤ min {A,M}. We discuss practical applications that arise in the contextual bandits setting, including sponsored search keyword advertising. In these problems, common context means many actions are irrelevant on any given round, and so S << min {A,M}, implying our bounds offer a significant improvement. The key to our new algorithm is a linear-programing-based exploration strategy that is optimal in a certain sense. In addition to proving tighter bounds, we run experiments on real-world data from an online advertising problem, and demonstrate that our refined exploration strategy leads to significant improvements over known approaches.
---
paper_title: Risk, Uncertainty and Profit

paper_content:

In Risk, Uncertainty and Profit, Frank Knight explored the riddle of profitability in a competitive market profit should not be possible under competitive conditions, as the entry of new entrepreneurs would drive prices down and nullify margins, however evidence abounds of competitive yet profitable markets. To explain this seeming paradox, Knight uncovers the distinction between calculable risk and essentially unknowable uncertainty. Knight argued that risk stems from repeated events, which therefore allow probabilities to be calculated and factored into decisions, as for instance insurers do. Uncertainty however, stems from events that are unpredictable and as such cannot be prepared against. According to Knight, it is the interplay between risk and uncertainty on the one hand and competition between incumbent and new entrepreneurs that accounts for the enormous variation in profitability across firms and, for the same firms, over time. His insights on the sources of profit have been instrumental in shaping modern economic theory and to the development of a useful understanding of probability. This New Edition has been typeset with modern techniques and contains a newly compiled Index of important topics. It has been painstakingly proofread to ensure that it is free from errors and that the content is faithful to the original.
---
paper_title: The nonstochastic multiarmed bandit problem

paper_content:

In the multi-armed bandit problem, a gambler must decide which arm of non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to nd the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate . We show by a matching lower bound that this is best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of strategies then our algorithm approaches the per-round payoff of the strategy at the rate . Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: The nonstochastic multiarmed bandit problem

paper_content:

In the multi-armed bandit problem, a gambler must decide which arm of non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to nd the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate . We show by a matching lower bound that this is best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of strategies then our algorithm approaches the per-round payoff of the strategy at the rate . Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate
---
paper_title: The nonstochastic multiarmed bandit problem

paper_content:

In the multi-armed bandit problem, a gambler must decide which arm of non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to nd the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate . We show by a matching lower bound that this is best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of strategies then our algorithm approaches the per-round payoff of the strategy at the rate . Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate
---
paper_title: Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

paper_content:

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K actions in response to the observed context, and observes the reward only for that action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only O(√KT) oracle calls across all T rounds. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We conduct a proof-of-concept experiment which demonstrates the excellent computational and statistical performance of (an online variant of) our algorithm relative to several strong baselines.
---
paper_title: Using Confidence Bounds for Exploitation-Exploration Trade-offs

paper_content:

We show how a standard tool from statistics --- namely confidence bounds --- can be used to elegantly deal with situations which exhibit an exploitation-exploration trade-off. Our technique for designing and analyzing algorithms for such situations is general and can be applied when an algorithm has to make exploitation-versus-exploration decisions based on uncertain information provided by a random process. We apply our technique to two models with such an exploitation-exploration trade-off. For the adversarial bandit problem with shifting our new algorithm suffers only O((ST)1/2) regret with high probability over T trials with S shifts. Such a regret bound was previously known only in expectation. The second model we consider is associative reinforcement learning with linear value functions. For this model our technique improves the regret from O(T3/4) to O(T1/2).
---
paper_title: Efficient Optimal Learning for Contextual Bandits

paper_content:

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.
---
paper_title: Regret Bounds for the Adaptive Control of Linear Quadratic Systems

paper_content:

We study the average cost Linear Quadratic (LQ) control problem with unknown model parameters, also known as the adaptive control problem in the control community. We design an algorithm and prove that apart from logarithmic factors its regret up to time T is O( p T ). Unlike previous approaches that use a forced-exploration scheme, we construct a high-probability condence set around the model parameters and design an algorithm that plays optimistically with respect to this condence set. The construction of the condence set is based on the recent results from online least-squares estimation and leads to improved worst-case regret bound for the proposed algorithm. To the best of our knowledge this is the the rst time that a regret bound is derived for the LQ control problem.
---
paper_title: The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information

paper_content:

We present Epoch-Greedy, an algorithm for multi-armed bandits with observable side information. Epoch-Greedy has the following properties: No knowledge of a time horizon $T$ is necessary. The regret incurred by Epoch-Greedy is controlled by a sample complexity bound for a hypothesis class. The regret scales as $O(T^{2/3} S^{1/3})$ or better (sometimes, much better). Here $S$ is the complexity term in a sample complexity bound for standard supervised learning.
---
paper_title: Experience-efficient learning in associative bandit problems

paper_content:

We formalize the associative bandit problem framework introduced by Kaelbling as a learning-theory problem. The learning environment is modeled as a k-armed bandit where arm payoffs are conditioned on an observable input selected on each trial. We show that, if the payoff functions are constrained to a known hypothesis class, learning can be performed efficiently with respect to the VC dimension of this class. We formally reduce the problem of PAC classification to the associative bandit problem, producing an efficient algorithm for any hypothesis class for which efficient classification algorithms are known. We demonstrate the approach empirically on a scalable concept class.
---
paper_title: Contextual Bandits with Linear Payoff Functions

paper_content:

In this paper we study the contextual bandit problem (also known as the multi-armed bandit problem with expert advice) for linear payoff functions. For T rounds, K actions, and d dimensional feature vectors, we prove an O (√ Td ln(KT ln(T )/δ) ) regret bound that holds with probability 1− δ for the simplest known (both conceptually and computationally) efficient upper confidence bound algorithm for this problem. We also prove a lower bound of Ω( √ Td) for this setting, matching the upper bound up to logarithmic factors.
---
paper_title: Contextual Bandit Algorithms with Supervised Learning Guarantees

paper_content:

We address the problem of competing with any large set of N policies in the nonstochastic bandit setting, where the learner must repeatedly select among K actions but observes only the reward of the chosen action.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: Bandit problems with side observations

paper_content:

An extension of the traditional two-armed bandit problem is considered, in which the decision maker has access to some side information before deciding which arm to pull. At each time t, before making a selection, the decision maker is able to observe a random variable, X/sub t/, that provides some information on the rewards to be obtained. The focus is on finding uniformly good rules (that minimize the growth rate or the regret) and on quantifying how much the additional information helps. Various settings are considered and asymptotically tight lower bounds on the achievable regret are provided.
---
paper_title: A One-Armed Bandit Problem with a Concomitant Variable

paper_content:

Abstract We consider a Bayesian sequential allocation problem that incorporates a concomitant variable in the model. Although the model is highly simplified, our results do have some mildly surprising aspects: (a) the approximate solution to the allocation problem is simpler in the presence of concomitant information than in its absence, (b) the exact value of the discount factor is less important than in previous work, and (c) the myopic procedure is asymptotically optimal.
---
paper_title: The multi-armed bandit problem with covariates

paper_content:

We consider a multi-armed bandit problem in a setting where each arm produces a noisy reward realization which depends on an observable random covariate. As opposed to the traditional static multi-armed bandit problem, this setting allows for dynamically changing rewards that better describe applications where side information is available. We adopt a nonparametric model where the expected rewards are smooth functions of the covariate and where the hardness of the problem is captured by a margin parameter. To maximize the expected cumulative reward, we introduce a policy called Adaptively Binned Successive Elimination (abse) that adaptively decomposes the global problem into suitably “localized” static bandit problems. This policy constructs an adaptive partition using a variant of the Successive Elimination (se) policy. Our results include sharper regret bounds for the se policy in a static bandit problem and minimax optimal regret bounds for the abse policy in the dynamic problem.
---
paper_title: The nonstochastic multiarmed bandit problem

paper_content:

In the multi-armed bandit problem, a gambler must decide which arm of non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to nd the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate . We show by a matching lower bound that this is best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of strategies then our algorithm approaches the per-round payoff of the strategy at the rate . Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate
---
paper_title: Linearly Parameterized Bandits

paper_content:

We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an $r$-dimensional random vector $\mathbf{Z} \in \mathbb{R}^r$, where $r \geq 2$. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order $\Theta(r \sqrt{T})$, by establishing a lower bound for an arbitrary policy, and showing that a matching upper bound is obtained through a policy that alternates between exploration and exploitation phases. The phase-based policy is also shown to be effective if the set of arms satisfies a strong convexity condition. For the case of a general set of arms, we describe a near-optimal policy whose regret and Bayes risk admit upper bounds of the form $O(r \sqrt{T} \log^{3/2} T)$.
---
paper_title: Contextual Bandits with Linear Payoff Functions

paper_content:

In this paper we study the contextual bandit problem (also known as the multi-armed bandit problem with expert advice) for linear payoff functions. For T rounds, K actions, and d dimensional feature vectors, we prove an O (√ Td ln(KT ln(T )/δ) ) regret bound that holds with probability 1− δ for the simplest known (both conceptually and computationally) efficient upper confidence bound algorithm for this problem. We also prove a lower bound of Ω( √ Td) for this setting, matching the upper bound up to logarithmic factors.
---
paper_title: Parametric bandits: The generalized linear case

paper_content:

We consider structured multi-armed bandit problems based on the Generalized Linear Model (GLM) framework of statistics. For these bandits, we propose a new algorithm, called GLM-UCB. We derive finite time, high probability bounds on the regret of the algorithm, extending previous analyses developed for the linear bandits to the non-linear case. The analysis highlights a key difficulty in generalizing linear bandit algorithms to the non-linear case, which is solved in GLM-UCB by focusing on the reward space rather than on the parameter space. Moreover, as the actual effectiveness of current parameterized bandit algorithms is often poor in practice, we provide a tuning method based on asymptotic arguments, which leads to significantly better practical performance. We present two numerical experiments on real-world data that illustrate the potential of the GLM-UCB approach.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: A contextual-bandit approach to personalized news article recommendation

paper_content:

Personalized web services strive to adapt their services (advertisements, news articles, etc.) to individual users by making use of both content and user information. Despite a few recent advances, this problem remains challenging for at least two reasons. First, web service is featured with dynamically changing pools of content, rendering traditional collaborative filtering methods inapplicable. Second, the scale of most web services of practical interest calls for solutions that are both fast in learning and computation. In this work, we model personalized recommendation of news articles as a contextual bandit problem, a principled approach in which a learning algorithm sequentially selects articles to serve users based on contextual information about the users and articles, while simultaneously adapting its article-selection strategy based on user-click feedback to maximize total user clicks. The contributions of this work are three-fold. First, we propose a new, general contextual bandit algorithm that is computationally efficient and well motivated from learning theory. Second, we argue that any bandit algorithm can be reliably evaluated offline using previously recorded random traffic. Finally, using this offline evaluation method, we successfully applied our new algorithm to a Yahoo! Front Page Today Module dataset containing over 33 million events. Results showed a 12.5% click lift compared to a standard context-free bandit algorithm, and the advantage becomes even greater when data gets more scarce.
---
paper_title: Using Confidence Bounds for Exploitation-Exploration Trade-offs

paper_content:

We show how a standard tool from statistics --- namely confidence bounds --- can be used to elegantly deal with situations which exhibit an exploitation-exploration trade-off. Our technique for designing and analyzing algorithms for such situations is general and can be applied when an algorithm has to make exploitation-versus-exploration decisions based on uncertain information provided by a random process. We apply our technique to two models with such an exploitation-exploration trade-off. For the adversarial bandit problem with shifting our new algorithm suffers only O((ST)1/2) regret with high probability over T trials with S shifts. Such a regret bound was previously known only in expectation. The second model we consider is associative reinforcement learning with linear value functions. For this model our technique improves the regret from O(T3/4) to O(T1/2).
---
paper_title: Linearly Parameterized Bandits

paper_content:

We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an $r$-dimensional random vector $\mathbf{Z} \in \mathbb{R}^r$, where $r \geq 2$. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order $\Theta(r \sqrt{T})$, by establishing a lower bound for an arbitrary policy, and showing that a matching upper bound is obtained through a policy that alternates between exploration and exploitation phases. The phase-based policy is also shown to be effective if the set of arms satisfies a strong convexity condition. For the case of a general set of arms, we describe a near-optimal policy whose regret and Bayes risk admit upper bounds of the form $O(r \sqrt{T} \log^{3/2} T)$.
---
paper_title: Improving Online Marketing Experiments with Drifting Multi-armed Bandits

paper_content:

Restless bandits model the exploration vs. exploitation trade-off in a changing (non-stationary) world. Restless ::: ::: bandits have been studied in both the context of continuously-changing (drifting) and change-point (sudden) ::: ::: restlessness. In this work, we study specific classes of drifting restless bandits selected for their relevance to ::: ::: modelling an online website optimization process. The contribution in this work is a simple, feasible weighted ::: ::: least squares technique capable of utilizing contextual arm parameters while considering the parameter space ::: ::: drifting non-stationary within reasonable bounds. We produce a reference implementation, then evaluate and ::: ::: compare its performance in several different true world states, finding experimentally that performance is ::: ::: robust to time drifting factors similar to those seen in many real world cases.
---
paper_title: From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning

paper_content:

This work covers several aspects of the optimism in the face of uncertainty principle applied to large scale optimization problems under finite numerical budget. The initial motivation for the research reported here originated from the empirical success of the so-called Monte-Carlo Tree Search method popularized in computer-go and further extended to many other games as well as optimization and planning problems. Our objective is to contribute to the development of theoretical foundations of the field by characterizing the complexity of the underlying optimization problems and designing efficient algorithms with performance guarantees. The main idea presented here is that it is possible to decompose a complex decision making problem (such as an optimization problem in a large search space) into a sequence of elementary decisions, where each decision of the sequence is solved using a (stochastic) multi-armed bandit (simple mathematical model for decision making in stochastic environments). This so-called hierarchical bandit approach (where the reward observed by a bandit in the hierarchy is itself the return of another bandit at a deeper level) possesses the nice feature of starting the exploration by a quasi-uniform sampling of the space and then focusing progressively on the most promising area, at different scales, according to the evaluations observed so far, and eventually performing a local search around the global optima of the function. The performance of the method is assessed in terms of the optimality of the returned solution as a function of the number of function evaluations. Our main contribution to the field of function optimization is a class of hierarchical optimistic algorithms designed for general search spaces (such as metric spaces, trees, graphs, Euclidean spaces, ...) with different algorithmic instantiations depending on whether the evaluations are noisy or noiseless and whether some measure of the ''smoothness'' of the function is known or unknown. The performance of the algorithms depend on the local behavior of the function around its global optima expressed in terms of the quantity of near-optimal states measured with some metric. If this local smoothness of the function is known then one can design very efficient optimization algorithms (with convergence rate independent of the space dimension), and when it is not known, we can build adaptive techniques that can, in some cases, perform almost as well as when it is known.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: An Empirical Evaluation of Thompson Sampling

paper_content:

Thompson sampling is one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly unpopular in the literature. We present here some empirical results using Thompson sampling on simulated and real data, and show that it is highly competitive. And since this heuristic is very easy to implement, we argue that it should be part of the standard baselines to compare against.
---
paper_title: The use of Thompson sampling to increase estimation precision.

paper_content:

In this article, we consider a sequential sampling scheme for efficient estimation of the difference between the means of two independent treatments when the population variances are unequal across groups. The sampling scheme proposed is based on a solution to bandit problems called Thompson sampling. While this approach is most often used to maximize the cumulative payoff over competing treatments, we show that the same method can also be used to balance exploration and exploitation when the aim of the experimenter is to efficiently increase estimation precision. We introduce this novel design optimization method and, by simulation, show its effectiveness.
---
paper_title: Hierarchical Exploration for Accelerating Contextual Bandits

paper_content:

Contextual bandit learning is an increasingly popular approach to optimizing recommender systems via user feedback, but can be slow to converge in practice due to the need for exploring a large feature space. In this paper, we propose a coarse-to-fine hierarchical approach for encoding prior knowledge that drastically reduces the amount of exploration required. Intuitively, user preferences can be reasonably embedded in a coarse low-dimensional feature space that can be explored efficiently, requiring exploration in the high-dimensional space only as necessary. We introduce a bandit algorithm that explores within this coarse-to-fine spectrum, and prove performance guarantees that depend on how well the coarse space captures the user's preferences. We demonstrate substantial improvement over conventional bandit algorithms through extensive simulation as well as a live user study in the setting of personalized news recommendation.
---
paper_title: A Neural Networks Committee for the Contextual Bandit Problem

paper_content:

This paper presents a new contextual bandit algorithm, NeuralBandit, which does not need hypothesis on stationarity of contexts and rewards. Several neural networks are trained to modelize the value of rewards knowing the context. Two variants, based on multi-experts approach, are proposed to choose online the parameters of multi-layer perceptrons. The proposed algorithms are successfully tested on a large dataset with and without stationarity of rewards.
---
paper_title: Efficient bandit algorithms for online multiclass prediction

paper_content:

This paper introduces the Banditron, a variant of the Perceptron [Rosenblatt, 1958], for the multiclass bandit setting. The multiclass bandit setting models a wide range of practical supervised learning applications where the learner only receives partial feedback (referred to as "bandit" feedback, in the spirit of multi-armed bandit models) with respect to the true label (e.g. in many web applications users often only provide positive "click" feedback which does not necessarily fully disclose a true label). The Banditron has the ability to learn in a multiclass classification setting with the "bandit" feedback which only reveals whether or not the prediction made by the algorithm was correct or not (but does not necessarily reveal the true label). We provide (relative) mistake bounds which show how the Banditron enjoys favorable performance, and our experiments demonstrate the practicality of the algorithm. Furthermore, this paper pays close attention to the important special case when the data is linearly separable --- a problem which has been exhaustively studied in the full information setting yet is novel in the bandit setting.
---
paper_title: Efficient Optimal Learning for Contextual Bandits

paper_content:

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.
---
paper_title: Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

paper_content:

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K actions in response to the observed context, and observes the reward only for that action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only O(√KT) oracle calls across all T rounds. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We conduct a proof-of-concept experiment which demonstrates the excellent computational and statistical performance of (an online variant of) our algorithm relative to several strong baselines.
---
paper_title: Learning and Planning in Structured Worlds

paper_content:

This thesis is concerned with the problem of how to make decisions in an uncertain world. We use a model of uncertainty based on Markov decision problems, and develop a number of algorithms for decision-making both for the planning problem, in which the model is known in advance, and for the reinforcement learning problem in which the decision-making agent does not know the model and must learn to make good decisions by trial and error. ::: The basis for much of this work is the use of structural representations of problems. If a problem is represented in a structured way we can compute or learn plans that take advantage of this structure for computational gains. This is because the structure allows us to perform abstraction. Rather than reasoning about each situation in which a decision must be made individually, abstraction allows us to group situations together and reason about a whole set of them in a single step. Our approach to abstraction has the additional advantage that we can dynamically change the level of abstraction, splitting a group of situations in two if they need to be reasoned about separately to find an acceptable plan, or merging two groups together if they no longer need to be distinguished. We present two planning algorithms and one learning algorithm that use this approach. ::: A second idea we present in this thesis is a novel approach to the exploration problem in reinforcement learning. The problem is to select actions to perform given that we would like good performance now and in the future. We can select the current best action to perform, but this may prevent us from discovering that another action is better, or we can take an exploratory action, but we risk performing poorly now as a result. Our Bayesian approach makes this tradeoff explicit by representing our uncertainty about the values of states and using this measure of uncertainty to estimate the value of the information we could gain by performing each action. We present both model-free and model-based reinforcement learning algorithms that make use of this exploration technique. ::: Finally, we show how these ideas fit together to produce a reinforcement learning algorithm that uses structure to represent both the problem being solved and the plan it learns, and that selects actions to perform in order to learn using our Bayesian approach to exploration.
---
paper_title: On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems

paper_content:

Multi-armed bandit problems are considered as a paradigm of the trade-off between exploring the environment to find profitable actions and exploiting what is already known. In the stationary case, the distributions of the rewards do not change in time, Upper-Confidence Bound (UCB) policies have been shown to be rate optimal. A challenging variant of the MABP is the non-stationary bandit problem where the gambler must decide which arm to play while facing the possibility of a changing environment. In this paper, we consider the situation where the distributions of rewards remain constant over epochs and change at unknown time instants. We analyze two algorithms: the discounted UCB and the sliding-window UCB. We establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played. For that purpose, we derive a Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor.
---
paper_title: Integrated Architectures for Learning, Planning, and Reacting Based on Approximating Dynamic Programming

paper_content:

This paper extends previous work with Dyna, a class of architectures for intelligent systems based on approximating dynamic programming methods. Dyna architectures integrate trial-and-error (reinforcement) learning and execution-time planning into a single process operating alternately on the world and on a learned model of the world. In this paper, I present and show results for two Dyna architectures. The Dyna-PI architecture is based on dynamic programming's policy iteration method and can be related to existing AI ideas such as evaluation functions and universal plans (reactive systems). Using a navigation task, results are shown for a simple Dyna-PI system that simultaneously learns by trial and error, learns a world model, and plans optimal routes using the evolving world model. The Dyna-Q architecture is based on Watkins's Q-learning, a new kind of reinforcement learning. Dyna-Q uses a less familiar set of data structures than does Dyna-PI, but is arguably simpler to implement and use. We show that Dyna-Q architectures are easy to adapt for use in changing environments.
---
paper_title: On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems

paper_content:

Multi-armed bandit problems are considered as a paradigm of the trade-off between exploring the environment to find profitable actions and exploiting what is already known. In the stationary case, the distributions of the rewards do not change in time, Upper-Confidence Bound (UCB) policies have been shown to be rate optimal. A challenging variant of the MABP is the non-stationary bandit problem where the gambler must decide which arm to play while facing the possibility of a changing environment. In this paper, we consider the situation where the distributions of rewards remain constant over epochs and change at unknown time instants. We analyze two algorithms: the discounted UCB and the sliding-window UCB. We establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played. For that purpose, we derive a Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor.
---
paper_title: Bandit Based Monte-Carlo Planning

paper_content:

For large state-space Markovian Decision Problems Monte-Carlo planning is one of the few viable approaches to find near-optimal solutions. In this paper we introduce a new algorithm, UCT, that applies bandit ideas to guide Monte-Carlo planning. In finite-horizon or discounted MDPs the algorithm is shown to be consistent and finite sample bounds are derived on the estimation error due to sampling. Experimental results show that in several domains, UCT is significantly more efficient than its alternatives.
---
paper_title: On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems

paper_content:

Multi-armed bandit problems are considered as a paradigm of the trade-off between exploring the environment to find profitable actions and exploiting what is already known. In the stationary case, the distributions of the rewards do not change in time, Upper-Confidence Bound (UCB) policies have been shown to be rate optimal. A challenging variant of the MABP is the non-stationary bandit problem where the gambler must decide which arm to play while facing the possibility of a changing environment. In this paper, we consider the situation where the distributions of rewards remain constant over epochs and change at unknown time instants. We analyze two algorithms: the discounted UCB and the sliding-window UCB. We establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played. For that purpose, we derive a Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor.
---
paper_title: The nonstochastic multiarmed bandit problem

paper_content:

In the multi-armed bandit problem, a gambler must decide which arm of non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to nd the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate . We show by a matching lower bound that this is best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of strategies then our algorithm approaches the per-round payoff of the strategy at the rate . Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate
---
paper_title: Improving Online Marketing Experiments with Drifting Multi-armed Bandits

paper_content:

Restless bandits model the exploration vs. exploitation trade-off in a changing (non-stationary) world. Restless ::: ::: bandits have been studied in both the context of continuously-changing (drifting) and change-point (sudden) ::: ::: restlessness. In this work, we study specific classes of drifting restless bandits selected for their relevance to ::: ::: modelling an online website optimization process. The contribution in this work is a simple, feasible weighted ::: ::: least squares technique capable of utilizing contextual arm parameters while considering the parameter space ::: ::: drifting non-stationary within reasonable bounds. We produce a reference implementation, then evaluate and ::: ::: compare its performance in several different true world states, finding experimentally that performance is ::: ::: robust to time drifting factors similar to those seen in many real world cases.
---
paper_title: Sub-sampling for Multi-armed Bandits

paper_content:

The stochastic multi-armed bandit problem is a popular model of the exploration/exploitation trade-off in sequential decision problems. We introduce a novel algorithm that is based on sub-sampling. Despite its simplicity, we show that the algorithm demonstrates excellent empirical performances against state-of-the-art algorithms, including Thompson sampling and KL-UCB. The algorithm is very flexible, it does need to know a set of reward distributions in advance nor the range of the rewards. It is not restricted to Bernoulli distributions and is also invariant under rescaling of the rewards. We provide a detailed experimental study comparing the algorithm to the state of the art, the main intuition that explains the striking results, and conclude with a finite-time regret analysis for this algorithm in the simplified two-arm bandit setting.
---
paper_title: Disappointment in Decision Making Under Uncertainty

paper_content:

Decision analysis requires that two equally desirable consequences should have the same utility and vice versa. Most analyses of financial decision making presume that two consequences with the same dollar outcome will be equally preferred However, winning the top prize of $10,000 in a lottery may leave one much happier than receiving $10,000 as the lowest prize in a lottery. This paper explores the implications of disappointment, a psychological reaction caused by comparing the actual outcome of a lottery to one's prior expectations, for decision making under uncertainty. Explicit recognition that decision makers may be paying a premium to avoid potential disappointment provides an interpretation for some known behavioral paradoxes, and suggests that decision makers may be sensitive to the manner in which a lottery is resolved. The concept of disappointment is integrated into utility theory in a prescriptive model.
---
paper_title: Detecting changes in signals and systems - A survey

paper_content:

Abstract The purpose of this paper is the presentation of a tentative general framework for change detection in signals and systems. It is based upon a non-exhaustive survey of available methods. The main emphasis is placed upon statistical (parametric) methods for detection, which are presented according to the increasing order of complexity of the change problem. Another noticeable feature is the joint presentation of two commonly disconnected aspects, namely the generation of the signals to be monitored and the design of statistical decision rules.
---
paper_title: Multi-armed Bandit, Dynamic Environments and Meta-Bandits

paper_content:

This paper presents the Adapt-EvE algorithm, extending the UCBT online learning algorithm (Auer et al. 2002) to abruptly changing environments. Adapt-EvE features an adaptive change-point detection test based on Page-Hinkley statistics, and two alternative xtra-exploration procedures respectively based on smooth-restart and Meta-Bandits.
---
paper_title: Finite-time Analysis of the Multiarmed Bandit Problem

paper_content:

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
---
paper_title: Sub-sampling for Multi-armed Bandits

paper_content:

The stochastic multi-armed bandit problem is a popular model of the exploration/exploitation trade-off in sequential decision problems. We introduce a novel algorithm that is based on sub-sampling. Despite its simplicity, we show that the algorithm demonstrates excellent empirical performances against state-of-the-art algorithms, including Thompson sampling and KL-UCB. The algorithm is very flexible, it does need to know a set of reward distributions in advance nor the range of the rewards. It is not restricted to Bernoulli distributions and is also invariant under rescaling of the rewards. We provide a detailed experimental study comparing the algorithm to the state of the art, the main intuition that explains the striking results, and conclude with a finite-time regret analysis for this algorithm in the simplified two-arm bandit setting.
---
paper_title: The nonstochastic multiarmed bandit problem

paper_content:

In the multi-armed bandit problem, a gambler must decide which arm of non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to nd the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate . We show by a matching lower bound that this is best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of strategies then our algorithm approaches the per-round payoff of the strategy at the rate . Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate
---
paper_title: EXP3 with drift detection for the switching bandit problem

paper_content:

The multi-armed bandit is a model of exploration and exploitation, where one must select, within a finite set of arms, the one which maximizes the cumulative reward up to the time horizon T. For the adversarial multi-armed bandit problem, where the sequence of rewards is chosen by an oblivious adversary, the notion of best arm during the time horizon is too restrictive for applications such as ad-serving, where the best ad could change during time range. In this paper, we consider a variant of the adversarial multi-armed bandit problem, where the time horizon is divided into unknown time periods within which rewards are drawn from stochastic distributions. During each time period, there is an optimal arm which may be different from the optimal arm at the previous time period. We present an algorithm taking advantage of the constant exploration of EXP3 to detect when the best arm changes. Its analysis shows that on a run divided into N periods where the best arm changes, the proposed algorithms achieves a regret in O(N √T log T).
---
paper_title: Disappointment in Decision Making Under Uncertainty

paper_content:

Decision analysis requires that two equally desirable consequences should have the same utility and vice versa. Most analyses of financial decision making presume that two consequences with the same dollar outcome will be equally preferred However, winning the top prize of $10,000 in a lottery may leave one much happier than receiving $10,000 as the lowest prize in a lottery. This paper explores the implications of disappointment, a psychological reaction caused by comparing the actual outcome of a lottery to one's prior expectations, for decision making under uncertainty. Explicit recognition that decision makers may be paying a premium to avoid potential disappointment provides an interpretation for some known behavioral paradoxes, and suggests that decision makers may be sensitive to the manner in which a lottery is resolved. The concept of disappointment is integrated into utility theory in a prescriptive model.
---
paper_title: Detecting changes in signals and systems - A survey

paper_content:

Abstract The purpose of this paper is the presentation of a tentative general framework for change detection in signals and systems. It is based upon a non-exhaustive survey of available methods. The main emphasis is placed upon statistical (parametric) methods for detection, which are presented according to the increasing order of complexity of the change problem. Another noticeable feature is the joint presentation of two commonly disconnected aspects, namely the generation of the signals to be monitored and the design of statistical decision rules.
---
paper_title: Multi-armed Bandit, Dynamic Environments and Meta-Bandits

paper_content:

This paper presents the Adapt-EvE algorithm, extending the UCBT online learning algorithm (Auer et al. 2002) to abruptly changing environments. Adapt-EvE features an adaptive change-point detection test based on Page-Hinkley statistics, and two alternative xtra-exploration procedures respectively based on smooth-restart and Meta-Bandits.
---
paper_title: A contextual-bandit approach to personalized news article recommendation

paper_content:

Personalized web services strive to adapt their services (advertisements, news articles, etc.) to individual users by making use of both content and user information. Despite a few recent advances, this problem remains challenging for at least two reasons. First, web service is featured with dynamically changing pools of content, rendering traditional collaborative filtering methods inapplicable. Second, the scale of most web services of practical interest calls for solutions that are both fast in learning and computation. In this work, we model personalized recommendation of news articles as a contextual bandit problem, a principled approach in which a learning algorithm sequentially selects articles to serve users based on contextual information about the users and articles, while simultaneously adapting its article-selection strategy based on user-click feedback to maximize total user clicks. The contributions of this work are three-fold. First, we propose a new, general contextual bandit algorithm that is computationally efficient and well motivated from learning theory. Second, we argue that any bandit algorithm can be reliably evaluated offline using previously recorded random traffic. Finally, using this offline evaluation method, we successfully applied our new algorithm to a Yahoo! Front Page Today Module dataset containing over 33 million events. Results showed a 12.5% click lift compared to a standard context-free bandit algorithm, and the advantage becomes even greater when data gets more scarce.
---
paper_title: On bayesian upper confidence bounds for bandit problems

paper_content:

Stochastic bandit problems have been analyzed from two dierent perspectives: a frequentist view, where the parameter is a deterministic unknown quantity, and a Bayesian approach, where the parameter is drawn from a prior distribution. We show in this paper that methods derived from this second perspective prove optimal when evaluated using the frequentist cumulated regret as a measure of performance. We give a general formulation for a class of Bayesian index policies that rely on quantiles of the posterior distribution. For binary bandits, we prove that the corresponding algorithm, termed BayesUCB, satisfies finite-time regret bounds that imply its asymptotic optimality. More generally, Bayes-UCB appears as an unifying framework for several variants of the UCB algorithm addressing dierent
---
paper_title: A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

paper_content:

We consider a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit problem in the case of distributions with finite supports (not necessarily known beforehand), whose asymptotic regret matches the lower bound of \cite{Burnetas96}. Our contribution is to provide a finite-time analysis of this algorithm; we get bounds whose main terms are smaller than the ones of previously known algorithms with finite-time analyses (like UCB-type algorithms).
---
paper_title: Solving non-stationary bandit problems by random sampling from sibling Kalman filters

paper_content:

The multi-armed bandit problem is a classical optimization problem where an agent sequentially pulls one of multiple arms attached to a gambling machine, with each pull resulting in a random reward. The reward distributions are unknown, and thus, one must balance between exploiting existing knowledge about the arms, and obtaining new information. Dynamically changing (non-stationary) bandit problems are particularly challenging because each change of the reward distributions may progressively degrade the performance of any fixed strategy. ::: ::: Although computationally intractable in many cases, Bayesian methods provide a standard for optimal decision making. This paper proposes a novel solution scheme for bandit problems with non-stationary normally distributed rewards. The scheme is inherently Bayesian in nature, yet avoids computational intractability by relying simply on updating the hyper parameters of sibling Kalman Filters, and on random sampling from these posteriors. Furthermore, it is able to track the better actions, thus supporting non-stationary bandit problems. ::: ::: Extensive experiments demonstrate that our scheme outperforms recently proposed bandit playing algorithms, not only in non-stationary environments, but in stationary environments also. Furthermore, our scheme is robust to inexact parameter settings. We thus believe that our methodology opens avenues for obtaining improved novel solutions.
---
paper_title: A two-armed bandit based scheme for accelerated decentralized learning

paper_content:

The two-armed bandit problem is a classical optimization problem where a decision maker sequentially pulls one of two arms attached to a gambling machine, with each pull resulting in a random reward. The reward distributions are unknown, and thus, one must balance between exploiting existing knowledge about the arms, and obtaining new information. Bandit problems are particularly fascinating because a large class of real world problems, including routing, QoS control, game playing, and resource allocation, can be solved in a decentralized manner when modeled as a system of interacting gambling machines. ::: ::: Although computationally intractable in many cases, Bayesian methods provide a standard for optimal decision making. This paper proposes a novel scheme for decentralized decision making based on the Goore Game in which each decision maker is inherently Bayesian in nature, yet avoids computational intractability by relying simply on updating the hyper parameters of sibling conjugate priors, and on random sampling from these posteriors. We further report theoretical results on the variance of the random rewards experienced by each individual decision maker. Based on these theoretical results, each decision maker is able to accelerate its own learning by taking advantage of the increasingly more reliable feedback that is obtained as exploration gradually turns into exploitation in bandit problem based learning. ::: ::: Extensive experiments demonstrate that the accelerated learning allows us to combine the benefits of conservative learning, which is high accuracy, with the benefits of hurried learning, which is fast convergence. In this manner, our scheme outperforms recently proposed Goore Game solution schemes, where one has to trade off accuracy with speed. We thus believe that our methodology opens avenues for improved performance in a number of applications of bandit based decentralized decision making.
---
paper_title: Continuum armed bandit problem of few variables in high dimensions

paper_content:

We consider the stochastic and adversarial settings of continuum armed bandits where the arms are indexed by [0,1]^d. The reward functions r:[0,1]^d ->R are assumed to intrinsically depend on at most k coordinate variables implying r(x_1,..,x_d) = g(x_{i_1},..,x_{i_k}) for distinct and unknown i_1,..,i_k from {1,..,d} and some locally Holder continuous g:[0,1]^k ->R with exponent 0<alpha<= 1. Firstly, assuming (i_1,..,i_k) to be fixed across time, we propose a simple modification of the CAB1 algorithm where we construct the discrete set of sampling points to obtain a bound of O(n^((alpha+k)/(2*alpha+k)) (log n)^((alpha)/(2*alpha+k)) C(k,d)) on the regret, with C(k,d) depending at most polynomially in k and sub-logarithmically in d. The construction is based on creating partitions of {1,..,d} into k disjoint subsets and is probabilistic, hence our result holds with high probability. Secondly we extend our results to also handle the more general case where (i_1,...,i_k) can change over time and derive regret bounds for the same.
---
paper_title: Multi-objective χ-Armed bandits

paper_content:

Many of the standard optimization algorithms focus on optimizing a single, scalar feedback signal. However, real-life optimization problems often require a simultaneous optimization of more than one objective. In this paper, we propose a multi-objective extension to the standard χ-armed bandit problem. As the feedback signal is now vector-valued, the goal of the agent is to sample actions in the Pareto dominating area of the objective space. Therefore, we propose the multi-objective Hierarchical Optimistic Optimization strategy that discretizes the continuous action space in relation to the Pareto optimal solutions obtained in the multi-objective objective space. We experimentally validate the approach on two well-known multi-objective test functions and a simulation of a real life application, the filling phase of a wet clutch. We demonstrate that the strategy allows to identify the Pareto front after just a few epochs and to sample accordingly. After learning, several multi-objective quality indicators indicate that the set of sampled solutions by the algorithm very closely approximates the Pareto front.
---
paper_title: On Two Continuum Armed Bandit Problems in High Dimensions

paper_content:

We consider the problem of continuum armed bandits where the arms are indexed by a compact subset of ?d$\mathbb {R}^{d}$. For large d, it is well known that mere smoothness assumptions on the reward functions lead to regret bounds that suffer from the curse of dimensionality. A typical way to tackle this in the literature has been to make further assumptions on the structure of reward functions. In this work we assume the reward functions to be intrinsically of low dimension k ? d and consider two models: (i) The reward functions depend on only an unknown subset of k coordinate variables and, (ii) a generalization of (i) where the reward functions depend on an unknown k dimensional subspace of ?d$\mathbb {R}^{d}$. By placing suitable assumptions on the smoothness of the rewards we derive randomized algorithms for both problems that achieve nearly optimal regret bounds in terms of the number of rounds n.
---
paper_title: Simple regret for infinitely many armed bandits

paper_content:

We consider a stochastic bandit problem with infinitely many arms. In this setting, the learner has no chance of trying all the arms even once and has to dedicate its limited number of samples only to a certain number of arms. All previous algorithms for this setting were designed for minimizing the cumulative regret of the learner. In this paper, we propose an algorithm aiming at minimizing the simple regret. As in the cumulative regret setting of infinitely many armed bandits, the rate of the simple regret will depend on a parameter β characterizing the distribution of the near-optimal arms. We prove that depending on β, our algorithm is minimax optimal either up to a multiplicative constant or up to a log(n) factor. We also provide extensions to several important cases: when β is unknown, in a natural setting where the near-optimal arms have a small variance, and in the case of unknown time horizon.
---
paper_title: On Hoeffding’s inequalities

paper_content:

In a celebrated work by Hoeffding [J. Amer. Statist. Assoc. 58 (1963) 13-30], several inequalities for tail probabilities of sums M n = X 1 + ... + X n of bounded independent random variables X j were proved. These inequalities had a considerable impact on the development of probability and statistics, and remained unimproved until 1995 when Talagrand [Inst. Hautes Etudes Sci. Publ. Math. 81 (1995a) 73-205] inserted certain missing factors in the bounds of two theorems. By similar factors, a third theorem was refined by Pinelis [Progress in Probability 43 (1998) 257-314] and refined (and extended) by me. In this article, I introduce a new type of inequality. Namely, I show that P{M n ≥ x} ≤ cP{S n ≥ x}, where c is an absolute constant and S n = e 1 + ... + e n is a sum of independent identically distributed Bernoulli random variables (a random variable is called Bernoulli if it assumes at most two values). The inequality holds for those x ∈ Ρ where the survival function x → P{S n ≥ x} has a jump down. For the remaining x the inequality still holds provided that the function between the adjacent jump points is interpolated linearly or log-linearly. If it is necessary, to estimate P{S n ≥ x} special bounds can be used for binomial probabilities. The results extend to martingales with bounded differences. It is apparent that Theorem 1.1 of this article is the most important. The inequalities have applications to measure concentration, leading to results of the type where, up to an absolute constant, the measure concentration is dominated by the concentration in a simplest appropriate model, such results will be considered elsewhere.
---
paper_title: Bandit Algorithms for Tree Search

paper_content:

Bandit based methods for tree search have recently gained popularity when applied to huge trees, e.g. in the game of go [6]. Their efficient exploration of the tree enables to return rapidly a good value, and improve precision if more time is provided. The UCT algorithm [8], a tree search method based on Upper Confidence Bounds (UCB) [2], is believed to adapt locally to the effective smoothness of the tree. However, we show that UCT is "over-optimistic" in some sense, leading to a worst-case regret that may be very poor. We propose alternative bandit algorithms for tree search. First, a modification of UCT using a confidence sequence that scales exponentially in the horizon depth is analyzed. We then consider Flat-UCB performed on the leaves and provide a finite regret bound with high probability. Then, we introduce and analyze a Bandit Algorithm for Smooth Trees (BAST) which takes into account actual smoothness of the rewards for performing efficient "cuts" of sub-optimal branches with high confidence. Finally, we present an incremental tree expansion which applies when the full tree is too big (possibly infinite) to be entirely represented and show that with high probability, only the optimal branches are indefinitely developed. We illustrate these methods on a global optimization problem of a continuous function, given noisy values.
---
paper_title: Modification of UCT with patterns in Monte-Carlo go

paper_content:

Algorithm UCB1 for multi-armed bandit problem has already been extended to Algorithm UCT (Upper bound Confidence for Tree) which works for minimax tree search. We have developed a Monte-Carlo Go program, MoGo, which is the first computer Go program using UCT. We explain our modification of UCT for Go application and also the intelligent random simulation with patterns which has improved significantly the performance of MoGo. UCT combined with pruning techniques for large Go board is discussed, as well as parallelization of UCT. MoGo is now a top level Go program on $9\times9$ and $13\times13$ Go boards.
---
paper_title: Online Optimization in X-Armed Bandits

paper_content:

We consider a generalization of stochastic bandit problems where the set of arms, X, is allowed to be a generic topological space. We constraint the mean-payoff function with a dissimilarity function over X in a way that is more general than Lipschitz. We construct an arm selection policy whose regret improves upon previous result for a large class of problems. In particular, our results imply that if X is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally Holder with a known exponent, then the expected regret is bounded up to a logarithmic factor by $\sqrt{n}$, i.e., the rate of the growth of the regret is independent of the dimension of the space. Moreover, we prove the minimax optimality of our algorithm for the class of mean-payoff functions we consider.
---
paper_title: Algorithms for adversarial bandit problems with multiple plays

paper_content:

Adversarial bandit problems studied by Auer et al. [4] are multi-armed bandit problems in which no stochastic assumption is made on the nature of the process generating the rewards for actions. In this paper, we extend their theories to the case where k(≥1) distinct actions are selected at each time step. As algorithms to solve our problem, we analyze an extension of Exp3 [4] and an application of a bandit online linear optimization algorithm [1] in addition to two existing algorithms (Exp3, ComBand [5]) in terms of time and space efficiency and the regret for the best fixed action set. The extension of Exp3, called Exp3.M, performs best with respect to all the measures: it runs in O(K(log k+1)) time and O(K) space, and suffers at most O(√kTK log(K/k)) regret, where K is the number of possible actions and T is the number of iterations. The upper bound of the regret we proved for Exp3.M is an extension of that proved by Auer et al. for Exp3.
---
paper_title: Learning diverse rankings with multi-armed bandits

paper_content:

Algorithms for learning to rank Web documents usually assume a document's relevance is independent of other documents. This leads to learned ranking functions that produce rankings with redundant results. In contrast, user studies have shown that diversity at high ranks is often preferred. We present two online learning algorithms that directly learn a diverse ranking of documents based on users' clicking behavior. We show that these algorithms minimize abandonment, or alternatively, maximize the probability that a relevant document is found in the top k positions of a ranking. Moreover, one of our algorithms asymptotically achieves optimal worst-case performance even if users' interests change.
---
paper_title: Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

paper_content:

A multi-armed bandit problem - or, simply, a bandit problem - is a sequential allocation problem defined by a set of actions. At each time step, a unit resource is allocated to an action and some observable payoff is obtained. The goal is to maximize the total payoff obtained in a sequence of allocations. The name bandit refers to the colloquial term for a slot machine (a "one-armed bandit" in American slang). In a casino, a sequential allocation problem is obtained when the player is facing many slot machines at once (a "multi-armed bandit"), and must repeatedly choose where to insert the next coin. Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the 1930s, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this book, the focus is on two extreme cases in which the analysis of regret is particularly simple and elegant: independent and identically distributed payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, it also analyzes some of the most important variants and extensions, such as the contextual bandit model. This monograph is an ideal reference for students and researchers with an interest in bandit problems.
---
paper_title: Online Learning with Switching Costs and Other Adaptive Adversaries

paper_content:

We study the power of different types of adaptive (nonoblivious) adversaries in the setting of prediction with expert advice, under both full-information and bandit feedback. We measure the player's performance using a new notion of regret, also known as policy regret, which better captures the adversary's adaptiveness to the player's behavior. In a setting where losses are allowed to drift, we characterize —in a nearly complete manner— the power of adaptive adversaries with bounded memories and switching costs. In particular, we show that with switching costs, the attainable rate with bandit feedback is Θ(T2/3). Interestingly, this rate is significantly worse than the Θ(√T) rate attainable with switching costs in the full-information case. Via a novel reduction from experts to bandits, we also show that a bounded memory adversary can force ****Θ(T2/3) regret even in the full information case, proving that switching costs are easier to control than bounded memory adversaries. Our lower bounds rely on a new stochastic adversary strategy that generates loss processes with strong dependencies.
---
paper_title: On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems

paper_content:

Multi-armed bandit problems are considered as a paradigm of the trade-off between exploring the environment to find profitable actions and exploiting what is already known. In the stationary case, the distributions of the rewards do not change in time, Upper-Confidence Bound (UCB) policies have been shown to be rate optimal. A challenging variant of the MABP is the non-stationary bandit problem where the gambler must decide which arm to play while facing the possibility of a changing environment. In this paper, we consider the situation where the distributions of rewards remain constant over epochs and change at unknown time instants. We analyze two algorithms: the discounted UCB and the sliding-window UCB. We establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played. For that purpose, we derive a Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor.
---

Title: A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit

Section 1: Introduction
Description 1: Introduce the concept of exploration versus exploitation and its applications in various fields including machine learning, artificial intelligence, and experiment design.

Section 2: Motivating Applications
Description 2: Discuss real-world applications that benefit from multi-armed bandit models, especially focusing on the medical trials scenario.

Section 3: The Multi-Armed Bandit Model
Description 3: Provide a detailed overview of the multi-armed bandit problem, explaining key concepts such as arms, payoffs, and the partial information nature of the problem.

Section 4: Considerations of Multi-Armed Bandits
Description 4: Examine different scenarios and considerations including best-arm identification and arm-to-arm comparisons.

Section 5: Measures of Regret
Description 5: Explain various regret measures used to evaluate bandit algorithms, including expected-expected regret, expected-payoff regret, and statistical regret.

Section 6: Variance and Bounds of Regret
Description 6: Discuss the importance of variance minimization and high-probability bounds in the context of regret in multi-armed bandit algorithms.

Section 7: Stationarity of the Problem
Description 7: Explore the challenges posed by non-stationary environments and variants of the bandit problem that address these issues.

Section 8: Feedback Delay
Description 8: Highlight the impact of feedback delay on multi-armed bandit algorithms and propose adjustments to handle delayed feedback.

Section 9: Algorithms for the Application of Multi-Armed Bandits
Description 9: Provide an in-depth survey of various algorithms, including Gittins index, ε-greedy strategies, UCB1, and Thompson sampling, among others.

Section 10: Complications of the Simple Stochastic Model
Description 10: Examine more complex variants of the bandit problem such as adversarial bandits, contextual bandits, and non-stationary bandits for ongoing experimentation.

Section 11: Contextual Bandits for Experiments with Covariates
Description 11: Discuss the incorporation of contextual information into bandit models and present related algorithms such as LinUCB and LinTS.

Section 12: Nonstationary Bandits for Ongoing Experimentation
Description 12: Detail algorithms and strategies for dealing with non-stationary environments in long-running experiments.

Section 13: Bandits with Multiple Plays
Description 13: Describe scenarios where multiple arms are played simultaneously, and present algorithms designed to address this variant of the bandit problem.

Section 14: State of the Theory and Future Work
Description 14: Summarize the current theoretical understanding of multi-armed bandit problems and identify areas for future research.