Venugopal V. Veeravalli

Conventional Multi-Armed Bandit (MAB) algorithms are designed for stationary environments, where the reward distributions associated with the arms do not change with time. In many applications, however, the environment is more accurately modeled as being non-stationary. In this work, piecewise stationary MAB (PS-MAB) environments are investigated, in which the reward distributions associated with a subset of the arms change at some change-points and remain stationary between change-points. Our focus is on the asymptotic analysis of PS-MABs, for which practical algorithms based on change detection have been previously proposed. Our goal is to modularize the design and analysis of such Detection Augmented Bandit (DAB) procedures. To this end, we first provide novel, improved performance lower bounds for PS-MABs. Then, we identify the requirements for stationary bandit algorithms and change detectors in a DAB procedure that are needed for the modularization. We assume that the rewards are sub-Gaussian. Under this assumption and a condition on the separation of the change-points, we show that the analysis of DAB procedures can indeed be modularized, so that the regret bounds can be obtained in a unified manner for various combinations of change detectors and bandit algorithms. Through this analysis, we develop new modular DAB procedures that are order-optimal. Finally, we showcase the practical effectiveness of our modular DAB approach in our experiments, studying its regret performance compared to other methods and investigating its detection capabilities.

State of the art methods for target tracking with sensor management (or controlled sensing) are model-based and are obtained through solutions to Partially Observable Markov Decision Process (POMDP) formulations. In this paper a Reinforcement Learning (RL) approach to the problem is explored for the setting where the motion model for the object/target to be tracked is unknown to the observer. It is assumed that the target dynamics are stationary in time, the state space and the observation space are discrete, and there is complete observability of the location of the target under certain (a priori unknown) sensor control actions. Then, a novel Markov Decision Process (MDP) rather than POMDP formulation is proposed for the tracking problem with controlled sensing, which is termed as Track-MDP. In contrast to the POMDP formulation, the Track-MDP formulation is amenable to an RL based solution. It is shown that the optimal policy for the Track-MDP formulation, which is approximated through RL, is guaranteed to track all significant target paths with certainty. The Track-MDP method is then compared with the optimal POMDP policy, and it is shown that the infinite horizon tracking reward of the optimal Track-MDP policy is the same as that of the optimal POMDP policy. In simulations it is demonstrated that Track-MDP based RL can lead to a policy that can track the target with high accuracy and superior energy efficiency.

A finite-horizon variant of the quickest change detection (QCD) problem that is of relevance to learning in non-stationary environments is studied. The metric characterizing false alarms is the probability of a false alarm occurring before the horizon ends. The metric that characterizes the delay is \emph{latency}, which is the smallest value such that the probability that detection delay exceeds this value is upper bounded to a predetermined latency level. The objective is to minimize the latency (at a given latency level), while maintaining a low false alarm probability. Under the pre-specified latency and false alarm levels, a universal lower bound on the latency, which any change detection procedure needs to satisfy, is derived. Change detectors are then developed, which are order-optimal in terms of the horizon. The case where the pre- and post-change distributions are known is considered first, and then the results are generalized to the non-parametric case when they are unknown except that they are sub-Gaussian with different means. Simulations are provided to validate the theoretical results.

The problem of quickest change detection is studied in the context of detecting an arbitrary unknown mean-shift in multiple independent Gaussian data streams. The James-Stein estimator is used in constructing detection schemes that exhibit strong detection performance both asymptotically and non-asymptotically. Our results indicate that utilizing the James-Stein estimator in the recently developed window-limited CuSum test constitutes a uniform improvement over its typical maximum likelihood variant. That is, the proposed James-Stein version achieves a smaller detection delay simultaneously for all possible post-change parameter values and every false alarm rate constraint, as long as the number of parallel data streams is greater than three. Additionally, an alternative detection procedure that utilizes the James-Stein estimator is shown to have asymptotic detection delay properties that compare favorably to existing tests. The second-order asymptotic detection delay term is reduced in a predefined low-dimensional subspace of the parameter space, while second-order asymptotic minimaxity is preserved. The results are verified in simulations, where the proposed schemes are shown to achieve smaller detection delays compared to existing alternatives, especially when the number of data streams is large.

Two-sample hypothesis testing is a common practice in many fields of science, where the goal is to identify whether a set of observations and a set of training data are drawn from the same distribution. Traditionally, this is achieved using parametric and non-parametric frequentist tests, such as the Generalized Likelihood Ratio (GLR) test. However, these tests are not optimal in a Neyman-Pearson sense, especially when the number of observations and training samples are finite. Therefore, in this work, we study a parametric Bayesian test, called the Uncertain Likelihood Ratio (ULR) test, and compare its performance to the traditional GLR test. We establish that the ULR test is the optimal test for any number of samples when the parameters of the likelihood models are drawn from the true prior distribution. We then study an asymptotic form of the ULR test statistic and compare it against the GLR test statistic. As a byproduct of this analysis, we establish a new asymptotic optimality property for the GLR test when the parameters of the likelihood models are drawn from the Jeffreys prior. Furthermore, we analyze conditions under which the ULR test outperforms the GLR test, and include a numerical study to validate the results.

We study the problem of Non-Stationary Reinforcement Learning (NS-RL) without prior knowledge about the system's non-stationarity. A state-of-the-art, black-box algorithm, known as MASTER, is considered, with a focus on identifying the conditions under which it can achieve its stated goals. Specifically, we prove that MASTER's non-stationarity detection mechanism is not triggered for practical choices of horizon, leading to performance akin to a random restarting algorithm. Moreover, we show that the regret bound for MASTER, while being order optimal, stays above the worst-case linear regret until unreasonably large values of the horizon. To validate these observations, MASTER is tested for the special case of piecewise stationary multi-armed bandits, along with methods that employ random restarting, and others that use quickest change detection to restart. A simple, order optimal random restarting algorithm, that has prior knowledge of the non-stationarity is proposed as a baseline. The behavior of the MASTER algorithm is validated in simulations, and it is shown that methods employing quickest change detection are more robust and consistently outperform MASTER and other random restarting approaches.

The problem of quickest change detection in a sequence of independent observations is considered. The pre-change distribution is assumed to be known, while the post-change distribution is unknown. Two tests based on post-change density estimation are developed for this problem, the window-limited non-parametric generalized likelihood ratio (NGLR) CuSum test and the non-parametric window-limited adaptive (NWLA) CuSum test. Both tests do not assume any knowledge of the post-change distribution, except that the post-change density satisfies certain smoothness conditions that allows for efficient non-parametric estimation; also, they do not require any pre-collected post-change training samples. Under certain convergence conditions on the density estimator, it is shown that both tests are first-order asymptotically optimal, as the false alarm rate goes to zero. The analysis is validated through numerical results, where both tests are compared with baseline tests that have distributional knowledge.

In the problem of quickest change detection (QCD), a change occurs at some unknown time in the distribution of a sequence of independent observations. This work studies a QCD problem where the change is either a bad change, which we aim to detect, or a confusing change, which is not of our interest. Our objective is to detect a bad change as quickly as possible while avoiding raising a false alarm for pre-change or a confusing change. We identify a specific set of pre-change, bad change, and confusing change distributions that pose challenges beyond the capabilities of standard Cumulative Sum (CuSum) procedures. Proposing novel CuSum-based detection procedures, S-CuSum and J-CuSum, leveraging two CuSum statistics, we offer solutions applicable across all kinds of pre-change, bad change, and confusing change distributions. For both S-CuSum and J-CuSum, we provide analytical performance guarantees and validate them by numerical results. Furthermore, both procedures are computationally efficient as they only require simple recursive updates.

Distributed and decentralized optimization problems, such as those encountered in federated learning, often suffer from a communication bottleneck at compute nodes when a large number of messages get aggregated. To address this communication bottleneck, compressed Stochastic Gradient Descent (SGD) algorithms have been proposed. Most existing compressed SGD algorithms use non-adaptive step-sizes (constant or diminishing) that depend on unknown system parameters to provide theoretical convergence guarantees, with the step-sizes being fine-tuned in practice to obtain good empirical performance for a given dataset and learning model. Such fine-tuning might be impractical in many scenarios. Therefore, it is of interest to study compressed SGD using adaptive step-sizes that do not depend on unknown system parameters. Motivated by prior work that employs adaptive step-sizes for uncompressed SGD, we develop an Armijo rule based step-size selection method for compressed SGD with feedback. In particular, we first motivate a novel scaling technique for Gradient Descent (GD) with Armijo step-size search, based on which we develop an Armijo step-search method with scaling for the descent step of the compressed SGD algorithm with memory feedback. We then establish that our algorithm has order-optimal convergence rates for convex-smooth and strong convex-smooth objectives under an interpolation condition , and for non-convex objectives under a strong growth condition . Experiments comparing our proposed algorithm with state-of-the-art compressed SGD methods with memory feedback demonstrate a notable improvement in terms of training loss across various levels of compression.

We study the problem of distributed and rate-adaptive feature compression for linear regression. A set of distributed sensors collect disjoint features of regressor data. A fusion center is assumed to contain a pretrained linear regression model, trained on a dataset of the entire uncompressed data. At inference time, the sensors compress their observations and send them to the fusion center through communication-constrained channels, whose rates can change with time. Our goal is to design a feature compression {scheme} that can adapt to the varying communication constraints, while maximizing the inference performance at the fusion center. We first obtain the form of optimal quantizers assuming knowledge of underlying regressor data distribution. Under a practically reasonable approximation, we then propose a distributed compression scheme which works by quantizing a one-dimensional projection of the sensor data. We also propose a simple adaptive scheme for handling changes in communication constraints. We demonstrate the effectiveness of the distributed adaptive compression scheme through simulated experiments.