More Like this

1. On Distributed Multi-Player Multiarmed Bandit Problems in Abruptly Changing Environment

   https://doi.org/10.1109/CDC.2018.8619603  

   Wei, Lai; Srivastava, Vaibhav (December 2018, IEEE Conference on Decision and Control)

   We study the multi-player stochastic multiarmed bandit (MAB) problem in an abruptly changing environment. We consider a collision model in which a player receives reward at an arm if it is the only player to select the arm. We design two novel algorithms, namely, Round-Robin Sliding-Window Upper Confidence Bound# (RR-SW-UCB#), and the Sliding- Window Distributed Learning with Prioritization (SW-DLP). We rigorously analyze these algorithms and show that the expected cumulative group regret for these algorithms is upper bounded by sublinear functions of time, i.e., the time average of the regret asymptotically converges to zero. We complement our analytic results with numerical illustrations. 

   more » « less
2. Dynamic Regret of Policy Optimization in Non-Stationary Environments

   Fei, Yingjie; Yang, Zhuoran; Wang, Zhaoran; Xie, Qiaomin (December 2020, Advances in neural information processing systems)

   null (Ed.)

   We consider reinforcement learning (RL) in episodic MDPs with adversarial full-information reward feedback and unknown fixed transition kernels. We propose two model-free policy optimization algorithms, POWER and POWER++, and establish guarantees for their dynamic regret. Compared with the classical notion of static regret, dynamic regret is a stronger notion as it explicitly accounts for the non-stationarity of environments. The dynamic regret attained by the proposed algorithms interpolates between different regimes of non-stationarity, and moreover satisfies a notion of adaptive (near-)optimality, in the sense that it matches the (near-)optimal static regret under slow-changing environments. The dynamic regret bound features two components, one arising from exploration, which deals with the uncertainty of transition kernels, and the other arising from adaptation, which deals with non-stationary environments. Specifically, we show that POWER++ improves over POWER on the second component of the dynamic regret by actively adapting to non-stationarity through prediction. To the best of our knowledge, our work is the first dynamic regret analysis of model-free RL algorithms in non-stationary environments. 

   more » « less
3. Link rate selection using constrained Thompson sampling

   Gupta, H; Eryilmaz, A; Srikant, R (April 2019, IEEE INFOCOM)

   We consider the optimal link rate selection problem in time-varying wireless channels with unknown channel statistics. The aim of optimal link rate selection is to transmit at the optimal rate at each time slot in order to maximize the expected throughput of the wireless channel/link or equivalently minimize the expected regret. Lack of information about channel state or channel statistics necessitates the use of online/sequential learning algorithms to determine the optimal rate. We present an algorithm called CoTS - Constrained Thompson sampling algorithm which improves upon the current state-of-the-art, is fast and is also general in the sense that it can handle several different constraints in the problem with the same algorithm. We also prove an asymptotic lower bound on the expected regret and a high probability large-horizon upper bound on the regret, which show that the regret grows logarithmically with time in an order sense. We also provide numerical results which establish that CoTS significantly outperforms the current state-of-the-art algorithms. 

   more » « less
4. Finite Time Logarithmic Regret Bounds for Self-Tuning Regulation

   Singh, R; Mete, A; Kar, A; Kumar, P R (July 2024, Proceedings of the 41st International Conference on Machine Learning)

   We establish the first finite-time logarithmic regret bounds for the self-tuning regulation problem. We introduce a modified version of the certainty equivalence algorithm, which we call PIECE, that clips inputs in addition to utilizing probing inputs for exploration. We show that it has a ClogT upper bound on the regret after T time-steps for bounded noise, and Clog3T in the case of sub-Gaussian noise, unlike the LQ problem where logarithmic regret is shown to be not possible. The PIECE algorithm is also designed to address the critical challenge of poor initial transient performance of reinforcement learning algorithms for linear systems. Comparative simulation results illustrate the improved performance of PIECE. 

   more » « less
5. Power of Hints for Online Learning with Movement Costs

   Bhaskara, Aditya; Cutkosky, Ashok; Kumar, Ravi; Purohit, Manish (January 2021, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics)

   We consider the online linear optimization problem with movement costs, a variant of online learning in which the learner must not only respond to cost vectors c_t with points x_t in order to maintain low regret, but is also penalized for movement by an additional cost. Classically, simple algorithms that obtain the optimal sqrt(T) regret already are very stable and do not incur a significant movement cost. However, recent work has shown that when the learning algorithm is provided with weak "hint" vectors that have a positive correlation with the costs, the regret can be significantly improved to log(T). In this work, we study the stability of such algorithms, and provide matching upper and lower bounds showing that incorporating movement costs results in intricate tradeoffs logarithmic and sqrt(T) regret. 

   more » « less