# Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 43 references that are in the map.
- First posted on arXiv 25 Feb 2022.

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

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Nonstationary Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2010.04244/) (2020)
- [On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2110.09771/) (2021)
- [Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2011.13034/) (2020)

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

- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [STRIDE: A Tool-Assisted LLM Agent Framework for Strategic and Interactive Decision-Making](https://mlsanity.com/paper/2405.16376/) (2024)
- [Modeling Recommender Ecosystems: Research Challenges at the Intersection of Mechanism Design, Reinforcement Learning and Generative Models](https://mlsanity.com/paper/2309.06375/) (2023)
- [Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning](https://mlsanity.com/paper/2205.02450/) (2022)
- [Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments](https://mlsanity.com/paper/2506.19038/) (2025)

## Abstract (arXiv)

Dynamic mechanism design studies how mechanism designers should allocate resources among agents in a time-varying environment. We consider the problem where the agents interact with the mechanism designer according to an unknown Markov Decision Process (MDP), where agent rewards and the mechanism designer's state evolve according to an episodic MDP with unknown reward functions and transition kernels. We focus on the online setting with linear function approximation and propose novel learning algorithms to recover the dynamic Vickrey-Clarke-Grove (VCG) mechanism over multiple rounds of interaction. A key contribution of our approach is incorporating reward-free online Reinforcement Learning (RL) to aid exploration over a rich policy space to estimate prices in the dynamic VCG mechanism. We show that the regret of our proposed method is upper bounded by tildeO(T2/3) and further devise a lower bound to show that our algorithm is efficient, incurring the same Omega(T2 / 3) regret as the lower bound, where T is the total number of rounds. Our work establishes the regret guarantee for online RL in solving dynamic mechanism design problems without prior knowledge of the underlying model.