Cooperative Thresholded Lasso for Sparse Linear Bandit

• URL: http://arxiv.org/abs/2305.19161v1
• Date: Tue, 30 May 2023 16:05:44 GMT
• Title: Cooperative Thresholded Lasso for Sparse Linear Bandit
• Authors: Haniyeh Barghi, Xiaotong Cheng, Setareh Maghsudi
• Abstract summary: We present a novel approach to address the multi-agent sparse contextual linear bandit problem. It is first algorithm that tackles row-wise distributed data in sparse linear bandits. It is widely applicable to high-dimensional multi-agent problems where efficient feature extraction is critical for minimizing regret.
• Score: 6.52540785559241
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel approach to address the multi-agent sparse contextual linear bandit problem, in which the feature vectors have a high dimension $d$ whereas the reward function depends on only a limited set of features - precisely $s_0 \ll d$. Furthermore, the learning follows under information-sharing constraints. The proposed method employs Lasso regression for dimension reduction, allowing each agent to independently estimate an approximate set of main dimensions and share that information with others depending on the network's structure. The information is then aggregated through a specific process and shared with all agents. Each agent then resolves the problem with ridge regression focusing solely on the extracted dimensions. We represent algorithms for both a star-shaped network and a peer-to-peer network. The approaches effectively reduce communication costs while ensuring minimal cumulative regret per agent. Theoretically, we show that our proposed methods have a regret bound of order $\mathcal{O}(s_0 \log d + s_0 \sqrt{T})$ with high probability, where $T$ is the time horizon. To our best knowledge, it is the first algorithm that tackles row-wise distributed data in sparse linear bandits, achieving comparable performance compared to the state-of-the-art single and multi-agent methods. Besides, it is widely applicable to high-dimensional multi-agent problems where efficient feature extraction is critical for minimizing regret. To validate the effectiveness of our approach, we present experimental results on both synthetic and real-world datasets.

Related papers

• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  A network of $N$ agents communicate locally to minimize their collective regret while keeping their expected cost under a specified threshold $tau$. We propose a safe distributed upper confidence bound algorithm, so called textitMA-OPLB, and establish a high probability bound on its $T$-round regret. We show that our regret bound is of order $ mathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)
  arXiv  Detail & Related papers  (2024-10-22T19:34:53Z)
• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  The explosion of large-scale data has outstripped the processing capabilities of single-machine systems. Traditional approaches to distributed inference often struggle with achieving true sparsity in high-dimensional datasets. We propose a novel, two-stage, distributed best subset selection algorithm to address these issues.
  arXiv  Detail & Related papers  (2024-08-30T13:22:08Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities [12.104551746465932]
  We investigate safe multi-agent reinforcement learning, where agents seek to collectively maximize an aggregate sum of local objectives while satisfying their own safety constraints. Our algorithm converges to a first-order stationary point (FOSP) at the rate of $mathcalOleft(T-2/3right)$. In the sample-based setting, we demonstrate that, with high probability, our algorithm requires $widetildemathcalOleft(epsilon-3.5right)$ samples to achieve an $epsilon$-FOSP.
  arXiv  Detail & Related papers  (2023-05-27T20:08:35Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  We study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. We tackle this problem under the context of function approximation, leveraging powerful function approximators. We establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.
  arXiv  Detail & Related papers  (2021-10-19T07:26:33Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
  We study decentralized linear bandits, where a network of $N$ agents acts cooperatively to solve a linear bandit-optimization problem. We propose DLUCB: a fully decentralized algorithm that minimizes the cumulative regret over the entire network. We show that our ideas extend naturally to the emerging, albeit more challenging, setting of safe bandits.
  arXiv  Detail & Related papers  (2020-12-01T07:33:00Z)
• An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
  We introduce Coop-FTPL, a cooperative version of the well-known Follow The Perturbed Leader algorithm. We show that the expected regret of our algorithm after T time steps is of order QT log(k)(k$alpha$ 1 /Q + m), where Q is the total activation probability mass.
  arXiv  Detail & Related papers  (2020-10-05T07:08:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.