  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.
