Search

We consider a sequential adaptive allocation problem which is formulated as a traditional two armed bandit problem but with one important modification: at each time step t, before selecting which arm to pull, the decision maker has access to a random variable Xt which provides information on the reward in each arm. Performance is measured as the fraction of time an inferior arm (generating lower mean reward) is pulled. We derive a minimax lower bound that proves that in the absence of sufficient statistical “diversity” in the distribution of the covariate X, a property that we shall refer to as lack of persistent excitation, no policy can improve on the best achievable performance in the traditional bandit problem without side information. [ABSTRACT FROM AUTHOR]

Examines the mathematical aspects of learning unknown mappings with Mixture of Experts Model (MEM). Discussion on the effects of MEM in neutral networks; Discussion on stochastic error in the context of learning from independent and identically distributed examples; Limiting factors for the error.

Given a finite number of stochastic systems, the goal of our problem is to dynamically allocate a finite sampling budget to maximize the probability of selecting the "best" system. Systems are encoded with the probability distributions that govern sample observations, which are unknown and only assumed to belong to a broad family of distributions that need not admit any parametric representation. The best system is defined as the one with the highest quantile value. The objective of maximizing the probability of selecting this best system is not analytically tractable. In lieu of that, we use the rate function for the probability of error relying on large deviations theory. Our point of departure is an algorithm that naively combines sequential estimation and myopic optimization. This algorithm is shown to be asymptotically optimal; however, it exhibits poor finite-time performance and does not lead itself to implementation in settings with a large number of systems. To address this, we propose practically implementable variants that retain the asymptotic performance of the former while dramatically improving its finite-time performance. [ABSTRACT FROM AUTHOR]