Tight Regret Bounds for Bilateral Trade under Semi Feedback

• URL: http://arxiv.org/abs/2601.16412v1
• Date: Fri, 23 Jan 2026 02:58:29 GMT
• Title: Tight Regret Bounds for Bilateral Trade under Semi Feedback
• Authors: Yaonan Jin,
• Abstract summary: We find an $widetildeO(T2 / 3)$-regret mechanism, matching the $(T2 / 3)$ lower bound from [CJLZ25] up to polylogarithmic factors.
• Score: 0.805458491503507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The study of \textit{regret minimization in fixed-price bilateral trade} has received considerable attention in recent research. Previous works [CCC+24a, CCC+24b, AFF24, BCCF24, CJLZ25, LCM25a, GDFS25] have acquired a thorough understanding of the problem, except for determining the tight regret bound for GBB semi-feedback fixed-price mechanisms under adversarial values. In this paper, we resolve this open question by devising an $\widetilde{O}(T^{2 / 3})$-regret mechanism, matching the $Ω(T^{2 / 3})$ lower bound from [CJLZ25] up to polylogarithmic factors.

Related papers

• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  We study the statistical efficiency of online learning with respect to KL-regularized objectives.<n>We show that the KL-regularized regret for MABs is $$-independent and scales as $tilde(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-02T18:17:33Z)
• Optimal Lower Bounds for Online Multicalibration [9.852468478532652]
  We prove an $(T2/3)$ lower bound on expected multicalibration error using just three disjoint binary groups.<n>We then turn to lower bounds for the more difficult case of group functions that may depend on context but not on the learner's predictions.
  arXiv  Detail & Related papers  (2026-01-08T18:59:32Z)
• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II) [51.320599504997745]
  We show that when the number $K$ of communities remains smaller than $sqrtn$, non-trivial community recovery is possible in time above the Kesten--Stigum threshold.<n>We also show that, in moderately sparse settings, the optimal algorithms appear to be fundamentally different from spectral methods.
  arXiv  Detail & Related papers  (2025-11-26T15:54:17Z)
• Tight Regret Bounds for Fixed-Price Bilateral Trade [9.12082890580808]
  We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization.<n>For independent values, a near-optimal $widetildeTheta(T2/3)$ tight bound for $textsfGlobal Budget Balance$ fixed-price mechanisms with two-bit/one-bit feedback.<n>For correlated/adversarial values, a near-optimal $Omega(T3/4)$ lower bound for $textsfGlobal Budget Balance$ fixed-price mechanisms with two-bit/one-bit feedback.
  arXiv  Detail & Related papers  (2025-04-06T03:56:42Z)
• 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)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  We prove lower bounds for computing a near-optimal $T$-sparse CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in time.
  arXiv  Detail & Related papers  (2024-11-04T00:34:56Z)
• An $α$-regret analysis of Adversarial Bilateral Trade [10.275531964940425]
  We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary. We consider gain from trade which is harder to approximate than social welfare.
  arXiv  Detail & Related papers  (2022-10-13T08:57:30Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  We establish efficient and uncoupled learning dynamics so that the trigger regret of each player grows as $O(log T)$ after $T$ repetitions of play. This improves exponentially over the prior best known trigger-regret bound of $O(T1/4)$.
  arXiv  Detail & Related papers  (2022-08-20T20:48:58Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  We show that it is possible to obtain regret scaling as $mathcalO(sqrtV_1star K)$ in reinforcement learning with large state spaces. We demonstrate that existing techniques based on at least squares estimation are insufficient to obtain this result.
  arXiv  Detail & Related papers  (2021-12-07T00:29:57Z)
• Bilateral Trade: A Regret Minimization Perspective [5.031063690574698]
  We cast the bilateral trade problem in a regret minimization framework over $T$ rounds of seller/buyer interactions. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different feedback models and private valuations.
  arXiv  Detail & Related papers  (2021-09-08T22:11:48Z)
• A Regret Analysis of Bilateral Trade [5.031063690574698]
  We cast for the first time the bilateral trade problem in a regret minimization framework over rounds of seller/buyer interactions. Our main contribution is a complete characterization of the regret regimes for fixedprice mechanisms with different models of feedback and private valuations.
  arXiv  Detail & Related papers  (2021-02-16T08:53:17Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

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.