Linear Stochastic Bandits over a Bit-Constrained Channel

Aritra Mitra, Hamed Hassani, George J. Pappas
Proceedings of The 5th Annual Learning for Dynamics and Control Conference, PMLR 211:1387-1399, 2023.

Abstract

One of the primary challenges in large-scale distributed learning stems from stringent communication constraints. While several recent works address this challenge for static optimization problems, sequential decision-making under uncertainty has remained much less explored in this regard. Motivated by this gap, we introduce a new linear stochastic bandit formulation over a bit-constrained channel. Specifically, in our setup, an agent interacting with an environment transmits encoded estimates of an unknown model parameter to a server over a communication channel of finite capacity. The goal of the server is to take actions based on these estimates to minimize cumulative regret. To this end, we develop a novel and general algorithmic framework that hinges on two main components: (i) an adaptive encoding mechanism that exploits statistical concentration bounds, and (ii) a decision-making principle based on confidence sets that account for encoding errors. As our main result, we prove that when the unknown model is $d$-dimensional, a channel capacity of $O(d)$ bits suffices to achieve order-optimal regret. We also establish that for the simpler unstructured multi-armed bandit problem, $1$ bit channel capacity is sufficient for achieving optimal regret bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v211-mitra23a, title = {Linear Stochastic Bandits over a Bit-Constrained Channel}, author = {Mitra, Aritra and Hassani, Hamed and Pappas, George J.}, booktitle = {Proceedings of The 5th Annual Learning for Dynamics and Control Conference}, pages = {1387--1399}, year = {2023}, editor = {Matni, Nikolai and Morari, Manfred and Pappas, George J.}, volume = {211}, series = {Proceedings of Machine Learning Research}, month = {15--16 Jun}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v211/mitra23a/mitra23a.pdf}, url = {https://proceedings.mlr.press/v211/mitra23a.html}, abstract = {One of the primary challenges in large-scale distributed learning stems from stringent communication constraints. While several recent works address this challenge for static optimization problems, sequential decision-making under uncertainty has remained much less explored in this regard. Motivated by this gap, we introduce a new linear stochastic bandit formulation over a bit-constrained channel. Specifically, in our setup, an agent interacting with an environment transmits encoded estimates of an unknown model parameter to a server over a communication channel of finite capacity. The goal of the server is to take actions based on these estimates to minimize cumulative regret. To this end, we develop a novel and general algorithmic framework that hinges on two main components: (i) an adaptive encoding mechanism that exploits statistical concentration bounds, and (ii) a decision-making principle based on confidence sets that account for encoding errors. As our main result, we prove that when the unknown model is $d$-dimensional, a channel capacity of $O(d)$ bits suffices to achieve order-optimal regret. We also establish that for the simpler unstructured multi-armed bandit problem, $1$ bit channel capacity is sufficient for achieving optimal regret bounds.} }
Endnote
%0 Conference Paper %T Linear Stochastic Bandits over a Bit-Constrained Channel %A Aritra Mitra %A Hamed Hassani %A George J. Pappas %B Proceedings of The 5th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2023 %E Nikolai Matni %E Manfred Morari %E George J. Pappas %F pmlr-v211-mitra23a %I PMLR %P 1387--1399 %U https://proceedings.mlr.press/v211/mitra23a.html %V 211 %X One of the primary challenges in large-scale distributed learning stems from stringent communication constraints. While several recent works address this challenge for static optimization problems, sequential decision-making under uncertainty has remained much less explored in this regard. Motivated by this gap, we introduce a new linear stochastic bandit formulation over a bit-constrained channel. Specifically, in our setup, an agent interacting with an environment transmits encoded estimates of an unknown model parameter to a server over a communication channel of finite capacity. The goal of the server is to take actions based on these estimates to minimize cumulative regret. To this end, we develop a novel and general algorithmic framework that hinges on two main components: (i) an adaptive encoding mechanism that exploits statistical concentration bounds, and (ii) a decision-making principle based on confidence sets that account for encoding errors. As our main result, we prove that when the unknown model is $d$-dimensional, a channel capacity of $O(d)$ bits suffices to achieve order-optimal regret. We also establish that for the simpler unstructured multi-armed bandit problem, $1$ bit channel capacity is sufficient for achieving optimal regret bounds.
APA
Mitra, A., Hassani, H. & Pappas, G.J.. (2023). Linear Stochastic Bandits over a Bit-Constrained Channel. Proceedings of The 5th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 211:1387-1399 Available from https://proceedings.mlr.press/v211/mitra23a.html.

Related Material