# A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design

arXiv: https://arxiv.org/abs/2210.10278 · HTML: https://mlsanity.com/paper/2210.10278/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 19 Oct 2022.

## Builds on (most cited first, 23 of 23)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [Deep Reinforcement Learning for Sponsored Search Real-time Bidding](https://mlsanity.com/paper/1803.00259/) (2018)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Dynamic Pricing with Demand Covariates](https://mlsanity.com/paper/1604.07463/) (2016)
- [Policy Optimization Using Semi-parametric Models for Dynamic Pricing](https://mlsanity.com/paper/2109.06368/) (2021)
- [Semi-parametric dynamic contextual pricing](https://mlsanity.com/paper/1901.02045/) (2019)
- [Multi-Product Dynamic Pricing in High-Dimensions with Heterogeneous Price Sensitivity](https://mlsanity.com/paper/1901.01030/) (2019)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [No-Regret Learning in Partially-Informed Auctions](https://mlsanity.com/paper/2202.10606/) (2022)
- [Reserve Pricing in Repeated Second-Price Auctions with Strategic Bidders](https://mlsanity.com/paper/1906.09331/) (2019)
- [Dynamic Pricing and Demand Learning on a Large Network of Products: A PAC-Bayesian Approach](https://mlsanity.com/paper/2111.00790/) (2021)

## Built on by (most cited first, 1 of 1)

- [Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2402.19420/) (2024)

## Abstract (arXiv)

We study reserve price optimization in multi-phase second price auctions, where the seller's prior actions affect the bidders' later valuations through a Markov Decision Process (MDP). Compared to the bandit setting in existing works, the setting in ours involves three challenges. First, from the seller's perspective, we need to efficiently explore the environment in the presence of potentially untruthful bidders who aim to manipulate the seller's policy. Second, we want to minimize the seller's revenue regret when the market noise distribution is unknown. Third, the seller's per-step revenue is an unknown, nonlinear random variable, and cannot even be directly observed from the environment but realized values. We propose a mechanism addressing all three challenges. To address the first challenge, we use a combination of a new technique named "buffer periods" and inspirations from Reinforcement Learning (RL) with low switching cost to limit bidders' surplus from untruthful bidding, thereby incentivizing approximately truthful bidding. The second one is tackled by a novel algorithm that removes the need for pure exploration when the market noise distribution is unknown. The third challenge is resolved by an extension of LSVI-UCB, where we use the auction's underlying structure to control the uncertainty of the revenue function. The three techniques culminate in the Contextual-LSVI-UCB-Buffer (CLUB) algorithm which achieves tildeO(H5/2√K) revenue regret, where K is the number of episodes and H is the length of each episode, when the market noise is known and tildeO(H3√K) revenue regret when the noise is unknown with no assumptions on bidders' truthfulness.