# A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 8 Jul 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [Learning Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2403.03672/) (2024)
- [Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study](https://mlsanity.com/paper/1709.03465/) (2017)
- [A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraints](https://mlsanity.com/paper/2304.14326/) (2023)
- [Markov Persuasion Processes: Learning to Persuade from Scratch](https://mlsanity.com/paper/2402.03077/) (2024)
- [Dynamic Pricing on E-commerce Platform with Deep Reinforcement Learning: A Field Experiment](https://mlsanity.com/paper/1912.02572/) (2019)
- [Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints](https://mlsanity.com/paper/2405.14372/) (2024)
- [Thompson Sampling for Dynamic Pricing](https://mlsanity.com/paper/1802.03050/) (2018)

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

- [Online Dynamic Pricing of Complementary Products](https://mlsanity.com/paper/2511.22291/) (2025)

## Abstract (arXiv)

We address the challenging problem of dynamically pricing complementary items that are sequentially displayed to customers. An illustrative example is the online sale of flight tickets, where customers navigate through multiple web pages. Initially, they view the ticket cost, followed by ancillary expenses such as insurance and additional luggage fees. Coherent pricing policies for complementary items are essential because optimizing the pricing of each item individually is ineffective. Our scenario also involves a sales constraint, which specifies a minimum number of items to sell, and uncertainty regarding customer demand curves. To tackle this problem, we originally formulate it as a Markov Decision Process with constraints. Leveraging online learning tools, we design a primal-dual online optimization algorithm. We empirically evaluate our approach using synthetic settings randomly generated from real-world data, covering various configurations from stationary to non-stationary, and compare its performance in terms of constraints violation and regret against well-known baselines optimizing each state singularly.