6 papers · 1 filter
The Query Complexity of Uniform Pricing
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the \textit{pricing query complexity} problem in Mechanism Design. The previou…
Improved sampling algorithms and functional inequalities for non-log-concave distributions
Yuchen He, Zhehan Lei, Jianan Shao +1
We study the problem of sampling from a distribution with density for some potential function with query access to and $\nabla…
On the Problem of Best Arm Retention
Houshuang Chen, Yuchen He, Chihao Zhang
This paper presents a comprehensive study on the problem of Best Arm Retention (BAR), which has recently found applications in streaming algorithms for multi-armed bandits. In the…
Tight Regret Bounds for Fixed-Price Bilateral Trade
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetildeΘ(…
Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
Zichun Ye, Chihao Zhang, Jiahao Zhao
We study the problem of minimizing gap-dependent regret for single-pass streaming stochastic multi-armed bandits (MAB). In this problem, the arms are present in a stream, and a…
On the query complexity of sampling from non-log-concave distributions
Yuchen He, Chihao Zhang
We study the problem of sampling from a -dimensional distribution with density , which does not necessarily satisfy good isoperimetric conditions. Specifi…