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 Xtwhich 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.

We consider the problem of recovering edges of an image from noisy tomographic data. The original image is assumed to have a discontinuity jump (edge) along the boundary of a compact convex set. The Radon transform of the image is observed with noise, and the problem is to estimate the edge. We develop an estimation procedure which is based on recovering the support function of the edge. It is shown that the proposed estimator is nearly optimal in order in a minimax sense. Numerical examples illustrate reasonable practical behavior of the estimation procedure.

The paper deals with estimating the transfer functions of stable linear time-invariant systems under stochastic assumptions. We adopt a nonparametric minimax approach for measuring the estimation accuracy. The quality of an estimator is measured by its worst case error over a family of transfer functions. The families with polynomially and exponentially decaying impulse response sequences are considered. We establish nonasymptotic upper bounds on the accuracy of the least squares estimator for finite impulse response approximation. It is shown that the attainable estimation accuracy is determined essentially by the rate at which the "true" impulse response tends to zero. Lower bounds on the estimation accuracy are presented. An adaptive estimator which does not exploit any a priori information about the "true" system, is developed.

The paper is devoted to spatial adaptive estimation of signals satisfying linear differential inequalities with an unknown differential operator of a given order. The classes of signals under consideration cover a wide variety of classes common to nonparametric regression. In particular, they contain the signals whose parameters of smoothness are not uniformly bounded, even locally. We develop an estimator which is optimal in order over a wide range of the classes and "discrete" global accuracy measures.