Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

• URL: http://arxiv.org/abs/2608.10526v1
• Date: Tue, 11 Aug 2026 06:06:12 GMT
• Title: Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits
• Abstract summary: We study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown.<n>We consider three information structures: (A)unobserved actions with common rewards, (B)observed actions with independent rewards, and (C)unobserved actions with independent rewards.
• Score: 1.3700362496838856
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by decentralized applications, we study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown. We consider three information structures: (A)~unobserved actions with common rewards, (B)~observed actions with independent rewards, and (C)~unobserved actions with independent rewards. In each case we design and analyze an algorithm that estimates the Lipschitz constant, chooses a discretization of the joint action space, and applies a cooperative bandit method to the induced discrete problem. Players never communicate once learning starts, so the central difficulty is that they must reach the \emph{same} discretization from their own data. We prove regret guarantees showing that common rewards and observable actions each supply this agreement for free, and that in their absence agreement can still be bought, through a dithered quantization of the estimate, at no cost in the leading order of the regret.

Related papers

• The Price of Decentralization in Top-$K$ Arm Identification [1.3700362496838856]
  We study top-$K$ joint-arm identification in multi-agent multi-armed bandits.<n>Agents simultaneously choose individual actions that compose a joint arm.<n>We show that shared-reward identification is optimal up to one universal logarithmic factor.
  arXiv  Detail & Related papers  (2026-08-22T22:22:06Z)
• Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry [1.1689657956099038]
  We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes.<n>We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates.
  arXiv  Detail & Related papers  (2026-08-11T06:10:42Z)
• Latent Order Bandits [11.231384213521489]
  Bandit algorithms solve diverse sequential decision-making problems, but are often too sample-inefficient for from-scratch personalization.<n>We propose latent order bandits (LOB), relaxing the assumptions of latent bandits to require only prior knowledge of a partial order of action preferences in each state.<n>LOB allows instances of the same state to vary in reward distributions, as long as the partial order of actions is shared.
  arXiv  Detail & Related papers  (2026-05-08T06:15:21Z)
• Multi-Agent Lipschitz Bandits [7.465238700168576]
  We study the decentralized multi-player bandit problem over a continuous, Lipschitz-structured action space.<n>We propose a protocol that decouples the problem into $N$ independent single-player Lipschitz bandits.<n>We establish a near-optimal regret bound of $tildeO(T(d+1)/(d+2))$ plus a $T$-independent coordination cost, matching the single-player rate.
  arXiv  Detail & Related papers  (2026-02-18T23:58:36Z)
• Incentivized Lipschitz Bandits [7.465238700168576]
  We study incentivized exploration in multi-armed bandit (MAB) settings with infinitely many arms modeled as elements in continuous metric spaces.<n>We propose novel incentivized exploration algorithms that discretize the infinite arm space uniformly and demonstrate that these algorithms simultaneously achieve sublinear cumulative regret and sublinear total compensation.
  arXiv  Detail & Related papers  (2025-08-26T22:54:29Z)
• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback.<n>This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc.<n>Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  We study EgalMAB, an egalitarian assignment problem in the context of multi-armed bandits. We design and analyze a UCB-based policy EgalUCB and establish upper bounds on the cumulative regret.
  arXiv  Detail & Related papers  (2024-10-08T09:49:47Z)
• Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback [11.262167746929332]
  Restless multi-armed bandits (RMAB) play a central role in modeling sequential decision making problems. In this paper, we consider the task of learning in episodic RMAB with unknown transition functions and adversarial rewards. We develop a novel reinforcement learning algorithm with two key contributors.
  arXiv  Detail & Related papers  (2024-05-02T02:20:19Z)
• Reward Imputation with Sketching for Contextual Batched Bandits [48.80803376405073]
  Contextual batched bandit (CBB) is a setting where a batch of rewards is observed from the environment at the end of each episode. Existing approaches for CBB often ignore the rewards of the non-executed actions, leading to underutilization of feedback information. We propose Sketched Policy Updating with Imputed Rewards (SPUIR) that completes the unobserved rewards using sketching.
  arXiv  Detail & Related papers  (2022-10-13T04:26:06Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  Intrinsic rewards play a central role in handling the exploration-exploitation trade-off. We introduce emphanti-concentrated confidence bounds for efficiently approximating the elliptical bonus. We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic rewards on Atari benchmarks.
  arXiv  Detail & Related papers  (2021-10-21T15:25:15Z)
• Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
  We formalize decision-making problems with querying budget. We consider multi-armed bandits, linear bandits, and reinforcement learning problems. We show that CBM based algorithms perform well in the presence of adversity.
  arXiv  Detail & Related papers  (2021-02-05T19:56:31Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  Lipschitz bandits is a prominent version of multi-armed bandits that studies large, structured action spaces.<n>A central theme here is the adaptive discretization of the action space, which gradually zooms in'' on the more promising regions.<n>We provide the first algorithm for adaptive discretization in the adversarial version, and derive instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-06-22T16:06:25Z)

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.